Order of general linear group of $2 \times 2$ matrices over $\mathbb{Z}_3$

From problem 2.3.25 in Topics in Algebra, 2$\varepsilon$ by I. N. Herstein:

Let $G$ be the group of all $2 \times 2$ matrices $\left(\begin{array}{c c}a & b \\ c & d\end{array}\right)$ where $ad-bc \ne 0$ and $a,b,c,d$ are integers modulo 3, relative to matrix multiplication. Show that $o(G) = 48$.

I know that $o(G) \le 3^4 = 81$, since $a,b,c,d$ can each take one of 3 values (mod 3). I attempted to tighten this bound by finding the number of matrices such that $ad=bc$ (mod 3):

• Suppose $ad=bc=0$ (mod 3). Then ($a = 0$ or $d = 0$) and ($b = 0$ or $c = 0$), leading to 36 possible values for $(a,b,c,d)$.
• Suppose $ad=bc=1$ (mod 3). Then ($a=d=1$ or $a=d=2$) and ($b=c=1$ or $b=c=2$), leading to 4 possible values for $(a,b,c,d)$.
• Suppose $ad=bc=2$ (mod 3). Then ($(a,d)=(1,2)$ or $(a,d)=(2,1)$) and ($(b,c)=(1,2)$ or $(b,c)=(2,1)$), leading to 4 possible values for $(a,b,c,d)$.

So, there are in total $36+4+4 = 44$ such $\left(\begin{array}{c c}a & b \\ c & d\end{array}\right)$ where $ad-bc=0$ (mod 3). That means there are at most $81-44 = 37$ such $\left(\begin{array}{c c}a & b \\ c & d\end{array}\right)$ where $ad-bc\ne 0$, i.e., $o(G) \le 37$. However, this contradicts the problem. Where did I go wrong? Can someone set me on the right path?

-
There are great answers below, but one thing that you might want to try next time for this kind of problem is to make a big table. There are only 81 of them, after all. It's not a proof, but you probably would have seen right away where you missed something. Never underestimate the power of seeing a pattern with your own eyes. – John Moeller Feb 6 at 5:35

Hints:

(1) In how many ways can you choose the first column for a matrix in $\,G\,$ ?

(2) Now, in how many ways can you choose the second column?

If you know the vector field $\,\Bbb F_3^2=\left(\Bbb Z/3\Bbb Z\right)^2\,$ then $\,G\,$ is the set of all the invertible matrices over this vector space, and the hints above basically ask: how many different (ordered, of course) basis are there for $\,\Bbb F_3^2\,$ over $\,\Bbb F_3\,$ ?

-
 Thanks! That was much neater than my case-by-case argument. – Red Feb 6 at 5:44 @Red: Note, however, that your case-by-case argument works; you just didn’t count one case correctly. – Brian M. Scott Feb 6 at 6:20

Use the following result: A matrix is non-singular $\iff$ the columns are linearly indipendent.

-

Vector $a\choose c$ must be non-zero, this allows $p^2-1$ choices. Vector $b\choose d$ must not be a multiple of $a\choose c$, this allows $p^2-p$ choices. Thus, $|G|=(p^2-1)(p^2-p)$.

-
 @eitzen : is it true that number of such matrices from $G$ whose determinant is $1$ is half the order of $G$? i found it true for case $p=3$. – wanderer Feb 6 at 14:10

There are only $25$ matrices with $ad=bc=0$. To get $ad=0$ you must have $a=0$ ($3$ cases) or $b=0$ ($3$ cases), but two of those $6$ cases are identical ($a=b=0$), so you really have only $5$. After this correction you’re throwing out $25+4+4=33$ matrices, leaving the desired $48$.

-

This is known as the general linear group $\text{GL}(n,q)$ where $n$ is the dimension of your matrices, $q$ denotes the Galois field $\text{GF}(q)$. In your case, $G=\text{GL}(2,3)$. There is a general way to count the size of $\text{GL}(n,q)$ by scanning each row of a matrix, roughly speaking.

-