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 $\displaystyle \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. ($\displaystyle a, b, c,d \in \mathbb{F}_p$ and are distinct.)

To start with I need a check. For matrices of the following form:

$\displaystyle \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

$\displaystyle \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:

$\displaystyle \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

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.

Re: Construction of GL_2(F) counting issues

Quote:

Originally Posted by

**topsquark** 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 $\displaystyle \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. ($\displaystyle a, b, c,d \in \mathbb{F}_p$ and are distinct.)

To start with I need a check. For matrices of the following form:

$\displaystyle \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** There seems to be (p - 1)(p - 2) matrices of the form

$\displaystyle \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:

$\displaystyle \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 $\displaystyle \mathbb{F}_p^2$. You want to count the number of linearly independent pairs. There are $\displaystyle 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 $\displaystyle p-1$ nonzero scalars. So, there are a total of $\displaystyle p(p-1) - (p-1)$ vectors that are not linearly dependent with the first vector you chose. That means there are $\displaystyle p(p-1)^3$ pairs of linearly independent vectors.

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 p^{4} 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.

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

Re: Construction of GL_2(F) counting issues

Quote:

Originally Posted by

**topsquark** 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 $\displaystyle 2(p-1)$ nonzero vectors with one component zero. That means there are $\displaystyle [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 $\displaystyle p(p-1)^3 - 2(p-1)^3 = (p-1)^3(p-2)$ matrices with no zero entries and nonzero determinant.

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 2^{nd} position, and one choice for third and fourth for a total of

(p-1)(p-2).

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.

Re: Construction of GL_2(F) counting issues

Quote:

Originally Posted by

**SlipEternal** Consider a vector in $\displaystyle \mathbb{F}_p^2$. You want to count the number of linearly independent pairs. There are $\displaystyle 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 $\displaystyle p-1$ nonzero scalars. So, there are a total of $\displaystyle p(p-1) - (p-1)$ vectors that are not linearly dependent with the first vector you chose. That means there are $\displaystyle p(p-1)^3$ pairs of linearly independent vectors.

Oops, that was stupid of me. There are $\displaystyle p^2-1$ nonzero vectors if $\displaystyle \mathbb{F}_p^2$. So, given any nonzero vector, there are $\displaystyle p^2-1 - (p-1) = p^2-p$ linearly independent vectors. That means there are $\displaystyle (p^2-1)(p^2-p)$ elements of $\displaystyle 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 $\displaystyle p^2$ such vectors. If the first vector is nonzero, there are $\displaystyle p-1$ nonzero vectors and one zero vector that are linearly dependent with it. Thus there are $\displaystyle p^2 + (p^2-1)p = p^3+p^2-p$ matrices with zero determinant.

Example: $\displaystyle |GL_2(\mathbb{F}_3)| = (3^2-1)(3^2-3) = 48$ and the number of matrices with zero determinant are $\displaystyle 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 $\displaystyle 48+33 = 81 = 3^4$ 2x2 matrices over $\displaystyle \mathbb{F}_3$.

1 Attachment(s)

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:

Attachment 29725

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}.

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