Author |
Topic: Char poly of binomial matrix (Read 3410 times) |
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Char poly of binomial matrix
« on: Feb 3rd, 2006, 3:15pm » |
Quote 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:
Posts: 1948
|
|
Re: Char poly of binomial matrix
« Reply #1 on: Feb 10th, 2006, 10:43pm » |
Quote 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:
Posts: 2276
|
|
Re: Char poly of binomial matrix
« Reply #2 on: Feb 21st, 2006, 8:56am » |
Quote 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:
Posts: 1948
|
|
Re: Char poly of binomial matrix
« Reply #3 on: Feb 21st, 2006, 4:51pm » |
Quote 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:
Posts: 1948
|
|
Re: Char poly of binomial matrix
« Reply #4 on: Feb 24th, 2007, 6:50pm » |
Quote 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:
Posts: 2276
|
|
Re: Char poly of binomial matrix
« Reply #5 on: Mar 8th, 2007, 9:10am » |
Quote 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. ]
|
« Last Edit: Mar 8th, 2007, 9:44am by Barukh » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Char poly of binomial matrix
« Reply #6 on: Mar 8th, 2007, 2:12pm » |
Quote 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:
Posts: 2276
|
|
Re: Char poly of binomial matrix
« Reply #7 on: Mar 9th, 2007, 3:40am » |
Quote Modify
|
on Mar 8th, 2007, 2:12pm, 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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Char poly of binomial matrix
« Reply #8 on: Mar 9th, 2007, 7:37am » |
Quote Modify
|
A2(i',j') = A(i', k) A(k, j'). What is A(i', k) mod p?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Char poly of binomial matrix
« Reply #9 on: Mar 10th, 2007, 2:18am » |
Quote Modify
|
on Mar 9th, 2007, 7:37am, Eigenray wrote: 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:
Posts: 1948
|
|
Re: Char poly of binomial matrix
« Reply #10 on: Mar 10th, 2007, 6:01pm » |
Quote Modify
|
Compare A(i', k) with C(i, k), mod p.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Char poly of binomial matrix
« Reply #11 on: Mar 12th, 2007, 5:40am » |
Quote 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:
Posts: 1948
|
|
Re: Char poly of binomial matrix
« Reply #12 on: Mar 12th, 2007, 4:53pm » |
Quote Modify
|
I said to compare A(i', k) with C(i, k), not C(i'+k, k) . . .
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Char poly of binomial matrix
« Reply #13 on: Mar 14th, 2007, 12:01am » |
Quote Modify
|
Oops
Sorry, Eigenray. Too little time to concentrate on this problem. It remains to think at nights . 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:
Posts: 1948
|
|
Re: Char poly of binomial matrix
« Reply #14 on: Mar 14th, 2007, 8:18pm » |
Quote 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:
Posts: 2276
|
|
Re: Char poly of binomial matrix
« Reply #15 on: Mar 16th, 2007, 10:16am » |
Quote 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. If my guess is correct, does that means A(p) is not diagonalizable over Z/p?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Char poly of binomial matrix
« Reply #16 on: Mar 16th, 2007, 4:08pm » |
Quote 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. |
| 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:
Posts: 2276
|
|
Re: Char poly of binomial matrix
« Reply #17 on: Mar 17th, 2007, 6:22am » |
Quote 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. |
| 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:
Posts: 1948
|
|
Re: Char poly of binomial matrix
« Reply #18 on: Mar 17th, 2007, 1:50pm » |
Quote Modify
|
on Mar 17th, 2007, 6:22am, Barukh 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'. Quote: 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:
Posts: 2276
|
|
Re: Char poly of binomial matrix
« Reply #19 on: Mar 20th, 2007, 10:16am » |
Quote 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:
Posts: 1948
|
|
Re: Char poly of binomial matrix
« Reply #20 on: Mar 20th, 2007, 12:21pm » |
Quote 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:
Posts: 1001
|
|
Re: Char poly of binomial matrix
« Reply #21 on: Mar 20th, 2007, 11:36pm » |
Quote 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:
Posts: 1948
|
|
Re: Char poly of binomial matrix
« Reply #22 on: Mar 21st, 2007, 1:49pm » |
Quote 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:
Posts: 1001
|
|
Re: Char poly of binomial matrix
« Reply #23 on: Mar 21st, 2007, 2:10pm » |
Quote 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:
Posts: 2276
|
|
Re: Char poly of binomial matrix
« Reply #24 on: Mar 22nd, 2007, 6:47am » |
Quote 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 |
|
|
|
|