Many matrix calculations are easy when the matrix is diagonal and hard when it is not. Eigen decomposition rewrites a square matrix around a diagonal matrix of its eigenvalues. So a hard problem on the matrix becomes an easy problem on a few numbers. If eigenvalues and eigenvectors are new to you, see the Eigenvector and Eigenvalue page first.
Eigen Decomposition is a method of splitting a matrix into multiplication of following three matrix.
- What does each matrix in the decomposition mean ?
- How does Eigen Decomposition make a matrix power easy ?
What does each matrix in the decomposition mean ?
What does each of the matrix mean ? Each of the matrix in the equation indicates as shown below. Now you would know why this is called Eigen Decomposition.
Let's read the picture column by column. Q holds the eigenvectors v1, v2 and v3 of A as its columns. Λ holds the matching eigenvalues λ1, λ2 and λ3 on its diagonal, in the same order. The last factor is the inverse of Q. It is built from the same eigenvectors, but it is not the eigenvector matrix itself.
The decomposition is only a compact way to write the eigenvalue equation. Avi = λivi for every column gives AQ = QΛ. Multiply both sides by Q-1 on the right, and you get A = QΛQ-1. This step needs Q-1 to exist, so A must have n linearly independent eigenvectors. Such a matrix is called diagonalizable.
Let's check it with a 2 x 2 example. A = [4 1; 2 3] has the eigenvalues 2 and 5, with the eigenvectors [1 -2]T and [1 1]T. So Q = [1 1; -2 1], Λ = diag(2, 5) and Q-1 = [1 -1; 2 1]/3. Multiplying the three matrices gives back [4 1; 2 3].
Not every matrix has this form. A = [1 1; 0 1] has the eigenvalue 1 twice but only one independent eigenvector, [1 0]T. Its Q would be singular, so it has no eigen decomposition. A real symmetric matrix is the opposite case. It always has one, and its eigenvectors can be chosen orthonormal, so Q-1 = QT.
The columns of Q are the eigenvectors : and the diagonal of Λ holds the eigenvalues in the same order.A = QΛQ-1 is AQ = QΛ rearranged : it says nothing more than Avi = λivi for every column.The decomposition needs n independent eigenvectors : a matrix such as [1 1; 0 1] does not have them and cannot be decomposed this way.Symmetric matrices are the easy case : Q can be orthogonal, so its inverse is just its transpose.
How does Eigen Decomposition make a matrix power easy ?
One of the most common application of this decomposition is as follows. You can express a power of matrix as shown below (I wouldn't show you how to prove this. I think you can easily prove this or just use it). In this form, you don't have to do power operation for Q, you only have to power the diagonal matrix which is made up of eigen value. Powering the diagonal matrix is just like powering scalers.
The proof is short. A2 = QΛQ-1QΛQ-1, and the Q-1Q in the middle is the identity matrix. So A2 = QΛ2Q-1, and every further power adds one more Λ in the same way. Λn is again diagonal, with λin on its diagonal.
Let's use the 2 x 2 example above. For A = [4 1; 2 3], Λ10 = diag(210, 510) = diag(1024, 9765625). Then QΛ10Q-1 gives A10 = [6510758 3254867; 6509734 3255891]. This takes two scalar powers and two matrix products, instead of nine matrix products by repeated multiplication.
The same idea extends to any function that is built from powers. The matrix exponential is eAt = QeΛtQ-1, where eΛt is diagonal with eλit on its diagonal. This is the solution of the linear differential equation dx/dt = Ax, so the eigenvalues tell you directly whether the solution grows or decays. Linear recurrences work the same way. The Fibonacci numbers come from powers of [1 1; 1 0], whose eigenvalues are (1 + √5)/2 and (1 - √5)/2.
A power of A is a power of its eigenvalues : An = QΛnQ-1, and Λn needs only scalar powers.The largest eigenvalue dominates : for large n, the term with the largest |λi| decides how fast An grows.The same trick gives eAt : so eigen decomposition solves linear differential equations and linear recurrences.