\documentclass[12pt]{article}
\pagestyle{empty}
\usepackage{amssymb}
\usepackage{latexsym}
\title{MA20008 Algebra 1, 2004, Sheet 6 Solutions}
\author{Geoff Smith, {\tt http://www.bath.ac.uk/$\sim$masgcs}}
\date{}
\begin{document}
\maketitle
\begin{enumerate}
\item {\em Let $V$ be a vector space of dimension
$n$. Suppose that $\alpha: V \rightarrow V$ is a linear
map. Show that the following are equivalent.}
\begin{enumerate}
\item {\em $\alpha$ is injective.}
\item {\em $\alpha$ is bijective.}
\item {\em $\alpha$ is surjective.}
\item {\em There is a basis ${\bf v_1}, \ldots, {\bf v_n}$ of $V$ such that
$\alpha({\bf v_1}), \ldots, \alpha({\bf v_n})$ is a basis of $V$.}
\item {\em For every basis ${\bf v_1}, \ldots, {\bf v_n}$ of $V$, the vectors
$\alpha({\bf v_1}), \ldots, \alpha({\bf v_n})$ also form a basis of $V$.}
\end{enumerate}
\noindent {\bf Solution\ } The rank nullity theorem tells us that
$\alpha$ is injective if and only if it is surjective. Therefore
(a), (b) and (c) are equivalent. Now (c) implies (e) since 
a spanning set must map to a spanning set, and a spanning set of
size $n$ must be a basis. Certainly (e) implies (d). However, condition (d)
forces the image of $\alpha$ to include a spanning set, and so (c) is forced.
We are done.

\item {\em Suppose that 
\[ X = \left( \begin{array}{cc} A & B\\
0 & C\end{array}\right)\]
is a $2r$ by $2r$ matrix built from the four $r$ by $r$ matrices
$A, B, C$ and the zero matrix $0$. Suppose that $X$ has an inverse matrix.
Describe that matrix in terms of $A, B, C$ and $0$.} 
\newline \noindent {\bf Solution\ } Let the inverse matrix 
be of the shape \[ Y = \left( \begin{array}{cc} D & E\\ F & G 
\end{array}\right)\] where $D, E, F$ and $G$ are $r$ by $r$ matrices.
Now 
\begin{enumerate}
\item $AD + BF = I_r$, \item $AE + BG = 0$, \item $CF = 0$ and \item
$CG = I_r$.
\end{enumerate} From (d) $G = C^{-1}.$ From (c) and premultiplication
by $C^{-1}$ we obtain $F = 0$. Next (a) forces $D = A^{-1}$ an d
(b) implies that  $AE + BC^{-1}= 0$ so $E = - A^{-1}BC^{-1}$.

\item {\em The matrix 
\[ F = \left( \begin{array}{cc} 1 & 1\\
1 & 0\end{array}\right) \] has entries in the Field $F_7$, the integers
modulo $7$. Calculate} 
\begin{enumerate}
\item $F^2$.
\item $F^5$.
\item $F^{1000}$.
\item \[ \sum_{i= 0}^{999} F^i\]
{\em where $F^0$ denotes the identity matrix.}
\end{enumerate}
\noindent {\bf Solution\ } For integers $n \geq 0$ define the
Fibonacci sequence mod $7$ via $F_0 = 0$ and $F_1 = 1$ where
$F_0, F_1 \in \mathbb Z_7.$ Then inductively $F_n = F_{n-1} + F_{n-2}$
whenever $n \geq 2$. Thus
\[ (F_n) = 0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1, \ldots.\]
Thus $F_{16} =0$ and $F_{17} = 1$ so $(F_n)$ is periodic
with fundamental period 16. Now
\[ F^n = \left( \begin{array}{cc} F_{n+1} & F_n\\
F_n & F_{n-1}\end{array}\right) \] by induction on $n$.
Therefore 
\begin{enumerate}
\item \[ F^2 =  \left( \begin{array}{cc} F_3 & F_2\\
F_2 & F_1\end{array}\right) =
\left( \begin{array}{cc} 2  & 1\\
1 & 1\end{array}\right).\]
\item \[ F^5 =  \left( \begin{array}{cc} F_6 & F_5\\
F_5 & F_4\end{array}\right) =
\left( \begin{array}{cc} 1  & 5\\
5 & 3\end{array}\right).\]
\item \[ F^{1000} =  \left( \begin{array}{cc} F_{1001} & F_{1000}\\
F_{1000} & F_{999} \end{array}\right) =
\left( \begin{array}{cc} F_9  & F_8 \\
F_8 & F_7\end{array}\right) = 
\left( \begin{array}{cc} 6  & 0 \\
0 & 6 \end{array}\right).\]
\item {\em The matrix
\[ F = \left( \begin{array}{cc} 1 & 1\\
1 & 0\end{array}\right) \] has entries in $\mathbb Q$,
Let $I$ denote the 2 by 2 identity matrix.
Show that $I$ and $F$ are linearly independent but
that $I, F$ and $F^2$ are linearly dependent elements
of the vector space of $2$ by $2$ matrices with rational entries
(with scalars in $\mathbb Q$).}\newline \noindent {\bf Solution\ }
By inspection or from the Fibonacci recurrence $F^2 = F+1$
so $F^2 - F -1$ is a non-trivial linear relation among
$1$, $F$ and $F^2$. Suppose that $\lambda, \mu \in \mathbb Q$
and $\lambda I + \mu F = 0$ then 
\begin{enumerate}
\item $\lambda + \mu = 0$,
\item $\mu = 0$,
\item $\lambda + \mu = 0$ and
\item $ 0 + 0 = 0$.
\end{enumerate}
by inspecting the four positions in turn. These equations
force $\lambda = \mu = 0$ as required.
\end{enumerate}
\item {\em Suppose that $\alpha, \beta: V \longrightarrow V$ are a 
pair of commuting linear maps.} 
\begin{enumerate}
\item {\em Prove that both $\mbox{Im }\alpha$
and $\mbox{Ker }\alpha$ are $\beta$-invariant spaces.}
\newline \noindent {\bf Solution }
Suppose that ${\bf v} \in \mbox{Im }\alpha$
so there is ${\bf u} \in V$ such that $\alpha({\bf u} ) = {\bf v}.$
Now $\beta({\bf v}) =\beta(\alpha({\bf u} )) = \alpha(\beta({\bf u} )) 
\in \mbox{Im }\alpha.$  ON the other hand, suppose that
${\bf x} \in \mbox{Ker }\alpha$, then $\alpha(\beta({\bf x}))
= \beta(\alpha({\bf x}))
= \beta({\bf 0}) = {\bf 0}.$ Thus $\beta({\bf x}) \in \mbox{Ker }\alpha$
as required.
\item {\em Prove that $\mbox{Im }\alpha + \mbox{Im }\beta$ is
both $\alpha$-invariant and $\beta$-invariant.} \newline
\noindent {\bf Solution\ }Each of $\mbox{Im }\alpha$
and $\mbox{Im }\beta$ is both $\alpha$-invariant and $\beta$-invariant.
It follows that their sum has the same property, because if ${\bf x} \in
\mbox{Im }\alpha$ and ${\bf y} \in
\mbox{Im }\beta$, then $\alpha ({\bf x}+{\bf y}) = \alpha ({\bf x})
+ \alpha({\bf y})$ which is the sum of two vectors, the first of which is
in $\mbox{Im }\alpha$ and the second in $\mbox{Im }\beta$.  The sum of subspaces
is also $\beta$-invariant by symmetry.
\item {\em Prove that $\mbox{Im }\alpha \cap \mbox{Im }\beta$ is
both $\alpha$-invariant and $\beta$-invariant.}  \newline
\noindent {\bf Solution\ } This is a formality. If ${\bf x}$ is in the intersection,
then $\alpha({\bf x}) \in \mbox{Im }\alpha$ and $\alpha({\bf x}) \in \mbox{Im }\beta$
so  $\alpha({\bf x})\in \mbox{Im }\alpha \cap \mbox{Im }\beta$. The same holds
for $\beta$ by symmetry.
\end{enumerate}
\end{enumerate} 
\end{document}
