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
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 .
The implementation is based on the class
sage.groups.perm_gps.partn_ref2.refinement_generic.PartitionRefinement_generic
.
See the description of this algorithm in
sage.groups.perm_gps.partn_ref2.refinement_generic
.
In the language given there, we have to implement the group action of
on the set
of
matrices over
(with the above
restrictions).
The derived class here implements the stabilizers
of the projections
of
to
the coordinates specified in the sequence
. Furthermore, we implement
the inner minimization, i.e. the computation of a canonical form of
the projection
under the action of
.
Finally, we provide suitable homomorphisms of group actions for the refinements
and methods to compute the applied group elements in
.
The algorithm also uses Jeffrey Leon’s idea of maintaining an
invariant set of codewords which is computed in the beginning, see
_init_point_hyperplane_incidence()
.
An example for such a set is the set of all codewords of weight for
some uniquely defined
. 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
PartitionRefinementLinearCode._point_refine()
and
PartitionRefinementLinearCode._hyp_refine()
.
Since we are interested in subspaces (linear codes) instead of matrices, our
group elements returned in
PartitionRefinementLinearCode.get_transporter()
and
PartitionRefinementLinearCode.get_autom_gens()
will be elements in the group
.
AUTHORS:
- Thomas Feulner (2012-11-15): initial version
REFERENCES:
EXAMPLES:
Get the canonical form of the Simplex code:
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode
sage: mat = codes.HammingCode(3, GF(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
-
class
sage.coding.codecan.codecan.
InnerGroup
¶ Bases:
object
This class implements the stabilizers
described in
sage.groups.perm_gps.partn_ref2.refinement_generic
with.
Those stabilizers can be stored as triples:
rank
- an integer inrow_partition
- a partition ofwith
discrete cells for all integers
.
frob_pow
an integer inif
The group
contains all elements
, where
is a
blockmatrix, whose upper left matrix is a
diagonal matrix whose entries
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
intersect exactly one cell of the partition. The entry
is equal to the entries of the corresponding diagonal entry of
.
is a power of
, where
denotes the
Frobenius automorphism of the finite field
.
See [Feu2009] for more details.
-
column_blocks
(mat)¶ Let
mat
be a matrix which is stabilized byself
having no zero columns. We know that for each column ofmat
there is a uniquely defined cell inself.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]]
-
get_frob_pow
()¶ 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
-
sage.coding.codecan.codecan.
OP_represent
(n, merges, perm)¶ Demonstration and testing.
TESTS:
sage: from sage.groups.perm_gps.partn_ref.automorphism_group_canonical_label import OP_represent sage: OP_represent(9, [(0,1),(2,3),(3,4)], [1,2,0,4,3,6,7,5,8]) Allocating OrbitPartition... Allocation passed. Checking that each element reports itself as its root. Each element reports itself as its root. Merging: Merged 0 and 1. Merged 2 and 3. Merged 3 and 4. Done merging. Finding: 0 -> 0, root: size=2, mcr=0, rank=1 1 -> 0 2 -> 2, root: size=3, mcr=2, rank=1 3 -> 2 4 -> 2 5 -> 5, root: size=1, mcr=5, rank=0 6 -> 6, root: size=1, mcr=6, rank=0 7 -> 7, root: size=1, mcr=7, rank=0 8 -> 8, root: size=1, mcr=8, rank=0 Allocating array to test merge_perm. Allocation passed. Merging permutation: [1, 2, 0, 4, 3, 6, 7, 5, 8] Done merging. Finding: 0 -> 0, root: size=5, mcr=0, rank=2 1 -> 0 2 -> 0 3 -> 0 4 -> 0 5 -> 5, root: size=3, mcr=5, rank=1 6 -> 5 7 -> 5 8 -> 8, root: size=1, mcr=8, rank=0 Deallocating OrbitPartition. Done.
-
sage.coding.codecan.codecan.
PS_represent
(partition, splits)¶ Demonstration and testing.
TESTS:
sage: from sage.groups.perm_gps.partn_ref.automorphism_group_canonical_label import PS_represent sage: PS_represent([[6],[3,4,8,7],[1,9,5],[0,2]], [6,1,8,2]) Allocating PartitionStack... Allocation passed: (0 1 2 3 4 5 6 7 8 9) Checking that entries are in order and correct level. Everything seems in order, deallocating. Deallocated. Creating PartitionStack from partition [[6], [3, 4, 8, 7], [1, 9, 5], [0, 2]]. PartitionStack's data: entries -> [6, 3, 4, 8, 7, 1, 9, 5, 0, 2] levels -> [0, 10, 10, 10, 0, 10, 10, 0, 10, -1] depth = 0, degree = 10 (6|3 4 8 7|1 9 5|0 2) Checking PS_is_discrete: False Checking PS_num_cells: 4 Checking PS_is_mcr, min cell reps are: [6, 3, 1, 0] Checking PS_is_fixed, fixed elements are: [6] Copying PartitionStack: (6|3 4 8 7|1 9 5|0 2) Checking for consistency. Everything is consistent. Clearing copy: (0 3 4 8 7 1 9 5 6 2) Splitting point 6 from original: 0 (6|3 4 8 7|1 9 5|0 2) Splitting point 1 from original: 5 (6|3 4 8 7|1|5 9|0 2) Splitting point 8 from original: 1 (6|8|3 4 7|1|5 9|0 2) Splitting point 2 from original: 8 (6|8|3 4 7|1|5 9|2|0) Getting permutation from PS2->PS: [6, 1, 0, 8, 3, 9, 2, 7, 4, 5] Finding first smallest: Minimal element is 5, bitset is: 0000010001 Finding element 1: Location is: 5 Bitset is: 0100000000 Deallocating PartitionStacks. Done.
-
class
sage.coding.codecan.codecan.
PartitionRefinementLinearCode
¶ Bases:
sage.groups.perm_gps.partn_ref2.refinement_generic.PartitionRefinement_generic
See
sage.coding.codecan.codecan
.EXAMPLES:
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(3, GF(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
-
get_autom_gens
()¶ Return generators of the automorphism group of the initial matrix.
EXAMPLES:
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(3, GF(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
-
get_autom_order_inner_stabilizer
()¶ Return the order of the stabilizer of the initial matrix under the action of the inner group
.
EXAMPLES:
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(3, GF(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
-
get_canonical_form
()¶ Return the canonical form for this matrix.
EXAMPLES:
sage: from sage.coding.codecan.codecan import PartitionRefinementLinearCode sage: mat = codes.HammingCode(3, GF(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
-
get_transporter
()¶ 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(3, GF(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
-
-
sage.coding.codecan.codecan.
SC_test_list_perms
(L, n, limit, gap, limit_complain, test_contains)¶ Test that the permutation group generated by list perms in L of degree n is of the correct order, by comparing with GAP. Don’t test if the group is of size greater than limit.
TESTS:
sage: from sage.groups.perm_gps.partn_ref.automorphism_group_canonical_label import SC_test_list_perms sage: limit = 10^7 sage: def test_Sn_on_m_points(n, m, gap, contains): ... perm1 = [1,0] + range(m)[2:] ... perm2 = [(i+1)%n for i in range( n )] + range(m)[n:] ... SC_test_list_perms([perm1, perm2], m, limit, gap, 0, contains) sage: for i in range(2,9): ... test_Sn_on_m_points(i,i,1,0) sage: for i in range(2,9): ... test_Sn_on_m_points(i,i,0,1) sage: for i in range(2,9): # long time ... test_Sn_on_m_points(i,i,1,1) # long time sage: test_Sn_on_m_points(8,8,1,1) sage: def test_stab_chain_fns_1(n, gap, contains): ... perm1 = sum([[2*i+1,2*i] for i in range(n)], []) ... perm2 = [(i+1)%(2*n) for i in range( 2*n)] ... SC_test_list_perms([perm1, perm2], 2*n, limit, gap, 0, contains) sage: for n in range(1,11): ... test_stab_chain_fns_1(n, 1, 0) sage: for n in range(1,11): ... test_stab_chain_fns_1(n, 0, 1) sage: for n in range(1,9): # long time ... test_stab_chain_fns_1(n, 1, 1) # long time sage: test_stab_chain_fns_1(11, 1, 1) sage: def test_stab_chain_fns_2(n, gap, contains): ... perms = [] ... for p,e in factor(n): ... perm1 = [(p*(i//p)) + ((i+1)%p) for i in range(n)] ... perms.append(perm1) ... SC_test_list_perms(perms, n, limit, gap, 0, contains) sage: for n in range(2,11): ... test_stab_chain_fns_2(n, 1, 0) sage: for n in range(2,11): ... test_stab_chain_fns_2(n, 0, 1) sage: for n in range(2,11): # long time ... test_stab_chain_fns_2(n, 1, 1) # long time sage: test_stab_chain_fns_2(11, 1, 1) sage: def test_stab_chain_fns_3(n, gap, contains): ... perm1 = [(-i)%n for i in range( n )] ... perm2 = [(i+1)%n for i in range( n )] ... SC_test_list_perms([perm1, perm2], n, limit, gap, 0, contains) sage: for n in range(2,20): ... test_stab_chain_fns_3(n, 1, 0) sage: for n in range(2,20): ... test_stab_chain_fns_3(n, 0, 1) sage: for n in range(2,14): # long time ... test_stab_chain_fns_3(n, 1, 1) # long time sage: test_stab_chain_fns_3(20, 1, 1) sage: def test_stab_chain_fns_4(n, g, gap, contains): ... perms = [] ... for _ in range(g): ... perm = range(n) ... shuffle(perm) ... perms.append(perm) ... SC_test_list_perms(perms, n, limit, gap, 0, contains) sage: for n in range(4,9): # long time ... test_stab_chain_fns_4(n, 1, 1, 0) # long time ... test_stab_chain_fns_4(n, 2, 1, 0) # long time ... test_stab_chain_fns_4(n, 2, 1, 0) # long time ... test_stab_chain_fns_4(n, 2, 1, 0) # long time ... test_stab_chain_fns_4(n, 2, 1, 0) # long time ... test_stab_chain_fns_4(n, 3, 1, 0) # long time sage: for n in range(4,9): ... test_stab_chain_fns_4(n, 1, 0, 1) ... for j in range(6): ... test_stab_chain_fns_4(n, 2, 0, 1) ... test_stab_chain_fns_4(n, 3, 0, 1) sage: for n in range(4,8): # long time ... test_stab_chain_fns_4(n, 1, 1, 1) # long time ... test_stab_chain_fns_4(n, 2, 1, 1) # long time ... test_stab_chain_fns_4(n, 2, 1, 1) # long time ... test_stab_chain_fns_4(n, 3, 1, 1) # long time sage: test_stab_chain_fns_4(8, 2, 1, 1) sage: def test_stab_chain_fns_5(n, gap, contains): ... perms = [] ... m = n//3 ... perm1 = range(2*m) ... shuffle(perm1) ... perm1 += range(2*m,n) ... perm2 = range(m,n) ... shuffle(perm2) ... perm2 = range(m) + perm2 ... SC_test_list_perms([perm1, perm2], n, limit, gap, 0, contains) sage: for n in [4..9]: # long time ... for _ in range(2): # long time ... test_stab_chain_fns_5(n, 1, 0) # long time sage: for n in [4..8]: # long time ... test_stab_chain_fns_5(n, 0, 1) # long time sage: for n in [4..9]: # long time ... test_stab_chain_fns_5(n, 1, 1) # long time sage: def random_perm(x): ... shuffle(x) ... return x sage: def test_stab_chain_fns_6(m,n,k, gap, contains): ... perms = [] ... for i in range(k): ... perm = sum([random_perm(range(i*(n//m),min(n,(i+1)*(n//m)))) for i in range(m)], []) ... perms.append(perm) ... SC_test_list_perms(perms, m*(n//m), limit, gap, 0, contains) sage: for m in range(2,9): # long time ... for n in range(m,3*m): # long time ... for k in range(1,3): # long time ... test_stab_chain_fns_6(m,n,k, 1, 0) # long time sage: for m in range(2,10): ... for n in range(m,4*m): ... for k in range(1,3): ... test_stab_chain_fns_6(m,n,k, 0, 1) sage: test_stab_chain_fns_6(10,20,2, 1, 1) sage: test_stab_chain_fns_6(8,16,2, 1, 1) sage: test_stab_chain_fns_6(6,36,2, 1, 1) sage: test_stab_chain_fns_6(4,40,3, 1, 1) sage: test_stab_chain_fns_6(4,40,2, 1, 1) sage: def test_stab_chain_fns_7(n, cop, gap, contains): ... perms = [] ... for i in range(0,n//2,2): ... p = range(n) ... p[i] = i+1 ... p[i+1] = i ... if cop: ... perms.append([c for c in p]) ... else: ... perms.append(p) ... SC_test_list_perms(perms, n, limit, gap, 0, contains) sage: for n in [6..14]: ... test_stab_chain_fns_7(n, 1, 1, 0) ... test_stab_chain_fns_7(n, 0, 1, 0) sage: for n in [6..30]: ... test_stab_chain_fns_7(n, 1, 0, 1) ... test_stab_chain_fns_7(n, 0, 0, 1) sage: for n in [6..14]: # long time ... test_stab_chain_fns_7(n, 1, 1, 1) # long time ... test_stab_chain_fns_7(n, 0, 1, 1) # long time sage: test_stab_chain_fns_7(20, 1, 1, 1) sage: test_stab_chain_fns_7(20, 0, 1, 1)