Author 
Topic: Char poly of binomial matrix (Read 3399 times) 

Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Char poly of binomial matrix
« on: Feb 3^{rd}, 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+j}C_{i}). That is, the upperleft 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(p^{k}) 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 10^{th}, 2006, 10:43pm » 
Quote Modify

Definitely have a look at A, A^{2}, A^{3}, ... 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 21^{st}, 2006, 8:56am » 
Quote Modify

Let me start with the following question: Does it help to know that if (m_{0},
, m_{d}) and (n_{0},
, n_{d}) are the expansions of numbers m, n in base p (a prime), then C(n, m) = C(n_{0}, m_{0})
C(n_{d}, m_{d}) mod p?


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Char poly of binomial matrix
« Reply #3 on: Feb 21^{st}, 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(2^{k}), 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(p^{k}). 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 24^{th}, 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 A^{2} 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 A^{3} 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 8^{th}, 2007, 9:10am » 
Quote Modify

on Feb 24^{th}, 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, A^{3}(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. A^{2}(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 A^{2}(p) (1, 1) = 0. [Edited: well, in fact, I do. ]

« Last Edit: Mar 8^{th}, 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 8^{th}, 2007, 2:12pm » 
Quote Modify

on Mar 8^{th}, 2007, 9:10am, Barukh wrote: Well, it turns out that for any prime p, A^{3}(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(p^{k})^{3} = I mod p^{2}, but my method of proof will not show it, since the relation between A^{2} and A fails mod p^{2}. Quote:These are simple observations, though... I have no idea how to show, for instance, that A^{2}(p) (1, 1) = 0. 
 The claim is that A^{2}(i', j') = A(i,j) mod p, where i' = p1i. 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 p^{2}.)


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Char poly of binomial matrix
« Reply #7 on: Mar 9^{th}, 2007, 3:40am » 
Quote Modify

on Mar 8^{th}, 2007, 2:12pm, Eigenray wrote:Any which aren't the square of a prime? 
 No. Quote:The claim is that A^{2}(i', j') = A(i,j) mod p, where i' = p1i. 
 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, A^{2}(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 9^{th}, 2007, 7:37am » 
Quote Modify

A^{2}(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 10^{th}, 2007, 2:18am » 
Quote Modify

on Mar 9^{th}, 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 10^{th}, 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 12^{th}, 2007, 5:40am » 
Quote Modify

on Mar 10^{th}, 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 12^{th}, 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 14^{th}, 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(p1i, j) = C(p1i+j, j) = (pi+j1)(pi+j2)
(pi) / j! Consider this as a polynomial in p. Its free term equals: (1)^{j}i(i1)
(ij+1) / j! = (1)^{j}C(i, j) and is an integer. Therefore, the sum of ppowers is also an integer, and as such is divisible by p. So, we get: A(p1i, j) = (1)^{j}C(i, j) mod p (1) Next, we proceed (mod p): A^{2}(p1i, p1j) = _{k} A(p1i,k)A(k,p1j) = (A is symmetric) _{k} A(p1i,k)A(p1j,k) = (from (1)) _{k} (1)^{2k}C(i, k)C(j, k) = (Vandermonde Identity) C(i+j, i) = A(i, j), as stated. Finally (this time p being an odd prime): A^{3}(i,j) = _{k} A(i,k)A^{2}(k,j) = _{k} A(i,k)A(p1j,p1k) = _{k} (1)^{p1}C(p1i,k)C(j,p1k) = C(p1i+j, p1). 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 14^{th}, 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 F_{p}[x], so A(i', j) = C(p1i, j) = C(1i, j) = (1)^{j}C(i,j). More generally, if j<p^{k}, then C(n+p^{k}, 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(p^{k}) too (but it's not necessary, once we know how to get A(p^{k}) 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 skewsymmetric, but this isn't at all obvious from looking at the integer matrix. In writing this, I just realized another proof: The pth (or more generally p^{k}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)^{j}C(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)^{j}C(i, j) = (1)^{j}[C(i+1, j)  C(i, j1)] = C'(i+1, j) + C'(i, j1), i.e., each element of C' is the sum of the elements below and left of it. Once we have A^{2}(i',j') = A(i,j), we could alternately compute A^{3}(i',j') = A(i', k)A^{2}(k, j') = (1)^{k}C(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 16^{th}, 2007, 10:16am » 
Quote Modify

on Mar 14^{th}, 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 (x^{3} 1). I did analyze some small cases, which allowed me to formulate the formulate conjecture: C(p) = (x^{3} 1)^{n}C(p), where n = _ p/3 _, and C(p) depends on the residue p mod 3: C(p) = 1, x1, x^{2}+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 16^{th}, 2007, 4:08pm » 
Quote Modify

on Mar 16^{th}, 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(qk) 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 C_{ij} = C(i,j) as before, and define the permutation matrix P_{ij} = (i',j), i.e., the matrix with 1s on the antidiagonal. Also let S_{ij} = (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(q1i,j). 2) A = CC^{t} (Vandermonde) 3) (CS)^{2} = I, i.e., (1)^{k} C(i,k)C(k,j) = (1)^{j}(i,j). Then we have A^{2} = AA^{t} = (PCS)(S^{t}C^{t}P^{t}) = PCC^{t}P = PAP, which says A is a reflection of A, and then A^{3} = PAPA = P(PCS)P(PCS) = (CS)(CS) = I. Quote:C(p) = (x^{3} 1)^{n}C(p), where n = _ p/3 _, and C(p) depends on the residue p mod 3: C(p) = 1, x1, x^{2}+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 (x^{3}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. A^{3}=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 A^{3}=I, the minimal polynomial divides x^{3}1, which has distinct roots (of degree no more than 2) over F_{p} iff p 3. So A is diagonalizable over F_{p^2} for all p except 3, and in fact diagonalizable over F_{p} for p=1 mod 3.

« Last Edit: Mar 20^{th}, 2007, 12:20pm by Eigenray » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Char poly of binomial matrix
« Reply #17 on: Mar 17^{th}, 2007, 6:22am » 
Quote Modify

on Mar 16^{th}, 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(qk) 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. A^{3}=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 A^{3}=I, and A I, the minimal polynomial is x^{3}1, which has distinct roots (of degree no more than 2) over F_{p} iff p 3 
 Um? Let x^{3} 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 = t^{2}. For instance in F/13, x^{3} 1 = (x1)(x3)(x9). Quote:and in fact diagonalizable over F_{p} for p=1 mod 3. 
 This is clear, when you know the multiplicity of the x^{3} 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 17^{th}, 2007, 1:50pm » 
Quote Modify

on Mar 17^{th}, 2007, 6:22am, Barukh wrote: For p3, the eigenvalues are 1, , ^{2}, say with multiplicities a, b, b', respectively, where F_{p^2} is a primitive 3rd root of unity (and F_{p} 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 F_{p}, i.e., it's separable over F_{p}.

« Last Edit: Mar 17^{th}, 2007, 1:51pm by Eigenray » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Char poly of binomial matrix
« Reply #19 on: Mar 20^{th}, 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 17^{th}, 2007, 1:50pm, Eigenray wrote: For p3, the eigenvalues are 1, , ^{2}, say with multiplicities a, b, b', respectively, where F_{p^2} is a primitive 3rd root of unity (and F_{p} 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 20^{th}, 2007, 12:21pm » 
Quote Modify

on Mar 20^{th}, 2007, 10:16am, Barukh wrote:How do we know there are no other eigenvalues? Otherwise, even the equation we have isn't justified. 
 If A^{3} = 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 20^{th}, 2007, 11:36pm » 
Quote Modify

on Mar 20^{th}, 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 21^{st}, 2007, 1:49pm » 
Quote Modify

on Mar 20^{th}, 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 m_{A} of A divides any other polynomial which has A as a root. By Cayley Hamilton, the minimal polynomial divides the characteristic polynomial c_{A}, so every root of m_{A} 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 m_{A}(t) = a_{i} t^{i}, we have 0 = Ov = m_{A}(A)v = a_{i}A^{i}v = a_{i}^{i}v = m_{A}()v, and so m_{A}()=0. But there's another way to look at the problem, which also tells you the multiplicities of each eigenvalue in m_{A}. WLOG we may assume A is in Jordan normal form, with blocks J_{1}, ..., J_{k}. Since A is block diagonal, the minimal polynomial of A is the lcm of the minimal polynomials of the J_{i}s, 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 m_{A} is the size of the largest Jordan block corresponding to , while the multiplicity in c_{A} 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 21^{st}, 2007, 2:10pm » 
Quote Modify

on Mar 21^{st}, 2007, 1:49pm, Eigenray wrote: The easiest way is to suppose is an eigenvalue, i.e., say Av = v with v 0. Writing m_{A}(t) = a_{i} t^{i}, we have 0 = Ov = m_{A}(A)v = a_{i}A^{i}v = a_{i}^{i}v = m_{A}()v, and so m_{A}()=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 m_{A}. WLOG we may assume A is in Jordan normal form, with blocks J_{1}, ..., J_{k}. Since A is block diagonal, the minimal polynomial of A is the lcm of the minimal polynomials of the J_{i}s, 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 m_{A} is the size of the largest Jordan block corresponding to , while the multiplicity in c_{A} 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 22^{nd}, 2007, 6:47am » 
Quote Modify

on Mar 21^{st}, 2007, 1:49pm, Eigenray wrote:The easiest way is to suppose is an eigenvalue, i.e., say Av = v with v 0. Writing m_{A}(t) = a_{i} t^{i}, we have 0 = Ov = m_{A}(A)v = a_{i}A^{i}v = a_{i}^{i}v = m_{A}()v, and so m_{A}()=0. 
 Yes, of course! on Mar 21^{st}, 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 m_{A}. WLOG we may assume A is in Jordan normal form, with blocks J_{1}, ..., J_{k}... 
 That doesn't help to find the multiplicites in our case, does it? Well, I think I know how to proceed. on Mar 17^{th}, 2007, 1:50pm, Eigenray wrote: For p3, the eigenvalues are 1, , ^{2}, say with multiplicities a, b, b', respectively, where F_{p^2} is a primitive 3rd root of unity (and F_{p} 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: ab = 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 



