wu :: forums
« wu :: forums - Devil Matrix »

Welcome, Guest. Please Login or Register.
Dec 13th, 2024, 7:43pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: towr, SMQ, Eigenray, Grimbal, william wu, Icarus)
   Devil Matrix
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Devil Matrix  (Read 1157 times)
ecoist
Senior Riddler
****





   


Gender: male
Posts: 405
Devil Matrix  
« on: Jan 4th, 2007, 8:14pm »
Quote Quote Modify Modify

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.
IP Logged
Michael Dagg
Senior Riddler
****






   


Gender: male
Posts: 500
Re: Devil Matrix  
« Reply #1 on: Jan 4th, 2007, 8:44pm »
Quote Quote Modify Modify

Ah, the Amityville matrix. Let pray for a norm rank reducing technique!
« Last Edit: Jan 4th, 2007, 8:46pm by Michael Dagg » IP Logged

Regards,
Michael Dagg
Michael Dagg
Senior Riddler
****






   


Gender: male
Posts: 500
Re: Devil Matrix  
« Reply #2 on: Jan 5th, 2007, 4:51pm »
Quote Quote Modify Modify

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

Regards,
Michael Dagg
ThudnBlunder
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Devil Matrix  
« Reply #3 on: Jan 5th, 2007, 4:55pm »
Quote Quote Modify Modify

on Jan 5th, 2007, 4:51pm, Michael_Dagg wrote:
Of course I am kidding. I made up Amityville matrix, silly.

That didn't stop me Googling for it.   Cheesy
 
I think a rank rank reducing technique would also do.   Wink
IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Michael Dagg
Senior Riddler
****






   


Gender: male
Posts: 500
Re: Devil Matrix  
« Reply #4 on: Jan 5th, 2007, 5:30pm »
Quote Quote Modify Modify

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)?
« Last Edit: Jan 5th, 2007, 5:32pm by Michael Dagg » IP Logged

Regards,
Michael Dagg
ecoist
Senior Riddler
****





   


Gender: male
Posts: 405
Re: Devil Matrix  
« Reply #5 on: Jan 6th, 2007, 10:46am »
Quote Quote Modify Modify

You found me out, Michael!  Since the guys here are as wise as saints, I mess-with-top-of-these!
IP Logged
Michael Dagg
Senior Riddler
****






   


Gender: male
Posts: 500
Re: Devil Matrix  
« Reply #6 on: Jan 6th, 2007, 1:53pm »
Quote Quote Modify Modify

Hmm. Sure?
IP Logged

Regards,
Michael Dagg
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Devil Matrix  
« Reply #7 on: Jan 7th, 2007, 5:35am »
Quote Quote Modify Modify

on Jan 5th, 2007, 5:30pm, 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)?

 Huh Roll Eyes
IP Logged
Michael Dagg
Senior Riddler
****






   


Gender: male
Posts: 500
Re: Devil Matrix  
« Reply #8 on: Jan 7th, 2007, 8:58pm »
Quote Quote Modify Modify

Huh
IP Logged

Regards,
Michael Dagg
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Devil Matrix  
« Reply #9 on: Jan 9th, 2007, 9:34pm »
Quote Quote Modify Modify

Huh
 
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!)
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Devil Matrix  
« Reply #10 on: Jan 9th, 2007, 11:54pm »
Quote Quote Modify Modify

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.
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Devil Matrix  
« Reply #11 on: Jan 13th, 2007, 6:10am »
Quote Quote Modify Modify

Remembering a similar problem:
 
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.
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Devil Matrix  
« Reply #12 on: Jan 13th, 2007, 9:25am »
Quote Quote Modify Modify

Eigenray, I am not sure I understand your argument. Could you elaborate, please?
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Devil Matrix  
« Reply #13 on: Jan 13th, 2007, 10:03pm »
Quote Quote Modify Modify

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.
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Devil Matrix  
« Reply #14 on: Jan 14th, 2007, 11:10am »
Quote Quote Modify Modify

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.
 
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Devil Matrix  
« Reply #15 on: Jan 14th, 2007, 3:51pm »
Quote Quote Modify Modify

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.
IP Logged
ecoist
Senior Riddler
****





   


Gender: male
Posts: 405
Re: Devil Matrix  
« Reply #16 on: Jan 14th, 2007, 5:05pm »
Quote Quote Modify Modify

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.
IP Logged
ecoist
Senior Riddler
****





   


Gender: male
Posts: 405
Re: Devil Matrix  
« Reply #17 on: Jan 14th, 2007, 8:23pm »
Quote Quote Modify Modify

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.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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