Coverage for local/lib/python2.7/site-packages/sage/coding/codecan/autgroup_can_label.pyx : 94%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
r""" 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 :class:`~sage.coding.codecan.autgroup_can_label.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 :class:`~sage.coding.codecan.autgroup_can_label.LinearCodeAutGroupCanLabel`. When the object gets available, all computations are already finished and you can access the relevant data using the member functions:
* :meth:`~sage.coding.codecan.autgroup_can_label.LinearCodeAutGroupCanLabel.get_canonical_form`
* :meth:`~sage.coding.codecan.autgroup_can_label.LinearCodeAutGroupCanLabel.get_transporter`
* :meth:`~sage.coding.codecan.autgroup_can_label.LinearCodeAutGroupCanLabel.get_autom_gens`
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, 16, 8, 21, 12, 9, 13, 18, 11, 19, 15, 7, 20, 14, 17, 10]]
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 """ #***************************************************************************** # Copyright (C) 2012 Thomas Feulner <thomas.feulner@uni-bayreuth.de> # # Distributed under the terms of the GNU General Public License (GPL) # as published by the Free Software Foundation; either version 2 of # the License, or (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
r""" If ``p`` is a list of pairwise distinct coordinates in ``range(n)``, then this function returns the cyclic shift of the coordinates contained in ``p``, when acting on a vector of length `n`.
Note that the domain of a ``Permutation`` is ``range(1, n+1)``.
EXAMPLES::
sage: from sage.coding.codecan.autgroup_can_label import _cyclic_shift sage: p = _cyclic_shift(10, [2,7,4,1]); p [1, 3, 8, 4, 2, 6, 7, 5, 9, 10]
We prove that the action is as expected::
sage: t = list(range(10)) sage: p.action(t) [0, 2, 7, 3, 1, 5, 6, 4, 8, 9] """
r""" 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 :meth:`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 """
""" see :class:`LinearCodeAutGroupCanLabel`
INPUT:
- ``C`` -- a linear code
- ``P`` (optional) -- a coloring of the coordinates i.e. a partition (list of disjoint lists) of [0 , ..., C.length()-1 ]
- ``algorithm_type`` (optional) -- which defines the acting group, either
* ``permutational``
* ``linear``
* ``semilinear``
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: P.get_canonical_form().generator_matrix() [1 0 0 0 1 1 1] [0 1 0 1 0 1 1] [0 0 1 1 1 1 0] sage: P2 = LinearCodeAutGroupCanLabel(C, P=[[0,3,5],[1,2,4,6]], ....: algorithm_type="permutational") sage: P2.get_canonical_form().generator_matrix() [1 1 1 0 0 0 1] [0 1 0 1 1 0 1] [0 0 1 0 1 1 1] """
raise TypeError("%s is not a linear code"%C)
else:
else: # now we can start the main algorithm:
# the dimension of the code is smaller or equal than # the dimension of the dual code # in this case we work with the code itself.
# this command allows you some advanced debuging # it prints the backtrack tree -> must be activated when installing # pr._latex_view(title="MyTitle") #this will provide you some visual representation of what is going on
# it could happen (because of the recursive call, see `else`) that # the canonical form is the identity matrix # linear or semilinear if algorithm_type == "semilinear": A.append(S_short(autom=F.hom([F.gen() ** F.characteristic()]))) self._full_autom_order *= F.degree() for p in P_refined: m = [F.one()] * n m[p[0]] = F.gen() A.append(S_short(v=m)) self._full_autom_order *= (len(F) - 1) ** n # cyclic shift of all elements A.append(S_short(perm=_cyclic_shift(n, p))) else: # use the dual code for the computations # this might have zero columns or multiple columns, hence # we call this algorithm again.
pos = p.pop() perm[pos] = next(it) + 1
""" In order to call the algorithm described in :class:`PartitionRefinementLinearCode` we remove zero columns and multiple occurrences of the same column (up to normalization).
This function computes a set of generators for the allowed permutations of such a block of equal columns (depending on the partition). If ``zero_column_case==True`` we also add a generator for the multiplication by units. Furthermore, we return the order of this group.
INPUT:
- ``normalization`` -- an element in the semimonomial transformation group `S`
- ``normalization_inverse`` -- the inverse of ``normalization``
- ``col2pos`` -- a list of disjoint indices in ``range(n)``
- ``col2P`` -- an increasing list of integers, with ``len(col2P) == len(col2pos)`` with ``col2P[i] == col2P[j]`` if and only if the indices ``col2pos[i]`` and ``col2pos[j]`` are in the same partition
- ``zero_column_case`` (boolean) -- set to ``True`` iff we are dealing with the zero column
OUTPUT:
- a list of generators in `S`
- the order of this group
EXAMPLES::
sage: from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel sage: S = SemimonomialTransformationGroup(GF(3), 10) sage: s = S.one() sage: col2pos = [1,4,2,3,5] sage: col2P = [1,1,3,3,3] sage: LinearCodeAutGroupCanLabel._compute_trivial_automs(s, s, col2pos, col2P, True) ([((1, 2, 1, 1, 1, 1, 1, 1, 1, 1); (), Ring endomorphism of Finite Field of size 3 Defn: 1 |--> 1), ((1, 1, 1, 1, 1, 1, 1, 1, 1, 1); (2,5), Ring endomorphism of Finite Field of size 3 Defn: 1 |--> 1), ((1, 1, 2, 1, 1, 1, 1, 1, 1, 1); (), Ring endomorphism of Finite Field of size 3 Defn: 1 |--> 1), ((1, 1, 1, 1, 1, 1, 1, 1, 1, 1); (3,4), Ring endomorphism of Finite Field of size 3 Defn: 1 |--> 1), ((1, 1, 1, 1, 1, 1, 1, 1, 1, 1); (3,4,6), Ring endomorphism of Finite Field of size 3 Defn: 1 |--> 1)], 384) """
else:
# we append a transposition of the first two elements # we append a cycle on all elements
""" In order to call the algorithm described in :class:`sage.coding.codecan.codecan.PartitionRefinementLinearCode` we removed zero columns and multiple occurrences of the same column (up to normalization). This function lifts the generators ``gens`` which were returned to their full length.
INPUT:
- ``gens`` -- a list of semimonomial transformation group elements of length `m`
- ``normalization`` -- a semimonomial transformation of length `n`
- ``normalization_inverse`` -- the inverse of ``normalization``
- ``col2pos`` -- a partition of ``range(n)`` into `m` disjoint sets, given as a list of lists. The elements `g` in ``gens`` are only allowed to permute entries of ``col2pos`` of equal length.
OUTPUT:
- a list of semimonomial transformations containing ``normalization`` which are the lifts of the elements in ``gens``
EXAMPLES::
sage: from sage.coding.codecan.autgroup_can_label import LinearCodeAutGroupCanLabel sage: S = SemimonomialTransformationGroup(GF(3), 10) sage: T = SemimonomialTransformationGroup(GF(3), 5) sage: s = S.one() sage: col2pos = [[1,4,2,3,5], [0],[6],[8],[7,9]] sage: gens = [T(perm=Permutation([1,3,4,2,5]), v=[2,1,1,1,1])] sage: LinearCodeAutGroupCanLabel._compute_PGammaL_automs(gens, s, s, col2pos) [((1, 2, 2, 2, 2, 2, 1, 1, 1, 1); (1,7,9), Ring endomorphism of Finite Field of size 3 Defn: 1 |--> 1)] """
""" 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 """
""" 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 """
""" 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 """
""" 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 """
r""" 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 """
r""" 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 """ |