Consider the binary linear $(13, 64, 5)$-code $C_3$, or a $[13, 6, 5]$-code.

Then, let $M$ be the generator matrix for $C_3$, such that we can rearrange the coordinate positions of the words in $C_3$ so that $M$ is in the form:

$$\left[\begin{array} {ccccc|cccccccc} 1&1&1&1&1&0&0&0&0&0&0&0&0 \\ &&G_1 &&&&&&&G_2 \\ \end{array}\right]$$

I have to show that $G_2$ is the generator matrix for a linear $[8, 5, 3]$ code. It is clear that if $G_2$ is a generator matrix, then the length of the code is $n=8$ and that the dimension is $k=6-1=5$. It is also clear that if $G_2$ is a generator for this code, then the code is linear by definition.

However, how do I show that $G_2$ is in fact a generator matrix? I was thinking of using the fact that a generator matrix has linearly independent rows. But just because $M$ has linearly indepenedet rows does not mean that $G_2$ does as well. So I am not sure why we can say that $G_2$ is a generator matrix.

I am also stuck on showing that the minimum distance would be $3$. I was thinking of using that the code $C_3$ has minimum distance $5$, but I am not sure how.

Any help is appreciated, thank you!

Edit: $C_3$ is obtained by assuming that there exists a linear $(16, 256, 6)$ code for contradiction, then removing the last digit to get a linear $(15, 256, 5)$ code, then cross section $x_1=0$ to get a linear $(14, 128, 4)$ code, and then cross section $x_1=0$ again to get $C_3$, a linear $(13, 64, 5)$ code.


2 Answers 2


From your details, your code is binary (you should mention that).

You always have that $G_{2}$ generates some code (its row space). To show that it is a generator matrix for that code, you need to show that it has full row rank.

You know that $\begin{bmatrix} G_{1} & G_{2} \end{bmatrix}$ has full row rank 5. To show that $G_{2}$ also has full row rank, consider starting with $M$ in standard form, that is $M = \begin{bmatrix} I_{6} & A \end{bmatrix}$. When you reorder the columns to put $M$ into the form you have given, what happened to the other 5 pivots that made up the $I_{6}$?


In fact, using Hamming bound, we know $A_2(8,3) \le \frac{2^8}{1+8} <2^5$, so there is no $[8,5,3]$ binary code. Consequently, there is no point discussing the generator matrix of a non-existent code.

  • 2
    $\begingroup$ Of course there is a point. If you show that $G_{2}$ is the generator matrix for a binary $[8,5,3]$ code, then the nonexistence of an $[8,5,3]$ code gives you the nonexistence of a binary $[13,6,5]$ code (which is not ruled out by the Hamming bound). $\endgroup$ May 15, 2018 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.