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.

Get to the point already.

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.



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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: