Author |
Topic: Cardinality of matrix set (Read 3630 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
Cardinality of matrix set
« on: Oct 15th, 2004, 2:40pm » |
 Quote  Modify
|
Hi folks! I've had a bit of sleep deprivation for a couple of days now, all because of a little problem from last year's brazilian math olympiad (university level). Here it is.
Let p > 2 be a prime number. Let GL4([bbz]p) be the general linear group of order 4 over the field [bbz]p. In simpler terms, it is the set of all invertible 4x4 matrices with coefficients in [bbz]p = {0, 1, ... , p-1}. Here, matrix multiplication is carried out in the usual way, but multiplication and addition of matrix coefficients is done in [bbz]p, that is, modulo p.
Define Xp = { A [in] GL4([bbz]p) : A2 = I }, that is, the subset of all matrices that are their own inverses.
Determine how many elements Xp has.
|
|
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Cardinality of matrix set
« Reply #1 on: Dec 10th, 2005, 11:44am » |
Quote Modify
|
Only 14 months late, but I thought I would get the ball rolling here by examining the much easier case of GL2(Zp).
(I also bumped a few other old unanswered posts.)
If we let A be the matrix [ a b ][ c d ] (i.e., A is
[ a b ]
[ c d ] )
then A2 = [ a2+bc b(a+d) ][ c(a+d) d2+bc ]. If A2 = I, then either (a+d) = 0 or b = c = 0.
Assume a+d <> 0. Then a2 = d2 = 1, so a = +-1 and d = +-1. Taking into account the condition that a+d <> 0, there are two solutions A = I and A = -I.
Now, assume a+d=0. Then a2 + bc = 1.
if a2 = 1 (two solutions), then bc=0. If c=0, b can be any value, and if b = 0, c can be any value. So we have 2p-1 choices (-1 since b=c=0 gets counted twice). This give 4p-2 solutions for all a2 = 1.
If a2 <> 1, then bc <> 0, and for each a, b, c is determined by c = (1-a2)/b. Any non-zero value of b is possible, so there are p-1, and p-2 values for a. This gives (p-2)(p-1) solutions.
Adding them all up, card(Xp) = (p2 - 3p + 2) + (4p-2) + 2 = p2 + p + 2.
Of course, this actual question Pietro asked is much harder.
|
| « Last Edit: Dec 10th, 2005, 11:46am by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Cardinality of matrix set
« Reply #2 on: Dec 10th, 2005, 3:05pm » |
Quote Modify
|
Looks like taking combinatorics and grading linear algebra this semester finally paid off:
| hidden: | Equivalently, we count the number of linear operators T : V -> V with T2=I, where V=Fn, F=Zp.
Any such T is a reflection:
v = [ (v+T(v))/2 ] + [ (v-T(v))/2 ],
and the first term in the eigenspace E1, the second in E-1. Conversely, any decomposition of V as a direct sum of two (ordered) spaces determines a unique T.
Let A(n,k) be the number of ways to pick subspaces of dimension k, n-k, direct summing to n. Then
|Xp| = A(n,0) + A(n,1) + . . . + A(n,n-1) + A(n,n).
Let B(k) be the number of (ordered) bases for a k-dimensional space over F. Then
B(n) = A(n,k)*B(k)*B(n-k),
because we can first decompose V and then take bases for each component.
To find B(k), pick the first basis vector non-zero, in pk-1 ways, and then the (i+1)-th vector not in the span of the first i, in pk-pi ways. Thus
B(k) = (pk-1)(pk-p)...(pk-pk-1)
= p(k-1)k/2 (pk-1)(pk-1-1)...(p-1)
= p(k-1)k/2 (p-1)k [k]p!
by definition of the "q-factorial":
[k]p! = [1]*[2]*...*[k], where
[k] = (pk-1)/(p-1) = 1 + p + p2 + ... + pk-1.
After some cancellation,
A(n,k) = B(n) / ( B(k)B(n-k) )
= pk(n-k) [n]! / ( [k]! [n-k]! ) = pk(n-k) [nk],
where [nk] is called the "q binomial", or Gaussian, coefficient.
In the case n=4, we have
|Xp| = [40] + p3 [41] + p4 [42] + p3 [43] + [44]
= 1 + p3 (p4-1)/(p-1) + p4(p4-1)(p3-1)/((p2-1)(p-1)) + p3 (p4-1)/(p-1) + 1. |
|
| « Last Edit: Dec 10th, 2005, 3:11pm by Eigenray » |
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Cardinality of matrix set
« Reply #3 on: Dec 11th, 2005, 7:53am » |
Quote Modify
|
Interesting problem Icarus dug up and nice work by Eigenray.
Here is another idea: noting that X^2=I, so the eigenvalues are all +1 and -1; moreover, the matrix is diagonalizable since char(F)>2 (this is a standard result in Representation Theory). Since the eigenvalues are in the ground field, the diagonalization can take place over that field too, i.e. X = P^(-1) D P for some other matrix P in GL_4(p), where D is one of the diagonal matrices I, -I, diag(1,1,1,-1), diag(1,1,-1,-1), or diag(1,-1,-1,-1). (Only one of these works for any given X of course.) So we need only add up the numbers of matrices similar to each of these diagonal matrices.
For that, one can use the standard orbit-counting fact: there are [GL_4(p): C(D)] such similar matrices, where C(D) is the centralizer of D in GL_4. This is of course all of GL_4 when D = I or -I; in the other cases, it's a block sum of smaller GL_n's (GL_1 x GL_3 in two cases and GL_2 x GL_2 in the other). So multiply the orders of the blocks to get the order of the centralizer, and divide into the order of GL_4 to get the number of similar matrices. Add these up to get the complete count of square roots of I.
|
| « Last Edit: Dec 11th, 2005, 8:03am by Michael Dagg » |
IP Logged |
Regards,
Michael Dagg
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print