\documentclass[11pt]{article}
\textwidth = 17cm
\textheight = 25.5cm
\hoffset = -2.8cm
\voffset = -2cm

\pagestyle{empty}

\usepackage{latexsym,amssymb,amsmath}

\def\C{\mathbb{C}}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\H{\mathbb{H}}
\def\N{\mathbb{N}}
\def\Ucal{\mathcal{U}}
\def\n{\noindent}


\begin{document}

\begin{center}
\textsc{Algebra (MA 183) 2008-2009} \\
\smallskip
\textbf{Solutions to Homework Problems 2} \\
\smallskip
\end{center}

\medskip

\begin{enumerate}

\item[2.]
Let $A=\left(\begin{array}{rr} a_1 & b_1 \\ c_1 &
  d_1\end{array}\right)$, 
$B=\left(\begin{array}{rr} a_2 & b_2 \\ c_2 & d_2\end{array}\right)$. 
Then 
$$
AB = \left(\begin{array}{rr} a_1a_2+b_1c_2 & a_1b_2+b_1d_2 \\
c_1a_2+d_1c_2 & c_1b_2+d_1d_2\end{array}\right),
$$
and 
\begin{eqnarray*}
\det (AB) & = &
(a_1a_2+b_1c_2)(c_1b_2+d_1d_2)-(a_1b_2+b_1d_2)(c_1a_2+d_1c_2) \\
& = & a_1a_2d_1d_2 + b_1c_2c_1b_2 - a_1b_2d_1c_2 - b_1d_2c_1a_2 \\
& = & a_1d_1(a_2d_2-b_2c_2)-b_1c_1(a_2d_2-b_2c_2) \\
& = & (a_1d_1-b_1c_1)(a_2d_2-b_2c_2) \\
& = & \det (A) \det (B).
\end{eqnarray*}
\item[(b)] Suppose that $A$ and $B$ both have inverses, denoted by
  $A^{-1}B^{_1}$ respectively. Then 
$$
(AB)(B^{-1}A^{-1}) = A(bb^{-1})A^{-1} = AI_2A^{-1}=AA^{-1}=I_2.
$$
Similarly $(B^{-1}A^{-1})(AB)=I_2$, and so $B^{-1}A^{-1}$ is the
inverse of the matrix $AB$.

\item[3.]
\begin{itemize}
\item[(a)]
A typical point on the line $L$ has coordinates $(t,\frac{4-t}{2})$,
where $t$ is a real number. To find the typical coordinates of
the image under $T$ of a point of $L$, calculate the matrix product 
$$
\left(\begin{array}{rr}1 & 4 \\ -2 & 2 \end{array}\right)
\left(\begin{array}{r} t \\ \frac{4-t}{2}\end{array}\right)  
= 
\left(\begin{array}{r} t+2(4-t) \\ -2t+4-t\end{array}\right) 
=
\left(\begin{array}{r} 8-t \\ 4-3t \end{array}\right) 
$$
Thus if $(x,y)$ is a point on the image of $L$ under $T$, then for
some real number $t$ we have $x=8-t$ and $y=2-t$. Thus $t=8-x$ and
$y=4-3(8-x)=3x-20$. So the image of $L$ under $T$ is the line with
equation $3x-y=20$. 

\item[(b)] 
The equation of the line to which $L$ is mapped by $T$ is the image of
$L$ under the inverse of $T$. The matrix of the inverse of $T$ is the
inverse of the matrix of $T$. This is 
$$
\frac{1}{10}\left(\begin{array}{rr}2 & -4 \\ 2 & 1\end{array}\right).
$$
We can proceed as above to find the coordinates of a typical point of
the image of $L$ under $T^{-1}$. 
$$
\frac{1}{10}\left(\begin{array}{rr}2 & -4 \\ 2 &
  1\end{array}\right)\left(\begin{array}{r} t \\
    \frac{4-t}{2}\end{array}\right) =
\frac{1}{10}\left(\begin{array}{r}2t-2(4-t) \\
  2t+\frac{4-t}{2}\end{array}\right) = 
\frac{1}{10}\left(\begin{array}{r} 4t-8 \\
  2+\frac{3}{2}t\end{array}\right).
$$
Thus if $(x,y)$ is a point on the image of $L$ under $T^{-1}$, then for
some real number $t$ we have $x=\frac{4t-8}{10}$ and
$y=\frac{1}{10}(2+\frac{3}{2}t)$. Thus $t=\frac{10x+8}{4}$ and 
$$
y=\frac{1}{10}\left(2+\frac{3}{2}\left(\frac{10x+8}{4}\right)\right).
$$ 
Simplifying gives $3x-8y+4=0$ : this is the equation of the line which
is mapped by $T$ to $L$.
\end{itemize}



\item[6.]
Suppose that $T:\R^n\longrightarrow \R^p$ is a linear transformation
with matrix $M_T$. Suppose also that $S:\R^q\longrightarrow\R^m$ is a
linear transformation with matrix $M_S$. 
\begin{enumerate}
\item If $p=4$ and $n=6$, how many rows and how many columns are in
  the matrix $M_T$?
\item If $M_S$ is a $5\times 7$ matrix, what is $m$ and what is $q$?
\item Under what conditions on $n,p,q,m$ is the composition $T\circ S$
  defined?
\item Under what conditions on $n,p,q,m$ is the matrix product
  $M_SM_T$ defined?
\item Suppose that $A$ and $B$ are matrices. Explain in your own words
  why the matrix product $AB$ can be defined only if the number of
  columns in $A$ is equal to the number of rows in $B$.
\end{enumerate}

\n\emph{Solution}:
\begin{enumerate}
\item $4$ rows, $6$ columns. 
\item $m=5,\ q=7$.
\item $T\circ S$ is defined if $m=n$.
\item $M_SM_T$ is defined if the composition $S\circ T$ is defined,
  i.e. if $p=q$.
\end{enumerate}



\item[7.]
\begin{itemize}
\item[(a)] 
The characteristic polynomial of $B$ is 
$$
\det(\lambda I_2 -B) = \det \left(\begin{array}{cc} 
\lambda -2 & 3 \\ 1 & \lambda-4\end{array}\right) = 
(\lambda -2)(\lambda -4)-(3)(1) = \lambda^2-6\lambda +5.
$$
\item[(b)] 
The eigenvalues are the solutions of the equation $\lambda^2-6\lambda
+5 = 0$, i.e. $(\lambda -5)(\lambda -1)=0$, eigenvalues $\lambda_1 =
5$, $\lambda_2 = 1$.
\item[(c)] 
For $\lambda_1 = 5$ :
$$
\left(\begin{array}{rr} 2 & -3 \\ -1 & 4 \end{array}\right)
\left(\begin{array}{r} x \\ y\end{array}\right) = 5
\left(\begin{array}{r} x \\ y\end{array}\right)
\Longrightarrow 
\begin{array}{rcrcr}
2x & - & 3y & = & 5x \\
-x & + & 4y & = & 5y
\end{array}
$$
Both these equations say $x = -y$; any non-zero vector $\binom{x}{y}$
whose components satisfy this equation is an eigenvector of $B$
corresponding to the eigenvalue 5 : for example $\binom{-1}{1}$.

\medskip

For $\lambda_2 = 1$ :
$$
\left(\begin{array}{rr} 2 & -3 \\ -1 & 4 \end{array}\right)
\left(\begin{array}{r} x \\ y\end{array}\right) = 1
\left(\begin{array}{r} x \\ y\end{array}\right)
\Longrightarrow 
\begin{array}{rcrcr}
2x & - & 3y & = & x \\
-x & + & 4y & = & y
\end{array}
$$
Both these equations say $x = 3y$; any non-zero vector $\binom{x}{y}$
whose components satisfy this equation is an eigenvector of $B$
corresponding to the eigenvalue 1 : for example $\binom{3}{1}$.

\item[(d)]
$E = \left(\begin{array}{rr} -1 & 3 \\ 1 & 1\end{array}\right),\ \ 
D = \left(\begin{array}{rr} 5 & 0 \\ 0 & 1\end{array}\right)$.

\item[(e)] $B^6 = (EDE^{-1})^6 = ED^6E^{-1}$. Thus 
\begin{eqnarray*}
B^6 & = & \left(\begin{array}{rr} -1 & 3 \\ 1 & 1\end{array}\right)
\left(\begin{array}{cc} 5^6 & 0 \\ 0 & 1^6\end{array}\right)
\frac{1}{-4}\left(\begin{array}{rr} 1 & -3 \\ -1 &
  -1\end{array}\right) \\
 & = & 
-\frac{1}{4}
\left(\begin{array}{rr} -5^6 & 3 \\ 5^6 & 1\end{array}\right)
\left(\begin{array}{rr} 1 & -3 \\ -1 &
  -1\end{array}\right) \\
& = & 
-\frac{1}{4}
\left(\begin{array}{rr} 
-5^6-3 & 3(5^6)-3  \\ 5^6-1 & -3(5^6)-1\end{array}\right) \\
& = & 
\left(\begin{array}{rr} 3907 & -11718 \\ -3906 & 11719
\end{array}\right) \\
\end{eqnarray*}
\end{itemize}


\item[9.]
\begin{enumerate}
\item[(a)] This is a matter of straightforward checking.
\item[(b)] The recurrence relations can be written in matrix form as 
$$
\left(\begin{array}{l}F_{n+2} \\F_{n+1}\end{array}\right) = 
\left(\begin{array}{rr}1 & 1 \\ 0 & 1 \end{array}\right)
\left(\begin{array}{l}F_{n+1} \\ F_n\end{array}\right)
$$
for $n\ge 0$.  \\
Write $A = \left(\begin{array}{rr} 1 & 1 \\ 0 & 1\end{array}\right)$. 
Then 
$$
\left(\begin{array}{l}F_{n+1} \\F_{n}\end{array}\right) = 
A^n
\left(\begin{array}{l}F_1 \\ F_0 \end{array}\right) = 
A^n
\left(\begin{array}{l}0 \\ 1 \end{array}\right) 
$$
So we need to calculate $A^n$. The characteristic polynomial of $A$ is $\lambda^2-\lambda-1$ which has roots 
$$
a=\frac{1+\sqrt{5}}{2},\ b=\frac{1-\sqrt{5}}{2}.
$$
To find an eigenvector of $A$ corresponding to the eigenvalue $a$, we need 
$$
\left(\begin{array}{rr} 1 & 1 \\ 0 & 1\end{array}\right)
\left(\begin{array}{l} x \\ y\end{array}\right) = a
\left(\begin{array}{l} x \\ y\end{array}\right)
\Longrightarrow
\begin{array}{rcrcr} 
x & + & y & = & ax \\
x & & & = & ay
\end{array}
$$
Since $a^2-a-1=0$, $\frac{1}{a}=a-1$ and both equations say
$a=ay$. Thus $\binom{a}{1}$ is an eigenvector of $A$ corresponding to
the eigenvalue $a$. Similarly $\binom{b}{1}$ is an eigenvector of  $A$
corresponding to $b$ as an eigenvalue. \\  
Thus $A^n=ED^nE^{-1}$ where  
$$
E=\left(\begin{array}{rr} a & b \\ 1 & 1\end{array}\right),\ 
D=\left(\begin{array}{rr} a & 0 \\ 0 & b\end{array}\right). 
$$
Then 
\begin{eqnarray*} 
A^n & = & \left(\begin{array}{rr} a & b \\ 1 &
  1\end{array}\right)\left(\begin{array}{rr} a^n & 0 \\ 0 &
    b^n\end{array}\right)
\frac{1}{a-b}
\left(\begin{array}{rr} 1 & -b \\ -1 &
  a\end{array}\right) \\
& = & 
 \ \\
& = & 
\frac{1}{a-b}
\left(\begin{array}{rr} a^{n+1} & b^{n+1} \\ a^n &
    b^n\end{array}\right)
\left(\begin{array}{rr} 1 & -b \\ -1 &
  a\end{array}\right) \\
\ \\
& = & 
\frac{1}{a-b}
\left(\begin{array}{rr} a^{n+1}-b^{n+1} & -ba^{n+1}+ab^{n+1} \\ a^n-b^n &
  -ba^n+ab^n\end{array}\right)
\end{eqnarray*}
Now 
$$
\left(\begin{array}{l}F_{n+1} \\F_{n}\end{array}\right) =
A^n\left(\begin{array}{l}1 \\ 0\end{array}\right) = 
\frac{1}{a-b}
\left(\begin{array}{rr} a^{n+1}-b^{n+1} & -ba^{n+1}+ab^{n+1} \\ a^n-b^n &
  -ba^n+ab^n\end{array}\right)
\left(\begin{array}{l}1 \\ 0\end{array}\right) = 
\left(\begin{array}{l}
a^{n+1}-b^{n+1} \\a^n-b^n\end{array}\right).
$$
Looking at the second entries here gives 
$$
F_n = \frac{1}{a-b}(a^n-b^n) = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right),
$$
as required.



\end{enumerate}

\end{enumerate}

\end{document}
