Canonical forms and automorphisms for linear codes over finite fields¶
We implemented the algorithm described in [Feu2009] which computes, a unique
code (canonical form) in the equivalence class of a given
linear code . Furthermore, this algorithm will return the
automorphism group of
, too. You will find more details about the algorithm
in the documentation of the class
LinearCodeAutGroupCanLabel
.
The equivalence of codes is modeled as a group action by the group
on the set
of subspaces of
. The group
will be called the
semimonomial group of degree
.
The algorithm is started by initializing the class
LinearCodeAutGroupCanLabel
.
When the object gets available, all computations are already finished and
you can access the relevant data using the member functions:
People do also use some weaker notions of equivalence, namely
permutational equivalence and monomial equivalence (linear isometries).
These can be seen as the subgroups and
of
.
If you are interested in one of these notions, you can just pass
the optional parameter
algorithm_type
.
A second optional parameter P
allows you to restrict the
group of permutations to a subgroup which respects the coloring given
by
P
.
AUTHORS:
- Thomas Feulner (2012-11-15): initial version
REFERENCES:
[Feu2009] | T. 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, Nov 2009 |
EXAMPLES:
sage: from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel
sage: C = codes.HammingCode(GF(3), 3).dual_code()
sage: P = LinearCodeAutGroupCanLabel(C)
sage: P.get_canonical_form().generator_matrix()
[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: LinearCode(P.get_transporter()*C.generator_matrix()) == P.get_canonical_form()
True
sage: A = P.get_autom_gens()
sage: all( [ LinearCode(a*C.generator_matrix()) == C for a in A])
True
sage: P.get_autom_order() == GL(3, GF(3)).order()
True
If the dimension of the dual code is smaller, we will work on this code:
sage: C2 = codes.HammingCode(GF(3), 3)
sage: P2 = LinearCodeAutGroupCanLabel(C2)
sage: P2.get_canonical_form().parity_check_matrix() == P.get_canonical_form().generator_matrix()
True
There is a specialization of this algorithm to pass a coloring on the coordinates. This is just a list of lists, telling the algorithm which columns do share the same coloring:
sage: C = codes.HammingCode(GF(4, 'a'), 3).dual_code()
sage: P = LinearCodeAutGroupCanLabel(C, P=[ [0], [1], range(2, C.length()) ])
sage: P.get_autom_order()
864
sage: A = [a.get_perm() for a in P.get_autom_gens()]
sage: H = SymmetricGroup(21).subgroup(A)
sage: H.orbits()
[[1], [2], [3, 5, 4], [6, 10, 13, 20, 17, 9, 8, 11, 18, 15, 14, 16, 12, 19, 21, 7]]
We can also restrict the group action to linear isometries:
sage: P = LinearCodeAutGroupCanLabel(C, algorithm_type="linear")
sage: P.get_autom_order() == GL(3, GF(4, 'a')).order()
True
and to the action of the symmetric group only:
sage: P = LinearCodeAutGroupCanLabel(C, algorithm_type="permutational")
sage: P.get_autom_order() == C.permutation_automorphism_group().order()
True
-
class
sage.coding.codecan.autgroup_can_label.
LinearCodeAutGroupCanLabel
(C, P=None, algorithm_type='semilinear')¶ Canonical representatives and automorphism group computation for linear codes over finite fields.
There are several notions of equivalence for linear codes: Let
,
be linear codes of length
and dimension
.
and
are said to be
- permutational equivalent, if there is some permutation
such that
for all
.
- linear equivalent, if there is some permutation
and a vector
of units of length
such that
for all
.
- semilinear equivalent, if there is some permutation
, a vector
of units of length
and a field automorphism
such that
for all
.
These are group actions. This class provides an algorithm that will compute a unique representative
in the orbit of the given linear code
. Furthermore, the group element
with
and the automorphism group of
will be computed as well.
There is also the possibility to restrict the permutational part of this action to a Young subgroup of
. This could be achieved by passing a partition
(as a list of lists) of the set
. This is an option which is also available in the computation of a canonical form of a graph, see
sage.graphs.generic_graph.GenericGraph.canonical_label()
.EXAMPLES:
sage: from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel sage: C = codes.HammingCode(GF(3), 3).dual_code() sage: P = LinearCodeAutGroupCanLabel(C) sage: P.get_canonical_form().generator_matrix() [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: LinearCode(P.get_transporter()*C.generator_matrix()) == P.get_canonical_form() True sage: a = P.get_autom_gens()[0] sage: (a*C.generator_matrix()).echelon_form() == C.generator_matrix().echelon_form() True sage: P.get_autom_order() == GL(3, GF(3)).order() True
-
get_PGammaL_gens
()¶ Return the set of generators translated to the group
.
There is a geometric point of view of code equivalence. A linear code is identified with the multiset of points in the finite projective geometry
. The equivalence of codes translates to the natural action of
. Therefore, we may interpret the group as a subgroup of
as well.
EXAMPLES:
sage: from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel sage: C = codes.HammingCode(GF(4, 'a'), 3).dual_code() sage: A = LinearCodeAutGroupCanLabel(C).get_PGammaL_gens() sage: Gamma = C.generator_matrix() sage: N = [ x.monic() for x in Gamma.columns() ] sage: all([ (g[0]*n.apply_map(g[1])).monic() in N for n in N for g in A]) True
-
get_PGammaL_order
()¶ Return the size of the automorphism group as a subgroup of
.
There is a geometric point of view of code equivalence. A linear code is identified with the multiset of points in the finite projective geometry
. The equivalence of codes translates to the natural action of
. Therefore, we may interpret the group as a subgroup of
as well.
EXAMPLES:
sage: from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel sage: C = codes.HammingCode(GF(4, 'a'), 3).dual_code() sage: LinearCodeAutGroupCanLabel(C).get_PGammaL_order() == GL(3, GF(4, 'a')).order()*2/3 True
-
get_autom_gens
()¶ Return a generating set for the automorphism group of the code.
EXAMPLES:
sage: from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel sage: C = codes.HammingCode(GF(2), 3).dual_code() sage: A = LinearCodeAutGroupCanLabel(C).get_autom_gens() sage: Gamma = C.generator_matrix().echelon_form() sage: all([(g*Gamma).echelon_form() == Gamma for g in A]) True
-
get_autom_order
()¶ Return the size of the automorphism group of the code.
EXAMPLES:
sage: from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel sage: C = codes.HammingCode(GF(2), 3).dual_code() sage: LinearCodeAutGroupCanLabel(C).get_autom_order() 168
-
get_canonical_form
()¶ Return the canonical orbit representative we computed.
EXAMPLES:
sage: from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel sage: C = codes.HammingCode(GF(3), 3).dual_code() sage: CF1 = LinearCodeAutGroupCanLabel(C).get_canonical_form() sage: s = SemimonomialTransformationGroup(GF(3), C.length()).an_element() sage: C2 = LinearCode(s*C.generator_matrix()) sage: CF2 = LinearCodeAutGroupCanLabel(C2).get_canonical_form() sage: CF1 == CF2 True
-
get_transporter
()¶ Return the element which maps the code to its canonical form.
EXAMPLES:
sage: from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel sage: C = codes.HammingCode(GF(2), 3).dual_code() sage: P = LinearCodeAutGroupCanLabel(C) sage: g = P.get_transporter() sage: D = P.get_canonical_form() sage: (g*C.generator_matrix()).echelon_form() == D.generator_matrix().echelon_form() True
- permutational equivalent, if there is some permutation