```

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 12th, 2007, 4:08pm)

```

Title: Common Eigenvector Condition
Post by william wu on Dec 12th, 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 15th, 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 17th, 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 17th, 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 17th, 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 17th, 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 30th, 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 x2, 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 7th, 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, CAk has rank http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 1, and trace 0, so CAkCAk=0, and therefore CAkC=0.  So the image of span<AkC> 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 20th, 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 19th, 2008, 1:08pm

on 12/15/07 at 19:06:03, ecoist wrote:
 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?

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.