Results 1 to 11 of 11

Math Help - Order of group

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    52

    Order of group

    Consider the following matrix <br /> <br />
\begin{pmatrix} a & b \\ c & d \end{pmatrix}<br /> <br />
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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by sashikanth View Post
    Consider the following matrix <br /> <br />
\begin{pmatrix} a & b \\ c & d \end{pmatrix}<br /> <br />
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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    52
    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?
    Last edited by sashikanth; March 8th 2010 at 07:55 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Feb 2010
    Posts
    52
    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
    Last edited by sashikanth; March 8th 2010 at 08:00 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2010
    Posts
    52
    -delete post-
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by sashikanth View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by sashikanth View Post
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Feb 2010
    Posts
    52
    Quote Originally Posted by tonio View Post
    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.
    Last edited by sashikanth; March 8th 2010 at 11:11 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Feb 2010
    Posts
    52
    Quote Originally Posted by tonio View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by sashikanth View Post
    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
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Feb 2010
    Posts
    52
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. element of order II, in 2n order group
    Posted in the Advanced Algebra Forum
    Replies: 14
    Last Post: December 14th 2011, 09:32 AM
  2. Order of Group. Direct Product of Cyclic Group
    Posted in the Advanced Algebra Forum
    Replies: 9
    Last Post: November 19th 2011, 01:06 PM
  3. Order of a Group, Order of an Element
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 15th 2010, 06:28 PM
  4. Order of a Group, Order of an Element
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 15th 2010, 06:02 PM
  5. Prove that a group of order 375 has a subgroup of order 15
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 13th 2010, 11:08 PM

Search Tags


/mathhelpforum @mathhelpforum