\documentclass[12pt]{amsart}

\usepackage{241}

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

\begin{document}

\maketitle

\section{Sets, logic, and proofs}

  21-241 is a mathematics course, so inevitably we will make use of mathematical concepts introduced in the course 21-127, Concepts of Mathematics.  Since this is not an official prerequisite for the course, I will try to keep this to a minimum.  If you're confused about one of these topics, you can come to me during office hours to talk about it;  I also invite you to consult~\cite{BS}.  I've included here a table defining some of the logical notation that we'll be using.  Below, $S$ is a set, and $P$ and $Q$ are logical statements.

  \begin{table}[h]
  \begin{tabular}{cp{30ex}p{50ex}}
    Notation & Definition & Notes \\ \hline
    $x\in S$ &   ``$x$ is a member of $S$'' & Here $x$ is a \emph{free variable}. \\
    $\set{x\in S}{P(x)}$ & ``the set of all $x$ in $S$ such that $P(x)$'' & \\
    $\NN$ & $\{0,1,2,\ldots\}$ & The \emph{natural numbers}.  Note that $0\in\NN$! \\
    $\ZZ$ & $\{\ldots,-1,0,1,2,\ldots\}$ & The \emph{integers}.  \\
    $\QQ$ & $\set{p/q}{p,q\in\ZZ\land q\neq 0}$ & The \emph{rationals}.  \\
    $\RR$ & the set of all real numbers & We can't provide a true definition here.. \\
    $\CC$ & the set of all complex numbers & \\
    $\lnot P$ &   ``not $P$'' & \\
    $P\land Q$ &   ``$P$ and $Q$'' & \\
    $P\lor Q$ &   ``$P$ or $Q$'' &   This is an \emph{inclusive} or, ie, if \emph{both} $P$ and $Q$ are true, then we still consider $P\lor Q$ to be true. \\
    $P\implies Q$ &   ``$P$ implies $Q$'' &   $P\implies Q$ is considered a statement of its own, with its own truth value, which I invite you to deduce from the truth values of $P$ and $Q$.  The case when $P$ is false is particularly interesting. \\
    $P\iff Q$ &   ``$P$ if and only if $Q$'' &   This is exactly the same as $(P\implies Q)\land (Q\implies P)$. \\
    $\forall x\; P(x)$ & ``for all $x$, $P(x)$'' & Here and below $x$ is a \emph{bound variable}.  \\
    $\exists x\; P(x)$ & ``there exists an $x$ such that $P(x)$'' & \\
  \end{tabular}
  \end{table}

\section{Solving systems of linear equations}
  Consider the following chemistry problem (which I have lifted directly from Hefferon's book~\cite{H}).  I've got $x$ molecules of toluene, $C_7 H_8$, and $y$ molecules of nitric oxide, $HNO_3$.  Putting them together, I can produce trinitrotoluene (TNT), which has the form $C_7 H_5 O_6 N_3$, with some water ($H_2 O$) byproduct.  Say I produce $z$ molecules of the first and $w$ of the second.  I'd like to balance this equation;
  \[
    x C_7 H_8 + y H N O_3 \to z C_7 H_5 O_6 N_3 + w H_2 O
  \]
  That is, I'd like to find values of $x,y,z$, and $w$ so that the number of atoms of each type is the same before and after the reaction.  Counting them each individually, this leads to the following system of equations;
  \begin{align}
    7x & = 7z \\
    8x + 1y  & = 5z + 2w \\
    1y & = 3z \\
    3y & = 6z + 1w
  \end{align}
  Of course, we're only interested in nonnegative integer values of $x,y,z,w$ in this situation (since these represent the number of molecules we're dealing with), so we'll have to watch out for that when we're searching for solutions.  Equation (1) clearly implies $x = z$, and so subtracting equation (3) from equation (2), we get
  \[
    8z = 2z + 2w \implies 6z = 2w \implies w = 3z
  \]
  So if $(x,y,z,w)$ is any solution, then $x = z$, $y = 3z$, and $w = 3z$.  Moreover, it's easy to check that no matter what choice I make for the value of $z$, then letting $x = z$ and $y,w = 3z$, I get a solution to the above system, and if $z$ is a nonnegative integer then so are $x,y$, and $w$.  So I've found a solution; in fact, infinitely many!

  In general, there is a straightforward process which will tell us all of the solutions to a given system of linear equations, if there are any; and that there aren't any, if there aren't any.  This is called \emph{Gaussian elimination}.  To describe it I'll need to formally define some of the concepts we've been using informally up to now.
  \begin{defn}
    Let $x_1,\ldots,x_n$ be variables.  A \emph{linear combination} of $x_1,\ldots,x_n$ is an expression of the form $a_1 x_1 + \cdots + a_n x_n$, where $a_1,\ldots,a_n\in\RR$.  $a_1,\ldots,a_n$ are called the \emph{coefficients} of the combination.  A \emph{linear equation} in variables $x_1,\ldots,x_n$ is an equation of the form $a_1 x_1 + \cdots a_n x_n = b$, where $b\in\RR$.  $b$ is called the \emph{constant} of the equation.

    A \emph{system of linear equations} is simply a finite set of linear equations in the same variables, e.g.
    \begin{align*}
      a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n & = b_1 \\
      a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n & = b_2 \\
      \vdots \\
      a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n & = b_m \\
    \end{align*}
    A tuple $(s_1,\ldots,s_n)\in\RR^n$ is a \emph{solution} to this system of equations if the equations obtained by replacing $x_i$ by $s_i$ for each $i$, in each equation, results in unanimously true statements.   If $S$ is a system of linear equations then we write $\sol(S)$ for its set of solutions.  So $\sol(S)\subseteq\RR^n$.

    When a system of equations is written like the above, we often refer to the $i$th equation down as \emph{row $i$}, or $\rho_i$.  Of course, the order of the equations does not matter when considering solutions; it only matters to our written system.  The first term $a_{ij} x_j$ in row $i$ such that $a_{ij} \neq 0$ is called the \emph{leading term} of that row, and $a_{ij}$ the \emph{leading coefficient}.  Note that a row may not have a leading term, e.g., if all of the coefficients are zero;
    \[
      0x_1 + 0x_2 + \cdots + 0x_n = b
    \]
    
    A system is in \emph{echelon form} if the leading term of each row (except the first) is strictly to the right of all the leading terms of the rows above it, and all of the rows without a leading term are below the ones that are.  Visually;
    \begin{LinearSystems}{10}
      a_{1j_1} x_{j_1} + \cdots + a_{1j_2} x_{j_2} + \cdots + a_{1j_i} x_{j_i} + \cdots + a_{1n} x_n = b_1 \\
       & & a_{2j_2} x_{j_2} + \cdots + a_{2j_i} x_{j_i} + \cdots + a_{2n} x_n = b_2 \\
       & & & & & & & \vdots \\
       & & & & a_{ij_i} x_{j_i} + \cdots + a_{in} x_n = b_i \\
       & & & & & & 0 = b_{i\+1} \\
       & & & & & & & \vdots \\
       & & & & & &  0 = b_m \\
    \end{LinearSystems}
    Here $j_1, j_2, \ldots$, etc are the column indices of the leading terms in rows $1, 2, \ldots$, respectively, and row $i$ is the last with a leading term.


    For instance, the following is in echelon form;
    \begin{align*}
      x - 2y + z & = 0 \\
      z & = 2 \\
    \end{align*}
    However, the following system is not in echelon form.
    \begin{LinearSystems}{5}
      & y + 3z = 1 \\
      \-x - y - z = 0 \\
      & 5y - 2z = \-1 \\
    \end{LinearSystems}
  \end{defn}

  The object of Gaussian elimination is to produce, through a series of operations on a given system of linear equations, a final system which is in echelon form.  There are three different operations that we use;
  \begin{itemize}
    \item swap:   Swapping two of the equations, written $\rho_i \liff \rho_j$ (where $i\neq j$).
    \item scaling:   Multiplying some row by a nonzero number; $\rho_i\to \lambda\rho_i$, where $\lambda\neq 0$.
    \item row combination:   Replacing some row by the sum of itself with a multiple of another row; $\rho_i\to \rho_i + \lambda\rho_j$.  Here $\lambda$ may be zero but $i$ and $j$ must be different.
  \end{itemize}
  There is a systematic way of applying these operations to get a system in echelon form, but first we need to know that they won't change the solution set we're after.  This is proven in the following theorem.  

  \begin{thm}
    If $S$ is a system of linear equations and $T$ is the result of applying one of the above operations to $S$, then $S$ and $T$ have exactly the same set of solutions, ie, $\sol(S) = \sol(T)$.
  \end{thm}
  \begin{proof}
    For clarity, let's say $S$ is the following system of linear equations;
    \begin{align*}
      a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n & = b_1 \\
      a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n & = b_2 \\
      \vdots \\
      a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n & = b_m \\
    \end{align*}
    To prove the theorem it suffices to show;
    \begin{enumerate}
      \item\label{gauss.subset}  If $r\in\RR^n$ is a solution to $S$ then $r$ is also a solution to $T$.
      \item\label{gauss.reverse}  There is a row-operation which, when applied to $T$, produces $S$.
    \end{enumerate}
    \eqref{gauss.subset} proves that $\sol(S)\subseteq \sol(T)$; then, \eqref{gauss.reverse} and \eqref{gauss.subset} prove together that $\sol(T)\subseteq\sol(S)$.

    Let's prove~\eqref{gauss.subset} first.  Let $(s_1,\ldots,s_n)\in\RR^n$ be a solution to $S$.  This means we have
    \begin{align*}
      a_{11} s_1 + a_{12} s_2 + \cdots + a_{1n} s_n & = b_1 \\
      \vdots \\
      a_{m1} s_1 + a_{m2} s_2 + \cdots + a_{mn} s_n & = b_m \\
    \end{align*}
    To fully prove~\eqref{gauss.subset} we'd have to handle three cases, according to which type of row operation we applied to $S$ to get $T$; I'll just do the row-combination case, since that's the hardest.  So for some $i\neq j$ and some $\lambda\in\RR$,  $T$ is the system
     \begin{align*}
      a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n & = b_1 \\
      \vdots  \\
      (a_{i1} x_1 + \cdots a_{in} x_n) + \lambda (a_{j1} x_1 + \cdots a_{jn} x_n) & = b_i + \lambda b_j \\
      \vdots \\
      a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n & = b_m \\
    \end{align*}
    Since $(s_1,\ldots,s_n)$ is a solution to $S$, we have $a_{i1} s_1 + \cdots a_{in} s_n = b_i$ and $a_{j1} s_1 + \cdots a_{jn} s_n = b_j$, so
    \[
      (a_{i1} s_1 + \cdots a_{in} s_n) + \lambda (a_{j1} s_1 + \cdots a_{jn} s_n) = b_i + \lambda b_j
    \]
    The other equations in $T$ are the same as those in $S$.  Hence $(s_1,\ldots,s_n)$ is a solution to $T$.

    Now we prove~\eqref{gauss.reverse}.  This comes down to another proof by cases, based on which type of row operation we applied to get $T$ from $S$.  I'll write the row operation down along with its reverse.
    \begin{itemize}
      \item To reverse a swap $\rho_i\liff\rho_j$, we just apply the same swap again; $\rho_i\liff\rho_j$.
      \item To reverse a row combination $\rho_i\to \rho_i + \lambda\rho_j$ we apply the row combination $\rho_i\to \rho_i - \lambda\rho_j$.  (It's implicit that $i\neq j$, here.  Why is this important?)
      \item To reverse a scaling operation $\rho_i\to \lambda\rho_i$, we apply $\rho_i\to\frac{1}{\lambda}\rho_i$.  (Here it's implicit that $\lambda\neq 0$.)
    \end{itemize}
    This completes the proof of the theorem.
    
  \end{proof}

  Now I'll describe the \emph{Gaussian elimination} algorithm.  Let $S$ be the following system.
  \begin{align*}
    a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n & = b_1 \\
    a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n & = b_2 \\
    \vdots \\
    a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n & = b_m \\
  \end{align*}
  Perform the following operations for each $i$ from $1$ to $m$ in that order, or until I tell you to stop.
  \begin{itemize}
    \item  Find the row, below row $i$, with the leftmost leading term among those rows.  If there is no such thing (ie, if $a_{jk} = 0$ for all $j \ge i$ and $1\le k\le m$), stop.  Otherwise, swap this row with row $i$.
    \item  Say the leading coefficient in row $i$ is in column $j$.  For each $k > i$, perform the row combination $\rho_k \to \rho_k - (a_{kj}/a_{ij})\rho_i$.
    \item  Repeat.
  \end{itemize}
  After the first $i$ steps of this algorithm, we've ensured that the leading terms of the first $i$ rows go from left to right (this is easily proven by induction on $i$).  If we go through every row, then we've ensured that the leading terms are ordered this way throughout the whole matrix.  If we stop at row $i$, then none of the rows below have leading terms.  Either way, after finishing, the system is in echelon form.

  So what do we do with this?  First, let's consider the equations without leading terms.  They look something like this;
  \[
    0x_1 + 0x_2 + \cdots + 0x_n = b
  \]
  This equation is either true or false outright, depending on whether $b = 0$ or $b\neq 0$.  If $b\neq 0$ then we call the equation \emph{inconsistent}.  If, after performing Gaussian elimination to bring a system into echelon form, we find an inconsistent equation at the bottom, then we've determined that it has no solutions, since no system with an inconsistent equation can have a solution.  But what if there are no inconsistent equations at the bottom?  Do we have solutions in this case?

  \emph{Back-substitution} is the algorithm which shows that indeed, the answer is yes.  To perform back-substitution we perform the following operations for each $i$, starting with the largest $i$ such that row $i$ has a leading variable, and going down to $1$.
  \begin{itemize}
    \item  Solve equation $i$ for the leading variable, in terms of all the other variables in equation $i$.
    \item  In your formula for the leading variable, for each $j > i$, replace the leading variable of row $j$ with formula you found for it previously.
  \end{itemize}
  After this process ends, you've found a formula for each leading variable in the system, in terms of only the free variables.  Any choice of values for the free variables then results in a solution to the given system of linear equations.

\end{document}
