Math 896 - Coding Theory
``Problem Set'' Problems from June 8, 2005

# 35

Suppose $\mathcal{C}_1$ and $\mathcal{C}_2$ are permutation equivalent codes where $\mathcal{C}_1P=\mathcal{C}_2$ for some permutation matrix $P$. Prove that:

(a)

$\mathcal{C}_1^\perp P=\mathcal{C}_2^\perp$, and

(b)

if $\mathcal{C}_1$ is self-dual, so is $\mathcal{C}_2$.

Solution:
Proof of (a)
Suppose $\textbf{y} \in \mathcal{C}_1^\perp P$. Thus $\textbf{y}=\textbf{x}P$ for some $\textbf{x} \in \mathcal{C}_1^\perp$. Consider $\textbf{y} \cdot \textbf{c}$ for $\textbf{c} \in \mathcal{C}_2$. Since $\textbf{c} \in \mathcal{C}_2$ and $\mathcal{C}_1P=\mathcal{C}_2$ then $\textbf{c}=\textbf{a}P$ for some $\textbf{a} \in \mathcal{C}_1$. Thus

$$\textbf{y}\cdot \textbf{c} =(\textbf{x}P)\cdot \textbf{c}$$

$$=(\textbf{x}P)\cdot (\textbf{a}P)$$

$$=\textbf{x}PP^T\textbf{a}^T$$

$$P PP^T=I_n$$

$$=\textbf{x}\textbf{a}^T$$

$$\textbf{x} \in \mathcal{C}_1^\perp \textbf{a} \in \mathcal{C}_1$$

$$=0.$$

Hence we see that $\textbf{y}\cdot \textbf{c}=0$ for $\textbf{c} \in \mathcal{C}_2$. Therefore, $\textbf{y} \in \mathcal{C}_2^\perp$. Thus $\mathcal{C}_1^\perp P\subseteq\mathcal{C}_2^\perp$. Since $\mathcal{C}_2$ is an $[n,k]$ coded then $\mathcal{C}_2^\perp$ has dimension $n-k$. Similarly, $\mathcal{C}_1$ is an $[n,k]$ coded then $\mathcal{C}_1^\perp$ has dimension $n-k$. Since $P$ is an invertible matrix and only permutes the columns of the generator matrix of $\mathcal{C}_1^\perp$ then $P$ does not change the rank of the generator matrix of $\mathcal{C}_1^\perp$. Thus $\mathcal{C}_1^\perp P$ has dimension $n-k$. Since $\mathcal{C}_1^\perp P$ and $\mathcal{C}_2^\perp$ have the same dimension and $\mathcal{C}_1^\perp P\subseteq\mathcal{C}_2^\perp$ we see that $\mathcal{C}_1^\perp P=\mathcal{C}_2^\perp$.

Proof of (b)
Suppose $\mathcal{C}_1$ is self-dual. Then we see that $\mathcal{C}_1=\mathcal{C}_1^\perp$. Thus we see that,

$$\mathcal{C}_2 =\mathcal{C}_1P$$

$$\mathcal{C}_1=\mathcal{C}_1^\perp$$

$$=\mathcal{C}_1^\perp P$$
by part (a)

$$=\mathcal{C}_2^\perp.$$

Hence we see that $\mathcal{C}_2=\mathcal{C}_2^\perp$. Therefore, $\mathcal{C}_2$ is self-dual.

#40

Prove Theorem 1.6.4:
Theorem 1.6.4 Let ${\mathcal C}$, ${\mathcal C}_1$, and ${\mathcal C}_2$ be codes over ${\mathbb{F}}_q$. Then:

(i)

$PAut({\mathcal C}) = PAut({\mathcal C}^\perp)$,

(ii)

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

(iii)

if ${\mathcal C}_1 P = {\mathcal C}_2$ for a permutation matrix $P$, then $P^{-1} PAut({\mathcal C}_1) P = PAut({\mathcal C}_2)$.

Solution:

To prove some of the statements in this theorem, we require the use of the following lemma:

Lemma:
Let ${\mathcal C}$ be a finite-dimensional linear code. Then, ${\mathcal C}= ({\mathcal C}^\perp)^\perp$. If $q = 4$, ${\mathcal C}= ({\mathcal C}^{\perp_H})^{\perp_H}$
Proof:
Let ${\mathbf x}\in{\mathcal C}$. Then, for all ${\mathbf y}\in {\mathcal C}^\perp$, $\left<{{\mathbf x}, {\mathbf y}}\right> =0$. Then, for all ${\mathbf y}\in {\mathcal C}^\perp$, $\left<{{\mathbf y}, {\mathbf x}}\right> =0$, so ${\mathbf x}\in ({\mathcal C}^\perp)^\perp$. Because ${\mathcal C}$ has dimension $k$, $({\mathcal C}^\perp)^\perp$ must have dimension $n-(n-k) = k$ and ${\mathcal C}\subseteq ({\mathcal C}^\perp)^\perp$, we must have equality - ${\mathcal C}= ({\mathcal C}^\perp)^\perp$.
The case for $q = 4$ follows similarly.

(i)

Suppose that $\sigma\in PAut({\mathcal C})$ (note it must be a bijection). Then, ${\mathcal C}\sigma = {\mathcal C}$. From exercise 35, $({\mathcal C}\sigma)^\perp = {\mathcal C}^\perp \sigma = {\mathcal C}^\perp$, so $\sigma \in PAut({\mathcal C}^\perp)$ and $PAut({\mathcal C}) \subseteq PAut({\mathcal C}^\perp)$. Additionally, as ${\mathcal C}= ({\mathcal C}^\perp)^\perp$, we get the reverse inequality.
Note that the operation $\cdot$ is performed as matrix multiplication in both groups - hence, as the group elements are the same and the group operations are the same, we can say that $PAut({\mathcal C}) = PAut({\mathcal C}^\perp)$.

(ii)

We see that if $\sigma\in PAut({\mathcal C})$, then $\sigma :{\mathcal C}\longrightarrow{\mathcal C}$ is a bijection. Let ${\mathbf y}=y_{1}y_{2}\dots y_{n}\in{\mathcal C}^{\perp_{H}}$. Then $0=\langle{\mathbf x},{\mathbf y}\rangle_{H}=\sum_{i=1}^{n}x_{i}\overline{y}_{i}$ for all ${\mathbf x}\in{\mathcal C}$. Then we have the following equivalences:

$$\langle{\mathbf x},{\mathbf y}\sigma\rangle_{H} =\sum_{i=1}^{n}x_{i}\overline{y}_{i\sigma^{-1}}$$

$$=\sum_{\substack{i=1 i=j\sigma}}^{n}x_{j\sigma}\overline{y}_{j\sigma\sigma^{-1}}$$

$$=\sum_{\substack{i=1 i=j\sigma}}^{n}x_{j\sigma}\overline{y}_{j}$$

$$=\sum_{j=1}^{n}x_{j\sigma}\overline{y}_{j}$$

$$=\langle{\mathbf x}\sigma^{-1},{\mathbf y}\rangle_{H}.$$

As ${\mathbf x}\sigma^{-1}\in{\mathcal C}$, we see that $0=\langle{\mathbf x}\sigma^{-1},{\mathbf y}\rangle_{H}=\langle{\mathbf x},{\mathbf y}\sigma\rangle_{H}$. Hence ${\mathbf y}\sigma\in{\mathcal C}^{\perp_{H}}$, and so $\sigma\in PAut({\mathcal C}^{\perp_{H}})$. Thus, $PAut({\mathcal C})\subseteq PAut({\mathcal C}^{\perp_{H}})$. Again, we can use the equality ${\mathcal C}= ({\mathcal C}^{\perp_H})^{\perp_H}$ to get the reverse inclusion. Hence, $PAut({\mathcal C}) = PAut({\mathcal C}^{\perp_H})$.

(iii)

Pick any ${\mathbf x}P \in {\mathcal C}_2$, where ${\mathbf x}\in {\mathcal C}_1$. Let $Q \in PAut({\mathcal C}_1)$. Then, ${\mathbf x}Q = {\mathbf x}\in {\mathcal C}_1$. Also,

$${\mathbf x}P(P^{-1} Q P) = {\mathbf x}(P P^{-1}) Q P = {\mathbf x}Q P = {\mathbf y}P \in {\mathcal C}_2$$

Hence, $P^{-1} Q P \in PAut({\mathcal C}_2)$, and $P^{-1} PAut({\mathcal C}_1) P \subseteq PAut({\mathcal C}_2)$. To get the other direction, note that ${\mathcal C}_2 P^{-1} = {\mathcal C}_1$. Then,

$$(P^{-1})^{-1} PAut({\mathcal C}_2) P^{-1} \subseteq PAut({\mathcal C}_1)$$

Multiplying by $P$ on the right and $P^{-1}$ on the left,

$$PAut({\mathcal C}_2) \subseteq P^{-1} PAut({\mathcal C}_1) P$$

# 41

Prove that if ${\mathcal C}_1$ and ${\mathcal C}_2$ are permutation equivalent codes, then so are $\widehat{{\mathcal C}}_1$ and $\widehat{{\mathcal C}}_2$.

Solution: If ${\mathcal C}_1$ and ${\mathcal C}_2$ are permutation equivalent codes, and $G_1$ is a generator matrix for ${\mathcal C}_1$, then there is a permutation matrix $P$ such that $G_1 P$ is a generator matrix for ${\mathcal C}_2$. Now, let

$$\widehat{P} = \left[% \begin{array}{c\vert c} P & 0 \\ \hline 0 & 1 \\ \end{array}% \right].$$

Now $\widehat{P}$ is a permutation matrix, since all but the last column have precisely one 1 in them, and similarly all but the last row have precisely one 1 in them, since $P$ is a permutation matrix. Also, the last column, and the bottom most row also have precisely one 1 in them, as can be seen by the construction of $\widehat{P}$.

Now, let $\widehat{G_1}$ be the generator matrix for ${\mathcal C}_1$ obtained by extending each row in $G_1$, so

$$\widehat{G_1} = \left[% \begin{array}{c\vert c} G_1 & \begi... ... \vdots \\ g_k \\ \end{array} \\ \end{array}% \right],$$

for some $g_i \in {\mathbb{F}}_q$.

Then

$$\widehat{G_1}\widehat{P} = \left[% \begin{array}{c\vert c} ... ... \vdots \\ g_k \\ \end{array} \\ \end{array}% \right],$$

and since $GP$ is a generator matrix for ${\mathcal C}_2$, it remains to show that each row in $\widehat{G_1}\widehat{P}$ is even-like, since that will mean that $\widehat{G_1}\widehat{P}$ is just $GP$ extended.

So, suppose that $x_1 x_2 ... x_n g_j$ is the $j^{th}$ row of $\widehat{G_1}\widehat{P}$. Then $x_1 x_2 ... x_n$ is the $j^{th}$ row of $GP$, and since $P$ is a permutation matrix, $x_1+...+x_n$ is just a rearrangement of $c_1+...+c_n$, where $c_1...c_n$ is the $j^{th}$ row of $G_1$. Thus, $x_1+...+x_n+g_j = c_1+...+c_n+g_j$, which is zero because the $g_i$'s were defined to be such that the sum of the row entries of $G_1$ is zero.

# 43

Let ${\mathcal C}$ be the code of Example 1.4.4.

(a)

Is $PAut({\mathcal C})$ transitive?

(b)

Find generator matrices for all six codes punctured on one point. Which of these punctured codes are equivalent?

(c)

Find generator matrices for all 15 codes punctured on two points. Which of these punctured codes are equivalent?

Solution: From Example 1.4.4, ${\mathcal C}$ is the binary code with generator matrix

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

(a)

PAut$({\mathcal C})$ is transitive. To see this, let $i,j$ be coordinates, $1 \le i,j \le 6$. If the set $\{i,j\}$ is any of the sets $\{1,2\}, \{3,4\}, \{5,6\}$ then the permutation $(i,j)$ fixes $G$ and so the resulting equivalent code is ${\mathcal C}$. So $(i,j) \in$   PAut$({\mathcal C})$ and $(i,j)$ sends coordinate $i$ to $j$ and $j$ to $i$. Otherwise, suppose $\{i,i'\}, \{j,j'\}$ are two distinct sets from $\{1,2\}, \{3,4\}, \{5,6\}$. Then the permutation $(i,j)(i',j')$ which changes the coordinates of $i$ and $j$ and the corresponding pair $i'$ and $j'$ when applied to $G$ simply permutes the two rows: the one with $\{i,i'\}$ nonzero and the one with $\{j,j'\}$ nonzero. Therefore, the resulting matrix is still a generating matrix for ${\mathcal C}$. So $(i,j)(i',j') \in$   PAut$({\mathcal C})$.

(b)

A generating matrix for a punctured code is obtained by deleting the corresponding columns from the original code's generating matrix. Thus, if ${\mathcal C}_i$ represents the code where coordinate $i$ was punctured, then ${\mathcal C}_i$ has generating matrix $G_i$ below.

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

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

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

By Theorem 1.6.6, since PAut$({\mathcal C})$ is transitive, all six punctured codes are equivalent.

(c)

Let ${\mathcal C}_{i,j}$ be the code obtained from ${\mathcal C}$ by puncturing on coordinates $i$ and $j$. Then ${\mathcal C}_{i,j}$ has $G_{i,j}$ below as a generating matrix which is obtained from $G$ by deleting columns $i$ and $j$ (and removing any resulting rows of all zeros).

$$G_{1,2} = G_{3,4} = G_{5,6} = \begin{bmatrix} 1&1&0&0\\ 0&0&1&1 \end{bmatrix}$$

$$G_{1,3} = G_{1,4} = G_{2,3} = G_{2,4} = \begin{bmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&1&1 \end{bmatrix}$$

$$G_{1,5} = G_{1,6} = G_{2,5} = G_{2,6} = \begin{bmatrix} 1&0&0&0\\ 0&1&1&0\\ 0&0&0&1 \end{bmatrix}$$

$$G_{3,5} = G_{3,6} = G_{4,5} = G_{4,6} = \begin{bmatrix} 1&1&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}$$

Therefore, ${\mathcal C}_{1,2}, {\mathcal C}_{3,4}$, and ${\mathcal C}_{5,6}$ are all equivalent as they have the same generating matrix. Furthermore, they are not equivalent to any of the other codes as the dimensions of the codes are different. We claim that the remaining codes are all equivalent. First, as permutation equivalence is an equivalence relation, it is enough to show that $G_{1,3}$ and $G_{1,5}$ generate equivalent codes and $G_{1,5}$ and $G_{3,5}$ generate equivalent codes. For this, we simply exhibit two permutation matrices, $P_{2,4}$ and $P_{1,3}$ (which permutes coordinates 2 and 4 and coordinates 1 and 3 respectively). Then we notice that $G_{1,3}P_{2,4}$ is simply the matrix $G_{1,5}$ with the second and third rows swapped and therefore generate the same code. Similarly, $G_{1,5}P_{1,3}$ is the matrix $G_3,5$ with the first and second rows permuted and therefore generate the same code.

$$P_{2,4} = \begin{bmatrix} 1&0&0&0\\ 0&0&0&1\\ 0&0&1&0\\ 0&1&0&0 \end{bmatrix}$$

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