You are about to erase your work on this activity. Are you sure you want to do this?
Updated Version Available
There is an updated version of this activity. If you update to the most recent version of this activity, then your current progress on this activity will be erased. Regardless, your record of completion will remain. How would you like to proceed?
Mathematical Expression Editor
QR Factorization
One of the main virtues of orthogonal matrices is that they can be easily
inverted—the transpose is the inverse. This fact, combined with the factorization
theorem in this section, provides a useful way to simplify many matrix calculations
(for example, in least squares approximation).
Let \(A\) be an \(m \times n\) matrix with independent columns. A QR-factorization of \(A\) expresses it as \(A = QR\)
where \(Q\) is \(m \times n\) with orthonormal columns and \(R\) is an invertible and upper triangular
matrix with positive diagonal entries.
The importance of the factorization lies in the fact that there are computer
algorithms that accomplish it with good control over round-off error, making it
particularly useful in matrix calculations. The factorization is a matrix version of the
Gram-Schmidt process.
Suppose \(A = \left [ \begin{array}{cccc} |&|& &| \\ \vec {c}_{1} & \vec {c}_{2} & \cdots & \vec {c}_{n}\\ |&|& &| \end{array}\right ]\) is an \(m \times n\) matrix with linearly independent columns \(\vec {c}_{1}, \vec {c}_{2}, \dots , \vec {c}_{n}\). The Gram-Schmidt
algorithm can be applied to these columns to provide orthogonal columns \(\vec {f}_{1}, \vec {f}_{2}, \dots , \vec {f}_{n}\) where \(\vec {f}_{1} = \vec {c}_{1}\)
and
for each \(k = 2, 3, \dots , n\). Now write \(\vec {q}_{k} = \frac {1}{\norm { \vec {f}_{k} }}\vec {f}_{k}\) for each \(k\). Then \(\vec {q}_{1}, \vec {q}_{2}, \dots , \vec {q}_{n}\) are orthonormal columns, and the above
equation becomes
Here the first factor \(Q = \left [ \begin{array}{ccccc} |&|&|& &| \\ \vec {q}_{1} & \vec {q}_{2} & \vec {q}_{3} & \cdots & \vec {q}_{n}\\ |&|&|& &| \end{array}\right ]\) has orthonormal columns, and the second factor is an \(n \times n\) upper
triangular matrix \(R\) with positive diagonal entries (and so is invertible). We record this
in the following theorem.
QR-Factorization Every \(m \times n\) matrix \(A\) with linearly independent columns has a
QR-factorization \(A = QR\) where \(Q\) has orthonormal columns and \(R\) is upper triangular with
positive diagonal entries.
The matrices \(Q\) and \(R\) in Theorem th:QR-025133 are uniquely determined by \(A\); we return to this
below.
Denote the columns of \(A\) as \(\vec {c}_{1}\), \(\vec {c}_{2}\), and \(\vec {c}_{3}\), and observe that \(\{\vec {c}_{1}, \vec {c}_{2}, \vec {c}_{3}\}\) is independent. If we apply the
Gram-Schmidt algorithm to these columns, the result is:
If a matrix \(A\) has independent rows and we apply QR-factorization to \(A^{T}\), the result
is:
If \(A\) has independent rows, then \(A\) factors uniquely as \(A = LP\) where \(P\) has orthonormal rows
and \(L\) is an invertible lower triangular matrix with positive main diagonal entries.
Since a square matrix with orthonormal columns is orthogonal, we have
Every square invertible matrix \(A\) has factorizations \(A = QR\) and \(A = LP\) where \(Q\) and \(P\) are orthogonal, \(R\)
is upper triangular with positive diagonal entries, and \(L\) is lower triangular with
positive diagonal entries.
We now take the time to prove the uniqueness of the QR-factorization.
Let \(A\) be an \(m \times n\) matrix with independent columns. If \(A = QR\) and \(A = Q_{1}R_{1}\) are QR-factorizations of \(A\),
then \(Q_{1} = Q\) and \(R_{1} = R\).
Write \(Q = \left [ \begin{array}{cccc} |&|& &| \\ \vec {c}_{1} & \vec {c}_{2} & \cdots & \vec {c}_{n}\\ |&|& &| \end{array}\right ]\) and \(Q_{1} = \left [ \begin{array}{cccc} |&|& &| \\ \vec {d}_{1} & \vec {d}_{2} & \cdots & \vec {d}_{n}\\ |&|& &| \end{array}\right ]\) in terms of their columns, and observe first that \(Q^TQ = I_{n} = Q_{1}^TQ_{1}\) because \(Q\) and \(Q_{1}\) have
orthonormal columns. Hence it suffices to show that \(Q_{1} = Q\) (then \(R_{1} = Q_{1}^TA = Q^TA = R\)). Since \(Q_{1}^TQ_{1} = I_{n}\), the
equation \(QR = Q_{1}R_{1}\) gives \(Q_{1}^TQ = R_{1}R^{-1}\); for convenience we write this matrix as
This matrix is upper
triangular with positive diagonal elements (since this is true for \(R\) and \(R_{1}\)), so \(t_{ii} > 0\) for
each \(i\) and \(t_{ij} = 0\) if \(i > j\). On the other hand, the \((i, j)\)-entry of \(Q_{1}^TQ\) is \(\vec {d}_{i}^T\vec {c}_{j} = \vec {d}_{i} \dotp \vec {c}_{j}\), so we have \(\vec {d}_{i} \dotp \vec {c}_{j} = t_{ij}\) for all \(i\)
and \(j\). But each \(\vec {c}_{j}\) is in \(\mbox {span}\{\vec {d}_{1}, \vec {d}_{2}, \dots , \vec {d}_{n}\}\) because \(Q = Q_{1}(R_{1}R^{-1})\). We know how to write a vector as a linear
combination of an orthonormal basis (using Corollary cor:orthonormal from Orthogonality and
Projections):
The first of
these equations gives \(1 = \norm { \vec {c}_{1} } = \norm { t_{11}\vec {d}_{1} } = | t_{11} | \norm { \vec {d}_{1} } = t_{11}\), whence \(\vec {c}_{1} = \vec {d}_{1}\). But then we have \(t_{12} = \vec {d}_{1} \dotp \vec {c}_{2} = \vec {c}_{1} \dotp \vec {c}_{2} = 0\), so the second equation
becomes \(\vec {c}_{2} = t_{22}\vec {d}_{2}\). Now a similar argument gives \(\vec {c}_{2} = \vec {d}_{2}\), and then \(t_{13} = 0\) and \(t_{23} = 0\) follows in the same
way. Hence \(\vec {c}_{3} = t_{33}\vec {d}_{3}\) and \(\vec {c}_{3} = \vec {d}_{3}\). Continue in this way to get \(\vec {c}_{i} = \vec {d}_{i}\) for all \(i\). This proves that \(Q_{1} = Q\).
QR-Algorithm for approximating eigenvalues
In The Power Method and the Dominant Eigenvalue, we learned about an iterative
method for computing eigenvalues. We also mentioned that a better method
for approximating the eigenvalues of an invertible matrix \(A\) depends on the
QR-factorization of \(A\). While it is beyond the scope of this book to pursue a detailed
discussion of this method, we give an example and conclude with some remarks on
the QR-algorithm. The interested reader is referred to J. M. Wilkinson, The
Algebraic Eigenvalue Problem (Oxford, England: Oxford University Press, 1965) or G.
W. Stewart, Introduction to Matrix Computations (New York: Academic Press,
1973).
The QR-algorithm uses QR-factorization repeatedly to create a sequence of matrices \(A_{1} =A, A_{2}, A_{3}, \dots ,\)
as follows:
Let \(A\) be an invertible matrix.
Step 1: Define \(A_{1} = A\) and factor it as \(A_{1} = Q_{1}R_{1}\).
Step 2: Define \(A_{2} = R_{1}Q_{1}\) and factor it as \(A_{2} = Q_{2}R_{2}\).
Step 3: Define \(A_{3} = R_{2}Q_{2}\) and factor it as \(A_{3} = Q_{3}R_{3}\).
Note that \(A_{k + 1}\) is similar to \(A_{k}\) (in fact, \(A_{k+1} = R_{k}Q_{k} = (Q_{k}^{-1}A_{k})Q_{k}\)), and hence each \(A_{k}\) has the same eigenvalues as \(A\). If
the eigenvalues of \(A\) are real and have distinct absolute values, the sequence of
matrices \(A_{1}, A_{2}, A_{3}, \dots \) converges to an upper triangular matrix with these eigenvalues on
the main diagonal. We will discuss the complex case eigenvalue case below.
If \(A = \left [ \begin{array}{rr} 1 & 1 \\ 2 & 0 \end{array}\right ]\) as in Example ?? of The Power Method and the Dominant Eigenvalue, use the
QR-algorithm to approximate the eigenvalues.
The matrices \(A_{1}\), \(A_{2}\), and \(A_{3}\) are as follows:
This is converging to \(\left [ \begin{array}{rr} 2 & \ast \\ 0 & -1 \end{array}\right ]\) and so is approximating the eigenvalues \(2\) and \(-1\) on the main
diagonal.
Shifting.
We first learned about the concept of shifting in The Power Method and the
Dominant Eigenvalue. Convergence is accelerated if, at stage \(k\) of the algorithm, a
number \(\tau _{k}\) is chosen and \(A_{k} - \tau _{k}I\) is factored in the form \(Q_{k}R_{k}\) rather than \(A_{k}\) itself. Then
is said to be in upper Hessenberg form, and the QR-factorizations
of such matrices are greatly simplified. Given an \(n \times n\) matrix \(A\), a series of orthogonal
matrices \(H_{1}, H_{2}, \dots , H_{m}\) (called Householder matrices can be easily constructed such that
\begin{equation*} B = H_{m}^T \cdots H_{1}^TAH_{1} \cdots H_{m} \end{equation*}
is in
upper Hessenberg form. Then the QR-algorithm can be efficiently applied to \(B\) and,
because \(B\) is similar to \(A\), it produces the eigenvalues of \(A\).
Complex Eigenvalues.
If some of the eigenvalues of a real matrix \(A\) are not real, the QR-algorithm converges
to a block upper triangular matrix where the diagonal blocks are either \(1 \times 1\) (the real
eigenvalues) or \(2 \times 2\) (each providing a pair of conjugate complex eigenvalues of
\(A\)).
If \(R\) is upper triangular and invertible, show that there exists a diagonal matrix \(D\)
with diagonal entries \(\pm 1\) such that \(R_{1} = DR\) is invertible, upper triangular, and has positive
diagonal entries.
If \(A\) has independent columns, let \(A = QR\) where \(Q\) has orthonormal columns and \(R\) is invertible and upper triangular. (Some
authors do not require a \(QR\)-factorization to have positive diagonal entries.) Show that
there is a diagonal matrix \(D\) with diagonal entries \(\pm 1\) such that \(A = (QD)(DR)\) is the QR-factorization of
\(A\).
See Practice Problem
In each case, find the exact eigenvalues and then approximate them using the
QR-algorithm.
If \(A\) is symmetric, show that each matrix \(A_{k}\) in the QR-algorithm is also symmetric.
Deduce that they converge to a diagonal matrix.
Click the arrow to see answer.
Use induction on \(k\). If \(k = 1\), \(A_{1} = A\). In general \(A_{k+1} = Q_{k}^{-1}A_{k}Q_{k} = Q_{k}^{T}A_{k}Q_{k}\), so the fact that \(A_{k}^{T} = A_{k}\)
implies \(A_{k+1}^{T} = A_{k+1}\). The eigenvalues of \(A\) are all real (Theorem ??), so the \(A_{k}\) converge to an upper
triangular matrix \(T\). But \(T\) must also be symmetric (it is the limit of symmetric
matrices), so it is diagonal.
Apply the QR-algorithm to \(A = \left [ \begin{array}{rr} 2 & -3 \\ 1 & -2 \end{array}\right ]\). Explain.
Given a matrix \(A\), let \(A_{k}\), \(Q_{k}\), and \(R_{k}\), \(k \geq 1\), be the matrices constructed in the QR-algorithm.
Show that \(A_{k} = (Q_{1}Q_{2} \cdots Q_{k})(R_{k} \cdots R_{2}R_{1})\) for each \(k \geq 1\) and hence that this is a QR-factorization of \(A_{k}\).
Show that \(Q_{k}R_{k} = R_{k-1}Q_{k-1}\) for
each \(k \geq 2\), and use this equality to compute \((Q_{1}Q_{2} \cdots Q_{k})(R_{k} \cdots R_{2}R_{1})\) “from the centre out.” Use the fact that \((AB)^{n+1} = A(BA)^{n}B\) for
any square matrices \(A\) and \(B\).