An Inquiry-Based Introduction to Linear Algebra and Applications

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 \(\vw\) in a subspace \(W\) of \(\R^n\) that is the “best” approximation to a vector \(\vv\) not in the subspace. A natural measure of “best” is to find a vector \(\vw\)in \(W\) if one exists, such that the distance from \(\vw\) to \(\vu\) is a minimum. This means we want to find \(\vw\) so that the quantity

is as small as possible over all vectors \(\vw\) in \(W\) To do this, we will need to find a suitable projection of the vector \(\vv\) onto the subspace \(W\) We have already done this in the case that \(W = \Span\{\vw_1\}\) is the span of a single vector -- we can project the vector \(\vv\) in the direction of \(\vw_1\text{.}\) Our goal is to generalize this to project a vector \(\vv\) onto an entire subspace in a useful way.

Preview Activity 25.1.

Let \(\CB = \{\vw_1, \vw_2\}\) be a basis for a subspace \(W\) of \(\R^3\) where \(\vw_1 = [1 \ 0 \ 0]^{\tr}\) and \(\vw_2 = [0 \ 1 \ 0]^{\tr}\) Note that \(\CB\) is an orthonormal basis for \(W\) Let \(\vv = [1 \ 2 \ 1]^{\tr}\) Note that \(W\) is the \(xy\)plane and that \(\vv\) is not in \(W\) as illustrated in Figure 25.2.

(a)

Find the projection \(\vu_1\)of \(\vv\)onto \(W_1 = \Span\{\vw_1\}\)

Hint.

See Equation (23.2).

(b)

Find the projection \(\vu_2\)of \(\vv\)onto \(W_2 = \Span\{\vw_2\}\)

(c)

Calculate the distance between \(\vv\)and \(\vu_1\)and \(\vv\)and \(\vu_2\) Which of \(\vu_1\)and \(\vu_2\)is closer to \(\vv\text{?}\)

(d)

Show that the vector \(\frac{3}{4} [1 \ 2 \ 0]^{\tr}\)is in \(W\)and find the distance between \(\vv\)and \(\frac{3}{4} [1 \ 2 \ 0]^{\tr}\)

(e)

Part (4) shows that neither vector \(\vu_1 = \proj_{\vw_1} \vv\)nor \(\vu_2 = \proj_{\vw_2} \vv\)is the vector in \(W\)that is closest to \(\vv\) 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 \(\vu_3 = \vu_1+\vu_2\) Calculate the components of this vector \(\vu_3\)and determine the distance between \(\vu_3\)and \(\vv\) Which of the three vectors \(\vu_1\) \(\vu_2\) and \(\vu_3\)in \(W\)is closest to \(\vv\text{?}\)

(f)

A picture of \(\vw_1\) \(\vw_2\) \(W\) and \(\vv\)is shown in Figure 25.2. Draw in \(\vu_1\) \(\vu_2\) and \(\vu_3\) Draw a picture of the vector \(\vw\)in \(W\)that appears to be closest to \(\vv\) Does this vector seem to have any relationship to \(\vu_1\) \(\vu_2\) or \(\vu_3\text{?}\) 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 \(\vv\) in \(\R^n\) onto a subspace \(W\) of \(\R^n\text{.}\) If we have an orthogonal basis for \(W\text{,}\) we can just add the projections of \(\vv\) onto each basis vector. The resulting vector is called the projection of \(\vv\) onto the subspace \(W\text{.}\) As we did with projections onto vectors, we can also define the projection of \(\vv\) orthogonal to \(W\text{.}\) Note that to make this all work out properly, we will see that we need an orthogonal basis for \(W\text{.}\)

The notation \(\proj_{\perp W} \vv\) indicates that we expect this vector to be orthogonal to every vector in \(W\text{.}\) We address this in the following activity.

Activity 25.2 indicates that the vector \(\proj_{\perp W} \vv\) is in fact orthogonal to every vector in \(W\text{.}\) To see that this is true in general, let \(\CB = \{\vw_1, \vw_2, \ldots, \vw_m\}\) be an orthogonal basis for a subspace \(W\) of \(\R^n\) and let \(\vv\) be a vector in \(\R^n\text{.}\) Let

Then \(\vv - \vw\) is the projection of \(\vv\) orthogonal to \(W\text{.}\) We will show that \(\vv - \vw\) is orthogonal to every basis vector for \(W\text{.}\) Since \(\CB\) is an orthogonal basis for \(W\text{,}\) we know that \(\vw_i \cdot \vw_j = 0\) for \(i \neq j\text{.}\) So if \(k\) is between 1 and \(m\) then

So the vector \(\vv - \vw\) is orthogonal to every basis vector for \(W\text{,}\) and therefore to every vector in \(W\) (Theorem 23.16). Because \(\CB\) is a basis for \(W\text{,}\) if \(\vx\) is in \(W\text{,}\) then

for some scalars \(c_1\text{,}\) \(c_2\text{,}\) \(\ldots\text{,}\) \(c_m\text{.}\) So

and so \(\vv - \vw\) is orthogonal to every vector in \(W\text{.}\)

Subsection Best Approximations

We have seen that \(\proj_{\perp W} \vv\) is orthogonal to every vector in \(W\text{,}\) which suggests that \(\proj_W \vv\) is in fact the vector in \(W\) that is closest to \(\vv\text{.}\) We now verify this fact and conclude that \(\proj_W \vv\) is the vector in \(W\) closest to \(\vv\) and therefore the best approximation of \(\vv\) by a vector in \(W\text{.}\)

Proof.

Let \(\B = \{\vw_1, \vw_2, \ldots, \vw_m\}\) be an orthogonal basis for a subspace \(W\) of \(\R^n\) and let \(\vv\) be a vector in \(\R^n\text{.}\) Let \(\vx\) be a vector in \(W\text{.}\) The vector \(\proj_W \vv - \vx\) is in \(W\text{,}\) so is orthogonal to \(\proj_{\perp W} \vv = \vv - \proj_W \vv\text{.}\) Thus, the dotted triangle whose vertices are the tips of the vectors \(\vv\text{,}\) \(\vx\text{,}\) and \(\proj_W \vv\) in Figure 25.5 is a right triangle.

The Pythagorean theorem then shows that

\begin{equation*} || \vv - \vx ||^2 = || \proj_{\perp W} \vv ||^2 + || \proj_W \vv - \vx ||^2\text{.} \end{equation*}

Now \(\vx \neq \proj_W \vv\text{,}\) so \(|| \proj_W \vv - \vx ||^2 > 0\text{.}\) This implies

\begin{equation*} || \vv - \vx ||^2 > || \proj_{\perp W} \vv ||^2 \end{equation*}

and it follows that

\begin{equation*} || \vv - \vx || > || \proj_{\perp W} \vv ||\text{.} \end{equation*}

This theorem shows that the distance from \(\proj_W \vv\) to \(\vv\) is less than the distance from any other vector in \(W\) to \(\vv\text{.}\) So \(\proj_W \vv\) is the best approximation to \(\vv\) of all the vectors in \(W\text{.}\)

If \(\vv = [v_1 \ v_2 \ v_3 \ \ldots \ v_m]^{\tr}\) and \(\proj_W \vv = [w_1 \ w_2 \ w_3 \ \ldots \ w_m]^{\tr}\text{,}\) then the square of the error in approximating \(\vv\) by \(\proj_W \vv\) is given by

So \(\proj_W \vv\) minimizes this sum of squares over all vectors in \(W\text{.}\) As a result, we call \(\proj_W \vv\) the least squares approximation to \(\vv\text{.}\)

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 shows the first steps of the Gram-Schmidt process to construct an orthogonal basis from any basis of a subspace in \(\R^n\text{.}\) To understand why the process works in general, let \(\{\vv_1, \vv_2, \ldots, \vv_m\}\) be a basis for a subspace \(W\) of \(\R^n\text{.}\) Let \(\vw_1 = \vv_1\) and let \(W_1 = \Span\{\vw_1\}\text{.}\) Since \(\vw_1 = \vv_1\) we have that \(W_1 = \Span\{\vw_1\} = \Span\{\vv_1\}\text{.}\)

The vectors \(\vv_1 = \vw_1\) and \(\vv_2\) are possibly not orthogonal, but we know the orthogonal projection of \(\vv_2\) onto \(W_1^{\perp}\) is orthogonal to \(\vw_1\text{.}\) Let

Then \(\{\vw_1, \vw_2\}\) is an orthogonal set. Note that \(\vw_1 = \vv_1 \neq \vzero\text{,}\) and the fact that \(\vv_2 \notin W_1\) implies that \(\vw_2 \neq \vzero\text{.}\) So the set \(\{\vw_1, \vw_2\}\) is linearly independent, being a set of non-zero orthogonal vectors. Now the question is whether \(\Span\{\vw_1,\vw_2\} = \Span\{\vv_1,\vv_2\}\text{.}\) Note that \(\vw_2\) is a linear combination of \(\vv_1\) and \(\vv_2\text{,}\) so \(\vw_2\) is in \(\Span\{\vv_1,\vv_2\}\text{.}\) Since \(\Span\{\vw_1,\vw_2\}\) is a 2-dimensional subspace of the 2-dimensional space \(\Span\{\vv_1,\vv_2\}\text{,}\) it must be true that \(\Span\{\vw_1,\vw_2\} = W_2 = \Span\{\vv_1,\vv_2\}\text{.}\)

Now we take the next step, adding \(\vv_3\) into the mix. The vector

is orthogonal to both \(\vw_1\) and \(\vw_2\) and, by construction, \(\vw_3\) is a linear combination of \(\vv_1\text{,}\) \(\vv_2\text{,}\) and \(\vv_3\text{.}\) So \(\vw_3\) is in \(W_3 = \Span\{\vv_1, \vv_2, \vv_3\}\text{.}\) The fact that \(\vv_3 \notin W_2\) implies that \(\vw_3 \neq \vzero\) and \(\{\vw_1, \vw_2, \vw_3\}\) is a linearly independent set. Since \(\Span\{\vw_1, \vw_2, \vw_3\}\) is a 3-dimensional subspace of the 3-dimensional space \(\Span\{\vv_1,\vv_2,\vv_3\}\text{,}\) we conclude that \(\Span\{\vw_1, \vw_2, \vw_3\} = W_3 = \Span\{\vv_1,\vv_2,\vv_3\}\text{.}\)

We continue inductively in this same manner. If we have constructed a set \(\{\vw_1\text{,}\) \(\vw_2\text{,}\) \(\vw_3\text{,}\) \(\ldots\text{,}\) \(\vw_{k-1}\}\) of \(k-1\) orthogonal vectors such that

then we let

where

We know that \(\vw_k\) is orthogonal to \(\vw_1\text{,}\) \(\vw_2\text{,}\) \(\ldots\text{,}\) \(\vw_{k-1}\text{.}\) Since \(\vw_1\text{,}\) \(\vw_2\text{,}\) \(\ldots\text{,}\) \(\vw_{k-1}\text{,}\) and \(\vv_k\) are all in \(W_k = \Span\{\vv_1, \vv_2, \ldots, \vv_k\}\) we see that \(\vw_k\) is also in \(W_k\text{.}\) Since \(\vv_k \notin W_{k-1}\) implies that \(\vw_k \neq \vzero\) and \(\{\vw_1, \vw_2, \ldots, \vw_k\}\) is a linearly independent set. Then \(\Span\{\vw_1, \vw_2, \vw_3, \ldots, \vw_{k}\}\) is a \(k\)-dimensional subspace of the \(k\)-dimensional space \(W_k\text{,}\) so it follows that

This process will end when we have an orthogonal set \(\{\vw_1\text{,}\) \(\vw_2\text{,}\) \(\vw_3\text{,}\) \(\ldots\text{,}\) \(\vw_{m}\}\) with \(\Span\{\vw_1\text{,}\) \(\vw_2\text{,}\) \(\vw_3\text{,}\) \(\ldots\text{,}\) \(\vw_{m}\}\) = \(W\text{.}\)

We summarize the process in the following theorem.

The Gram-Schmidt process builds an orthogonal basis \(\{\vw_1, \vw_2, \vw_3, \ldots, \vw_{m}\}\) for us from a given basis. To make an orthonormal basis \(\{\vu_1, \vu_2, \vu_3, \ldots, \vu_{m}\}\text{,}\) all we need do is normalize each basis vector: that is, for each \(i\text{,}\) we let

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 contains the main ideas to find the QR factorization of a matrix. Let

be an \(m \times n\) matrix with rank⁴⁴ \(n\text{.}\) We can use the Gram-Schmidt process to find an orthonormal basis \(\{\vu_1, \vu_2, \ldots, \vu_n\}\) for \(\Col A\text{.}\) Recall also that \(\Span\{\vu_1, \vu_2, \ldots, \vu_k\} = \Span\{\va_1, \va_2, \ldots, \va_k\}\) for any \(k\) between 1 and \(n\text{.}\) Let

If \(k\) is between 1 and \(n\text{,}\) then \(\va_k\) is in \(\Span\{\vu_1, \vu_2, \ldots, \vu_k\}\) and

for some scalars \(r_{1k}\text{,}\) \(r_{2k}\text{,}\) \(\ldots\text{,}\) \(r_{kk}\text{.}\) Then

If we let \(\vr_k = \left[ \begin{array}{c} r_{1k} \\ r_{2k} \\ \vdots \\ r_{kk} \\ 0 \\ \vdots \\ 0 \end{array} \right]\) for \(k\) from 1 to \(n\text{,}\) then

This is the QR factorization of \(A\) into the product

where the columns of \(Q\) form an orthonormal basis for \(\Col A\) and

is an upper triangular matrix. Note that \(Q\) is an \(m \times n\) matrix and \(R = [r_{ij}]\) is an \(n \times n\) matrix with \(r_{ii} \neq 0\) for each \(i\text{.}\)

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\text{.}\) Let \(A_1 = A\text{.}\)

• Find the QR factorization for \(A_1\) and write it as \(A_1 = Q_1R_1\text{,}\) where \(Q_1\) is orthogonal and \(R_1\) is upper triangular.

• Let \(A_2 = Q_1^{-1}A_1Q_1 = Q_1^{\tr}AQ_1 = R_1Q_1\text{.}\) Find the QR factorization of \(A_2\) and write it as \(A_2 = Q_2R_2\text{.}\)

• Let \(A_3 = Q_2^{-1}A_2Q_2 = Q_2^{\tr}AQ_2 = R_2Q_2\text{.}\) Find the QR factorization of \(A_3\) and write it as \(A_3 = Q_3R_3\text{.}\)

• Continue in this manner to obtain a sequence \(\{A_k\}\) where \(A_k = Q_kR_k\) and \(A_{k+1} = R_kQ_k\text{.}\)

Note that \(A_{k+1} = Q_k^{-1}A_kQ_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.

Subsection Summary

• The projection of the vector \(\vv\) in \(V\) onto \(W\) is the vector

  \begin{equation*} \proj_W \vv = \frac{\vv \cdot \vw_1}{\vw_1 \cdot \vw_1} \vw_1 + \frac{\vv \cdot \vw_2}{\vw_2 \cdot \vw_2} \vw_2 + \cdots + \frac{\vv \cdot \vw_m}{\vw_m \cdot \vw_m} \vw_m\text{,} \end{equation*}

  where \(W\) is the a subspace of \(\R^n\) with orthogonal basis \(\{\vw_1, \vw_2, \ldots, \vw_m\}\text{.}\) These projections are important in that \(\proj_W \vv\) is the best approximation of the vector \(\vv\) by a vector in \(W\) in the least squares sense.

• With \(W\) as in (a), the projection of \(\vv\) orthogonal to \(W\) is the vector

  \begin{equation*} \proj_{\perp W} \vv = \vv - \proj_W \vv\text{.} \end{equation*}

  The norm of \(\proj_{\perp W} \vv\) provides a measure of how well \(\proj_W \vv\) approximates the vector \(\vv\text{.}\)

• The Gram-Schmidt process produces an orthogonal basis from any basis. It works as follows. Let \(\{\vv_1, \vv_2, \ldots, \vv_m\}\) be a basis for a subspace \(W\) of \(\R^n\text{.}\) The set \(\{\vw_1\text{,}\) \(\vw_2\text{,}\) \(\vw_3\text{,}\) \(\ldots\text{,}\) \(\vw_{m}\}\) defined by

  • \(\vw_1 = \vv_1\text{,}\)

  • \(\vw_2 = \vv_2 - \ds \frac{\vv_2 \cdot \vw_1}{\vw_1 \cdot \vw_1} \vw_1\text{,}\)

  • \(\vw_3 = \vv_3 - \ds \frac{ \vv_3 \cdot \vw_1 }{ \vw_1 \cdot \vw_1 } \vw_1 - \frac{ \vv_3 \cdot \vw_2 }{ \vw_2 \cdot \vw_2 } \vw_2\text{,}\) \(\vdots\)

  • \(\vw_m = \vv_m - \ds \frac{ \vv_m \cdot \vw_1 }{ \vw_1 \cdot \vw_1 } \vw_1 - \frac{ \vv_m \cdot \vw_2 }{ \vw_2 \cdot \vw_2 } \vw_2 - \cdots - \frac{ \vv_m \cdot \vw_{m-1} }{ \vw_{m-1} \cdot \vw_{m-1} } \vw_{m-1}\text{.}\)

  is an orthogonal basis for \(W\text{.}\) Moreover,

  \begin{equation*} \Span\{\vw_1, \vw_2, \vw_3, \ldots, \vw_{k}\} = \Span\{\vv_1,\vv_2,\vv_3, \ldots, \vv_{k}\} \end{equation*}

  for each \(k\) between 1 and \(m\text{.}\)

• 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 = QR\text{,}\) where the columns of \(Q\) form an orthonormal basis for \(\Col A\) and

  \begin{equation*} R = [\vr_1 \ | \ \vr_2 \ | \ \vr_3 \ | \ \cdots \ | \ \vr_n ] = \left[ \begin{array}{cccccc} r_{11}\amp r_{12}\amp r_{13}\amp \cdots \amp r_{1n-1}\amp r_{1n} \\ 0\amp r_{22}\amp r_{23}\amp \cdots \amp r_{2n-1}\amp r_{2n} \\ 0\amp 0\amp r_{33}\amp \cdots \amp r_{3n-1}\amp r_{3n} \\ \vdots\amp \vdots \amp \vdots \amp \vdots \amp \vdots \amp \vdots \\ 0\amp 0\amp 0\amp \cdots \amp 0\amp r_{nn} \end{array} \right] \end{equation*}

  is an upper triangular matrix.

Subsection Project: MIMO Systems and Householder Transformations