Linear Algebra and Its Applications, Exercise 3.3.10

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 | Leave a comment

Linear Algebra and Its Applications, Exercise 3.3.9

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 , | Leave a comment

Linear Algebra and Its Applications, Exercise 3.3.8

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 , , | Leave a comment

Linear Algebra and Its Applications, Exercise 3.3.7

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 , | Leave a comment

Linear Algebra and Its Applications, Exercise 3.3.6

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 , , , , | 6 Comments

Linear Algebra and Its Applications, Exercise 3.3.5

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 , , , | Leave a comment

Linear Algebra and Its Applications, Exercise 3.3.4

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&0 \\ 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&0 \\ 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}

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 , , , | Leave a comment