wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Char poly of binomial matrix
        
(Message started by: Eigenray on Feb 3rd, 2006, 3:15pm)
Title: Char poly of binomial matrix
Post by Eigenray on Feb 3rd, 2006, 3:15pm
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) [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1138334283]another thread[/link].)
Title: Re: Char poly of binomial matrix
Post by Eigenray on Feb 10th, 2006, 10:43pm
Definitely have a look at A, A2, A3, ... mod p for a few cases!  Proving that is half the problem.
Title: Re: Char poly of binomial matrix
Post by Barukh on Feb 21st, 2006, 8:56am
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?
Title: Re: Char poly of binomial matrix
Post by Eigenray on Feb 21st, 2006, 4:51pm
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!
Title: Re: Char poly of binomial matrix
Post by Eigenray on Feb 24th, 2007, 6:50pm
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?
Title: Re: Char poly of binomial matrix
Post by Barukh on Mar 8th, 2007, 9:10am

on 02/24/07 at 18:50:22, 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.  ;D]
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 8th, 2007, 2:12pm

on 03/08/07 at 09:10:51, 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.)
Title: Re: Char poly of binomial matrix
Post by Barukh on Mar 9th, 2007, 3:40am

on 03/08/07 at 14:12:06, Eigenray wrote:
Any which aren't the square of a prime?

No.  ;)


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.
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 9th, 2007, 7:37am
A2(i',j') = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif A(i', k) A(k, j').

What is A(i', k) mod p?
Title: Re: Char poly of binomial matrix
Post by Barukh on Mar 10th, 2007, 2:18am

on 03/09/07 at 07:37:46, 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.
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 10th, 2007, 6:01pm
Compare A(i', k) with C(i, k), mod p.
Title: Re: Char poly of binomial matrix
Post by Barukh on Mar 12th, 2007, 5:40am

on 03/10/07 at 18:01:40, 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...
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 12th, 2007, 4:53pm
I said to compare A(i', k) with C(i, k), not C(i'+k, k) . . .

:'( :-* :-/ :-X :-[ :P ::) ??? 8) :o :( >:( ;D :D ;) :)
Title: Re: Char poly of binomial matrix
Post by Barukh on Mar 14th, 2007, 12:01am
Oops… Sorry, Eigenray. Too little time to concentrate on this problem. It remains to think at nights  ;D. 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) =
  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifk A(p-1-i,k)A(k,p-1-j)  =  (A is symmetric)
  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifk A(p-1-i,k)A(p-1-j,k)  = (from (1))
   http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifk (-1)2kC(i, k)C(j, k) =  (Vandermonde Identity (http://en.wikipedia.org/wiki/Vandermonde's_identity))
C(i+j, i) = A(i, j),

as stated.

Finally (this time p being an odd prime):

A3(i,j) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifk A(i,k)A2(k,j)  =  
   http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifk A(i,k)A(p-1-j,p-1-k)  =  
   http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifk (-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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1139008533;start=0#2)) or j < i (because of symmetry).
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 14th, 2007, 8:18pm
Maybe a simpler way to see the identity A(i', j) = (-1)j C(i, j) is that, since 0http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifj<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') = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifA(i', k)A2(k, j')
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif(-1)kC(i,k)A(k',j)
= (-1)j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif(-1)k C(i,k)C(k,j)
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/delta.gif(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.
Title: Re: Char poly of binomial matrix
Post by Barukh on Mar 16th, 2007, 10:16am

on 03/14/07 at 20:18:56, 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.  ???

If my guess is correct, does that means A(p) is not diagonalizable over Z/p?
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 16th, 2007, 4:08pm

on 03/16/07 at 10:16:26, Barukh wrote:
Yes, definitely. If this result is not known, I would encourage you to write a paper on it.

[link=http://arxiv.org/abs/math/0212144]Someone already has[/link], 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 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/delta.gif(i',j), i.e., the matrix with 1s on the anti-diagonal.  Also let Sij = (-1)jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/delta.gif(i,j) = diag(1,-1,1,-1,...,1).  (All these have indices 0http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 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., http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif(-1)k C(i,k)C(k,j) = (-1)jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/delta.gif(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.  ???

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 [link=http://en.wikipedia.org/wiki/Jordan_form]Jordan normal form[/link] 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif3.  So A is diagonalizable over Fp^2 for all p except 3, and in fact diagonalizable over Fp for p=1 mod 3.
Title: Re: Char poly of binomial matrix
Post by Barukh on Mar 17th, 2007, 6:22am

on 03/16/07 at 16:08:49, Eigenray wrote:
[link=http://arxiv.org/abs/math/0212144]Someone already has[/link], 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.

???


Quote:
Since A3=I, and A http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif I, the minimal polynomial is x3-1, which has distinct roots (of degree no more than 2) over Fp iff p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif3

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.
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 17th, 2007, 1:50pm

on 03/17/07 at 06:22:23, Barukh wrote:
???

For phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif3, the eigenvalues are 1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2, say with multiplicities a, b, b', respectively, where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifFp^2 is a primitive 3rd root of unity (and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifFp 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.
Title: Re: Char poly of binomial matrix
Post by Barukh on Mar 20th, 2007, 10:16am
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 03/17/07 at 13:50:49, Eigenray wrote:
For phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif3, the eigenvalues are 1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2, say with multiplicities a, b, b', respectively, where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifFp^2 is a primitive 3rd root of unity (and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifFp iff p=1 mod 3).

How do we know there are no other eigenvalues? Otherwise, even the equation we have isn't justified.
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 20th, 2007, 12:21pm

on 03/20/07 at 10:16:29, 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 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gifv, then http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif3=1.  More generally, if f(A) = 0, and Av = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gifv, then f(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif)=0, which shows that every eigenvalue is a root of the minimal polynomial of A.
Title: Re: Char poly of binomial matrix
Post by TenaliRaman on Mar 20th, 2007, 11:36pm

on 03/20/07 at 12:21:07, Eigenray wrote:
More generally, if f(A) = 0, and Av = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gifv, then f(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif)=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
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 21st, 2007, 1:49pm

on 03/20/07 at 23:36:40, 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif is an eigenvalue, i.e., say Av = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gifv with v http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0.  Writing mA(t) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif ai ti, we have
0 = Ov = mA(A)v = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifaiAiv = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifaihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gifiv = mA(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif)v,

and so mA(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif)=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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif, is just (t-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif)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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif in mA is the size of the largest Jordan block corresponding to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif, 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.
Title: Re: Char poly of binomial matrix
Post by TenaliRaman on Mar 21st, 2007, 2:10pm

on 03/21/07 at 13:49:56, Eigenray wrote:
The easiest way is to suppose http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif is an eigenvalue, i.e., say Av = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gifv with v http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0.  Writing mA(t) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif ai ti, we have
0 = Ov = mA(A)v = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifaiAiv = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifaihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gifiv = mA(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif)v,

and so mA(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif)=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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif, is just (t-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif)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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif in mA is the size of the largest Jordan block corresponding to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif, 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
Title: Re: Char poly of binomial matrix
Post by Barukh on Mar 22nd, 2007, 6:47am

on 03/21/07 at 13:49:56, Eigenray wrote:
The easiest way is to suppose http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif is an eigenvalue, i.e., say Av = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gifv with v http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0.  Writing mA(t) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif ai ti, we have
0 = Ov = mA(A)v = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifaiAiv = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifaihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gifiv = mA(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif)v,

and so mA(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif)=0.

Yes, of course!


on 03/21/07 at 13:49:56, 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 03/17/07 at 13:50:49, Eigenray wrote:
For phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif3, the eigenvalues are 1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2, say with multiplicities a, b, b', respectively, where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifFp^2 is a primitive 3rd root of unity (and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifFp 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2 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.
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 22nd, 2007, 11:34am

on 03/22/07 at 06:47:34, Barukh wrote:
That doesn't help to find the multiplicites in our case, does it?

I'm not sure what you mean: we know the minimal polynomial of A divides t3-1, so it has distinct roots.  This implies all Jordan blocks of A are 1x1, i.e., A is diagonalizable.  The multiplicity of an eigenvalue in the characteristic polynomial is the sum of the sizes of the Jordan blocks corresponding to it, but this is just the number of times it appears in the diagonalization of A.


Quote:
Another equation would be b = b’ (because http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2 are kind of conjugate)

This reasoning would be enough in the case p=2 mod 3, because then http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/notin.gif Fp, so the Frobenius automorphism fixes Fp (hence the characteristic polynomial) but interchanges http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2.

But in the case p=1 mod 3, a different argument is needed.  For example, there are matrices with entries in F7, with eigenvalues 1, 2, 4, of arbitrary multiplicities.


Quote:
, 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.

Exactly.  We have of course

Tr(A) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifk=0p-1 C(2k, k).

As a sort of hint, what is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifk=0http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supinfty.gif  C(2k, k) xk?  Why?
Title: Re: Char poly of binomial matrix
Post by Barukh on Mar 23rd, 2007, 8:25am

on 03/22/07 at 11:34:28, Eigenray wrote:
I'm not sure what you mean: we know the minimal polynomial of A divides t3-1, so it has distinct roots.

I meant that using all this information didn't show (at least to me) the way to calculate the multiplicites.


Quote:
This implies all Jordan blocks of A are 1x1, i.e., A is diagonalizable.

This takes me once again to the point we were discussing earlier and that is still not completely clear for me (maybe, I simply misunderstand the concept of diagonalization?).

Take p = 5. The eigenvalues of A(5) will be, as we know, 1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2, and these same values will be at the diagonal of the diagonalization of A. Now, 4 out of 5 values are not in Z/5. This clear is not in line with you statement earlier in this thread:

Quote:
that a matrix is diagonalizable (over some field F) iff its minimal polynomial splits into distinct linear factors over F.

But later you mentioned that “over F” should be replaced by “over some extension of F”. Which extension of Z/5 can we take in this case?


Quote:
But in the case p=1 mod 3, a different argument is needed.  For example, there are matrices with entries in F7, with eigenvalues 1, 2, 4, of arbitrary multilicities.

Yes… I felt something is missing here.


Quote:
As a sort of hint, what is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifk=0http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supinfty.gif  C(2k, k) xk?  Why?

It equals (1-4x)-1/2 (because of a nice identity involving convolution of central binomial coefficients).

???
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 23rd, 2007, 1:36pm

on 03/23/07 at 08:25:39, Barukh wrote:
I meant that using all this information didn't show (at least to me) the way to calculate the multiplicites.

It wasn't really intended to, it was just to show how the minimal polynomial can be read off from the Jordan normal form; in this case, knowing the minimal polynomial gives you information about the Jordan normal form.


Quote:
Take p = 5. The eigenvalues of A(5) will be, as we know, 1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2, and these same values will be at the diagonal of the diagonalization of A. Now, 4 out of 5 values are not in Z/5.

So A(5) is not diagonalizable over F5=Z/5.  But it is diagonalizable over F25 = F5[http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif], a degree 2 extension of F5, obtained by adjoining http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, a solution to x2+x+1=0.  That is, F25 is isomorphic to F5[x]/(x2+x+1), where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif corresponds to the equivalence class of x.

Explicitly, over this field, a basis of eigenvectors is

(1, 3, 3, 3, 1),
(1, 1, -1+2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, 0, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2)
(0, 1, -2-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, 1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, 0)
(1, 1, -1+2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2, 0, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif)
(0, 1, -2-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2, 1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2, 0),

with eigenvalues 1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2, respectively.


Quote:
This clear is not in line with you statement earlier in this thread:
a matrix is diagonalizable (over some field F) iff its minimal polynomial splits into distinct linear factors over F

That statement is true.  Over F5, the minimal polynomial factors into irreducibles as (x-1)(x2+x+1).  It doesn't split into linear factors, but it's still separable, because over the field F5[http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif], it factors into distinct linear factors (x-1)(x-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif)(x-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif2).  So the matrix is diagonalizable over F5[http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/omega.gif], but not over F5.


Quote:
But later you mentioned that “over F” should be replaced by “over some extension of F”.

When I said that I was referring to

Quote:
x3-1, which has distinct roots (of degree no more than 2) over Fp iff phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif3

What I meant was, if you consider x3-1 as a polynomial, not over Q, but with coefficients in Fp, then it "has distinct roots" iff phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif3.  And when I say "has distinct roots," I mean it's separable: it splits into distinct linear factors over some extension of the field containing its coefficients.  In this case, the splitting field has degree 1 or 2 over Fp.

I guess I should have used the term "separable" because it depends only on the polynomial (compared to the question "does f have a root", which depends on the field you're working in).  That is, if f has coefficients in some field F http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subset.gif K, then f is separable, viewed as a polynomial over F, iff it's separable as a polynomial over K.

(Although the term separable is also used to mean only that each irreducible factor has distinct roots in some extension -- compare [link=http://planetmath.org/encyclopedia/SeparablePolynomial.html]planetmath[/link] to [link=http://en.wikipedia.org/wiki/Separable_polynomial]wikipedia[/link] -- and with this usage, it does depend on the field.)


Quote:
Yes… I felt something is missing here.

What do you know about A and [hide]A-1[/hide]?


Quote:
It equals (1-4x)-1/2 (because of a nice identity involving convolution of central binomial coefficients).

The other way to think of it is because

(1-4x)-1/2 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifC(-1/2, k) (-4x)k = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifC(2k, k) xk
Title: Re: Char poly of binomial matrix
Post by Barukh on Mar 25th, 2007, 6:24am

Quote:
The other way to think of it is because
(1-4x)-1/2 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifC(-1/2, k) (-4x)k = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifC(2k, k) xk


Oh, I see. That’s a very simple demonstration. Here’s how I did it (actually, using the approach taken in the aforementioned paper).

I started from the following identity:
1x3x…(2k-1) = 2-k(k+1)(k+2)…(2k)

which is simply demonstrated by induction. Now, replace every term i at the left with (p-i), and take modulo p:
(p-1)(p-3)…(p-2k+1) = (-2)-k(k+1)(k+2)…(2k) mod p

Divide both sides by k!2k to get
C((p-1)/2, k) = C(2k, k)(-4)-k mod p.


Therefore (the summation is from 0 to (p-1)/2):

Tr(A) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif C(2k,k) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifC((p-1)/2, k)(-4)k = (binom!) = (-3) (p-1)/2 mod p

Using the results from quadratic residues theory, we obtain:
(-3) (p-1)/2 mod p = (-3 | p) = (p | -3) = -(-1)p mod 3,

where (x|y) is Legendre symbol (http://mathworld.wolfram.com/LegendreSymbol.html).

Eigenray, I apologize for this lengthy demonstration, yours is much more concise, but I thought that way more people will follow the discussion.

I must say that I really enjoyed working on this problem!
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 25th, 2007, 2:42pm

on 03/25/07 at 06:24:53, Barukh wrote:
Using the results from quadratic residues theory, we obtain

We don't actually need quadratic reciprocity here (or rather, the special case we need has a short proof).  For p > 3 an odd prime, -3 is a square mod p iff the equation x2 + x + 1 = 0 has a solution in Fp (since (2x+1)2 = -3).  But any solution will be a primitive 3rd root of unity; since Fp* is cyclic, this exists iff p = 1 mod 3.  So (-3|p) = (p|3).


Quote:
I must say that I really enjoyed working on this problem!

And thank you for working on it.  But it's not done yet!  So, what is the relation between A(p) and A(pk), that led me to this question in the first place?
Title: Re: Char poly of binomial matrix
Post by Barukh on Mar 29th, 2007, 10:10am

on 03/25/07 at 14:42:46, Eigenray wrote:
But it's not done yet!  So, what is the relation between A(p) and A(pk), that led me to this question in the first place?

Maybe, the following is relevant (assuming k =2 for a moment) :

From the previously mentioned property (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1139008533;start=0#2), it follows that
Amp+i,np+q(p2) = Amn(p) Aij(p)

Putting it differently, A(p2) may be divided into p2 blocks Bij of size pxp each, so that Bij = A(p)Aij(p). I learned just today that this is called matrix direct, or Kronecker product (http://en.wikipedia.org/wiki/Kronecker_product) of matrix A(p) with itself. The resulting matrix has eigenvalues equal to the Cartesian product of eigenvalues of the base matrices. In our case, eigenvalues of A(p) form a group under multiplication modulo p, therefore A(p2) will have the same eigenvalues. Their multiplicities are easily computed.

This is easily extended to any natural k.
Title: Re: Char poly of binomial matrix
Post by Eigenray on Mar 30th, 2007, 7:07pm

on 03/29/07 at 10:10:10, Barukh wrote:
Putting it differently, A(p2) may be divided into p2 blocks Bij of size pxp each, so that Bij = A(p)Aij(p).

Yes, precisely.  When p=2, this says that if A=A(q), then A(2q) is
[ A  A ]
[ A  O ],
which is exactly how Sierpinski's triangle is formed. (In fact, in this case [A(2k) mod 2] and [A(2) mod 2]http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/otimes.gif...http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/otimes.gif[A(2) mod 2] are equal as integer matrices, not just mod 2.)


Quote:
I learned just today that this is called matrix direct, or Kronecker product (http://en.wikipedia.org/wiki/Kronecker_product) of matrix A(p) with itself. The resulting matrix has eigenvalues equal to the Cartesian product of eigenvalues of the base matrices.

Moreover, if v, w, are eigenvectors of A, B, with eigenvalues http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/mu.gif, respectively, then vhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/otimes.gifw is an eigenvector of Ahttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/otimes.gifB with eigenvalue http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/mu.gif.  And if {vi}, {wj} are bases of V, W, respectively, then {vihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/otimes.gifwj} is a basis of Vhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/otimes.gifW.  So we can even give an eigenbasis for A(pk) (for phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 3).

Another way to see this: if UAU-1, VBV-1 are diagonal (or at least upper-triangular), then (Uhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/otimes.gifV)(Ahttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/otimes.gifB)(Uhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/otimes.gifV)-1 = (UAU-1)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/otimes.gif(VBV-1) is also diagonal (or upper-triangular -- so we can still read off the eigenvalues).


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