\documentclass{amsart}


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

\author{James Cummings}


\begin{document}

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



\section{Sets and logic}


\begin{enumerate}


\item  Using truth tables or otherwise, prove that:

\begin{enumerate}

\item  ``A implies B'' is logically equivalent to ``not-A or B''.

    A couple of proofs:

\smallskip

Proof 1: To show that two propositions are equivalent it is enough to show that they are true 
         in exactly the same circumstances, or that they are false in exactly the same circumstances.

         ``$A$ implies $B$'' is false $\iff$ $A$ is true and $B$ is false
          $\iff$ ``not $A$'' is false  and $B$ is false 
          $\iff$ ``not $A$ or $B$'' is false.

\smallskip

Proof 2: Truth table proof. 

\smallskip 

\begin{displaymath}
\begin{array}{|c|c|c|c|c|c}
   A
 & B
 & A \implies B
 & \lnot{}A
 & B
 & \lnot{}A \lor B \\
\hline
F & F & T & T & F & T \\
F & T & T & T & T & T \\
T & F & F & F & F & F \\
T & T & T & F & T & T \\
\hline
\end{array}
\end{displaymath}

\smallskip 

\item  ``not-(A or B)'' is logically equivalent to ``not-A and not-B''.


\smallskip

Proof 1: ``not-(A or B)'' is true $\iff$ ``$A$ or $B$'' is false 
         $\iff$  $A$ is false and $B$ is false 
         $\iff$  ``not $A$'' is true and ``not $B$'' is true 
         $\iff$  ``not-$A$  and not-$B$'' is true.


\smallskip 
 

\smallskip

Proof 2: Truth table proof. 

\smallskip 

\begin{displaymath}
\begin{array}{|c|c|c|c|c|c|c}
   A
 & B
 & A \lor B
 & \lnot(A \lor B)
 & \lnot{}A
 & \lnot{}B
 & \lnot{}A \land \lnot{}B \\
\hline
F & F & F & T & T & T & T \\
F & T & T & F & T & F & F \\
T & F & T & F & F & T & F \\
T & T & T & F & F & F & F \\
\hline
\end{array}
\end{displaymath}

\smallskip 




\item  ``not-(A implies B)'' is logically equivalent to ``A and not-B''.
       
\smallskip

  We could do it by either of the methods used above, but it's quicker to
    combine the previous two results.

``not-(A implies B)'' $\iff$ ``not-(not-A or B)''
 $\iff$ ``not-(not-A) and not-B''
$\iff$ ``A and not-B''.

\smallskip

\end{enumerate}


\item  Recall that the basic operations on sets are intersection, union and set difference.
       Let $X$ be a set, let $\phi(x)$ and $\psi(x)$ be properties that elements $x \in X$
       may have. Let $A = \{ x \in X: \phi(x) \}$ and let $B = \{ x \in X : \psi(x) \}$.
       Describe (with proof) each of the following sets in terms of the basic operations:

\begin{enumerate}

\item  $\{ x \in X : \text{not  $\phi(x)$} \}$.

We claim this is $X \setminus A$, which we prove by showing that the two sets have the same members.
 $y \in X \setminus A$  $\iff$ $y \in X$ and $y \notin A$ $\iff$ $y \in X$ and not $\phi(x)$
  $\iff$ $y \in \{ x \in X : \text{not  $\phi(x)$} \}$.


\item  $\{ x \in X : \text{$\phi(x)$ or $\psi(x)$} \}$.

$A \cup B$. 

$y \in A \cup B$ $\iff$ $y \in A$ or $y \in B$ $\iff$ ($y \in X$ and $\phi(y)$) or
   ($y \in X$ and $\psi(y)$) $\iff$ $y \in X$ and ($\phi(x)$ or $\psi(x)$) 
  $\iff$ $y \in \{ x \in X : \text{$\phi(x)$ or $\psi(x)$} \}$.

\item  $\{ x \in X : \text{$\phi(x)$ implies $\psi(x)$} \}$.


$(X \setminus A) \cup B$.

  We use an earlier problem. 
$y \in (X \setminus A) \cup B$ $\iff$ $y \in X$ and  ($y \notin A$ or $y \in B$)
   $\iff$ $y \in X$ and  ($\phi(x)$ implies $\psi(x)$)


 

\end{enumerate} 



\end{enumerate}








\section{Linear equations}


\begin{enumerate}

\item 
 Consider  linear systems in two variables $x,y$  of the general form
\begin{eqnarray*}
    x + 2 y & = & 1 \\
    a x + y & = & b \\
\end{eqnarray*}
    where $a, b$ are constants. 

    For which values of $a, b$ does this system have

\begin{enumerate}

\item  Exactly one solution?

\item  No solutions?

\item  Infinitely many solutions? 

\end{enumerate} 


  Before we start, a note on the logic of equation solving. Suppose we have a set $E = \{ e_1, \ldots e_m \}$
  of equations. By algebraic manipulation we may deduce some new equations $F = \{ e_{m+1}, \ldots e_n \}$.
  Assuming we did not make an algebra mistake every solution of $E$ is a solution of $F$, but in general
  $F$ may have more solutions. For example if we square the equation $x=2$ we get $x^2 = 4$. For the
  purposes of this question we want to be careful about this issue. 


    We start by eliminating $y$, which we do by subtracting twice equation two from equation one.
    Key point: the new  system below is equivalent to the system we started with, since we can recover
    the old system by adding twice the second equation of the new system to the first equation of the 
    new system.
\begin{eqnarray*}
    (1 - 2 a) x & = & 1 -2 b \\
    a x + y & = & b \\
\end{eqnarray*}

   Claim: if $2 a \neq 1$ there is a unique solution.

   Proof: Since $2 a -1$ we can divide by it to determine the value of $x$, then use $y = b - a x$ to
   find $y$. 

   So suppose now that $2 a = 1$. The first equation is only solvable if $b = 1/2$, and in this 
   case it becomes the identity $0 = 0$. So if $b \neq 1/2$ there is no solution, while if 
   $b = 1/2$ then any choice of $(x, y)$ such that $y = b - ax$ works.  

\end{enumerate} 



\section{Matrices and vectors}

\begin{enumerate}

\item 
   Linear transformations. 


\begin{enumerate}

\item   Prove that if $T$ is a linear transformation then there is exactly one matrix $A$ as above. 

     By definition there is at least one such $A$. To show it is unique suppose that 
   $B$ is any matrix with the required property. By inspecting $T(1,0)$ and $T(0,1)$ we can
   deduce the entries in the first and second columns of $B$, so there is only one 
   possibility for $B$. 


\item 
 Prove that a rotation by $\phi$ radians about the origin $(0, 0)$ is a linear transformation
     and describe the corresponding matrix. 

    We compute the image of the point $(x, y)$. This point is reached by starting at the origin,
    going $x$ units along the
    $x$-axis and then $y$ units along the $y$-axis. So if $T$ is the rotation map then $T(x, y)$
    is obtained by going $x$ units along the line which makes an angle $\phi$ with the $x$-axis
    (which by trigonometry brings us to $(x \cos(\phi), x \sin(\phi))$), and then $y$ units
    along the line which makes an angle $\phi  + \pi/2$ with the $x$-axis
    (which brings us to $(x \cos(\phi) - y \sin(\phi),  x \sin(\phi) + y \cos(\phi))$).
 
    A little thought shows that
\[
\left ( 
  \begin{array}{r}
 x \cos(\phi) - y \sin(\phi)   \\ 
 x \sin(\phi) + y \cos(\phi) \\
\end{array}
\right )
= 
\left (
\begin{array}{rr}
\cos(\phi) & -\sin(\phi) \\
\sin(\phi) & \cos(\phi) \\
\end{array}
\right )
\left ( 
  \begin{array}{r}
x \\ 
y \\
\end{array} 
\right )
\]



\item  
 Prove that the translation $(x, y) \mapsto (x+1, y+1)$ is {\em not} a linear transformation. 

   It is easy to see that any linear transformation fixes $(0,0)$. 



\item 
  Consider the line $L$ with equation $y = a x$. Is reflection in $L$ a linear transformation?
      If yes find the corresponding matrix. 

     We compute the image of the point $P = (x, y)$.

      If $a =0$ then the line is $y = 0$ and the image is just $(x, -y)$.  

      So suppose that $a \neq 0$.  Let $Q =(x_0, y_0)$ be the point on $y =a x$ closest
     to $(x, y)$. If $y \neq a x$ then the line $PQ$ has slope $-a^{-1}$ 
     so we have equations $y_0 = a x_0$ and $y - y_0 = -a^{-1}(x - x_0)$.
     Some tedious algebra gives $x_0 = b^{-1}(y + x a^{-1})$ and 
     $y_0 = a x_0$ where $b = a + a^{-1}$. This formula also works when
     $y = a x$. 

     Now easily the reflection of $(x, y)$ has coordinates $(2 x_0 - x, 2 y_0 - y)$ and
\[
     2 x_0 - x = 2 b^{-1} y + (2 b^{-1} a^{-1} - 1) x,
     2 y_0 - y = (2 a b^{-1} - 1) y + 2 b^{-1} x.
\]
     So the final matrix is
\[
\left (
\begin{array}{rr}
 2 b^{-1} a^{-1} - 1 & 2 b^{-1} \\
 2 b^{-1} &  2 a b^{-1} - 1 \\
\end{array} 
\right )
\]

   


     

\item 
 Let $A_\phi$ be the matrix for rotation by $\phi$. Prove that $A_\phi A_\psi = A_{\phi + \psi}$. 

  Routine calculation. 



\end{enumerate} 


\item 
  Let $X$ be the set of $2 \times 2$ real matrices.  Prove or give a counterexample to
      each of the following statements:

\begin{enumerate}

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

   True: the $(i, j)$ entry is $a_{ij} + b_{ij} = b_{ij} +a_{ij}$.


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

    False: let
\[ 
A =\left (
\begin{array}{rr}
 0  & 0 \\
 0 &  1 \\
\end{array}
\right )
\]
and
\[ 
B =\left (
\begin{array}{rr}
 0  & 1 \\
 0 &  0 \\
\end{array}
\right )
\]


\item 
 $A^2 = 0$ implies $A =0$ for all $A \in X$.

False: look at $B$ from the last part, $B^2 = 0$ but $B \neq 0$.  

\item 
  $A A^2 = A^2 A$ for all $A \in X$. 

     True by associativity of matrix multiplication. 


\end{enumerate} 


\section{Maple} 

    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 Maple sections in later
    homeworks. 
 


\begin{enumerate}

\item Either install Maple (CMU has a license)  on your personal computer or find a public workstation
   which has it installed. 


\item  Start Maple. 

\item  Open up a new Maple worksheet.

\item  Load the ``LinearAlgebra'' package with the command \texttt{with(LinearAlgebra);}

\item  Locate the online help for the LinearAlgebra package.

\item  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 Maple to compute $A + B, A B, B A,  A^{100}$.

\item Export your results to a PDF file. 

\end{enumerate}



\end{enumerate} 




\end{document}



