I am trying to study error control and coding theory by myself. There is an unsolved question which says that the total number of distinct generator matrices of a linear [n,k,d] code over $F=GF(q)$ is $\prod_{i=0}^{k-1}(q^k-q^i)$

Now the hint says that the required number of generator matrices is equal to the number of $k\times k$ non singular matrices over $F$, which is clear to be as I can write generator matrix $(k\times n)$ as $$G=(I_k|A)$$ where $I_k$ is the identity matrix with $k\times k$ dimensions and is the non singular part and rest $A$ is some linear function.

Now comes the main doubt, the hint says the number of such matrices is given as, suppose there are $i<k$ first independent rows in the matrix then adding a linearly independent row has

$$q^k-q^i$$ choices.

But I believe once I have already used $q^k-(i-1)$ choices so now I have $$q^i-i$$ choices of selection, in this way my answer turns out to be $$\prod_{i=0}^{k-1}(q^k-i)$$

Where I am doing wrong?

  • 2
    $\begingroup$ That you are not taking out $i$ vectors, you are taking out all the linear combinations of the already chosen vectors. To choose a linear combination is to choose the scalars that multiply them. That's where $q^i$ appears. $\endgroup$
    – Phicar
    Nov 20 at 20:07
  • $\begingroup$ @Phicar I have tried to answer my question based on your comment, can you please check my answer, am I correct now? $\endgroup$
    – Userhanu
    Nov 20 at 20:25
  • $\begingroup$ Looks good to me $\endgroup$
    – Phicar
    Nov 20 at 21:13

1 Answer 1


I think @Phicar comment was enough to answer my questions. If I already have $i$ independent vectors then the total number of linear combinations, i.e., dependent vectors I can make from them is $q^i$, so the total number of independent vectors left are $q^k-q^i$ and this is how the question is being solved to get the requisite answer.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .