# What is the number of invertible $n\times n$ matrices in $\operatorname{GL}_n(F)$?

$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.

• 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. – André 3000 Aug 16 '15 at 16:13
• @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!$ – Marcus M Aug 16 '15 at 16:18
• @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. – André 3000 Aug 16 '15 at 16:20

## 2 Answers

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.

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.