\magnification=\magstep1
\def\sol{\bigskip\item{}{\it Solution:} }
\centerline{Mathematics 244, section 1 -- Linear Algebra}
\centerline{Solutions for Final Exam Review Questions}
\centerline{May 4, 2007}
\bigskip
\noindent
I.  The following matrix is the augmented matrix for a system
of 3 linear equations in 4 unknowns.  For which value(s) of $a \in {\bf R}$
does the system have a solution?  Find all solutions for those $a$.
$$\pmatrix{-1& 2& 0 &1& |&2\cr
            3& 1& 3 &0& |&0\cr
            1&12& 6 &5& |&a\cr}$$
\sol
Applying row operations,
$$\eqalign{
\pmatrix{-1& 2& 0 &1& |&2\cr
            3& 1& 3 &0& |&0\cr
            1&12& 6 &5& |&a\cr}
&\sim 
\pmatrix{1& -2& 0 &-1& |&-2\cr
         0&  7& 3 & 3& |& 6\cr
         0& 14& 6 & 6& |& a + 2\cr}\cr
&\sim
\pmatrix{1& -2& 0 &-1& |&-2\cr
         0&  7& 3 & 3& |& 6\cr
         0&  0& 0 & 0& |& a - 10\cr}\cr}$$
The system is inconsistent unless $a = 10$.  When $a = 10$,
we continue reducing to row-reduced echelon form:
$$ \sim \pmatrix{1&  0& 6/7 &-1/7& |&-2/7\cr
                 0&  1& 3/7 & 3/7& |& 6/7\cr
                 0&  0& 0 & 0& |& 0 \cr}$$
Here, $x_3$ and $x_4$ are free variables.  The solutions in parametric form:
$$\pmatrix{x_1 \cr x_2 \cr x_3 \cr x_4} = 
\pmatrix{-2/7 \cr 6/7 \cr 0 \cr 0} + x_3 \pmatrix{-6/7 \cr -3/7 \cr 1 \cr 0} +
x_4 \pmatrix{1/7 \cr -3/7 \cr 0 \cr 1},$$
where $x_3$ and $x_4$ are arbitrary real numbers.
\bigskip
\noindent
II.  Let $V = P_4({\bf R})$, and let 
$W = \{p(x) \in V : p'(1) = 0\ {\rm and}\ p(0) = 3p(2)\}$.
\item{A)}  Show that $W$ is a vector subspace of $V$.
\sol
Let $p,q \in W$, so $p'(1) = q'(1) = 0$ and $p(0) = 3p(2)$, $q(0) = 3q(2)$.
Then 
$$(p+q)'(1) = p'(1) + q'(1) = 0 + 0 = 0,$$
and 
$$(p+q)(0) = p(0) + q(0) = 3p(2) + 3q(2) = 3(p+q)(2).$$
Hence $W$ is closed under sums.  In addition, if $r \in {\bf R}$,
$$(rp)'(1) = rp'(1) = r\cdot 0 = 0$$
and
$$(rp)(0) = r\cdot p(0) = r \cdot 3p(2)  = 3(rp)(2).$$
Hence $W$ is also closed under scalar multiples, and a subspace of $V$.
\bigskip
\item{B)}  Find a subset $S \subset W$ such that 
$W = {\rm Span}(S)$.
\sol
Write $p \in V$ as $p = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4$.
Then the equations $p'(1) = 0$ and $p(0) = 3p(2)$ say
$$\eqalign{0 &= a_1 + 2a_2 + 3a_3 + 4a_4\cr
           0 &= 2a_0 + 6a_1 + 12a_2 + 24a_3 + 48 a_4\cr}$$
In matrix form this is the homogenenous system $Aa = 0$ for
$$A = \pmatrix{0 & 1 & 2 & 3 & 4\cr
               2 & 6 & 12& 24& 48\cr}$$
(and $a = $ the vector of coefficients -- the coordinate vector
of $p$ with respect to the standard basis in $V$).  The row-reduced
echelon form is
$$E = \pmatrix{1 & 0 & 0 & 3 & 12\cr
           0 & 1 & 2 & 3 & 4\cr}$$
There are three free variables, so the dimension of the space
of solutions is three.  
$$S = {\rm Span}\{-2x + x^2, -3 - 3x + x^3, -12 -4x + x^4\}$$
is a set that spans $W$.  (Note: these are the polynomial forms 
of the coordinate vectors spanning the solutions of the echelon form system $Ea = 0$.)
\bigskip
\item{C)}  Is your set $S$ linearly independent?
Justify your assertion.
\sol
Yes it is linearly independent.  If 
$$0 = c_1(-2x + x^2) + c_2(-3 - 3x + x^3)+ c_3(-12 -4x + x^4),$$
then equating coefficients of $x^2$ on both sides, $c_1 = 0$.
Similarly $c_2 = c_3 = 0$ from the coefficients of $x^3$ and $x^4$.
(Recall, this is a general property of the spanning set of the null
space of a matrix computed from the row-reduced echelon form.)
\bigskip
\noindent
III.  Let $V$ be a vector space.  Show that a set $S \subset V$
is linearly dependent if and only if there is some
${\bf x} \in S$ such that ${\bf x}$ is a linear combination of the
vectors in ${\rm Span}(S - \{{\bf x}\})$.
\bigskip
\sol
See class notes.
\bigskip
\noindent
IV.  All parts of this problem refer to the linear mapping 
$T : {\bf R}^4 \to {\bf R}^3$ defined by
$$T(x_1,x_2,x_3,x_4) = (4x_1 - 3x_2 + 2x_3 - x_4, x_2 + x_3, x_1 - x_4)$$
({\it Added note:}  all vectors here are written as row vectors
to save space, but you should read them as column vectors -- that is,
transpose them -- to perform
the calculations in the following questions.)
\item{A)}  Find the matrix of $T$ with respect to the standard
bases in the domain and target.
\sol
By the standard recipe
$$\eqalign{
T(e_1) = T(1,0,0,0) = (4,0,1)\cr
T(e_2) = T(0,1,0,0) = (-3,1,0)\cr
T(e_3) = T(0,0,1,0) = (2,1,0)\cr
T(e_4) = T(0,0,0,1) = (-1,0,-1)\cr}$$
Hence
$$[T]_{std \leftarrow std} = \pmatrix{4 & -3 & 2 & -1\cr
                                      0 & 1 & 1& 0\cr
                                      1 & 0 & 0 & -1\cr}.$$
\item{B)} Find the matrix of $T$ with respect to the basis
$${\cal B} = \{(1,-1,0,0),(1,1,0,0),(0,0,2,3),(0,0,-1,2)\}$$
in the domain and 
$${\cal C} = \{(0,0,1),(0,-1,1),(-1,1,0)\}$$
in the target.  
\sol
By the change of coordinates formula 
$$\eqalign{
[T]_{{\cal C} \leftarrow {\cal B}} &= 
P_{{\cal C} \leftarrow std} [T]_{std \leftarrow std} P_{std \leftarrow {\cal B}}\cr
&= \pmatrix{0 & 0 & -1\cr
            0 & -1& 1\cr
            1 & 1 & 0\cr}^{-1}
\pmatrix{4 & -3 & 2 & -1\cr
         0 & 1 & 1& 0\cr
         1 & 0 & 0 & -1\cr}
\pmatrix{1 & 1& 0 & 0\cr
         -1 & 1& 0 & 0\cr
         0 & 0 & 2 & -1\cr
         0 & 0 & 3 & 2\cr}\cr
&=\pmatrix{1&1&1\cr
          -1&-1&0\cr
          -1&0&0\cr}
\pmatrix{7&1&1&-4\cr
         -1&1&2&-1\cr
         1&1&-3&-2\cr}\cr
&=\pmatrix{7&3&0&-7\cr
         -6&-2&-3&5\cr
         -7&-1&-1&4\cr}.}$$
\vfill\eject
\noindent
V.   Show by mathematical induction that the determinant
of an $n\times n$ upper-triangular matrix $A = (a_{ij})$ is 
the product of the diagonal entries:  
$\det(A) = a_{11}a_{22} \cdots a_{nn}$.
\sol
The base case is trivial: For a $1\times 1$ matrix
$$\det(a_{11}) = a_{11}$$
by definition.
Now assume that the result is true for all $k \times k$ upper-triangular 
matrices, and consider a $(k+1)\times (k+1)$ upper-triangular matrix $A$.
Expanding along row $k+1$, we see
$$\det(A) = 0 + \cdots + 0 + (-1)^{2k + 2} a_{k+1,k+1}\det(A_{k+1,k+1}).$$
The matrix $A_{k+1,k+1}$ is an upper-triangular $k\times k$ matrix.
So the induction hypothesis shows that 
$$\det(A_{k+1,k+1}) = a_{11} \cdots a_{kk}.$$
Hence
$$\det(A) = a_{k+1,k+1} a_{11} \cdots a_{kk} = a_{11} \cdots a_{kk} a_{k+1,k+1},$$
which is what we wanted to show.

\bigskip
\noindent
VI.  Let 
$$A = \pmatrix{2&9&0\cr
               1&2&-1\cr
               0&0&5\cr}$$
\item{A)}  Find the eigenvalues of $A$.
\sol
The characteristic polynomial is
$$\det(A - \lambda I) = \det\pmatrix{2-\lambda&9&0\cr
                                     1&2-\lambda&-1\cr
                                     0&0&5-\lambda\cr}$$
Expanding along the third row
$$= (5 - \lambda)\det\pmatrix{2-\lambda&9\cr
                             1&2-\lambda\cr} = (5 - \lambda)(\lambda^2 - 4\lambda - 5)
= (5 - \lambda)^2(-1 - \lambda)$$
The eigenvalues are $\lambda = 5$ (multiplicity 2), and $\lambda = -1$.
\item{B)}  For each eigenvalue $\lambda$, find a basis
of ${\rm Nul}(A - \lambda I)$.
\sol
For $\lambda = 5$,
$$A - 5I = \pmatrix{-3&9&0\cr
                    1&-3&-1\cr
                    0 & 0 & 0\cr} 
\sim
\pmatrix{1&-3&0\cr
         0&0&1\cr
         0 & 0 & 0\cr} $$
There is only one free variable in the echelon form 
system.  
So a basis for ${\rm Nul}(A - 5I)$ is 
$$\left\{\pmatrix{3\cr 1\cr 0}\right\}.$$
Then, for $\lambda = -1$,
$$A + I = \pmatrix{ 3&9&0\cr
                    1&3&-1\cr
                    0&0&6\cr} 
\sim
\pmatrix{1&3&0\cr
         0&0&1\cr
         0&0&0\cr} $$
There is alson only one free variable in the echelon form 
system.  
So a basis for ${\rm Nul}(A + I)$ is 
$$\left\{\pmatrix{-3\cr 1\cr 0}\right\}.$$
\item{C)}  Is $A$ diagonalizable?  Explain.
\sol
$A$ is {\it not} diagonalizable because 
$$\dim{\rm Nul}(A - 5I) + \dim{\rm Nul}(A + I) = 2$$
(not 3).
\bigskip
\noindent
VII.  True - False.  For each true statement give a brief proof.  For
each false statement give a counterexample or a reason.
\item{A)}  If ${\bf y}, {\bf z}$ are two fixed vectors in 
${\bf R}^n$, then the mapping $T : {\bf R}^n \to {\bf R}^n$
defined by 
$$T({\bf x}) = ({\bf x}\cdot {\bf y}) {\bf y} + 
({\bf x}\cdot {\bf z}) {\bf z}$$
is linear.
\sol
This is {\bf True}.  To prove it, use the fact that
the dot product is linear in the first variable.  
\bigskip
\item{B)} No matter what the entries $a,b,c \in {\bf R}$ are, 
all the roots of the characteristic polynomial of the 
matrix $A = \pmatrix{a&b \cr b&c}$ are real.  
\sol
This is {\bf True}.  For the proof, use the quadratic
formula to determine the roots of the characteristic polynomial.
Both roots are real because the discriminant (the expression
in the square root) is always $\ge 0$.
This fact was also derived in class -- see the notes.
(Or, you could also say:  This follows from the Spectral
Theorem since $A$ is a symmetric matrix.)
\bigskip
\item{C)} If $A \in M_{2\times 5}({\bf R})$,
then for every $b \in {\bf R}^2$ the general solution of the 
equation $Ax = b$ contains three arbitrary constants.
\sol
This is {\bf False}.  The system could be inconsistent
(so there are no solutions at all).  For instance
to make a counterexample, let 
$$A = \pmatrix{1 & 0 & 0 & 0 & 0 \cr
               0 & 0 & 0 & 0 & 0\cr}$$
and let $b$ be any vector in ${\bf R}^2$ whose second
component is nonzero.  Then $b$ is not in the column space
of $A$, and there are no solutions of $Ax = b$.
\bigskip
\item{D)}  If $A$ is an $n\times n$ matrix and $\det(A^2 - 49I) = 0$,
then there exists a nonzero vector $x$ such that $Ax = 7x$.  
\sol
This is {\bf False}.  This would say that $\lambda = 7$
must be an eigenvalue of $A$.  But here is a counterexample:
$$A = \pmatrix{-7&0\cr
                0&-7\cr}.$$
Note that $\lambda = +7$ is not an eigenvalue of $A$, but $\lambda = 49$ is 
an eigenvalue of 
$$A^2 = \pmatrix{49&0\cr
                 0&49\cr}.$$
\item{E)}  If $A,B \in M_{n\times n}({\bf R})$, and
$B = Q^{-1}AQ$ for some invertible $n\times n$ matrix $Q$, then
$\det(B) = \det(A)$. 
\sol
This is {\bf True}.  For the proof, use standard properties of determinants
(the product formula, the inverse formula).
\bigskip 
\item{F)}  If $A \in M_{6 \times 9}({\bf R})$ then  
$\dim {\rm Col}(A)$ can equal 8.
\sol
This is {\bf False}.  The column space of $A$ is a subspace of 
${\bf R}^6$.  No subspace of ${\bf R}^6$ has dimension larger than $6$.
\bigskip  
\item{G)}  If $A \in M_{6 \times 9}({\bf R})$ then  
$\dim {\rm Nul}(A)$ is at most 6.
\sol
This is also {\bf False}.  Counterexample: If $A$ is the $6\times 9$ 
zero matrix, then $\dim{\rm Nul}(A) = 9$ (it's all of ${\bf R}^9$). 
\bigskip
\item{H)}  If $A \in M_{6 \times 9}({\bf R})$ and  
$\dim {\rm Nul}(A) = 4$, then $\dim {\rm Col}(A) = 5$.
\sol 
This is {\bf True}.  Proof uses the fact that if $A$ is $m\times n$, then 
$$\dim {\rm Nul}(A) + \dim {\rm Col}(A) = n.$$
\item{I)}  If $U$ is a $7\times 3$ matrix whose columns $\{u_1,u_2,u_3\}$
form an orthonormal set in ${\bf R}^7$, then $u_1, u_2, u_3$ are 
eigenvectors of the $7\times 7$ matrix $UU^t$.
\sol
This is {\bf True}.  They are all eigenvectors with eigenvalue $1$.
Because of the orthonormality, $U^t u_1 = e_1$, $U^t u_2 = e_2$ and 
$U^t u_3 = e_3$ (the standard basis vectors in ${\bf R}^3$. 
Therefore, $UU^t u_i = Ue_i = u_i$ for $i = 1, 2, 3$.  
\bigskip
\item{J)}  If $A$ is a $3\times 3$ matrix with eigenvalues $\lambda = 2,5,-7$
then Cramer's Rule can be used to solve $Ax = b$ for all
$b \in {\bf R}^3$. 
\sol
This is {\bf True}.  The determinant of $A$ is the value of the characteristic
polynomial at $\lambda = 0$.  Since we know the roots, the polynomial
factors as 
$$\det(A - \lambda I) = (2 - \lambda)(5 - \lambda)(-7 - \lambda).$$
Therefore $\det(A) = -70 \ne 0$.  It follows that $A$ is invertible,
so Cramer's Rule can be used to solve $Ax = b$ no matter what $b$ is.
\bigskip
\noindent
VIII. ({\it more challenging})
\bigskip
\item{A)}  Show that there exists a basis $\{p_1(x), p_2(x), p_3(x)\}$
for $V = P_2({\bf R})$ satisfying 
$$\matrix{p_1(0) = 1, &p_1(1) = 0, &p_1(2) = 0\cr
          p_2(0) = 0, &p_2(1) = 1, &p_2(2) = 0\cr
          p_3(0) = 0, &p_3(1) = 0, &p_3(2) = 1\cr}$$
Be sure to say how you know your polynomials form a basis for $V$.
\sol
To get a quadratic polynomial $p_1$ that satisfies $p_1(1) = p_1(2) = 0$,
note that $x = 1,2$ are the roots.  So the polynomial must factor as
$$p_1(x) = c(x - 1)(x - 2)$$
for some constant $c$.  The constant must be chosen to get
$p_1(0) = 1$, so $c = 1/2$.  Hence $p_1(x)$ can be written as 
$$p_1(x) = {(x - 1)(x - 2)\over (0 - 1)(0 - 2)}$$
Similarly, the other two polynomials are
$$p_2(x) = {(x - 0)(x - 2)\over (1 - 0)(1 - 2)}$$
and 
$$p_3(x) = {(x - 0)(x - 1)\over (2 - 0)(2 - 1)}$$
To see that these are a basis for $P_2({\bf R})$, note that this
vector space has dimension 3 (the standard basis
$\{1,x,x^2\}$ has three elements).  Hence to show a set of three
polynomials in here is a basis, we only have to show that
it is linearly independent.    If
$$0 = c_1 p_1(x) + c_2 p_2(x) + c_3 p_3(x)$$
for all $x$, then substituting $x = 0$ gives
$$0 = c_1\cdot 1 + c_2 \cdot 0 + c_3 \cdot 0.$$
Hence $c_1 =0$.  Similarly, setting $x = 1$ and $x = 2$ shows
$c_2 = c_3 = 0$ also.
\bigskip
\item{B)}  Suppose you knew that the polynomial
$q(x)$ satisfied $q(0) = 8$, $q(1) = -3$ and $q(2) = 4$.
What would the expansion of $q(x)$ in terms of the 
basis $\{p_1(x),p_2(x),p_3(x)\}$ be?
\sol
The expansion is
$$q(x) = 8p_1(x) + (-3)p_2(x) + 4p_3(x).$$
(Note what happens if you substitute $x = 0, 1, 2$ here.)
\bigskip
\item{C)}  Generalize what you did in part A to show that
given any three distinct real numbers $a,b,c$, there exists
a basis $\{p_1(x), p_2(x), p_3(x)\}$ of $V = P_2({\bf R})$ satisfying 
$$\matrix{p_1(a) = 1, &p_1(b) = 0, &p_1(c) = 0\cr
          p_2(a) = 0, &p_2(b) = 1, &p_2(c) = 0\cr
          p_3(a) = 0, &p_3(b) = 0, &p_3(c) = 1\cr}$$
\sol
Following the recipe from part A, the desired basis is 
$$\left\{ {(x - b)(x - c)\over (a - b)(a - c)}, 
{(x - a)(x - c)\over (b - a)(b - c)}, {(x - a)(x - b)\over (c - a)(c - b)}\right\}$$
Note that $a,b,c$ must be distinct or else we would be dividing by zero,
and who knows what would happen then?  The paper might burst into flames
or something similarly dire!
The given equations imply linear independence as in part A.
\noindent
{\it Added Note:}  The $p_i(x)$ are called
{\it Lagrange interpolating polynomials}.  If you are taking Numerical 
Analysis next year, you will use this idea {\it a lot}(!)
\bigskip
\noindent
IX.  ({\it more challenging})
\item{A)} Show that if ${\bf x}$ is an eigenvector of 
a matrix $A$ with 
eigenvalue $\lambda$, then ${\bf x}$ is also an eigenvector of $A^2$.
\sol
We have 
$$A^2{\bf x} = A(A{\bf x}) = A(\lambda {\bf x}) = \lambda (A{\bf x}) = \lambda(\lambda {\bf x}) = \lambda^2 {\bf x}.$$
Hence ${\bf x}$ is an eigenvector of $A$ with eigenvalue $\lambda^2$.
\item{B)} Suppose that $A$ is symmetric with 
eigenvalues $\lambda_1, \ldots, \lambda_n$, 
and corresponding eigenvectors ${\bf x}_1,\ldots, {\bf x}_n$ forming an orthonormal
basis of ${\bf R}^n$.  Let $P_1, \ldots, P_n$
be the matrices of the orthogonal projections onto the lines spanned
by the eigenvectors of $A$.  Explain why
$$A^2 = \lambda_1^2 P_1 + \cdots + \lambda_n^2 P_n,$$
using the Spectral Theorem.
\sol
Using the fact that $A$ is symmetric, the matrix $A^2$ satisfies 
$$(A^2)^t = (AA)^t = A^t A^t = A A = A^2.$$
Therefore, $A^2$ is also symmetric.  The Spectral Theorem
applied to $A$ says that there is an orthonormal basis 
$\{u_1, \ldots, u_n\}$ of ${\bf R}^n$ consisting of eigenvectors
of $A$.  But part A shows that the $u_i$ are also eigenvectors of $A^2$:
$$A u_i = \lambda_i u_i \Rightarrow A^2 u_i = \lambda_i^2 u_i.$$
The second part of the Spectral Theorem (the spectral decomposition)
then shows
$$A^2 = \lambda_1^2 u_1u_1^t + \cdots + \lambda_n^2 u_nu_n^t.$$
The matrix $P_i = u_i u_i^t$, so this is what we wanted to show.
\bigskip 
\item{C)} Verify that the formula in part B is true in the 
case of the $2\times 2$ symmetric matrix 
$A = \pmatrix{4&1\cr 1&4}$.
\sol
The spectral decomposition of $A$ is 
$$A = 5\cdot \pmatrix{1/2 & 1/2\cr
                      1/2 & 1/2\cr} + 3\cdot \pmatrix{1/2 & -1/2\cr
                                                      -1/2 & 1/2\cr}$$
Then
$$5^2\cdot \pmatrix{1/2 & 1/2\cr
                      1/2 & 1/2\cr} + 3^2\cdot \pmatrix{1/2 & -1/2\cr
                                                      -1/2 & 1/2\cr}
=\pmatrix{17 & 8\cr 8 & 17\cr} = A^2$$
which is what we wanted to show.
\bye

