1. ## Order of group

Consider the following matrix $

\begin{pmatrix} a & b \\ c & d \end{pmatrix}

$
with a, b, c, d being integers modulo p, where p is a prime number, such that $\mbox{ad-bc} \neq 0$ . G forms a group relative to matrix multiplication. What is the order of G?

I can do it by taking various cases for p = 2, 3 but I can't even begin to start for a general p. Can anyone help?

2. Originally Posted by sashikanth
Consider the following matrix $

\begin{pmatrix} a & b \\ c & d \end{pmatrix}

$
with a, b, c, d being integers modulo p, where p is a prime number, such that $\mbox{ad-bc} \neq 0$ . G forms a group relative to matrix multiplication. What is the order of G?

I can do it by taking various cases for p = 2, 3 but I can't even begin to start for a general p. Can anyone help?

Think of the vector space $\mathbb{F}_p^2$ over $\mathbb{F}_p$ , with $\mathbb{F}_p=\mathbb{Z}\slash p\mathbb{Z}$ . As p is a prime $\mathbb{F}_p$ is a field and then a matrix $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ is regular iff its columns, seen as elements of $\mathbb{F}_p^2$ , are linearly independent.

Well, we then need only to calculate how many different basis are there in $\mathbb{F}_p^2$ : first column can be ANY vector but the zero vector, so there are ____ choices for it, and then the second column can be ANY vector but all the scalar multiples of the first one. Since there are p scalar multiples for any vector, we get _____ choices for the second column, and multiplying the choices we get ____ different possible basis.

Tonio

3. Thank you for your reply. I was thinking of this approach but I'll tell you why I abandoned it. Firstly a clarification: when 'a' is an integer modulo p, does that mean that 'a' can not be greater than p-1?

If this is true, then consider this train of thought. The first row has $p^2 - 1$ ways of being formed, 1 being subtracted because the option of both 'a' and 'b' being zero. Now if the two rows are to be LI, then the 2nd row should NOT be a scalar multiple of the first row. Therefore the number of options for the 2nd row are $p^2 - p$ options so the answer should be $(p^2 - 1)(p^2 - p)$ matrices.

This is what I thought of. Let p=3. Consider a=1 and b=2 as the 1st row of the given matrix. Now one of the rows that we eliminated in the 2nd row was 2x{1,2} = {2,4} i.e b=4 and d=4. But since b and d are integer modulo p, they can not take value of 4. Hence we have, in our calculation, eliminated an additional value. So shouldn't our answer be wrong?

4. Another bit to the problem that I attempted, the 2nd part of the question asked for the order of the subgroup of G with the condition that the determinant of the matrix be 1.

This is my train of thought: Consider the matrix $\mathbb{I} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$. Our initial matrix can be converted to $\mathbb{I}$ by finite row operations. Hence we can go backwards as well. Consider all the possible rows that can result from row operations on $\mathbb{I}$. I think we will get 'p' options for the top row, {1,0}, {1,1}, ... {1,p-1}, if our bottom row is {0,1}. Similarly for our bottom row as {1,1} we get 'p-1' options for the 1st row: {1,0}, {2,1}, ... {p-1,p-2}. (The row {p,p-1} is not allowed because our integers are modulo p). Similarly for all the possible bottom rows we get 'p-2', 'p-3' ... options for the top rows. Hence the order of our group is p + (p-1) + ... + 1 = p*(p-1)/2

Is it right? Am I overcomplicating a simple problem?

PS: Sorry for not using Latex as much as I should. I'm new to this

5. -delete post-

6. Originally Posted by sashikanth
Thank you for your reply. I was thinking of this approach but I'll tell you why I abandoned it. Firstly a clarification: when 'a' is an integer modulo p, does that mean that 'a' can not be greater than p-1?

There is no "greater", "bigger" or the like in finite fields. When you talk about "an integer modulo p" you must think in a representative of some residue class modulo p. You can choose your representatives from the integer $\{0,1,\ldots,p-1\}$ , but you infinite possible choices for them: for example, with p = 5, the next are full representative sets modulo 5: $\{0,1,2,3,4\}\,,\,\,\{10,11,12,13,14\}\,,\,\,\{25, 41, 122, -57, -1\}\,,\,\,$ etc.

If this is true, then consider this train of thought. The first row has $p^2 - 1$ ways of being formed, 1 being subtracted because the option of both 'a' and 'b' being zero. Now if the two rows are to be LI, then the 2nd row should NOT be a scalar multiple of the first row. Therefore the number of options for the 2nd row are $p^2 - p$ options so the answer should be $(p^2 - 1)(p^2 - p)$ matrices.

Exactly...way to go! That's all you need. As a nice exercise calculate the number of regular matrices n x n modulo p, for any natural number n.

This is what I thought of. Let p=3. Consider a=1 and b=2 as the 1st row of the given matrix. Now one of the rows that we eliminated in the 2nd row was 2x{1,2} = {2,4} i.e b=4 and d=4. But since b and d are integer modulo p, they can not take value of 4. Hence we have, in our calculation, eliminated an additional value. So shouldn't our answer be wrong?
Again, you must take into account ONLY integers MODULO 3...! If you choose in this case the standard, usual set of representatives $\{0,1,2\}$ , then $2\cdot (1,2)=(2,1)$ , since $4=1\!\!\!\pmod 3$ .

Tonio

7. Originally Posted by sashikanth
Another bit to the problem that I attempted, the 2nd part of the question asked for the order of the subgroup of G with the condition that the determinant of the matrix be 1.

This is my train of thought: Consider the matrix $\mathbb{I} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$. Our initial matrix can be converted to $\mathbb{I}$ by finite row operations. Hence we can go backwards as well. Consider all the possible rows that can result from row operations on $\mathbb{I}$. I think we will get 'p' options for the top row, {1,0}, {1,1}, ... {1,p-1}, if our bottom row is {0,1}. Similarly for our bottom row as {1,1} we get 'p-1' options for the 1st row: {1,0}, {2,1}, ... {p-1,p-2}. (The row {p,p-1} is not allowed because our integers are modulo p). Similarly for all the possible bottom rows we get 'p-2', 'p-3' ... options for the top rows. Hence the order of our group is p + (p-1) + ... + 1 = p*(p-1)/2

Is it right? Am I overcomplicating a simple problem?

PS: Sorry for not using Latex as much as I should. I'm new to this

It's fine but there's a much easier way using the first isomorphism theorem (FIT): if we dente by $GL(n,p)$ the group of all invertible nxn matrices modulo p, then the determinant map is a group epimorphism $\det:GL(n,p)\rightarrow \mathbb{F}_p^{*}$ ...now use the FIT together with Lagrange's theorem to find the order of the kernel of the above homomorphism...

Tonio

8. Originally Posted by tonio
Again, you must take into account ONLY integers MODULO 3...! If you choose in this case the standard, usual set of representatives $\{0,1,2\}$ , then $2\cdot (1,2)=(2,1)$ , since $4=1\!\!\!\pmod 3$ .

Tonio
I think I finally understand. Ok let me summarize what my doubt was, because maybe it will help others who might have the same doubt.

By our computation, $\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ is NOT counted as a part of the required group BECAUSE the bottom row is a Scalar multiple (of 2) of the first row since $4=1\!\!\!\pmod 3$.

But the determinant of $\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ is 2*2-1*1 = 3 so it MUST be a part of the required group.

BUT, (this is what I understand to be the flaw in the argument), multiplying while computing the determinant MUST be done modulo p. Otherwise G would NOT be in the group in the first place. If you compute the inverse of $\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ by using the determinant to equal 3, you will get an inverse $\begin{pmatrix} \frac{2}{3} & \frac{1}{3} \\ \frac{-1}{3} & \frac{2}{3} \end{pmatrix}$ which is clearly not a part of G.

9. Originally Posted by tonio
It's fine but there's a much easier way using the first isomorphism theorem (FIT): if we dente by $GL(n,p)$ the group of all invertible nxn matrices modulo p, then the determinant map is a group epimorphism $\det:GL(n,p)\rightarrow \mathbb{F}_p^{*}$ ...now use the FIT together with Lagrange's theorem to find the order of the kernel of the above homomorphism...

Tonio
The only thing I understood from ^^^ is the Lagrange's Theorem . I started studying groups a week ago, I did the Lagrange's Theorem yesterday! Maybe in due course of time I will understand. Thanks!

10. Originally Posted by sashikanth
I think I finally understand. Ok let me summarize what my doubt was, because maybe it will help others who might have the same doubt.

By our computation, $\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ is NOT counted as a part of the required group BECAUSE the bottom row is a Scalar multiple (of 2) of the first row since $4=1\!\!\!\pmod 3$.

But the determinant of $\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ is 2*2-1*1 = 3 so it MUST be a part of the required group.

NO!! If $p=3$ , then $3=0\!\!\!\pmod 3$ , and this means $3=0\,\,\,in\,\,\,\mathbb{F}_3$ ...

BUT, (this is what I understand to be the flaw in the argument), multiplying while computing the determinant MUST be done modulo p. Otherwise G would NOT be in the group in the first place. If you compute the inverse of $\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ by using the determinant to equal 3, you will get an inverse $\begin{pmatrix} \frac{2}{3} & \frac{1}{3} \\ \frac{-1}{3} & \frac{2}{3} \end{pmatrix}$ which is clearly not a part of G.

There is NO inverse of that matrix since its determinant in $3=0$ (ZERO!!!) in the given field...you can't compute what doesn't exist!

Tonio

11. Yes I understand. I was NOT performing modular multiplication/addition while multiplying or adding. That was my fundamental mistake. Thank you so much for your help.