0
$\begingroup$

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?

$\endgroup$
3
  • 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

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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