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