18.06 Problem Set 5 Solutions

Problem 1. If a parabola fit the data exactly we would get a solution (v_{1}, v_{2}, v_{3}) to the system

[ \begin{matrix}1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \\ 1 & 4 & 16 \end{matrix} ] [ \begin{matrix}v_{1} \\ v_{2} \\ v_{3} \end{matrix} ] = [ \begin{matrix}2 \\ 5 \\ 7 \\ 1 \end{matrix} ] .

Since this system is over determined, we seek the vector x̂ = (B, C, D) which best approximates a solution to this system in the sense of least squares. Then the least squares parabola will be y = B + Cx + Dx^{2}. We know that the vector x̂ satisfies the normal equation

A^{T} Ax̂ = A^{T} b.

Here, A denotes the 4 × 3 matrix above, and b = (2, 5, 7, 1). We have

A^{T} A = [ \begin{matrix}4 & 10 & 30 \\ 10 & 30 & 100 \\ 30 & 100 & 354 \end{matrix} ]; A^{T} b = [ \begin{matrix}15 \\ 37 \\ 101 \end{matrix} ]

Solving the system gives x̂ = (\frac{−29}{4}, \frac{223}{20}, \frac{−9}{4}).

Problem 2. (a) The line for the European data is y = C + Dx where the vector x̂ = (C, D) satisfies A^{T} Ax̂ = A^{T} b with

A = [ \begin{matrix}1 & 0 \\ 1 & 5 \\ 1 & 10 \\ 1 & 15 \end{matrix} ]; b = [ \begin{matrix}90 \\ 197 \\ 335 \\ 394 \end{matrix} ]

crunching the numbers gives x̂ = (\frac{193}{2}, 21).

For the North American data we use the same matrix A with b = (317, 474, 816, 1101) which gives x̂ = (\frac{2729}{10}, \frac{1347}{25}).

(b) Using the line y = \frac{193}{2} +21x, we plug in x = 30 corresponding to the year 2000 and get y = 726.5 as the estimated expenditures.

(c) Certainly one expects the difference in expenditures to increase dramatically since the slope of the North American line is more than twice that of the European line.

Problem 3.To show that S is linearly independent, suppose there are constants c_{1}, … c_{n} such that

c_{1}v_{1} + c_{2}v_{2} + ⋯ c_{n}v_{n} = 0.

Now, since S is an orthogonal set, we know that v_{i} · v_{j} = 0 for i ≠ j and v_{i} · v_{i} ≠ 0 (1 ≤ i, j ≤ n). Hence for each i between 1 and n we get

v_{i} · (c_{1}v_{1} + c_{2}v_{2} + ⋯ c_{n}v_{n}) = v_{i} · 0 = 0.

Hence

c_{1}(v_{1} · v_{i}) + ⋯ + c_{n}(v_{n} · v_{i}) = 0,

with all the terms on the left side of this equation zero except the i − th term. Thus the equation reduces to c_{i}(v_{i} · v_{i}) = 0. Since v_{i} · v_{i} ≠ 0, we must have c_{i} = 0. Hence we see that if

c_{1}v_{1} + c_{2}v_{2} + ⋯ c_{n}v_{n} = 0

Then c_{1} = c_{2} = ⋯ = c_{n} = 0, and the set S is linearly independent.

Problem 4.(a) Let v_{1}, …, v_{n} denote the columns of B, and write AB = [Av_{1} Av_{2} ⋯ Av_{n}]. We need to show that the set S = {Av_{1}, Av_{2}, …, Av_{n}} is orthonormal. To do this, consider Av_{i} · Av_{j} with 1 ≤ i, j ≤ n. We have

Av_{i} · Av_{j} = (Av_{i})^{T} Av_{j} = v_{i}^{T} A^{T} Av_{j}.

Now, since A is orthogonal, A^{T} A = I, and v_{i}^{T} A^{T} Av_{j} = v_{i}^{T} v_{j}. Moreover, since B is orthogonal and the vectors v_{1}, …, v_{n} are its columns, we have v_{i}^{T} v_{j} = 0 if i ≠ j and v_{i}^{T} v_{j} = 1 if i = j. Hence S is an orthonormal set. Since S consists of the columns of the matrix AB, this matrix is orthogonal.

Alternative Proof: A square matrix C is orthogonal if and only if C^{T} C = I (Problem set 4). Now, (AB)^{T} (AB) = B^{T} A^{T} AB. Since A and B are orthogonal, A^{T} A = I and B^{T} B = I. Thus (AB)^{T} AB = B^{T} A^{T} AB = B^{T} IB = B^{T} B = I, and AB is orthogonal.

(b) Since det(A) = det(A^{T}) and AA^{T} = I, we have det(AA^{T}) = det(A)det(A^{T}) = det(A)^{2} = 1. Hence det(A) is either 1 or −1.

Problem 6. Using row operations we have:

| \begin{matrix}1 & a & a^{2} \\ 1 & b & b^{2} \\ 1 & c & c^{2} \end{matrix} | = | \begin{matrix}1 & a & a^{2} \\ 0 & b − a & (b^{2} − a^{2}) \\ 0 & c − a & (c^{2} − a^{2}) \end{matrix} | = | \begin{matrix}1 & a & a^{2} \\ 0 & b − a & (b^{2} − a^{2}) \\ 0 & 0 & (c^{2} − a^{2}) − \frac{(c−a)}{(b−a)} \end{matrix} | = | \begin{matrix}1 & a & a^{2} \\ 0 & b − a & (b^{2} − a^{2}) \\ 0 & 0 & (c − a)(c − b) \end{matrix} |
= (b − a)(c − a)(c − b).