[Math] Control Matrix from a generator matrix

coding-theory

Given a [8,4]-Code over field $\mathbb{Z}_2$ and it's basis, I need to calculae the control matrix.

In my homework, we are given (0,0,0,0,1,1,1,1), (0,0,1,1,0,0,1,1), (0,1,0,1,0,1,0,1), and (1,1,0,0,1,1,0,0) as basis.

I've already constructed one of the possible generator matrices, by simply putting those vectors as rows in to the generator matrix.

Now, I probably have to do some matrix manipulations to get it to the standard form $G = [I_{k\times k} \mid (P^T)_{k\times(n-k)}]$
from which I could get control matrix $H$ as $H=[-P^T|I]$, but I'm not sure how to proceeed, and if there is any easier way to do that.

Best Answer

Just so we're on the same page, here's the definition of control matrix I'm familiar with.

Definition: Let $C$ be a $[n,k]$ linear code over a field $F$ with generator matrix $G$, so that $C = \{ mG \mid m \in F^k \}$. If $H$ is a matrix such that

$$C = \{ x \in F^n \mid Hx^T = 0 \},$$

then $H$ is called a control matrix of $C$.

First, we need a small lemma. You may have already seen this in your class.

Lemma: Let $C$ be a $[n,k]$ linear code over a field $F$ with generator matrix $G$ and let $S$ be an invertible matrix. Let $D$ be the code with generator matrix $GS$. If $H$ is a control matrix of $D$, then $HS^T$ is a control matrix of $C$.

Proof: Since $D$ has generator matrix $GS$ and control matrix $H$, we have

$$ D = \{ mGS \mid m \in F^k \} = \{ x \in F^n \mid Hx^T = 0 \}. $$

Note that $C = \{ mG \mid m \in F^k \}$. Define $X = \{ x \in F^n \mid HS^T x^T = 0 \}$. We will show that $C = X$.

  • ($C \subseteq X$) Consider any $c \in C$. Then $cS \in D$, so $HS^T c^T = H(cS)^T = 0$, and so $c \in X$.

  • ($C \supseteq X$) Let $x \in F^n$ and $HS^T x^T = H(xS)^T = 0$. Then $xS \in D$, so there is some $m \in F^k$ such that $mGS = xS$. Since $S$ is invertible, we have $mG = x$, so $x \in C$.

Since $C = X = \{ x \in F^n \mid HS^T x^T = 0 \}$, we have that $HS^T$ is a control matrix for $C$.

Back to your problem. Let

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

Put $G$ in reduced row echelon form to get a matrix

$$ G' = \begin{bmatrix} 1&0&0&1&0&1&1&0\\ 0&1&0&1&0&1&0&1\\ 0&0&1&1&0&0&1&1\\ 0&0&0&0&1&1&1&1 \end{bmatrix}. $$ Note that the row space of $G$ and $G'$ are the same, so they're both generator matrices of $C$. The problem here is $G'$ isn't in the form $[I|P^T]$. Let $S$ be the $8 \times 8$ permutation matrix that swaps columns 4 and 5:

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

Then $G'S = [I|P]$ for some matrix $P$, so the code with generator matrix $G'S$ has control matrix $[-P^T|I]$. By the lemma, $[-P^T|I]S^T$ is then a control matrix for $C$.

TL;DR: Let $C$ have generator matrix $G$. Put $G$ in RREF. Swap columns until it's in the form $[I|P]$. Let $H = [-P^T|I]$. Swap the same columns in $H$ in the reverse order. The resulting matrix is a control matrix of $C$.

Related Question