# Problem from Herstein (Group Theory)

This is the problem from Topics in Algebra by I. N. Herstein. Part of Example No. 2.2.9:

Let $G$ be the set of all $2 \times 2$ matrices $\left( {\begin{array}{cc} a & b \\ c & d \\ \end{array} } \right)$ where $a, b, c, d$ are integers modulo $p$, ($p$ a prime number), such that $ad-bc \neq 0$. Under matrix multiplication, prove that $G$ is a non-abelian finite group for any general $p$. All the multiplication and additions of the entries are those with modulo $p$.

Till now, I am solving it for small values of $p$, writing down elements explicitly as suggested in the example itself. I would like to know proof for any general $p$.

-
What part of the request are you not able to prove in the general case? Is proving G a group, proving it non abelian or showing it finite that bother you? –  Marco Vergura Jul 6 '14 at 16:30
Are you familiar with the language and concepts of vector spaces over the field $\Bbb{Z}/p\Bbb{Z}$? This makes a huge difference here. –  Jyrki Lahtonen Jul 6 '14 at 16:36
I would like to know the whole solution... (I did things in bits and pieces, like it being in group etc.) No, I am not familiar with language you mentioned. I have done some courses in basic linear algebra, calculus, mathematical physics and have just started doing group theory. –  Amit Seta Jul 6 '14 at 16:40
You mean $ad-bc\not\equiv 0(\mod p)$ right? –  Gina Jul 6 '14 at 16:46
Sorry, yes Gina I should have mentioned that. –  Amit Seta Jul 6 '14 at 16:48

For general $p$ prime, the group in question is $GL_{2}(\mathbb{Z}/p)$, the general linear group of degree $2$ over the field $\mathbb{Z}/p$, the ring of integers modulo $p$. For a matrix $A=\begin{pmatrix} a & b \\ c & d \end{pmatrix}$, $ad-bc = \text{det}(A)$. For two matrices $A,B \in G$, we have that $\text{det}(AB)=\text{det}(A)\text{det}(B) \neq 0$, because the unit group of $\mathbb{Z}/p$ consists of all non-zero elements, i.e $\text{det}:G \rightarrow \mathbb{Z}/p^{\times}$ is a group homorphism. So $G$ is closed under matrix multiplication. The normal formula for the inverse of a $2$x$2$ matrix holds, the identity element is $I_{2}$, and associativity holds because it holds in $\mathbb{Z}/p$. So $G=GL_{2}(\mathbb{Z}/p)$ is a group.

$G$ is nonabelian for any $p$ prime as $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$, but $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$

The finiteness of $G$ is clear because the total number of possible $2$x$2$ matrices over $\mathbb{Z}/p$ is $p^{4}$, and $G$ is a subset of this. $\square$

-
The examples is given in the book before speaking anything about homorphism, linear groups, rings and fields. –  Amit Seta Jul 6 '14 at 19:00
Are any of those topics covered in the book later? If not, just note that if $\text{det}(A), \text{det}(B)$ are $\neq 0$ mod $p$, then $\text{det}(A)\text{det}(B)$ is also $\neq 0$ mod $p$, otherwise $p$ divides $\text{det}(A)\text{det}(B)$ which implies $\text{det}(A)$ or $\text{det}(B)$ are $0$ mod $p$, a contradiction. –  Edward ffitch Jul 6 '14 at 19:06
Yes, they are actually covered later. But since, the question is given before that I assume the knowledge of those is not mandatory. The solution you provided now is very similar to another answer. Thanks –  Amit Seta Jul 6 '14 at 19:09
Your assumption is correct, and you are welcome. =) –  Edward ffitch Jul 6 '14 at 19:11

For an elementary method that simply involve multiplying out everything...

To check for closure, simply multiplying out everything.

Associative can once again be checked by multiplying out everything.

The identity is $\begin{pmatrix}1 & 0\\0 & 1\end{pmatrix}$

The inverse is $(ad-bc)^{p-2}\begin{pmatrix}d & -b\\-c & a\end{pmatrix}$ (get this from normal rule for 2x2 matrix inverse, and the inverse of determinant is just from FLT).

To prove that it is nonabelian, consider $\begin{pmatrix}1 & 1\\0 & 1\end{pmatrix}$ and $\begin{pmatrix}1 & 0\\1 & 1\end{pmatrix}$ which is guaranteed to work for any $p$.

Finiteness is from the fact that each component is finite.

-

lemma: if $gcd(a,n)=1$ then $a^{-1}$ exist in $\mathbb Z_n$.

Let $A\in G$ then $A^{-1}=(det(A))^{-1}Adj(A)$, In that case, we need to check whether $det(A)^{-1}$ exist in $\mathbb Z_p$.

Since $p\nmid det(A)$ then $gcd(p,det(A))=1$.

Since $det(AB)=det(A)det(B)$ which shows that if $A,B\in G$ then $AB\in G$.

We are done.

Finiteness is obvious as number of the all possible matrices is $p^4$ so this number is less than $p^4$.

I left you to show that it is nonabelian.

-

The above answers elaborate on proving the group properties, non-commutativity and finiteness. However, what Herstein asks is for the reader to find a general formula for the order of the group.

A general formula for the order of $GL_{2}(\mathbb{Z}/p)$ such that $det(A)\neq 0$ can be found using a simple combinatorial argument.

The elements of the group are of the form $\left( {\begin{array}{cc} a & b \\ c & d \\ \end{array} } \right)$ where $ad - bc \neq 0$

$Lemma$ : For any non-zero $a \in \mathbb{Z}/p$, $a(\mathbb{Z}/p - \{0\})$ = $\mathbb{Z}/p -\{0\}$

$Proof:$ There are $p -1$ non zero elements in $\mathbb{Z}/p -\{0\}$ i.e $\{1, 2, ...., p-1\}$

Let $a\in \mathbb{Z}/p -\{0\}$

The set $a(\mathbb{Z}/p - \{0\})=\{ab | b \in \mathbb{Z}/p\}$ has $p-1$ elements.

We show that all the elements are distinct.

Let $ab_1 = ab_2$

Then $a(b_1-b_2)$ is divisible by $p$.

Now $a, b_1 \ and\ b_2 \in \mathbb{Z}/p$ and are thus less than $p$.

Therefore $p\nmid a$. Thus $p \mid (b_1 - b_2)$ which is possible iff $b_1 = b_2$

Thus all of the elements of $\{ab | b \in \mathbb{Z}/p\}$ are distinct and by the definition of multiplication mod $p$ all of them belong to $\mathbb{Z}/p -\{0\}$ which itself has $p-1$ elements.

($0$ cannot be one of the products as neither $a$ nor $b$ is divisible by $p$)

$\therefore\ a(\mathbb{Z}/p - \{0\}) = \mathbb{Z}/p -\{0\}$

(The above lemma basically shows that every non zero element of $\mathbb{Z}/p -\{0\}$ must be multiplied by an unique element to reach a (unique) value in $\mathbb{Z}/p -\{0\}$)

Now for the counting part

$Case\ 1$ Considering $\left( {\begin{array}{cc} a & b \\ c & d \\ \end{array} } \right)$ with $ad - bc \neq 0$ where none of $a, b, c, d$ is zero

We can choose $a, b, c$ in any one of $p-1$ ways. However once $b$ and $c$ are chosen we have to choose $d$ in such a way such that $ad \neq bc$. Now $bc \in \mathbb{Z}/p -\{0\}$ and for any $a$, only one $d$ exists such that $ad = bc$. Thus $d$ can be chosen in $p-2$ ways

The total number of matrices with non-zero entries in $GL_{2}(\mathbb{Z}/p)$ such that $det(A)\neq 0$ is $(p-1)^3(p-2)$.

$Case 2$ Considering matrices in which one or more of the matrix entries are zero.

For the condition $det(A)\neq 0$ to be satisfied, the entries along one of the diagonals must be non-zero.

Let $a = 0$ then $b, c and d$ can be chosen in $p-1$, $p$ and $p-1$ ways respectively. (As $b$ and $d$ must be non zero and $c$ can take any value including $0$)

The choice of a was arbitrary and any of the four entries could have been chosen.

The total number of matrices with one or more zero entries in $GL_{2}(\mathbb{Z}/p)$ such that $det(A)\neq 0$ is $4p(p-1)^2 - 2(p-1)^2$.

(The last term arises because of the overcounting of the cases where both terms along the diagonal are zero).

Thus the total number of elements in $GL_{2}(\mathbb{Z}/p)$ such that $det(A)\neq 0$ is $(p-1)^3(p-2) + 2(p-1)^2(2p-1)$.

-