QR Factorization

Let's jump right to the result:

If A is a real valued n x n matrix, then A can be written as QR where Q is an orthogonal matrix (that is, the columns of Q are orthogonal unit vectors) and R is an upper triangular matrix. If A is  invertible, then the factorization is unique if we require the diagonal elements of R to be positive.

A bit of a mouthful, but intuitive enough in light of yesterday's result. First lets look at the case when A is invertible. If that's so, then A is of rank n, which means its columns span Rⁿ. Now, from yesterday, that means we not only can create an orthonormal basis from the columns of A, but we know how to do it in a way that each of the original columns is a linear combination of the basis elements that precede it. That is:



Thus, A = QR where Q contains the unit vectors from the Gram-Schmidt process and R = {r_ij} are the coefficients of those vectors to construct the original set of columns in A. Since r_ij = 0 for all i > j, R is upper triangular.

In the case where A is not invertible, the rank of A is less than n, so just run Gram-Schmidt and whenever you hit a column that is dependent on the previous columns, stick a zero vector in A and just set the coefficients in R to reconstruct the original column from the existing basis rows. You'll still wind up with an upper-triangular R since you can just stick any non-zero coefficient you want in the remaining part of that row of R (which is why R is only guaranteed unique if A is invertible).

Decomposing a matrix like this is useful for solving least squares problems as well as certain eigenvalue problems. The rub is that the Gram Schmidt process is numerically unstable so, while it's a great way to explain why this works, it's not a very good way to actually get a solution. Fortunately, there are numerically stable alternatives that are included in any computation package. The value of Gram-Schmidt is simply that it does such a good job of illustrating how this all works.