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 .
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
on the set
of
matrices over
(with the above
restrictions).
The derived class here implements the stabilizers
of the projections
of
to
the coordinates specified in the sequence
. Furthermore, we implement
the inner minimization, i.e. the computation of a canonical form of
the projection
under the action of
.
Finally, we provide suitable homomorphisms of group actions for the refinements
and methods to compute the applied group elements in
.
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 for
some uniquely defined
. 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
.
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
described in
sage.groups.perm_gps.partn_ref2.refinement_generic
with.
Those stabilizers can be stored as triples:
rank
- an integer inrow_partition
- a partition ofwith
- discrete cells for all integers
.
frob_pow
an integer inif
The group
contains all elements
, where
is a
blockmatrix, whose upper left matrix is a
diagonal matrix whose entries
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
intersect exactly one cell of the partition. The entry
is equal to the entries of the corresponding diagonal entry of
.
is a power of
, where
denotes the
- Frobenius automorphism of the finite field
.
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
.
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
-