wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> putnam exam (pure math) >> Devil Matrix
(Message started by: ecoist on Jan 4th, 2007, 8:14pm)

Title: Devil Matrix
Post by ecoist on Jan 4th, 2007, 8:14pm
Let A be a 667x667 matrix with zeros on the main diagonal and in which every row contains 370 4's and 296 -5's.  Show that A has rank 666.

Title: Re: Devil Matrix
Post by Michael_Dagg on Jan 4th, 2007, 8:44pm
Ah, the Amityville matrix. Let pray for a norm rank reducing technique!

Title: Re: Devil Matrix
Post by Michael_Dagg on Jan 5th, 2007, 4:51pm
Of course I am kidding. I made up Amityville matrix, silly.

Title: Re: Devil Matrix
Post by THUDandBLUNDER on Jan 5th, 2007, 4:55pm

on 01/05/07 at 16:51:17, Michael_Dagg wrote:
Of course I am kidding. I made up Amityville matrix, silly.

That didn't stop me Googling for it.   :D

I think a rank rank reducing technique would also do.   ;)

Title: Re: Devil Matrix
Post by Michael_Dagg on Jan 5th, 2007, 5:30pm
I was messing with ecoist (as we routinely mess with each  
other off forum), but this is funny -- sorry to mislead you!

Does this mean that the since the Trace(M) = 0, M is not  
invertible (as in convertible from the devil to Christ)?

Title: Re: Devil Matrix
Post by ecoist on Jan 6th, 2007, 10:46am
You found me out, Michael!  Since the guys here are as wise as saints, I mess-with-top-of-these!

Title: Re: Devil Matrix
Post by Michael_Dagg on Jan 6th, 2007, 1:53pm
Hmm. Sure?

Title: Re: Devil Matrix
Post by Barukh on Jan 7th, 2007, 5:35am

on 01/05/07 at 17:30:38, Michael_Dagg wrote:
Does this mean that the since the Trace(M) = 0, M is not  
invertible (as in convertible from the devil to Christ)?

??? ::)

Title: Re: Devil Matrix
Post by Michael_Dagg on Jan 7th, 2007, 8:58pm
???

Title: Re: Devil Matrix
Post by Eigenray on Jan 9th, 2007, 9:34pm
???

I haven't made much progress, but in the case that A is circulant, the problem is equivalent to the statement that if f(x) is a polynomial of degree 665, with 370 coefficients equal to 4, and 296 equal to -5, then f is not divisible by the 23rd, 29th, or 667th cyclotomic polynomials.  (This case would be much easier if 667 were prime!)

Title: Re: Devil Matrix
Post by Eigenray on Jan 9th, 2007, 11:54pm
Well, I have the case that A is circulant at least.

Suppose A is circulant, i.e., ai,j = cj-i, where j-i is computed mod n=667.  Let z denote a primitive n-th root of unity, and let vk be the vector (1, zk, z2k, ..., z(n-1)k).  Then the i-th entry of Avk is

[sum]j ai,j (vk)j = [sum]j cj-i zjk
= [sum]j' cj' z(j'+i)k
= zik [sum] cjzjk
= f(zk) (vk)i,

where f(x) = [sum] cj xj.  So vk is an eigenvector with eigenvalue f(zk).  By the Vandermonde determinant, and the fact that {zk : 0<k<n} are distinct, the n vectors {vk} are linearly independent, so the rank of A is the number of k for which f(zk) is non-zero.

Since 370 of the cj are 4, and 296 are -5 (and c0=0), it follows f(1)=0.  Hence it suffices to show that if f(zk)=0, then k=0.  But we can write

f(x) = 4(1+x+...+xn-1) - 4 - 9g(x)
= 4(xn-1)/(x-1) - 4 - 9g(x),

where g is a sum of 296 distinct powers of x.  So if x=zk is a n-th root of 1, but not 1 itself, and f(x)=0, then the above equation shows g(zk) = -4/9.  But z is an algebraic integer, and therefore so is g(zk), a contradiction.

Title: Re: Devil Matrix
Post by Eigenray on Jan 13th, 2007, 6:10am
Remembering a [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1141190497]similar problem[/link]:

Suppose Av = 0, and that v has integer entries.  For each i, considering the i-th row of A shows that the entries other than vi can be partitioned into two subsets, with sums x and y, such that 4x=5y.  It follows that the sum of the entries of v is

S = vi + x+y = vi + 9x/5 = vi (mod 9).

Thus all entries of v are congruent mod 9.

Since the vector w of all 1s is in the kernel of A, the argument applies to v' = v - v1w, which has first entry 0, and we find that v' is divisible by arbitrarily large powers of 9.  It follows v'=0, and A has nullity 1, as desired.

Title: Re: Devil Matrix
Post by Barukh on Jan 13th, 2007, 9:25am
Eigenray, I am not sure I understand your argument. Could you elaborate, please?

Title: Re: Devil Matrix
Post by Eigenray on Jan 13th, 2007, 10:03pm
I'll rephrase: if w is the vector of all 1s, then Aw = 0, since each row of A has sum 0.  Conversely, suppose Av = 0; we show v is a multiple of w.  By the rank-nullity theorem, it will follow A has rank 666.

By subtracting a multiple of w, we may assume that one of the entries of v is 0.  If v is the 0 vector we're done.  Otherwise, we may scale v by some rational so that its entries are integers with no common factor.

Let B be the matrix of all 4s.  Then A = B - 4I mod 9.  So if Av = 0, then Bv = 4v mod 9.  But Bv is a constant vector, so v is constant mod 9.  Since one of the entries is 0, all entries are divisible by 9, a contradiction.

Title: Re: Devil Matrix
Post by Aryabhatta on Jan 14th, 2007, 11:10am
Here is a different proof, which in essence is probably same as Eigenray's.


Let the given matrix be D.

Consider D as a matrix D_3 over the ternary field F_3 (in essence work modulo 3).

We can show that rank(D) >= rank(D_3)

D_3 has all entries 1 except the main diagonal, which is all zeroes.

Let J be the all 2's matrix.

Now D_3 + J = 2I

Now we have that rank(A) + rank(B) >= rank(A+B)  (consider the row spans)

Thus rank(D_3) + rank(J) >= rank(2I)

i.e rank(D_3) + 1 >= 667.

thus rank(D) >= rank(D_3) >= 666

Since rank(D) =/= 667 the result follows.


Title: Re: Devil Matrix
Post by Eigenray on Jan 14th, 2007, 3:51pm
That argument seems simpler.  It didn't occur to me since I was approaching it like the other problem, as in:

Given 9n+1 real numbers, such that for each number, the others can be partitioned into two groups, of 4n and 5n numbers, with the same average.  Show that all the numbers are equal.

Title: Re: Devil Matrix
Post by ecoist on Jan 14th, 2007, 5:05pm
Wow, Eigenray and Aryabhatta!  Eigenray exposed my devlilsh attempt to disguise a problem previously posted, and Aryabhatta's solution almost gave me a heart attack!

However, I would like to point out a variant of  part of Aryabhatta's proof.  The matrix D3 is well known (among combinatorialists).  It's eigenvalues (mod 3) are, one 0, and 666 2's.  Hence its rank is 666 over F3.

Title: Re: Devil Matrix
Post by ecoist on Jan 14th, 2007, 8:23pm
So that there is no doubt how amazingly simple Aryabhatta's proof is, let me show how easy it is to compute the eigenvalues of a matrix C whose main diagonal has all its entries equal to the number a and whose off-diagonal entries are all equal the number b.

All row sums of C equal a+(n-1)b, where n is the size of the square matrix C.  Hence the vector of all 1's is an eigenvector of C with eigenvalue a+(n-1)b.  Now consider the n-1 vectors vi, which have a 1 in the first position, a -1 in the i-th position, and zeros elsewhere, for i=2,...,n.  Then vi is easily seen as an eigenvector of C with eigenvalue a-b.  That's n linearly independent eigenvectors for C.



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