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:
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(3, GF(3)).dual_code()
sage: P = LinearCodeAutGroupCanLabel(C)
sage: P.get_canonical_form().gen_mat()
[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.gen_mat()) == P.get_canonical_form()
True
sage: A = P.get_autom_gens()
sage: all( [ LinearCode(a*C.gen_mat()) == 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(3, GF(3))
sage: P2 = LinearCodeAutGroupCanLabel(C2)
sage: P2.get_canonical_form().check_mat() == P.get_canonical_form().gen_mat()
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(3, GF(4, 'a')).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
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(3, GF(3)).dual_code()
sage: P = LinearCodeAutGroupCanLabel(C)
sage: P.get_canonical_form().gen_mat()
[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.gen_mat()) == P.get_canonical_form()
True
sage: a = P.get_autom_gens()[0]
sage: (a*C.gen_mat()).echelon_form() == C.gen_mat().echelon_form()
True
sage: P.get_autom_order() == GL(3, GF(3)).order()
True
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(3, GF(4, 'a')).dual_code()
sage: A = LinearCodeAutGroupCanLabel(C).get_PGammaL_gens()
sage: Gamma = C.gen_mat()
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
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(3, GF(4, 'a')).dual_code()
sage: LinearCodeAutGroupCanLabel(C).get_PGammaL_order() == GL(3, GF(4, 'a')).order()*2/3
True
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(3, GF(2)).dual_code()
sage: A = LinearCodeAutGroupCanLabel(C).get_autom_gens()
sage: Gamma = C.gen_mat().echelon_form()
sage: all([(g*Gamma).echelon_form() == Gamma for g in A])
True
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(3, GF(2)).dual_code()
sage: LinearCodeAutGroupCanLabel(C).get_autom_order()
168
Return the canonical orbit representative we computed.
EXAMPLES:
sage: from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel
sage: C = codes.HammingCode(3, GF(3)).dual_code()
sage: CF1 = LinearCodeAutGroupCanLabel(C).get_canonical_form()
sage: s = SemimonomialTransformationGroup(GF(3), C.length()).an_element()
sage: C2 = LinearCode(s*C.gen_mat())
sage: CF2 = LinearCodeAutGroupCanLabel(C2).get_canonical_form()
sage: CF1 == CF2
True
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(3, GF(2)).dual_code()
sage: P = LinearCodeAutGroupCanLabel(C)
sage: g = P.get_transporter()
sage: D = P.get_canonical_form()
sage: (g*C.gen_mat()).echelon_form() == D.gen_mat().echelon_form()
True