How many generator matrices does an [n, k]q - linear code have?

Question

So far, I have realised that there exists a unique generator matrix for a $[n,k]_q$-linear code if and only if $n=k=1$ and $q=2$.

I also believe that the number of generator matrices is given by the product of $k!$ and the number of possible basis' of the $[n,k]_q-$linear code.

Is the above claim correct?

Is there an easy solution to this problem?

Answer 1

The question amounts to: given a linear subspace of $q^k$ vectors over $GF(q)$, how many basis it has.

For the binary case (I leave the general $q$ case to you):

For the first row, we can select any of the $2^k$ vectors except for the null vector. This generates a sub-space of $2^1=2$ vectors.

For the second row, we can select any of $2^k-2^1$ vector (all except the already generated).

For the third row, we can select any of $2^k-2^2$ ...

Hence the number of basis is

$$\begin{align} N_B&=(2^k-2^0)(2^k-2^1)(2^k-2^2) \cdots (2^k-2^{k-1}) \\ &= 2^{k^2}(1-2^{-k})(1-2^{-k+1})\cdots (1-2^{-1})\\ &= 2^{k^2} (1/2; 1/2)_k \end{align} $$

where $(a;q)_n$ denotes the q-Pochhammer symbol.

Answer 2

You are correct that the number of generator matrices for a given $[n,k]_{q}$ code is equal to the number of ordered bases for the corresponding $k$-dimensional subspace of $\mathbb{F}_{q}^{n}$.

We say two codes are equivalent if one can be obtained from the other by operations including permuting coordinate positions, and muliplying all entries in each coordinate position by a nonzero scalar. So performing elementary row operations of a generator matrix preserves your code identically (since it preserves the row space of a matrix), and performing elementary column operations changes your code to a possibly different but equivalent code. With these column operations, any code is equivalent to one that has a generator matrix in standard form: $$G = \begin{bmatrix} I & A \end{bmatrix}$$ where $I$ is a $k\times k$ identity matrix. Any matrix that is row equivalent to $G$ this will generate the same code as $G$.

(HINT: A matrix $G^{\prime}$ is row equivalent to $G = \begin{bmatrix} I & A \end{bmatrix}$ if and only if $G^{\prime} = \begin{bmatrix} B & BA \end{bmatrix}$ for some invertible $k \times k$ matrix $B$. So try counting the invertible $k \times k$ matrices over $\mathbb{F}_q$, i.e., finding the size of $\mathrm{GL}(k,q)$.)