Wednesday, February 6, 2013

Some Math Trickery

Now when I use the word trickery in this post's title, I am not talking about any sort of drama (as those of you who have seen my Downton Abbey graph may be thinking). Sorry to disappoint but there will be no lies, betrayals, jealousies or schemings. No, my math trickery is much more peaceful and magical thank that. I have rolled up my math magician sleeves and have created a neat little mathematical proof with my trusty wand (i.e. my pencil). Below is a proof that I wrote recently for a matrix theory class that I am currently taking. I am pleased with it because it rather gracefully avoids some of the gory details that can crop up in problems like these that involve identifying eigenvalues.

Here is the problem: For the general n by n matrix consisting of all 1's (call it J), show that the only eigenvalues of J are 0 and n. 

Proof: 
One way to go about this proof is by performing row reductions and linearly combining the columns (these operations won't alter the determinant for finding eigenvalues). However, rather than go through all of that calculation business which trips me up sometimes, I'll do more of a direct proof. 

Suppose that x is the n by 1 eigenvector corresponding to an eigenvalue of J. Finding an eigenvalue corresponds to solving the system (tI - J)x = 0 where t is the eigenvalue and 0 is the zero vector. The matrix tI - J has (t-1) in the main diagonal and -1's everywhere else. If we multiply this out by x = [x1, x2,...,xn] we get the following system of equations: 

(t-1)x1 - (x2 + x3 + .... + xn) = 0 
(t-1)x2 - (x1 + x3 + ... + xn) = 0 
.


(t-1)xn - (x1 + x2 + ... + x(n-1)) = 0  

From the n equations above we can express the sum x1 through xn in the following form: 

(*) x1 + x2 + .... + xn = (t-1)xi + xi = t*xi for all i = 1,...,n 

Now let's add up all of the n equations shown above before *. This gives us: 
(t-1)(x1 + x2 + ... + xn) - (n-1)(x1 + x2 + ... + xn) = 0 

This simplifies to: 
(t-n)(x1 + x2 + ... + xn) = 0 

Substituting in (*) we then get: 
(t-n)*t*xi = 0 which is true for all i 

Now clearly t = n and 0 are eigenvalues. To show that these are the only eigenvalues of the all 1's matrix, assume that there is an eigenvalue t of J not equal to n or 0. Dividing by (t-n) and t we then get that xi = 0 for all i. That is a contradiction though because x is an eigenvector and eigenvectors are assumed to be nonzero. Therefore the only eigenvalues of an n by n all 1's matrix are n and zero.
 
I like this proof because it is clean and gives the result through a little bit equation manipulation. An advantage of following the messier row reduction method (not shown here) though is being able to see the multiplicities of the eigenvalues as well as the general form of the corresponding eigenvectors. Clearly, both proof approaches have their merits.

Fin :-)