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 \(C \leq \GF{q}^n\). Furthermore, this algorithm will return the automorphism group of \(C\), 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 \(G = {\GF{q}^*}^n \rtimes (Aut(\GF{q}) \times S_n)\) on the set of subspaces of \(\GF{q}^n\) . The group \(G\) will be called the semimonomial group of degree \(n\).

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 \(S_n\) and \({\GF{q}^*}^n \rtimes S_n\) of \(G\). 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 \(S_n\) to a subgroup which respects the coloring given by P.

AUTHORS:

  • Thomas Feulner (2012-11-15): initial version

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

>>> from sage.all import *
>>> from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel
>>> C = codes.HammingCode(GF(Integer(3)), Integer(3)).dual_code()
>>> P = LinearCodeAutGroupCanLabel(C)
>>> 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]
>>> LinearCode(P.get_transporter()*C.generator_matrix()) == P.get_canonical_form()
True
>>> A = P.get_autom_gens()
>>> all(LinearCode(a*C.generator_matrix()) == C for a in A)
True
>>> P.get_autom_order() == GL(Integer(3), GF(Integer(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

>>> from sage.all import *
>>> C2 = codes.HammingCode(GF(Integer(3)), Integer(3))
>>> P2 = LinearCodeAutGroupCanLabel(C2)
>>> 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], list(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, 19, 16, 21, 9, 10, 15, 8, 20, 11, 14, 13, 7, 12, 18, 17))

>>> from sage.all import *
>>> C = codes.HammingCode(GF(Integer(4), 'a'), Integer(3)).dual_code()
>>> P = LinearCodeAutGroupCanLabel(C, P=[ [Integer(0)], [Integer(1)], list(range(Integer(2), C.length())) ])
>>> P.get_autom_order()
864
>>> A = [a.get_perm() for a in P.get_autom_gens()]
>>> H = SymmetricGroup(Integer(21)).subgroup(A)
>>> H.orbits()
((1,),
 (2,),
 (3, 5, 4),
 (6, 19, 16, 21, 9, 10, 15, 8, 20, 11, 14, 13, 7, 12, 18, 17))

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

>>> from sage.all import *
>>> P = LinearCodeAutGroupCanLabel(C, algorithm_type='linear')
>>> P.get_autom_order() == GL(Integer(3), GF(Integer(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

>>> from sage.all import *
>>> P = LinearCodeAutGroupCanLabel(C, algorithm_type='permutational')
>>> P.get_autom_order() == C.permutation_automorphism_group().order()
True
class sage.coding.codecan.autgroup_can_label.LinearCodeAutGroupCanLabel(C, P=None, algorithm_type='semilinear')[source]

Bases: object

Canonical representatives and automorphism group computation for linear codes over finite fields.

There are several notions of equivalence for linear codes: Let \(C\), \(D\) be linear codes of length \(n\) and dimension \(k\). The codes \(C\) and \(D\) are said to be

  • permutational equivalent, if there is some permutation \(\pi \in S_n\) such that \((c_{\pi(0)}, \ldots, c_{\pi(n-1)}) \in D\) for all \(c \in C\).

  • linear equivalent, if there is some permutation \(\pi \in S_n\) and a vector \(\phi \in {\GF{q}^*}^n\) of units of length \(n\) such that \((c_{\pi(0)} \phi_0^{-1}, \ldots, c_{\pi(n-1)} \phi_{n-1}^{-1}) \in D\) for all \(c \in C\).

  • semilinear equivalent, if there is some permutation \(\pi \in S_n\), a vector \(\phi\) of units of length \(n\) and a field automorphism \(\alpha\) such that \((\alpha(c_{\pi(0)}) \phi_0^{-1}, \ldots, \alpha( c_{\pi(n-1)}) \phi_{n-1}^{-1} ) \in D\) for all \(c \in C\).

These are group actions. This class provides an algorithm that will compute a unique representative \(D\) in the orbit of the given linear code \(C\). Furthermore, the group element \(g\) with \(g * C = D\) and the automorphism group of \(C\) will be computed as well.

There is also the possibility to restrict the permutational part of this action to a Young subgroup of \(S_n\). This could be achieved by passing a partition \(P\) (as a list of lists) of the set \(\{0, \ldots, n-1\}\). 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

>>> from sage.all import *
>>> from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel
>>> C = codes.HammingCode(GF(Integer(3)), Integer(3)).dual_code()
>>> P = LinearCodeAutGroupCanLabel(C)
>>> 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]
>>> LinearCode(P.get_transporter()*C.generator_matrix()) == P.get_canonical_form()
True
>>> a = P.get_autom_gens()[Integer(0)]
>>> (a*C.generator_matrix()).echelon_form() == C.generator_matrix().echelon_form()
True
>>> P.get_autom_order() == GL(Integer(3), GF(Integer(3))).order()
True
get_PGammaL_gens()[source]

Return the set of generators translated to the group \(P\Gamma L(k,q)\).

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 \(PG(k-1, q)\). The equivalence of codes translates to the natural action of \(P\Gamma L(k,q)\). Therefore, we may interpret the group as a subgroup of \(P\Gamma L(k,q)\) 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

>>> from sage.all import *
>>> from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel
>>> C = codes.HammingCode(GF(Integer(4), 'a'), Integer(3)).dual_code()
>>> A = LinearCodeAutGroupCanLabel(C).get_PGammaL_gens()
>>> Gamma = C.generator_matrix()
>>> N = [ x.monic() for x in Gamma.columns() ]
>>> all((g[Integer(0)]*n.apply_map(g[Integer(1)])).monic() in N for n in N for g in A)
True
get_PGammaL_order()[source]

Return the size of the automorphism group as a subgroup of \(P\Gamma L(k,q)\).

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 \(PG(k-1, q)\). The equivalence of codes translates to the natural action of \(P\Gamma L(k,q)\). Therefore, we may interpret the group as a subgroup of \(P\Gamma L(k,q)\) 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

>>> from sage.all import *
>>> from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel
>>> C = codes.HammingCode(GF(Integer(4), 'a'), Integer(3)).dual_code()
>>> LinearCodeAutGroupCanLabel(C).get_PGammaL_order() == GL(Integer(3), GF(Integer(4), 'a')).order()*Integer(2)/Integer(3)
True
get_autom_gens()[source]

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

>>> from sage.all import *
>>> from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel
>>> C = codes.HammingCode(GF(Integer(2)), Integer(3)).dual_code()
>>> A = LinearCodeAutGroupCanLabel(C).get_autom_gens()
>>> Gamma = C.generator_matrix().echelon_form()
>>> all((g*Gamma).echelon_form() == Gamma for g in A)
True
get_autom_order()[source]

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

>>> from sage.all import *
>>> from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel
>>> C = codes.HammingCode(GF(Integer(2)), Integer(3)).dual_code()
>>> LinearCodeAutGroupCanLabel(C).get_autom_order()
168
get_canonical_form()[source]

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

>>> from sage.all import *
>>> from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel
>>> C = codes.HammingCode(GF(Integer(3)), Integer(3)).dual_code()
>>> CF1 = LinearCodeAutGroupCanLabel(C).get_canonical_form()
>>> s = SemimonomialTransformationGroup(GF(Integer(3)), C.length()).an_element()
>>> C2 = LinearCode(s*C.generator_matrix())
>>> CF2 = LinearCodeAutGroupCanLabel(C2).get_canonical_form()
>>> CF1 == CF2
True
get_transporter()[source]

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

>>> from sage.all import *
>>> from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel
>>> C = codes.HammingCode(GF(Integer(2)), Integer(3)).dual_code()
>>> P = LinearCodeAutGroupCanLabel(C)
>>> g = P.get_transporter()
>>> D = P.get_canonical_form()
>>> (g*C.generator_matrix()).echelon_form() == D.generator_matrix().echelon_form()
True