wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Common Eigenvector Condition
        
(Message started by: william wu on Dec 12^th, 2007, 4:08pm)

Title: Common Eigenvector Condition
Post by william wu on Dec 12^th, 2007, 4:08pm

Let A and B be square matrices. Prove the following:

if Rank(A·B – B·A) <= 1,
then A and B have at least one eigenvector in common.

Source: W. Kahan

Title: Re: Common Eigenvector Condition
Post by ecoist on Dec 15^th, 2007, 7:06pm

Please pardon this aside, Wu (little progress so far on this interesting problem). A novel I am reading says that "wu" is "five" in Mandarin, and that the chinese character represents the five elements of herbal medecine, metal, wood, water, fire, and earth. Is this true?

Title: Re: Common Eigenvector Condition
Post by Aryabhatta on Dec 17^th, 2007, 5:49pm

Here is a partial try at the problem: special case when AB = BA.

[hide]
Say l is an eigenvalue of A and x is a correponding eigenvector.

Then we have that

A(Bx) = B(Ax) = l(Bx)

Thus Bx is also an eigenvector of A.

Consider the eigenspace E(l,A) corresponding to A and l.

We can show that E(l,A) is invariant under B.

I think we can show that a finite dimensional space which is invariant under a linear transform must contain an eigenvector of that transform.

Since E(l,A) is invariant under B, it must contain an eigenvector of B... hence A and B have a common eigenvector.

[/hide]

Title: Re: Common Eigenvector Condition
Post by ecoist on Dec 17^th, 2007, 7:17pm

The case AB=BA is in a textbook, Aryabhatta, along with your proof (can't recall a reference). As for the part of your proof that you left out, [hide]let W be a subspace invariant under a linear transformation T and let w=/=0 be in W. Consider the polynomial p(x) of least degree such that p(T)w=0.[/hide] (I used your trick for my posted problem concerning two rational matrices that commute. Didn't know then that there was a more elementary solution)

Title: Re: Common Eigenvector Condition
Post by Aryabhatta on Dec 17^th, 2007, 7:56pm

on 12/17/07 at 19:17:33, ecoist wrote:

I used your trick for my posted problem concerning two rational matrices that commute.

Which problem is that? I must have missed it. Can you please post a link?

Title: Re: Common Eigenvector Condition
Post by ecoist on Dec 17^th, 2007, 8:26pm

My damn updated IE won't let me copy urls! The problem is on page 6 of putnam exam entitled "Can these rational matrices commute?"

Title: Re: Common Eigenvector Condition
Post by ecoist on Dec 30^th, 2007, 9:18pm

It is obvious that, if A and B have a common eigenvector, then that vector must lie in the null space of AB-BA. But, so far, I can't even prove that A has any eigenvector in the null space of AB-BA! A could have only one eigenvector (modulo scalar multiiples)! Also, I don't yet see the significance of AB-BA having rank <1. This fact implies that the minimum polynomial of AB-BA is x or x², but it doesn't seem to help. I even wondered if there are any matrices A and B at all such that AB-BA has rank 1. I stumbled on such a pair.

A=|0 0|, B=|1 1|. |1 -1|, |1 1|

This A and B have the common eigenvector (1,1).

Title: Re: Common Eigenvector Condition
Post by Eigenray on Jan 7^th, 2008, 9:52pm

on 12/30/07 at 21:18:03, ecoist wrote:

But, so far, I can't even prove that A has any eigenvector in the null space of AB-BA!

I can at least show this much: suppose C = AB-BA has rank 1. Adding a scalar multiple of I to A doesn't change anything, so we can assume A is invertible.

For any k, CA^k has rank http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 1, and trace 0, so CA^kCA^k=0, and therefore CA^kC=0. So the image of span<A^kC> is a non-zero A-invariant subspace of K = ker C. So A has some eigenspace E intersecting K non-trivially.

Now B(E http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cap.gif K) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subseteq.gif E, so if E http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subseteq.gif K (for example, if dim E =1), then we're done. But otherwise I don't know what to do.

I don't think we can use the same trick to show CMC=0 for any monomial M in A,B, because tr(CM) may not be 0...

Title: Re: Common Eigenvector Condition
Post by Eigenray on Mar 20^th, 2008, 5:05pm

We have two obvious A-invariant subspaces, Ker(A) and Im(A). But at least one of them must also be B-invariant:

Suppose Ker(A) is not B-invariant. Pick x with Ax=0, ABx http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0. Then Cx = ABx - BAx = ABx http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0, and since C has rank 1, it follows Im(C) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subseteq.gif Im(A). But BA = AB - C, so Im(BA) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subseteq.gif Im(A), i.e., Im(A) is B-invariant.

Now, if A is a scalar multiple of I, it is obvious. Otherwise, we can add a scalar multiple of I to A so that both Ker(A) and Im(A) are non-zero, so at least one of them is invariant under both A and B. Passing to this subspace, we induct until the dimension is 1, where the problem is trivial.

Title: Re: Common Eigenvector Condition
Post by william wu on May 19^th, 2008, 1:08pm

on 12/15/07 at 19:06:03, ecoist wrote:

Digressing, here's a late reply to this:

- Regarding the interpretation of "five" that you mentioned, I've seen that in some references. The original character was an hourglass, and later it morphed into the modern-day character. "The two principles yin and yang, begetting the five elements, between heaven and earth." - Wieger. However, there isn't always agreement on the interpretations; Karlgren calls it "far-fetched". It's difficult to know what the original derivation was.
- Not sure if you were wondering whether my last name means "five", but in case you did, here are some interesting facts about Chinese:

- Chinese is ridden with homonyms. The romanization "wu" has over 100 different characters corresponding to it.
- Furthermore, Chinese is a tonal language. In Mandarin, there are four tones: so to trim down the possibilities, we can write wu1, wu2, wu3, and wu4, all corresponding to different intonations of the same phonetic sound. However, the ratio of 4:114 is still pretty low. So we have to rely on context to make sense of things -- isolated words with no context make no sense.
- Given the odds, its not surprising that my last name's (wu2) is totally different from the (wu3) that means five.