My Math Homework

Linear Algebra and Its Applications, Exercise 3.3.12

Posted on October 8, 2016 by hecker

Exercise 3.3.12. Given the subspace $V$ spanned by the two vectors $(1, 1, 0, 1)$ and $(0, 0, 1, 0)$ find the following:

a) a set of basis vectors for $V^\perp$

b) the matrix $P$ that projects onto $V$

c) the vector in $V$ that has the minimum distance to the vector $b = (0, 1, 0, -1)$ in $V^\perp$

Answer: a) The subspace $V$ is the column space $\mathcal{R}(A)$ for the matrix

$A = \begin{bmatrix} 1&0 \\ 1&0 \\ 0&1 \\ 1&0 \end{bmatrix}$

for which the vectors $(1, 1, 0, 1)$ and $(0, 0, 1, 0)$ are the columns. The orthogonal complement $V^\perp$ corresponds to the left nullspace $\mathcal{N}(A^T)$ , so we can find a basis for $V^\perp$ by solving the system of equations corresponding to $A^Ty =0$ :

$\begin{bmatrix} 1&1&0&1 \\ 0&0&1&0 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \end{bmatrix} = 0$

in matrix form or

$\setlength\arraycolsep{0.2em}\begin{array}{rcrcrcrcl}y_{1}&+&y_{2}&+&&&y_{4}&=&0 \\ &&&&y_{3}&&&=&0 \end{array}$

expressed as a system of equations.

The matrix $A^T$ is already in echelon form, with $y_1$ and $y_3$ as basic variables and $y_2$ and $y_4$ as free variables. Setting $y_2 = 1$ and $y_4 = 0$ we have $y_1 = -1$ and $y_3 = 0$ . Setting $y_2 = 0$ and $y_4 = 1$ we again have $y_1 = -1$ and $y_3 = 0$ . So two solutions to $A^Ty = 0$ are $(-1, 1, 0, 0)$ and $(-1, 0, 0, 1)$ and these form a basis for $V^\perp = \mathcal{N}(A^T)$ .

b) Since $V$ is the column space for the matrix $A$ above, the projection matrix onto $V$ is $P = A(A^TA)^{-1}A^T$ . We have

$A^TA = \begin{bmatrix} 1&1&0&1 \\ 0&0&1&0 \end{bmatrix} \begin{bmatrix} 1&0 \\ 1&0 \\ 0&1 \\ 1&0 \end{bmatrix} = \begin{bmatrix} 3&0 \\ 0&1 \end{bmatrix}$

Since $A^TA$ is a diagonal matrix its inverse is simply

$(A^TA)^{-1} = \begin{bmatrix} \frac{1}{3}&0 \\ 0&1 \end{bmatrix}$

We then have

$P = A(A^TA)^{-1}A^T$

$= \begin{bmatrix} 1&0 \\ 1&0 \\ 0&1 \\ 1&0 \end{bmatrix} \begin{bmatrix} \frac{1}{3}&0 \\ 0&1 \end{bmatrix} \begin{bmatrix} 1&1&0&1 \\ 0&0&1&0 \end{bmatrix}$

$= \begin{bmatrix} \frac{1}{3}&0 \\ \frac{1}{3}&0 \\ 0&1 \\ \frac{1}{3}&0 \end{bmatrix} \begin{bmatrix} 1&1&0&1 \\ 0&0&1&0 \end{bmatrix}$

$= \begin{bmatrix} \frac{1}{3}&\frac{1}{3}&0&\frac{1}{3} \\ \frac{1}{3}&\frac{1}{3}&0&\frac{1}{3} \\ 0&0&1&0 \\ \frac{1}{3}&\frac{1}{3}&0&\frac{1}{3} \end{bmatrix}$

c) The vector in $V$ closest to the vector $b = (0, 1, 0, -1)$ is simply the projection $Pb$ of $b$ onto $V$ . But since $b$ is in $V^\perp$ it is orthogonal to all vectors in $V$ and its projection $Pb$ onto $V$ is the zero vector.

This can also be seen by explicitly doing the matrix multiplication:

$Pb = \begin{bmatrix} \frac{1}{3}&\frac{1}{3}&0&\frac{1}{3} \\ \frac{1}{3}&\frac{1}{3}&0&\frac{1}{3} \\ 0&0&1&0 \\ \frac{1}{3}&\frac{1}{3}&0&\frac{1}{3} \end{bmatrix} \begin{bmatrix} 0 \\ 1 \\ 0 \\ -1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} = 0$

UPDATE: Corrected a typo in the statement of question (b).

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fifth Edition and the accompanying free online course, and Dr Strang’s other books.

Posted in linear algebra | Tagged basis, column space, left nullspace, orthogonal complement, projection matrix | Leave a comment

Linear Algebra and Its Applications, Exercise 3.3.11

Posted on October 1, 2016 by hecker

Exercise 3.3.11. Suppose that $S$ is a subspace with orthogonal complement $S^{\perp}$ , with $P$ a projection matrix onto $S$ and $Q$ a projection matrix onto $S^{\perp}$ . What are $P+Q$ and $PQ$ ? Also, show that $P-Q$ is its own inverse.

Answer: Given any vector $v$ we have $(P+Q)v = Pv + Qv$ where $Pv$ is the projection of $v$ onto $S$ and $Qv$ is the projection of $v$ onto $S^{\perp}$ . Since $S$ and $S^\perp$ are orthogonal complements the sum of the projections $Pv$ and $Qv$ is equal to $v$ itself. So we have $(P+Q)v = Pv + Qv = v$ and since this is true for all $v$ we have $P+Q = I$ .

This can be more formally proved as follows: Consider the matrix $I-Q$ . It is a projection matrix and it projects onto $S$ . Also, if $P$ is a projection matrix onto $S$ then it is unique. Since $P$ is a projection matrix onto $S$ and $I-Q$ is a projection matrix onto $S$ we therefore have $P = I-Q$ or $P+Q = I$ . For the full proof see below.

Since $P = I - Q$ we have

$PQ = (I - Q)Q = IQ - Q^2 = Q - Q = 0$ .

(Applying $PQ$ to a vector $v$ first projects $v$ onto $S^\perp$ and then projects the resulting vector onto $S$ . But projecting any vector in $S^\perp$ onto $S$ will produce the zero vector, since $S^\perp$ and $S$ are orthogonal.)

Finally, we have

$(P-Q)(P-Q) = [(I-Q) - Q][(I-Q) - Q]$

$(I - 2Q)(I - 2Q) = I^2 - 2Q - 2Q + 4Q^2$

$I - 4Q + 4Q = I$

Since $(P-Q)(P-Q) = I$ we have $(P-Q)^{-1} = P-Q$ so that $P-Q$ is its own inverse.

Here is the full proof that if $P$ a projection matrix onto $S$ and $Q$ a projection matrix onto $S^{\perp}$ then $P+Q = I$ :

We first show that $I-Q$ is a projection matrix. The identity matrix $I$ is symmetric, and since $Q$ is a projection matrix it is also symmetric. The difference $I-Q$ is therefore symmetric as well, so that we have $(I-Q)^T = I-Q$ .

We also have

$(I-Q)^2 = (I-Q)(I-Q) = I^2 - IQ - QI + Q^2$

$= I - 2Q + Q = I-Q$

Since $(I-Q)^T = I-Q$ and $(I-Q)^2 = I-Q$ we see that $I-Q$ is a projection matrix.

Onto what subspace does $I-Q$ project? For any vector $v$ we have $(I-Q)v = v - Qv$ . Since $Q$ is a projection matrix the vector $Qv$ is in the space onto which $Q$ projects, and the vector $v - Qv$ is orthogonal to that space. But $Q$ projects onto $S^\perp$ so $v-Qv$ must therefore be in $(S^\perp)^\perp = S$ .

We have thus shown that $I-Q$ is a projection matrix that projects onto $S$ . We now show that any such projection matrix is unique.

Suppose that like $P$ the matrix $P'$ is also a projection matrix onto $S$ . Consider the vector $(P - P')v$ for any vector $v$ . We have

$\|(P - P')v\|^2 = [(P-P')v]^T[(P-P')v]$

$= v^T(P-P')^T(P-P')v$

where we take advantage of the fact that $(AB)^T = B^TA^T$ .

But since $P$ and $P'$ are projection matrices they are symmetric, and therefore their difference $P-P'$ is also symmetric. We thus have

$\|(P - P')v\|^2 = v^T(P-P')(P-P')v$

$= v^T[P^2 - PP' - P'P + (P')^2]v$

But since $P$ and $P'$ are projection matrices we have $P = P^2$ and $P' = (P')^2$ . We thus have

$\|(P - P')v\|^2 = v^T[P - PP' - P'P + P']v$

Since $P$ is a projection matrix onto $S$ we know that $Pw = w$ for any vector $w$ in $S$ . (In other words, when applied to any vector $w$ in $S$ the projection matrix $P$ projects that vector onto itself.) The same is true for $P'$ since it is also a projection matrix onto $S$ . We thus have $Pw = P'w = w$ for all $w$ in $S$ .

Given any vector $v$ (not necessarily in $S$ ) we then have $PPv = P'Pv$ since $Pv$ is a vector in $S$ . Since $P$ is a projection matrix we have $P^2 = P$ and thus $PPv = Pv$ , so that $Pv = P'Pv$ for all vectors $v$ . This implies that $P = P'P$ .

Similarly for any vector $v$ we have $P'P'v = PP'v$ since $P'v$ is a vector in $S$ . Since $P'$ is a projection matrix we have $(P')^2 = P'$ and thus $P'P'v = P'v$ , so that $P'v = PP'v$ for all vectors $v$ . This implies that $P' = PP'$ .

Since $P = P'P$ and $P' = PP'$ we have

$\|(P - P')v\|^2 = v^T(P - P' - P + P')v$

$= v^T \cdot 0 \cdot v = 0$

Since $\|(P - P')v\|^2 = 0$ we have $(P-P')v = 0$ , and since this is true for any vector $v$ we must have $P-P' = 0$ or $P = P'$ . A projection matrix $P$ onto a subspace $S$ is therefore unique.

Thus since $P$ is a projection matrix onto $S$ and $I-Q$ is also a projection matrix onto $S$ we have $P = I-Q$ or $P+Q=I$ .

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

Posted in linear algebra | Tagged orthogonal complement, projection matrix | Leave a comment

Linear Algebra and Its Applications, Exercise 3.3.10

Posted on September 24, 2016 by hecker

Exercise 3.3.10. Given mutually orthogonal vectors $a_1$ , $a_2$ , and $b$ and the matrix $A$ with columns $a_1$ and $a_2$ , what are $A^TA$ and $A^Tb$ ? What is the projection of $b$ onto the plane formed by $a_1$ and $a_2$ ?

Answer: We have

$A^TA = \begin{bmatrix} a_1^T \\ a_2^T \end{bmatrix} \begin{bmatrix} a_1&a_2 \end{bmatrix} = \begin{bmatrix} a_1^Ta_1&a_1^Ta_2 \\ a_2^Ta_1&a_2^Ta_2 \end{bmatrix} = \begin{bmatrix} \|a_1\|^2&0 \\ 0&\|a_2\|^2 \end{bmatrix}$

where the zero entries are the result of $a_1$ and $a_2$ being orthogonal.

Similarly we have

$A^Tb = \begin{bmatrix} a_1^T \\ a_2^T \end{bmatrix} b = \begin{bmatrix} a_1^Tb \\ a_2^Tb \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} = 0$

where the zero entries are the result of $a_1$ and $a_2$ being orthogonal to $b$ .

Since $b$ is orthogonal to both $a_1$ and $a_2$ it is orthogonal to any linear combination of $a_1$ and $a_2$ and therefore is orthogonal to the plane spanned by $a_1$ and $a_2$ . The projection of $b$ onto that plane is therefore the zero vector.

This also follows from the formula for the projection matrix $P$ corresponding to the matrix $A$ . The projection $p$ of $b$ onto the column space of $A$ (the space spanned by $a_1$ and $a_2$ ) is

$p = Pb = A(A^TA)^{-1}A^Tb = A(A^TA)^{-1} \cdot 0 = 0$

since $A^Tb = 0$ as discussed above.

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.

Posted in linear algebra | Tagged orthogonal vectors | Leave a comment

Linear Algebra and Its Applications, Exercise 3.3.9

Posted on September 17, 2016 by hecker

Exercise 3.3.9. Suppose that $P$ is a matrix such that $P = P^TP$ .

a) Show that $P$ is a projection matrix.

b) If $P = 0$ then what is the subspace onto which $P$ projects?

Answer: a) To show that $P$ is a projection matrix we must show that $P = P^2$ and also that $P = P^T$ . We have

$P^T = (P^TP)^T = P^T(P^T)^T = P^TP = P$

Since $P^T = P$ we then have

$P^2 = P P = P^T P = P$

Since $P = P^T = P^2$ the matrix $P$ is a projection matrix.

b) If $P = 0$ then for all vectors $v$ we have $P v = 0$ . So $P$ projects onto the subspace consisting of the zero vector.

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.

Posted in linear algebra | Tagged projection matrix, subspace | Leave a comment

Linear Algebra and Its Applications, Exercise 3.3.8

Posted on September 10, 2016 by hecker

Exercise 3.3.8. Suppose that $P$ is a projection matrix from $\mathbb R^n$ onto a subspace $S$ with dimension $k$ . What is the column space of $P$ ? What is its rank?

Answer: Suppose that $b$ is a arbitrary vector in $\mathbb R^n$ . From the definition of $P$ we know that $Pb$ is a vector in $S$ . But $Pb$ is a linear combination of the columns of $P$ , so that $Pb$ also is in the column space $\mathcal{R}(P)$ . Since any vector in $S$ can be expressed as $Pb$ for some $b$ , all vectors in $S$ are also in $\mathcal{R}(P)$ , so that $S \subseteq \mathcal{R}(P)$ .

Now suppose that $v$ is an arbitrary vector in the column space $\mathcal{R}(P)$ . Then $v$ can be expressed as a linear combination of the columns of $P$ for some set of coefficients $a_1, a_2, \dots, a_n$ . Consider the vector $w = (a_1, a_2, \dots, a_n)$ . We then have $v = Pw$ by the definition of $w$ . But if $v = Pw$ for some $w$ then $v$ is in $S$ . So all vectors in $\mathcal{R}(P)$ are also in $S$ and thus $\mathcal{R}(P) \subseteq S$ .

Since $S \subseteq \mathcal{R}(P)$ and $\mathcal{R}(P) \subseteq S$ we then have $S = \mathcal{R}(P)$ : The column space of $P$ is $S$ .

The rank of $P$ is the dimension of its column space. But since $S$ is the column space of $P$ , the rank of $P$ is $k$ , the dimension of $S$ .

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.

Posted in linear algebra | Tagged column space, projection matrix, rank | Leave a comment

Linear Algebra and Its Applications, Exercise 3.3.7

Posted on September 3, 2016 by hecker

Exercise 3.3.7. Given the two vectors $a_1 = (1, 0, 1)$ and $a_2 = (1, 1, -1)$ find the projection matrix $P$ that projects onto the subspace spanned by $a_1$ and $a_2$ .

Answer: The subspace spanned by $a_1$ and $a_2$ is the column space $\mathcal{R}(A)$ where

$A = \begin{bmatrix} 1&1 \\ 0&1 \\ 1&-1 \end{bmatrix}$

The projection matrix onto the subspace is then $P = A(A^TA)^{-1}A^T$ . We have

$A^TA = \begin{bmatrix} 1&0&1 \\ 1&1&-1 \end{bmatrix} \begin{bmatrix} 1&1 \\ 0&1 \\ 1&-1 \end{bmatrix} = \begin{bmatrix} 2&0 \\ 0&3 \end{bmatrix}$

Since $A^TA$ is a diagonal matrix we can compute its inverse by simply taking the reciprocals of the diagonal entries:

$(A^TA)^{-1} = \begin{bmatrix} \frac{1}{2}&0 \\ 0&\frac{1}{3} \end{bmatrix}$

We then have

$P = A(A^TA)^{-1}A^T = \begin{bmatrix} 1&1 \\ 0&1 \\ 1&-1 \end{bmatrix} \begin{bmatrix} \frac{1}{2}&0 \\ 0&\frac{1}{3} \end{bmatrix} \begin{bmatrix} 1&0&1 \\ 1&1&-1 \end{bmatrix}$

$= \begin{bmatrix} \frac{1}{2}&\frac{1}{3} \\ 0&\frac{1}{3} \\ \frac{1}{2}&-\frac{1}{3} \end{bmatrix} \begin{bmatrix} 1&0&1 \\ 1&1&-1 \end{bmatrix} = \begin{bmatrix} \frac{5}{6}&\frac{1}{3}&\frac{1}{6} \\ \frac{1}{3}&\frac{1}{3}&-\frac{1}{3} \\ \frac{1}{6}&-\frac{1}{3}&\frac{5}{6} \end{bmatrix}$

NOTE: This continues a series of posts containing worked-out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.

Posted in linear algebra | Tagged column space, projection matrix | Leave a comment

Linear Algebra and Its Applications, Exercise 3.3.6

Posted on July 10, 2016 by hecker

Exercise 3.3.6. Given the matrix $A$ and vector $b$ defined as follows

$A = \begin{bmatrix} 1&1 \\ 2&-1 \\ -2&4 \end{bmatrix} \qquad b = \begin{bmatrix} 1 \\ 2 \\ 7 \end{bmatrix}$

find the projection of $b$ onto the column space of $A$ .

Decompose the vector $b$ into the sum $p + q$ of two orthogonal vectors $p$ and $q$ where $p$ is in the column space. Which subspace is $q$ in?

Answer: We have $p = A(A^TA)^{-1}A^Tb$ per equation (3) of 3L on page 156. We first compute

$A^TA = \begin{bmatrix} 1&2&-2 \\ 1&-1&4 \end{bmatrix} \begin{bmatrix} 1&1 \\ 2&-1 \\ -2&4 \end{bmatrix}$

$= \begin{bmatrix} 9&-9 \\ -9&18 \end{bmatrix}$

and then compute

$(A^TA)^{-1} = \frac{1}{9 \cdot 18 - (-9)(-9)} \begin{bmatrix} 18&-(-9) \\ -(-9)&9 \end{bmatrix}$

$= \frac{1}{81} \begin{bmatrix} 18&9 \\ 9&9 \end{bmatrix} = \begin{bmatrix} \frac{2}{9}&\frac{1}{9} \\ \frac{1}{9}&\frac{1}{9} \end{bmatrix}$

Finally we compute

$p = A(A^TA)^{-1}A^Tb$

$= \begin{bmatrix} 1&1 \\ 2&-1 \\ -2&4 \end{bmatrix} \begin{bmatrix} \frac{2}{9}&\frac{1}{9} \\ \frac{1}{9}&\frac{1}{9} \end{bmatrix} \begin{bmatrix} 1&2&-2 \\ 1&-1&4 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 7 \end{bmatrix}$

$= \begin{bmatrix} 1&1 \\ 2&-1 \\ -2&4 \end{bmatrix} \begin{bmatrix} \frac{2}{9}&\frac{1}{9} \\ \frac{1}{9}&\frac{1}{9} \end{bmatrix} \begin{bmatrix} -9 \\ 27 \end{bmatrix}$

$= \begin{bmatrix} 1&1 \\ 2&-1 \\ -2&4 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \end{bmatrix} = \begin{bmatrix} 3 \\ 0 \\ 6 \end{bmatrix}$

Since $b = p + q$ we have

$q = b - p = \begin{bmatrix} 1 \\ 2 \\ 7 \end{bmatrix} - \begin{bmatrix} 3 \\ 0 \\ 6 \end{bmatrix} = \begin{bmatrix} -2 \\ 2 \\ 1 \end{bmatrix}$

We have

$p \cdot q = 3 \cdot (-2) + 0 \cdot 2 + 6 \cdot 1 = -6 + 0 + 6 = 0$

so that $p$ and $q$ are orthogonal.

The vector $p$ is in $\cal{R}(A)$ , the column space of A, and the orthogonal subspace of $\cal{R}(A)$ is $\cal{N}(A^T)$ , the left nullspace of $A$ . Since $p$ is in $\cal{R}(A)$ and $q$ is orthogonal to $p$ , $q$ must be in $\cal{N}(A^T)$ , so that $A^Tq = 0$ . We confirm this:

$A^Tq = \begin{bmatrix} 1&2&-2 \\ 1&-1&4 \end{bmatrix} \begin{bmatrix} -2 \\ 2 \\ 1 \end{bmatrix}$

$= \begin{bmatrix} -2 + 4 -2 \\ -2 - 2 + 4 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} = 0$

UPDATE: I corrected the calculation of $q$ ; thanks go to KTL for pointing out the error.

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.

Posted in linear algebra | Tagged column space, left nullspace, orthogonal subspaces, orthogonal vectors, projection matrix | 6 Comments

Linear Algebra and Its Applications, Exercise 3.3.5

Posted on October 25, 2014 by hecker

Exercise 3.3.5. Given the system

$Ax = \begin{bmatrix} 1&-1 \\ 1&0 \\ 1&1 \end{bmatrix} \begin{bmatrix} C \\ D \end{bmatrix} = \begin{bmatrix} 4 \\ 5 \\ 9 \end{bmatrix} = b$

with no solution, provide a graph of a straight line that minimizes

$(C - D -4)^2 + (C - 5)^2 + (C + D - 9)^2$

and solve for the equation of the line. What is the result of projecting the vector $b$ onto the column space of $A$ ?

Answer: We have

$(C - D -4)^2 + (C - 5)^2 + (C + D - 9)^2 = \| Ax - b \|^2$

In other words, this problem is essentially that of finding $\bar{x} = \begin{bmatrix} \bar{C} \\ \bar{D} \end{bmatrix}$ , the least squares solution to $Ax = b$ that minimizes the error vector $E^2 = \| Ax - b \|^2$ .

From 3L on page 156 we have $\bar{x} = (A^TA)^{-1}A^Tb$ . In this case we have

$A^TA = \begin{bmatrix} 1&1&1 \\ -1&0&1 \end{bmatrix} \begin{bmatrix} 1&-1 \\ 1&0 \\ 1&1 \end{bmatrix} = \begin{bmatrix} 3&0 \\ 0&2 \end{bmatrix}$

and thus

$(A^TA)^{-1} = \frac{1}{6} \begin{bmatrix} 2&0 \\ 0&3 \end{bmatrix}$

so that

$\bar{x} = (A^TA)^{-1}A^Tb = \frac{1}{6} \begin{bmatrix} 2&0 \\ 0&3 \end{bmatrix} \begin{bmatrix} 1&-1 \\ 1&0 \\ 1&1 \end{bmatrix} \begin{bmatrix} 4 \\ 5 \\ 9 \end{bmatrix}$

$= \frac{1}{6} \begin{bmatrix} 2&0 \\ 0&3 \end{bmatrix} \begin{bmatrix} 18 \\ 5 \end{bmatrix} = \frac{1}{6} \begin{bmatrix} 36 \\ 15 \end{bmatrix} = \begin{bmatrix} 6 \\ \frac{5}{2} \end{bmatrix}$

Thus the line that minimizes

$E^2 = \|Ax -b\|^2$

$= (C - D - 4)^2 + (C - 5)^2 + (C + D - 9)^2$

is $\bar{C} + \bar{D}t$ with slope $\bar{D} = \frac{5}{2}$ and intercept $\bar{C} = 6$ .

Also from 3L on page 156 the projection of $b$ onto the column space of $A$ is

$p = A\bar{x} = \begin{bmatrix} 1&-1 \\ 1&0 \\ 1&1 \end{bmatrix} \begin{bmatrix} 6 \\ \frac{5}{2} \end{bmatrix} = \begin{bmatrix} \frac{7}{2} \\ 6 \\ \frac{17}{2} \end{bmatrix}$

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.

Posted in linear algebra | Tagged column space, error vector, least squares, projection | Leave a comment

Linear Algebra and Its Applications, Exercise 3.3.4

Posted on June 29, 2014 by hecker

Exercise 3.3.4. Given

$A = \begin{bmatrix} 1&0 \\ 0&1 \\ 1&1 \end{bmatrix} \qquad x = \begin{bmatrix} u \\ v \end{bmatrix} \qquad b = \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix}$

expand the expression $E^2 = \| Ax - b \|^2$ , compute its partial derivatives with respect to $u$ and $v$ , and set them to zero. Compare the resulting equations to $A^TA\bar{x} = A^Tb$ to confirm that you obtain the same normal equations in both cases (i.e., using calculus vs. geometry). Then find the projection $p = A\bar{x}$ and explain why $p = b$ .

Answer: We have

$Ax-b = \begin{bmatrix} 1&0 \\ 0&1 \\ 1&1 \end{bmatrix} \begin{bmatrix} u \\ v \end{bmatrix} - \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix}$

$= \begin{bmatrix} u \\ v \\ u+v \end{bmatrix} - \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} u-1 \\ v-3 \\ (u+v)-4 \end{bmatrix}$

so that

$E^2 = \| Ax-b \| = \left(Ax-b\right)^T\left(Ax-b\right)$

$= (u-1)^2 + (v-3)^2 + [(u+v)-4]^2$

$= (u^2-2u+1) + (v^2-6v+9) +[ (u+v)^2 - 8(u+v) + 16]$

$= u^2-2u+1+v^2-6v+9+u^2+2uv+v^2-8u-8v+16$

$= 2u^2+2v^2+2uv-10u-14v+26$

Taking the partial derivative of this expression with respect to $u$ we have

$\partial E^2/{\partial u} = \partial/{\partial u}(2u^2+2v^2+2uv-10u-14v+26)$

$= 4u+2v-10$

and setting it to zero we have

$4\bar{u}+2\bar{v}-10 = 0$

where $\bar{u}$ and $\bar{v}$ represent the least squares solution.

Taking the partial derivative of this expression with respect to $v$ we have

$\partial E^2/{\partial v} = \partial/{\partial v}(2u^2+2v^2+2uv-10u-14v+26)$

$= 4v+2u-14$

and setting it to zero we have

$4\bar{v}+2\bar{u}-14 = 0$

where again $\bar{u}$ and $\bar{v}$ represent the least squares solution.

We then have a system of two equations

$\begin{array}{rcrcr} 4\bar{u}&+&2\bar{v}&=&10 \\ 2\bar{u}&+&4\bar{v}&=&14 \end{array}$

that is equivalent to the matrix equation

$\begin{bmatrix} 4&2 \\ 2&4 \end{bmatrix} \begin{bmatrix} \bar{u} \\ \bar{v}\end{bmatrix} = \begin{bmatrix} 10 \\ 14 \end{bmatrix}$

We now compare this to the normal equations $A^TA\bar{x} = A^Tb$ . We have

$A^TA = \begin{bmatrix} 1&0&1 \\ 0&1&1 \end{bmatrix} \begin{bmatrix} 1&0 \\ 0&1 \\ 1&1 \end{bmatrix} = \begin{bmatrix} 2&1 \\ 1&2 \end{bmatrix}$

and

$A^Tb = \begin{bmatrix} 1&0&1 \\ 0&1&1 \end{bmatrix} \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 5 \\ 7 \end{bmatrix}$

so that the normal equation in matrix form is

$\begin{bmatrix} 2&1 \\ 1&2 \end{bmatrix} \begin{bmatrix} \bar{u} \\ \bar{v} \end{bmatrix} = \begin{bmatrix} 5 \\ 7 \end{bmatrix}$

Note that this equation is the same as the previous equation calculated from taking the derivatives, except with both sides divided by 2.

We can now solve for $\bar{x} = \left(A^TA\right)^{-1}A^Tb$ . We have

$\left(A^TA\right) = \begin{bmatrix} 2&1 \\ 1&2 \end{bmatrix}^{-1} = \frac{1}{2 \cdot 2 - 1 \cdot 1} \begin{bmatrix} 2&-1 \\ -1&2 \end{bmatrix}$

$= \frac{1}{3} \begin{bmatrix} 2&-1 \\ -1&2 \end{bmatrix} = \begin{bmatrix} \frac{2}{3}&-\frac{1}{3} \\ -\frac{1}{3}&\frac{2}{3} \end{bmatrix}$

so that

$\bar{x} = \left(A^TA\right)^{-1}A^Tb = \begin{bmatrix} \frac{2}{3}&-\frac{1}{3} \\ -\frac{1}{3}&\frac{2}{3} \end{bmatrix} \begin{bmatrix} 5 \\ 7 \end{bmatrix}$

$= \begin{bmatrix} \frac{10}{3}-\frac{7}{3} \\ -\frac{5}{3}+\frac{14}{3} \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \end{bmatrix}$

We can multiply $\bar{x}$ by $A$ to obtain the projection $p$ of $b$ onto the column space of $A$ :

$p = A\bar{x} = \begin{bmatrix} 1&0 \\ 0&1 \\ 1&1 \end{bmatrix} \begin{bmatrix} 1 \\ 3 \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix} = b$

We have $p = b$ because $b$ is already in the column space of $A$ ; in particular, $b$ is equal to the first column of $A$ plus 3 times the second column of $A$ :

$b = \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} + 3 \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}$

UPDATE: Fixed a typo in the equations involving $A^TA$ and $A^Tb$ . Thanks go to Matt for finding this error.

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.

Posted in linear algebra | Tagged derivative, error vector, least squares, projection | 2 Comments

Linear Algebra and Its Applications, Exercise 3.3.3

Posted on June 23, 2014 by hecker

Exercise 3.3.3. Given

$A = \begin{bmatrix} 1&0 \\ 0&1 \\ 1&1 \end{bmatrix} \qquad b = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}$

solve $Ax = b$ to find $p = A\bar{x}$ . Show that $b-p$ is orthogonal to every column in $A$ .

Answer: We have $A^TA\bar{x} = A^Tb$ or $\bar{x} = \left(A^TA\right)^{-1}A^Tb$ if $A^TA$ is invertible. In this case we have

$A^TA = \begin{bmatrix} 1&0&1 \\ 0&1&1 \end{bmatrix} \begin{bmatrix} 1&0 \\ 0&1 \\ 1&1 \end{bmatrix} = \begin{bmatrix} 2&1 \\ 1&2 \end{bmatrix}$

so that

$\left(A^TA\right)^{-1} = \frac{1}{2 \cdot 2 - 1 \cdot 1} \begin{bmatrix} 2&-1 \\ -1&2 \end{bmatrix}$

$= \frac{1}{3} \begin{bmatrix} 2&-1 \\ -1&2 \end{bmatrix} = \begin{bmatrix} \frac{2}{3}&-\frac{1}{3} \\ -\frac{1}{3}&\frac{2}{3} \end{bmatrix}$

We then have

$\bar{x} = \begin{bmatrix} \frac{2}{3}&-\frac{1}{3} \\ -\frac{1}{3}&\frac{2}{3} \end{bmatrix} \begin{bmatrix} 1&0&1 \\ 0&1&1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}$

$= \begin{bmatrix} \frac{2}{3}&-\frac{1}{3} \\ -\frac{1}{3}&\frac{2}{3} \end{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{1}{3} \\ \frac{1}{3} \end{bmatrix}$

and

$p = A\bar{x} = \begin{bmatrix} 1&0 \\ 0&1 \\ 1&1 \end{bmatrix} \begin{bmatrix} \frac{1}{3} \\ \frac{1}{3} \end{bmatrix} = \begin{bmatrix} \frac{1}{3} \\ \frac{1}{3} \\ \frac{2}{3} \end{bmatrix}$

The error vector is then

$b - p = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} - \begin{bmatrix} \frac{1}{3} \\ \frac{1}{3} \\ \frac{2}{3} \end{bmatrix} = \begin{bmatrix} \frac{2}{3} \\ \frac{2}{3} \\ -\frac{2}{3} \end{bmatrix}$

The inner product of the error vector $b-p$ with column 1 of $A$ is

$\begin{bmatrix} \frac{2}{3}&\frac{2}{3}&-\frac{2}{3} \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \frac{2}{3} + 0 - \frac{2}{3} = 0$

The inner product of $b-p$ with column 2 of $A$ is

$\begin{bmatrix} \frac{2}{3}&\frac{2}{3}&-\frac{2}{3} \end{bmatrix} \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} = 0 + \frac{2}{3} - \frac{2}{3} = 0$

Thus $b-p$ is othogonal to all columns of $A$ (and thus to the column space of $A$ as well).

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.

Buy me a snack to sponsor more posts like this!

Posted in linear algebra | Tagged error vector, least squares, orthogonal vectors | Leave a comment

My Math Homework

Linear Algebra and Its Applications, Exercise 3.3.12

Linear Algebra and Its Applications, Exercise 3.3.11

Linear Algebra and Its Applications, Exercise 3.3.10

Linear Algebra and Its Applications, Exercise 3.3.9

Linear Algebra and Its Applications, Exercise 3.3.8

Linear Algebra and Its Applications, Exercise 3.3.7

Linear Algebra and Its Applications, Exercise 3.3.6

Linear Algebra and Its Applications, Exercise 3.3.5

Linear Algebra and Its Applications, Exercise 3.3.4

Linear Algebra and Its Applications, Exercise 3.3.3

Archives

Meta