# Question about proof in particular text on linear algebra ...

Printable View

• Jan 31st 2013, 04:57 AM
mrproper
Question about proof in particular text on linear algebra ...
Greetings again,

I am wondering about the proof of a theorem. I suspect that the proof, as described in the textbook I'm reading (see the comments below for detailed description) is either imprecise (maybe intentionally - this is an introductory level book) or, what is infinitely more probable, my understanding of diagonalizable matrices, eigenvectors and eigenspaces has some flaws. The theorem concerns a method for approximating dominant eigenvalue. In the textbook it is called "power method" and It seems to me that the same thing is described in Wikipedia as "power iteration algorithm" or Von Mises Iteration.

Theorem: Let A be a $\displaystyle n\times n$ diagonalizable matrix with dominant eigenvalue $\displaystyle \lambda_{1}$. Then there exists a nonzero vector $\displaystyle x_{0}$ such, that the sequence of vectors $\displaystyle x_{k}$ defined by $\displaystyle x_{1}=Ax_{0}, x_{2}=Ax_{1},x_{3}=Ax_{2}, ... ,x_{k}=Ax_{k-1}, ...$ approaches a dominant eigenvector of A.

Proof: We may assume that the eigenvalues of A have been labeled so that:
$\displaystyle |\lambda_{1}| > |\lambda_{2}| \geq |\lambda_{3}| \geq ...\geq |\lambda_{n}|$

Let $\displaystyle v_{1}, v_{2}, v_{3}, ... , v_{n}$ be the corresponding eigenvectors. Since $\displaystyle v_{1}, v_{2}, v_{3}, ... , v_{n}$ are linearly independent, they form a basis for $\displaystyle \mathbb{R}^{n}$. Consequently we can write $\displaystyle x_{0}$ as linear combination of these eigenvectors. Say:
$\displaystyle x_{0}=c_{1}v_{1}+c_{2}v_{2}+ ... + c_{n}v_{n}$

We use that $\displaystyle x_{k}=A^{k}x_0$ and substitute the above equation into it to get:
$\displaystyle x_{k}=A^{k}x_0=c_{1} \lambda_{1}^{k}v_{1}+c_{2} \lambda_{2}^{k}v_{2}+ ... + c_{n} \lambda_{n}^k v_{n}$

We next factor out $\displaystyle \lambda_{1}^k$ to get

$\displaystyle x_{k} = \lambda_{1}^{k} ( c_{1}v_{1} + c_{2} (\frac{\lambda_{2}}{\lambda_{1}})^{k} + ... + c_{n} (\frac{\lambda_{n}}{\lambda_{1}})^{k} )$
Doing so we use the fact that $\displaystyle \lambda_{1}$ is not equal to zero.

So far so good. But I cannot get why the dominant eigenvalue cannot be zero. It is obvious that If there are more than one distinct eigenvalues, for $\displaystyle \lambda_{1}$ to be dominant, its absolute value must be greater than the absolute value of every other eigenvalue. So it cannot be zero. But what if the only eigenvalue is 0? It certainly is not wrong to have eigenvalue equals zero and it's certainly not wrong diagonalizable matrix to have less than n distinct eigenvalues. It seems to me at first look, that only a zero matrix can have zero as only eigenvalue (and will have $\displaystyle \mathbb{R}^n$ as eigenspace). But If we substitute zero matrix for A, things certainly won't behave as in the theorem? [0][0]...[0]x will converge to the zero vector which is not eigenvector at all.

Uhhh. Help???

The book in question is - David Poole's Linear Algebra (Second Edition). (Great book so far as a layman as me can say). This is theorem 4.28 on page 309.
• Jan 31st 2013, 06:23 AM
Deveno
Re: Question about proof in particular text on linear algebra ...
yes a matrix can have 0 as an eigenvalue. if, however, 0 is the DOMINANT eigenvalue, this means that 0 is the ONLY eigenvalue. since A is assumed diagonalizable, this means there is an invertible matrix P for which:

A = P0P-1 = 0.

if A = 0, then EVERY vector is a dominant eigenvector, so we get one on the first iteration (pick any non-zero x0. whoa! a dominant eigenvector!). this is a trivial case, and can be disregarded. so we can assume that A has a non-zero eigenvector.

there do exist non-zero matrices with only 0 eigenvalues, but these matrices are not diagonalizable (such matrices are called nilpotent). here is an example: A =

[0 1]
[0 0].

let me try to give you an idea of what something like theorem could be used for. imagine you have an incoming sound-signal, composing of various component wave-forms. you have a signal processor, which acts as a linear operator. an eigenvector in this case, is a wave-shape which is amplified with minimal distortion (theoretically 0). therefore if you arrange that the sound signal input is matched to the eigenvectors of the processor, you will get a clean sound, but with perhaps say the treble boosted. technology related to this is actually used in noise filters, to sort out signals that carry useful information from "scattered" (non-eigenvector input) wave-forms.

similar technology is used to make cars quieter on the road (inside the cabin), or test a steel beam for imperfections (the beam is struck by a hammer, and the eigenvalues are "heard". an experienced steel worker knows what good eigenvalues sound like-they listen for the dominant eigenvalue, which should have a clear, crisp bell-like tone).

determining the largest (dominant) eigenvalue is key to the speed and efficiency of search engines like google. when that low-rider car with the blow-out speakers drives by and shakes the street...yes, you can blame eignevectors. systems of differential equations often have linear models....and what matters in these models is the size of the eigenvalues. even if these systems are "chaotic" at dominant eigenvalues they often display coherent and predictable behavior.

often, some underlying symmetry in the modelling of a situation justifies the assumption the the matrix we assign to it is diagonalizable. diagonalization is GOOD, because diagonal matrices are much easier to compute with than arbitrary ones (fewer computations). if we already know a matrix is diagonalizable, but haven't actually diagonalized it (computing the inverse of an nxn matrix is not a user-friendly task, for n > 6, let's say), computing the eigenvectors numerically is sometimes useful (especially if you just want "the dominant eigenspace"). remember the matrices you will do problems with in your text are "toy matrices" like 2x2 or 3x3, for the most part. in the "real world" matrices can have 100's or thousands of rows/columns.
• Jan 31st 2013, 09:39 AM
mrproper
Re: Question about proof in particular text on linear algebra ...
Deveno, thanks for being as always, clear, punctual and thorough!

Not being engineer or physicist I don't know much about sound waves, but applications to Google PageRank are surely a killer and of great interest to me. Besides Markov Chains look very interesting and are from some time on my ultimate reading list...