Author 
Topic: Devil Matrix (Read 1156 times) 

ecoist
Senior Riddler
Gender:
Posts: 405


Devil Matrix
« on: Jan 4^{th}, 2007, 8:14pm » 
Quote 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:
Posts: 500


Re: Devil Matrix
« Reply #1 on: Jan 4^{th}, 2007, 8:44pm » 
Quote Modify

Ah, the Amityville matrix. Let pray for a norm rank reducing technique!

« Last Edit: Jan 4^{th}, 2007, 8:46pm by Michael Dagg » 
IP Logged 
Regards, Michael Dagg



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Devil Matrix
« Reply #2 on: Jan 5^{th}, 2007, 4:51pm » 
Quote 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:
Posts: 4489


Re: Devil Matrix
« Reply #3 on: Jan 5^{th}, 2007, 4:55pm » 
Quote Modify

on Jan 5^{th}, 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. I think a rank rank reducing technique would also do.


IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Devil Matrix
« Reply #4 on: Jan 5^{th}, 2007, 5:30pm » 
Quote 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 5^{th}, 2007, 5:32pm by Michael Dagg » 
IP Logged 
Regards, Michael Dagg



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Devil Matrix
« Reply #5 on: Jan 6^{th}, 2007, 10:46am » 
Quote Modify

You found me out, Michael! Since the guys here are as wise as saints, I messwithtopofthese!


IP Logged 



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Devil Matrix
« Reply #6 on: Jan 6^{th}, 2007, 1:53pm » 
Quote Modify

Hmm. Sure?


IP Logged 
Regards, Michael Dagg



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Devil Matrix
« Reply #7 on: Jan 7^{th}, 2007, 5:35am » 
Quote Modify

on Jan 5^{th}, 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)? 



IP Logged 



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Devil Matrix
« Reply #8 on: Jan 7^{th}, 2007, 8:58pm » 
Quote Modify



IP Logged 
Regards, Michael Dagg



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


Re: Devil Matrix
« Reply #9 on: Jan 9^{th}, 2007, 9:34pm » 
Quote Modify

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:
Posts: 1948


Re: Devil Matrix
« Reply #10 on: Jan 9^{th}, 2007, 11:54pm » 
Quote Modify

Well, I have the case that A is circulant at least. Suppose A is circulant, i.e., a_{i,j} = c_{ji}, where ji is computed mod n=667. Let z denote a primitive nth root of unity, and let v_{k} be the vector (1, z^{k}, z^{2k}, ..., z^{(n1)k}). Then the ith entry of Av_{k} is [sum]_{j} a_{i,j} (v_{k})_{j} = [sum]_{j} c_{ji} z^{jk} = [sum]_{j'} c_{j'} z^{(j'+i)k} = z^{ik} [sum] c_{j}z^{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 nonzero. Since 370 of the c_{j} are 4, and 296 are 5 (and c_{0}=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^{n1})  4  9g(x) = 4(x^{n}1)/(x1)  4  9g(x), where g is a sum of 296 distinct powers of x. So if x=z^{k} is a nth 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.


IP Logged 



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


Re: Devil Matrix
« Reply #11 on: Jan 13^{th}, 2007, 6:10am » 
Quote Modify

Remembering a similar problem: Suppose Av = 0, and that v has integer entries. For each i, considering the ith 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_{1}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.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Devil Matrix
« Reply #12 on: Jan 13^{th}, 2007, 9:25am » 
Quote Modify

Eigenray, I am not sure I understand your argument. Could you elaborate, please?


IP Logged 



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


Re: Devil Matrix
« Reply #13 on: Jan 13^{th}, 2007, 10:03pm » 
Quote 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 ranknullity 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:
Posts: 1321


Re: Devil Matrix
« Reply #14 on: Jan 14^{th}, 2007, 11:10am » 
Quote 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:
Posts: 1948


Re: Devil Matrix
« Reply #15 on: Jan 14^{th}, 2007, 3:51pm » 
Quote 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:
Posts: 405


Re: Devil Matrix
« Reply #16 on: Jan 14^{th}, 2007, 5:05pm » 
Quote 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 D_{3} is well known (among combinatorialists). It's eigenvalues (mod 3) are, one 0, and 666 2's. Hence its rank is 666 over F_{3}.


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Devil Matrix
« Reply #17 on: Jan 14^{th}, 2007, 8:23pm » 
Quote 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 offdiagonal entries are all equal the number b. All row sums of C equal a+(n1)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+(n1)b. Now consider the n1 vectors v_{i}, which have a 1 in the first position, a 1 in the ith position, and zeros elsewhere, for i=2,...,n. Then v_{i} is easily seen as an eigenvector of C with eigenvalue ab. That's n linearly independent eigenvectors for C.


IP Logged 



