Canonical forms and automorphism group computation for linear codes over finite fields¶
We implemented the algorithm described in [Feu2009] which computes the unique
semilinearly isometric code (canonical form) in the equivalence class of a given
linear code C
. Furthermore, this algorithm will return the automorphism
group of C
, too.
The algorithm should be started via a further class
LinearCodeAutGroupCanLabel
.
This class removes duplicated columns (up to multiplications
by units) and zero columns. Hence, we can suppose that the input for the algorithm
developed here is a set of points in \(PG(k-1, q)\).
The implementation is based on the class
sage.groups.perm_gps.partn_ref2.refinement_generic.PartitionRefinement_generic
.
See the description of this algorithm in
sage.groups.perm_gps.partn_ref2.refinement_generic
.
In the language given there, we have to implement the group action of
\(G = (GL(k,q) \times {\GF{q}^*}^n ) \rtimes Aut(\GF{q})\) on the set \(X =
(\GF{q}^k)^n\) of \(k \times n\) matrices over \(\GF{q}\) (with the above
restrictions).
The derived class here implements the stabilizers \(G_{\Pi^{(I)}(x)}\) of the projections \(\Pi^{(I)}(x)\) of \(x\) to the coordinates specified in the sequence \(I\). Furthermore, we implement the inner minimization, i.e. the computation of a canonical form of the projection \(\Pi^{(I)}(x)\) under the action of \(G_{\Pi^{(I^{(i-1)})}(x)}\) . Finally, we provide suitable homomorphisms of group actions for the refinements and methods to compute the applied group elements in \(G \rtimes S_n\).
The algorithm also uses Jeffrey Leon’s idea of maintaining an
invariant set of codewords which is computed in the beginning, see
_init_point_hyperplane_incidence()
.
An example for such a set is the set of all codewords of weight \(\leq w\) for
some uniquely defined \(w\). In our case, we interpret the codewords as a set of
hyperplanes (via the corresponding information word) and compute invariants of
the bipartite, colored derived subgraph of the point-hyperplane incidence graph,
see PartitionRefinementLinearCode._point_refine()
and
PartitionRefinementLinearCode._hyp_refine()
.
Since we are interested in subspaces (linear codes) instead of matrices, our
group elements returned in
PartitionRefinementLinearCode.get_transporter()
and
PartitionRefinementLinearCode.get_autom_gens()
will be elements in the group
\(({\GF{q}^*}^n \rtimes Aut(\GF{q})) \rtimes S_n =
({\GF{q}^*}^n \rtimes (Aut(\GF{q}) \times S_n)\).
AUTHORS:
Thomas Feulner (2012-11-15): initial version
REFERENCES:
[Feu2009]
EXAMPLES:
Get the canonical form of the Simplex code:
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode
sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix()
sage: P = PartitionRefinementLinearCode(mat.ncols(), mat)
sage: cf = P.get_canonical_form(); cf
[1 0 0 0 0 1 1 1 1 1 1 1 1]
[0 1 0 1 1 0 0 1 1 2 2 1 2]
[0 0 1 1 2 1 2 1 2 1 2 0 0]
The transporter element is a group element which maps the input to its canonical form:
sage: cf.echelon_form() == (P.get_transporter() * mat).echelon_form()
True
The automorphism group of the input, i.e. the stabilizer under this group action, is returned by generators:
sage: P.get_autom_order_permutation() == GL(3, GF(3)).order()/(len(GF(3))-1)
True
sage: A = P.get_autom_gens()
sage: all((a*mat).echelon_form() == mat.echelon_form() for a in A)
True
-
class
sage.coding.codecan.codecan.
InnerGroup
¶ Bases:
object
This class implements the stabilizers \(G_{\Pi^{(I)}(x)}\) described in
sage.groups.perm_gps.partn_ref2.refinement_generic
with \(G = (GL(k,q) \times \GF{q}^n ) \rtimes Aut(\GF{q})\).Those stabilizers can be stored as triples:
rank
- an integer in \(\{0, \ldots, k\}\)row_partition
- a partition of \(\{0, \ldots, k-1\}\) withdiscrete cells for all integers \(i \geq rank\).
frob_pow
an integer in \(\{0, \ldots, r-1\}\) if \(q = p^r\)
The group \(G_{\Pi^{(I)}(x)}\) contains all elements \((A, \varphi, \alpha) \in G\), where
\(A\) is a \(2 \times 2\) blockmatrix, whose upper left matrix is a \(k \times k\) diagonal matrix whose entries \(A_{i,i}\) are constant on the cells of the partition
row_partition
. The lower left matrix is zero. And the right part is arbitrary.The support of the columns given by \(i \in I\) intersect exactly one cell of the partition. The entry \(\varphi_i\) is equal to the entries of the corresponding diagonal entry of \(A\).
- \(\alpha\) is a power of \(\tau^{frob_pow}\), where \(\tau\) denotes the
Frobenius automorphism of the finite field \(\GF{q}\).
See [Feu2009] for more details.
-
column_blocks
(mat)¶ Let
mat
be a matrix which is stabilized byself
having no zero columns. We know that for each column ofmat
there is a uniquely defined cell inself.row_partition
having a nontrivial intersection with the support of this particular column.This function returns a partition (as list of lists) of the columns indices according to the partition of the rows given by
self
.EXAMPLES:
sage: from sage.coding.codecan.codecan import InnerGroup sage: I = InnerGroup(3) sage: mat = Matrix(GF(3), [[0,1,0],[1,0,0], [0,0,1]]) sage: I.column_blocks(mat) [[1], [0], [2]]
-
get_frob_pow
()¶ Return the power of the Frobenius automorphism which generates the corresponding component of
self
.EXAMPLES:
sage: from sage.coding.codecan.codecan import InnerGroup sage: I = InnerGroup(10) sage: I.get_frob_pow() 1
-
class
sage.coding.codecan.codecan.
PartitionRefinementLinearCode
¶ Bases:
sage.groups.perm_gps.partn_ref2.refinement_generic.PartitionRefinement_generic
See
sage.coding.codecan.codecan
.EXAMPLES:
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P = PartitionRefinementLinearCode(mat.ncols(), mat) sage: cf = P.get_canonical_form(); cf [1 0 0 0 0 1 1 1 1 1 1 1 1] [0 1 0 1 1 0 0 1 1 2 2 1 2] [0 0 1 1 2 1 2 1 2 1 2 0 0]
sage: cf.echelon_form() == (P.get_transporter() * mat).echelon_form() True
sage: P.get_autom_order_permutation() == GL(3, GF(3)).order()/(len(GF(3))-1) True sage: A = P.get_autom_gens() sage: all((a*mat).echelon_form() == mat.echelon_form() for a in A) True
-
get_autom_gens
()¶ Return generators of the automorphism group of the initial matrix.
EXAMPLES:
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P = PartitionRefinementLinearCode(mat.ncols(), mat) sage: A = P.get_autom_gens() sage: all((a*mat).echelon_form() == mat.echelon_form() for a in A) True
-
get_autom_order_inner_stabilizer
()¶ Return the order of the stabilizer of the initial matrix under the action of the inner group \(G\).
EXAMPLES:
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P = PartitionRefinementLinearCode(mat.ncols(), mat) sage: P.get_autom_order_inner_stabilizer() 2 sage: mat2 = Matrix(GF(4, 'a'), [[1,0,1], [0,1,1]]) sage: P2 = PartitionRefinementLinearCode(mat2.ncols(), mat2) sage: P2.get_autom_order_inner_stabilizer() 6
-
get_canonical_form
()¶ Return the canonical form for this matrix.
EXAMPLES:
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P1 = PartitionRefinementLinearCode(mat.ncols(), mat) sage: CF1 = P1.get_canonical_form() sage: s = SemimonomialTransformationGroup(GF(3), mat.ncols()).an_element() sage: P2 = PartitionRefinementLinearCode(mat.ncols(), s*mat) sage: CF1 == P2.get_canonical_form() True
-
get_transporter
()¶ Return the transporter element, mapping the initial matrix to its canonical form.
EXAMPLES:
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P = PartitionRefinementLinearCode(mat.ncols(), mat) sage: CF = P.get_canonical_form() sage: t = P.get_transporter() sage: (t*mat).echelon_form() == CF.echelon_form() True
-