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 \(PG(k-1, q)\).
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
\(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
_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 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
\(({\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
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
-
class
sage.coding.codecan.codecan.
InnerGroup
¶ Bases:
object
This class implements the stabilizers \(G_{\Pi^{(I)}(x)}\) described in
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.
-
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(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
-
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(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
-
get_autom_order_inner_stabilizer
()¶ 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
-
get_canonical_form
()¶ 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
-
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(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
-
-
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] + list(range(2, m)) ....: perm2 = [(i+1)%n for i in range( n )] + list(range(n,m)) ....: 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 = list(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 = list(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(list(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 = list(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)