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