wu :: forums
« wu :: forums - Char poly of binomial matrix »

Welcome, Guest. Please Login or Register.
May 3rd, 2024, 5:33am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Icarus, william wu, Grimbal, Eigenray, SMQ, towr)
   Char poly of binomial matrix
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Char poly of binomial matrix  (Read 3355 times)
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Char poly of binomial matrix  
« on: Feb 3rd, 2006, 3:15pm »
Quote Quote Modify Modify

Let A(n) be the n x n matrix whose (i,j) entry, 0<i,j<n, is the binomial coefficient (i+jCi).  That is, the upper-left n x n minor of
 
1  1  1  1  1 . . .
1  2  3  4  5 . . .
1  3  6 10 15 . . .
1  4 10 20 35 . . .
1  5 15 35 70 . . .  
.    .    .    .    .    .
 
For p prime, compute the characteristic polynomial of A(pk) mod p (as a polynomial over the field Z/p).
 
(Inspired by (warning: spoiler) another thread.)
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Char poly of binomial matrix  
« Reply #1 on: Feb 10th, 2006, 10:43pm »
Quote Quote Modify Modify

Definitely have a look at A, A2, A3, ... mod p for a few cases!  Proving that is half the problem.
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Char poly of binomial matrix  
« Reply #2 on: Feb 21st, 2006, 8:56am »
Quote Quote Modify Modify

Let me start with the following question: Does it  help to know that if (m0, …, md) and (n0, …, nd) are  the expansions of numbers m, n in base p (a prime), then C(n, m) = C(n0, m0)…C(nd, md) mod p?
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Char poly of binomial matrix  
« Reply #3 on: Feb 21st, 2006, 4:51pm »
Quote Quote Modify Modify

It was this exact property that led me to the problem -- specifically, the fact that A mod 2 is Sierpinski's triangle.  I noticed it could be expressed cleanly in terms of the operators A(2k), and thought about how to use this fact to say something interesting about all of them, given A(2).  And then, for each A(p), you can say something about all the A(pk).  What I didn't expect was that the answer would be the same for all p!
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Char poly of binomial matrix  
« Reply #4 on: Feb 24th, 2007, 6:50pm »
Quote Quote Modify Modify

For example, A = A(5) mod 5:
 
1 1 1 1 1
1 2 3 4 0
1 3 1 0 0
1 4 0 0 0
1 0 0 0 0
 
A2 mod 5:
 
0 0 0 0 1
0 0 0 4 1
0 0 1 3 1
0 4 3 2 1
1 1 1 1 1
 
and A3 mod 5 (surprise):
 
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
 
Prove that the same thing holds for any prime, and you're halfway there.  Any takers?
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Char poly of binomial matrix  
« Reply #5 on: Mar 8th, 2007, 9:10am »
Quote Quote Modify Modify

on Feb 24th, 2007, 6:50pm, Eigenray wrote:
Prove that the same thing holds for any prime, and you're halfway there.  Any takers?

Well, it turns out that for any prime p, A3(p) mod p is the identity matrix (by the way, it happens for some composite numbers as well). Also:
 
1. A(p) is kind of "triangular" (but not in the usual sense of this property). It's clear why.
 
2. A2(p) is kind of "transpose" to A(p) (but again not in the usual sense).
 
These are simple observations, though... I have no idea how to show, for instance, that A2(p) (1, 1) = 0. [Edited: well, in fact, I do.  Grin]
« Last Edit: Mar 8th, 2007, 9:44am by Barukh » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Char poly of binomial matrix  
« Reply #6 on: Mar 8th, 2007, 2:12pm »
Quote Quote Modify Modify

on Mar 8th, 2007, 9:10am, Barukh wrote:

Well, it turns out that for any prime p, A3(p) mod p is the identity matrix (by the way, it happens for some composite numbers as well)

Any which aren't the square of a prime?
 
It appears A(pk)3 = I mod p2, but my method of proof will not show it, since the relation between A2 and A fails mod p2.
 
Quote:
These are simple observations, though... I have no idea how to show, for instance, that A2(p) (1, 1) = 0.

The claim is that
 
A2(i', j') = A(i,j) mod p,
 
where i' = p-1-i.  It's actually pretty combinatorial once you go mod p.
 
This may or may not help, but there is a surprising (though easy to prove) relation between A and C, where C is
 
1 0  0  0  0 ...
1 1  0  0  0 ...
1 2  1  0  0 ...
1 3  3  1  0 ...
1 4  6  4  1 ...
...
 
(But again, this fails mod p2.)
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Char poly of binomial matrix  
« Reply #7 on: Mar 9th, 2007, 3:40am »
Quote Quote Modify Modify

on Mar 8th, 2007, 2:12pm, Eigenray wrote:
Any which aren't the square of a prime?

No.  Wink
 
Quote:
The claim is that
 
A2(i', j') = A(i,j) mod p,
 
where i' = p-1-i.

Yes, that's exactly what I see.
 
Quote:
It's actually pretty combinatorial once you go mod p.

Hmm... It is relatively easy to establish when i,j are small numbers (for instance, A2(1,1) is a sum of squares, and therefore is divisible by a prime number), but gets pretty messy when indices grow.
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Char poly of binomial matrix  
« Reply #8 on: Mar 9th, 2007, 7:37am »
Quote Quote Modify Modify

A2(i',j') = A(i', k) A(k, j').
 
What is A(i', k) mod p?
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Char poly of binomial matrix  
« Reply #9 on: Mar 10th, 2007, 2:18am »
Quote Quote Modify Modify

on Mar 9th, 2007, 7:37am, Eigenray wrote:
What is A(i', k) mod p?

Except the fact that it's 0 for i'+k >= p (which follows from the statement in my post more than a year ago), I don't see any other way to simplify this.
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Char poly of binomial matrix  
« Reply #10 on: Mar 10th, 2007, 6:01pm »
Quote Quote Modify Modify

Compare A(i', k) with C(i, k), mod p.
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Char poly of binomial matrix  
« Reply #11 on: Mar 12th, 2007, 5:40am »
Quote Quote Modify Modify

on Mar 10th, 2007, 6:01pm, Eigenray wrote:
Compare A(i', k) with C(i, k), mod p.

A(i, j) = C(i+j, j) mod p, which is just the definition of A.
 
I am certainly missing something...
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Char poly of binomial matrix  
« Reply #12 on: Mar 12th, 2007, 4:53pm »
Quote Quote Modify Modify

I said to compare A(i', k) with C(i, k), not C(i'+k, k) . . .
 
 Cry Kiss Undecided Lips Sealed Embarassed Tongue Roll Eyes Huh Cool Shocked Sad Angry Grin Cheesy Wink Smiley
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Char poly of binomial matrix  
« Reply #13 on: Mar 14th, 2007, 12:01am »
Quote Quote Modify Modify

Oops… Sorry, Eigenray. Too little time to concentrate on this problem. It remains to think at nights  Grin. But seriously:
 
A(p-1-i, j) = C(p-1-i+j, j) = (p-i+j-1)(p-i+j-2)…(p-i) / j!

Consider this as a polynomial in p. Its free term equals:
(-1)ji(i-1)…(i-j+1) / j! = (-1)jC(i, j)

and is an integer. Therefore, the sum of p-powers is also an integer, and as such is divisible by p. So, we get:
 
A(p-1-i, j) = (-1)jC(i, j) mod p    (1)

 
Next, we proceed (mod p):
 
A2(p-1-i, p-1-j) =  
   k A(p-1-i,k)A(k,p-1-j)  =  (A is symmetric)
   k A(p-1-i,k)A(p-1-j,k)  = (from (1))
    k (-1)2kC(i, k)C(j, k) =  (Vandermonde Identity)
C(i+j, i) = A(i, j),

 
as stated.
 
Finally (this time p being an odd prime):
 
A3(i,j) = k A(i,k)A2(k,j)  =  
    k A(i,k)A(p-1-j,p-1-k)  =    
    k (-1)p-1C(p-1-i,k)C(j,p-1-k) =
C(p-1-i+j, p-1).

 
The last value equals 1 when i = j; equals 0 when j > i (because of this) or j < i (because of symmetry).
 
 
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Char poly of binomial matrix  
« Reply #14 on: Mar 14th, 2007, 8:18pm »
Quote Quote Modify Modify

Maybe a simpler way to see the identity A(i', j) = (-1)j C(i, j) is that, since 0j<p, we can view C(x, j) as a polynomial in Fp[x], so
 
A(i', j) = C(p-1-i, j) = C(-1-i, j) = (-1)jC(i,j).
 
More generally, if j<pk, then C(n+pk, j) = C(n, j) mod p for all n (positive or negative), though this is a bit trickier since j can be divisible by p.  So this works for A=A(pk) too (but it's not necessary, once we know how to get A(pk) from A(p)).
 
 
This says that if we take the matrix of A, flip it upside down, and negate every other column, we get the matrix of C=(C(i,j)).  Of course the rows of C are symmetric, but this implies that also the columns/diagonals of C have symmetry mod p, but only if we take the first q rows, q a power of p.  For example, when q=p=7, C mod p is
 
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 3 3 5 1
1 6 1 6 1 6 1,
 
and we can see that the columns/diagonals of C alternate symmetric and skew-symmetric, but this isn't at all obvious from looking at the integer matrix.
 
In writing this, I just realized another proof: The p-th (or more generally pk-th) row of C is simply 1000...0001, so the bottom row of C is 1,-1,1,-1,...,1 (p elements).  Let C'(i,j) = (-1)jC(i,j).  Since the zeroth column and the bottom row of C' are all 1s, to show that C' is A flipped upside down, it suffices to note
 
C'(i, j) = (-1)jC(i, j) = (-1)j[C(i+1, j) - C(i, j-1)] = C'(i+1, j) + C'(i, j-1),
 
i.e., each element of C' is the sum of the elements below and left of it.
 
 
Once we have A2(i',j') = A(i,j), we could alternately compute
 
A3(i',j') = A(i', k)A2(k, j')
 = (-1)kC(i,k)A(k',j)
 = (-1)j (-1)k C(i,k)C(k,j)
 = (i,j),
 
which uses another combinatorial identity for the last line.
 
 
So A has order 3 mod p.  Remarkable, no?  This tells us almost everything we need to know to find the characteristic polynomial of A, or even its Jordan canonical form.
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Char poly of binomial matrix  
« Reply #15 on: Mar 16th, 2007, 10:16am »
Quote Quote Modify Modify

on Mar 14th, 2007, 8:18pm, Eigenray wrote:
So A has order 3 mod p.  Remarkable, no?

Yes, definitely. If this result is not known, I would encourage you to write a paper on it.
 
Quote:
This tells us almost everything we need to know to find the characteristic polynomial of A

Maybe, but not to me (I am not an expert in eigensystems, but try to learn more). The sparse knowledge tells that the c.p. has degree p, and is divisible by (x3 – 1). I did analyze some small cases, which allowed me to formulate the formulate conjecture: C(p) = (x3 – 1)nC’(p), where n = |_ p/3 _|, and C’(p) depends on the residue p mod 3:  C’(p) = 1, x-1, x2+x+1, if p = 0, 1, 2 mod 3, respectively.  
 
I don't know how to prove this, though.  Huh
 
If my guess is correct, does that means A(p) is not diagonalizable over Z/p?
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Char poly of binomial matrix  
« Reply #16 on: Mar 16th, 2007, 4:08pm »
Quote Quote Modify Modify

on Mar 16th, 2007, 10:16am, Barukh wrote:

Yes, definitely. If this result is not known, I would encourage you to write a paper on it.

Someone already has, which I found shortly after posting this problem here last year.  They consider the more general case, for example they give a formula relating the characteristic polynomials of A(q-k) and A(k) mod p, for q a power of p.
 
They actually give a different proof that A=A(q) has order 3 mod p.  But the proof in this thread can be expressed quite nicely with matrices:
 
Let Cij = C(i,j) as before, and define the permutation matrix Pij = (i',j), i.e., the matrix with 1s on the anti-diagonal.  Also let Sij = (-1)j(i,j) = diag(1,-1,1,-1,...,1).  (All these have indices 0 i,j < q.)  Then the proof follows from one congruence mod p, and two combinatorial identities:
 
1) A = PCS  (mod p),  i.e., C(i+j,j) = (-1)j C(q-1-i,j).
2) A = CCt (Vandermonde)
3) (CS)2 = I, i.e., (-1)k C(i,k)C(k,j) = (-1)j(i,j).
 
Then we have
 
A2 = AAt = (PCS)(StCtPt) = PCCtP = PAP,
 
which says A is a reflection of A, and then
 
A3 = PAPA = P(PCS)P(PCS) = (CS)(CS) = I.
 
Quote:
C(p) = (x3 – 1)nC’(p), where n = |_ p/3 _|, and C’(p) depends on the residue p mod 3:  C’(p) = 1, x-1, x2+x+1, if p = 0, 1, 2 mod 3, respectively.

That is it exactly, and the same is true replacing p by a power of p (but still working mod p).  In a sense, it's as close as possible to (x3-1)q/3.
 
Quote:
I don't know how to prove this, though.  Huh

Finding the characteristic polynomial is equivalent to determining the eigenvalues, together with their multiplicities.  A3=I gives you the possible eigenvalues.  The multiplicities must add up to p, so you need two more pieces of information to finish.
 
Quote:
If my guess is correct, does that means A(p) is not diagonalizable over Z/p?

It follows from the Jordan normal form that a matrix is diagonalizable (over some field F) iff its minimal polynomial splits into distinct linear factors over F.  (More generally, the multiplicity of a root of the minimal polynomial is the size of the largest Jordan block corresponding to that eigenvalue.)
 
Since A3=I, the minimal polynomial divides x3-1, which has distinct roots (of degree no more than 2) over Fp iff p 3.  So A is diagonalizable over Fp^2 for all p except 3, and in fact diagonalizable over Fp for p=1 mod 3.
« Last Edit: Mar 20th, 2007, 12:20pm by Eigenray » IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Char poly of binomial matrix  
« Reply #17 on: Mar 17th, 2007, 6:22am »
Quote Quote Modify Modify

on Mar 16th, 2007, 4:08pm, Eigenray wrote:

Someone already has, which I found shortly after posting this problem here last year.  They consider the more general case, for example they give a formula relating the characteristic polynomials of A(q-k) and A(k) mod p, for q a power of p.

Thanks. I will try to study this paper.
 
Quote:
Finding the characteristic polynomial is equivalent to determining the eigenvalues, together with their multiplicities.  A3=I gives you the possible eigenvalues.

Yes, I knew this.
 
Quote:
The multiplicities must add up to p, so you need two more pieces of information to finish.

Huh
 
Quote:
Since A3=I, and A I, the minimal polynomial is x3-1, which has distinct roots (of degree no more than 2) over Fp iff p 3

Um? Let x3 – 1 = (x – r)(x – s)(x – t), where r, s, t are (not necessarily distinct) elements in the field Z/p. It is not difficult to see that this implies that one of the elements, say t, has a multiplicative order 3. And this is possible only when p = 1 mod 3. Then, r = 1, s = t2. For instance in F/13, x3 – 1 = (x-1)(x-3)(x-9).  
 
Quote:
and in fact diagonalizable over Fp for p=1 mod 3.

This is clear, when you know the multiplicity of the x3 – 1 in the c.p.
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Char poly of binomial matrix  
« Reply #18 on: Mar 17th, 2007, 1:50pm »
Quote Quote Modify Modify

on Mar 17th, 2007, 6:22am, Barukh wrote:
Huh

For p3, the eigenvalues are 1, , 2, say with multiplicities a, b, b', respectively, where Fp^2 is a primitive 3rd root of unity (and Fp iff p=1 mod 3).
 
We already know a+b+b' = p, so we need two more equations to determine a,b,b'.
 
Quote:
Um?

Sorry, I meant that it has distinct roots in some extension of Fp, i.e., it's separable over Fp.
« Last Edit: Mar 17th, 2007, 1:51pm by Eigenray » IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Char poly of binomial matrix  
« Reply #19 on: Mar 20th, 2007, 10:16am »
Quote Quote Modify Modify

I give it a try wih the paper. Unfortunately, the gaps are too big to follow (for me). I did  like the more symmetrical expression for the c.p. though.
 
So, let's proceed slowly, if you don't mind.
 
on Mar 17th, 2007, 1:50pm, Eigenray wrote:

For p3, the eigenvalues are 1, , 2, say with multiplicities a, b, b', respectively, where Fp^2 is a primitive 3rd root of unity (and Fp iff p=1 mod 3).

How do we know there are no other eigenvalues? Otherwise, even the equation we have isn't justified.
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Char poly of binomial matrix  
« Reply #20 on: Mar 20th, 2007, 12:21pm »
Quote Quote Modify Modify

on Mar 20th, 2007, 10:16am, Barukh wrote:
How do we know there are no other eigenvalues? Otherwise, even the equation we have isn't justified.

If A3 = I, and Av = v, then 3=1.  More generally, if f(A) = 0, and Av = v, then f()=0, which shows that every eigenvalue is a root of the minimal polynomial of A.
IP Logged
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Char poly of binomial matrix  
« Reply #21 on: Mar 20th, 2007, 11:36pm »
Quote Quote Modify Modify

on Mar 20th, 2007, 12:21pm, Eigenray wrote:
More generally, if f(A) = 0, and Av = v, then f()=0, which shows that every eigenvalue is a root of the minimal polynomial of A.

Isnt it true (By Cayley Hamilton) that a minimal polynomial of a given matrix divides its characteristic polynomial. How can we be sure that *every* eigenvalue will satisfy the minimal polynomial?
 
-- AI
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Char poly of binomial matrix  
« Reply #22 on: Mar 21st, 2007, 1:49pm »
Quote Quote Modify Modify

on Mar 20th, 2007, 11:36pm, TenaliRaman wrote:

Isnt it true (By Cayley Hamilton) that a minimal polynomial of a given matrix divides its characteristic polynomial. How can we be sure that *every* eigenvalue will satisfy the minimal polynomial?

Yes, by definition (since F[t] is a principal ideal domain) the minimal polynomial mA of A divides any other polynomial which has A as a root.  By Cayley Hamilton, the minimal polynomial divides the characteristic polynomial cA, so every root of mA is an eigenvalue.  There are two ways to see the converse.
 
The easiest way is to suppose is an eigenvalue, i.e., say Av = v with v 0.  Writing mA(t) = ai ti, we have
0 = Ov = mA(A)v = aiAiv = aiiv = mA()v,
 
and so mA()=0.
 
But there's another way to look at the problem, which also tells you the multiplicities of each eigenvalue in mA.  WLOG we may assume A is in Jordan normal form, with blocks J1, ..., Jk.  Since A is block diagonal, the minimal polynomial of A is the lcm of the minimal polynomials of the Jis, and we can see that the minimal polynomial of an n x n Jordan block, with eigenvalue , is just (t-)n, which is also the characteristic polynomial of the Jordan block.
 
So the minimal polynomial of A is the lcm of the minimal/characteristic polynomials of its Jordan blocks, while the characteristic polynomial of A is the product of these polynomials.  In particular, the multiplicity of in mA is the size of the largest Jordan block corresponding to , while the multiplicity in cA is the sum of the sizes of the corresponding blocks.  One consequence of this, as I mentioned before, is that A is diagonalizable (over some field extension) iff its minimal polynomial has no repeated roots.
IP Logged
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Char poly of binomial matrix  
« Reply #23 on: Mar 21st, 2007, 2:10pm »
Quote Quote Modify Modify

on Mar 21st, 2007, 1:49pm, Eigenray wrote:

The easiest way is to suppose is an eigenvalue, i.e., say Av = v with v 0.  Writing mA(t) = ai ti, we have
0 = Ov = mA(A)v = aiAiv = aiiv = mA()v,
 
and so mA()=0.

Awesome. I have never done linear algebra, the abstract algebra way, so this converse never really came up anywhere in my texts. Thanks for this info!
 
Quote:
But there's another way to look at the problem, which also tells you the multiplicities of each eigenvalue in mA.  WLOG we may assume A is in Jordan normal form, with blocks J1, ..., Jk.  Since A is block diagonal, the minimal polynomial of A is the lcm of the minimal polynomials of the Jis, and we can see that the minimal polynomial of an n x n Jordan block, with eigenvalue , is just (t-)n, which is also the characteristic polynomial of the Jordan block.
 
So the minimal polynomial of A is the lcm of the minimal/characteristic polynomials of its Jordan blocks, while the characteristic polynomial of A is the product of these polynomials.  In particular, the multiplicity of in mA is the size of the largest Jordan block corresponding to , while the multiplicity in cA is the sum of the sizes of the corresponding blocks.  One consequence of this, as I mentioned before, is that A is diagonalizable (over some field extension) iff its minimal polynomial has no repeated roots.

I think i got the first paragraph and probably most of the second paragraph. I still dont see the consequence you mention, but let me not jump to it. I will read up on these things, then i will probably understand these paragraphs. Thanks for this info though, never knew that you can see the characteristic polynomial as a product of characteristic polynomials of the Jordan blocks, even though it seems to make so much sense.
 
-- AI
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Char poly of binomial matrix  
« Reply #24 on: Mar 22nd, 2007, 6:47am »
Quote Quote Modify Modify

on Mar 21st, 2007, 1:49pm, Eigenray wrote:
The easiest way is to suppose is an eigenvalue, i.e., say Av = v with v 0.  Writing mA(t) = ai ti, we have
0 = Ov = mA(A)v = aiAiv = aiiv = mA()v,
 
and so mA()=0.

Yes, of course!  
 
on Mar 21st, 2007, 1:49pm, Eigenray wrote:

But there's another way to look at the problem, which also tells you the multiplicities of each eigenvalue in mA.  WLOG we may assume A is in Jordan normal form, with blocks J1, ..., Jk...

That doesn't help to find the multiplicites in our case, does it?
 
Well, I think I know how to proceed.
 
on Mar 17th, 2007, 1:50pm, Eigenray wrote:

For p3, the eigenvalues are 1, , 2, say with multiplicities a, b, b', respectively, where Fp^2 is a primitive 3rd root of unity (and Fp iff p=1 mod 3).
 
We already know a+b+b' = p, so we need two more equations to determine a,b,b'.

Another equation would be b = b’ (because , 2 are kind of conjugate), and the last is: a-b = Tr(A) mod p. The latter turns out to be equal to -(-1)p mod 3. This gives the answer.
 
It remains then to prove the last identity.
IP Logged
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board