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\}$$ 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)
[, , ]
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

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