Counting invertible matrices of 2x2 provided Zn

[bsc.j.j.w]

Dear forum members,

I have a small problem counting all the invertible matrices of the size 2x2 providing \mathbb{Z}_{n}. This problem was difficult for me so I decided to go on counting how many invertible 2x2 matrices there are for n=32. My strategy to solve the problem was first by calculating all possible matrices and then subtracting all the matrices for which the deteminant is equal to zero.

Given matrix \begin{pmatrix}a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2}\end{pmatrix} in \mathbb{Z}_{32}, there are 32^4 possible matrices.

The cases in which the determinant is equal to zero are:

If a_{1,1} = 0, a_{1,2} = 0, a_{2,1}=0, a_{2,2}=0, which is eqaul to one case.

If there are three elements equal to zero and one not, the possibilities of that are {4 choose 3} \cdot 32.

If there are two elements equal to zero, provided they are not diagonally of each other ((a_{1,1} = 0 \vee a_{2,2} = 0) \wedge (a_{1,2} = 0 \vee a_{2,1} = 0)), the number of possibilities of that are ({4 \choose 2} - 2) \cdot 32^2.

Now how can I continue to calculate the other number of possibilities? I am not sure how can I count the possibilities when a_{1,1} \cdot a_{2,2} = a_{1,2} \cdot a_{2,1}.

I have already searched the forum, there was I think one similar case (see: showthread.php?t=470215), but there r is a prime and I don't actually get how they suddenly got to that formula, furtheremore the comments suggest that the question is ill-formulated.

Furthermore I have made a small program capable of finding the solution of all non-invertible matrices for this question, however strangely it came up with the answer 7600, which is too low I think, but correct me if I'm wrong. It's written in JAVA.

Thank you for your responses!

PS: I cannot post links, so I post a partial link, the begin section should be equal to the link of this forum. If anyone would like to see the program, the pastebin code is 01uKfAKF.

 

[bsc.j.j.w]

I have another clue. I found that this has something to do with General Linear Group, however I am unfamiliar with group theory. Even though the lack of understanding of group theory, I came across the explanation of how to count invertible matrices.

There are accordingly to Wikipedia (q^n-1)(q^n-q)... invertible matrices. However I do not understand one small thing, how come there are exactly q possibilities in which the second column can be linearly dependent of the previous column? I understand that the first column cannot be zero, hence the -1.

PS: I'm definately sure my program is somehow wrong :(, as 32^4 - 7600 is way off the answer I got from apply the formula from the wikipedia page.

 

[Dick]

There's another problem with your example. The wiki article is about matrices over finite fields. Z32 isn't a field. You can't generally divide in it. For example, 2x=1 has no solution, so you can't divide by 2.

 

[bsc.j.j.w]

So, if I continue with my reasoning as with my first post, how should I continue? And is this countable without using computer programs?

The answer should be (3/8)*32^4.

 

[Dick]

So, if I continue with my reasoning as with my first post, how should I continue? And is this countable without using computer programs?

The answer should be (3/8)*32^4.

I don't know offhand. Are you sure you are counting them right with a computer? The matrix [[2,0],[0,1]] is not invertible in Z32, even though it has a nonzero determinant.