Uniqueness of linear codes

Question

In this textbook, I found the following remark:

An $(n,k)$ linear code $\mathcal{C}$ is a unique subspace consisting of a set of $2^k$ codewords.

The statement surprised me because in vector spaces over infinite fields like $\mathbb{R}^n$, there are infinitely many subspaces with dimension $k<n$.

Below is my attempt to prove the statement.

Let $\mathcal{C}_1$ and $\mathcal{C_2}$ be $(n,k)$ linear codes. Consider their generator matrices in systematic form $\mathbf{G}_1=[\mathbf{I}_k|\mathbf{P}_1]$ and $\mathbf{G}_2=[\mathbf{I}_k|\mathbf{P}_2]$. By symmetry, it suffices to show that every codeword in $\mathcal{C}_1$ is a codeword in $\mathcal{C}_2$.

Let $\mathbf{u}$ be a binary $1\times k$ vector. Then, the corresponding codeword in $\mathcal{C}_1$ is $\mathbf{x}=[\mathbf{u}|\mathbf{u}\mathbf{P}_1]$. Then, a necessary condition so that $\mathbf{x}\in\mathcal{C}_2$ is to set $\mathbf{u}=\mathbf{v}$ so that

$$ \mathbf{x}=[\mathbf{u}|\mathbf{u}\mathbf{P}_1]=[\mathbf{v}|\mathbf{v}\mathbf{P}_2], $$

Then, to complete the proof, I have to show that $\mathbf{u}(\mathbf{P}_1-\mathbf{P}_2)=\mathbf{0}$.

My question is:

What argument can I use to prove that $\mathbf{P}_1 =\mathbf{P}_2$ using what I have right now?

Answer 1

A $(n,k)$ linear code $\mathcal{C}$ is a subspace living in the vector space $(\mathbb{F}^n,\mathbb{F}_2,+_2,.)$ which has $2^k$ distinct code words, is the right way to read it.

Let $G$ be the generator matrix for $\mathcal{C}$. Since $\mathcal{C}$ is a $k$ dimensional subspace in $\mathbb{F}^n_2$, $G$ is a $k \times n$. Then for any vector $x=(x_1,x_2\dots,x_k), \hspace{0.2cm}$ $ x_i\in \mathbb{F}_2$, $G^Tx$ is a codeword. Suppose for some $x_1,x_2$, $G^Tx_1=G^Tx_2$ then, $G^T(x_1-x_2)=0$. This implies $x_1-x_2 \in \text{ Nullspace }(G^T)$. But $G^{T}$ is a matrix with linearly independent columns by definition and hence only the zero linear combination fetch the $0$ codeword and thus, $x_1-x_2=0$, guaranteeing uniqness of codewords. Finally as there are $2^k$ possible $x$ vectors, the statement holds true.

Answer 2

To go directly from what you have written, if $[u|uP_{1}]=[v|vP_{2}]$, you can see right away that $u=v$. Therefore $uP_{1}=vP_{2}=uP_{2}$. You should be able to finish from here.

The word "unique" in the definition you have been given is without meaning and so does not belong since it only adds confusion. It really means that an $[n,k]$ code (not usually written $(n,k)$, the curved parentheses usually mean a nonlinear code where the values have a different meaning) is a fixed $k$-dimensional space; there are many to choose from that will have different properties as codes, and any specific choice of a $k$-subspace can be considered a code.

As far as the number of subspaces, when your field is not infinite, $\mathbb{F}^{n}$ has only finitely many vectors; therefore there are finitely many subsets of vectors, implying that of course there can only be finitely many vector subspaces.