Author |
Topic: Devil Matrix (Read 1150 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Devil Matrix
« on: Jan 4th, 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 4th, 2007, 8:44pm » |
Quote 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:
Posts: 500
|
|
Re: Devil Matrix
« Reply #2 on: Jan 5th, 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 5th, 2007, 4:55pm » |
Quote 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. 
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 5th, 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 5th, 2007, 5:32pm by Michael Dagg » |
IP Logged |
Regards,
Michael Dagg
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Devil Matrix
« Reply #5 on: Jan 6th, 2007, 10:46am » |
Quote 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:
Posts: 500
|
|
Re: Devil Matrix
« Reply #6 on: Jan 6th, 2007, 1:53pm » |
Quote Modify
|
Hmm. Sure?
|
|
IP Logged |
Regards,
Michael Dagg
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Devil Matrix
« Reply #7 on: Jan 7th, 2007, 5:35am » |
Quote 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)? |
|
 
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Devil Matrix
« Reply #8 on: Jan 7th, 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 9th, 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 9th, 2007, 11:54pm » |
Quote 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:
Posts: 1948
|
|
Re: Devil Matrix
« Reply #11 on: Jan 13th, 2007, 6:10am » |
Quote 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:
Posts: 2276
|
|
Re: Devil Matrix
« Reply #12 on: Jan 13th, 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 13th, 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 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:
Posts: 1321
|
|
Re: Devil Matrix
« Reply #14 on: Jan 14th, 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 14th, 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 14th, 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 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:
Posts: 405
|
|
Re: Devil Matrix
« Reply #17 on: Jan 14th, 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 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print