
# 16.2: Review Problems

1.
Consider an arbitrary matrix $$M:\Re^{m}\to \Re^{n}.$$

a)    Argue that $$Mx=0$$ if only if $$x$$ is perpendicular to all columns of $$M^{T}$$.

b)    Argue that $$Mx=0$$ if only if $$x$$ is perpendicular to all of the linear combinations of the columns of $$M^{T}$$.

c)    Argue that $$\ker M$$ is perpendicular to $${\rm ran} \,M^{T}$$.

d)    Argue further $$\Re^{m}=\ker M \oplus {\rm ran}\, M^{T}$$.

e)    Argue analogously that $$\Re^{n}=\ker M^{T} \oplus {\rm ran}\, M$$.

The equations in the last two parts describe how a linear transformation $$M:\Re^{m}\to \Re^{n}$$ determines orthogonal decompositions of both it's domain and target.  This result sometimes goes by the humble name $$\textit{The Fundamental Theorem of Linear Algebra}$$.

2.    Let $$L \colon V\rightarrow W$$ be a linear transformation.  Show that $$\ker L=\{0_{V}\}$$ if and only if $$L$$ is one-to-one:

a)    $$\textit{(Trivial kernel \(\Rightarrow$$ injective.)}\) Suppose that $$\ker L=\{0_V\}$$. Show that $$L$$ is one-to-one.  Think about methods of proof--does a proof by contradiction, a proof by induction, or a direct proof seem most appropriate?

b)    $$\textit{(Injective \(\Rightarrow$$ trivial kernel.)}\) Now suppose that $$L$$ is one-to-one. Show that $$\ker L=\{0_{V}\}$$.  That is, show that $$0_{V}$$ is in $$\ker L$$, and then show that there are no other vectors in $$\ker L$$.

3.    Let $$\{v_{1}, \ldots, v_{n} \}$$ be a basis for $$V$$.  Carefully explain why
$L(V)= span \{Lv_{1}, \ldots, Lv_{n} \}.$

4.    Suppose $$L \colon \Re^{4}\rightarrow \Re^{3}$$ whose matrix $$M$$ in the standard basis is row equivalent to the following matrix:
$\begin{pmatrix} 1&0&0&\!-1\\ 0&1&0&1\\ 0&0&1&1\\ \end{pmatrix}={\rm RREF}(M)\sim M.$

a)    $$\textit{Explain}$$ why the first three columns of the original matrix $$M$$ form a basis for $$L(\Re^{4})$$.

b)    $$\textit{Find and describe}$$ an algorithm ($$\textit{i.e.}$$, a general procedure) for computing a basis for $$L(\Re^{n})$$ when $$L \colon \Re^{n}\rightarrow \Re^{m}$$.

c)    $$\textit{Use}$$ your algorithm to find a basis for $$L(\Re^{4})$$ when $$L \colon \Re^{4} \to \Re^{3}$$ is the linear transformation whose matrix $$M$$ in the standard basis is
$\begin{pmatrix} 2&1&1&4\\ 0&1&0&5\\ 4&1&1&6\\ \end{pmatrix}.$

5.    Claim:
If $$\{v_{1}, \ldots, v_{n} \}$$ is a basis for $$\ker L$$, where $$L \colon V\rightarrow W$$, then it is always possible to extend this set to a basis for $$V$$.
Choose some simple yet non-trivial linear transformations with non-trivial kernels and verify the above claim for those transformations.

6.    Let $$P_{n}(x)$$ be the space of polynomials in $$x$$ of degree less than or equal to $$n$$, and consider the derivative operator $$\frac{d}{dx}:P_{n}(x)\to P_{n}(x)\, .$$
Find the dimension of the kernel and image of this operator.  What happens if the target space is changed to $$P_{n-1}(x)$$ or $$P_{n+1}(x)$$?

Now consider $$P_{2}(x,y)$$, the space of polynomials of degree two or less in $$x$$ and $$y$$.  (Recall how degree is counted; $$xy$$ is degree two, $$y$$ is degree one and $$x^{2}y$$ is degree three, for example.)  Let
$$L:=\frac{\partial}{\partial x}+\frac{\partial}{\partial y}:P_{2}(x,y) \to P_{2}(x,y).$$
(For example, $$L(xy)=\frac{\partial}{\partial x}(xy)+\frac{\partial}{\partial y}(xy) = y+x$$.)  Find a basis for the kernel of $$L$$.  Verify the dimension formula in this case.

7.
Lets demonstrate some ways the dimension formula can break down if a vector space is infinite dimensional:

a)    Let $$\mathbb{R}[x]$$ be the vector space of all polynomials in the variable $$x$$ with real coefficients.  Let $$D = \frac{d}{dx}$$ be the usual derivative operator.  Show that the range of $$D$$ is $$\mathbb{R}[x]$$.  What is $$\ker D$$?  $$\textit{Hint: Use the basis \({ x^{n} \mid n \in \mathbb{N} }.$$}\)

b)    Let $$L \colon \mathbb{R}[x] \rightarrow \mathbb{R}[x]$$ be the linear map $$L(p(x)) = xp(x)\, .$$  What is the kernel and range of $$M$$?

c)    Let $$V$$ be an infinite dimensional vector space and $$L \colon V \rightarrow V$$ be a linear operator.  Suppose that $$\dim \ker L < \infty$$, show that $$\dim L(V)$$ is infinite.  Also show that when $$\dim L(V) < \infty$$ that $$\dim \ker L$$ is infinite.

8.    This question will answer the question, "If I choose a bit vector $$\textit{at random}$$, what is the probability that it lies in the span of some other vectors?''

[$$i.$$]    Given a collection $$S$$ of $$k$$ bit vectors in $$B^{3}$$, consider the bit matrix $$M$$ whose columns are the vectors in $$S$$.  Show that $$S$$ is linearly independent if and only if the kernel of $$M$$ is trivial, namely the set $${\rm ker}M=\{v\in B^{3}| \, Mv=0\}$$ contains only the zero vector.

[$$ii.$$]    Give some method for choosing a random bit vector $$v$$ in $$B^{3}$$.  Suppose $$S$$ is a collection of $$2$$ linearly independent bit vectors in $$B^{3}$$.  How can we tell whether $$S\cup \{v\}$$ is linearly independent?  Do you think it is likely or unlikely that $$S\cup \{v\}$$ is linearly independent?  Explain your reasoning.

[$$iii.$$]    If $$P$$ is the characteristic polynomial of a $$3 \times 3$$ bit matrix, what must the degree of $$P$$ be?  Given that each coefficient must be either 0 or 1, how many possibilities are there for $$P$$?  How many of these possible characteristic polynomials have $$0$$ as a root?  If $$M$$ is a $$3 \times 3$$ bit matrix chosen at random, what is the probability that it has 0 as an eigenvalue?  (Assume that you are choosing a random matrix $$M$$ in such a way as to make each characteristic polynomial equally likely.)  What is the probability that the columns of $$M$$ form a basis for $$B^{3}$$?  $$(\textit{Hint: what is the relationship between the kernel of \(M$$ and its eigenvalues?})\)

[Note:]    We could ask the same question for real vectors:  If I choose a real vector at random, what is the probability that it lies in the span of some other vectors?  In fact, once we write down a reasonable way of choosing a random real vector, if I choose a real vector in $$\Re^{n}$$ at random, the probability that it lies in the span of $$n-1$$ other real vectors is zero!