Results 1 to 12 of 12
Like Tree6Thanks
  • 1 Post By Hartlw
  • 1 Post By SlipEternal
  • 1 Post By Hartlw
  • 1 Post By SlipEternal
  • 1 Post By Hartlw
  • 1 Post By SlipEternal

Math Help - Construction of GL_2(F) counting issues

  1. #1
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1

    Construction of GL_2(F) counting issues

    Counting principles (however easy they may be) are not something I'm all that good with.

    I am trying to find all 2 x 2 matrices with elements in \mathbb{F}_p = \mathbb{Z}/n \mathbb{Z} where p is prime. I'm not going to go into the details but I am breaking the matrices down into subsets and counting them. I have two questions about the counting. ( a, b, c,d \in \mathbb{F}_p and are distinct.)

    To start with I need a check. For matrices of the following form:
    \left ( \begin{matrix} a & a \\ b & b \end{matrix} \right )

    I am counting that there are (p - 1)(p - 2) matrices of the above example. Is that right?

    There seems to be (p - 1)(p - 2) matrices of the form
    \left ( \begin{matrix} a & a \\ a & b \end{matrix} \right )

    as well. I'm fairly sure I'm right, I just want to check.

    My second question is about the matrix:
    \left ( \begin{matrix} a & b \\ c & d \end{matrix} \right )

    I need to remove matrices where the determinant ad - bc = 0. How do I count these?

    Hopefully I've been clear. Let me know if I'm not.

    Thanks!
    -Dan
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Construction of GL_2(F) counting issues

    1) Is Z/nZ the set of integers modulo n, Zn? For ex, is Z/4Z {0,1,2,3}
    2) What is Fp? The field Zp?

    EDIT: Never mind. Looked up Z/nZ- out of my leaque. I can only add the trivial observation that if you can populate each position of a 2x2 matrix with any of q elements, the number of different matrices is q^4.
    Last edited by Hartlw; November 12th 2013 at 11:45 AM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,937
    Thanks
    785

    Re: Construction of GL_2(F) counting issues

    Quote Originally Posted by topsquark View Post
    Counting principles (however easy they may be) are not something I'm all that good with.

    I am trying to find all 2 x 2 matrices with elements in \mathbb{F}_p = \mathbb{Z}/n \mathbb{Z} where p is prime. I'm not going to go into the details but I am breaking the matrices down into subsets and counting them. I have two questions about the counting. ( a, b, c,d \in \mathbb{F}_p and are distinct.)

    To start with I need a check. For matrices of the following form:
    \left ( \begin{matrix} a & a \\ b & b \end{matrix} \right )

    I am counting that there are (p - 1)(p - 2) matrices of the above example. Is that right?
    All matrices of that form are guaranteed to have a linear dependency (so they will give a zero determinant).

    Quote Originally Posted by topsquark View Post
    There seems to be (p - 1)(p - 2) matrices of the form
    \left ( \begin{matrix} a & a \\ a & b \end{matrix} \right )

    as well. I'm fairly sure I'm right, I just want to check.

    My second question is about the matrix:
    \left ( \begin{matrix} a & b \\ c & d \end{matrix} \right )

    I need to remove matrices where the determinant ad - bc = 0. How do I count these?

    Hopefully I've been clear. Let me know if I'm not.

    Thanks!
    -Dan
    Consider a vector in \mathbb{F}_p^2. You want to count the number of linearly independent pairs. There are p(p-1) nonzero vectors. For each nonzero vector, of the other nonzero vectors, how many of them would be linearly dependent with the vector you chose? That would be the vector you chose times a scalar for some scalar. There are only p-1 nonzero scalars. So, there are a total of p(p-1) - (p-1) vectors that are not linearly dependent with the first vector you chose. That means there are p(p-1)^3 pairs of linearly independent vectors.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Construction of GL_2(F) counting issues

    Checked Google. Fp is Z/pZ, which has p elements. You can populate each place in a 2x2 matrix with p elements. So there are p4 matrices.

    EDIT: But that's not the OP. Sorry. At least we know we are starting with p different elements. That's half the battle. Now it just becomes a problem in counting.

    How many have det=0? When does ad=bc? That's the hard part.

    Since Fp is a field, we can solve a=bc/d, d unequal to 0. Now count the possiblities for bc/d.

    Looks like all the questions of OP can now be answered. Will try to get to it later.
    Last edited by Hartlw; November 12th 2013 at 12:21 PM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1

    Re: Construction of GL_2(F) counting issues

    I don't think it makes any difference in the above arguments (thanks by the way), but all of a, b, c, d are non-zero. That's where the p - 1 instead of p comes from. I've already counted the cases where any number of 0's appear.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,937
    Thanks
    785

    Re: Construction of GL_2(F) counting issues

    Quote Originally Posted by topsquark View Post
    I don't think it makes any difference in the above arguments (thanks by the way), but all of a, b, c, d are non-zero. That's where the p - 1 instead of p comes from. I've already counted the cases where any number of 0's appear.

    -Dan
    There are 2(p-1) nonzero vectors with one component zero. That means there are [p(p-1) - (p-1)][2(p-1)] = 2(p-1)^3 matrices with nonzero determinant that include at least one component that is zero. Hence there are p(p-1)^3 - 2(p-1)^3 = (p-1)^3(p-2) matrices with no zero entries and nonzero determinant.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Construction of GL_2(F) counting issues

    Number of deteminants equal to 0 for Fp:

    Sometimes an example helps. For F3 the multiplication table is:
    x 0 1 2
    0 0 0 0
    1 0 1 2
    2 0 2 1

    Then for each bc, list all ad such that ad=bc using the multiplication table for F3:
    bc; ad
    00=0; 00,01,10,02,20
    01=0; 00,01,10,02,20
    02=0; 00,01,10,02,20
    10=0; 00,01,10,02,20
    11=1; 11,22
    12=2; 12,21
    20=0; 00,01,10,02,20
    21=2; 12,21
    22=2; 11,22

    Total number of matrices with determinant equal to zero is 29.

    From the above you can probably figure out for Fp the general formula for total number of matrices with determinant equal to zero.

    For more of a feel, maybe try F5 with multiplication table:
    x 0 1 2 3 4
    0 0 0 0 0 0
    1 0 1 2 3 4
    2 0 2 4 1 3
    3 0 3 1 4 2
    4 0 4 3 2 1

    .
    .
    for bc=13=3; ad=13, 24, 31, 42
    .
    .

    Note [a][b]=[ab]
    [a] is the residue class of all integers with remainder a after division by n. a=0,1,2,3.n-1

    Just delete the non-zero terms if you don't want them. I haven't really thought abut the other parts of op.

    EDIT: If M = [a,b;a,a] and there are p-1
    elements wo 0, then there are (p-1) choices for first position, (p-2) choices
    for 2nd position, and one choice for third and fourth for a total of
    (p-1)(p-2).
    Last edited by Hartlw; November 13th 2013 at 05:14 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Construction of GL_2(F) counting issues

    Number of determinants equal to zero wo zero elements :

    For each a, a=bc/d has a unique solution d from multiplication table.
    There are p-1 choices for b, p-1 choices for c, and p-1 choices for a, for a total of (p-1)3 determinants with non-zero elements. For p=3, n=8. But above example gives n=4.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,937
    Thanks
    785

    Re: Construction of GL_2(F) counting issues

    Quote Originally Posted by SlipEternal View Post
    Consider a vector in \mathbb{F}_p^2. You want to count the number of linearly independent pairs. There are p(p-1) nonzero vectors. For each nonzero vector, of the other nonzero vectors, how many of them would be linearly dependent with the vector you chose? That would be the vector you chose times a scalar for some scalar. There are only p-1 nonzero scalars. So, there are a total of p(p-1) - (p-1) vectors that are not linearly dependent with the first vector you chose. That means there are p(p-1)^3 pairs of linearly independent vectors.
    Oops, that was stupid of me. There are p^2-1 nonzero vectors if \mathbb{F}_p^2. So, given any nonzero vector, there are p^2-1 - (p-1) = p^2-p linearly independent vectors. That means there are (p^2-1)(p^2-p) elements of GL_2(\mathbb{F}_p).

    Number of matrices with zero determinant are the number of matrices with linearly dependent vectors. If the first vector is the zero vector, then any vector will be linearly dependent with it. There are p^2 such vectors. If the first vector is nonzero, there are p-1 nonzero vectors and one zero vector that are linearly dependent with it. Thus there are p^2 + (p^2-1)p = p^3+p^2-p matrices with zero determinant.

    Example: |GL_2(\mathbb{F}_3)| = (3^2-1)(3^2-3) = 48 and the number of matrices with zero determinant are 3^3+3^2-3 = 33. This is contrary to hartlw's calculation of 29 matrices with zero determinant (although recounting, he actually had 33 entries, but somehow only counted 29 of them), but consistent with the fact that there are 48+33 = 81 = 3^4 2x2 matrices over \mathbb{F}_3.
    Last edited by SlipEternal; November 13th 2013 at 06:18 AM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    714
    Thanks
    299

    Re: Construction of GL_2(F) counting issues

    Hi topsquark,
    More years ago than I care to remember, the professor of my first group theory class posed this question. The class was unresponsive. However, when he pointed out how to count the number of elements of the full finite general linear group, it was perfectly clear to everyone. Here's a paraphrasing of my professor's explanation:

    Construction of GL_2(F)  counting issues-mhfgroups17.png
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Construction of GL_2(F) counting issues

    Hartlw wrote ("reply with quote" didn't work)

    "Number of determinants equal to zero wo zero elements :

    For each a, a=bc/d has a unique solution d from multiplication table.
    There are p-1 choices for b, p-1 choices for c, and p-1 choices for a, for a total of (p-1)3 determinants with non-zero elements. For p=3, n=8. But above example gives n=4."

    Correction: The example gives n=8, confirming the formula for number of determinants equal to zero with non-zero elements for Fp as n=(p-1)3.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1

    Re: Construction of GL_2(F) counting issues

    Thank you all for your help. I'll have to study these carefully at another time, but I think all the pertinent information is there.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The Size of GL_2(Z_7)
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 1st 2010, 02:41 PM
  2. Bearing issues!
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: April 20th 2010, 09:51 AM
  3. lost of issues
    Posted in the Calculus Forum
    Replies: 5
    Last Post: March 16th 2010, 04:41 PM
  4. Logarithm issues.
    Posted in the Algebra Forum
    Replies: 5
    Last Post: February 15th 2010, 01:28 PM
  5. Show GL_2(R) is isomorphic to Z_2 x Z_2
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: October 28th 2009, 12:46 PM

Search Tags


/mathhelpforum @mathhelpforum