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

REFERENCES:

[Feu2009](1, 2) Thomas Feulner, The Automorphism Groups of Linear Codes and Canonical Representatives of Their Semilinear Isometry Classes, Advances in Mathematics of Communications 3 (4), pp. 363-383, 2009.
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\} with
    discrete 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 by self having no zero columns. We know that for each column of mat there is a uniquely defined cell in self.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