QR-Factorization.

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) $A$, we want to decompose $A$ into an orthogonal matrix $Q$ and an upper-triangular matrix $R$

Just to remind you what this all means, if $Q$ is an orthogonal matrix, then its columns are orthogonal unit vectors, which means that $Q^{T}Q = I$.  A matrix $R$ is upper triangular if everything to the left of the diagonal is 0.  For example, we could have $R$ equal to

$\left(\begin{array}{cccc}1 & 2 & 3 & 4 \\ 0 & 5 & 6 & 7 \\ 0 & 0 & 8 & 9 \\ 0 & 0 & 0 & 10 \end{array}\right)$

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 $A$ be able to be decomposed as a product of an orthogonal matrix and an upper-triangular one.

Here’s how we do it.  Let’s let $V$ be our vector space (with inner product $\langle\cdot , \cdot\rangle$), and $A$ is our matrix.  Let’s write $A$ as

$[a_{1} \,\,\, a_{2} \,\,\, \cdots \,\,\, a_{n}]$

where each $a_{i}$ is a column vector.  Now apply Gram-Schmidt to these, and we obtain an orthonormal set $\{e_{1}, e_{2}, \dots, e_{n}\}$

Our orthogonal matrix $Q$ will be equal to

$[e_{1} \,\,\, e_{2} \,\,\, \cdots \,\,\, e_{n}]$

and our upper-triangular matrix will be equal to

$\left(\begin{array}{ccccc} \langle e_{1}, a_{1}\rangle & \langle e_{1}, a_{2}\rangle & \langle e_{1}, a_{3}\rangle & \cdots & \langle e_{1}, a_{n}\rangle \\ 0 & \langle e_{2}, a_{2}\rangle & \langle e_{2}, a_{3}\rangle & \cdots & \langle e_{2}, a_{n}\rangle \\ 0 & 0 & \langle e_{3}, a_{3}\rangle & \cdots & \langle e_{3}, a_{n}\rangle \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \langle e_{n}, a_{n}\rangle\end{array}\right)$

which looks messy and complex, but it really isn’t too bad in practice.

Example!

Let’s do a simple example using the standard real vector space with the inner product as the dot product.

Let’s let $A$ be the matrix

$\left( \begin{array}{cc} 0 & 1\\ 2 & 2\end{array}\right)$

Now, we need to apply Gram-Schmidt to the column vectors (which I will write horizontally now, for ease of typing) $[0\,\,\, 2]$ and $[1\,\,\, 2]$.  So we obtain $e_{1} = [0\,\,\, 1]$ and $e_{2} = [1\,\,\, 2] - 2[0\,\,\, 1] = [1\,\,\, 0]$.  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 $Q$ is equal to

$\left( \begin{array}{cc} 0 & 1\\ 1 & 0\end{array}\right)$

which is obviously orthogonal, and our $R$ is equal to

$\left( \begin{array}{cc} 2 & 2\\ 0 & 1\end{array}\right)$

which is nicely upper-triangular.  Now notice that

$\left( \begin{array}{cc} 0 & 1\\ 1 & 0\end{array}\right)\left( \begin{array}{cc} 2 & 2\\ 0 & 1\end{array}\right) =\left( \begin{array}{cc} 0 & 1\\ 2 & 2\end{array}\right)$

So sweet.  Try this on paper, you’ll really be amazed with how fun it is to do.