Final Exam

(a) Each special solution tells us the solution to $R\mathbf{x} = \mathbf{0}$ when we set one free variable $= 1$ and the others $= 0$. Here, the third and fourth variables must be the two free variables, and the other two are the pivots:

Now multiply out $R\mathbf{x}_1 = \mathbf{0}$ and $R\mathbf{x}_2 = \mathbf{0}$ to find the $*$‘s:

(The $*$‘s are just the negatives of the special solutions’ pivot entries.)

(b) We know the nullspace $N(A)$ has $n - r = 4 - 2 = 2$ dimensions: the special solutions $\mathbf{x}_1, \mathbf{x}_2$ form a basis.

The row space $C(A^T)$ has $r = 2$ dimensions. It’s orthogonal to $N(A)$, so just pick two linearly independent vectors orthogonal to $\mathbf{x}_1$ and $\mathbf{x}_2$ to form a basis: for example,

(Or: $C(A^T) = C(R^T)$ is just the row space of $R$, so the first two rows are a basis. Same thing!)

The column space $C(A)$ has $r = 2$ dimensions (same as $C(A^T)$). We can’t write down a basis because we don’t know what $A$ is, but we can say that the first two columns of $A$ are a basis.

The left nullspace $N(A^T)$ has $m - r = 3 - 2 = 1$ dimension; it’s orthogonal to $C(A)$, so any vector orthogonal to the first two columns of $A$ (whatever they are) will be a basis.

(a) By elimination: keep track of the elimination matrix $E$ on one side, and the product $EU$ on the other. When $EU = I$, then $E = U^{-1}$:

By cofactors: take the minors, then “checkerboard” the signs to get the cofactor matrix, then transpose and divide by $\det(U) = adf$:

and dividing by $adf$ gives

(b) We have a complete set of eigenvectors for $A$, so we can diagonalize: $A = U\Lambda U^{-1}$. We know $U$ is upper triangular, and so is the diagonal matrix $\Lambda$, and we’ve just shown that $U^{-1}$ is upper triangular too. So their product $A$ is also upper triangular.

(c) The columns aren’t orthogonal! (For example, the product $\mathbf{u}_1^T\mathbf{u}_2$ of the first two columns is $ab + 0 \cdot d + 0 \cdot 0 = ab$, which is nonzero because we’re assuming all the entries are nonzero.)

(a) All you can say is that $\operatorname{rank} A \leq \operatorname{rank} \begin{bmatrix} A & B \end{bmatrix}$. ($A$ can have any number $r$ of pivot columns, and these will all be pivot columns for $\begin{bmatrix} A & B \end{bmatrix}$; but there could be more pivot columns among the columns of $B$.)

(b) Now $\operatorname{rank} A = \operatorname{rank} \begin{bmatrix} A & A^2 \end{bmatrix}$. (Every column of $A^2$ is a linear combination of columns of $A$. For instance, if we call $A$‘s first column $\mathbf{a}_1$, then $A\mathbf{a}_1$ is the first column of $A^2$. So there are no new pivot columns in the $A^2$ part of $\begin{bmatrix} A & A^2 \end{bmatrix}$.)

(c) The nullspace $N(A)$ has dimension $n - r$, as always. Since $\begin{bmatrix} A & A \end{bmatrix}$ only has $r$ pivot columns — the $n$ columns we added are all duplicates — $\begin{bmatrix} A & A \end{bmatrix}$ is an $m$-by-$2n$ matrix of rank $r$, and its nullspace $N\left(\begin{bmatrix} A & A \end{bmatrix}\right)$ has dimension $2n - r$.

(a) $N(A) = \lbrace \mathbf{0} \rbrace$ so $A$ has full column rank $r = n = 3$: the columns are linearly independent.

(b) $\mathbf{x}^TA^TA\mathbf{x} = (A\mathbf{x})^T A\mathbf{x}$ is the squared length of $A\mathbf{x}$. The only way it can be zero is if $A\mathbf{x}$ has zero length (meaning $A\mathbf{x} = \mathbf{0}$).

(c) $B$ is a left inverse of $A$, since $BA = (A^TA)^{-1}A^TA = I$ is the (3-by-3) identity matrix. $B$ is not a right inverse of $A$, because $AB$ is a 5-by-5 matrix but can only have rank 3. (In fact, $AB = A(A^TA)^{-1}A^T$ is the projection onto the (3-dimensional) column space of $A$.)

(a) Using orthonormality ($\mathbf{q}_i^T\mathbf{q}_j = 0$ for $i \neq j$ and $\mathbf{q}_i^T\mathbf{q}_i = 1$):

(b) We maximize $(c_1^2\lambda_1 + c_2^2\lambda_2 + c_3^2\lambda_3)/(c_1^2 + c_2^2 + c_3^2)$ when $c_1 = c_2 = 0$, so $\mathbf{x} = c_3\mathbf{q}_3$ is a multiple of the eigenvector $\mathbf{q}_3$ with the largest eigenvalue $\lambda_3$.

(Also notice that the maximum value of this “Rayleigh quotient” $\mathbf{x}^TA\mathbf{x}/\mathbf{x}^T\mathbf{x}$ is the largest eigenvalue itself. This is another way of finding eigenvectors: maximize $\mathbf{x}^TA\mathbf{x}/\mathbf{x}^T\mathbf{x}$ numerically.)

(a) You could just write down $\mathbf{w} = 0\mathbf{u} + 0\mathbf{v} = \mathbf{0}$ — that’s perpendicular to everything! But a more useful choice is to subtract off just enough $\mathbf{u}$ so that $\mathbf{w} = \mathbf{v} - c\mathbf{u}$ is perpendicular to $\mathbf{u}$. That means $0 = \mathbf{w}^T\mathbf{u} = \mathbf{v}^T\mathbf{u} - c\,\mathbf{u}^T\mathbf{u}$, so $c = (\mathbf{v}^T\mathbf{u})/(\mathbf{u}^T\mathbf{u})$ and

(b) We already know $\mathbf{u}$ and $\mathbf{w}$ are orthogonal; just normalize them! Take $\mathbf{q}_1 = \mathbf{u}/|\mathbf{u}|$ and $\mathbf{q}_2 = \mathbf{w}/|\mathbf{w}|$. Then solve for the columns $\mathbf{r}_1, \mathbf{r}_2$ of $R$: $Q\mathbf{r}_1 = \mathbf{u}$ gives

and $Q\mathbf{r}_2 = \mathbf{v}$ gives

(where $c = (\mathbf{v}^T\mathbf{u})/(\mathbf{u}^T\mathbf{u})$ as before). Then $Q = \begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2 \end{bmatrix}$ and $R = \begin{bmatrix} \mathbf{r}_1 & \mathbf{r}_2 \end{bmatrix}$.

(c) Substituting $A = QR$ into the projection formula and using $Q^TQ = I$:

(a) Take the determinant of $C - \lambda I$ (expanded by cofactors): $\lambda^4 - 1 = 0$. The roots of this “characteristic equation” are the eigenvalues: $+1, -1, i, -i$.

The eigenvalues of $C^2$ are just $\lambda^2 = \pm 1$ (two of each).

(Here’s a “guessing” approach. Since $C^4 = I$, all the eigenvalues $\lambda^4$ of $C^4$ are 1: so $\lambda = 1, -1, i, -i$ are the only possibilities. Just check to see which ones work. Then the eigenvalues of $C^2$ must be $\pm 1$.)

(b) For any permutation matrix, $C^{-1} = C^T$: so

and $(C^2)^{-1} = C^2$ is itself.

(c) The determinant of $C$ is the product of its eigenvalues: $1 \cdot (-1) \cdot i \cdot (-i) = -1$.

Add 1 to every eigenvalue to get the eigenvalues of $C + I$ (if $C = S\Lambda S^{-1}$, then $C + I = S(\Lambda + I)S^{-1}$): $\det(C + I) = 2 \cdot 0 \cdot (1+i)(1-i) = 0$. (Or let $\lambda = -1$ in the characteristic equation $\det(C - \lambda I)$.)

Add 2 to get the eigenvalues of $C + 2I$ (or let $\lambda = -2$): $\det(C + 2I) = 3 \cdot 1 \cdot (2+i)(2-i) = 15$.

(a) Multiply both sides of $A\mathbf{x} = \mathbf{b}$ by $A^T$ to get the normal equations:

Since the columns of $A$ are independent, $A^TA$ is invertible, so

(b) $\mathbf{p} = A\hat{\mathbf{x}}$ is a linear combination of columns of $A$, so it’s in the column space $C(A)$. The error $\mathbf{e} = \mathbf{b} - \mathbf{p}$ is orthogonal to this space, so it’s in the left nullspace $N(A^T)$.

(c) Use $P = A(A^TA)^{-1}A^T$. Since

and

(a) $\det(A_2) = 3 \cdot 3 - 1 \cdot 2 = 7$ and $\det(A_3) = 3\det(A_2) - 2 \cdot 1 \cdot 3 = 15$.

(b) Expanding by cofactors along row 1: the entry 3 multiplies the determinant $D_{n-1}$ of the same tridiagonal matrix one size smaller, and the entry 2 multiplies a cofactor whose first column has the single entry 1 — expanding that cofactor down its first column leaves $D_{n-2}$. So

that is, $a = 3$ and $b = -2$.

(c) The trace of that matrix is $a = 3$, and the determinant is $-b = 2$. So the characteristic equation is $\lambda^2 - a\lambda - b = 0$, which has roots (the eigenvalues)

$D_n$ grows at the same rate as the largest eigenvalue power: $\lambda_+^n = 2^n$.

The final point: $D_5 = 3D_4 + 2D_3 = 3(3D_3 + 2D_2) + 2D_3 = 11D_3 + 6D_2 = 11 \cdot 15 + 6 \cdot 7 = 207$.