Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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 '13 at 5:35
add comment

5 Answers

up vote 4 down vote accepted

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\,$ ?

share|improve this answer
    
Thanks! That was much neater than my case-by-case argument. –  Red Feb 6 '13 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 '13 at 6:20
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
@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 '13 at 14:10
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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