Eigenvalues and eigenvectors prominently appear in many statistical and other computational fields that require transformations of linear systems or are interested in the evolution of systems from an initial point. Some examples of the applications of eigenvalues and eigenvectors include Google’s PageRank algorithm, image compression, compounding interest, Markov Chains, and statistical methods such as Principal Component Analysis and Spectral Clustering. Even Special Relativity’s second postulate of the invariance of light can be restated as “Light is an eigenvector of the Lorentz transform” (Naslund, n.d.). More examples of real-world applications of eigenvectors and eigenvalues can be found in the references at the end of this post.
This post will explore the background of eigenvalues and eigenvectors and demonstrate their computation with a \(3 \times 3\) matrix. When the matrix is \(2 \times 2\) or \(3 \times 3\), the determinant of the matrix can be employed to find the eigenvalues and eigenvectors, but for large matrices, other approaches are required. The matrix \(A\) utilized in the examples below was taken from Problem 2.19 in the book Methods of Multivariate Analysis by Alvin Rencher.
An eigenvalue is denoted by lambda, \(\lambda\), and is defined as a scalar that when multiplied by a non-zero vector \(x\) satisfies the following:
\[ Ax = \lambda x \]
The above equation can be written differently to express the desire to find \(\lambda\) and \(x\).
\[ (A - \lambda I)x = 0 \]
To find the solutions that don’t end up as \(x = 0\), the matrix \((A - \lambda I)\) is set to \(\left|A - \lambda I \right| = 0\), which is called the characteristic equation.
For example, consider the following matrix \(A\).
\[A = \begin{bmatrix} 1 & 1 & -2 \\ -1 & 2 & 1 \\ 0 & 1 & -1 \end{bmatrix}\]
The lambda identity matrix \(\lambda I\) is thus:
\[\lambda I = \begin{bmatrix} \lambda & 0 & 0 \\ 0 & \lambda & 0 \\ 0 & 0 & \lambda \end{bmatrix}\]
Therefore the characteristic equation is written as:
\[\left|A - \lambda I \right| = det \begin{bmatrix} 1 - \lambda & 1 & -2 \\ -1 & 2 - \lambda & 1 \\ 0 & 1 & -1 - \lambda \end{bmatrix} = 0\]
For an \(n \times n\) matrix, there will be \(n\) roots and thus \(n\) eigenvalues.
The method of finding the eigenvalues of an \(n \times n\) matrix can be summarized into two steps. First, find the determinant of the left-hand side of the characteristic equation \(A - \lambda I\). After the determinant is computed, find the roots (eigenvalues) of the resultant polynomial.
The determinant in this example is given above. The determinant can be computed using Laplace expansion along the matrix’s first row.
\[\left|A \right| = (1 - \lambda) \cdot \left| \begin{array}{cc} 2 - \lambda & 1 \\ 1 & -1 - \lambda \end{array} \right| - 1 \cdot \left| \begin{array}{cc} -1 & 1 \\ 0 & - 1 - \lambda \end{array} \right| + (-2) \cdot \left| \begin{array}{cc} -1 & 2 - \lambda \\ 0 & 1 \end{array} \right| \]
\[ = (1 - \lambda)\left[(2-\lambda)(1-\lambda)-(1)(1)\right] - 1 \left[ (-1)(-1-\lambda)-(1)(0)\right] + (-2)\left[(-1)(1) - (2-\lambda)(0)\right]\]
\[ = \lambda^3 - 2\lambda^2 - \lambda + 2 \]
The equation is then factored to find the eigenvalues. We can use \((\lambda - 1)\) to factor the equation.
\[ (\lambda - 1)(\lambda^2 - 2\lambda - + \lambda - 2) \] \[ = (\lambda - 1)(\lambda - 2)(\lambda + 1) \]
Thus the eigenvalues of the matrix \(A\) are 2, 1, and -1.
We can confirm this result in R using the eigen() function.
A <- as.matrix(data.frame(c(1,-1,0),c(1,2,1),c(-2,1,-1)))
A## c.1...1..0. c.1..2..1. c..2..1...1.
## [1,] 1 1 -2
## [2,] -1 2 1
## [3,] 0 1 -1The eigen() function computes the eigenvalues and eigenvectors simultaneously. Therefore it’s typically best to save the results in a variable and access the appropriate vector.
e <- eigen(A)
e$values## [1] 2 1 -1The eigenvectors can now be computed for the associated eigenvalues. Consider the characteristic function when \(\lambda = 2\)
\[\left|A - \lambda I \right| = det \begin{bmatrix} 1 - (2) & 1 & -2 \\ -1 & 2 - (2) & 1 \\ 0 & 1 & -1 - (2) \end{bmatrix} = 0\]
The system can be reduced using Gaussian Elimination to find the eigenvectors.
The first step in the row reduction is to subtract row 1 from row 2.
\[\begin{bmatrix} -1 & 1 & -2 \\ 0 & -1 & 3 \\ 0 & 1 & -3 \end{bmatrix}\]
Then add row 2 to row 3.
\[\begin{bmatrix} -1 & 1 & -2 \\ 0 & -1 & 3 \\ 0 & 0 & 0 \end{bmatrix}\]
Row 2 can then be multiplied by \(-1\).
\[\begin{bmatrix} -1 & 1 & -2 \\ 0 & 1 & -3 \\ 0 & 0 & 0 \end{bmatrix}\]
Lastly, row 2 is subtracted from row 1, and the resultant is multiplied by \(-1\).
\[\begin{bmatrix} 1 & 0 & -1 \\ 0 & 1 & -3 \\ 0 & 0 & 0 \end{bmatrix}\]
With the matrix reduced, we can find the associated eigenvectors for \(\lambda = 2\) by solving the system.
\[ \lambda - \lambda_3 = 0 \] \[ \lambda_2 - 3\lambda_3 = 0 \] \[ \lambda_3 \]
Thus the eigenvector associated with \(\lambda = 2\) is:
\[\begin{bmatrix} \lambda \\ 3\lambda \\ \lambda \end{bmatrix} = \begin{bmatrix} 2 \\ 6 \\ 2 \end{bmatrix}\]
The eigenvectors are typically normalized by dividing by its length \(\sqrt{a'a}\).
\[ c = \frac{\begin{bmatrix} 2 \\ 6 \\ 2 \end{bmatrix}}{\sqrt{\begin{bmatrix} 2 & 6 & 2 \end{bmatrix}\begin{bmatrix} 2 \\ 6 \\ 2 \end{bmatrix}}} \]
\[ c = \begin{bmatrix} .3015 \\ .9045 \\ .3015 \end{bmatrix} \]
This result can be confirmed with R by accessing the variable e we stored earlier.
e$vectors## [,1] [,2] [,3]
## [1,] 0.3015113 -0.8017837 7.071068e-01
## [2,] 0.9045340 -0.5345225 -1.922963e-16
## [3,] 0.3015113 -0.2672612 7.071068e-01The first column corresponds to \(\lambda = 2\) and matches our result.
It was shown earlier that an eigenvalue is a scalar that when multiplied by a non-zero vector equals the following:
\[ Ax = \lambda x \]
We can show this holds with our computed eigenvalue of \(\lambda = 2\) and associated eigenvector.
a <- c(2,6,2)
x <- a / sqrt(crossprod(a)) # normalized vector
round(A %*% x, 5) == round(2 * x, 5)## [,1]
## [1,] TRUE
## [2,] TRUE
## [3,] TRUEAs mentioned at the beginning of the post, eigenvalues and eigenvectors frequently appear in a variety of methods and situations that deal with the evolution of systems and those involving differential equations. Eigenvalues and eigenvectors are also prominent in methods such as principal component analysis, factor analysis, and cluster analysis. Refer to this post for an excellent visual explanation of eigenvalues and eigenvectors.
Eigenvalues and eigenvectors. (2016, September 20). In Wikipedia, The Free Encyclopedia. From https://en.wikipedia.org/w/index.php?title=Eigenvalues_and_eigenvectors&oldid=740362145
Naslund, E. Special_Relativity_Using_Linear_Algebra.Pdf. Retrieved from https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxuYXNsdW5kZXJpY3xneDo2ZTAyNzA4NTZmOGZmNmU4
PageRank. (2016, September 26). In Wikipedia, The Free Encyclopedia. From https://en.wikipedia.org/w/index.php?title=PageRank&oldid=741332093
Powell, V., & Lehe, L. Eigenvectors and Eigenvalues explained visually. Retrieved from http://setosa.io/ev/eigenvectors-and-eigenvalues/
Rencher, A. (2002). Methods of Multivariate Analysis (Second Edition ed.)