October 28, 2010
While I was studying for a linear algebra exam, I discovered a deep-seeded love for QR-Factorization. I’m not going to explain why this is important, or why we should care about such a factorization; in fact, I have no idea why this is important or why I should care about this. I was directed to this, so I’ll direct you there too.
Anyhow, here’s the game. Given some square matrix (this is not necessarily, but it makes it easier) , we want to decompose into an orthogonal matrix and an upper-triangular matrix .
Just to remind you what this all means, if is an orthogonal matrix, then its columns are orthogonal unit vectors, which means that . A matrix is upper triangular if everything to the left of the diagonal is 0. For example, we could have equal to
which is a nice example of an upper-triangular matrix. Note that, in general, orthogonal matrices are very nice (they have lots of cool properties that I may write a post on one day), and upper-triangular matrices are pretty sweet as well (and I think I may have already written up a post on these…) which is why it’s nice to have any arbitrary square matrix be able to be decomposed as a product of an orthogonal matrix and an upper-triangular one.
Get to the point already.
Here’s how we do it. Let’s let be our vector space (with inner product ), and is our matrix. Let’s write as
where each is a column vector. Now apply Gram-Schmidt to these, and we obtain an orthonormal set .
Our orthogonal matrix will be equal to
and our upper-triangular matrix will be equal to
which looks messy and complex, but it really isn’t too bad in practice.
Let’s do a simple example using the standard real vector space with the inner product as the dot product.
Let’s let be the matrix
Now, we need to apply Gram-Schmidt to the column vectors (which I will write horizontally now, for ease of typing) and . So we obtain and . Note that, in general, you need to divide out by a messy norm, but I was clever here so I didn’t really have to. So now we have our matrices.
We have that is equal to
which is obviously orthogonal, and our is equal to
which is nicely upper-triangular. Now notice that
So sweet. Try this on paper, you’ll really be amazed with how fun it is to do.