5
$\begingroup$

$F$ is a finite field of order $q$. What is the size of $\operatorname{GL}_n(F)$ ?

I am reading Dummit and Foote "Abstract Algebra". The following formula is given: $(q^n - 1)(q^n - q)\cdots(q^n - q^{n-1})$. The case for $n = 1$ is trivial. I understand that for $n = 2$ the first row of the matrix can be any ordered pair of field elements except for $0,0$. and the second row can be any ordered pair of field elements that is not a multiple of the first row. So for $n = 2$ there are $(q^n - 1)(q^n - q)$ invertible matrices. For $n\geq 3$, I cannot seem to understand why the formula works. I have looked at Sloane's OEIS A002884. I have also constructed and stared at a list of all $168$ $3\times 3$ invertible matrices over $GF(2)$. I would most appreciate a concrete and detailed explanation of how say $(2^3 - 1)(2^3 - 2)(2^3 - 2^2)$ counts these $168$ matrices.

$\endgroup$
  • 2
    $\begingroup$ An invertible matrix must map a basis to a basis. The number of bases of $\mathbb{F}_q^n$ is the formula you gave above. See Example 1 on p. 412 of Dummit and Foote for a derivation of this formula. $\endgroup$ – André 3000 Aug 16 '15 at 16:13
  • $\begingroup$ @SpamIAm, I don't think that's actually correct. This formula counts the number of ordered bases. To make them unordered, you need to divide by $n!$ $\endgroup$ – Marcus M Aug 16 '15 at 16:18
  • 2
    $\begingroup$ @MarcusM I certainly want to consider my bases as ordered, so I shouldn't divide out. I should have specified that in my comment, though. $\endgroup$ – André 3000 Aug 16 '15 at 16:20
10
$\begingroup$

In order for an $n \times n$ matrix to be invertible, we need the rows to be linearly independent. As you note, we have $q^n - 1$ choices for the first row; now, there are $q$ vectors in the span of the first row, so we have $q^n - q$ choices for the second row. Now, let $v_1, v_2$ be the first two rows. Then the set of vectors in the span of $v_1, v_2$ is of the form $\{c_1 v_1 + c_2 v_2 | c_1,c_2 \in F\}$. This set is of size $q^2$, as we have $q$ choices for $c_1$ and $q$ choices for $c_2$. Thus, we have $q^n - q^2$ choices for the third row. Continuing this gives the desired formula.

$\endgroup$
1
$\begingroup$

For $n=3$, the third row must not be in the subspace generated by the first two rows. A vector in this subspace requires $2$ coefficients ($q^2$ possibilities), you must substract $q^2$ vectors, whence a third factor $q^3-q^2$. And so on.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.