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 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
-