Projections onto Subspaces and the Gram-Schmidt Process in \R^n

Section 25 Projections onto Subspaces and the Gram-Schmidt Process in $R^{n}$

Focus Questions

By the end of this section, you should be able to give precise and thorough answers to the questions listed below. You may want to keep these questions in mind to focus your thoughts as you complete the section.

What is a projection of a vector onto a subspace and why are such projections important?
What is a projection of a vector orthogonal to a subspace and why are such orthogonal projections important?
What is the Gram-Schmidt process and why is it useful?
What is the QR-factorization of a matrix and why is it useful?

🔗

Subsection Application: MIMO Systems

🔗

MIMO (Multiple Input Multiple Output) systems are widely used to increase data transmission rates and improve the quality of wireless communication systems. MIMO is one of several forms of smart antenna technology, and it makes use of multiple antennas at the transmitter to send signals and multiple antennas at the receiver to accept the signals. MIMO systems transmit the same data on multiple streams, which introduces redundancy into the system. MIMO systems can utilize bounced and reflected signals to actually improve signal strength. This is very useful in urban environments in the presence of large buildings and the absence of direct line-of-sight transmission. MIMO systems can transmit several information streams in parallel (known as spatial multiplexing), allowing for increased data transformation rates. The presence of multiple receiver antennas allows for greater reliability in the system.

🔗

In a MIMO system, every transmitter antenna sends a signal to every receiver antenna as illustrated in Figure 25.1. In each of these transmissions the signal can be disturbed in some way. Two types of disturbances are fading and noise. Fading is due to time variations in the received signal, which can occur because of atmospheric conditions or obstacles over the path which are varying with respect to time. In a MIMO system we have multipath fading for the different paths the signal takes from different antennas to receivers, which causes fluctuations in amplitude, phase and angle of arrival of the received signal. Noise is an unwanted signal which interferes with actual signal. Both fading and noise result in a received signal that is different than the transmitted signal. The problem is how to recover the original signal from the transmitted signal. The QR decomposition is used in this process. To improve the efficiency of MIMO systems, different methods are introduced to determine a QR decomposition. We will discuss MIMO systems in more detail later in this section, and how Householder transformations can be used to find QR decompositions.

🔗

Subsection Introduction

🔗

In many situations (least squares approximations, for example) want to find a vector

w

in a subspace

W

R^{n}

that is the “best” approximation to a vector

v

not in the subspace. A natural measure of “best” is to find a vector

w

W

if one exists, such that the distance from

w

u

is a minimum. This means we want to find

w

so that the quantity

| | w - u | |

🔗

is as small as possible over all vectors

w

W

To do this, we will need to find a suitable projection of the vector

v

onto the subspace

W

We have already done this in the case that

W = Span {w_{1}}

is the span of a single vector -- we can project the vector

v

in the direction of

w_{1} .

Our goal is to generalize this to project a vector

v

onto an entire subspace in a useful way.

🔗

Preview Activity 25.1.

Let $B = {w_{1}, w_{2}}$ be a basis for a subspace $W$ of $R^{3}$ where $w_{1} = [1 0 0]^{T}$ and $w_{2} = [0 1 0]^{T}$ Note that $B$ is an orthonormal basis for $W$ Let $v = [1 2 1]^{T}$ Note that $W$ is the $x y$ plane and that $v$ is not in $W$ as illustrated in Figure 25.2.

Figure 25.2. The space $W$ and vectors $w_{1},$ $w_{2},$ and $v .$

🔗

(a)

Find the projection $u_{1}$ of $v$ onto $W_{1} = Span {w_{1}}$

Hint.

See Equation (23.2).

🔗

(b)

Find the projection $u_{2}$ of $v$ onto $W_{2} = Span {w_{2}}$

🔗

(c)

Calculate the distance between $v$ and $u_{1}$ and $v$ and $u_{2}$ Which of $u_{1}$ and $u_{2}$ is closer to $v ?$

🔗

(d)

Show that the vector $\frac{3}{4} [1 2 0]^{T}$ is in $W$ and find the distance between $v$ and $\frac{3}{4} [1 2 0]^{T}$

🔗

(e)

Part (4) shows that neither vector $u_{1} = {proj}_{w_{1}} v$ nor $u_{2} = {proj}_{w_{2}} v$ is the vector in $W$ that is closest to $v$ We should probably expect this neither projection uses the fact that the other vector might contribute to the closest vector. Let us instead consider the sum $u_{3} = u_{1} + u_{2}$ Calculate the components of this vector $u_{3}$ and determine the distance between $u_{3}$ and $v$ Which of the three vectors $u_{1}$ $u_{2}$ and $u_{3}$ in $W$ is closest to $v ?$

🔗

(f)

A picture of $w_{1}$ $w_{2}$ $W$ and $v$ is shown in Figure 25.2. Draw in $u_{1}$ $u_{2}$ and $u_{3}$ Draw a picture of the vector $w$ in $W$ that appears to be closest to $v$ Does this vector seem to have any relationship to $u_{1}$ $u_{2}$ or $u_{3} ?$ If yes, what relationship do you see?

🔗

Subsection Projections onto Subspaces and Orthogonal Projections

🔗

Preview Activity 25.1 gives an indication of how we can project a vector

v

R^{n}

onto a subspace

W

R^{n} .

If we have an orthogonal basis for

W,

we can just add the projections of

v

onto each basis vector. The resulting vector is called the projection of

v

onto the subspace

W .

As we did with projections onto vectors, we can also define the projection of

v

orthogonal to

W .

Note that to make this all work out properly, we will see that we need an orthogonal basis for

W .

🔗

Definition 25.3.

Let $W$ be a subspace of $R^{n}$ and let ${w_{1}, w_{2}, \dots, w_{m}}$ be an orthogonal basis for $W .$ The projection of the vector $v$ in $V$ onto $W$ is the vector

{proj}_{W} v = \frac{v \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} + \frac{v \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2} + \dots + \frac{v \cdot w_{m}}{w_{m} \cdot w_{m}} w_{m} .

The projection of $v$ orthogonal to $W$ is the vector

{proj}_{⊥ W} v = v - {proj}_{W} v .

🔗

The notation

{proj}_{⊥ W} v

indicates that we expect this vector to be orthogonal to every vector in

W .

We address this in the following activity.

🔗

Activity 25.2.

Let $W = Span {w_{1}, w_{2}}$ in $R^{3},$ with $w_{1} = [1 0 0]^{T}$ and $w_{2} = [0 1 0]^{T},$ and $v = [1 2 1]^{T}$ as in Preview Activity 25.1. Recall that ${proj}_{W} v = [1 2 0]^{T} .$ Find the projection of $v$ orthogonal to $W$ and show directly that ${proj}_{⊥ W} v$ is orthogonal to the basis vectors for $W$ (and hence to every vector in $W$ ).

🔗

Activity 25.2 indicates that the vector

{proj}_{⊥ W} v

is in fact orthogonal to every vector in

W .

To see that this is true in general, let

B = {w_{1}, w_{2}, \dots, w_{m}}

be an orthogonal basis for a subspace

W

R^{n}

and let

v

be a vector in

R^{n} .

Let

w = {proj}_{W} v = \frac{v \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} + \frac{v \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2} + \dots + \frac{v \cdot w_{m}}{w_{m} \cdot w_{m}} w_{m} .

🔗

Then

v - w

is the projection of

v

orthogonal to

W .

We will show that

v - w

is orthogonal to every basis vector for

W .

Since

B

is an orthogonal basis for

W,

we know that

w_{i} \cdot w_{j} = 0

for

i \neq j .

So if

k

is between 1 and

m

then

\begin{aligned} w_{k} \cdot (v - w) & = (w_{k} \cdot v) - (w_{k} \cdot w) \\ = (w_{k} \cdot v) - [w_{k} \cdot (\frac{v \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} + \frac{v \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2} + \dots + \frac{v \cdot w_{m}}{w_{m} \cdot w_{m}} w_{m})] \\ = (w_{k} \cdot v) - (\frac{v \cdot w_{k}}{w_{k} \cdot w_{k}}) (w_{k} \cdot w_{k}) \\ = (w_{k} \cdot v) - (v \cdot w_{k}) \\ = 0 . \end{aligned}

🔗

So the vector

v - w

is orthogonal to every basis vector for

W,

and therefore to every vector in

W

(Theorem 23.16). Because

B

is a basis for

W,

x

is in

W,

then

x = c_{1} w_{1} + c_{2} w_{2} + \dots + c_{m} w_{m}

🔗

for some scalars

c_{1},

c_{2},

\dots,

c_{m} .

(v - w) \cdot x = \sum_{k = 1}^{m} c_{k} (v - w) \cdot w_{k} = 0,

🔗

and so

v - w

is orthogonal to every vector in

W .

🔗

Subsection Best Approximations

🔗

We have seen that

{proj}_{⊥ W} v

is orthogonal to every vector in

W,

which suggests that

{proj}_{W} v

is in fact the vector in

W

that is closest to

v .

We now verify this fact and conclude that

{proj}_{W} v

is the vector in

W

closest to

v

and therefore the best approximation of

v

by a vector in

W .

🔗

Theorem 25.4.

Let $B = {w_{1}, w_{2}, \dots, w_{m}}$ be an orthogonal basis for a subspace $W$ of $R^{n}$ and let $v$ be a vector in $R^{n} .$ Then

| | v - {proj}_{W} v | | < | | v - x | |

for every vector $x$ different from ${proj}_{W} v$ in $W .$

🔗

Proof.

Let $B = {w_{1}, w_{2}, \dots, w_{m}}$ be an orthogonal basis for a subspace $W$ of $R^{n}$ and let $v$ be a vector in $R^{n} .$ Let $x$ be a vector in $W .$ The vector ${proj}_{W} v - x$ is in $W,$ so is orthogonal to ${proj}_{⊥ W} v = v - {proj}_{W} v .$ Thus, the dotted triangle whose vertices are the tips of the vectors $v,$ $x,$ and ${proj}_{W} v$ in Figure 25.5 is a right triangle.

Figure 25.5. The best approximation to $v$ in $W$

The Pythagorean theorem then shows that

| | v - x | |^{2} = | | {proj}_{⊥ W} v | |^{2} + | | {proj}_{W} v - x | |^{2} .

Now $x \neq {proj}_{W} v,$ so $| | {proj}_{W} v - x | |^{2} > 0 .$ This implies

| | v - x | |^{2} > | | {proj}_{⊥ W} v | |^{2}

and it follows that

| | v - x | | > | | {proj}_{⊥ W} v | | .

🔗

This theorem shows that the distance from

{proj}_{W} v

v

is less than the distance from any other vector in

W

v .

{proj}_{W} v

is the best approximation to

v

of all the vectors in

W .

🔗

v = [v_{1} v_{2} v_{3} \dots v_{m}]^{T}

and

{proj}_{W} v = [w_{1} w_{2} w_{3} \dots w_{m}]^{T},

then the square of the error in approximating

v

{proj}_{W} v

is given by

| | v - {proj}_{W} v | |^{2} = \sum_{i = 1}^{m} (v_{i} - w_{i})^{2} .

🔗

{proj}_{W} v

minimizes this sum of squares over all vectors in

W .

As a result, we call

{proj}_{W} v

the least squares approximation to

v .

🔗

Activity 25.3.

Let $B = {[\begin{array}{r} 1 \\ 0 \\ - 1 \\ 0 \end{array}], [\begin{array}{r} 0 \\ 1 \\ 0 \\ - 1 \end{array}], [\begin{array}{r} - 1 \\ 1 \\ - 1 \\ 1 \end{array}]}$ and let $W = Span (B)$ in $R^{4} .$ Find the best approximation in $W$ to the vector $v = [\begin{array}{r} 2 \\ 3 \\ 1 \\ - 1 \end{array}]$ in $W .$

🔗

Subsection The Gram-Schmidt Process

🔗

We have seen that orthogonal bases make computations very convenient. However, until now we had no convenient way to construct orthogonal bases. The problem we address in this section is how to create an orthogonal basis from any basis.

🔗

Preview Activity 25.4.

Let $W = Span {v_{1}, v_{2}, v_{3}}$ in $R^{4},$ where $v_{1} = [1 1 1 1]^{T},$ $v_{2} = [- 1 4 4 - 1]^{T},$ and $v_{3} = [2 - 1 1 0]^{T} .$ Our goal in this preview activity is to begin to understand how we can find an orthogonal set $B = {w_{1}, w_{2}, w_{3}}$ in $R^{4}$ so that $Span B = W .$ To begin, we could start by letting $w_{1} = v_{1} .$

🔗

(a)

Now we want to find a vector in $W$ that is orthogonal to $w_{1} .$ Let $W_{1} = Span {w_{1}} .$ Explain why $w_{2} = {proj}_{⊥ W_{1}} v_{2}$ is in $W$ and is orthogonal to $w_{1} .$ Then calculate the vector $w_{2} .$

🔗

(b)

Next we need to find a third vector $w_{3}$ that is in $W$ and is orthogonal to both $w_{1}$ and $w_{2} .$ Let $W_{2} = Span {w_{1}, w_{2}} .$ Explain why $w_{3} = {proj}_{⊥ W_{2}} v_{3}$ is in $W$ and is orthogonal to both $w_{1}$ and $w_{2} .$ Then calculate the vector $w_{3} .$

🔗

(c)

Explain why the set ${w_{1}, w_{2}, w_{3}}$ is an orthogonal basis for $W .$

🔗

Preview Activity 25.4 shows the first steps of the Gram-Schmidt process to construct an orthogonal basis from any basis of a subspace in

R^{n} .

To understand why the process works in general, let

{v_{1}, v_{2}, \dots, v_{m}}

be a basis for a subspace

W

R^{n} .

Let

w_{1} = v_{1}

and let

W_{1} = Span {w_{1}} .

Since

w_{1} = v_{1}

we have that

W_{1} = Span {w_{1}} = Span {v_{1}} .

🔗

The vectors

v_{1} = w_{1}

and

v_{2}

are possibly not orthogonal, but we know the orthogonal projection of

v_{2}

onto

W_{1}^{⊥}

is orthogonal to

w_{1} .

Let

w_{2} = {proj}_{⊥ W_{1}} v_{2} = v_{2} - \frac{v_{2} \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} .

🔗

Then

{w_{1}, w_{2}}

is an orthogonal set. Note that

w_{1} = v_{1} \neq 0,

and the fact that

v_{2} \notin W_{1}

implies that

w_{2} \neq 0 .

So the set

{w_{1}, w_{2}}

is linearly independent, being a set of non-zero orthogonal vectors. Now the question is whether

Span {w_{1}, w_{2}} = Span {v_{1}, v_{2}} .

Note that

w_{2}

is a linear combination of

v_{1}

and

v_{2},

w_{2}

is in

Span {v_{1}, v_{2}} .

Since

Span {w_{1}, w_{2}}

is a 2-dimensional subspace of the 2-dimensional space

Span {v_{1}, v_{2}},

it must be true that

Span {w_{1}, w_{2}} = W_{2} = Span {v_{1}, v_{2}} .

🔗

Now we take the next step, adding

v_{3}

into the mix. The vector

w_{3} = {proj}_{⊥ W_{2}} v_{3} = v_{3} - \frac{v_{3} \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} - \frac{v_{3} \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2}

🔗

is orthogonal to both

w_{1}

and

w_{2}

and, by construction,

w_{3}

is a linear combination of

v_{1},

v_{2},

and

v_{3} .

w_{3}

is in

W_{3} = Span {v_{1}, v_{2}, v_{3}} .

The fact that

v_{3} \notin W_{2}

implies that

w_{3} \neq 0

and

{w_{1}, w_{2}, w_{3}}

is a linearly independent set. Since

Span {w_{1}, w_{2}, w_{3}}

is a 3-dimensional subspace of the 3-dimensional space

Span {v_{1}, v_{2}, v_{3}},

we conclude that

Span {w_{1}, w_{2}, w_{3}} = W_{3} = Span {v_{1}, v_{2}, v_{3}} .

🔗

We continue inductively in this same manner. If we have constructed a set

{w_{1},

w_{2},

w_{3},

\dots,

w_{k - 1}}

k - 1

orthogonal vectors such that

Span {w_{1}, w_{2}, w_{3}, \dots, w_{k - 1}} = Span {v_{1}, v_{2}, v_{3}, \dots, v_{k - 1}},

🔗

then we let

\begin{aligned} w_{k} & = {proj}_{⊥ W_{k - 1}} v_{k} \\ = v_{k} - \frac{v_{k} \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} - \frac{v_{k} \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2} - \dots - \frac{v_{k} \cdot w_{k - 1}}{w_{k - 1} \cdot w_{k - 1}} w_{k - 1}, \end{aligned}

🔗

where

W_{k - 1} = Span {w_{1}, w_{2}, w_{3}, \dots, w_{k - 1}} .

🔗

We know that

w_{k}

is orthogonal to

w_{1},

w_{2},

\dots,

w_{k - 1} .

Since

w_{1},

w_{2},

\dots,

w_{k - 1},

and

v_{k}

are all in

W_{k} = Span {v_{1}, v_{2}, \dots, v_{k}}

we see that

w_{k}

is also in

W_{k} .

Since

v_{k} \notin W_{k - 1}

implies that

w_{k} \neq 0

and

{w_{1}, w_{2}, \dots, w_{k}}

is a linearly independent set. Then

Span {w_{1}, w_{2}, w_{3}, \dots, w_{k}}

is a

k

-dimensional subspace of the

k

-dimensional space

W_{k},

so it follows that

Span {w_{1}, w_{2}, w_{3}, \dots, w_{k}} = W_{k} = Span {v_{1}, v_{2}, v_{3}, \dots, v_{k}} .

🔗

This process will end when we have an orthogonal set

{w_{1},

w_{2},

w_{3},

\dots,

w_{m}}

with

Span {w_{1},

w_{2},

w_{3},

\dots,

w_{m}}

W .

🔗

We summarize the process in the following theorem.

🔗

Theorem 25.6. The Gram-Schmidt Process.

Let ${v_{1}, v_{2}, \dots, v_{m}}$ be a basis for a subspace $W$ of $R^{n} .$ The set ${w_{1}, w_{2}, w_{3}, \dots, w_{m}}$ defined by

$w_{1} = v_{1},$
$w_{2} = v_{2} - \frac{v_{2} \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1},$
$w_{3} = v_{3} - \frac{v_{3} \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} - \frac{v_{3} \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2},$ $⋮$
$w_{m} = v_{m} - \frac{v_{m} \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} - \frac{v_{m} \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2} - \dots - \frac{v_{m} \cdot w_{m - 1}}{w_{m - 1} \cdot w_{m - 1}} w_{m - 1} .$

is an orthogonal basis for $W .$ Moreover,

Span {w_{1}, w_{2}, w_{3}, \dots, w_{k}} = Span {v_{1}, v_{2}, v_{3}, \dots, v_{k}}

for $1 \leq k \leq m .$

🔗

The Gram-Schmidt process builds an orthogonal basis

{w_{1}, w_{2}, w_{3}, \dots, w_{m}}

for us from a given basis. To make an orthonormal basis

{u_{1}, u_{2}, u_{3}, \dots, u_{m}},

all we need do is normalize each basis vector: that is, for each

i,

we let

u_{i} = \frac{w_{i}}{| | w_{i} | |} .

🔗

Activity 25.5.

Let $W = Span {[\begin{matrix} 1 \\ 1 \\ 0 \\ 0 \end{matrix}], [\begin{matrix} 0 \\ 1 \\ 1 \\ 0 \end{matrix}], [\begin{matrix} 0 \\ 0 \\ 1 \\ 1 \end{matrix}]} .$

🔗

(a)

Use the Gram-Schmidt process to find an orthogonal basis for $W .$

Hint.

Order your vectors carefully to minimize computation.

🔗

(b)

Find the projection of the vector $v = [0 1 1 1]^{T}$ onto $W .$

🔗

Subsection The QR Factorization of a Matrix

🔗

There are several different factorizations, or decompositions, of matrices where each matrix is written as a product of certain types of matrices: LU decomposition using lower and upper triangular matrices (see Section 22), EVD (EigenVector Decomposition) decomposition using eigenvectors and diagonal matrices (see Section 19), and in this section we will introduce the QR decomposition of a matrix. The QR decomposition is one of the most important tools for matrix computations. Jack Dongarra and Francis Sullivan⁴² nominated the QR decomposition as one of the “10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century.” The QR algorithm's importance stems from the fact that is a “genuinely new contribution to the field of numerical analysis and not just a refinement of ideas given by Newton, Gauss, Hadamard, or Schur.”⁴³ Most computer algebra systems (e.g., MATLAB) use a variant of the QR decomposition to compute eigenvalues. While there are other methods for approximating eigenvalues, the QR algorithm stands out. For example, the power method is useful when a matrix is large and contains a lot of zero entries (such matrices are called sparse). When most of the entries of a matrix are nonzero, the power method is not recommended. The better, more sophisticated, alternative in these situations is to use the QR decomposition. The QR factorization has applications to solving least squares problems and approximating eigenvalues of matrices.

🔗

Activity 25.6.

Let $A = [\begin{array}{cc} 1 & 0 \\ 0 & 0 \\ 0 & 2 \end{array}] .$

🔗

(a)

Find an orthonormal basis $B$ for $Col A .$ Let $Q$ be the matrix whose columns are these orthonormal basis vectors.

🔗

(b)

Write the columns of $A$ as linear combinations of the columns of $Q .$ That is, if $A = [a_{1} a_{2}],$ find $[a_{1}]_{B}$ and $[a_{2}]_{B} .$ Let $R = [[a_{1}]_{B} [a_{2}]_{B}] .$

🔗

(c)

Find the product $Q R$ and compare to $A .$

🔗

Activity 25.6 contains the main ideas to find the QR factorization of a matrix. Let

A = [a_{1} a_{2} a_{3} \dots a_{n}]

🔗

be an

m \times n

matrix with rank⁴⁴

n .

We can use the Gram-Schmidt process to find an orthonormal basis

{u_{1}, u_{2}, \dots, u_{n}}

for

Col A .

Recall also that

Span {u_{1}, u_{2}, \dots, u_{k}} = Span {a_{1}, a_{2}, \dots, a_{k}}

for any

k

between 1 and

n .

Let

Q = [u_{1} u_{2} u_{3} \dots u_{n}] .

🔗

k

is between 1 and

n,

then

a_{k}

is in

Span {u_{1}, u_{2}, \dots, u_{k}}

and

a_{k} = r_{1 k} u_{1} + r_{2 k} u_{2} + \dots + r_{k k} u_{k}

🔗

for some scalars

r_{1 k},

r_{2 k},

\dots,

r_{k k} .

Then

Q [\begin{matrix} r_{1 k} \\ r_{2 k} \\ ⋮ \\ r_{k k} \\ 0 \\ ⋮ \\ 0 \end{matrix}] = a_{k} .

🔗

If we let

r_{k} = [\begin{matrix} r_{1 k} \\ r_{2 k} \\ ⋮ \\ r_{k k} \\ 0 \\ ⋮ \\ 0 \end{matrix}]

for

k

from 1 to

n,

then

A = [Q r_{1} Q r_{2} Q r_{3} \dots Q r_{k}] .

🔗

This is the QR factorization of

A

into the product

A = Q R

🔗

where the columns of

Q

form an orthonormal basis for

Col A

and

R = [r_{1} r_{2} r_{3} \dots r_{n}] = [\begin{array}{cccccc} r_{11} & r_{12} & r_{13} & \dots & r_{1 n - 1} & r_{1 n} \\ 0 & r_{22} & r_{23} & \dots & r_{2 n - 1} & r_{2 n} \\ 0 & 0 & r_{33} & \dots & r_{3 n - 1} & r_{3 n} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & \dots & 0 & r_{n n} \end{array}]

🔗

is an upper triangular matrix. Note that

Q

is an

m \times n

matrix and

R = [r_{i j}]

is an

n \times n

matrix with

r_{i i} \neq 0

for each

i .

🔗

Activity 25.7.

The set ${u_{1}, u_{2}},$ where $u_{1} = [1 1 1 1]^{T}$ and $u_{2} = [1 - 1 1 - 1]^{T}$ is an orthogonal basis for the column space of a $4 \times 2$ matrix $A = [a_{1} a_{2}] .$ Moreover, $a_{1} = 2 u_{1}$ and $a_{2} = 3 u_{2} + 4 u_{2} .$ What is $A ?$

🔗

The QR factorization provides a widely used algorithm (the QR algorithm) for approximating all of the eigenvalues of a matrix. The computer system MATLAB utilizes four versions of the QR algorithm to approximate the eigenvalues of real symmetric matrices, eigenvalues of real nonsymmetric matrices, eigenvalues of pairs of complex matrices, and singular values of general matrices.

🔗

The algorithm works as follows.

Start with an $n \times n$ matrix $A .$ Let $A_{1} = A .$
Find the QR factorization for $A_{1}$ and write it as $A_{1} = Q_{1} R_{1},$ where $Q_{1}$ is orthogonal and $R_{1}$ is upper triangular.
Let $A_{2} = Q_{1}^{- 1} A_{1} Q_{1} = Q_{1}^{T} A Q_{1} = R_{1} Q_{1} .$ Find the QR factorization of $A_{2}$ and write it as $A_{2} = Q_{2} R_{2} .$
Let $A_{3} = Q_{2}^{- 1} A_{2} Q_{2} = Q_{2}^{T} A Q_{2} = R_{2} Q_{2} .$ Find the QR factorization of $A_{3}$ and write it as $A_{3} = Q_{3} R_{3} .$
Continue in this manner to obtain a sequence ${A_{k}}$ where $A_{k} = Q_{k} R_{k}$ and $A_{k + 1} = R_{k} Q_{k} .$

🔗

Note that

A_{k + 1} = Q_{k}^{- 1} A_{k} Q_{k}

and so all of the matrices

A_{k}

are similar to each other and therefore all have the same eigenvalues. We won't go into the details, but it can be shown that if the eigenvalues of

A

are real and have distinct absolute values, then the sequence

{A_{i}}

converges to an upper triangular matrix with the eigenvalues of

A

as the diagonal entries. If some of the eigenvalues of

A

are complex, then the sequence

{A_{i}}

converges to a block upper triangular matrix, where the diagonal blocks are either

1 \times 1

(approximating the real eigenvalues of

A

) or

2 \times 2

(which provide a pair of conjugate complex eigenvalues of

A

🔗

Subsection Examples

🔗

What follows are worked examples that use the concepts from this section.

🔗

Example 25.7.

Let $W$ be the subspace of $R^{4}$ spanned by $w_{1} = [1 0 0 0]^{T},$ $w_{2} = [1 1 1 0]^{T},$ and $w_{3} = [1 2 0 1]^{T} .$

🔗

(a)

Use the Gram-Schmidt process to find an orthonormal basis for the subspace $W$ of $R^{4}$ spanned by $w_{1} = [1 0 0 0]^{T},$ $w_{2} = [1 1 1 0]^{T},$ and $w_{3} = [1 2 0 1]^{T} .$

Solution.

First note that $w_{1},$ $w_{2},$ and $w_{3}$ are linearly independent. We let $v_{1} = w_{1}$ and the Gram-Schmidt process gives us

\begin{aligned} v_{2} & = w_{2} - \frac{w_{2} \cdot v_{1}}{v_{1} \cdot v_{1}} v_{1} \\ = [1 1 1 0]^{T} - \frac{1}{1} [1 0 0 0]^{T} \\ = [0 1 1 0]^{T} \end{aligned}

and

\begin{aligned} v_{3} & = w_{3} - \frac{w_{3} \cdot v_{1}}{v_{1} \cdot v_{1}} v_{1} - \frac{w_{3} \cdot v_{2}}{v_{2} \cdot v_{2}} v_{2} \\ = [1 2 0 1]^{T} - \frac{1}{1} [1 0 0 0]^{T} - \frac{2}{2} [0 1 1 0]^{T} \\ = [0 1 - 1 1]^{T} . \end{aligned}

So ${v_{1}, v_{2}, v_{3}}$ is an orthogonal basis for $W .$ An orthonormal basis is found by dividing each vector by its magnitude, so

{[1 0 0 0]^{T}, \frac{1}{\sqrt{2}} [0 1 1 0]^{T}, \frac{1}{\sqrt{3}} [0 1 - 1 1]^{T}}

is an orthonormal basis for $W .$

🔗

(b)

Find a QR factorization of the matrix $A = [\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & 1 & 2 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{array}] .$

Solution.

Technology shows that the reduced row echelon form of $A$ is $I_{4},$ so the columns of $A$ are linearly independent and $A$ has rank $4 .$ From part (a) we have an orthogonal basis for the span of the first three columns of $A .$ To find a fourth vector to add so that the span is $Col A,$ we apply the Gram-Schmidt process one more time with $w_{4} = [0 0 0 1]^{T} :$

\begin{aligned} v_{4} & = w_{4} - \frac{w_{4} \cdot v_{1}}{v_{1} \cdot v_{1}} v_{1} - \frac{w_{4} \cdot v_{2}}{v_{2} \cdot v_{2}} v_{2} - \frac{w_{4} \cdot v_{3}}{v_{3} \cdot v_{3}} v_{3} \\ = [0 0 0 1]^{T} - \frac{0}{1} [1 0 0 0]^{T} - \frac{0}{2} [0 1 1 0]^{T} - \frac{1}{3} [0 1 - 1 1]^{T} \\ = \frac{1}{3} [0 - 1 1 2]^{T} . \end{aligned}

So ${u_{1}, u_{2}, u_{3}, u_{4}}$ is an orthonormal basis for $Col A,$ where

\begin{array}{ccc} u_{1} = [1 0 0 0]^{T} & u_{2} = \frac{\sqrt{2}}{2} [0 1 1 0]^{T} \\ u_{3} = \frac{\sqrt{3}}{3} [0 1 - 1 1]^{T} & u_{4} = \frac{\sqrt{6}}{6} [0 - 1 1 2]^{T} . \end{array}

This makes

Q = [\begin{array}{ccrr} 1 & 0 & 0 & 0 \\ 0 & \frac{\sqrt{2}}{2} & \frac{\sqrt{3}}{3} & - \frac{\sqrt{6}}{6} \\ 0 & \frac{\sqrt{2}}{2} & - \frac{\sqrt{3}}{3} & \frac{\sqrt{6}}{6} \\ 0 & 0 & \frac{\sqrt{3}}{3} & \frac{\sqrt{6}}{3} \end{array}] .

To find the matrix $R,$ we write the columns of $A$ in terms of the basis vectors $u_{1},$ $u_{2},$ $u_{3},$ and $u_{4} .$ Technology shows that the reduced row echelon form of $[Q | A]$ is

[\begin{array}{cccccccc} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & \sqrt{2} & \sqrt{2} & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & \sqrt{3} & \frac{\sqrt{3}}{3} \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & \frac{\sqrt{6}}{3} \end{array}] .

R = [\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & \sqrt{2} & \sqrt{2} & 0 \\ 0 & 0 & \sqrt{3} & \frac{\sqrt{3}}{3} \\ 0 & 0 & 0 & \frac{\sqrt{6}}{3} \end{array}] .

🔗

Example 25.8.

Let $W = Span {[1 0 1 0]^{T}, [0 0 1 - 1]^{T}, [1 0 - 1 0]^{T}} .$ Find the vector in $W$ that is closest to the vector $[1 1 1 1]^{T} .$ Provide a numeric measure of the error in approximating $[1 1 1 1]^{T}$ by this vector.

Solution.

Our job is to find ${proj}_{W} [1 1 1 1]^{T} .$ To do this, we need an orthogonal basis of $W .$ Let $v_{1} = [1 0 1 0]^{T},$ $v_{2} = [0 0 1 - 1]^{T},$ and $v_{3} = [1 0 - 1 0]^{T} .$ Technology shows that each column of the matrix $[v_{1} v_{2} v_{3}]$ is a pivot column, so the set ${v_{1}, v_{2}, v_{3}}$ is a basis for $W .$ We apply the Gram-Schmidt process to this basis to obtain an orthogonal basis ${w_{1}, w_{2}, w_{3}}$ of $W .$ We start with $w_{1} = v_{1},$ then

\begin{aligned} w_{2} & = v_{2} - \frac{v_{2} \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} \\ = [0 0 1 - 1]^{T} - \frac{1}{2} [1 0 1 0]^{T} \\ = \frac{1}{2} [- 1 0 1 - 2]^{T} \end{aligned}

and

\begin{aligned} w_{3} & = v_{3} - \frac{v_{3} \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} - \frac{v_{3} \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2} \\ = [1 0 - 1 0]^{T} - \frac{0}{2} [1 0 1 0]^{T} + \frac{2}{3} (\frac{1}{2} [- 1 0 1 - 2]^{T}) \\ = \frac{1}{3} [2 0 - 2 - 2]^{T} . \end{aligned}

Then, letting $z = [1 1 1 1]^{T}$ we have

\begin{aligned} {proj}_{W} z & = \frac{z \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} + \frac{z \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2} + \frac{z \cdot w_{3}}{w_{3} \cdot w_{3}} w_{3} \\ = \frac{2}{2} [1 0 1 0]^{T} + \frac{- 1}{3 / 2} \frac{1}{2} [- 1 0 1 - 2]^{T} + \frac{- 2 / 3}{4 / 3} \frac{1}{3} [2 0 - 2 - 2]^{T} \\ = [1 0 1 0]^{T} - \frac{1}{3} [- 1 0 1 - 2]^{T} - \frac{1}{6} [2 0 - 2 - 2]^{T} \\ = [1 0 1 1]^{T} . \end{aligned}

The norm of ${proj}_{W^{⊥}} z = z - {proj}_{W} z$ tells us how well our projection $[1 0 1 1]^{T}$ approximates $z = [1 1 1 1]^{T} .$ Now

| | {proj}_{W^{⊥}} z | | = | | [1 1 1 1]^{T} - [1 0 1 1]^{T} | | = | | [0 1 0 0]^{T} | | = 1,

so $[1 0 1 1]^{T}$ is one unit away from $z = [1 1 1 1]^{T} .$

🔗

Subsection Summary

The projection of the vector $v$ in $V$ onto $W$ is the vector

${proj}_{W} v = \frac{v \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} + \frac{v \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2} + \dots + \frac{v \cdot w_{m}}{w_{m} \cdot w_{m}} w_{m},$

where $W$ is the a subspace of $R^{n}$ with orthogonal basis ${w_{1}, w_{2}, \dots, w_{m}} .$ These projections are important in that ${proj}_{W} v$ is the best approximation of the vector $v$ by a vector in $W$ in the least squares sense.
With $W$ as in (a), the projection of $v$ orthogonal to $W$ is the vector

${proj}_{⊥ W} v = v - {proj}_{W} v .$

The norm of ${proj}_{⊥ W} v$ provides a measure of how well ${proj}_{W} v$ approximates the vector $v .$
The Gram-Schmidt process produces an orthogonal basis from any basis. It works as follows. Let ${v_{1}, v_{2}, \dots, v_{m}}$ be a basis for a subspace $W$ of $R^{n} .$ The set ${w_{1},$ $w_{2},$ $w_{3},$ $\dots,$ $w_{m}}$ defined by
- $w_{1} = v_{1},$
- $w_{2} = v_{2} - \frac{v_{2} \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1},$
- $w_{3} = v_{3} - \frac{v_{3} \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} - \frac{v_{3} \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2},$ $⋮$
- $w_{m} = v_{m} - \frac{v_{m} \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} - \frac{v_{m} \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2} - \dots - \frac{v_{m} \cdot w_{m - 1}}{w_{m - 1} \cdot w_{m - 1}} w_{m - 1} .$
is an orthogonal basis for $W .$ Moreover,

$Span {w_{1}, w_{2}, w_{3}, \dots, w_{k}} = Span {v_{1}, v_{2}, v_{3}, \dots, v_{k}}$

for each $k$ between 1 and $m .$
The QR factorization has applications to solving least squares problems and approximating eigenvalues of matrices. The QR factorization writes an $m \times n$ matrix with rank $n$ as a product $A = Q R,$ where the columns of $Q$ form an orthonormal basis for $Col A$ and

$R = [r_{1} | r_{2} | r_{3} | \dots | r_{n}] = [\begin{array}{cccccc} r_{11} & r_{12} & r_{13} & \dots & r_{1 n - 1} & r_{1 n} \\ 0 & r_{22} & r_{23} & \dots & r_{2 n - 1} & r_{2 n} \\ 0 & 0 & r_{33} & \dots & r_{3 n - 1} & r_{3 n} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & \dots & 0 & r_{n n} \end{array}]$

is an upper triangular matrix.

🔗

Exercises Exercises

🔗

1.

Let $W = Span {w_{1}, w_{2}}$ in $R^{3},$ with $w_{1} = [1 2 1]^{T}$ and $w_{2} = [1 - 1 1]^{T},$ and $v = [1 0 0]^{T} .$

🔗

(a)

Find ${proj}_{W} v$ and ${proj}_{⊥ W} v$

🔗

(b)

Find the vector in $W$ that is closest to $v .$ How close is this vector to $v ?$

🔗

2.

🔗

3.

In this exercise we determine the least-squares line (the line of best fit in the least squares sense) to a set of $k$ data points $(x_{1}, y_{1}),$ $(x_{2}, y_{2}),$ $\dots,$ $(x_{k}, y_{k})$ in the plane. In this case, we want to fit a line of the form $f (x) = m x + b$ to the data. If the data were to lie on a line, then we would have a solution to the system

\begin{aligned} m x_{1} + b & = y_{1} \\ m x_{2} + b & = y_{2} \\ ⋮ \\ m x_{k} + b & = y_{k} \end{aligned}

This system can be written as

m w_{1} + b w_{2} = y,

where $w_{1} = [x_{1} x_{2} \dots x_{k}]^{T},$ $w_{2} = [1 1 \dots 1]^{T},$ and $y = [y_{1} y_{2} \dots y_{k}]^{T} .$ If the data does not lie on a line, then the system won't have a solution. Instead, we want to minimize the square of the distance between $y$ and a vector of the form $m w_{1} + b w_{2} .$ That is, minimize

\begin{matrix} (25.1) & | | y - (m w_{1} + b w_{2}) | |^{2} . \end{matrix}

Rephrasing this in terms of projections, we are looking for the vector in $W = Span {w_{1}, w_{2}}$ that is closest to $y .$ In other words, the values of $m$ and $b$ will occur as the weights when we write ${proj}_{W} y$ as a linear combination of $w_{1}$ and $w_{2} .$ The one wrinkle in this problem is that we need an orthogonal basis for $W$ to find this projection. Find the least squares line for the data points $(1, 2),$ $(2, 4)$ and $(3, 5)$ in $R^{2} .$

🔗

4.

Each set $S$ is linearly independent. Use the Gram-Schmidt process to create an orthogonal set of vectors with the same span as $S .$ Then find an orthonormal basis for the same span.

🔗

(a)

$S = {[1 1 1]^{T}, [5 - 1 2]^{T}}$ in $R^{3}$

🔗

(b)

$S = {[1 0 2]^{T}, [- 1 1 1]^{T}, [1 1 19]^{T}}$ in $R^{3}$

🔗

(c)

$S = {[1 0 1 0 1 0 1]^{T}, [- 1 2 3 0 1 0 1]^{T}, [1 0 4 - 1 2 0 1]^{T}, [1 1 1 1 1 1 1]^{T}}$ in $R^{7}$

🔗

5.

Let $S = {v_{1}, v_{2}, v_{3}}$ be a set of linearly dependent vectors in $R^{n}$ for some integer $n \geq 3 .$ What is the result if the Gram-Schmidt process is applied to the set $S ?$ Explain.

🔗

6.

A fellow student wants to find a QR factorization for a $3 \times 4$ matrix. What would you tell this student and why?

🔗

7.

Find the QR factorizations of the given matrices.

🔗

(a)

$[\begin{array}{ccc} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{array}]$

🔗

(b)

$[\begin{array}{cc} 1 & 2 \\ 1 & 3 \\ 1 & 2 \\ 1 & 3 \end{array}]$

🔗

(c)

$[\begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 3 & 0 & 4 \\ 0 & 0 & 5 \end{array}] .$

🔗

8.

Find an orthonormal basis ${u_{1}, u_{2}, u_{3}}$ of $R^{3}$ such that $Span {u_{1}, u_{2}} = Span {[1 2 3]^{T}, [1 1 0]^{T}} .$

🔗

9.

🔗

(a)

Let $A = [\begin{array}{cc} 2 & 1 \\ 2 & 6 \\ 2 & 6 \\ 2 & 1 \end{array}] = [a_{1} a_{2}] .$ A QR factorization of $A$ has $Q = [u_{1} u_{2}]$ with $u_{1} = \frac{1}{2} [1 1 1 1]^{T}$ and $u_{2} = \frac{1}{2} [- 1 1 1 - 1]^{T},$ and $u_{3} = \frac{1}{\sqrt{12}} [1 - 1 - 1 3]^{T}$ and $R = [r_{i j}] = [\begin{array}{cc} 4 & 7 \\ 0 & 5 \end{array}] .$ Calculate the dot products $a_{i} \cdot u_{j}$ for $i$ and $j$ between $1$ and $2 .$ How are these dot products connected to the entries of $R ?$

🔗

(b)

Explain why the result of part (a) is true in general. That is, if $A = [a_{1} a_{2} \dots a_{n}]$ has QR factorization with $Q = [u_{1} u_{2} \dots u_{n}]$ and $R = [r_{i j}],$ then $r_{i j} = a_{j} \cdot u_{i} .$

🔗

10.

Upper triangular matrices play an important role in the QR decomposition. In this exercise we examine two properties of upper triangular matrices.

🔗

(a)

Show that if $R$ and $S$ are upper triangular $n \times n$ matrices with positive diagonal entries, then $R S$ is also an upper triangular $n \times n$ matrices with positive diagonal entries.

🔗

(b)

Show that if $R$ is an invertible upper triangular matrix with positive diagonal entries, then $R^{- 1}$ is also an upper triangular matrix with positive diagonal entries.

🔗

11.

In this exercise we demonstrate that the QR decomposition of an $m \times n$ matrix with linearly independent columns is unique.

🔗

(a)

Suppose that $A = Q R,$ where $Q$ is an $m \times n$ matrix with orthogonal columns and $R$ is an $n \times n$ upper triangular matrix. Show that $R$ is invertible.

Hint.

What can we say about $x$ if $R x = 0 ?$

🔗

(b)

Show that the only $n \times n$ orthogonal upper triangular matrix with positive diagonal entries is the identity matrix $I_{n} .$

Hint.

Let $A = [a_{1} a_{2} \dots a_{n}] = [a_{i j}]$ be an $n \times n$ orthogonal upper triangular matrices with positive diagonal entries. What does that tell us about $a_{i} \cdot a_{j} ?$

🔗

(c)

Show that if $Q_{1}$ and $Q_{2}$ are $m \times n$ matrices with orthogonal columns, and $S$ is a matrix such that $Q_{1} = Q_{2} S,$ then $S$ is an orthogonal matrix.

Hint.

Write $Q_{1}^{T} Q_{1}$ in terms of $Q_{2}$ and $S .$

🔗

(d)

Suppose that $Q_{1}$ and $Q_{2}$ are $m \times n$ matrices with orthogonal columns and $R_{1}$ and $R_{2}$ are $n \times n$ upper triangular matrices such that

A = Q_{1} R_{1} = Q_{2} R_{2} .

Show that $Q_{1} = Q_{2}$ and $R_{1} = R_{2} .$ Conclude that the QR factorization of a matrix is unique.

Hint.

Use the previous parts of this problem along with the results of Exercise 10.

🔗

12.

Label each of the following statements as True or False. Provide justification for your response. Throughout, let $V$ be a vector space.

🔗

(a) True/False.

If ${w_{1}, w_{2}}$ is a basis for a subspace $W$ of $R^{3},$ then the vector $\frac{v \cdot w_{1}}{w_{1} \cdot w_{1}} w_{1} + \frac{v \cdot w_{2}}{w_{2} \cdot w_{2}} w_{2}$ is the vector in $W$ closest to $v .$

🔗

(b) True/False.

If $W$ is a subspace of $R^{n},$ then the vector $v - {proj}_{W} v$ is orthogonal to every vector in $W .$

🔗

(c) True/False.

If $u_{1},$ $u_{2},$ $u_{3}$ are vectors in $R^{n},$ then the Gram-Schmidt process constructs an orthogonal set of vectors ${v_{1}, v_{2}, v_{3}}$ with the same span as ${u_{1}, u_{2}, u_{3}} .$

🔗

(d) True/False.

Any set ${u_{1}, u_{2}, \dots, u_{k}}$ of orthogonal vectors in $R^{n}$ can be extended to an orthogonal basis of $V .$

🔗

(e) True/False.

If $A$ is an $n \times n$ matrix with $A A^{T} = I_{n},$ then the rows of $A$ form an orthogonal set.

🔗

(f) True/False.

Every nontrivial subspace of $R^{n}$ has an orthogonal basis.

🔗

(g) True/False.

If $W$ is a subspace of $R^{n}$ satisfying $W^{⊥} = {0},$ then $W = R^{n} .$

🔗

Subsection Project: MIMO Systems and Householder Transformations

🔗

In a simplified model, a MIMO system will have

k

transmitting antennas and

m

receiving antennas. We record a transmitted symbol in a vector

x = [x_{1} x_{2} \dots x_{k}]^{T}

(one

x_{i}

for each transmitting antenna) and the received symbol as a vector

y = [y_{1} y_{2} \dots y_{m}]^{T}

(one

y_{j}

for each received symbol).

🔗

Between each transmit antenna and each receiver antenna is a fading channel. The MIMO system is the collection of fading channels. If we let

h_{i j}

be the fading between the

j

th transmitter and

i

th receiver, then we can represent this multipath fading as an

m \times k

matrix

H = [h_{i j}] .

We assume that there is also some noise in the received signal that we represent by

n_{j}

(for the

j

th receiving antenna). Our MIMO system is then represented as the matrix-vector equation

y = H x + n,

🔗

where

n = [n_{1} n_{2} \dots n_{m}]^{T} .

The goal is to reproduce the original signal

x

from the received signal

y .

This is where the QR decomposition comes into play.

🔗

Project Activity 25.8.

To see why and how the QR decomposition is used in MIMO systems, we begin with an example. Assume that we have two transmitters and three receivers, and suppose $H = [\begin{array}{cc} 2 & 1 \\ 2 & 1 \\ 1 & 5 \end{array}] .$ From this point, to simplify the situation we assume that noise is negligible and consider the system $y = H x .$ Assume that the received signal is $y = [\begin{matrix} 2 \\ 1 \\ 4 \end{matrix}] .$

🔗

(a)

Show that the system $H x = y$ is inconsistent.

🔗

(b)

When we receive a signal, we need to interpret it, and that is difficult if we cannot find a solution. One reason that the system might not have a solution is that the elements in $x$ have to come from a specified alphabet, and so we are looking for solutions that are in that alphabet, and there may be no direct solution in that alphabet. As a result, we generally have to find a “best” solution in the alphabet space. That can be done with the QR decomposition. Assume that $H$ has a QR decomposition $H = Q R$ with $Q$ having orthonormal columns and $R$ a diagonal matrix. Explain how the equation $y = H x$ can be transformed into

\begin{matrix} (25.2) & Q^{T} y = R x . \end{matrix}

🔗

(c)

Return to our example of $H = [\begin{array}{cc} 2 & 1 \\ 2 & 1 \\ 1 & 5 \end{array}] .$ Assume that

H = Q R = [\begin{array}{cr} \frac{2}{3} & - \frac{\sqrt{2}}{6} \\ \frac{2}{3} & - \frac{\sqrt{2}}{6} \\ \frac{1}{3} & \frac{2 \sqrt{2}}{3} \end{array}] [\begin{array}{cc} 3 & 3 \\ 0 & 3 \sqrt{2} \end{array}] .

Use (25.2) to find $x$ if $y = [\begin{matrix} 2 \\ 1 \\ 4 \end{matrix}] .$

🔗

In Project Activity 25.8 we saw that a QR decomposition allows us to replace the system

y = H x

with an upper triangular system

Q^{T} y = R x

that has a solution. This solution is what is called a least squares solution (which we will discuss in more detail in a later section). The key to all of this is finding an efficient way to calculate a QR decomposition. This is the focus of the remainder of this project.

🔗

Subsection Householder Transformations and the QR Decomposition

🔗

There are three main ways to compute a QR decomposition.

The method discussed in this section uses Gram-Schmidt orthogonalization. This method is not recommended for numerical use as it is inherently numerically unstable. Under certain circumstances, cancellation can destroy the accuracy of the computed vectors and the resulting vectors may not be orthogonal.
The method that we will discuss in this project using Householder transformations (developed by Alston S. Householder). In Gaussian elimination, we can zero out entries below the diagonal by multiplying by elementary matrices to perform row operations. Householder transformations do something similar, allowing us to replace columns with columns of mostly zeros, which then allow for more efficient computations.
Givens (or Jacobi) rotations (used by W. Givens and originally invented by Jacobi for use with in solving the symmetric eigenvalue problem) is another method that allows us to selectively produce zeros into a matrix. We will focus on Householder transformations in this project.

🔗

The first step in a QR decomposition using Householder matrices is to create a matrix that is upper triangular. To get to this form, we use a Householder transformation. A Householder transformation (or matrix) is a matrix of the form

H = I - 2 \frac{v v^{T}}{| | v | |^{2}},

🔗

where

v

is a vector in

R^{n}

and

I

is the

n \times n

identity matrix.

🔗

Project Activity 25.9.

We will discover some properties of Householder transformations in this activity.

🔗

(a)

Let $x$ be any vector and let $y$ be a unit vector. In this part of the exercise we show that, with a suitable choice of $v,$ the Householder transformation $H$ transforms $x$ into a vector of the same length parallel to $y .$ That is,

H x = - σ y

for some scalar $σ .$ A similar argument shows that $H (x - σ y) = σ y .$ Letting $y = e_{1}$ gives us the following result.

🔗

Lemma 25.9.

Let $x$ be any vector, let $σ = | | x | |,$ and let $v = x \pm σ e_{1} .$ Then $H x = \mp σ e_{1} .$

Hint.

Let $σ = | | x | |,$ and let $v = x + σ y .$ Apply $H$ to $x,$ factor out $x + σ y,$ and ultimately show that $H x = - σ y .$

🔗

(b)

The Householder matrix $H$ has two other important properties. Show that $H$ is symmetric and orthogonal.

🔗

There are many advantages to using Householder matrices. One is that instead of having to store all entries of the matrix

H = I - 2 \frac{v v^{T}}{| | v | |^{2}},

all we need to store is the entries of

v .

Another advantage of Householder transformations is that they can be used to efficiently calculate QR decompositions. The next project activity shows how to use Lemma 25.9 and Householder transformations to compute a QR decomposition through an example.

🔗

Project Activity 25.10.

Assume that we have five receiving antennas and three transmitting antennas, and that

A = [\begin{array}{crc} 1.0 & 0.0 & 1.0 \\ 7.0 & 7.0 & 8.0 \\ 1.0 & 2.0 & 1.0 \\ 7.0 & 7.0 & 6.0 \\ 0.0 & - 1.0 & 0.0 \end{array}] .

(We use $A$ now instead of $H$ so as to avoid confusion with Householder matrices.) The calculations in this activity can get rather messy, so use appropriate technology and round entries to four decimal places to the right of the decimal.

🔗

(a)

Let $x_{1}$ be the first column of $A .$ Identify an appropriate Householder transformation $H_{1}$ so that $H_{1} x$ is a constant multiple of $[1 0 0 0 0]^{T} .$ Determine the matrix $A_{1},$ where $A_{1} = H_{1} A .$ (Special note: when deciding which of $x \pm σ e_{1}$ to use to create $H,$ it is best to use the one whose sign is the same as $x_{1}$ (the first entry of $x$ ). We won't go into the details, but this helps prevent problems due to cancellation,)

🔗

(b)

Next we consider just the bottom right $4 \times 2$ portion ${\hat{A}}_{2}$ of the matrix $A_{1}$ found in part (a).

🔗

(i)

Repeat the process on ${\hat{A}}_{2}$ to find a Householder matrix ${\hat{H}}_{2}$ that will make the first column of ${\hat{A}}_{2}$ have all zeros below its first entry.

🔗

(ii)

Let

H_{2} = [\begin{array}{cc} I_{1} & 0 \\ 0 & {\hat{H}}_{2} \end{array}] .

Explain what the matrix $A_{2} = H_{2} H_{1} A$ is.

🔗

(c)

As a final step, we consider just the bottom right $3 \times 1$ portion ${\hat{A}}_{3}$ of the matrix $A_{2}$ and repeat the process.

🔗

(i)

Find a matrix ${\hat{H}}_{3}$ that produces zeros below the first entry.

🔗

(ii)

Let

H_{3} = [\begin{array}{cc} I_{2} & 0 \\ 0 & {\hat{H}}_{3} \end{array}] .

What matrix is $H_{3} H_{2} H_{1} A ?$ Why?

🔗

(d)

Explain why $Q = H_{1} H_{2} H_{3}$ is an orthogonal matrix. Then find an upper triangular matrix $R$ such that $A = Q R .$

🔗

Project Activity 25.10 illustrates the general method for finding a QR decomposition of a matrix

A

by using Householder transformations to reduce

A

to an upper triangular matrix

R .

The product of the Householder matrices is then the orthogonal matrix

Q .

One final note: You may have noticed that the matrix

Q

you found in this project was a square

5 \times 5

matrix and

R

was a

5 \times 3

matrix, and so they have different sizes than the QR decomposition in this section. We could use the Gram-Schmidt process to obtain these larger matrices by extending the columns of a

5 \times 3

matrix

Q

to form an orthonormal basis for

R^{5} .

However, if we want a QR decomposition for

A

in which

Q

5 \times 3

and

R

3 \times 3

from the work we did in Project Activity 25.10, we can simply delete the last two columns of the matrix

Q

and the last two rows of the matrix

R

we calculated. This smaller QR decomposition is often referred to as a thin QR decomposition.

Jack Dongarra and Francis Sullivan. Introduction to the top 10 algorithms. Computing in Science and Engineering, 2: 22-23, 2000.

[3] Beresford N. Parlett. The QR algorithm. Computing in Science and Engineering, 2:38-42, 2000.

Recall that the rank of a matrix

A

is the dimension of the column space of

A .

Section 25 Projections onto Subspaces and the Gram-Schmidt Process in Rn

Focus Questions

Subsection Application: MIMO Systems

Subsection Introduction

Preview Activity 25.1.

(a)

(b)

(c)

(d)

(e)

(f)

Subsection Projections onto Subspaces and Orthogonal Projections

Definition 25.3.

Activity 25.2.

Subsection Best Approximations

Theorem 25.4.

Proof.

Activity 25.3.

Subsection The Gram-Schmidt Process

Preview Activity 25.4.

(a)

(b)

(c)

Theorem 25.6. The Gram-Schmidt Process.

Activity 25.5.

(a)

(b)

Subsection The QR Factorization of a Matrix

Activity 25.6.

(a)

(b)

(c)

Activity 25.7.

Subsection Examples

Example 25.7.

(a)

Solution.

(b)

Solution.

Example 25.8.

Solution.

Subsection Summary

Exercises Exercises

1.

(a)

(b)

2.

3.

4.

(a)

(b)

(c)

5.

6.

7.

(a)

(b)

(c)

8.

9.

(a)

(b)

10.

(a)

(b)

11.

(a)

(b)

(c)

(d)

12.

(a) True/False.

(b) True/False.

(c) True/False.

(d) True/False.

(e) True/False.

(f) True/False.

(g) True/False.

Subsection Project: MIMO Systems and Householder Transformations

Project Activity 25.8.

Section 25 Projections onto Subspaces and the Gram-Schmidt Process in $R^{n}$