Codes: Distance, number of codewords, etc

Question

Let $p\geq 3$ be any prime and consider the code $C = N(H)\subseteq\mathbb{Z}_p^2$, where $H = \begin{pmatrix} 1 & 1 & 1 & \dots & 1 & 1 \\ 0 & 1 & 2 & \dots & p-2 & p-1 \end{pmatrix}\in \mathbb{Z}_p^{2\times p}$.

a) How many codewords does the code $C$ contain? I've got an idea on this part. It should just be $p^2$, shouldn't it?

b) Show that every selection of two distinct columns of $H$ results in a non-singular 2x2 matrix.

c) Find a codeword in $C$ of weight 3 and use (b) to conclude that the code $C$ has distance 3.

Parts b and c I have no clue on where to start. I'm sure that I could probably reason my way through c if I could figure out b, since finding the codeword of weight 3 should be trivial. However, I'm willing to take any assistance on this problem.

Answer 1

For part b, what does a selection of two distinct columns look like? What's the condition for a matrix to be non-singular?

For part c, can't you find a vector $v=(a,b,c,0,\dots,0)$ such that $Hv=0$?

Answer 2

In coding theory terminology,The matrix $H$ is called the parity check matrix. If the code takes $k$ data symbols and produces $n$ coded symbols, the rate of the code is $\frac{k}{n}$ and the parity check matrix will be of size $(n-k) \times n$.

a) In your case, $n-k = 2$ and $n=p$. Therefore, $k = p-2$ which means that the code C has $p^{p-2}$ codewords.

b) In your comment to Gerry Myerson's answer, you seem to have answered this yourself.

Answer 3

A row vector $C$ is a codeword in a linear code if $HC^T = 0$ where $H$ is the parity check matrix of the code. If this codeword has Hamming weight $w$, then the corresponding $w$ columns of $H$ are linearly dependent vectors. Thus, if all sets of $1$, $2, \ldots, d-1$ columns of $H$ are sets of linearly independent vectors, then no vector of Hamming weight $1$, $2, \ldots, d-1$ can be a codeword, and hence the minimum weight (and minimum distance) of the code is at least $d$. For the OP's question,

• no column of $H$ is the all-zero column
• every set of $2$ different columns of $H$ constitutes a $2\times 2$ nonsingular matrix and so no pair of columns is linearly dependent

Therefore, the minimum weight is at least $3$. But since there exists a codeword of weight $3$, the minimum weight (and minimum distance) is exactly $3$.