Matrix Theory: Diagonalisation and Eigenvector Computation

I return to the first example about basis vectors, when I spoke of linear transformations. The linear transformation we had was this:

  A=  \left( \begin{array}{cc}  2 & 0 \\  0 & 5 \end{array} \right)\

The operation it performed on basis vectors of the standard basis S was one of scaling, and scaling only. When operated on by a linear transformation matrix, if a vector is only scaled as a consequence, that vector is an eigenvector of the matrix, and the scalar is the corresponding eigenvalue. This is just the definition of an eigenvector, which I rewrite below:

A.x = \lambda x

You will have also noticed that the matrix A is a diagonal matrix. It is particularly easy to find the eigenvectors of a matrix if it is diagonal in a basis, because the eigenvectors are always the basis vectors themselves, as expressed in that basis. That last phrase is particularly important. Basis vectors as expressed in that basis always look like this:
  {\left( \begin{array}{ccc}  1 & 0 & 0 \ldots 0\end{array} \right)}^T \\  {\left( \begin{array}{ccc}  0 & 1 & 0 \ldots 0\end{array} \right)}^T \\  {\left( \begin{array}{ccc}  0 & 0 & 1 \ldots 0\end{array} \right)}^T \\  \vdots\\  {\left( \begin{array}{ccc}  0 & 0 & 0 \ldots 1\end{array} \right)}^T

It’s now easy to see how our previous statement is true, because any of the above vectors when multipled by a diagonal vector gives the same vector, only scaled by a certain scalar.

Life would be great if we always got to work with diagonal matrices. Unfortunately, that is not the case. Though small-dimensional matrices (2,3,4) yield themselves to algebraic solutions for their eigenvectors/eigenvalues, much of the data we will work are easily higher-dimensional than that.
So, what can we do? Examine the diagram below:

The situation is this, we have a matrix AS in standard basis. We wish to find the eigenvectors and eigenvalues of this matrix. Now here comes the trick: AS is not diagonal in basis, but there is probably another basis out there somewhere in which it *is* diagonal. Let’s assume that this hypothetical basis is B. Now, it follows from our previous discussion that if a matrix is diagonal in a basis, the basis vectors (as expressed in that basis) are the eigenvectors of that matrix.
Thus, the basis vectors of B are the eigenvectors of our matrix AB (which is our original AS expressed in basis B).

Now all we have done is change the basis, which means that the basis vectors of B that we found are going to be eigenvectors of A no matter what the basis, as long as both the vectors and the transformation matrix A are expressed in the same basis.
Thus, the basis matrix of B (in standard basis) is the eigenvector matrix of AS.

The basic idea underlying all eigenvector computation methods is then, this: find a set of bases in which the matrix A is diagonal, this set of bases, expressed in the standard basis, is the set of eigenvectors of A. Thus our objective will be to find a similarity transformation on A which will make A diagonal.

This concludes the basic matrix theory you’ll need to understand the eigenvector algorithms for symmetric matrices. From here on, I’ll dive into the specific eigenvector/eigenvalue numerical methods.