\documentclass[12pt]{amsart}

\usepackage{241}

\title{21-241 Matrices and Linear Transformations \\
       Summer 1 2012 \\
       Course notes \\
       Day 5}
\author{Paul McKenney}


\begin{document}

\maketitle

\begin{defn}
  A linear equation with a constant term of zero, ie of the form
  \[
    a_1 x_1 + \cdots + a_n x_n = 0
  \]
  is called \emph{homogeneous}. A system of linear equations is called \emph{homogeneous} if each of its equations is homogeneous.
\end{defn}

Note that a homogeneous system always has at least one solution, namely the zero vector.
\begin{lemma}
  Let $A$ be an $m\times n$ matrix.  If $A$ is left-invertible then the \emph{only} solution to the homogeneous system $Ax = 0$ is the zero vector.
\end{lemma}
\begin{proof}
  Let $B$ be a left-inverse for $A$.  (Why is it incorrect to talk about $A^{-1}$ here?)  Then if $s$ is any solution to the homogeneous system $Ax = 0$, we have
  \[
    s = Is = (BA)s = B(As) = B0 = 0
  \]
  So in fact, $0$ is the only solution.
\end{proof}

The proof of the following lemma will have to wait for a later date.  I'll give a sketch, and an example of its use.
\begin{lemma}
  Suppose a system $Ax = b$, where $A$ is $m\times n$, has at least one solution, $p\in\RR^n$.  Let $k$ be the number of free variables in some echelon form of the system $Ax = b$.  Then there exist solutions $h_1,\ldots,h_k\in\RR^n$ to the homogeneous equation $Ax = 0$, such that
  \[
    \set{s\in\RR^n}{As = b} = \set{p + c_1 h_1 + \cdots + c_k h_k}{c_1,\ldots,c_k\in\RR}
  \]
\end{lemma}
\begin{proof}[Proof sketch.]
  The main idea here is that if $h\in\RR^n$ is any solution to the homogeneous system $Ax = 0$, then
  \[
    A(p + h) = Ap + Ah = Ap + 0 = Ap = b
  \]
  and then so is $p + h$.  Moreover if any $s\in\RR^n$ is a solution to $Ax = b$, then
  \[
    A(s - p) = As - Ap = b - b = 0
  \]
  and so $s - p$ is a solution to the homogeneous system $Ax = 0$.  This tells us that a vector $s\in\RR^n$ is a solution to $Ax = b$ if and only if it's of the form $p + h$, where $h$ is a solution to the homogeneous system $Ax = 0$.  To see that there are fixed vectors $h_1,\ldots,h_k\in\RR^n$ which generate the solutions to $Ax = 0$ will require more work; it essentially falls out of back-substitution.
\end{proof}

\begin{example*}
  The system
  \begin{LinearSystems}{5}
    x   & +  z +  w = 2 \\
   2x - y    & +  w = 1 \\
    x + y + 3z + 2w = 5 \\
  \end{LinearSystems}
  has a solution $\smat{0 \\ 0 \\ 1 \\ 1 \\}$.  What about the homogeneous system?  It reduces to
  \begin{LinearSystems}{5}
    x   & + z +  w = 0 \\
    &   y + 2z + w = 0 \\
    &   &   &    0 = 0 \\
  \end{LinearSystems}
  Then the solution set to the homogeneous system is
  \[
    \lset{z\begin{pmatrix} -1 \\ -2 \\ 1 \\ 0 \\ \end{pmatrix}
      +  w\begin{pmatrix} -1 \\ -1 \\ 0 \\ 1 \\ \end{pmatrix}}{z,w\in\RR}
  \]
  and so the solution set to the original system of equations is
  \[
    \lset{\begin{pmatrix} 0 \\ 0 \\ 1 \\ 1 \\ \end{pmatrix}
      +  z\begin{pmatrix} -1 \\ -2 \\ 1 \\ 0 \\ \end{pmatrix}
      +  w\begin{pmatrix} -1 \\ -1 \\ 0 \\ 1 \\ \end{pmatrix}}{z,w\in\RR}
  \]
\end{example*}


\begin{lemma}
  Suppose $R$ is an invertible, $n\times n$ matrix in reduced row echelon form.  Then $R = I$.
\end{lemma}
\begin{proof}
  Consider the homogeneous system $Rx = 0$.  If there were any free variables in this system, then there would be a nonzero vector $h\in\RR^n$ such that $Rh = 0$.  But as $R$ is invertible, by the lemma above this can't happen.  So there can't be any free variables in this system.  Since $R$ is in reduced row echelon form, this means exactly that $R = I_n$.
\end{proof}

\begin{lemma}
  If $A$ and $B$ are square, invertible matrices of the same size, then $AB$ is also invertible.  Moreover, $(AB)^{-1} = B^{-1}A^{-1}$.
\end{lemma}
\begin{proof}
  We have
  \[
    (AB)(B^{-1} A^{-1}) = A(BB^{-1})A^{-1} = AIA^{-1} = AA^{-1} = I
  \]
  and
  \[
    (B^{-1} A^{-1})(AB) = B^{-1}(A^{-1}A)B = B^{-1}IB = B^{-1}B = I
  \]
\end{proof}

\begin{cor}
  If $A_1,\ldots,A_k$ are square, invertible matrices of the same size, then $A_1 A_2\cdots A_k$ is also invertible, and $(A_1\cdots A_k)^{-1} = A_k^{-1}\cdots A_1^{-1}$.
\end{cor}
\begin{proof}
  By induction on $k$.  This proof is routine, but I'll include it here just to give an example of such a routine.  When $k = 1$ the statement is trivial.  So suppose it holds for $k$.  To prove it for $k+1$, let $A_1,\ldots,A_k,A_{k+1}$ be square, invertible matrices of the same size.  Then $A_1\cdots A_k$ is invertible and $(A_1\cdots A_k)^{-1} = A_k^{-1}\cdots A_1^{-1}$ by the induction hypothesis.  Hence by the above lemma, $(A_1\cdots A_k)A_{k+1}$ is invertible, and
  \[
    ((A_1\cdots A_k)A_{k+1})^{-1} = A_{k+1}^{-1} (A_1\cdots A_k)^{-1} = A_{k+1}^{-1} (A_k^{-1} \cdots A_1^{-1})
  \]
  Hence the statement is proven for $k+1$, and by induction it holds for all $k$.
\end{proof}

\begin{lemma}
  If $A$ is an invertible matrix, then so is $A^{-1}$, and $(A^{-1})^{-1} = A$.
\end{lemma}
\begin{proof}
  We have
  \[
    AA^{-1} = I\qquad A^{-1}A = I
  \]
  simply by definition of $A^{-1}$.  Then $A$ is both a left and right inverse for $A^{-1}$.
\end{proof}

We've already essentially seen the following result, but I'll repeat the proof for clarity.
\begin{lemma}
  If $E$ is an elementary matrix, then $E$ is invertible, and $E^{-1}$ is the elementary matrix which implements the row operation that reverses that which $E$ implements.
\end{lemma}
\begin{proof}
  Suppose $E$ is $m\times m$.  Let $F$ be the ($m\times m$) elementary matrix which implements the reverse of the row operation $E$ implements.  (I'm not calling it $E^{-1}$ yet because that would be presumptuous.)  Then $(EF)A = A$ and $(FE)A = A$ for all $m\times n$ matrices $A$, for all $n$.  In particular, with $A = I_m$, we get
  \[
    EF = (EF)I_m = I_m\qquad FE = (FE)I_m = I_m
  \]
\end{proof}

\begin{thm}
  Let $A$ be a square matrix.  Then $A$ is invertible if and only if $A$ is row-equivalent to $I$.
\end{thm}

\begin{proof}
  Let $R$ be the reduced row echelon form of $A$.  Since we can obtain $R$ from $A$ by row operations, there are elementary matrices $E_1,\ldots,E_k$ such that
  \[
    R = E_k E_{k-1} \cdots E_1 A
  \]
  As we've seen before, elementary matrices are invertible.  Hence by the above, $R$ is invertible, and square. Then $R$ is actually $I$.

  If $A$ is row-equivalent to $I$, then there are elementary matrices $E_1,\ldots,E_k$ such that
  \[
    E_k E_{k-1} \cdots E_1 A = I
  \]
  Then
  \[
    A = IA = (E_k E_{k-1}\cdots E_1)^{-1} (E_k E_{k-1} \cdots E_1) A = (E_k E_{k-1}\cdots E_1)^{-1} I = (E_k E_{k-1} \cdots E_1)^{-1}
  \]
\end{proof}

The proof of the theorem above actually gives us a way of computing the inverse of a square matrix.  I'll summarize it in this fact.
\begin{fact}
  Let $A$ be an invertible matrix, and let $E_1,\ldots,E_k$ be elementary matrices reducing $A$ to $I$, ie, such that
  \[
    E_k E_{k-1} \cdots E_1 A = I
  \]
  Then $A^{-1} = E_k E_{k-1} \cdots E_1 I$.  In terms of row-operations, to find the inverse of $A$, we start with $I$ and apply the same row operations we used to reduce $A$ to $I$.
\end{fact}

Typically, when finding the inverse of $A$, one performs row operations on $A$ and $I$ in parallel, as in the following example.
\begin{example*}
  Let $A = \smat{2 & 7 \\ 1 & 4 \\}$.  Then we compute $A^{-1}$ using the following.
  \begin{align*}
    & 
    \begin{pmatrix}
      2 & 7 \\
      1 & 4 \\
    \end{pmatrix}
    \qquad
    \begin{pmatrix}
      1 & 0 \\
      0 & 1 \\
    \end{pmatrix}
    \\
    \rho_1 \swap \rho_2 \qquad & 
    \begin{pmatrix}
      1 & 4 \\
      2 & 7 \\
    \end{pmatrix}
    \qquad
    \begin{pmatrix}
      0 & 1 \\
      1 & 0 \\
    \end{pmatrix}
    \\
    \rho_2 \to \rho_2 - 2\rho_1 \qquad &
    \begin{pmatrix}
      1 & 4 \\
      0 & -1 \\
    \end{pmatrix}
    \qquad
    \begin{pmatrix}
      0 & 1 \\
      1 & -2 \\
    \end{pmatrix}
    \\
    \rho_1 \to \rho_1 + 4\rho_1 \qquad &
    \begin{pmatrix}
      1 & 0 \\
      0 & -1 \\
    \end{pmatrix}
    \qquad
    \begin{pmatrix}
      4 & -7 \\
      1 & -2 \\
    \end{pmatrix}
    \\
    \rho_2 \to -\rho_2 \qquad & 
    \begin{pmatrix}
      1 & 0 \\
      0 & 1 \\
    \end{pmatrix}
    \qquad
    \begin{pmatrix}
      4 & -7 \\
      -1 & 2 \\
    \end{pmatrix}
  \end{align*}
  Now to check, we compute;
  \[
    \begin{pmatrix}
      2 & 7 \\
      1 & 4 \\
    \end{pmatrix}
    \begin{pmatrix}
      4 & -7 \\
      -1 & 2 \\
    \end{pmatrix}
     =
    \begin{pmatrix}
      1 & 0 \\
      0 & 1 \\
    \end{pmatrix}
  \]
  So it worked!
\end{example*}

\end{document}
