# 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

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], 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, 9, 21, 10, 8, 15, 14, 11, 20, 13, 12, 7, 17, 18]]

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 $$C$$, $$D$$ be linear codes of length $$n$$ and dimension $$k$$. $$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
get_PGammaL_gens()

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
get_PGammaL_order()

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