wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Eigenvalues 
        
(Message started by: THUDandBLUNDER on Dec 5^th, 2006, 6:10pm)

Title: Eigenvalues
Post by THUDandBLUNDER on Dec 5^th, 2006, 6:10pm

Given a 2n x 2n matrix whose entries are all odd integers, show that its eigenvalues cannot be odd integers.

Title: Re: Eigenvalues
Post by Sameer on Dec 5^th, 2006, 9:58pm

Consider matrix


A = a1,1  a1,2    ... a1,2n
         a2,1  a2,2    ... a2,2n
         ...
         a2n,1  a2n,2  ... a2n,2n

Then eigenvector can be defines as L such that

AX=LX

So (a1,1+a2,1+...a2n,1) = L1
(a1,2+a2,2+...a2n,2) = L2
...
(a1,2n+a2,2n+....+a2n,2n) = L2n

Since all the elements are odd summation of 2n odd numbers is also even. Thus all L1,L2...L2n is even.

Title: Re: Eigenvalues
Post by towr on Dec 6^th, 2006, 1:21am

If I had to hazard a guess
I'd say A² has all even integers, so it's eigenvalues are all even, and they're the squares of the eigenvalues of A, which can thus not be odd.
On the other hand, that's assumming the eigenvectors aren't all even. But then, if they were you could divide them by the highest common factor of two. So errr, I'm left to hope there isn't a (reduced) eigenvector with an even number of odd numbers..

Title: Re: Eigenvalues
Post by Eigenray on Dec 6^th, 2006, 6:11am

on 12/06/06 at 01:21:05, towr wrote:

So errr, I'm left to hope there isn't a (reduced) eigenvector with an even number of odd numbers..

The number of odd numbers can be even all it wants, it just can't be 0.

My solution: Suppose A has an odd integer eigenvalue L. Then Ax=Lx for some rational vector x; multiplying by an integer, and dividing by a power of 2 if necessary, we may assume x is integral, with at least one odd coordinate. Now, Ax=Lx means that, mod 2,

x_i = Lx_i = [sum] a_ijx_j = [sum] x_j

for all i. Since the RHS is independent of i, all the x_i must be odd. But then [sum] x_j is even, a contradiction.

(On the other hand, an odd array of odd size can have odd eigenvalues, but they can't all be odd integers, since the determinant is even, except in the 1x1 case.)

Title: Re: Eigenvalues
Post by towr on Dec 6^th, 2006, 6:30am

on 12/06/06 at 06:11:51, Eigenray wrote:

The number of odd numbers can be even all it wants, it just can't be 0.

Sometimes I look back at something I wrote, and wonder what I was thinking..

Title: Re: Eigenvalues
Post by flamingdragon on Dec 6^th, 2006, 3:35pm

LOL