Let C be an [n, k] linear code and G a permutation group of degree n. Then G acts on C in the following way: for a codeword v of C and a permutation x of G, the image of v under x is obtained from v by permuting the coordinate positions of v according to x. We call this the permutation action of G on C.
If C is a non-binary code over a finite field, there is also a monomial action on C. Let K be the alphabet of C. A monomial permutation of monomial degree n is equivalent to a permutation s on K * x { 1, ..., n } which satisfies the following property: (α, i)s = (β, j) implies (γα, i)s = (γβ, j) for all α, β, γ ∈K * and i, j ∈{ 1, ..., n }. The actual degree of s is (q - 1)n. Note that s is completely determined by its action on the points (1, i) for each i, and the matrix representation of s is also determined by its action on the elements (1, i), for 1 ≤i ≤n. To represent a monomial permutation of monomial degree n, we number the pair (α, i) by (q - 1)(i - 1) + α and then use a permutation s of degree (q - 1)n.
The functions in this section allow one to investigate such actions. The algorithms in Magma to compute with such actions are backtrack searches due to Jeff Leon [Leo82][Leo97]. There are 4 algorithms which are provided for codes of length n over a field of cardinality q:
Given a codeword v belonging to the [n, k] code C and an element x belonging to a permutation group G, construct the vector w obtained from v by the action of x. If G has degree n, the permutation action is used; otherwise G should have degree n(q - 1) and the monomial action is used.
Given a codeword v belonging to the [n, k] code C and a permutation group G (with permutation or monomial action on C), construct the vector orbit Y of v under the action of G. The orbit Y is a G-set for the group G.
Given an [n, k] code C and an element x belonging to a permutation group G (with permutation or monomial action on C), construct the code consisting of all the images of the codewords of C under the action of x.
Given an [n, k] code C and a permutation group G (with permutation or monomial action on C), construct the orbit Y of C under the action of G. The orbit Y is a G-set for the group G.
Given a set or sequence S of codewords belonging to the [n, k] code C and an element x belonging to a permutation group (with permutation or monomial action on the codewords), construct the set or sequence of the vectors obtained by permuting the coordinate positions of v, for each v in S, according to the permutation x.
Given a set or sequence S of codes of length n and an element x belonging to a permutation group (with permutation or monomial action on the codes) construct the set or sequence of the codes consisting of all the images of the codewords of C under the action of x.
Given an [n, k] code C and a permutation group G of degree n, find the subcode of C which consists of those vectors of C which are fixed by the elements of G. That is, the subcode consists of those codewords that are fixed by the group G.
Weight: RngIntElt Default: 0
The automorphism group A of the [n, k] linear code C over the field K, where A is the group of all monomial-action permutations which preserve the code. Thus both permutation of coordinates and multiplication of components by non-zero elements from K is allowed, and the degree of A is n(q - 1) where q is the cardinality of K. A power structure P and transfer map t are also returned, so that, given a permutation g from A, one can create a map f = t(g) which represents the automorphism g as a mapping P: C -> C.If the code is known to have very few words of low weight, then it may take some time to compute the support of the code (a set of low weight words). The optional parameter Weight can be used to specify the set of vectors of the specified weight to be used as the support in the algorithm. This set should be of a reasonable size, (possibly hundreds for a large code), while also keeping the weight as small as possible.
Warning: If Weight specifies a set that is too small, then the algorithm risks getting stuck.
The permutation group G of the [n, k] linear code C over the field K, where G is the group of all permutation-action permutations which preserve the code. Thus only permutation of coordinates is allowed, and the degree of G is always n. A power structure P and transfer map t are also returned, so that, given a permutation g from G, one can create a map f = t(g) which represents the automorphism g as a mapping P: C -> C.
A subgroup of the (monomial) automorphism group A of the code C. If the automorphism group of C is already known then the group returned is the full automorphism group, otherwise it will be a subgroup generated by one element. This allows one to find just one automorphism of C if desired. A power structure P and transfer map t are also returned, so that, given a permutation g from A, one can create a map f = t(g) which represents the automorphism g as a mapping P: C -> C.
The subgroup of the (monomial) automorphism group A of the code C, which stabilizes the first k base points as chosen by the backtrack search. These base points may be different to those of the returned group. A power structure P and transfer map t are also returned, so that, given a permutation g from A, one can create a map f = t(g) which represents the automorphism g as a mapping P: C -> C.
The power structure A of all automorphisms of the code C (with monomial action), together with the transfer map t into A from the generic symmetric group associated with the automorphism group of C.
The power structure A of all automorphisms of the code C, together with the transfer map t into A from the generic symmetric group associated with the automorphism group of C; the string T determines which action type should be used: "Monomial" or "Permutation".
> C := ReedMullerCode(2, 6);
> aut := AutomorphismGroup(C);
> FactoredOrder(aut);
[ <2, 21>, [3, 4>, <5, 1>, <7, 2>, <31, 1> ]
> CompositionFactors(aut);
G
| A(5, 2) = L(6, 2)
*
| Cyclic(2)
*
| Cyclic(2)
*
| Cyclic(2)
*
| Cyclic(2)
*
| Cyclic(2)
*
| Cyclic(2)
1
> C := BCHCode(GF(2),23,2);
> C;
[23, 12, 7] BCH code (d = 2, b = 1) over GF(2)
Generator matrix:
[1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1]
[0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0]
[0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1]
[0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1]
[0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1]
[0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1]
[0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1]
[0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0 1]
> WeightDistribution(C);
[ <0, 1>, <7, 253>, <8, 506>, <11, 1288>, <12, 1288>, <15, 506>,
<16, 253>, <23, 1> ]
> AutomorphismGroup(C : Weight := MinimumWeight(C) );
Permutation group acting on a set of cardinality 23
Order = 10200960 = 2^7 * 3^2 * 5 * 7 * 11 * 23
(6, 15, 12)(7, 20, 19)(8, 9, 17)(10, 13, 22)(11, 14, 23)(16,
18, 21)
(5, 17, 9)(6, 21, 20)(7, 16, 23)(10, 13, 22)(11, 12, 19)(14,
18, 15)
(5, 16, 21)(6, 23, 19)(7, 17, 12)(8, 14, 15)(9, 20, 11)(10,
13, 22)
(1, 2)(4, 12)(5, 7)(6, 17)(9, 10)(13, 21)(15, 18)(22, 23)
(2, 3)(4, 21, 6, 20)(5, 10, 12, 17)(7, 13, 9, 11)(15, 18)(16,
19, 22, 23)
(3, 8)(4, 5, 20, 22)(6, 16, 21, 12)(7, 11, 13, 9)(10, 17, 19,
23)(15, 18)
(4, 8, 6, 21, 20)(5, 10, 14, 17, 12)(7, 22, 18, 16, 9)(11,
23, 19, 13, 15)
AutomorphismGroups: MonStgElt Default: "Right"
Weight: RngIntElt Default: 0
Given [n, k] codes C and D, this function returns true if and only if C is equivalent to D. If C is equivalent to D, an equivalence map f is also returned from C onto D. The equivalence is with respect to the monomial action. The function first computes none, one, or both of the automorphism groups of the left and right codes. This may assist the isomorphism testing.The parameter AutomorphismGroups, with valid string values Both, Left, Right, None, may be used to specify which of the automorphism groups should be constructed first if not already known. The default is Right.
In rare cases this algorithm can get stuck, due to an insufficient set of invariant vectors. In this case, the optional parameter Weight can be used to specify this set to be the vectors of the specified weight. This set should be of a reasonable size, (possibly hundreds for large codes), while also keeping the weight as small as possible.
Warning: If Weight specifies a set that is too small, then the algorithm risks getting stuck.