In this section we’re going to look at a way to “decompose” or “factor” an  matrix as follows.

Proof : The proof here will consist of actually constructing Q and R and showing that they in fact do multiply to give A.

Okay, let’s start with A and suppose that it’s columns are given by , , … , .  Also suppose that we perform the Gram-Schmidt process on these vectors and arrive at a set of orthonormal vectors , , … , .  Next, define Q (yes, the Q in the theorem statement) to be the  matrix whose columns are , , … ,  and so Q will be a matrix with orthonormal columns.  We can then write A and Q as,

Next, because each of the  ’s are in  we know from Theorem 2 of the previous section that we can write each  as a linear combination of , , … ,  in the following manner.

Next, define R (and yes, this will eventually be the R from the theorem statement) to be the  matrix defined as,

Now, let’s examine the product, QR.

From the section on Matrix Arithmetic we know that the j^th column of this product is simply Q times the j^th column of R.  However, if you work through a couple of these you’ll see that when we multiply Q times the j^th column of R we arrive at the formula for  that we’ve got above.  In other words,

So, we can factor A as a product of Q and R and Q has the correct form.  Now all that we need to do is to show that R is an invertible upper triangular matrix and we’ll be done.  First, from the Gram-Schmidt process we know that  is orthogonal to , , … , .  This means that all the inner products below the main diagonal must be zero since they are all of the form  with .

Now, we know from Theorem 2 from the Special Matrices section that a triangular matrix will be invertible if the main diagonal entries, , are non-zero.  This is fairly easy to show.  Here is the general formula for  from the Gram-Schmidt process.

Recall that we’re assuming that we found the orthonormal  ’s and so each of these will have a norm of 1 and so the norms are not needed in the formula.  Now, solving this for  gives,

Let’s look at the diagonal entries of R.  We’ll plug in the formula for  into the inner product and do some rewriting using the properties of the inner product.

However the  are orthonormal basis vectors and so we know that

Using these we see that the diagonal entries are nothing more than,

So, the diagonal entries of R are non-zero and hence R must be invertible.

So, now that we’ve gotten the proof out of the way let’s work an example.

There is a nice application of the QR-Decomposition to the Least Squares Process that we examined in the previous section.  To see this however, we will first need to prove a quick theorem.

Note that the only way Q can have orthonormal columns in  is to require that .  Because the columns are vectors in  and we know from Theorem 1 in the Orthonormal Basis section that a set of orthogonal vectors will also be linearly independent.  However, from Theorem 2 in the Linear Independence section we know that if  the column vectors will be linearly dependent.

Also, because we want to make it clear that we’re using the standard Euclidean inner product we will go back to the dot product notation, , instead of the usual inner product notation, .

Proof : Now recall that to prove an “if and only if” theorem we need to assume each part and show that this implies the other part.  However, there is some work that we can do that we’ll need in both parts so let’s do that first.

Let , , … ,  be the columns of Q.  So,

For the transpose we take the columns of Q and turn them into the rows of .  Therefore, the rows of  are , , … ,  (the transposes are needed to turn the column vectors, , into row vectors,  ) and,

Now, let’s take a look at the product .  Entries in the product will be rows of  times columns of Q and so the product will be,

Recalling that  we see that we can also write the product as,

Now, let’s actually do the proof.

 Assume that the columns of Q are orthogonal and show that this means that we must have .

Since we are assuming that the columns of Q are orthonormal we know that,

Therefore the product is,

So we’re done with this part.

 Here assume that  and we’ll need to show that this means that the columns of Q are orthogonal. 

So, we’re assuming that,

However, simply by setting entries in these two matrices equal we see that,

and this is exactly what it means for the columns to be orthogonal so we’re done.

The following theorem can be used, on occasion, to significantly reduce the amount of work required for the least squares problem.

Proof : There really isn’t much to do here other than plug formulas in.  We’ll start with the normal system for .

Now, A has linearly independent columns we know that it has a QR-Decomposition for A so let’s plug the decomposition into the normal system and using properties of transposes we’ll rewrite things a little.

Now, since the columns of Q are orthonormal we know that  by Theorem 2 above.  Also, we know that R is an invertible matrix and so know that  is also an invertible matrix.  So, we’ll also multiply both sides by .  Upon doing all this we arrive at,

So, just how is this supposed to help us with the Least Squares Problem?  We’ll since R is upper triangular this will be a very easy system to solve.  It can however take some work to get down to this system.

Let’s rework the last example from the previous section only this time we’ll use the QR-Decomposition method.

At this point you are probably asking yourself just why this method is better than the method we used in the previous section.  After all, it was a lot of work and some of the numbers were downright awful.  The answer is that by hand, this may not be the best way for doing these problems, however, if you are going to program the least squares method into a computer all of the steps here are very easy to program and so this method is a very nice method for programming the Least Squares process.