1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting invertible matrices of 2x2 provided Zn

  1. May 5, 2012 #1
    Dear forum members,

    I have a small problem counting all the invertible matrices of the size 2x2 providing [itex]\mathbb{Z}_{n}[/itex]. This problem was difficult for me so I decided to go on counting how many invertible 2x2 matrices there are for [itex]n=32[/itex]. 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 [itex]\begin{pmatrix}a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2}\end{pmatrix}[/itex] in [itex]\mathbb{Z}_{32}[/itex], there are [itex]32^4[/itex] possible matrices.

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

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

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

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

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

    I have already searched the forum, there was I think one similiar case (see: showthread.php?t=470215), but there [itex]r[/itex] 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.
     
  2. jcsd
  3. May 5, 2012 #2
    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 [itex](q^n-1)(q^n-q)...[/itex] 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 definetly sure my program is somehow wrong :(, as [itex]32^4 - 7600[/itex] is way off the answer I got from apply the formula from the wikipedia page.
     
  4. May 5, 2012 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  5. May 5, 2012 #4
    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.
     
    Last edited: May 5, 2012
  6. May 5, 2012 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Counting invertible matrices of 2x2 provided Zn
  1. Invertible Matrices (Replies: 2)

  2. Invertible Matrices (Replies: 3)

  3. Invertible matrices (Replies: 3)

Loading...