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 automorphism group computation for linear codes over finite fields
We implemented the algorithm described in [Feu2009]_ which computes the unique semilinearly isometric code (canonical form) in the equivalence class of a given linear code ``C``. Furthermore, this algorithm will return the automorphism group of ``C``, too.
The algorithm should be started via a further class :class:`~sage.coding.codecan.autgroup_can_label.LinearCodeAutGroupCanLabel`. This class removes duplicated columns (up to multiplications by units) and zero columns. Hence, we can suppose that the input for the algorithm developed here is a set of points in `PG(k-1, q)`.
The implementation is based on the class :class:`sage.groups.perm_gps.partn_ref2.refinement_generic.PartitionRefinement_generic`. See the description of this algorithm in :mod:`sage.groups.perm_gps.partn_ref2.refinement_generic`. In the language given there, we have to implement the group action of `G = (GL(k,q) \times {\GF{q}^*}^n ) \rtimes Aut(\GF{q})` on the set `X = (\GF{q}^k)^n` of `k \times n` matrices over `\GF{q}` (with the above restrictions).
The derived class here implements the stabilizers `G_{\Pi^{(I)}(x)}` of the projections `\Pi^{(I)}(x)` of `x` to the coordinates specified in the sequence `I`. Furthermore, we implement the inner minimization, i.e. the computation of a canonical form of the projection `\Pi^{(I)}(x)` under the action of `G_{\Pi^{(I^{(i-1)})}(x)}` . Finally, we provide suitable homomorphisms of group actions for the refinements and methods to compute the applied group elements in `G \rtimes S_n`.
The algorithm also uses Jeffrey Leon's idea of maintaining an invariant set of codewords which is computed in the beginning, see :meth:`~sage.coding.codecan.codecan.PartitionRefinementLinearCode._init_point_hyperplane_incidence`. An example for such a set is the set of all codewords of weight `\leq w` for some uniquely defined `w`. In our case, we interpret the codewords as a set of hyperplanes (via the corresponding information word) and compute invariants of the bipartite, colored derived subgraph of the point-hyperplane incidence graph, see :meth:`PartitionRefinementLinearCode._point_refine` and :meth:`PartitionRefinementLinearCode._hyp_refine`.
Since we are interested in subspaces (linear codes) instead of matrices, our group elements returned in :meth:`PartitionRefinementLinearCode.get_transporter` and :meth:`PartitionRefinementLinearCode.get_autom_gens` will be elements in the group `({\GF{q}^*}^n \rtimes Aut(\GF{q})) \rtimes S_n = ({\GF{q}^*}^n \rtimes (Aut(\GF{q}) \times S_n)`.
AUTHORS:
- Thomas Feulner (2012-11-15): initial version
REFERENCES:
- [Feu2009]
EXAMPLES:
Get the canonical form of the Simplex code::
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P = PartitionRefinementLinearCode(mat.ncols(), mat) sage: cf = P.get_canonical_form(); cf [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]
The transporter element is a group element which maps the input to its canonical form::
sage: cf.echelon_form() == (P.get_transporter() * mat).echelon_form() True
The automorphism group of the input, i.e. the stabilizer under this group action, is returned by generators::
sage: P.get_autom_order_permutation() == GL(3, GF(3)).order()/(len(GF(3))-1) True sage: A = P.get_autom_gens() sage: all( [(a*mat).echelon_form() == mat.echelon_form() for a in A]) True
REFERENCES:
.. [Feu2009] Thomas 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, 2009.
"""
#******************************************************************************* # 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/ #******************************************************************************* from __future__ import absolute_import
from cysignals.memory cimport check_allocarray, sig_free
from sage.rings.integer cimport Integer from sage.matrix.matrix cimport Matrix cimport sage.groups.perm_gps.partn_ref2.refinement_generic from sage.modules.finite_submodule_iter cimport FiniteFieldsubspace_projPoint_iterator as FFSS_projPoint from sage.groups.perm_gps.partn_ref.data_structures cimport * include "sage/data_structures/bitset.pxi"
cdef class InnerGroup: r""" This class implements the stabilizers `G_{\Pi^{(I)}(x)}` described in :mod:`sage.groups.perm_gps.partn_ref2.refinement_generic` with `G = (GL(k,q) \times \GF{q}^n ) \rtimes Aut(\GF{q})`.
Those stabilizers can be stored as triples:
- ``rank`` - an integer in `\{0, \ldots, k\}` - ``row_partition`` - a partition of `\{0, \ldots, k-1\}` with discrete cells for all integers `i \geq rank`. - ``frob_pow`` an integer in `\{0, \ldots, r-1\}` if `q = p^r`
The group `G_{\Pi^{(I)}(x)}` contains all elements `(A, \varphi, \alpha) \in G`, where
- `A` is a `2 \times 2` blockmatrix, whose upper left matrix is a `k \times k` diagonal matrix whose entries `A_{i,i}` are constant on the cells of the partition ``row_partition``. The lower left matrix is zero. And the right part is arbitrary. - The support of the columns given by `i \in I` intersect exactly one cell of the partition. The entry `\varphi_i` is equal to the entries of the corresponding diagonal entry of `A`. - `\alpha` is a power of `\tau^{frob_pow}`, where `\tau` denotes the Frobenius automorphism of the finite field `\GF{q}`.
See [Feu2009]_ for more details. """ def __cinit__(self, k=0, algorithm="semilinear", **kwds): r""" See :class:`sage.coding.codecan.codecan.InnerGroup`
INPUT:
- ``k`` -- an integer, gives the dimension of the matrix component - ``algorithm`` -- either
* "semilinear" -- full group * "linear" -- no field automorphisms, i.e. `G = (GL(k,q) \times \GF{q}^n )` * "permutational -- no field automorphisms and no column multiplications
i.e. `G = GL(k,q)` - ``transporter`` (optional) -- set to an element of the group :class:`sage.groups.semimonomial_transformations.semimonomial_transformation_group.SemimonomialTransformationGroup` if you would like to modify this element simultaneously
EXAMPLES::
sage: from sage.coding.codecan.codecan import InnerGroup sage: IG = InnerGroup(10) sage: IG = InnerGroup(10, "linear") sage: IG = InnerGroup(10, "permutational")
::
sage: S = SemimonomialTransformationGroup(GF(4, 'a'), 8) sage: IG = InnerGroup(3, transporter=S.an_element()) """
else:
def __dealloc__(self): r""" Deallocates ``self``. """
cdef int get_rep(self, int pos): """ Get the index of the cell of ``self.row_partition`` containing ``pos``. """
cdef bint has_semilinear_action(self): """ Returns ``True`` iff the field automorphism group component of ``self`` is non-trivial. """
cdef int join_rows(self, int rep1, int rep2): """ Join the cells with unique representatives ``rep1`` and ``rep2`` of ``self.row_partition``. Return the index of the join. """
cdef void copy_from(self, InnerGroup other): """ Copy the group ``other`` to ``self``. """
cdef minimize_by_row_mult(self, FreeModuleElement w): r""" We suppose `v \in \GF{q}^k` and the entries `v_i = 0` for all ``i >= self.rank``. We compute the smallest element ``w`` in the orbit of ``v`` under the group action of the matrix components of all elements in ``self``.
We return ``d, w``, where ``d`` is a dictionary mapping ``self.row_partition`` (accessed via their unique representatives) to its necessary multiplication. Non-occurring cells are multiplicated by 1. """
else:
cdef minimize_matrix_col(self, object m, int pos, list fixed_minimized_cols, bint *group_changed): r""" Minimize the column at position ``pos`` of the matrix ``m`` by the action of ``self``. ``m`` should have no zero column. ``self`` is set to the stabilizer of this column.
We return ``group_changed, mm`` where ``group_changed`` is a boolean indicating if ``self`` got changed and ``mm`` is the modification of ``m``.
In the array ``fixed_minimized_cols`` we store, those columns of ``m`` which are known to be invariant under ``self``. """ cdef SemimonomialTransformation my_trans cdef int applied_frob, i, col, row, first_nz_rep
# this column is linearly dependent on those already fixed
# rescale the already fixed part by column multiplications
else: # this column is linearly independent on those already fixed, # map it to the self._rank-th unit vector
cdef void gaussian_elimination(self, object m, int pos, int pivot, list nz_pos): r""" Minimize the column at position ``pos`` of the matrix ``m`` by the action of ``self``. We know that there is some nonzero entry of this column at ``pivot >= self.rank``. All nonzero entries are stored in the list ``nz_pos``.
``self`` is not modified by this function, but ``m`` is. """
cdef InnerGroup _new_c(self): r""" Make a new copy of ``self``. """
cdef SemimonomialTransformation get_transporter(self): r""" Return the group element we have applied. Should only be called if we passed an element in :meth:`sage.coding.codecan.codecan.InnerGroup.__cinit__`. """
def __repr__(self): """ EXAMPLES::
sage: from sage.coding.codecan.codecan import InnerGroup sage: InnerGroup(10) Subgroup of (GL(k,q) times \GF{q}^n ) rtimes Aut(\GF{q}) with rank = 0, frobenius power = 1 and partition = 0 -> 0 1 -> 1 2 -> 2 3 -> 3 4 -> 4 5 -> 5 6 -> 6 7 -> 7 8 -> 8 9 -> 9 """
cdef void minimize_by_frobenius(self, object v, int *applied_frob, int *stab_pow): r""" Minimize the vector ``v \in \GF{q}^k`` by the action of the field automorphism component of ``self``. ``self`` and ``v`` are not modified by this function.
Let `\tau` denote the Frobenius automorphism of ``\GF{q}``. Then ``applied_frob``-th power of `\tau` will give us the minimal element. The ``stab_pow``-th power of `\tau` will generate the stabilizer of `v`. """
# now x.frobenius(stab_pow*loc_frob) == x
cpdef int get_frob_pow(self): r""" Return the power of the Frobenius automorphism which generates the corresponding component of ``self``.
EXAMPLES::
sage: from sage.coding.codecan.codecan import InnerGroup sage: I = InnerGroup(10) sage: I.get_frob_pow() 1 """
cpdef column_blocks(self, mat): r""" Let ``mat`` be a matrix which is stabilized by ``self`` having no zero columns. We know that for each column of ``mat`` there is a uniquely defined cell in ``self.row_partition`` having a nontrivial intersection with the support of this particular column.
This function returns a partition (as list of lists) of the columns indices according to the partition of the rows given by ``self``.
EXAMPLES::
sage: from sage.coding.codecan.codecan import InnerGroup sage: I = InnerGroup(3) sage: mat = Matrix(GF(3), [[0,1,0],[1,0,0], [0,0,1]]) sage: I.column_blocks(mat) [[1], [0], [2]] """
# there should be no zero columns by assumption!
cdef class PartitionRefinementLinearCode(PartitionRefinement_generic): """ See :mod:`sage.coding.codecan.codecan`.
EXAMPLES::
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P = PartitionRefinementLinearCode(mat.ncols(), mat) sage: cf = P.get_canonical_form(); cf [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: cf.echelon_form() == (P.get_transporter() * mat).echelon_form() True
::
sage: P.get_autom_order_permutation() == GL(3, GF(3)).order()/(len(GF(3))-1) True sage: A = P.get_autom_gens() sage: all( [(a*mat).echelon_form() == mat.echelon_form() for a in A]) True """ def __cinit__(self): r""" Initialization. See :meth:`__init__`.
TESTS::
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: C = PartitionRefinementLinearCode.__new__(PartitionRefinementLinearCode, 0) """
def __init__(self, n, generator_matrix, P=None, algorithm_type="semilinear"): r""" Initialization, we immediately start the algorithm (see :mod:`sage.coding.codecan.codecan`) to compute the canonical form and automorphism group of the linear code generated by ``generator_matrix``.
INPUT:
- ``n`` -- an integer - ``generator_matrix`` -- a `k \times n` matrix over `\GF{q}` of full row rank, i.e. `k<n` and without zero columns. - partition (optional) -- a partition (as list of lists) of the set `\{0, \ldots, n-1\}` which restricts the action of the permutational part of the group to the stabilizer of this partition - algorithm_type (optional) -- use one of the following options
* "semilinear" - full group * "linear" - no field automorphisms, i.e. `G = (GL(k,q) \times \GF{q}^n )` * "permutational - no field automorphisms and no column multiplications i.e. `G = GL(k,q)`
EXAMPLES::
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P = PartitionRefinementLinearCode(mat.ncols(), mat)
::
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P = PartitionRefinementLinearCode(mat.ncols(), mat) """ # self._hyp_refine_vals will initialized after # we computed the set of codewords
def __dealloc__(self): r""" Deallocates ``self``. """ cdef int i
def __repr__(self): """ EXAMPLES::
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: PartitionRefinementLinearCode(mat.ncols(), mat) Canonical form algorithm for linear code generated by [1 0 1 1 0 1 0 1 1 1 0 1 1] [0 1 1 2 0 0 1 1 2 0 1 1 2] [0 0 0 0 1 1 1 1 1 2 2 2 2] """
def _run(self, P, algorithm_type): """ Start the main algorithm, this method is called in :meth:`init`. See this method for the description of the input.
EXAMPLES::
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P = PartitionRefinementLinearCode(mat.ncols(), mat) #indirect doctest sage: P.get_canonical_form() [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] """
# up to now, we just computed the permutational part of the group action # compute the other components of the transporter
# compute the other components of the automorphism group generators
else:
cdef _compute_group_element(self, SemimonomialTransformation trans, str algorithm_type): """ Apply ``trans`` to ``self._root_matrix`` and minimize the this matrix column by column under the inner minimization. The action is simoultaneously applied to ``trans``.
The output of this function is a triple containing, the modified group element ``trans``, the minimized matrix and the stabilizer of this matrix under the inner group. """ cdef int i
&group_changed)
def get_canonical_form(self): r""" Return the canonical form for this matrix.
EXAMPLES::
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P1 = PartitionRefinementLinearCode(mat.ncols(), mat) sage: CF1 = P1.get_canonical_form() sage: s = SemimonomialTransformationGroup(GF(3), mat.ncols()).an_element() sage: P2 = PartitionRefinementLinearCode(mat.ncols(), s*mat) sage: CF1 == P2.get_canonical_form() True """
def get_transporter(self): """ Return the transporter element, mapping the initial matrix to its canonical form.
EXAMPLES::
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P = PartitionRefinementLinearCode(mat.ncols(), mat) sage: CF = P.get_canonical_form() sage: t = P.get_transporter() sage: (t*mat).echelon_form() == CF.echelon_form() True """
def get_autom_gens(self): """ Return generators of the automorphism group of the initial matrix.
EXAMPLES::
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P = PartitionRefinementLinearCode(mat.ncols(), mat) sage: A = P.get_autom_gens() sage: all( [(a*mat).echelon_form() == mat.echelon_form() for a in A]) True """
def get_autom_order_inner_stabilizer(self): """ Return the order of the stabilizer of the initial matrix under the action of the inner group `G`.
EXAMPLES::
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(GF(3), 3).dual_code().generator_matrix() sage: P = PartitionRefinementLinearCode(mat.ncols(), mat) sage: P.get_autom_order_inner_stabilizer() 2 sage: mat2 = Matrix(GF(4, 'a'), [[1,0,1], [0,1,1]]) sage: P2 = PartitionRefinementLinearCode(mat2.ncols(), mat2) sage: P2.get_autom_order_inner_stabilizer() 6 """
cdef _init_point_hyperplane_incidence(self): """ Compute a set of codewords `W` of `C` (generated by self) which is compatible with the group action, i.e. if we start with some other code `(g,\pi)C` the result should be `(g,\pi)W`.
The set `W` will consist of all normalized codewords up to some weight `w`, where `w` is the smallest integer such that `W` spans the linear code `C`.
This set is then transformed to an incidence matrix ``self._points2hyp`` of the point-hyperplane graph (points correspond to rows, hyperplanes to columns). The hyperplanes correspond to the information words. For performance reasons, we also store the transpose ``self._hyp2points`` of ``self._points2hyp``.
This graph will be later used in the refinement procedures. """
# the codewords of weight <= max_weight span the code
s += len(x) if s >= 0: self._hyp_part.levels[s] = 0
self._hyp_part.degree, sizeof(long))
cdef bint _minimization_allowed_on_col(self, int pos): r""" Decide if we are allowed to perform the inner minimization on position ``pos`` which is supposed to be a singleton. For linear codes over finite fields, we can always return ``True``. """
cdef bint _inner_min_(self, int pos, bint *inner_group_changed): r""" Minimize the node by the action of the inner group on the ``pos``-th position. Sets ``inner_group_changed`` to ``True`` if and only if the inner group has changed.
INPUT:
- ``pos`` -- A position in ``range(self.n)``
OUTPUT:
- ``True`` if and only if the actual node compares less or equal to the candidate for the canonical form. """
# finally compare the new column with the best candidate return False # the next leaf will become the next candidate self._is_candidate_initialized = False
cdef bint _refine(self, bint *part_changed, bint inner_group_changed, bint first_step): """ Refine the partition ``self.part``. Set ``part_changed`` to ``True`` if and only if ``self.part`` was refined.
OUTPUT:
- ``False`` -- only if the actual node compares larger than the candidate for the canonical form. """
return True continue
return False else: return False return True
cdef bint _inner_min_refine(self, bint *inner_stab_changed, bint *changed_partition): """ Refine the partition ``self.part`` by computing the orbit (respectively the hash of a canonical form) of each column vector under the inner group.
New fixed points of ``self.part`` get refined by the inner group. If this leads to a smaller group then we set ``inner_stab_changed`` to ``True``. ``changed_partition`` is set to ``True`` if and only if ``self.part`` was refined.
OUTPUT:
- ``False`` only if the image under this homomorphism of group actions compares larger than the image of the candidate for the canonical form. """ cdef int i, j, res, stab_pow, apply_pow
# minimize by self._inner_group as in _inner_min:
else:
# provide some space to store the result (if not already exists) changed_partition, "supp_refine")
cdef bint _point_refine(self, bint *inner_stab_changed, bint *changed_partition): """ Refine the partition ``self.part`` by counting (colored) neighbours in the point-hyperplane graph.
New fixed points of ``self.part`` get refined by the inner group. If this leads to a smaller group then we set ``inner_stab_changed`` to ``True``. ``changed_partition`` is set to ``True`` if and only if ``self.part`` was refined.
OUTPUT:
- ``False`` only if the image under this homomorphism of group actions compares larger than the image of the candidate for the canonical form. """
cdef bitset_t scratch
# provide some space to store the result (if not already exists) inner_stab_changed, changed_partition, "point_refine")
cdef bint _hyp_refine(self, bint *changed_partition): """ Refine the partition of the hyperplanes by counting (colored) neighbours in the point-hyperplane graph.
``changed_partition`` is set to ``True`` if and only if the partition was refined.
OUTPUT:
- ``False`` only if the image under this homomorphism of group actions compares larger than the image of the candidate for the canonical form. """
cdef bitset_t scratch
# provide some space to store the result (if not already exists)
self._hyp_refine_vals_scratch, best_vals, 0, self._hyp_part.degree, &self._is_candidate_initialized, changed_partition)
cdef tuple _store_state_(self): r""" Store the current state of the node to a tuple, such that it can be restored by :meth:`_restore_state_`. """
cdef void _restore_state_(self, tuple act_state): r""" The inverse of :meth:`_store_state_`. """
cdef void _store_best_(self): """ Store this node as the actual best candidate for the canonical form. """
cdef void _latex_act_node(self, str comment="", int printlvl=0): """ Print the actual status as latex (tikz) commands to ``self._latex_debug_string``. Only needed if one wants to visualize the algorithm using latex. This is very helpful for debugging purposes. """
self._latex_debug_string += "\\node{\\begin{tabular}{" cdef int i, j, last = -1 divide_sign = "" for i from 0 <= i < self._part.degree: if self._part.levels[i] <= self._part.depth: self._latex_debug_string += divide_sign + "*{" + str(i - last) + "}{c}" last = i divide_sign = "|" self._latex_debug_string += "}"
# Print the applied permutation. We do highlight the fixed positions. for i from 0 <= i < (self._n): if self._part.entries[i] in self._fixed_minimized: self._latex_debug_string += "\\color{red}"
self._latex_debug_string += str(self._part.entries[i]) if i == self._n - 1: self._latex_debug_string += " \\\\\\hline\n" else: self._latex_debug_string += " & "
permuted_matrix = self._matrix.matrix_from_columns([self._part.entries[i] for i in range(self._n) ])
# Now we will finally print the matrix. for i from 0 <= i < self._k: for j from 0 <= j < (self._n - 1): self._latex_debug_string += "$" + permuted_matrix[i, j]._latex_() + "$ & " self._latex_debug_string += "$" + permuted_matrix[i, self._n - 1]._latex_() + "$ \\\\\n"
if comment != "": self._latex_debug_string += "\\multicolumn{" + str(self._n) + "}{c}{" + comment + "}\n" self._latex_debug_string += "\\end{tabular}};\n" |