Opening the book…
- Understand what a positive definite matrix is.
- Understand Cholesky Factorization.
- Understand \(QR\) Factorization.
Thus far, we have looked some important factorizations (or decompositions). In Chapter 1, we used the \(LU\) factorization to solve linear systems. In this chapter, we have used diagonalization (or orthogonal diagonalization) to decompose some square matrices and the singular value decomposition to factor non-square matrices.
In this section, we look at some other factorizations.
Positive Definite Matrices and the Cholesky Factorization
Positive definite matrices are often encountered in applications such mechanics and statistics, and as we will see these matrices can be factored in a special way.
We begin with a definition.
Let \(A\) be an \(n \times n\) symmetric matrix. Then \(A\) is positive definite if all of its eigenvalues are positive. \(A\) is negative definite if all of its eigenvalues are negative.
The relationship between a negative definite matrix and positive definite matrix is as follows.
An \(n\times n\) matrix \(A\) is negative definite if and only if \(-A\) is positive definite
Consider the following lemma.
If \(A\) is positive definite, then it is invertible.
- Proof
-
If \(A\vec{v}=\vec{0},\) then \(0\) is an eigenvalue if \(\vec{v}\) is nonzero, which does not happen for a positive definite matrix. Hence \(\vec{v}=\vec{0}\) and so \(A\) is one to one. This is sufficient to conclude that it is invertible.
Notice that this lemma implies that if a matrix \(A\) is positive definite, then \(\det(A) > 0\).
The following theorem provides another characterization of positive definite matrices. It gives a useful test for verifying if a matrix is positive definite.
Let \(A\) be a symmetric matrix. Then \(A\) is positive definite if and only if \(\vec{x}^T A \vec{x}\) is positive for all nonzero \(\vec{x} \in \mathbb{R}^n\).
- Proof
-
Since \(A\) is symmetric, there exists an orthogonal matrix \(U\) so that \[U^{T}AU=diag(\lambda_1,\lambda_2,\ldots,\lambda_n)=D,\nonumber \] where \(\lambda_1,\lambda_2,\ldots,\lambda_n\) are the (not necessarily distinct) eigenvalues of \(A\). Let \(\vec{x}\in\mathbb{R}^n\), \(\vec{x}\neq \vec{0}\), and define \(\vec{y}=U^T\vec{x}\). Then \[\vec{x}^TA\vec{x}=\vec{x}^T(UDU^T)\vec{x} = (\vec{x}^TU)D(U^T\vec{x}) =\vec{y}^TD\vec{y}.\nonumber \]
Writing \(\vec{y}^T=\left[\begin{array}{cccc} y_1 & y_2 & \cdots & y_n\end{array}\right]\), \[\begin{aligned} \vec{x}^TA\vec{x} & = \left[\begin{array}{cccc} y_1 & y_2 & \cdots & y_n\end{array}\right] diag(\lambda_1,\lambda_2,\ldots,\lambda_n) \left[\begin{array}{c} y_1 \\ y_2 \\ \vdots \\ y_n\end{array}\right]\\ & = \lambda_1 y_1^2 + \lambda_2 y_2^2 + \cdots \lambda_n y_n^2.\end{aligned}\]
\((\Rightarrow)\) First we will assume that \(A\) is positive definite and prove that \(\vec{x}^T A \vec{x}\) is positive.
Suppose \(A\) is positive definite, and \(\vec{x}\in\mathbb{R}^n\), \(\vec{x}\neq\vec{0}\). Since \(U^T\) is invertible, \(\vec{y}=U^T\vec{x}\neq \vec{0}\), and thus \(y_j\neq 0\) for some \(j\), implying \(y_j^2>0\) for some \(j\). Furthermore, since all eigenvalues of \(A\) are positive, \(\lambda_i y_i^2\geq 0\) for all \(i\) and \(\lambda_jy_j^2>0\). Therefore, \(\vec{x}^TA\vec{x}>0\).
\((\Leftarrow)\) Now we will assume \(\vec{x}^T A \vec{x}\) is positive and show that \(A\) is positive definite.
If \(\vec{x}^TA\vec{x}>0\) whenever \(\vec{x}\neq \vec{0}\), choose \(\vec{x}=U\vec{e}_j\), where \(\vec{e}_j\) is the \(j^{\mbox{th}}\) column of \(I_n\). Since \(U\) is invertible, \(\vec{x}\neq\vec{0}\), and thus \[\vec{y}=U^T\vec{x}=U^T(U\vec{e}_j) =\vec{e}_j.\nonumber \] Thus \(y_j=1\) and \(y_i=0\) when \(i\neq j\), so \[\lambda_1 y_1^2 + \lambda_2 y_2^2 + \cdots \lambda_n y_n^2 =\lambda_j,\nonumber \] i.e., \(\lambda_j=\vec{x}^TA\vec{x}>0\). Therefore, \(A\) is positive definite.
There are some other very interesting consequences which result from a matrix being positive definite. First one can note that the property of being positive definite is transferred to each of the principal submatrices which we will now define.
Let \(A\) be an \(n\times n\) matrix. Denote by \(A_{k}\) the \(k\times k\) matrix obtained by deleting the \(k+1,\cdots ,n\) columns and the \(k+1,\cdots ,n\) rows from \(A.\) Thus \(A_{n}=A\) and \(A_{k}\) is the \(k\times k\) submatrix of \(A\) which occupies the upper left corner of \(A.\)
Let \(A\) be an \(n\times n\) positive definite matrix. Then each submatrix \(A_{k}\) is also positive definite.
- Proof
-
This follows right away from the above definition. Let \(\vec{x}\in \mathbb{R}^{k}\) be nonzero. Then \[\vec{x}^{T}A_{k}\vec{x}=\left[ \begin{array}{cc} \vec{x}^{T} & 0 \end{array} \right] A\left[ \begin{array}{c} \vec{x} \\ 0 \end{array} \right] > 0\nonumber \] by the assumption that \(A\) is positive definite.
There is yet another way to recognize whether a matrix is positive definite which is described in terms of these submatrices. We state the result, the proof of which can be found in more advanced texts.
Let \(A\) be a symmetric matrix. Then \(A\) is positive definite if and only if \(\det \left( A_{k}\right)\) is greater than \(0\) for every submatrix \(A_{k}\), \(k=1,\cdots ,n\).
- Proof
-
We prove this theorem by induction on \(n.\) It is clearly true if \(n=1.\) Suppose then that it is true for \(n-1\) where \(n\geq 2\). Since \(\det \left( A\right) =\det \left( A_{n}\right) >0,\) it follows that all the eigenvalues are nonzero. We need to show that they are all positive. Suppose not. Then there is some even number of them which are negative, even because the product of all the eigenvalues is known to be positive, equaling \(\det \left( A\right)\). Pick two, \(\lambda _{1}\) and \(\lambda _{2}\) and let \(A \vec{u}_{i}=\lambda _{i}\vec{u}_{i}\) where \(\vec{u}_{i}\neq \vec{0}\) for \(i=1,2\) and \(\vec{u}_{1}\cdot \vec{u}_{2}=0.\) Now if \(\vec{y}\equiv \alpha _{1}\vec{u}_{1}+\alpha _{2}\vec{u}_{2}\) is an element of \(span\left\{ \vec{u}_{1},\vec{u}_{2}\right\} ,\) then since these are eigenvalues and \(\ \vec{u}_{1}\cdot \vec{u}_{2}=0,\) a short computation shows \[\left( \alpha _{1}\vec{u}_{1}+\alpha _{2}\vec{u}_{2}\right) ^{T}A\left( \alpha _{1}\vec{u}_{1}+\alpha _{2}\vec{u}_{2}\right)\nonumber \] \[=\left\vert \alpha _{1}\right\vert ^{2}\lambda _{1} \vec{u} _{1} ^{2}+\left\vert \alpha _{2}\right\vert ^{2}\lambda _{2}\vec{u}_{2}^{2}<0.\nonumber \] Now letting \(\vec{x}\in \mathbb{R}^{n-1},\) we can use the induction hypothesis to write \[\left[ \begin{array}{cc} x^{T} & 0 \end{array} \right] A\left[ \begin{array}{c} \vec{x} \\ 0 \end{array} \right] =\vec{x}^{T}A_{n-1}\vec{x}>0.\nonumber \] Now the dimension of \(\left\{ \vec{z}\in \mathbb{R}^{n}:z_{n}=0\right\}\) is \(n-1\) and the dimension of \(span\left\{ \vec{u}_{1},\vec{u} _{2}\right\} =2\) and so there must be some nonzero \(\vec{x}\in \mathbb{R} ^{n}\) which is in both of these subspaces of \(\mathbb{R}^{n}\). However, the first computation would require that \(\vec{x}^{T}A\vec{x}<0\) while the second would require that \(\vec{x}^{T}A\vec{x}>0.\) This contradiction shows that all the eigenvalues must be positive. This proves the if part of the theorem. The converse can also be shown to be correct, but it is the direction which was just shown which is of most interest.
Let \(A\) be symmetric. Then \(A\) is negative definite if and only if \[\left( -1\right) ^{k} \det \left( A_{k}\right) >0\nonumber \] for every \(k=1,\cdots ,n\).
- Proof
-
This is immediate from the above theorem when we notice that \(A\) is negative definite if and only if \(-A\) is positive definite. Therefore, if \(\det \left( -A_{k}\right) >0\) for all \(k=1,\cdots ,n,\) it follows that \(A\) is negative definite. However, \(\det \left( -A_{k}\right) =\left( -1\right) ^{k}\det \left( A_{k}\right) .\)
Another important theorem is the existence of a specific factorization of positive definite matrices. It is called the Cholesky Factorization and factors the matrix into the product of an upper triangular matrix and its transpose.
Let \(A\) be a positive definite matrix. Then there exists an upper triangular matrix \(U\) whose main diagonal entries are positive, such that \(A\) can be written \[A= U^TU\nonumber \] This factorization is unique.
The process for finding such a matrix \(U\) relies on simple row operations.
Let \(A\) be a positive definite matrix. The matrix \(U\) that creates the Cholesky Factorization can be found through two steps.
- Using only type \(3\) elementary row operations (multiples of rows added to other rows) put \(A\) in upper triangular form. Call this matrix \(\hat{U}\). Then \(\hat{U}\) has positive entries on the main diagonal.
- Divide each row of \(\hat{U}\) by the square root of the diagonal entry in that row. The result is the matrix \(U\).
Of course you can always verify that your factorization is correct by multiplying \(U\) and \(U^T\) to ensure the result is the original matrix \(A\).
Consider the following example.
Show that \(A=\left[\begin{array}{rrr} 9 & -6 & 3 \\ -6 & 5 & -3 \\ 3 & -3 & 6 \end{array}\right]\) is positive definite, and find the Cholesky factorization of \(A\).
Solution
First we show that \(A\) is positive definite. By Theorem \(\PageIndex{2}\) it suffices to show that the determinant of each submatrix is positive. \[A_{1}=\left[\begin{array}{c} 9 \end{array}\right] \mbox{ and } A_{2}=\left[\begin{array}{rr} 9 & -6 \\ -6 & 5 \end{array}\right],\nonumber \] so \(\det(A_{1})=9\) and \(\det(A_{2})=9\). Since \(\det(A)=36\), it follows that \(A\) is positive definite.
Now we use Procedure \(\PageIndex{1}\) to find the Cholesky Factorization. Row reduce (using only type \(3\) row operations) until an upper triangular matrix is obtained. \[\left[\begin{array}{rrr} 9 & -6 & 3 \\ -6 & 5 & -3 \\ 3 & -3 & 6 \end{array}\right] \rightarrow \left[\begin{array}{rrr} 9 & -6 & 3 \\ 0 & 1 & -1 \\ 0 & -1 & 5 \end{array}\right] \rightarrow \left[\begin{array}{rrr} 9 & -6 & 3 \\ 0 & 1 & -1 \\ 0 & 0 & 4 \end{array}\right]\nonumber \]
Now divide the entries in each row by the square root of the diagonal entry in that row, to give \[U=\left[\begin{array}{rrr} 3 & -2 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & 2 \end{array}\right]\nonumber \]
You can verify that \(U^TU = A\).
Let \(A\) be a positive definite matrix given by \[\left[ \begin{array}{ccc} 3 & 1 & 1 \\ 1 & 4 & 2 \\ 1 & 2 & 5 \end{array} \right]\nonumber \] Determine its Cholesky factorization.
Solution
You can verify that \(A\) is in fact positive definite.
To find the Cholesky factorization we first row reduce to an upper triangular matrix. \[\left[ \begin{array}{ccc} 3 & 1 & 1 \\ 1 & 4 & 2 \\ 1 & 2 & 5 \end{array} \right] \rightarrow \left[ \begin{array}{ccc} 3 & 1 & 1 \\ 0 & \frac{11}{3} & \frac{5}{3} \\ 0 & \frac{5}{3} & \frac{14}{5} \end{array} \right] \rightarrow \left[ \begin{array}{ccc} 3 & 1 & 1 \\ 0 & \frac{11}{3} & \frac{5}{3} \\ 0 & 0 & \frac{43}{11} \end{array} \right]\nonumber \]
Now divide the entries in each row by the square root of the diagonal entry in that row and simplify. \[U = \left[ \begin{array}{ccc} \sqrt{3} & \frac{1}{3}\sqrt{3} & \frac{1}{3}\sqrt{3} \\ 0 & \frac{1}{3}\sqrt{3}\sqrt{11} & \frac{5}{33}\sqrt{3}\sqrt{11} \\ 0 & 0 & \frac{1}{11}\sqrt{11}\sqrt{43} \end{array} \right]\nonumber \]
The Cholesky Factorization has many applications. One example that you're familiar with is in solving linear systems. It can be used in the same way that the \(LU\) Factorization can be used, but when the Cholesky Factorization is available to use, it is more efficient than the \(LU\) Factorization.
QR Factorization
In this section, a reliable factorization of matrices is studied. Called the \(QR\) factorization of a matrix, it always exists. While much can be said about the \(QR\) factorization, this section will be limited to real matrices. Therefore we assume the dot product used below is the usual dot product. We begin with a definition.
Let \(A\) be a real \(m\times n\) matrix. Then a \(QR\) Factorization of \(A\) consists of two matrices, \(Q\) orthogonal and \(R\) upper triangular, such that \(A=QR.\)
The following theorem claims that such a factorization exists.
Let \(A\) be any real \(m\times n\) matrix with linearly independent columns. Then there exists an orthogonal matrix \(Q\) and an upper triangular matrix \(R\) having non-negative entries on the main diagonal such that \[A=QR\nonumber\]
The procedure for obtaining the \(QR\) factorization for any matrix \(A\) is as follows.
Let \(A\) be an \(m \times n\) matrix given by \(A = \left[ \begin{array}{cccc} A_1 & A_2 & \cdots & A_n \end{array} \right]\) where the \(A_i\) are the linearly independent columns of \(A\).
- Apply the Gram-Schmidt Process 4.9.1 to the columns of \(A\), writing \(B_i\) for the resulting columns.
- Normalize the \(B_i\), to find \(C_i = \frac{1}{ B_i } B_i\).
- Construct the orthogonal matrix \(Q\) as \(Q=\left[ \begin{array}{cccc} C_1 & C_2 & \cdots & C_n \end{array} \right]\).
- Construct the upper triangular matrix \(R\) as \[R = \left[ \begin{array}{ccccc} B_1 & A_2 \cdot C_1 & A_3 \cdot C_1 & \cdots & A_n \cdot C_1 \\ 0 & B_2 & A_3 \cdot C_2 & \cdots & A_n \cdot C_2 \\ 0 & 0 & B_3 & \cdots & A_n \cdot C_3 \\ \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & 0 & \cdots & B_n \end{array} \right]\nonumber \]
- Finally, write \(A=QR\) where \(Q\) is the orthogonal matrix and \(R\) is the upper triangular matrix obtained above.
Notice that \(Q\) is an orthogonal matrix as the \(C_i\) form an orthonormal set. Since \( B_i > 0\) for all \(i\) (since the length of a vector is always positive), it follows that \(R\) is an upper triangular matrix with positive entries on the main diagonal.
Consider the following example.
Let \[A = \left[ \begin{array}{rr} 1 & 2 \\ 0 & 1 \\ 1 & 0 \end{array} \right]\nonumber \] Find an orthogonal matrix \(Q\) and upper triangular matrix \(R\) such that \(A=QR\).
Solution
First, observe that \(A_1\), \(A_2\), the columns of \(A\), are linearly independent. Therefore we can use the Gram-Schmidt Process to create a corresponding orthogonal set \(\left\{ B_1, B_2 \right\}\) as follows: \[\begin{aligned} B_1 &= A_1 = \left[ \begin{array}{r} 1 \\ 0 \\ 1 \end{array} \right] \\ B_2 &= A_2 - \frac{A_2 \cdot B_1}{ B_1 ^2} B_1 \\ &= \left[ \begin{array}{r} 2 \\ 1 \\ 0 \end{array} \right] - \frac{2}{2} \left[ \begin{array}{r} 1 \\ 0 \\ 1 \end{array} \right] \\ &= \left[ \begin{array}{r} 1 \\ 1 \\ -1 \end{array} \right]\end{aligned}\]
Normalize each vector to create the set \(\left\{ C_1, C_2 \right\}\) as follows: \[\begin{aligned} C_1 &= \frac{1}{ B_1 } B_1 = \frac{1}{\sqrt{2}} \left[ \begin{array}{r} 1 \\ 0 \\ 1 \end{array} \right] \\ C_2 &= \frac{1}{ B_2 } B_2 = \frac{1}{\sqrt{3}} \left[ \begin{array}{r} 1 \\ 1 \\ -1 \end{array}\right]\end{aligned}\]
Now construct the orthogonal matrix \(Q\) as \[\begin{aligned} Q &= \left[ \begin{array}{cccc} C_1 & C_2 & \cdots & C_n \end{array} \right] \\ &= \left[ \begin{array}{rr} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{3}} \\ 0 & \frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{2}} & - \frac{1}{\sqrt{3}} \end{array} \right]\end{aligned}\]
Finally, construct the upper triangular matrix \(R\) as \[\begin{aligned} R &= \left[ \begin{array}{cc} B_1 & A_2 \cdot C_1 \\ 0 & B_2 \end{array} \right] \\ &= \left[ \begin{array}{cc} \sqrt{2} & \sqrt{2} \\ 0 & \sqrt{3} \\ \end{array} \right]\end{aligned}\]
It is left to the reader to verify that \(A=QR\).
The QR Factorization and Eigenvalues
The \(QR\) factorization of a matrix has a very useful application. It turns out that it can be used repeatedly to estimate the eigenvalues of a matrix. Consider the following procedure.
Let \(A\) be an invertible matrix. Define the matrices \(A_1, A_2, \cdots\) as follows:
- \(A_1 = A\) factored as \(A_1 = Q_1R_1\)
- \(A_2 = R_1Q_1\) factored as \(A_2 = Q_2R_2\)
- \(A_3 = R_2Q_2\) factored as \(A_3 = Q_3R_3\)
Continue in this manner, where in general \(A_k = Q_kR_k\) and \(A_{k+1} = R_kQ_k\).
Then it follows that this sequence of \(A_i\) converges to an upper triangular matrix which is similar to \(A\). Therefore the eigenvalues of \(A\) can be approximated by the entries on the main diagonal of this upper triangular matrix.
Power Methods
While the \(QR\) algorithm can be used to compute eigenvalues, there is a useful and fairly elementary technique for finding the eigenvector and associated eigenvalue nearest to a given complex number which is called the shifted inverse power method. It tends to work extremely well provided you start with something which is fairly close to an eigenvalue.
Power methods are based on the consideration of powers of a given matrix. Let \(\left\{ \vec{x}_{1},\cdots ,\vec{x}_{n}\right\}\) be a basis of eigenvectors for \(\mathbb{C}^{n}\) such that \(A\vec{x}_{n}=\lambda _{n}\vec{x}_{n}.\) Now let \(\vec{u}_{1}\) be some nonzero vector. Since \(\left\{ \vec{x}_{1},\cdots ,\vec{x}_{n}\right\}\) is a basis, there exists unique scalars, \(c_{i}\) such that \[\vec{u}_{1}=\sum_{k=1}^{n}c_{k}\vec{x}_{k}\nonumber \] Assume you have not been so unlucky as to pick \(\vec{u}_{1}\) in such a way that \(c_{n}=0.\) Then let \(A\vec{u}_{k}=\vec{u}_{k+1}\) so that \[\vec{u}_{m}=A^{m}\vec{u}_{1}=\sum_{k=1}^{n-1}c_{k}\lambda _{k}^{m}\vec{x} _{k}+\lambda _{n}^{m}c_{n}\vec{x}_{n}. \label{20maye1}\] For large \(m\) the last term, \(\lambda _{n}^{m}c_{n}\vec{x}_{n},\) determines quite well the direction of the vector on the right. This is because \(\left\vert \lambda _{n}\right\vert\) is larger than \(\left\vert \lambda _{k}\right\vert\) for \(k<n\) and so for a large \(m,\) the sum, \(\sum_{k=1}^{n-1}c_{k}\lambda _{k}^{m}\vec{x}_{k},\) on the right is fairly insignificant. Therefore, for large \(m,\) \(\vec{u}_{m}\) is essentially a multiple of the eigenvector \(\vec{x}_{n},\) the one which goes with \(\lambda _{n}.\) The only problem is that there is no control of the size of the vectors \(\vec{u}_{m}.\) You can fix this by scaling. Let \(S_{2}\) denote the entry of \(A\vec{u}_{1}\) which is largest in absolute value. We call this a scaling factor. Then \(\vec{u}_{2}\) will not be just \(A\vec{u}_{1}\) but \(A\vec{u}_{1}/S_{2}.\) Next let \(S_{3}\) denote the entry of \(A\vec{u}_{2}\) which has largest absolute value and define \(\vec{u}_{3}\equiv A\vec{u}_{2}/S_{3}.\) Continue this way. The scaling just described does not destroy the relative insignificance of the term involving a sum in \(\eqref{20maye1}\). Indeed it amounts to nothing more than changing the units of length. Also note that from this scaling procedure, the absolute value of the largest element of \(\vec{u}_{k}\) is always equal to 1. Therefore, for large \(m,\) \[\vec{u}_{m}= \frac{\lambda _{n}^{m}c_{n}\vec{x}_{n}}{S_{2}S_{3}\cdots S_{m}}+\left( \text{relatively insignificant term}\right) .\nonumber \] Therefore, the entry of \(A\vec{u}_{m}\) which has the largest absolute value is essentially equal to the entry having largest absolute value of \[A\left( \frac{\lambda _{n}^{m}c_{n}\vec{x}_{n}}{S_{2}S_{3}\cdots S_{m}}\right) = \frac{\lambda _{n}^{m+1}c_{n} \vec{x}_{n}}{S_{2}S_{3}\cdots S_{m}}\approx \lambda _{n}\vec{u}_{m}\nonumber \] and so for large \(m,\) it must be the case that \(\lambda _{n}\approx S_{m+1}.\) This suggests the following procedure.
- Start with a vector \(\vec{u}_{1}\) which you hope has a component in the direction of \(\vec{x}_{n}.\) The vector \(\left( 1,\cdots ,1\right) ^{T}\) is usually a pretty good choice.
- If \(\vec{u}_{k}\) is known, \[\vec{u}_{k+1}=\frac{A\vec{u}_{k}}{S_{k+1}}\nonumber \] where \(S_{k+1}\) is the entry of \(A\vec{u}_{k}\) which has largest absolute value.
- When the scaling factors, \(S_{k}\) are not changing much, \(S_{k+1}\) will be close to the eigenvalue and \(\vec{u}_{k+1}\) will be close to an eigenvector.
- Check your answer to see if it worked well.
The shifted inverse power method involves finding the eigenvalue closest to a given complex number along with the associated eigenvalue. If \(\mu\) is a complex number and you want to find \(\lambda\) which is closest to \(\mu ,\) you could consider the eigenvalues and eigenvectors of \(\left( A-\mu I\right) ^{-1}\). Then \(A\vec{x}=\lambda \vec{x}\) if and only if \[\left( A-\mu I\right) \vec{x}=\left( \lambda -\mu \right) \vec{x}\nonumber \] If and only if \[\frac{1}{\lambda -\mu }\vec{x}=\left( A-\mu I\right) ^{-1}\vec{x}\nonumber \] Thus, if \(\lambda\) is the closest eigenvalue of \(A\) to \(\mu\) then out of all eigenvalues of \(\left( A-\mu I\right) ^{-1},\) you would have \(\frac{1}{ \lambda -\mu }\) would be the largest. Thus all you have to do is apply the power method to \(\left( A-\mu I\right) ^{-1}\) and the eigenvector you get will be the eigenvector which corresponds to \(\lambda\) where \(\lambda\) is the closest to \(\mu\) of all eigenvalues of \(A\). You could use the eigenvector to determine this directly.
Find the eigenvalue and eigenvector for \[\left[ \begin{array}{rrr} 3 & 2 & 1 \\ -2 & 0 & -1 \\ -2 & -2 & 0 \end{array} \right]\nonumber \] which is closest to \(0.9+0.9i\).
Solution
\[\left ( \left[ \begin{array}{rrr} 3 & 2 & 1 \\ -2 & 0 & -1 \\ -2 & -2 & 0 \end{array} \right] - (0.9+0.9i)\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \right )^{-1}\nonumber \]
\[= \left[ \begin{array}{ccc} -0.619\,19-10.\, 545i & -5.\, 524\,9-4.\, 972\,4i & -0.370\,57-5.\, 821\,3i \\ 5.\, 524\,9+4.\, 972\,4i & 5.\, 276\,2+0.248\,62i & 2.\, 762\,4+2.\, 486\,2i \\ 0.741\,14+11.\, 643i & 5.\, 524\,9+4.\, 972\,4i & 0.492\,52+6.\, 918\,9i \end{array} \right]\nonumber \]
Then pick an initial guess and multiply by this matrix raised to a large power. \[= \left[ \begin{array}{ccc} -0.619\,19-10.\, 545i & -5.\, 524\,9-4.\, 972\,4i & -0.370\,57-5.\, 821\,3i \\ 5.\, 524\,9+4.\, 972\,4i & 5.\, 276\,2+0.248\,62i & 2.\, 762\,4+2.\, 486\,2i \\ 0.741\,14+11.\, 643i & 5.\, 524\,9+4.\, 972\,4i & 0.492\,52+6.\, 918\,9i \end{array} \right]^{15}\left[ \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right]\nonumber \]
This equals \[\left[ \begin{array}{c} 1.\, 562\,9\times 10^{13}-3.\, 899\,3\times 10^{12}i \\ -5.\, 864\,5\times 10^{12}+9.\, 764\,2\times 10^{12}i \\ -1.\, 562\,9\times 10^{13}+3.\, 899\,9\times 10^{12}i \end{array} \right]\nonumber \] Now divide by an entry to make the vector have reasonable size. This yields \[\left[ \begin{array}{c} -0.999\,99-3.\, 614\,0\times 10^{-5}i \\ 0.499\,99-0.499\,99i \\ 1.0 \end{array} \right]\nonumber\] which is close to \[\left[ \begin{array}{c} -1 \\ 0.5-0.5i \\ 1.0 \end{array} \right]\nonumber\] Then \[\left[ \begin{array}{rrr} 3 & 2 & 1 \\ -2 & 0 & -1 \\ -2 & -2 & 0 \end{array} \right] \left[ \begin{array}{c} -1 \\ 0.5-0.5i \\ 1.0 \end{array} \right] =\left[ \begin{array}{c} -1.0-1.0i \\ 1.0 \\ 1.0+1.0i \end{array} \right]\nonumber \] Now to determine the eigenvalue, you could just take the ratio of corresponding entries. Pick the two corresponding entries which have the largest absolute values. In this case, you would get the eigenvalue is \(1+i\) which happens to be the exact eigenvalue. Thus an eigenvector and eigenvalue are \[\left[ \begin{array}{c} -1 \\ 0.5-0.5i \\ 1.0 \end{array} \right], 1+i\nonumber \]
Usually it won’t work out so well but you can still find what is desired. Thus, once you have obtained approximate eigenvalues using the \(QR\) algorithm, you can find the eigenvalue more exactly along with an eigenvector associated with it by using the shifted inverse power method.
This page titled 6.9: Special Factorizations was last modified on Wed, 27 Aug 2025 04:37:19 GMT and is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Doli Bambhania, Fatemeh Yarahmadi, and Bill Wilson.
The book could not be loaded just now.