Correspondence between r-dim subspaces of finite fields $F^n$ and $r \times n$ rref matrices.

109 Views Asked by At

enter image description here

Using the hint, I'm thinking the answer to question 1 should be $9^2$, and question 2 $9^5$, since we want to find the number of matrices of the following forms:

$$\left[ \begin{matrix} 1 & . & . \\ \end{matrix} \right]$$

and

$$\left[ \begin{matrix} 1 & . & . & .\\ 0 & 1 & . & . \end{matrix} \right]$$

for questions 1 and 2, respectively. There would be $9^2$ ways to fill in the blanks in the first matrix, and $9^5$ in the second matrix, using the 9 elements of the field.

But I'm not sure about this. Could anyone verify?

Also, for question 3, am I again asked for the number of those $r \times n$ matrices?

1

There are 1 best solutions below

0
On

(1) Let us use $q=9$ for the number of elements in the given field $F$. Let now $V$ be a $1$-dimensional subspace of $F^3$. We pick an element $b\ne 0$ in $V$, the system with the only one element $\{b\}$ is a basis for $V$. The number of such choices of a $b\ne 0$ is $q^3-1$. Two choices $b$, and $b'$ are generating the same space, iff they differ by multiplication with a non-zero scalar. There are $q-1$ such scalars. So the number of $1$-dimensional subspaces of $V=F^3$ is $$ \frac{q^3-1}{q-1}\ . $$ Alternatively, we can use the given result, so need to count "reduced echelon matrices", REM for short in the sequel. This counting may look as follows in this particular case. Let $$A=[\ a_{11}\ a_{12}\ a_{13}\ ] $$ be such an REM.

  • If $a_{11}=1$, then we have free choices for the other two entries, so there are $q^2$ choices of $A$ matching the pattern $[1**]$.

  • Else, $a_{11}=0$, so we go deeper in the row:

    • If $a_{12}=1$, then we have a free choice for the other entry, so there are $q$ choices of $A$ matching the pattern $[0\ 1\ *]$.
    • Else $a_{12}=0$, so we go deeper again.
      • Only the one choice $[\ 0\ 0\ 1]$ remains.

So there are $$q^2+q+1$$ vector subspaces of $V$, same answer.


(2) Same game, two ways to count. Let $W=F^4$, $F=\Bbb F_q$ being a field with $q$ elements. We choose a basis $b_1,b_2$ of $W$. For $b_1\ne 0$ we have $(q^4-1)$ choices. For each such choice, there are $q$ vectors which are linearly dependent w.r.t $b_1$, all scalar multiples of $b_1$, $b_2$ must avoid them, so that we get a linearly independent system, so there are $(q^4-q)$ choices for $b_2$.

Two such choices $(b_1, b_2)$, and $(b_1',b_2')$ are generating the same two-dimensional space, iff there is a base change, so iff we can formally write $$ \underbrace{ \begin{bmatrix} s_{11} & s_{12}\\ s_{21} & s_{22}\\ \end{bmatrix}}_{:=S} \begin{bmatrix} b_1\\b_2 \end{bmatrix} = \begin{bmatrix} b'_1\\b'_2 \end{bmatrix} $$ with an invertible $2\times 2$-matrix $S$ with entries in $F$. How many choices are there for $S$?

For its first column there are $q^2-1$ possibilities.

After each choice of the first column, there are for its second column exactly $q^2-q$ possibilities, so that there is not linear dependency.

Putting all together, we see that there are $$ \frac{(q^4-1)(q^4-q)}{(q^2-1)(q^2-q)} $$ vector subspaces of dimension two inside $W=\Bbb F_q^4$.

Alternatively, we can use the given result, so need to count the REM's of shape $2\times 4$. $$ A = \begin{bmatrix} a_{11}& a_{12}& a_{13} &a_{14}\\ a_{21}& a_{22}& a_{23} &a_{24} \end{bmatrix} $$ be such an REM. Things get now combinatorial, and less structural if we "must use" the result. The following shapes occur: $$ \begin{aligned} \begin{bmatrix} 1 & 0 & * & * \\ 0 & 1 & * & * \end{bmatrix} &\qquad\text{there are $q^2\cdot q^2$ possibilities,} \\ \begin{bmatrix} 1 & * & 0 & * \\ 0 & 0 & 1 & * \end{bmatrix} &\qquad\text{there are $q^2\cdot q$ possibilities,} \\ \begin{bmatrix} 1 & * & * & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} &\qquad\text{there are $q^2\cdot 1$ possibilities.} \\ &\qquad\qquad\text{So for this type $a_{11}=1$ there are totally $q^2\cdot (q^2+q+1)$ possibilities,} \\[2mm] \begin{bmatrix} 0 & 1 & 0 & * \\ 0 & 0 & 1 & * \end{bmatrix} &\qquad\text{there are $q\cdot q$ possibilities,} \\ \begin{bmatrix} 0 & 1 & * & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} &\qquad\text{there are $q\cdot 1$ possibilities,} \\ &\qquad\qquad\text{So for this type $a_{11}=a_{21}=0$, $a_{12}=1$ there are totally $q\cdot (q+1)$ possibilities,} \\[2mm] \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \\ &\qquad\text{$1\cdot 1$ last possibility.} \end{aligned} $$ Totally, we get $q^2(q^2+q+1)+(q^2+q)+1=q^2(q^2+q+1)+(q^2+q+1)=\dots$ $$ (q^2+1)(q^2+q+1) $$ possibilities, same result.


(3)

  • The vector $v_1\ne 0$ has $q^n$ possibilities. The are $q$ possible linear combination of the system $\{v_1\}$, namely $a_1v_1$, and we have $q$ choices for $a_1$.

  • The vector $v_2$ has then $q^n-q$ possibilities, so that the system $\{v_1,v_2\}$ is linearly independent, $v_2$ has to avoid the linear combinations above. The are now $q^2$ possible linear combination of the system $\{v_1,v_2\}$, namely $a_1v_1+a_2v2$, since we have $q$ choices for $a_1$, and $q$ choices for $a_2$.

  • The vector $v_3$ has then $q^n-q^2$ possibilities, so that the system $\{v_1,v_2,v_3\}$ is linearly independent, $v_3$ has to avoid the linear combinations above. The are now $q^3$ possible linear combination of the system $\{v_1,v_2,v_3\}$, namely $a_1v_1+a_2v2+a_3v_3$, since we have $q$ choices for each $a_1$, $a_2$, $a_3$.

This goes systematically further. So the number of linearly independent tuples is $$ (q^n-q^0) (q^n-q^1) (q^n-q^2) \dots (q^n-q^{r-1}) \ . $$