Permutation Equivalent Codes

In this section, we aim to answer the question ``when are two codes essentially the same?"

As has been noted before, vector space isomorphisms won't work as they don't preserve weight, which is an essential property of each code.

Definition 1.6.1   Two linear codes $C_1$ and $C_2$ are called permutation equivalent provided there is a permutation of coordinates which sends $C_1$ to $C_2$.

Remark: It is often convenient to express the permutation between codes in a permutation matrix, which is a matrix with exactly one $1$ in each row and column and zeros elsewhere. Another way to see that two codes are permutation equivalents is if there is a permutation matrix such that $G_1$ is a generator for $C_1$ if and only if $G_1 P$ is a generator for $C_2$. We define:

$$C P = \{ \textbf y : \textbf y = \textbf x P$$    for some $$\textbf x \in C_1 \}$$

Facts about permutation matrices:

• If $P$ and $Q$ are $n \times n$ permutation matrices, then so is $PQ$ (matrix multiplication).
• $I_n$ is a permutation matrix
• If $P$ is a permutation matrix, there exists an inverse permutation matrix, $P^{-1}$.

Exercise: 35 from the book.
Suppose that $C_1$ and $C_2$ are permutation equivalent codes where $C_1 P = C_2$ for some permutation matrix $P$. Prove that:

(a)

$C_1^\perp P = C_2^\perp$, and

(b)

if $C_1$ is self-dual, so is $C_2$.

Example: 1.6.1 from the book.
Let $C_1$, $C_2$, and $C_3$ be binary codes with generator matrices

$$G_1 = \begin{bmatrix}1 & 1 & 0 & 0 & 0 & 0 0 & 0 & 1 & 1 & 0 & 0 0 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}$$

$$G_2 = \begin{bmatrix}1 & 0 & 0 & 0 & 0 & 1 0 & 0 & 1 & 1 & 0 & 0 0 & 1 & 0 & 0 & 1 & 0 \end{bmatrix}$$

$$G_3 = \begin{bmatrix}1 & 1 & 0 & 0 & 0 & 0 1 & 0 & 1 & 0 & 0 & 0 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix}$$

Note that $C_1$ and $C_2$ are permutation equivalent with permutation matrix:

$$P = \begin{bmatrix}1 & 0 & 0 & 0 & 0 & 0 0 & 0 & 0 & 0 & 0 & 1... ... 0 & 1 & 0 & 0 0 & 0 & 0 & 0 & 1 & 0 0 & 1 & 0 & 0 & 0 & 0 \end{bmatrix}$$

We can also tell that $C_1$ and $C_3$ are not permutation equivalent - $C_1$ is a self-dual code while $C_3$ is not.

Example: Let $C_1$ and $C_2$ have generator matrices

$$G_1 = \begin{bmatrix}1 & 1 & 0 & 0 & 0 0 & 1 & 0 & 1 & 0 0 & 0 & 1 & 0 & 1 \end{bmatrix}$$

$$G_2 = \begin{bmatrix}1 & 0 & 0 & 1 & 0 1 & 1 & 1 & 1 & 0 0 & 1 & 1 & 1 & 1 \end{bmatrix},$$

respectively. Note that there is not going to be a permutation matrix $P$ so that $G_1 P = G_2$.
However, when we write out the codes:

$$C_1 = \{ 00000, 11000, 01010, 00101, 10010, 11101, 01111, 10111 \}$$

$$C_2 = \{ 00000, 10001, 00011, 01100, 10010, 11101, 01111, 11110 \}$$

we notice that the two codes are in fact permutation equivalent.

Theorem 1.6.2   Let $C$ be a linear code

(i)

$C$ is permutation equivalent to a code which has generator matrix in standard form

(ii)

If $I$ and $R$ are information and redundancy positions, respectively, for $C$, then $R$ and $I$ are information and redundancy positions, respectively, for the dual code $C^\perp$.

Note: Part (ii) states that information and redundancy positions switch for the dual code

Proof. For (i), apply elementary row operations to any generator matrix of $C$. This will produce a new generator matrix of $C$ which has columns the same as those in $I_k$, but possibly in a different order. Now choose a permutation of the columns of the new generator matrix so that these columns are moved to the order that produces $[ I_k \vert A ]$. The code generated by $[ I_k \vert A ]$ is equivalent to $C$.
If $I$ is an information set for $C$, then by row reducing a generator matrix for $C$, we obtain columns in the information positions that are the columns of $I_k$ in some order. As above, choose a permutation matrix $P$ to move the columns so that $CP$ has generator matrix $[ I_k \vert A ]$; $P$ has moved $I$ to the first $k$ coordinate positions. By Theorem 1.2.1, $(CP)^\perp$ has the last $n - k$ coordinates as information positions. By Exercise 35, $(CP)^\perp = C^\perp P$, implying that $R$ is a set of information positions for $C^\perp$, proving (ii). $\qedsymbol$

Instead of thinking of the permutation as a matrix that we multiply a code $C$ by, think of the permutation as an operation that we apply to $C$. This way, we can write the permutations much more succinctly in cycle form. To do this, let $\sigma \in Sym_n$ and $\textbf x = (x_1, x_2, \ldots, x_n) \in C$. Then,

$$\textbf x \sigma = (x_{1 \sigma^{-1}}, x_{2 \sigma^{-1}}, \ldots, x_{n \sigma^{-1}} )$$

Example: 1.6.3 from the book.
Let $n = 3$, $\textbf x = (x_1, x_2, x_3)$, and $\sigma = (1,2,3)$. Then,

$$\textbf x \sigma = (x_3, x_1, x_3)$$

We can also write out the permutation matrix from $\sigma$:

$$P = \begin{bmatrix}0 & 1 & 0 0 & 0 & 1 1 & 0 & 0 \end{bmatrix}$$

Note: If $\sigma, \tau \in Sym_n$, then $\textbf x (\sigma \tau) = (\textbf x \sigma) \tau$.

Of course, a coordinate permutation need not map a code $C$ to a new code.

Definition 1.6.3   If a permutation maps $C$ to itself, then it is called an (permutation) automorphism. The set of all permutation automorphisms of a group forms the permutation automorphism group of $C$.

Remark: In this book, we denote the permutation automorphism group as $PAut(C)$. If a code $C$ is of length $n$, then $PAut(C)$ is a subgroup of the symmetric group $Sym_n$.

Example: Let $C$ be the $[n,1]$ binary repetition code. Then, $PAut(C) = Sym_n$ because all permutations are automorphisms.

Example: Consider the $[7,4]_2$ binary code $\mathcal{H}_3$, with the following generator matrix:

$$G = \left[\begin{array}{cccc\vert ccc} 1 & 0 & 0 & 0 & 0 & 1 & 1 ... ...1 0 & 0 & 1 & 0 & 1 & 1 & 0 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right]$$

Show that the following are automorphisms:

1. $\sigma_1 = (1,2)(5,6)$:
   
   $$G \sigma_1 = \left[\begin{array}{cccc\vert ccc} 0 & 1 & 0 & 0 & 1... ...1 0 & 0 & 1 & 0 & 1 & 1 & 0 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right]$$
   $G \sigma_1$ is simply the matrix $G$ with the rows 1 and 2 switched, and thus still generates $C$.

2. $\sigma_2 = (1,2,3)(5,6,7)$
   $$G \sigma_2 = \left[\begin{array}{cccc\vert ccc} 0 & 1 & 0 & 0 & 1... ...0 1 & 0 & 0 & 0 & 0 & 1 & 1 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right]$$
   Again, $G \sigma_2$ is simply $G$ with the rows 1, 2, and 3 permuted. It still provides a basis for $C$.
3. $\sigma_3 = (1,2,4,5,7,3,6)$
   $$G \sigma_3 = \left[\begin{array}{cccc\vert ccc} 1 & 1 & 1 & 0 & 0... ... 1 1 & 0 & 0 & 0 & 0 & 1 & 1 1& 0 & 1 & 0 & 1 & 0 & 1 \end{array}\right]$$
   Through simple row operations, we can transform $G \sigma_3$ into $G$, so $G \sigma_3$ provides a basis for $C$.

These three permutations generate a simple, non-abelian group of order 168, which turns out to be a very special group, $PSL(2,7)$.

Exercise: How many unique groups are there that are permutation equivalent to $\mathcal{H}_3$?
The original solution was fixed (aka, completely rewritten) by Judy Walker to reflect the fact that, well, it was incorrect.
From Algebra, we know the old adage ``The length of the orbit is the index of the stabilizer." In this case, we have the symmetric group on 7 symbols acting on the set of subsets of $\mathbb{F}_2^7$ by permuting the coordinates of $\mathbb{F}_2^7$. The ``orbit" of the code is the set of all codes equivalent to the code. The ``stabilizer" of the code is the set of all elements of the symmetric group which fix the code (as a set), i.e., the permutation automorphism group of the code. So since we know the stabilizer has order 168 and since we know the order of the symmetric group is 7!, we have that the length of the orbit is 7!/168 = 30. In other words, the number of distinct codes equivalent to our original code (counting our original code) is 30.

Here are some useful properties to know about the permutation automorphism group:

Theorem 1.6.4   Let $C$, $C_1$, and $C_2$ be codes over $\mathbb{F}_q$. Then:

(i)

$PAut(C) = PAut(C^\perp)$,

(ii)

if $q = 4$, $PAut(C) = PAut(C^{\perp_H})$, and

(iii)

if $C_1 P = C_2$ for a permutation matrix $P$, then $P^{-1} PAut(C_1) P = PAut(C_2)$.

Proof is an exercise.

Example: 1.6.5 from the book.
Let $C$ be a binary code with the following generator matrix:

$$G = \begin{bmatrix}1 & 1 & 0 & 0 & 0 0 & 0 & 1 & 1 & 1 \end{bmatrix}$$

Let $C_1^*$ and $C_5^*$ be $C$ punctured on coordinates 1 and 5, respectively. Then, they are generated by the following matrices:

$$G_1^* = \begin{bmatrix}1 & 0 & 0 & 0 0 & 1 & 1 & 1 \end{bmatrix}$$

$$G_5^* = \begin{bmatrix}1 & 1 & 0 & 0 0 & 0 & 1 & 1 \end{bmatrix}$$

$G_1^*$ generates all odd weight codewords, while $G_5^*$ generates all even weight codewords. Hence, they cannot be permutation equivalent.

Definition 1.6.5   The group $PAut(C)$ is transitive as a permutation group if for every ordered pair $(i,j)$ of coordinates, there is a permutation in $PAut(C)$ which sends coordinate $i$ to coordinate $j$.

If we know that $PAut(C)$ is transitive, then we cannot have the case of the previous example.

(This lemma is used to prove part (i) of the next theorem, and is not in the book.)

Lemma 1.6.6   If $C$ is a code and $P$ a permutation where $jP = i$, then

$$(CP)_i^* = C_j^* P_j^*$$

where $P_j^*$ is the permutation punctured at $j$ (remove column $i$ and row $j$).

Theorem 1.6.7   Let $C$ be an $[n,k,d]$ code.

(i)

Suppose that $PAut(C)$ is transitive. Then the $n$ codes obtained from $C$ by puncturing $C$ on a coordinate are permutation equivalent.

(i)

Suppose that $PAut(\hat C)$ is transitive. Then the minimum weight $d$ of $C$ is its minimum odd-like weight, $d_o$. Furthermore, every minimum weight codeword of $C$ is odd-like.

Proof.

(i)

Left to an exercise (42). Suppose that $PAut(C)$ is transitive. Fix $1 \leq i,j \leq n$, and consider $C_i^*$ and $C_j^*$. Because $PAut(C)$ is transitive, there is a $P \in PAut(C)$ that sends $i$ to $j$. Because $P \in PAut(C)$, $CP = C$.
Now, puncture $CP$ on the $j^{th}$ coordinate and $C$ on the $j^{th}$ coordinate. Because of the lemma, $C_j^* = (CP)_j^* = C_i^* P_i^*$. Hence, $C_j^*$ is permutation equivalent to $C_i^*$.

(ii)

Again, assume that $PAut(\hat C)$ is transitive. Applying (i) to $\hat C$ we conclude that puncturing $\hat C$ on any coordinate gives a code permutation equivalent to $C$. Let $\textbf c$ be a minimum weight vector of $C$ and assume that $\textbf c$ is even-like. Then $\mathrm{wt}(\hat{ \textbf c} ) = d$, where $\hat{ \textbf c} \in \hat C$ is the extended vector. Puncturing $\hat C$ on a coordinate where $\textbf c$ is nonzero gives a vector of weight $d-1$ in a code permutation equivalent to $C$, a contradiction.

$\qedsymbol$

Thursday, June 9, 2005
Presenters: J. Brown Kramer, J. DeVries
Material: 1.8, 1.9, 1.10
For Lecture: 60
Problem Set: 59, 69, 62