wu :: forums - Print Page


    
      
        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 4^th, 2007, 8:14pm)

Title: Devil Matrix
Post by ecoist on Jan 4^th, 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 4^th, 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 5^th, 2007, 4:51pm

Of course I am kidding. I made up Amityville matrix, silly.

Title: Re: Devil Matrix
Post by THUDandBLUNDER on Jan 5^th, 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 5^th, 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 6^th, 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 6^th, 2007, 1:53pm

Hmm. Sure?

Title: Re: Devil Matrix
Post by Barukh on Jan 7^th, 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 7^th, 2007, 8:58pm

???

Title: Re: Devil Matrix
Post by Eigenray on Jan 9^th, 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 9^th, 2007, 11:54pm

Well, I have the case that A is circulant at least.

Suppose A is circulant, i.e., a_i,j = c_j-i, where j-i is computed mod n=667. Let z denote a primitive n-th root of unity, and let v_k be the vector (1, z^k, z^2k, ..., z^(n-1)k). Then the i-th entry of Av_k is

[sum]_j a_i,j (v_k)_j = [sum]_j c_j-i z^jk
= [sum]_j' c_j' z^(j'+i)k
= z^ik [sum] c_jz^jk
= f(z^k) (v_k)_i,

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

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

f(x) = 4(1+x+...+x^n-1) - 4 - 9g(x)
= 4(xⁿ-1)/(x-1) - 4 - 9g(x),

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

Title: Re: Devil Matrix
Post by Eigenray on Jan 13^th, 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 v_i 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 = v_i + x+y = v_i + 9x/5 = v_i (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 - v₁w, 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 13^th, 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 13^th, 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 14^th, 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 14^th, 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 14^th, 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 D₃ is well known (among combinatorialists). It's eigenvalues (mod 3) are, one 0, and 666 2's. Hence its rank is 666 over F₃.

Title: Re: Devil Matrix
Post by ecoist on Jan 14^th, 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 v_i, which have a 1 in the first position, a -1 in the i-th position, and zeros elsewhere, for i=2,...,n. Then v_i is easily seen as an eigenvector of C with eigenvalue a-b. That's n linearly independent eigenvectors for C.