\documentclass{article}
\usepackage{enumitem,amsmath,amssymb}
\usepackage{graphicx}
\usepackage[left=2.5cm,right=2.5cm, top=2cm, bottom=2cm,nohead,nofoot]{geometry}
\newenvironment{amatrix}[1]{%
\left(\begin{array}{@{}*{#1}{r}|r@{}}
}{%
\end{array}\right)
}
\def\vec#1{\mathbf{#1}}
\def\R{\mathbb{R}}
\def\df#1{\textbf{#1}}
\def\theorem{\par\noindent{\bf \underline{Theorem}} }
\def\example{\par\noindent{\bf \underline{Example}} }
\def\remark{\par\noindent{\bf \underline{Remark}} }
\title{Summary of Day 2}
\author{William Gunther}
\date{May 20, 2014}
\begin{document}
\maketitle
\section{Objectives}
\begin{itemize}
\item Define row echelon form (ref), free variable, leading variable, and rank.
\item Identify elementary row operations and their purpose.
\item Perform elementary row operations to reduce a matrix to ref (Gaussian Elimination).
\item Analyze solution set to system using Gaussian Elimination.
\item Express the Rank Theorem.
\end{itemize}
\section{Summary}
\begin{itemize}
\item An entry of a matrix is a \df{leading entry} if it is the leftmost nonzero entry of its row. Note: every nonzero row has a leading entry.
\item A matrix is in \df{row echelon form} if it satisfies the following properties: the leading entry of every row is to the left of the leading entries of every subsequent row and all rows with all $0$'s are the last rows of the matrix.
\example
\begin{center}
\begin{tabular}{c c c}
$\begin{pmatrix}
2& 1& 3\\
0& 1& 1\\
1& 1& 1
\end{pmatrix}$
&
$\begin{pmatrix}
2& 1& 3\\
0& 1& 1\\
0& 0& 4
\end{pmatrix}$
&
$\begin{pmatrix}
2 & 1 & 1 \\
0& 0& 1
\end{pmatrix}
$
\smallskip\\
not in ref & in ref & in ref
\end{tabular}
\end{center}
\example Row echelon form is useful because if an augmented matrix is in row echelon form then we can solve the system using back substitution.
So far all the systems we have seen have had a unique solution. This is not always the case.If a column does contain a leading entry then we make the variable that column represents a \df{free variable}, which is allowed to vary over all possible values. Let's do an example; consider the following augmented matrix:
\[
\begin{amatrix}{3}
1&0&1&3\\
0&2&1&3\\
0&0&0&0
\end{amatrix}
\]
This is in ref, and you can see the 3rd column does not contain a leading entry. Therefore, let us assign $t := x_3$. Then we can through back substitution solve for $x_1$ and $x_2$ in terms of $t$. $x_2 = \frac{1}{2}(3-t)$ and $x_1 = 3 - t$. Therefore we have the following for a solution:
\[
\vec{v} = \begin{pmatrix} 3-t\\ \frac{3-t}{2}\\t \end{pmatrix}
\]
where $t$ can vary over all real numbers. So this gives us infinitely many solutions. The solution set can be written as:
\[
\{\,[3-t, (3-t)/2, t]\in \R^3 \mid t\in \R\,\}
\]
\item The \df{elementary row operation} are a set of ways we can take a matrix and transform it and turn it into another matrix. There are three operations:
\begin{itemize}
\item Interchange two rows
\[
\begin{pmatrix}
R_1\\R_2\\\vdots\\R_n
\end{pmatrix}
\xrightarrow{R_1\leftrightarrow R_2}
\begin{pmatrix}
R_2\\R_1\\\vdots\\R_n
\end{pmatrix}
\]
\item Multiply a row by nonzero scalar
\[
\begin{pmatrix}
R_1\\R_2\\\vdots\\R_n
\end{pmatrix}
\xrightarrow{kR_1}
\begin{pmatrix}
kR_1\\R_2\\\vdots\\R_n
\end{pmatrix}
\]
\item Add a multiple of one row to another
\[
\begin{pmatrix}
R_1\\R_2\\\vdots\\R_n
\end{pmatrix}
\xrightarrow{R_1+kR_2}
\begin{pmatrix}
R_1+kR_2\\R_2\\\vdots\\R_n
\end{pmatrix}
\]
These operations are special because if you perform them to a matrix which represents a system then the solution set of the system is preserved (so it transforms the system into an equivalent system).
\item Two matrices are \df{row equivalent} if there is a sequence of row operations that turns one matrix into the other.
\remark This is an \df{equivalence relation} on matrices if you know what that means. It is a symmetric (you will essentially prove this on homework by showing that these operations are reversable), transitive (because you can chain together row operations), and reflexive (the empty set of row operations) relationship.
\theorem Every matrix is row equivalent to a matrix in row echelon form.
\remark This is not unique; that is, matrices are row equivalent to (infinitely) many matrices in row echelon form. For instance the following two row echelon forms are row equivalent:
\[
\begin{pmatrix}
1 & 0\\
0 & 1
\end{pmatrix}
\qquad\qquad
\begin{pmatrix}
2 & 3\\
0 & 1
\end{pmatrix}
\]
\theorem A matrix $A$ is row equivalent to a matrix $B$ if and only if they are both row equivalent to the same matrix in row echelon form.
\remark The non-uniqueness of row echelon form makes the above theorem seem rather useless. We will soon define a refinement of row echelon form called reduced row echelon form which is unique and will give us an easy way to see if two matrices are row equivalent.
\end{itemize}
\item \df{Gaussian Elimination} is an algorithm to solve a system of equations. These are the steps:
\begin{enumerate}
\item Write system as an augmented matrix.
\item Perform row reduction to find a row equivalent matrix in ref.
\item Perform back substitution on the system this matrix represents to obtain solutions.
\end{enumerate}
\example Consider the following system:
\begin{alignat*}{5}
x_1&+&2x_2&-&3x_3&=&9\\
2x_1&-&x_2&+&x_3&=&0\\
4x_1&-&x_2&+&x_3&=&4
\end{alignat*}
\begin{enumerate}
\item First we write the system as an augmented matrix:
\[\begin{amatrix}{3}
1&2&-3&9\\
2&-1&1&0\\
4&-1&1&4
\end{amatrix}\]
\item
\begin{alignat*}{3}
&&\begin{amatrix}{3}
1&2&-3&9\\
2&-1&1&0\\
4&-1&1&4
\end{amatrix}
&\xrightarrow[R_3-4R_1]{R_2-2R_1}&
\begin{amatrix}{3}
1&2&-3&9\\
0&-5&7&-18\\
0&-9&13&-32
\end{amatrix}
\\\\
&&&\xrightarrow{R_3-\frac{9}{5}R_2}&
\begin{amatrix}{3}
1&2&-3&9\\
0&-5&7&-18\\
0&0&2/5&2/5
\end{amatrix}
\end{alignat*}
This is in row echelon form.
\item We then perform back substitution.
\begin{align*}
2/5 x_3 &= 2/5 & -5x_2 + 7x_3 &= -18 & x_1 - 2x_2 - 3x_3 &= 9 \\
x_3 &= 1 & x_2 &= \frac{1}{5}\left( -18 - 7(1) \right) & x_1 &= 9 + 2(5) + 3(1) \\
& & x_2 &= 5 & x_1 &= 2
\end{align*}
Getting the (unique) solution: $\vec{v} = [2,5,1]$
\end{enumerate}
\item The \df{rank} of a matrix is the number of columns that have leading entries in a matrix's row echelon form.
\remark It's not clear this definition makes sense. After all, the row echelon form of a matrix is not unique; therefore, why can't there be two echelon forms of a matrix each of which contains a different number of columns with leading entries in them.
\theorem (The Rank Theorem) Let $A$ be a $m\times n$ matrix which we will interpret as the coefficient matrix for some system of $m$ linear equations of $n$ variables. Then, if the system is consistent, then:
\[
\text{\# of free variables} = n - \operatorname{rank}(A)
\]
\item To counteract all of the non-uniqueness problems we had with row echelon form, we introduce a new system which is unique: a matrix is in \df{reduced row echelon form} (rref) if:
\begin{itemize}
\item It is in row echelon form.
\item All leading entries are $1$.
\item Every leading entry has $0$s everywhere else in its column.
\end{itemize}
\example See the homework 1 solutions for some examples and non-examples.
\end{itemize}
\end{document}