\documentclass{amsart}


\title{Matrix theory autumn 2011: homework 2 solutions}

\author{James Cummings}


\begin{document}

\maketitle
    
   Homework due at start of class on Wed 14 September. 



   


\section{Matrices and vectors}

\begin{enumerate}

\item  Let $A$ be an $n \times n$ matrix. The {\em trace} of $A$ (denoted by $tr(A)$) is defined to be the sum of the
    diagonal elements of $A$, that is $\sum_{i=1}^n a_{ii}$. Prove that for any two $n \times n$ matrices
    $A$ and $B$, $tr(A B) = tr(B A)$. Is it true for any three such matrices $A, B, C$ 
    we have $tr(A B C) = tr(B A C)$? 

    Let $A = (a_{ij})$ and $B = (b_{ij})$. As usual the $(i, k)$ entry of $A B$ is $\sum_j a_{i j} b_{j k}$,
    in particular the diagonal $(i, i)$ entry is $\sum_j a_{i j} b_{j i}$. So the trace of 
    $A B$ is $\sum_i( \sum_j a_{i j} b_{j i}) = \sum_{i, j} a_{i j} b_{j i}$, and by symmetry this
    is equal to the trace of $B A$. 

    The statement is not true in general even for $2 \times 2$ matrices.  It is easy
    to find a counterexample. 


\item   Let $A$ be an $n \times n$ matrix where every entry $a_{ij}$ is either $0$ or $1$. 
        Prove  that for $t > 0$ the $(i, j)$-entry in the matrix power
         $A^t$ (the product of $t$ copies of $A$) is equal to the number
        of sequences $(x_0, \ldots x_t)$ such that
\begin{enumerate}
\item  Each $x_k$ for $0 \le k \le t$  is a natural number with $1 \le x_k \le n$.
\item  $x_0 = i$ and $x_t = j$.
\item  For all $k$ with $0 \le k < t$, $a_{x_k x_{k+1}} = 1$.
\end{enumerate}

Proof 1: By induction on $t$. Let $S_t(i, j)$ be the set of integer sequences with the properties listed 
    above, so we must prove that the $(i, j)$ entry in $A^t$ is $\vert S^t(i, j) \vert$. 

Base case $t =1$: The $(i, j)$ entry in $A^1 = A$ is $a_{i j}$. A sequence $(x_0, x_1)$ is in
   $S^1(i, j)$  if and only if $x_0 = i$, $x_1 = j$, and $a_{x_0 x_1} = 1$; so there are
   no such sequences if $a_{i j}= 0$ and exactly one such sequence if $a_{i j} = 1$, establishing the
   claim for $t = 1$.

Successor step: Suppose we have the claim for $t$. Let $A^t = B$ say. Now $A^{t +1} = A A^t = A B$, and so
    by definition the $(i, j)$ entry in $A^{t+1}$ is $\sum_{k=1}^n a_{i k} b_{k j}$. Since each entry $a_{i k}$ is one or zero,
    and we have by the induction hypothesis that  $b_{k j} = \vert S^t(k, j)$,  we can write this as 
\[
   \sum_{k, a_{i k} = 1} \vert S^t(k, j) \vert.
\]
   
   Now we compare this with $\vert S^{t+1}(i, j) \vert$. For each $k$ with $1 \le k \le n$ we will count the number
   of sequences $(x_0, x_1, \ldots x_{t+1})$ in $S^{t+1}(i, j)$ with $x_1 = k$; it is easy to see that there are no
   such sequences if $a_{i k} = 0$, while if $a_{i k}= 1$ then $(i, k, x_2, \ldots x_{t+1})$ is in
   $S^{t+1}(i, j)$ if and only if $(k, x_2, \ldots x_{t+1})$ is in $S^t(k, j)$. It follows that
  $\vert S^{t+1}(i, j)\vert = \sum_{k, a_{i k} = 1} \vert S^t(k, j) \vert = \sum_{k=1}^n a_{i k} b_{k j}$,
  and we are done. 

Proof 2:  (Sketch)  Start by establishing by induction that the $(i, j)$ term in $A^t$ is
    $\sum_{k_1, \ldots k_{t-1}} a_{i k_1} a_{k_1 k_2} \ldots a_{k_{t-1} j}$ where each $k$-variable
    runs from $1$ to $n$. Now observe that since each entry in $A$ is zero or one, each term
    $a_{i k_1} a_{k_1 k_2} \ldots a_{k_{t-1} j}$ is $1$ when all the factors in it are $1$ are
    zero otherwise, so that 
    $\sum_{k_1, \ldots k_{t-1}} a_{i k_1} a_{k_1 k_2} \ldots a_{k_{t-1} j}$ is the number of sequences
    $(k_1, \ldots k_{t-1})$ such that 
    $a_{i k_1} =  a_{k_1 k_2} =  \ldots = a_{k_{t-1} j} =1$, which is easily seen to be
    $\vert S^t(i, j) \vert$. 




\item  Let $X$ be the set of all real $2 \times 2$  matrices which are of the special form
\[
\left (
\begin{array}{rr}
a & - b \\
b &   a \\
\end{array}
\right )
\] for some real numbers $a$ and $b$.
  Let $I$ be the $2 \times 2$ identity matrix, that is
\[I = 
\left (
\begin{array}{rr}
1 & 0 \\
0 & 1 \\
\end{array}
\right )
\]
  
\begin{enumerate}
\item    Prove that $X$ is closed under matrix addition and multiplication.

\[
\left (
\begin{array}{rr}
a & - b \\
b &   a \\
\end{array}
\right )
+
\left (
\begin{array}{rr}
a' & - b' \\
b' &   a' \\
\end{array}
\right )
=
\left (
\begin{array}{rr}
a + a' & - (b+b') \\
b+b' &   a + a' \\
\end{array}
\right )
\]


\[
\left (
\begin{array}{rr}
a & - b \\
b &   a \\
\end{array}
\right )
\times
\left (
\begin{array}{rr}
a' & - b' \\
b' &   a' \\
\end{array}
\right )
=
\left (
\begin{array}{rr}
a a' - b  b' &  -(a b' + a' b)   \\
a b' + a' b  &  a a' - b b'       \\
\end{array}
\right )
\]




\item    Prove that $A B = B A$ for all $A, B \in X$.


  This is immediate from the calculation in the proof of closure under
   multiplication. 


\item    Prove that if $A \in X$ and $A$ is not the zero matrix, there is $B \in X$ such that $A B = I$.

Let 
\[
A =
\left (
\begin{array}{rr}
a & - b \\
b &   a \\
\end{array}
\right )
\]
  Since $A \neq 0$ either $a \neq 0$ or $b \neq 0$, so $a^2 + b^2 \neq 0$. 
Let $c = a^2 + b^2$ and let
\[
B =
\left (
\begin{array}{rr}
a/c &  b/c \\
-b/c &  a/c \\
\end{array}
\right )
\]

  It is routine to check that this works. 


\item    Prove that there is $A \in X$ such that $A^2 = -I$.


Let 
\[
A =
\left (
\begin{array}{rr}
0 & - 1 \\
1 &   0 \\
\end{array}
\right )
\]


 
\end{enumerate}


\item  Let 
 \[
A=
\left (
\begin{array}{rr}
a & b \\
c & d \\
\end{array}
\right )
\]
 be a $2 \times 2$ real matrix. Prove that if $a d - b c < 0$ there is no matrix $B$ such that
     $A = B^2$. Is it the case that whenever $a d - b c \ge 0$ then such a matrix $B$ exists? 

Suppose that $A = B^2$ where 
\[
B =
\left (
\begin{array}{rr}
e & f \\
g & h \\
\end{array}
\right )
\]
Then

\[
A = B^2 =
\left (
\begin{array}{rr}
e^2 + f g   &  e f + f h \\
e g + g h   &  f g + h^2 \\
\end{array}
\right )
\]
 so that $a d - b c =  (e^2 + f g)(f g + h^2) - f g(e+h)^2 = e^2 h^2 + f^2 g^2 - 2 f g e h = (e h - f g)^2$,
 and hence $a d- b c \ge 0$. It follows that when $a d - bc < 0$, $A \neq B^2$ for any $B$.

On the other hand consider the matrix
\[
A =
\left (
\begin{array}{rr}
0 & 1 \\
0 & 0 \\
\end{array}
\right )
\]
  $0 \times 0 - 1 \times 0 = 0 \ge 0$, but we claim it has no square root.  
   If $A = B^2$ with $B$ as above then $e^2 + f g = 0$, $f(e + h) = 1$,
   $g(e + h) = 0$, $f g + h^2 = 0$.   Now since $f(e + h) = 1$ we see that
   $f$ and $e + h$ are nonzero, in particular by $g(e + h) = 0$ we see 
   that $g = 0$. 
   So $e^2 + 0 = 0$ and $h^2 +0 = 0$, hence $e = h = 0$. This is impossible
   as $e + h \neq 0$.    


\end{enumerate} 

\section{Mathematica} 


    This section is {\em not for credit}, {\em you may collaborate} and {\em you need not hand anything in.}
    But you still should do it because probably none of this  will be true of the computer algebra sections in later
    homeworks. 
 


\begin{enumerate}

\item  Install the student version of Mathematica (for which CMU really and truly does 
       have a license) on your personal computer. 

\item  Start Mathematica.

\item  Work through the first couple of sections of the online tutorial
       at the URL

\begin{verbatim}
http://reference.wolfram.com/mathematica/tutorial/GettingStartedOverview.html
\end{verbatim}

\item  Read enough of 

\begin{verbatim}
http://reference.wolfram.com/mathematica/howto/CreateAMatrix.html
\end{verbatim}

\noindent and

\begin{verbatim}
http://reference.wolfram.com/mathematica/guide/MatrixOperations.html
\end{verbatim}

\noindent   to figure out how to enter a matrix and do elementary matrix arithmetic.

\item  Working in Mathematica, create matrices 
\[
A = \left (
\begin{array}{cc}
1 & 2 \\
4 & 5 \\
\end{array}
\right ),
B = \left (
\begin{array}{cc}
3 & 7 \\
6 & 8 \\
\end{array}
\right ).
\]

\item   Use Mathematica to compute $A + B$, $A B$, $B A$,  $A^{100}$.
  Check the first three answers by hand. 


\item Export your results to a PDF file. 

\end{enumerate}





\end{document}



