\documentclass[12pt]{article}
\usepackage{palatino, euler, amsmath, amssymb}
\usepackage{nils}

\newcommand{\noi}{\noindent}
%\renewcommand{\section}[1]{\medskip \noi \textbf{#1}\\}
%\renewcommand{\subsection}[1]{\medskip \noi \emph{#1}\\}

% Augmented matrices, like [A|b]
\newcommand{\augmatrix}[2]{\left[\begin{matrix}#1\end{matrix}\right\vert\left.\begin{matrix}#2\end{matrix}\right]}

\begin{document}
\noi \textsf{\Large{Solving linear equations}}
\vspace{.5in}

\section{Solving one equation: review}
Given a system of linear equations $Ax=b$, we can solve this equation
by Gau\ss-Jordan elimination. By solve we mean:
\begin{itemize}
 \item determine if a solution exists
 \item if so, find all possible solutions, which effectively is:
  \begin{itemize}
   \item find the kernel of $A$ (solve the homogeneous equation $Ax=0$)
   \item find a particular solution
  \end{itemize}
\end{itemize}
We do this by reducing the augmented matrix $[A|b]$ to a row-reduced
echelon matrix $[A'|b']$ (note that $b$ changes to $b'$ in the
process), from which we can read off the answer.

Suppose $A'$ has $k$ rows (that is, $A$ has rank $k$), and the pivots
are in columns $c_1,\dots,c_k$. Then:
\begin{itemize}
 \item a solution exists iff $b'$ vanishes after the $k$th entry:\\
   i.e., it's $b'=(b'_1,b'_2,\dots,b'_k,0,\dots,0)$ -- this is because
   otherwise we have a $0=1$ row.
 \item to find all possible solutions
  \begin{itemize}
   \item the kernel of $A$ is exactly ``the pivot equals minus the
   later terms in that row''
   \item a particular solution is ``put the $b'_i$ coordinate in the
   $c_i$th entry of $x$ (formally, $x_{c_i}=b'_i$).
  \end{itemize}
\end{itemize}
The above notation is confusing, but the idea is simple -- let's
illustrate.

For instance, if $[A'|b']$ is
$$\augmatrix{1&2&\\&&1\\&&\ }{4\\7\\0}$$
(I've left spaces for zeros, for readability), then:

The \Def{pivots}\footnote{I don't know if this usage is correct:
the point is that these are the ``unfree'' variables.} (the leading
$1$s in some rows) are $x_1$ and $x_3$, while $x_2$ is the
\Def{free variable}: we can set it to whatever we want (b/c the pivots
can be adjusted to compensate).

The solution is:
\begin{itemize}
 \item the system is \Def{consistent} (meaning it has a solution), as
   we have zeros opposite the zero rows
 \item the solution is given by:
  \begin{itemize}
   \item the kernel is the subspace of $\bR^3$ such that $x_1+2x_2=0$
  (so $x_1=-2x_2$) and $x_3=0$; in general we'd have more equations,
  but they'd all be of this form: some pivot equals negative the later
  coordinates in that row (or zero if there aren't any).
  So $\ker A$ is
  $$\begin{bmatrix}
-2x_2\\
 x_2\\
 0\end{bmatrix}$$
  For clarity, one often writes $r,s,t$ for the free variables, so
  $$\ker A = \begin{bmatrix}
-2r\\
 r\\
 0\end{bmatrix}$$

   \item A specific solution in $x_0=(4,0,7)$
     (i.e., $x_1=4, x_2=0, x_3=7$): the pivots tell us
     where to put the numbers so they'll end up in the right place.
  \end{itemize}
  Thus the general solution is:
$$x_0 + \ker A
= \begin{bmatrix}
4\\
0\\
7\end{bmatrix}
+ \begin{bmatrix}
-2r\\
r\\
0\end{bmatrix}
= \begin{bmatrix}
4-2r\\
r\\
7\end{bmatrix}$$
\end{itemize}

\section{Solving many equations}
The above shows how you can solve one particular equation, but what
if you want to solve many, like $Ax=b_i$. Maybe every day your boss
comes by
and gives you a $b_i$ to solve, and you really don't want to have to
do everything \emph{again}.

What's the solution? Well, every time you row reduce $[A|b]$, you'll
get the same $A'$, but maybe a different $b'$ -- so all you need to do
is record the sequence of row moves and apply this to each $b_i$.

Recall that a row operation is just left-multiplication by an
elementary matrix, so multiplying these together yields a matrix such
that left-multiplication by it does all of the row operations.
Call this matrix $R$, so $RA=A'$, and thus $R[A|b]=[A'|b']$.

So given $A$, compute $R$ (and in the process $A'$) and you're set!
Now given $b$, just compute $b'=Rb$ and you can read the solutions to
$A'x=b'$ straight off the matrix as above.

How can you compute $R$? Concretely, you can do this by looking at
the augmented matrix $[A|I]$ -- then Gau\ss-Jordan yields $[A'|R]$:
each row operation you do on the $A$ part gets recorded on the $I$
part.

\section{Special cases}
\subsection{Span}
Given a collection of vectors $\seq{v_1,\dots,v_l}$ where $v_i\in
\bR^n$, asking ``is $w$ in the span of $\seq{v_i}$, and if so,
express it'' is exactly the same as solving the equation
$Ax=b$ where $A$ is the column matrix of the $v_i$ and $b=w$.

If we want to solve this for any $w$ that's handed to us, just find
$A'$ and $R$ (as above), and run the machine.

\subsection{Invertible Matrices}
A particularly interesting case is when the rref matrix $A'$ is the
identity matrix $I_n$ (just $1$s on the diagonal); note that this can
only possible occur if $A$ is square, i.e., a map
$A\from \bR^n \to \bR^n$ between spaces of the same dimension.

In that case there's no kernel (the kernel is $x_i=0$ for all $i$),
and the image is the whole space -- the solution is exactly $x=b'$.

In that case $RA=I_n$, and $R=A^{-1}$.

For instance, for $A=\psmallmatrix{5&6\\4&5}$, we get
$A^{-1}=\psmallmatrix{5&-6\\-4&5}$; in equations, $Ax=b$ is solved by
applying $A^{-1}$ to both sides and getting $A^{-1}Ax=A^{-1}b$ so
$x=A^{-1}b$ (which we've also called $b'$).

\end{document}
