If a $ k \times n$ generator matrix has $k$ linearly dependent columns then there is a nonzero codeword with zeros in those $k$ positions.

329 Views Asked by At

Suppose the $ k \times n$ generator matrix of a $(n,k)$ linear block code has $k$ linearly dependent columns. Show that there is a nonzero codeword with zeros in those $k$ positions.

Since the generator matrix has $k$ linearly dependent columns, $d < n- k + 1$. So, there can be a codeword with $k$ zeroes but I don't know how to show there might be a codeword with zeroes in those $k$ positions.

1

There are 1 best solutions below

1
On

Suppose WLOG that the first $k$ columns of $G$ are linearly dependent. Then write $G=(G_1 | G_2)$ where $G_1$ is a $k\times k$ submatrix.

By assumption, the column rank of $G_1$ is less than $k$, as is the row rank, hence the rows of $G_1$ are also LD. Then, there is some $m \ne 0$ (size $1 \times k$) such that $m \, G_1 = 0$.

But $m (G_1 | G_2) = (c_1 | c_2) = c $ is a codeword. And $c\ne0$ (because $G$ is a generator matrix, and hence its rows are LI), and $c_1 = 0$.