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

 

Theorem 1 Suppose that A is an  matrix with linearly independent columns then A can be factored as,                                                                     where Q is an  matrix with orthonormal columns and R is an invertible  upper triangular matrix.

 

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 in this step we can assume that we’ve already converted the previous vectors to have a norm of 1 and so the norms are not needed in the formula for .  Note that we also know that .

 

Now, solving this for   and using   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 an 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.

 

Example 1  Find the QR-decomposition for the matrix,                                                            Solution The columns from A are,                                              We performed Gram-Schmidt on these vectors in Example 3 of the previous section.  So, the orthonormal vectors that we’ll use for Q are,                                and the matrix Q is,                                                         The matrix R is,                                  So, the QR-Decomposition for this matrix is,                                We’ll leave it to you to verify that this multiplication does in fact give A.

 

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.

 

Theorem 2 If Q is an  matrix with  then the columns of Q are an orthonormal set of vectors in  with the standard Euclidean inner product if and only if .

 

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.

 

Theorem 3 Suppose that A has linearly independent columns.  Then the normal system associated with  can be written as,

 

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.

 

Example 2  Find the least squares solution to the following system of equations.                                                      Solution First, we’ll leave it to you to verify that the columns of A are linearly independent.  Here are the columns of A.                                 Now, we’ll need to perform Gram-Schmidt on these to get them into a set of orthonormal vectors.  The first step is,                                                                    Here’s the inner product and norm that we’ll need for the second step.                                                 The second vector is then,                                        The final step will require the following inner products and norms.                  The third, and final orthogonal vector is then,                                            Okay, these are the orthogonal vectors.  If we divide each of them by their norms we will get the orthonormal vectors that we need for the decomposition.  The norms are,                                  The orthonormal vectors are then,                             We can now write down Q for the decomposition.                                                    Finally, R is given by,     Okay, we can now proceed with the Least Squares process.  First we’ll need .                                           The normal system can then be written as,                 This corresponds to the following system of equations.                      These are the same values that we received in the previous section.

 

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.