\section{Definition of a Matrix}

\definition{A \textbf{matrix} is a rectangular array of numbers each of which is called an \textbf{entry} of the matrix.}
\begin{example}\label{exam:matrixdefn}
  \[A=
    \begin{bmatrix*}[r]
      2 & 1  \\
      -1 & 2\\
      0 & 5
    \end{bmatrix*} \hspace{10ex}
    B=
    \begin{bmatrix*}[r]
      ~3&  2 & -1 \\
      0 &  5 & 1  \\
      1 &  1 & -2
    \end{bmatrix*} \hspace{10ex}
    C=
    \begin{bmatrix*}[r]
      5&  1 & 0
    \end{bmatrix*} \hspace{10ex}
    D=
    \begin{bmatrix*}[r]
      2\\
      2\\
      4\\
      8
    \end{bmatrix*}
    \]
\end{example}
We can assign a name ($A$, $B$, etc.) to the matrix as shown. Each horizontal line of numbers is called a \textbf{row} of the matrix; each vertical line of numbers is called a \textbf{column}.    Any matrix consists of $m$ rows and $n$ columns. Matrix $A$ above has 3 rows and 2 columns.  It is an example of a $3\times2$ (``three by two'') matrix. These are the \textbf{dimensions} of the matrix.  Matrix $B$ is an example of a \textbf{square matrix}, a matrix in which the number of columns equals the number of rows.  We can refer to an entry of a matrix by subscripts, row first then column.  So for matrix $A$ above, $a_{21}=-1$\,.  We will use upper case letters to represent matrices as a whole and lower case letters for their entries. For a matrix $A$ with entries $a_{ij}$ it is convenient to use the notation $A=[a_{ij}]$ .

\definition{A \textbf{row matrix} is a matrix of dimension $1\times n$ and a \textbf{column matrix} is a matrix of dimension $m\times1$.}

In Example~\ref{exam:matrixdefn} matrix $C$ is a row matrix and matrix $D$ is a column matrix.

\section{Linear Systems and Matrices}

The \textbf{general form} (or \textbf{standard form}) of a linear system of $m$ equations in $n$ unknowns is:
\begin{align*}
  \,a_{11}x_1\, + \,a_{12}x_2\, + \ldots+\,a_{1n}x_n\, &= b_1 \\
  \,a_{21}x_1\, + \,a_{22}x_2\, + \ldots+\,a_{2n}x_n\, &= b_2 \\
  \vdots\,~~~~~~~~~~~~~~~~~\\
  a_{m1}x_1 + a_{m2}x_2 + \ldots+a_{mn}x_n &= b_m 
\end{align*}
Note that here two indices are required to keep track of the coefficients; the first index indicates to which equation the coefficient belongs, while the second index indicates of which variable it is the coefficient.

The constants and unknowns can be organized into the following matrices:
\[A = \begin{bmatrix}
a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots &  & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn}
\end{bmatrix} \, \, , \, \, X = \begin{bmatrix}
x_1\\x_2\\\vdots\\x_n
\end{bmatrix} \, \, , \, \, B = \begin{bmatrix}
b_1\\b_2\\\vdots\\b_m
\end{bmatrix}\ .\]
The $m\times n$ matrix $A$ is called the \textbf{coefficient matrix}
of the system, $X$ is the matrix of unknowns and $B$ is the right-hand
side of the system.\footnote{Later we will show that a matrix multiplication
operation can be introduced so that the linear system is reducible to
the matrix equation $AX = B$\,.}

\definition{The matrix which is made up of the coefficient matrix $A$ and the right-hand side $B$ is called the \textbf{augmented matrix} of the system and is denoted by $[A|B]$\,.  For a linear system of $m$ equations in $n$ unknowns the augmented matrix is the $m\times(n+1)$ matrix:
\[[A|B] = \begin{bmatrix}[cccc|c]
a_{11} & a_{12} & \ldots & a_{1n} & b_1\\ a_{21} & a_{22} & \ldots & a_{2n} & b_2\\ \vdots & \vdots &  & \vdots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} & b_{m}
\end{bmatrix}\]
}
Note that each equation of a linear system corresponds to a row of the augmented matrix and \emph{vice versa}.

\begin{example}
Derive the augmented matrix for the following linear system.
  \begin{align*}
      3x+2z &= 7\\
      x+4y-4z &= 3\\
      2x+2y +8z &= 1\\
  \end{align*}

  Solution:\\
  We have the coefficient, unknown, and right-hand side matrices:
\[A=\begin{bmatrix*}[r]
~3&0&2\\~1&4&-4\\3&3&8
\end{bmatrix*}, ~~X=\begin{bmatrix}
x\\y\\z
\end{bmatrix}, ~~B= \begin{bmatrix}
7\\3\\1
\end{bmatrix}\ ,\]
so the augmented matrix is:
\[[A|B] = \begin{bmatrix}[rrr|r]
3&0&2&7\\1&4&-4&3\\3&3&8&1
  \end{bmatrix}\ .\]
\end{example}

\begin{example}
  Write down the system of linear equations for the following augmented matrix.
  \[\begin{bmatrix}[rrrr|r]
  -1&0&2&1&-10\\2&3&-5&4&8\\0&0&1&-2&5
  \end{bmatrix}\]

  Solution:\\
  Identifying the coefficient matrix $A$ and the unknown matrix $B$ we see we have the linear system of three equations in four unknowns is given by
\begin{align*}
  -x_1 + 2x_3 + x_4 &= -10\\
  2x_1 + 3x_2 -5x_3 + 4x_4 &= 8\\
  x_3 - 2x_4 &= 5
\end{align*}
\end{example}

\section{Row Echelon Form}
Consider the linear system
\begin{align*}
  2x+3y-2z &= -7\\
  3y+2z &= 3\\
  5z &= 15
\end{align*}
  Many of the coefficients are zero.  It is, equivalently
\begin{align*}
  2x+3y-2z &= -7\\
  0x+3y+2z &= 3\\
  0x+0y+5z &= 15
\end{align*}
and so its corresponding augmented matrix is therefore:  
\[\begin{bmatrix}[rrr|r]
2&3&-2&-7\\0&3&2&3\\0&0&5&1
\end{bmatrix}\]
A system of this type is easy to solve by a process called \textbf{back-substitution}.  In back-substitution we start by solving the last equation first for the final unknown.  That result can then be used in the second last equation to solve for the second last unknown, etc.
\begin{example}Solve the linear system:
\begin{align*}
  2x+3y-2z &= -7\\
  3y+2z &= 3\\
  5z &= 15
\end{align*}
Solution:\\
Solving the last equation first and using back-substitution gives:
  \begin{itemize}
  \item $5z = 15\implies
  \boxed{z = 3}$
  \item $3y + 2z = 3\implies
  3y + 2(3) = 3\implies
  3y =-3\implies
  \boxed{y = -1}$
  \item $2x+3y-2z = -7\implies
  2x+3(-1)-2(3) = -7\implies
  2x = 2\implies
  \boxed{x = 1}$
  \end{itemize}
  The solution is therefore
  \[x=1,\ y=-1,\ z=3\,.\]
\end{example}

An even simpler linear system to solve would have been
\begin{center}
\parbox{.3\textwidth}{
\begin{align*}
  1x+\frac{3}{2}y-z &= -\frac{7}{2}\\
  0x+1y+\frac{2}{3}z &= 1\\
  0x+0y+1z &= 3
  \end{align*}}~~~~$\implies$~~~~
  \parbox{.3\textwidth}{% \rule required to keep fractions looking okay at top.
\[\begin{bmatrix}[rrr|r]
\rule{0em}{1.1em}~1&\frac{3}{2}&-1&-\frac{7}{2}\\[.2em]0&1&\frac{2}{3}&1\\0&0&1&3
\end{bmatrix}\]}
\end{center}
since, upon back-substitution there would be no division required.  Finally an even easier linear system would have the form:
\begin{center}
\parbox{.3\textwidth}{
\begin{align*}
  1x +0y+0z&= 1\\
  0x+1y +0z&= -1\\
  0x+0y+1z &= 3
\end{align*}}~~~~$\implies$~~~~
 \parbox{.3\textwidth}{
\[\begin{bmatrix}[rrr|r]
~1&0&0&1~\\0&1&0&-1~\\0&0&1&3~
\end{bmatrix}\]}
\end{center}
Here finding the solution requires no calculation at all! Note that these last three linear systems are equivalent in the sense that they all have the same solution.  The facility with which a linear system in these forms may be solved suggests that it would be desirable if for \emph{any} linear system we could find an equivalent linear system that had a similar arrangement of zeros and ones in its augmented matrix.  We now show how that may be done, commencing with suitable definitions.

\definition{Two linear systems with $m$ equations in $n$ unknowns are \textbf{equivalent} to each other if they have the same solutions.}

\definition{The leftmost, nonzero entry in a row of a matrix is called the \textbf{leading entry} or \textbf{pivot}.}

\definition{A matrix is in \textbf{row echelon form} (\textbf{REF}) if:
\begin{enumerate}
  \item All zero rows (i.e. rows consisting entirely of zeros) are at the bottom of the matrix.
  \item All elements below a leading entry (pivot) are zero.
  \item Each leading entry is to the right of the leading entries of all rows above it.
  \item Each leading entry is equal to 1.  Such an entry is called the \textbf{leading 1}.
\end{enumerate}}

\definition{A matrix is in \textbf{reduced row echelon form} (\textbf{RREF}) if it is in row echelon form and the leading one is the only nonzero entry in its column.}

\begin{example} Determine if the matrices are in REF, RREF, or neither.
  \begin{enumerate}
  \begin{multicols}{2}
    \item \[A = \begin{bmatrix*}[r]
    1&2&-4\\0&1&-5\\0&0&0
    \end{bmatrix*} \Leftarrow REF\]
    \item \[B = \begin{bmatrix}
    1&0&3\\0&1&4\\0&0&0
    \end{bmatrix} \Leftarrow RREF\]
    \item \[C = \begin{bmatrix}
    2&1&0&0\\0&1&0&0\\1&0&1&0
    \end{bmatrix} \Leftarrow \text{Neither  form}\]
    \item \[D = \begin{bmatrix*}[r]
    1&0&0&-2\\0&1&0&5\\0&0&1&-3
    \end{bmatrix*} \Leftarrow RREF\]
    \item \[E = \begin{bmatrix*}[r]
    1&-7&5&5\\0&1&3&2
    \end{bmatrix*} \Leftarrow REF\]
    \item \[F = \begin{bmatrix}
    1&2&3\\0&0&0\\0&0&1
    \end{bmatrix} \Leftarrow \text{Neither form}\]
\end{multicols}
  \end{enumerate}
\end{example}

\section{Elementary Row Operations}
Performing one of the following three operations, called \textbf{elementary row operations} on a given linear system gives an equivalent linear system.
\begin{enumerate}
  \item Interchange two equations~(or rows), \rowswap{R_i}{R_j}\,.
  \item Multiply an equation~(row) by a nonzero number, \rowop{R_i}{cR_i}\,.
  \item Add a multiple of one equation~(row) to another equation~(row), \rowop{R_i}{R_i+cR_j}\,.
\end{enumerate}
Here $R$ denotes a row of an augmented matrix and $c$ represents a number.

Note: Every augmented matrix can be reduced to its row echelon form using elementary row operations.  This process is called \textbf{Gaussian elimination}. Every augmented matrix can be reduced to its reduced row echelon form by a process called \textbf{Gauss-Jordan elimination}.

\subsection{Steps in Gaussian Elimination}
\begin{enumerate}
\item\label{itm:gauss1} Locate the leftmost nonzero column in the augmented matrix. If the top entry of the column is zero, interchange the top row with another so the top entry (call it $a$) is nonzero.
\item\label{itm:gauss2} If $a$ is not a leading 1 make it so by multiplying the row by $1/a$\,.
  \item\label{itm:gauss3} Make all other entries in the column below the leading 1 equal zero by adding suitable multiples of the first row to the remaining rows.
  \item\label{itm:gauss4} Consider the remaining matrix produced by ignoring the top row.  Repeat steps \ref{itm:gauss1}--\ref{itm:gauss4} on that matrix. If the remaining matrix has no rows the original matrix is now in row echelon form. 
\end{enumerate}
Note that once the matrix is in row echelon form the system may be solved as shown in the following examples.

\begin{example}
  \label{exam:gaussianelimination}
  Solve each linear system using Gaussian elimination.
  \begin{enumerate}
  \item\label{itm:gaussianelimination1} From the end of the last chapter (unsolved):
    \begin{align*}
      x+y+2z&=9 \\
      2x+4y-3z&=1\\
      3x+6y-5z&=0
    \end{align*}

    Solution:\\
    The augmented matrix for the system is
    \[[A|B]=\begin{bmatrix}
      [rrr|r]1&1&2&9\\2&4&-3&1\\3&6&-5&0
      \end{bmatrix}\hspace{6.5em}\]
    Since the top left entry is already a leading 1, zero the 2 below it by adding -2 times row 1 to row 2.  (This is the same as subtracting 2 times row 1 from row 2.)
    % Note that the construction \begin{flalign*}& ... &\end{flalign*}
    % produces a left-justified expression with proper spacing around it.
    \begin{flalign*}&\rowopmatrix[15em]{ \\\rowop{R_2}{R_2+(-2)R_1}\\ }{\begin{bmatrix}[rrr|r]
        1&1&2&9\\
        0&2&-7&-17\\
        3&6&-5&0
    \end{bmatrix}}&\end{flalign*}
    Next zero the first entry in the third row by adding -3 times row 1 to row 3.
    \begin{flalign*}&\rowopmatrix[15em]{ \\ \\\rowop{R_3}{R_3-3R_1}}{\begin{bmatrix}[rrr|r]
        1&1&2&9\\
        0&2&-7&-17\\
        0&3&-11&-27
    \end{bmatrix}}&\end{flalign*}
    To get a leading 1 in the second row, multiply the row by 1/2, or equivalently, divide the row by 2.
    \begin{flalign*}&\rowopmatrix[15em]{ \\ \rowop{R_2}{\frac{1}{2}R_2} \\}{\begin{bmatrix}[rrr|r]
        1&1&2&9\\
        0&1&-\frac{7}{2}&-\frac{17}{2}\\
        0&3&-11&-27
    \end{bmatrix}}&\end{flalign*}
    Zero the second entry in the third row by adding -3 times row 2 to row 3.
    \begin{flalign*}&\rowopmatrix[15em]{ \\ \\ \rowop{R_3}{R_3-3R_2} }{\begin{bmatrix}[rrr|r]
        1&1&2&9\\
        0&1&-\frac{7}{2}&-\frac{17}{2}\\[.2em]
        0&0&-\frac{1}{2}&-\frac{3}{2}\\[.2em]
    \end{bmatrix}}&\end{flalign*}
    Get a leading 1 in the third row by dividing the row by -1/2, or, equivalently, multiplying it by -2.
    \begin{flalign*}&\rowopmatrix[15em]{ \\ \\ \rowop{R_3}{-2R_3} }{\begin{bmatrix}[rrr|r]
        1&1&2&9\\
        0&1&-\frac{7}{2}&-\frac{17}{2}\\[.2em]
        0&0&1&3
    \end{bmatrix}}&\end{flalign*}
    The linear system represented by the last augmented matrix is
    \begin{align*}
      x+y+2z &= 9\\
      y-\frac{7}{2}z &= -\frac{17}{2}\\
      z &= 3
    \end{align*}
    so back-substitution gives the following.
    \begin{itemize}
    \item  $\boxed{z = 3}$
    \item $y-\frac{7}{2}z = -\frac{17}{2}\implies
      y-\frac{7}{2}(3) = -\frac{17}{2}\implies
      y= -\frac{17}{2}+\frac{21}{2}\implies
      \boxed{y = 2}$
    \item $x+y+2z = 9\implies
      x+2+2(3) = 9\implies
      \boxed{x = 1}$
    \end{itemize}
  The solution is therefore $x=1$, $y=2$, $z=3$\, which is easily checked in the original system.
  
    \item \begin{align*}
      x_1+ x_2 &= 1\\ 4x_1 - x_2 &= -6 \\ 2x_1 - 3x_2 &= 8
    \end{align*}
      Solution:\\
      The augmented matrix is
      \[[A|B]=\begin{bmatrix}[rr|r]
    1&1&1\\ 4&-1&-6\\2&-3&8
      \end{bmatrix}\]
      which may be put into row echelon form as follows:
      \[\rowopmatrix{\\\rowop{R_2}{R_2 - 4R_1}\\\rowop{R_3}{R_3 - 2R_1}}{%
        \begin{bmatrix}[rr|r]
          1&1&1\\0&-5&-10\\0&-5&6
      \end{bmatrix}}\Rightarrow
      \rowopmatrix{\\ \rowop{R_2}{-\frac{1}{5}R_2}\\}{
        \begin{bmatrix}[rr|r]
          1&1&1\\0&1&2\\0&-5&6
        \end{bmatrix}}\Rightarrow
      \rowopmatrix{\\ \\\rowop{R_3}{R_3+5R_2}}{
        \begin{bmatrix}[rr|r]
          1&1&1\\0&-5&-10\\0&0&16
        \end{bmatrix}}\]
    The last augmented matrix presents a contradiction as its last equation is $0x_1 + 0x_2 = 16$ or simply $0=16$ which is never true.   There is therefore no solution to this system.
  \item \label{itm:gaussianelimination3}\begin{align*}
      w-x+2y-z &= -1\\
      2w+x-2y-2z &= -2\\
      -w+2x-4y+z &= 1\\
      3w-3z &= -3
  \end{align*}
    Solution:\\
    \[[A|B] = \begin{bmatrix}[rrrr|r]
      1&-1&2&-1&-1\\2&1&-2&-2&-2\\-1&2&-4&1&1\\3&0&0&-3&-3
    \end{bmatrix}\hspace{2em}\]
    \[\Downarrow\]
    \begin{flalign*}&\rowopmatrix[15em]{\\\rowop{R_2}{R_2 - 2R_1}\\\rowop{R_3}{R_3 + R_1}\\\rowop{R_4}{R_4 - 3R_1}}{\begin{bmatrix}[rrrr|r]
        1&-1&2&-1&-1\\0&3&-6&0&0\\0&1&-2&0&0\\0&3&-6&0&0
    \end{bmatrix}}&\end{flalign*}
    \[\Downarrow\]
    \begin{flalign*}&\rowopmatrix[15em]{\\\rowop{R_2}{\frac{1}{3}R_2}\\ \\}{%
      \begin{bmatrix}[rrrr|r]
        1&-1&2&-1&-1\\0&1&-2&0&0\\0&1&-2&0&0\\0&3&-6&0&0
    \end{bmatrix}}&\end{flalign*}
    \[\Downarrow\]
    \begin{flalign*}&\rowopmatrix[15em]{\\ \\ \rowop{R_3}{R_3 - R_2}\\\rowop{R_4}{R_4 - 3R_2}}{\begin{bmatrix}[rrrr|r]
        1&-1&2&-1&-1\\0&1&-2&0&0\\0&0&0&0&0\\0&0&0&0&0
      \end{bmatrix}}&\end{flalign*}
      The linear system corresponding to the row echelon form is then
      \begin{align*}
        w-x + 2y -z &= -1\\
        x-2y &=0\\
        0 &= 0\\
        0 &= 0
      \end{align*}
      This system will have an infinite number of solutions.  To characterize them we will introduce parameters.
      
  \end{enumerate}
\end{example}


\definition{The variables that correspond to the leading entries of the row echelon form of an augmented matrix are called the \textbf{leading variables} or \textbf{dependent variables}. The remaining variables are called the \textbf{free variables} or \textbf{independent variables}.}

To solve a system of linear equations, set the free variables equal to parameters and use the row echelon form with back-substitution to solve for the leading variables.

\begin{example}
  Complete the solution to the Question~\ref{itm:gaussianelimination3} of Example~\ref{exam:gaussianelimination}\,.

  Solution:\\
  The row echelon form found and corresponding linear system are
  \[\begin{bmatrix}[ccrr|r]
        \circled{1}&-1&2&-1&-1\\0&\circled{1}&-2&0&0\\0&0&0&0&0\\0&0&0&0&0
  \end{bmatrix}~~\Leftrightarrow~~\parbox{20ex}{\begin{align*}
        w-x + 2y -z &= -1\\
        x-2y &=0\\
        0 &= 0\\
        0 &= 0
      \end{align*}}\,.\]
  The leading entries are circled and are found in the $w$ and $x$ variable columns.  Thus $w$ and $x$ are the dependent variables and $y$ and $z$ are the independent variables.  So introduce two parameters for the independent variables letting $\boxed{y=s}$ and $\boxed{z=t}$.  Next solve for the dependent variables in terms of the parameters using back-substitution.
  \begin{itemize}
  \item $x-2y=0 \implies x=2y \implies \boxed{x=2s}$
  \item $w-x+2y-z=-1 \implies w-2s+2s-t=-1 \implies \boxed{w=-1+t}$
  \end{itemize}
  We can write the solution to the system as\\
  \[ w=-1+t,\ x=2s,\ y=s,\ z=t\, ,\]
  where $s$ and $r$ are parameters taking on any numbers. We can also write the solution in the matrix form:\\
      \[\begin{bmatrix}
        w\\x\\y\\z
      \end{bmatrix} = \begin{bmatrix}
        -1+t\\2s\\s\\t
      \end{bmatrix}\,.\]
\end{example}

\subsection{Gaussian Elimination in Practice}
Gaussian Elimination, as has been presented, is an algorithmic method for finding solutions to linear systems and can be easily encoded into a computer program.  However, as we saw in Question~\ref{itm:gaussianelimination1} of Example~\ref{exam:gaussianelimination} one can often get fractions in later row entries as one produces a leading 1.  If working by hand it is often easier to use the elementary row operations more liberally so that this may be avoided.  Such strategies include
\begin{itemize}
\item Swapping rows if there is a leading 1 already in a column, even if the top row leading entry is nonzero.
\item Zeroing leading entries in lower rows that are a multiple of a top row leading entry by subtracting the appropriate multiple, before making the top row leading entry equal 1\,.
\item Converting leading entries to 1 \emph{after} the matrix is otherwise reduced, or never converting them at all.
\end{itemize}

\begin{example}
Solve the linear system.
\begin{align*}
      2x_1 -x_2 -x_3 &= 3\\
      -6x_1 + 6x_2 + 5x_3 &= -3\\
      4x_1 + 4x_2 + 7x_3 &= 3
\end{align*}

Solution:\\
The augmented matrix for the system is:
\[\begin{bmatrix}[rrr|r]
    2&-1&-1&3\\-6&6&5&-3\\4&4&7&3
\end{bmatrix}\]

Perform the row operations:
\[\begin{bmatrix}[rrr|r]
    2&-1&-1&3\\-6&6&5&-3\\4&4&7&3
\end{bmatrix}\Rightarrow
\rowopmatrix{\\\rowop{R_2}{R_2 + 3R_1}\\ \rowop{R_3}{R_3-2R_1}}{\begin{bmatrix}[rrr|r]
    2&-1&-1&3\\0&3&2&6\\0&6&9&-3
    \end{bmatrix}}\Rightarrow
\rowopmatrix{\\ \\ \rowop{R_3}{R_3-2R_2}}{\begin{bmatrix}[rrr|r]
    2&-1&-1&3\\0&3&2&6\\0&0&5&-15
  \end{bmatrix}}
\]

    At this stage one could get row echelon form by multiplying the rows by 1/3, 1/2 and 1/5 respectively to get:
\[\begin{bmatrix}[rrr|r]
    1&-\frac{1}{2}&-\frac{1}{2}&\frac{3}{2}\\[.2em]0&1&\frac{2}{3}&2\\0&0&1&-3
 \end{bmatrix}\ ,\]
    but it is simpler just to do back-substitution on the previous matrix:
    \begin{itemize}
    \item $5x_3 = -15\ \implies\ \boxed{x_3 = -3}$
    \item $3x_2 + 2x_3 = 6\ \implies\ 3x_2 + 2(-3) = 6\ \implies\ \boxed{x_2 = 4}$
    \item $2x_1 -x_2 -x_3 = 3\ \implies\ 2x_1 -4 + 3 = 3\ \implies\ \boxed{x_1 = 2}$
    \end{itemize}
    So the solution is
    \[x_1=2,\ x_2=4,\ x_3=-3\ .\]
\end{example}

\subsection{Gauss-Jordan Elimination}
Gauss-Jordan elimination takes Gaussian elimination one further step to produce an augmented matrix in reduced row echelon form.  One does the following steps:
\begin{enumerate}
\item Perform Gaussian elimination to put the augmented matrix in row echelon form (REF).
%  Not required for our definition of REF.
  %  \item Make all leading entries equal 1\,.
\item\label{itm:gaussjordan1} Add suitable multiples of the last nonzero row to the rows above it to introduce zeros into them above the leading 1 of this row.
\item\label{itm:gaussjordan2} Consider the remaining matrix produced by ignoring the last nonzero row and any zero rows beneath it, if any.  Repeat steps \ref{itm:gaussjordan1}--\ref{itm:gaussjordan2} on that matrix.  If the remaining matrix has no rows the original matrix is now in reduced row echelon form (RREF).
\end{enumerate}

\begin{example}
  % Note the following example was slightly modified from the one below (still equivalent) to require an interchange of rows.  Most matrices below in the solution are still the same.
  %
  % Note Fotini has more examples that can be used here, though starting with
  % a single solution is perhaps most illustrative.
Solve the linear system using Gauss-Jordan elimination:
    \begin{align*}
       -y + 5z &= 9\\
      x+y+2z &= 8\\
      3x-7y + 4z &= 10
    \end{align*}

Solution:\\
\[[A|B] = \begin{bmatrix}
    [rrr|r]0&-1&5&9\\1&1&2&8\\3&-7&4&10
    \end{bmatrix}\hspace{4em}\] 

First put the augmented matrix in row echelon form:
    \begin{flalign*}&\rowopmatrix[17em]{\rowswap{R_1}{R_2}\\ \\}{\begin{bmatrix}[rrr|r]
          1&1&2&8\\0&-1&5&9\\3&-7&4&10
    \end{bmatrix}}&\end{flalign*}
    \[\Downarrow\]
    \begin{flalign*}&\rowopmatrix[17em]{\\ \\\rowop{R_3}{R_3-3R_1}}{\begin{bmatrix}[rrr|r]
        1&1&2&8\\0&-1&5&9\\0&-10&-2&-14
    \end{bmatrix}}&\end{flalign*}
    \[\Downarrow\]
    \begin{flalign*}&\rowopmatrix[17em]{\\ \\\rowop{R_3}{R_3-10R_2}}{\begin{bmatrix}[rrr|r]
        1&1&2&8\\0&-1&5&9\\0&0&-52&-104 
    \end{bmatrix}}&\end{flalign*}
    \[\Downarrow\]
    \begin{flalign*}&\rowopmatrix[17em]{\\\rowop{R_2}{-R_2}\\ \rowop{R_3}{-\frac{1}{52}R_3}}{\begin{bmatrix}[rrr|r]
        1&1&2&8\\0&1&-5&-9\\0&0&1&2
    \end{bmatrix}}\ \ \text{(REF)}&\end{flalign*}

    To achieve reduced row echelon form work from the bottom of the matrix upward, to get zeros above any leading one.
    \[\Downarrow\]
    \begin{flalign*}&\rowopmatrix[17em]{\rowop{R_1}{R_1 - 2R_3}\\\rowop{R_2}{R_2 + 5R_3}\\}{\begin{bmatrix}[rrr|r]
        1&1&0&4\\0&1&0&1\\0&0&1&2
    \end{bmatrix}}&\end{flalign*}
    \[\Downarrow\]
    \begin{flalign*}&\rowopmatrix[17em]{\rowop{R_1}{R_1 - R_2}\\ \\}{\begin{bmatrix}[rrr|r]
        1&0&0&3\\0&1&0&1\\0&0&1&2
    \end{bmatrix}}\ \ \text{(RREF)}&\end{flalign*}
    The unique solution to the system is therefore
    \[x=3,\ y=1,\ z=2\,.\]
\end{example}


\subsection{Interpreting the Reduced Row Echelon Form}
Once the augmented matrix has been put in RREF by Gauss-Jordan elimination one proceeds as follows:
\begin{enumerate}
\item If the last nonzero row of the matrix is of the form
  \[ \begin{bmatrix}[cccc|c]0&0&\ldots& 0& 1\end{bmatrix} \]
    then the linear system has \textbf{no solution}.\footnote{Note one can stop at REF if its last nonzero row indicates no solution.}
\item If not, assign parameters to any free (independent) variables and solve for the leading (dependent) variables using the nonzero rows. If no such parameters are needed there is a \textbf{unique solution}, otherwise one has  \textbf{infinitely many solutions}.
\end{enumerate}

\begin{example}
  Find values of $m$ such that the linear system
  \begin{align*}
    x+y+z &= 1 \\ 2x+y+4z&= 3\\2x+2y+2m^2z &= 2m
  \end{align*}
  has:
  \begin{enumerate}
   \item No solution
   \item Infinitely many solutions
   \item A unique solution
  \end{enumerate}
  Solution:\\
  The augmented matrix is:
    \[[A|B] = \begin{bmatrix}[rrr|r]
  1&1&1&1\\2&1&4&3\\2&2&2m^2&2m
    \end{bmatrix}\hspace{.5em}\]
    The following matrix is equivalent:
    \[\rowopmatrix{\\ \rowop{R_2}{R_2-2R_1} \\ \rowop{R_3}{R_3-2R_1}}{\begin{bmatrix}[rrr|r]
  1&1&1&1\\0&-1&2&1\\0&0&2m^2-2&2m-2
  \end{bmatrix}}\]
\begin{enumerate}
\item There is no solution if you have the contradiction $2m^2-2=0$ and $2m-2\neq0$ in the last row.  Solving gives

  \[2m^2 -2 = 0\ \implies\ m^2-1 = 0\ \implies\ (m-1)(m+1)= 0\ \implies\ m= \pm 1\]
  and
  \[2m-2\neq 0\ \implies\ m-1\neq 0\ \implies\ m\neq 1\]
Thus $m=\pm 1$ and $m\neq1$ for no solution.  This implies $m=-1$ gives no solution.

\item There are an infinite number of solutions when the last row is 0=0 since then the number of leading terms is less than the number of unknowns.
  We saw $2m^2-2=0\ \implies\ m=\pm1$.  Similarly $2m-2=0\ \implies\ m=1$.  Thus we get an infinite number of solutions when $m=1$.

\item Finally a unique solution occurs the rest of the time, logically when $m\neq1$ and $m\neq-1$.  We can see this directly by noting that when $2m^2-2\neq0$ we would be able to divide row three in the augmented matrix to get a leading 1, since $m\neq\pm1\ \implies\ 2m^2-2\neq 0$\,.
\end{enumerate}
\end{example}

Note:
\begin{enumerate}
\item For a given linear system, the row echelon form generated by Gaussian elimination is not unique.  The reduced row echelon form generated by Gauss-Jordan elimination is however unique.

\item On a computer, Gaussian Elimination (finding REF and using back-substitution) is more efficient, in general, than Gauss-Jordan elimination.

\item Terminology is not universal.  Some consider matrices for which the leading entry is not equal to~1 to be in row echelon form.  Some call Gaussian elimination what we have called Gauss-Jordan elimination.  
  
\end{enumerate}

\subsection{Rank of a Matrix}

Characterization of the solutions of a linear system is simplified by the introduction of the rank of a matrix. It can be shown that any REF and the RREF of a matrix $A$ always have the same number of nonzero rows allowing for the following definition.

\definition{The \textbf{rank} of a matrix $A$, $\rank{A}$, is the number of nonzero rows in the row echelon or reduced row echelon form of $A$.}

\begin{example}
  Find the rank of $A = \begin{bmatrix*}[r]
    1&2&-5&2\\2&-3&4&4\\4&1&-6&8
  \end{bmatrix*}$\,.\\

  Solution:\\
  Put the matrix $A$ in REF form:

  \[\begin{bmatrix*}[r]
    1&2&-5&2\\2&-3&4&4\\4&1&-6&8
  \end{bmatrix*} \Rightarrow \rowopmatrix{ \\ \rowop{R_2}{R_2-2R_1}\\ \rowop{R_3}{R_3-4R_1}}{\begin{bmatrix*}[r]
          1&2&-5&2\\0&-7&14&0\\0&-7&14&0\end{bmatrix*}}\Rightarrow
      \rowopmatrix{ \\ \rowop{R_2}{-\frac{1}{7}R_2}\\ \rowop{R_3}{R_3-R_2}}{\begin{bmatrix*}[r]
  1&2&-5&2\\0&1&-2&0\\0&0&0&0
  \end{bmatrix*}}
  \]

Therefore $\rank{A}= 2$.
\end{example}

\theorem{\label{thm:rank}Consider a linear system of $m$ equations in $n$ unknowns, with coefficient matrix $A$ and right-hand side matrix $B$. If $p$ is the rank of $A$ and $q$ is the rank of $[A|B]$. The linear system has:
\begin{enumerate}
  \item No solution if $p<q$\,.
  \item A unique solution if $p=q=n$\,.
  \item Infinitely many solutions if $p=q$ and $p<n$\,.
\end{enumerate}
}

\begin{example}
  Suppose the augmented matrix of a linear system is given by
  \[[A|B] = \begin{bmatrix}[ccc|c]
    1&0&0&2\\0&1&0&3\\0&0&x&y
  \end{bmatrix}\,.\]
  For what values of x and y give does the system have\\
  \begin{inparaenum} \item No solution? \item Exactly one solution? \item Infinitely many solutions?\end{inparaenum}
  
  Solution:\\
  The original system has $n=3$ unknowns.  We consider the various ranks which occur of $A$ and $[A|B]$ when either $x$ or $y$ or both are zero.
  \begin{enumerate}
    \item No solution $\Rightarrow x=0, y\neq0$ since then $p=\rank{A}=2<3=\rank{[A|B]}=q$
    \item Exactly one solution $\Rightarrow x\neq0$ since then $p=\rank{A}=3=\rank{[A|B]}=q=n$\,.
    \item Infinitely many solutions $\Rightarrow x=0, y=0$ since then\\ $p=\rank{A}=2=\rank{[A|B]}=q<3=n$\,.
  \end{enumerate}
\end{example}

\begin{example}
  Consider the linear system $AX=B$, where:
  \[A = \begin{bmatrix}
    a&b\\c&d
  \end{bmatrix} ,  B=\begin{bmatrix}e\\f\end{bmatrix} , a\neq0\]

  Determine conditions on the constants $a, \, b, \, c, \, d, \, e, \, f$ so that:
  \begin{enumerate}
    \item $\rank{A}=2$\,.
    \item $\rank{A}=1$ but $\rank{[A|B]}=2$\,.
    \item $\rank{A}$ and $\rank{[A|B]}$ are both 1\,.
  \end{enumerate}

  Solution:\\
  The augmented matrix is
  \[[A|B] = \begin{bmatrix}[cc|c]
    a&b&e\\c&d&f
  \end{bmatrix}\,.\]
  Since $a\neq0$ perform the row operation $\rowop{R_2}{R_2 -\frac{c}{a}R_1}$:
  \[\begin{bmatrix}[cc|c]
    a&b&e\\0&d-\frac{bc}{a} & f- \frac{ce}{a}
  \end{bmatrix}\]

Then:
  \begin{enumerate}
    \item $\rank{A} = 2 \implies d- \frac{bc}{a} \neq 0 \implies ad-bc\neq0$
    \item $\rank{A}=1 \implies d- \frac{bc}{a}=0 \implies ad-bc = 0$ and \\ $\rank{[A|B]} = 2 \implies f - \frac{ce}{a}\neq0 \implies af-ce \neq0$
    \item $\rank{A} = 1 \implies ad-bc=0$ and\\ $\rank{[A|B]} = 1 \implies f - \frac{ce}{a} = 0 \implies af-ce = 0$ 
  \end{enumerate}
  Note: The student may wish to consider the implications if $a=0$ but some other element of $A$ \mbox{(i.e. $b$, $c$, or $d$)} is taken to be nonzero.
\end{example}

Theorem~\ref{thm:rank} has some useful corollaries.  For a homogeneous system ($B=0$) the last column of $[A|B]$ is zero so $p=q$ and further the trivial solution ($X=0$) is always a solution to the system.  This gives the corollary:

\textbf{Corollary 1:} A homogeneous linear system with $m\times n$ coefficient matrix $A$ has:
\begin{enumerate}
  \item A unique solution (trivial solution $X=0$) if $\rank{A}=n$\,.
  \item Infinitely many solutions if $\rank{A}<n$\,.
\end{enumerate}

For coefficient matrix $A$ we have $p=\rank{A}$ necessarily less than or equal to its number of rows, which equals the number of equations $m$.  Since for an underdetermined system (fewer equations $m$ than unknowns $n$), it follows then that $p<n$, and one has the following corollaries:

\textbf{Corollary 2:} An underdetermined linear system has no solution or infinitely many solutions.

\textbf{Corollary 3:} An underdetermined homogeneous linear system has infinitely many solutions.

\begin{example}
Without solving the system what can you say about the number of solution for the following systems?

\begin{enumerate}
\item \begin{align*}2x+2y+4z&=0\\
w-y-3z&=0\\
2w+3x+y+2&=0
\end{align*}
  Solution:\\
This is a homogeneous system with 3 equations in 4 unknowns and so underdetermined.  Therefore there are infinitely many solutions.

\item \begin{align*}
x+2y+z+w&=-7\\
2x+3y-z+2w&=1\\
x-y-z-w&=3
\end{align*}
  Solution:\\
This is a non-homogeneous system with 3 equations in 4 unknowns and so underdetermined. Therefore there are either no solutions or infinitely many solutions.
\end{enumerate}
\end{example}

\section{Matrix Equality, Addition, and Subtraction}
\definition{Two matrices are \textbf{equal} if they have the same dimensions and their corresponding entries are equal.}
Therefore $A=B$ implies $a_{ij} = b_{ij}$ for all indices $i$ and $j$.
\begin{example}
  Given the matrices:
\[A=
\begin{bmatrix}
2&0\\
1&3\\
\end{bmatrix}\hspace{10ex}
B=
\begin{bmatrix}
\frac{8}{4}&0\\
1&\frac{12}{4}
\end{bmatrix}
\]
We see that $A=B$ since they are both $2\times2$ matrices with equal corresponding entries.
\end{example}

\definition{Let $A=[a_{ij}]$ and $B=[b_{ij}]$ be matrices with the same dimensions. The \textbf{sum} of $A$ and $B$, written $\bm{A + B}$, is the matrix obtained by adding corresponding entries of $A$ and $B$. The \textbf{difference} of $A$ and $B$, written $\bm{A-B}$, is obtained by subtracting corresponding entries from entry $A$ by entry $B$.  In symbols:
\[A+B = [a_{ij}]+[b_{ij}] = [a_{ij} + b_{ij}]\]
\[A-B = [a_{ij}]-[b_{ij}] = [a_{ij} - b_{ij}]\]
}
\begin{example}
If 
\[A=
\begin{bmatrix*}[r]
1&0&-1\\
2&3&8\end{bmatrix*}~~~
B= \begin{bmatrix*}[r]
2&5&-1\\
0&1&3
\end{bmatrix*}\,,
\]
then $A + B$ and $A-B$ are, respectively,
\[A+B= \begin{bmatrix} 
(1+2)&(0+5)&(-1-1)\\
(2+0)&(3+1)&(8+3)
\end{bmatrix}%
=\begin{bmatrix*}[r] 
3&5&-2\\
2&4&11
\end{bmatrix*}
\]
\[
A-B=\begin{bmatrix} 
(1-2)&(0-5)&(-1+1)\\
(2-0)&(3-1)&(8-3)
\end{bmatrix}%
=\begin{bmatrix*}[r] 
-1&-5&0\\
2&2&5\\
\end{bmatrix*}\,.
\]
\end{example}

Note that $A+B$ and $A-B$ will not be defined if the matrices do not have the same dimension.

\begin{example}
  For the matrices
  \[A=\begin{bmatrix}2 & 5 \\ 3 & 1 \end{bmatrix}~~~~~~%
  B=\begin{bmatrix*}[r] 1 & -1 \\ 0 & 5 \\ 2 & 3\end{bmatrix*}\]
  the sum $A+B$ and difference $A-B$ are not possible since $A$ is a $2\times2$ matrix and $B$ is a $3\times2$ matrix.
\end{example}

Note $A+B=B+A$ when the sum exists.  

\definition{A \textbf{zero matrix}, denoted by $\zeromat$, is an $m\times n$ matrix where all entries are zero.}
One may write $\zeromat_{mn}$ to make the dimension explicit.  Clearly $A+\zeromat=A$ for the zero matrix with same dimension as $A$.

\section{Scalar Multiplication}

\definition{Let $A=[a_{ij}]$ be a matrix and $c$ be a number (a \emph{scalar}) then the \textbf{scalar product} of $c$ times $A$, written  $\textbf{cA}$, is the matrix obtained by multiplying each entry of $A$ by $c$. In symbols one has
  \[cA=[ca_{ij}]\,.\]
}

\begin{example}
  If
  \[A=\begin{bmatrix*}[r]2 & 1\\-1 & 5\\3 & 0\end{bmatrix*},\ c=3\]
  then the scalar product is
  \[cA=3A=\begin{bmatrix}(3)(2) & (3)(1)\\(3)(-1) &(3)(5)\\(3)(3) & (3)(0)\end{bmatrix}=\begin{bmatrix*}[r]6 & 3\\-3 & 15\\9 & 0\end{bmatrix*}\,.\]
\end{example}

\definition{The \textbf{negative} of matrix $A=[a_{ij}]$, written $\textbf{-A}$, is defined to be $(-1)A$\,.}
Clearly  $-A=[-a_{ij}]$ and $-A+A=\zeromat$. 

One can combine scalar multiplication and matrix addition and subtraction to form new matrices.
\begin{example}
  Let
  \[A=\begin{bmatrix*}[r]-1 & 3 & 2 \\ 0 & 1 & -1 \\ 2 & 1 & 4\end{bmatrix*}~~~~
  B=\begin{bmatrix*}[r]1 & -1 & 0 \\ 2 & 5 & 1 \\ -1 & 1 & -2\end{bmatrix*}\]
  Find $A+2B$ and $3A-B$ .

  Solution:\\
  \[A+2B=\begin{bmatrix*}[r]-1 & 3 & 2 \\ 0 & 1 & -1 \\ 2 & 1 & 4\end{bmatrix*}+
  \begin{bmatrix*}[r]2 & -2 & 0 \\ 4 & 10 & 2 \\ -2 & 2 & -4\end{bmatrix*}=
  \begin{bmatrix*}[r]1 & 1 & 2 \\ 4 & 11 & 1 \\ 0 & 3 & 0\end{bmatrix*}\]
    \[3A-B=\begin{bmatrix*}[r]-3 & 9 & 6 \\ 0 & 3 & -3 \\ 6 & 3 & 12\end{bmatrix*}-\begin{bmatrix*}[r]1 & -1 & 0 \\ 2 & 5 & 1 \\ -1 & 1 & -2\end{bmatrix*}
    =\begin{bmatrix*}[r]-4 & 10 & 6 \\ -2 & -2 & -4 \\ 7 & 2 & 14\end{bmatrix*}
    \]
  
\end{example}

\section{Solutions of Homogeneous Linear Systems}
One can use scalar multiplication and addition to represent solutions to a linear system.

\begin{example}\label{example:homogeneous}
Find the solution of the homogeneous linear system
  \begin{align*}
  x_3+2x_4-x_5&= 0 \\ x_4-x_5 &= 0\\ x_3+3x_4-2x_5&=0\\ 2x_1+4x_2+x_3+7x_4&=0
  \end{align*}
  if its augmented matrix reduces to
\[\begin{bmatrix}[rrrrr|r]
    1 & 2 & 0 & 0 & 3 & 0\\
    0 & 0 & 1 & 0 & 1 & 0 \\
    0 & 0 & 0 & 1& -1 & 0 \\
    0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}\,,\]
and write your solution using matrix addition and the scalar product.

Solution:\\
The RREF augmented matrix and corresponding equivalent linear system are
\[\begin{bmatrix}[ccccr|r]
    \circled{1} & 2 & 0 & 0 & 3 & 0\\
    0 & 0 & \circled{1} & 0 & 1 & 0 \\
    0 & 0 & 0 & \circled{1}& -1 & 0 \\
    0 & 0 & 0 & 0 & 0 & 0
  \end{bmatrix}~~\Leftrightarrow~~\parbox{10em}{
  \begin{align*}
    x_1+2x_2+3x_5 &=0\\
    x_3+x_5 &=0\\
    x_4-x_5 &=0\\
    0&=0
  \end{align*}}\]
  The leading ones (circled) are in the variable $x_1$, $x_3$, and $x_4$ columns.  These are the leading (dependent) variables and the remaining variables, $x_2$ and $x_5$, are the free (independent) variables.  Assigning parameters to the latter we have $\boxed{x_2=s}$ and $\boxed{x_5=t}$\,.  Next solve the dependent variables using back-substitution.
  \begin{itemize}
  \item $x_4-x_5 =0 \implies x_4-t=0 \implies \boxed{x_4=t}$
  \item $x_3+x_5=0 \implies x_3+t=0 \implies \boxed{x_3=-t}$
  \item $x_1+2x_2+3x_5=0 \implies x_1+2s+3t=0 \implies \boxed{x_1=-2s-3t}$
  \end{itemize}
  Writing the solution as a column matrix we have
  \[X=\begin{bmatrix*}[c] x_1\\x_2\\x_3\\x_4\\x_5\end{bmatrix*}=\begin{bmatrix*}[c] -2s-3t\\~~s\\-t\\~~t\\~~t\end{bmatrix*}\,.\]
  Using matrix addition we can break the solution matrix into a column matrix for each parameter which we then factor out using scalar multiplication.
  \[X=\begin{bmatrix*}[c] -2s\\s\\0\\0\\0\end{bmatrix*}+\begin{bmatrix*}[c] -3t\\~~0\\-t\\~~t\\~~t\end{bmatrix*}=s\begin{bmatrix*}[r] -2\\1\\0\\0\\0\end{bmatrix*}+t\begin{bmatrix*}[r] -3\\0\\-1\\1\\1\end{bmatrix*}\,.\]
  
\end{example}

The general solution to the homogeneous linear system in the last example is therefore $X=sX_1+tX_2$ where
\[X_1=\begin{bmatrix*}[r]-2\\1\\0\\0\\0\end{bmatrix*},~~~
X_2=\begin{bmatrix*}[r]-3\\0\\-1\\1\\1\end{bmatrix*}\]

Both $X_1$ and $X_2$ are themselves solutions to the system by $s=1$, $t=0$ and $s=0$, $t=1$ respectively.  These solutions are called \textbf{basic solutions} of the homogeneous linear system and can be systematically found by reducing the system to RREF using Gauss-Jordan elimination.  Basic solutions are not unique since we can always replace the multiplicative parameter $s$ by, say, $2\tilde{s}$ in the general solution $X$ and then absorb the 2 into the basic solution using scalar multiplication.\footnote{This can be a useful step to remove fractions from a basic solution.}  However up to such a scalar multiple they are unique.  The number of basic solutions will correspond to the number of free parameters.

The solution of the last homogeneous linear system, $X=sX_1+tX_2$ suggests the following general definition.

\definition{Let $X_1$, $X_2$, \ldots, $X_n$ be matrices of the same dimension and $c_1$, $c_2$, \ldots $c_n$ be numbers, then
  \[c_1X_1+c_2X_2+\ldots+ c_nX_n\]
  is a \textbf{linear combination} of $X_1$, $X_2$, \ldots, $X_n$\,.}

With this definition we can now characterize solutions to homogeneous linear systems.

\theorem{Let $A$ be the coefficient matrix of a homogeneous linear system of $m$ equations in $n$ unknowns.  Then the system has $n-\rank{A}$ basic solutions and every solution to the system is a linear combination of these basic solutions and \emph{vice versa}. (If the system has no basic solutions it has only the trivial solution $X=0$.)}

Let $Y=a_1X_1+\ldots +a_kX_k$ and $Z=b_1X_1+\ldots+b_kX_k$ be any two solutions to a homogeneous linear system written in terms of the basic solutions $X_1$, \ldots, $X_k$.  Then their sum can be written
\[Y+Z=(a_1+b_1)X_1+\ldots+(a_k+b_k)X_k=c_1X_1+\ldots c_kX_k, \]
where we have defined $c_i=a_i+b_i$ ($i=1,\ldots, k$), and hence the sum itself is a solution to the system as it is a linear combination of the basic solutions. Similarly the scalar product $cY$ can be written 
\[cY=(ca_1)X_1+\ldots+(ca_k)X_k=d_1X_1+\ldots d_kX_k, \]
where we have defined $d_i=ca_i$ ($i=1,\ldots, k$), and hence the scalar product is also a solution to the system as it is a linear combination of the basic solutions.\footnote{These two results can also be shown directly by considering two solutions $Y=\begin{bsmallmatrix}y_1\\ \vdots\\y_n\\[.1em]\end{bsmallmatrix}$ and  $Z=\begin{bsmallmatrix}z_1\\ \vdots\\z_n\\[.1em]\end{bsmallmatrix}$ of a homogeneous linear system and plugging $Y+Z$ and $kY$ into each homogeneous equation to see that they still hold.}

More generally we have the following result.

\theorem{A linear combination of any solutions of a homogeneous linear system is also a solution to the system.}

Note that the system has to be homogeneous for this property to hold.

\textbook{\newpage}
We will often be interested in whether a matrix, particularly a column or row matrix, can be written as a linear combination of other matrices.  This amounts to solving a linear system.

\begin{example}
  Let $X=\begin{bmatrix*}[r]-1\\2\\3\end{bmatrix*}$ and $Y=\begin{bmatrix*}[r]1\\4\\2\end{bmatrix*}$\,.

  Write $V=\begin{bmatrix*}[r]-3\\0\\4\end{bmatrix*}$ as a linear combination of $X$ and $Y$ or show such a combination does not exist.

  Solution:\\
  For $V$ to be a linear combination of $X$ and $Y$ we must find values for $s$ and $t$ such that
  \[V=sX+tY\,.\]
  This implies
  \[\begin{bmatrix*}[r] -3\\0\\4\end{bmatrix*}=s\begin{bmatrix*}[r] -1\\2\\3\end{bmatrix*}+t\begin{bmatrix*}[r] 1\\4\\2\end{bmatrix*}=\begin{bmatrix*}[c] -s+t\\2s+4t\\3s+2t\end{bmatrix*}\,.\]
  Matrix equality of the first and last matrix implies we must solve the linear system:
  \begin{align*}
    -s+t &= -3 \\
    2s+4t &= 0 \\
    3s+2t &= 4
  \end{align*}
  Reducing the corresponding augmented matrix gives
  \[\begin{bmatrix}[rr|r] -1 & 1 & -3 \\ 2 & 4 & 0 \\ 3 & 2 & 4 \end{bmatrix} \Rightarrow
  \rowopmatrix{ \\ \rowop{R_2}{R_2+2R_1} \\ \rowop{R_3}{R_3+3R_1}}{\begin{bmatrix}[rr|r]-1 & 1 & -3 \\ 0 & 6 & -6 \\ 0 & 5 & -5 \end{bmatrix}} \Rightarrow
  \rowopmatrix{ \rowop{R_1}{-R_1}\\ \rowop{R_2}{\frac{1}{6}R_2} \\[.2em] \rowop{R_3}{\frac{1}{5}R_3}}{\begin{bmatrix}[rr|r] 1 & -1 & 3 \\ 0 & 1 & -1 \\ 0 & 1 & -1 \end{bmatrix}} \Rightarrow
    \rowopmatrix{ \rowop{R_1}{R_1+R_2}\\ \\ \rowop{R_3}{R_3-R_2}}{\begin{bmatrix}[rr|r] 1 & 0 & 2 \\ 0 & 1 & -1 \\ 0 & 0 & 0 \end{bmatrix}} \] 
    The solution corresponding to the RREF is
    \[ s=2,\ t=-1\,, \]
    so $\boxed{V=2X-1Y}$\,.  This is easily checked:
    \[\begin{bmatrix*}[r]-3\\0\\4\end{bmatrix*}=2\begin{bmatrix*}[r]-1\\2\\3\end{bmatrix*}-1\begin{bmatrix*}[r]1\\4\\2\end{bmatrix*}\,.\]

\end{example}

\section{Matrix Multiplication}

We now formally introduce how to multiply two matrices the motivation for which will be seen later.
\definition{Let $A=[a_{ij}]$ and $B=[b_{ij}]$ be two matrices with the number of columns of $A$ being equal to the number of rows of $B$. Suppose $A$ is an $m\times n$ matrix and $B$ is an $n\times q$ matrix. Then the \textbf{matrix product} $AB$ is an $m\times q$ matrix $C$, denoted $[c_{ij}]$ where the entry $c_{ij}$ in $i^\textsuperscript{th}$ row and $j\textsuperscript{th}$ column of the product, is found by multiplying each element in the $i$\textsuperscript{th} row of $A$ with the corresponding element in the $j$\textsuperscript{th} column of $B$ and then adding the products.  In symbols
\[c_{ij}= [i\textsuperscript{th}\text{row of } A]\left[\begin{matrix}[c]j^\textsuperscript{th}\\\text{column}\\ \text{of}\\ B\end{matrix}\right]=a_{i1}b_{1j} +  a_{i2}b_{2j}  + \ldots + a_{in}b_{nj}\]
}

\begin{example}
Find $AB$ and $BA$ if possible for the following pairs of matrices:
\begin{enumerate}
\item 
\[
A=
\begin{bmatrix*}[r]
2&1\\-1&3\\ 
\end{bmatrix*},~~
B = 
\begin{bmatrix*}[r]
1&0&2\\4&-1&3\\
\end{bmatrix*}
\]

Solution:\\
$A$ is $2\times2$ and $B$ is $2\times3$~.  So the product
\[A_{2\times\underset{\uparrow}{2}}B_{\underset{\uparrow}{2}\times3}=C_{2\times3}\]
is defined and is a $2\times3$ matrix.  (The inner dimensions, indicated by $\uparrow$, are equal so the multiplication is possible and the outer dimensions are the dimensions of the new matrix.) Direct calculation of $AB$ gives
\begin{align*}AB&=\begin{bmatrix*}[r]
2&1\\-1&3\\ 
\end{bmatrix*}\begin{bmatrix*}[r]
1&0&2\\4&-1&3\\
  \end{bmatrix*}\\
&=\begin{bmatrix*}[r]\\[-.7em]
\begin{bmatrix*}2 & 1\end{bmatrix*}\begin{bmatrix*}[r]1 \\ 4\end{bmatrix*}
    & \begin{bmatrix*}2 & 1\end{bmatrix*}\begin{bmatrix*}[r]0 \\ -1\end{bmatrix*}
          & \begin{bmatrix*}2 & 1\end{bmatrix*}\begin{bmatrix*}[r]2 \\ 3\end{bmatrix*}\\[1.5em]
                \begin{bmatrix*}-1 & 3\end{bmatrix*}\begin{bmatrix*}[r]1 \\ 4\end{bmatrix*}
                    &
                \begin{bmatrix*}-1 & 3\end{bmatrix*}\begin{bmatrix*}[r]0 \\ -1\end{bmatrix*}
                    &  \begin{bmatrix*}-1 & 3\end{bmatrix*}\begin{bmatrix*}[r]2 \\ 3\end{bmatrix*}\\[1em]\end{bmatrix*}\\
                           &=\begin{bmatrix*}(2)(1)+(1)(4) & (2)(0)+(1)(-1) & (2)(2)+(1)(3) \\
                           (-1)(1)+(3)(4) & (-1)(0)+(3)(-1) & (-1)(2)+(3)(3)\end{bmatrix*}\\
                           &=\begin{bmatrix*}2+4 & 0+(-1) & 4+3 \\
                           -1+12 & 0+(-3) & -2+9\end{bmatrix*}\\
&=\begin{bmatrix*}6&-1&7\\11&-3&7\end{bmatrix*}\ \ \ \ \leftarrow\text{($2\times3$ matrix)}
\end{align*}
Notice the pattern in the second step where the $i\textsuperscript{th}$ row of the first matrix multiplies the $j\textsuperscript{th}$ of the second matrix term by term and these results are added together.

The product $BA$ on the other hand does not exist
\[B_{2\times\underset{\uparrow}{3}}A_{\underset{\uparrow}{2}\times2}\]
since the inner dimensions are not the same.  (The $i\textsuperscript{th}$ row of the first matrix has three entries which cannot multiply term by term the $j\textsuperscript{th}$ column of the second matrix which has only two entries.)

\item
\[
A= \begin{bmatrix*}[r]1&2&4\\2&6&0\\\end{bmatrix*},~~
B= \begin{bmatrix*}[r]4&1&4&3\\0&-1&3&1\\2&7&5&2\\\end{bmatrix*}
\]
Solution:\\
$A$ is a $2\times3$ matrix and $B$ is a $3\times4$ matrix and so the product $AB$ exists and is a $2\times4$ matrix:
\[A_{2\times\underset{\uparrow}{3}}B_{\underset{\uparrow}{3}\times4}=C_{2\times4}\]
Matrix multiplication gives
\begin{align*}
  AB&=\begin{bmatrix*}[r]1&2&4\\2&6&0\\\end{bmatrix*}\begin{bmatrix*}[r]4&1&4&3\\0&-1&3&1\\2&7&5&2\\\end{bmatrix*}\\
  &=\begin{bmatrix*}[c]4+0+8&1-2+28&4+6+20&3+2+8\\8+0+0&2-6+0&8+18+0&6+6+0\\\end{bmatrix*}\\
    &=\begin{bmatrix*}12&27&30&13\\8&-4&26&12\\\end{bmatrix*}
\end{align*}

The matrix product $BA$ is not defined,
\[B_{3\times\underset{\uparrow}{4}}A_{\underset{\uparrow}{2}\times3}\]
since the number of columns of $B$ does not equal the number of rows of $A$.

\item
\[
A = \begin{bmatrix*}[r]-3&0\\-1&2\\1&1\\\end{bmatrix*},~~
B = \begin{bmatrix*}[r]6&1&3\\-1&1&4\\4& 1 & 0\end{bmatrix*}
  \]
  Solution:\\
  $AB$ is not defined because the number of columns in $A$ (2) does not equal the number of rows in $B$ (3),
\[A_{3\times\underset{\uparrow}{2}}B_{\underset{\uparrow}{3}\times3}\,.\]
The product $BA$ is defined because the number of columns in $B$ (3) equals the number of rows in $A$.
\[BA=B_{3\times\underset{\uparrow}{3}}A_{\underset{\uparrow}{3}\times2}=\begin{bmatrix*}[r]6&1&3\\-1&1&4\\4& 1 & 0\end{bmatrix*}\begin{bmatrix*}[r]-3&0\\-1&2\\1&1\\\end{bmatrix*}=\begin{bmatrix*}[r]-16 & 5 \\ 6 & 6 \\ -13 & 2\end{bmatrix*}\]
The product $BA$ has dimensions $3\times2$ as expected.
\end{enumerate}
\end{example}

Note: When multiplying matrices it is helpful to proceed systematically by multiplying the first row times each of the columns to get the first row of the product, followed by the second row times each of the columns, to get the second row, etc.


\section{Diagonal Matrices}

Recall a square matrix is a matrix where the number of rows equals the number of columns, i.e. an $n\times n$ matrix.

\definition{The entries $a_{ij}$ of a square matrix $A$ for which $i=j$ form the \textbf{main diagonal} of $A$\,.}

\begin{example}
\[A = \begin{bmatrix} \circled{5} &6 &-7 \\ -1&\circled{-2}&3 \\  0 &4 &\circled{-1} \end{bmatrix}
\]
The main diagonal of $A$ consists of the entries 5, -2, and -1\,.
\end{example}

\definition{A square matrix in which every element not on the main diagonal is zero is called a \textbf{diagonal matrix}. A special type of diagonal matrix is the \textbf{identity matrix}, denoted by $I$, in which every entry on the diagonal is 1\,.}

\begin{example}\label{exam:diagonal}
  \[A= \begin{bmatrix*}[r] 3&0&0 \\ 0&4&0 \\0&0&-5 \\\end{bmatrix*}\]
    is a diagonal matrix, while
    \[I = \begin{bmatrix}1&0&0 \\ 0&1&0 \\ 0&0&1 \\\end{bmatrix}\]
      is the $3\times3$ identity matrix.
\end{example}

Note that if we wish to denote a particular identity matrix we can write $I_m$ to represent the $m\times m$ identity matrix.  So in Example~\ref{exam:diagonal} the identity matrix is $I_3$\,.

\section{Properties of Matrix Operations}
We now collect some of the basic properties of matrices involving matrix addition, scalar multiplication, and matrix multiplication.

\theorem{\label{thm:matrixproperties}Let $A$, $B$, and $C$ be matrices and let $a$ and $b$ be scalars.  Let $I$ be an identity matrix and $\zeromat$ a zero matrix.  Assuming that the dimensions of each of the matrices is such that the following operations is defined we have the following:
  % To allow for enumeration on the left, change to left equation mode (see
  % the custom command in the included file).  Then the amsmath subequations
  % environment allows for each equation to get its own number and we then
  % redefine \theequation to only print that number.
  \leqnomode
  \begin{subequations}
    \renewcommand{\theequation}{\arabic{equation}}
\begin{align}
A + B &= B + A & (\text{commutative law for addition}) \\
(A + B) + C &= A + (B + C) & (\text{associative law for addition})\\
A + \zeromat &= A\\
A + (-A) &= \zeromat\\
A(BC) &= (AB)C & (\text{associative law for multiplication})\\
a(AB) &= (aA)B =A(aB)\\
(ab)C &= a(bC)=b(aC)\\
A(B+C) &= AB + AC & (\text{left distributive law})\\ 
(A+B)C &= AC + BC & (\text{right distributive law})\\
a(B+C) &= aB + aC & (\text{scalar distributive law})\\
(a+b)C &= aC + bC & (\text{scalar distributive law})\\
AI &= A\\
IB &= B\\
1A &= A\\
A\zeromat &= \zeromat \\
0B &= \zeromat\\
a\zeromat &= \zeromat
\end{align}
  \end{subequations}\reqnomode}

\vspace{-1em}
As with regular numbers the associative laws of matrix addition and multiplication ensure it is meaningful to write $A+B+C$ and $ABC$ without using parentheses.

The properties of Theorem~\ref{thm:matrixproperties} are analogous to the properties of real numbers. However \textbf{not all} real number properties correspond to matrix properties.  We note the following

\begin{enumerate}
\item It is possible for $AB$ to equal zero even if $A \neq \zeromat$ and $B \neq \zeromat$\,:

  \begin{example}
    If 
    \[ A = \begin{bmatrix*}[r]-1&1\\2&-2\\\end{bmatrix*},~~B = \begin{bmatrix}1\\1\\\end{bmatrix}\]
        then 
        \[AB = \begin{bmatrix} 0\\0\\\end{bmatrix}=\zeromat\,,\]
          yet $A\neq\zeromat$ and $B\neq\zeromat$\,.
  \end{example}

\item Even if $AB = AC$ with $A\neq \zeromat$, it may occur that $B$ may not equal $C$\,.
  \begin{example}
    If 
\[A=\begin{bmatrix}1&2\end{bmatrix},~~ B=\begin{bmatrix*}[r]1&1\\-1&0\end{bmatrix*},~ C=\begin{bmatrix*}[r]3&-1\\-2&1\end{bmatrix*}\,,\]
then
\[AB = \begin{bmatrix*}[r]-1&1\end{bmatrix*},~~ AC=\begin{bmatrix*} -1&1\end{bmatrix*}\,.\]
  Therefore $AB = AC$ but $B\neq C$\,.\\
  \end{example}
  
\item In general, even when it is defined, $AB \neq BA$\,.  Matrix multiplication is \emph{not commutative}.

  \begin{example}
    If 
\[A=\begin{bmatrix*}[r]1&1\\-1&0\end{bmatrix*},~ B=\begin{bmatrix*}[r]3&1\\2&1\end{bmatrix*}\,,\]
then
\[AB = \begin{bmatrix*}[r]5&2\\-3&-1\end{bmatrix*},~~ BA=\begin{bmatrix*}[r]2&3\\1&2\end{bmatrix*}\,.\]
  Therefore $AB\neq BA$\,.\\
   \end{example}

\end{enumerate}

\subsection{Commutative Matrices}
For the exceptional case that one can commute the product of two matrices and still get the same result one has the following definition.
\definition{A matrix $A$ \textbf{commutes} with a matrix $B$ if $AB = BA$\,.}

\begin{example}
  For matrices $A$ and $B$ defined by
  \[A = \begin{bmatrix*}[r]-2&0\\0&3\\\end{bmatrix*}\,~~ B = \begin{bmatrix*}4&0\\0&-1\\\end{bmatrix*}\,,\]
   show that $A$ and $B$ commute.

   Solution:\\
    \[AB=\begin{bmatrix*}[r]-2&0\\0&3\\\end{bmatrix*}\begin{bmatrix*}[r]4&0\\0&-1\\\end{bmatrix*}=\begin{bmatrix*}[r]-8&0 \\ 0&-3\\\end{bmatrix*}\]

    \[BA=\begin{bmatrix*}[r]4&0\\0&-1\\\end{bmatrix*}\begin{bmatrix*}[r]-2&0\\0&3\\\end{bmatrix*}=\begin{bmatrix*}[r]-8&0 \\ 0&-3\\\end{bmatrix*} \]
      Since $AB=BA$ the matrices $A$ and $B$ commute.
\end{example}

\section{Matrix Equations}
So far we have used equality involving matrices when assigning a variable to a matrix, or similarly with other identities when we convert a matrix to an equivalent matrix.  In regular algebra one often creates equations involving variables and then seeks to find values of those variables that make the equation true (i.e. solve the equation).  This can also be done with matrices where some or often all entries may be unknown.  Matrix equality requires corresponding entries on both sides of a matrix equation must be equal; thus each entry generates an equation.  These equations could then be solved for the unknowns.  However it is usually quicker if we do operations on a matrix as a whole to solve for the unknowns.
\begin{example}
  Suppose $X$ is a matrix of unknowns and $C$ and $D$ are constant matrices defined by
  \[X=\begin{bmatrix}x_{11} & x_{12}\\x_{21}  & x_{22}\end{bmatrix}~~~C=\begin{bmatrix*}[r]1 & -2\\-1 & 3\end{bmatrix*}~~~D=\begin{bmatrix*}[r]2 & 0\\0 & -2\end{bmatrix*}\,.\]
  If the matrices satisfy the equation
  \[2X-4C=D\,,\]
  find $X$.

  Solution:\\
  One \emph{could} evaluate the left and right-hand sides directly as follows:
  \begin{align*}
    2\begin{bmatrix}x_{11} & x_{12}\\x_{21}  & x_{22}\end{bmatrix}-4\begin{bmatrix*}[r]1 & -2\\-1 & 3\end{bmatrix*}&=\begin{bmatrix*}[r]2 & 0\\0 & -2\end{bmatrix*}\\[.3em]
\begin{bmatrix*}[c]2x_{11} -4 & 2x_{12}+8\\2x_{21}+4  & 2x_{22}-12\end{bmatrix*}&=
  \begin{bmatrix*}[r]2 & 0\\0 & -2\end{bmatrix*}\,.\end{align*}
   Then equating corresponding terms on both sides gives:
    \begin{align*}
      2x_{11} -4 &= 2 &2x_{12}+8 &= 0\\
      2x_{21}+4 &= 0 &2x_{22}-12 &= -2\,.
    \end{align*}
    Solving the equations one has:
    \begin{align*}
      x_{11}&=3 &x_{12}&=-4\\
      x_{21}&=-2 &x_{22}&=5\,,
    \end{align*}
    So $X=\begin{bmatrix*}[r]3 & -4\\-2 & 5\end{bmatrix*}$\,.  However it is more useful just to work with the matrices as a whole as we would in a regular equation, using inverse operations to isolate the matrix variable:
    \begin{align*}
      2X-4C & = D\\
      2X&=D+4C \\
      X&=\frac{1}{2}(D+4C)\\
      X&=\frac{1}{2}D+2C \\
      X&=\frac{1}{2}\begin{bmatrix*}[r]2 & 0\\0 & -2\end{bmatrix*}+2\begin{bmatrix*}[r]1 & -2\\-1 & 3\end{bmatrix*}\\
      X&=\begin{bmatrix*}[r]1 & 0\\0 & -1\end{bmatrix*}+\begin{bmatrix*}[r]2 & -4\\-2 & 6\end{bmatrix*}\\
      X&=\begin{bmatrix*}[r]3 & -4\\-2& 5\end{bmatrix*}\,.
    \end{align*}
\end{example}

\section{Transpose of a Matrix}

\definition{The \textbf{transpose} of an $m\times n$ matrix $A$, denoted by $A^T$, is the $n\times m$ matrix whose $j^{th}$ column is the $j^{th}$ row of $A$. In symbols
  \[(A^T)_{ij}=A_{ji}~.\]}

Note: To find $A^T$ one interchanges the rows and columns of A.
\begin{example}
  Find the transpose of the following matrices:
\[
A = \begin{bmatrix*}[r] -1&2 \\ 3&1 \\\end{bmatrix*},~~B = \begin{bmatrix*}[r] 2&1&3 \\ -1&0&5 \\\end{bmatrix*}\,.
    \]

    Solution:\\
    Exchanging rows and columns on has:
\[
A^T = \begin{bmatrix*}[r] -1&3 \\ 2&1 \\\end{bmatrix*}, ~~B^T = \begin{bmatrix*}[r] 2&-1\\1&0\\3&5\\\end{bmatrix*}\,.
\]
\end{example}

\subsection{Properties of the Transpose}
\theorem{\label{thm:transposeproperties}Let $A$ and $B$ be matrices of dimensions such that the following operations are defined and $b$ a scalar, then the transpose has the following properties:
  \leqnomode
  \begin{subequations}
    \renewcommand{\theequation}{\arabic{equation}}
\begin{align}
  (A+B)^T &= A^T + B^T\\
  (AB)^T &= B^TA^T\\
  (A^T)^T &= A\\
  (bA)^T &= bA^T
\end{align}\end{subequations}\reqnomode}

\begin{example}
Given the matrices
\[ A= \begin{bmatrix}1&2&0\\3&0&1\\\end{bmatrix},~~B= \begin{bmatrix*}[r]1&2\\0&1\\-2&4\\\end{bmatrix*}\]
    compute $AB$ , $(AB)^T$ , $A^TB^T$ and $B^TA^T$\,.
    
Solution:\\
\[AB = \begin{bmatrix}1&2&0\\3&0&1\\\end{bmatrix} \begin{bmatrix*}[r]1&2\\0&1\\-2&4\\\end{bmatrix*} = \begin{bmatrix*}[r] 1&4\\1&10\\\end{bmatrix*} \]

      
\[(AB)^T = \begin{bmatrix*}[r]1&1\\4&10\\\end{bmatrix*}\]
        
\[A^TB^T = \begin{bmatrix} 1&3\\2&0\\0&1\\\end{bmatrix}\begin{bmatrix*}[r]1&0&-2\\2&1&4\\\end{bmatrix*} = \begin{bmatrix*}[r]7&3&10\\2&0&-4\\2&1&4\\\end{bmatrix*}\]
              
\[B^TA^T = \begin{bmatrix*}[r]1&0&-2\\2&1&4\\\end{bmatrix*}\begin{bmatrix}1&3\\2&0\\0&1\\\end{bmatrix} = \begin{bmatrix*}[r]1&1\\4&10\\\end{bmatrix*}\]

So $(AB)^T=B^TA^T$ as predicted by the theorem.  It does not equal $A^TB^T$.
\end{example}

The transpose property of a product can be generalized to more than two matrices.
\begin{example}
Prove that $(ABC)^T = C^TB^TA^T$ \\

Proof:
\[(ABC)^T = ((AB)C)^T = C^T(AB)^T = C^T(B^TA^T) = C^TB^TA^T\]
\end{example}

Generalizing to $k$ matrices we have the following result.

\theorem{Let $A_1$, $A_2$, \ldots,  $A_k$ be matrices for which the product $A_1A_2\cdots A_k$ is defined, then
\[(A_1A_2\cdots A_k)^T = A_k^T\cdots A_2^TA_1^T\,.\]
}

\subsection{Symmetric Matrices}

\definition{A square matrix , $A = [a_{ij}]$, is called \textbf{symmetric} if $a_{ij} = a_{ji}$ for all $i$ and $j$.  A square matrix is called \textbf{skew symmetric} if $a_{ij} = -a_{ji}$ for all $i$ and $j$.}

\begin{example}
  The following matrices are symmetric:
\[A= \begin{bmatrix} 1&2\\2&3\\\end{bmatrix},~~ B = \begin{bmatrix*}[r]2&-1&3\\-1&5&0\\3&0&-7\\\end{bmatrix*}\,.\]

  The following matrices are skew symmetric:
\[C = \begin{bmatrix*}[r]0&-1 \\ 1&0 \\\end{bmatrix*},~~ B = \begin{bmatrix*}[r]0&-1&2\\1&0&1\\-2&-1&0\\\end{bmatrix*}\,.\]\\
\end{example}
    
\theorem{A square matrix $A = [a_{ij}]$ is symmetric if and only if $A^T = A$. It is skew symmetric if and only if $A^T = -A$\,.}

\section{Power of a Matrix}

\definition{Let $A$ be a square matrix, then the $n^{\textsuperscript{th}}$ power of $A$, denoted $A^n$, is the product of $n$ factors of $A$, i.e.
\begin{align*}
A^1 &= A \\
A^2 &= AA \\
A^3 &= AAA \\
&~\,\vdots \\
A^n & = \underbrace{AA\cdots A}_{n~\text{times}}
\end{align*}}

\begin{example}
  If 
\[
A=\begin{bmatrix*}[r]1&-1&3\\0&1&-2\\-1&1&1\\\end{bmatrix*}
\]
find $A^2$\,.

Solution:
\[A^2=\begin{bmatrix*}[r]1&-1&3\\0&1&-2\\-1&1&1\\\end{bmatrix*}\begin{bmatrix*}[r]1&-1&3\\0&1&-2\\-1&1&1\\\end{bmatrix*}=
\begin{bmatrix*}[r]1 + 0 -3 & -1-1+3 & 3+2+3\\ 0+0+2 & 0+1-2 & 0-2-2 \\ -1+0-1 & 1+1+1 & -3-2+1 \end{bmatrix*}\]
\[A^2 = 
\begin{bmatrix*}[r]
-2&1&8 \\ 2&-1&-4 \\ -2&3 &-4 \end{bmatrix*}
\]
\end{example}

Having defined the power of a matrix, it is now possible to create meaningful polynomial functions of a square matrix such as
\[p(A)=c_0I+c_1A+c_2A^2+\ldots+c_nA^n\]
for some positive integer $n$ and the identity matrix $I$ of the same dimension of $A$, and scalars $c_i$\,.\footnote{Note some texts
  % such as Lang's Linear Algebra
  will define $A^0=I$ (analogous to $x^0=1$) so one may write $p(A)=c_0A^0+c_1A^1+c_2A^2+\ldots+c_nA^n$\,.}  In more advanced courses we could similarly consider a power series in $A$ where we let $n\to\infty$.  Then questions of the meaning of the convergence of such a series needs to be addressed, just as with power series in terms of real variable $x$.

\subsection{Idempotent Matrices}

\definition{Matrix $A$ is called \textbf{idempotent} if $A^2 = A$\,.}

\begin{example}
Show that the matrix $A$ defined by
\[A = \begin{bmatrix*}[r]4&-1\\12&-3\\\end{bmatrix*}\]
is idempotent.

Solution:\\
\[A^2=AA=\begin{bmatrix*}[r]4&-1\\12&-3\\\end{bmatrix*} \begin{bmatrix*}[r]4&-1\\12&-3\\\end{bmatrix*}=\begin{bmatrix*}[r]4&-1\\12&-3\\\end{bmatrix*} = A \]

\end{example}

% If we wanted we could introduce other definitions like nilpotent and unipotent
% here, but this may be better left for problem sets.

\section{Ordered $n$-tuples}
\definition{The ordered sequence $(x_1,x_2,\ldots,x_n)$ where $x_i$ are real numbers and $n$ is a positive integer is called an \textbf{ordered $\bm{n}$-tuple}.  The set of all ordered $n$-tuples is called \textbf{$\bm{n}$-space} and is denoted by $\bm{\mathset{R}^n}$.}

\begin{example}
  \begin{itemize}
  \item $(5,3)$ is an ordered 2-tuple in $\mathset{R}^2$.  Note that it is different from $(3,5)$ (order matters).
  \item $(1,-2,4)$ is an ordered 3-tuple in $\mathset{R}^3$\,.
  \item $(-3,2.1,7,4,-9.5)$ is an ordered 5-tuple in $\mathset{R}^5$\,.
  \end{itemize}
\end{example}
As the last example suggests, an obvious geometric interpretation presents itself.  We can think of the ordered 2-tuple $(5,3)$ as representing a \textbf{point} in the two-dimensional coordinate plane.  Alternatively we can consider it as representing a directed line segment (an arrow), called a \textbf{vector}, originating at the origin of the coordinate system and terminating at the point.
\begin{center}
\includegraphics[height=1.5in]{matrices/tuplepoint}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\includegraphics[height=1.5in]{matrices/tuplevector}
\end{center}
Similarly $(1,-2,4)$ could be considered a representation of a point or vector in three-dimensional space, while an ordered $n$-tuple of higher dimension can be thought of as a generalized point or $n$-vector in some higher-dimensional space.  In future we will tend to use a vector interpretation and typically refer to ordered $n$-tuples as vectors. However vectors, as will be discussed further in Chapter~\ref{chap:vectors}, are constructions that are conceptually independent of a particular set of coordinates ($n$-tuple) used to represent them.

\subsection{Notation}
We will use lower case boldface letters such as $\lvec{x}$ to represent the ordered $n$-tuple $(x_1,x_2,\ldots,x_n)$, or vector. For example,  $\lvec{x}=(5,3)$\,.  When hand-written it is more common to put an arrow or bar over the letter, such as $\vec{x}$, or $\bar{x}$. When speaking of the ordered $n$-tuple containing all zeros we will write $\lvec{0}$\,.   It is convenient, when representing an ordered $n$-tuple (vector) by a matrix, to use an $\bm{n\times1}$ \textbf{column matrix}
\[\lvec{x}=\begin{bmatrix}x_1\\x_2\\\vdots\\x_n\end{bmatrix}\,'\]
We can now write $A\lvec{x}$, where previously we would have written $AX$, provided $A$ is an $m\times n$ matrix so the multiplication is meaningful.  If we wish to represent a vector within a sentence as a matrix we can conveniently use the transpose, since then $\lvec{x}=[x_1\, x_2\, \ldots\, x_n]^T$.

The motivation for considering a vector to be represented by a column matrix arises, in part, from linear systems.  Recall the linear system of $m$ equations in $n$ unknowns is:
\begin{align*}
  \,a_{11}x_1\, + \,a_{12}x_2\, + \ldots+\,a_{1n}x_n\, &= b_1 \\
  \,a_{21}x_1\, + \,a_{22}x_2\, + \ldots+\,a_{2n}x_n\, &= b_2 \\
  \vdots\,~~~~~~~~~~~~~~~~~\\
  a_{m1}x_1 + a_{m2}x_2 + \ldots+a_{mn}x_n &= b_m 
\end{align*}
By assigning the coefficient constants to $A$ as before, the unknowns to vector $\lvec{x}$ and the right-hand side constants to vector $\lvec{b}$ as follows
\[A = \begin{bmatrix}
a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots &  & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn}
\end{bmatrix} \, \, , \, \, \lvec{x} = \begin{bmatrix}
x_1\\x_2\\\vdots\\x_n
\end{bmatrix} \, \, , \, \, \lvec{b} = \begin{bmatrix}
b_1\\b_2\\\vdots\\b_m
\end{bmatrix}\ ,\]
we now see that we can represent the linear system in terms of matrix multiplication in terms of the simple matrix equation:
\[A\lvec{x}=\lvec{b}\ .\]
This follows since multiplying the left hand side out gives precisely the $m\times 1$ column matrix
\[A\lvec{x}= \begin{bmatrix}
a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n \\ a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n
\end{bmatrix}\ .\]
The matrix equality of this with the right-hand side matrix $\lvec{b}=[b_1,b_2,\ldots b_m]^T$ gives back our original linear system of equations.  This shows a clear advantage for defining matrix multiplication the way that we have done.

\begin{example}
  The linear system
  \begin{align*}
    3x_1+2x_3 &= 7\\
    x_1+4x_2-4x_3 &= 3\\
    2x_1+2x_2 +8x_3 &= 1\\
  \end{align*}
  can be represented by the matrix equation $A\lvec{x}=\lvec{b}$ where
  \[A=\begin{bmatrix*}[r]
  ~3&0&2\\~1&4&-4\\3&3&8
  \end{bmatrix*}, ~~\lvec{x}=\begin{bmatrix}
  x_1\\x_2\\x_3
  \end{bmatrix}, ~\text{and}~\lvec{b}= \begin{bmatrix}
    7\\3\\1
  \end{bmatrix}\,.\]
\end{example}

\subsection{Matrix Multiplying a Vector}
\label{subsec:matrixmultiplyingvector}
We can consider the $m\times n$ matrix $A$ to be composed of $n$ columns of vectors in $m$-space labelled $\lvec{a}_1$, $\lvec{a}_2$, \ldots, $\lvec{a}_n$\,.  These are the \textbf{column vectors} of $A$\,.  We write
\[A= \begin{bmatrix}
a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots &  & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn}
\end{bmatrix}=[\lvec{a}_1\, \lvec{a}_2\, \cdots \,\lvec{a}_n]\ .\]
Cast in this form we see that our previous product $A\lvec{x}$ can be written as a sum of $m\times 1$ matrices (vectors), namely
\[A\lvec{x}= \begin{bmatrix} a_{11}x_1 \\  a_{21}x_1 \\ \vdots \\ a_{m1}x_1 \end{bmatrix}
+\begin{bmatrix} a_{12}x_2 \\  a_{22}x_2 \\ \vdots \\ a_{m2}x_2 \end{bmatrix}
+\ldots+
\begin{bmatrix} a_{1n}x_n \\  a_{2n}x_n \\ \vdots \\ a_{mn}x_n \end{bmatrix}
=x_1\lvec{a}_1+x_2\lvec{a}_2+\ldots+x_n\lvec{a}_n\, .\]
We have the following result.
\theorem{If $A=[\lvec{a}_1\, \lvec{a}_2\,\ldots\, \lvec{a}_n]$ is an $m\times n$ matrix written in terms of its column vectors $\lvec{a}_i$, then the matrix product of $A$ times the vector $\lvec{x}=[x_1\, x_2\, \ldots\, x_n]^T$ in $\mathset{R}^n$  can be written
  \[A\lvec{x}=x_1\lvec{a}_1+x_2\lvec{a}_2+\ldots+x_n\lvec{a}_n\, .\]
}

The matrix equation $A\lvec{x}=\lvec{b}$ takes the new vector equation form
\[x_1\lvec{a}_1+x_2\lvec{a}_2+\ldots+x_n\lvec{a}_n=\lvec{b}\,.\]
From this follows the following theorem.
\theorem{The linear system $A\lvec{x}=\lvec{b}$ is consistent if and only if $\lvec{b}$ can be written as a linear combination of the columns of matrix $A$\,.}

\begin{example}
  Find a vector equation involving only constant vectors that is equivalent to the linear system
  \begin{align*}
    3x_1+2x_3 &= 7\\
    x_1+4x_2-4x_3 &= 3\\
    2x_1+2x_2 +8x_3 &= 1
  \end{align*}

  Solution:\\
  The above linear system is equivalent to the vector equation
    \[\begin{bmatrix}
    3x_1+2x_3 \\
    x_1+4x_2-4x_3\\
    2x_1+2x_2 +8x_3
    \end{bmatrix}
    =\begin{bmatrix}[c]
    7\\3\\1
    \end{bmatrix}\,.\]
    An equivalent vector equation is
    \[\begin{bmatrix*}[r]
      3x_1\\
      x_1\\
      2x_1
    \end{bmatrix*}
    +\begin{bmatrix*}[r]
    0x_2\\
    4x_2\\
    2x_2
    \end{bmatrix*}
    +\begin{bmatrix}[r]
    2x_3 \\
    -4x_3\\
    8x_3
    \end{bmatrix}
    =\begin{bmatrix}[c]
    7\\3\\1\end{bmatrix}\ .\]
    Finally factoring out the variables one has:
    \[x_1\begin{bmatrix*}[r]
      3\\
      1\\
      2
    \end{bmatrix*}
    +x_2\begin{bmatrix*}[r]
    0\\
    4\\
    2
    \end{bmatrix*}
    +x_3\begin{bmatrix}[r]
    2 \\
    -4\\
    8
    \end{bmatrix}
    =\begin{bmatrix}[c]
    7\\3\\1\end{bmatrix}\ .\]
    This result also follows directly from our previous formula
    \[x_1\lvec{a}_1+x_2\lvec{a}_2+\ldots+x_n\lvec{a}_n=\lvec{b}\,,\]
    since
    \[A=[\lvec{a}_1\lvec{a}_2\lvec{a}_3]=\begin{bmatrix*}[r] 3 & 0 & 2 \\ 1 & 4 & -4 \\ 2 & 2 & 8 \end{bmatrix*}\ \text{and}\ \lvec{b}=\begin{bmatrix*}[r] 7 \\ 3  \\ 1\end{bmatrix*}\,.\]
\end{example}

\subsection{General Solution of a Linear System}

Consider a general linear system $A\lvec{x}=\lvec{b}$.  If the system is consistent then there exists at least one particular solution $\lvec{x}_p$ of the system.  If $\lvec{x}$ is any other solution of the system then the vector difference $\lvec{x}_0=\lvec{x}-\lvec{x}_p$ is a solution of the \textbf{associated homogeneous system} $A\lvec{x}=\lvec{0}$ since
\[A\lvec{x}_0=A(\lvec{x}-\lvec{x}_p)=A\lvec{x}-A\lvec{x}_p=\lvec{b}-\lvec{b}=\lvec{0}\,.\]
Furthermore any vector $\lvec{x}=\lvec{x}_p+\lvec{x}_0$ where $\lvec{x}_0$ is any solution of the associated homogeneous system is a solution of the original linear system since
\[A\lvec{x}=A(\lvec{x}_p+\lvec{x}_0)=A\lvec{x}_p+A\lvec{x}_0=\lvec{b}+\lvec{0}=\lvec{b}\,.\]
We have the following result
\theorem{For any consistent linear system $A\lvec{x}=\lvec{b}$ the general solution can be written in the form
  \[\lvec{x}=\lvec{x}_p+\lvec{x}_0\]
  where $\lvec{x}_p$ is a particular solution of the linear system and $\lvec{x}_0$ is any solution of the associated homogeneous system, i.e. $A\lvec{x}_0=\lvec{0}$\,.}

As such one approach to solving a non-homogeneous linear system is to find a particular solution and then add to it the general solution of the associated homogeneous system.  This is a pattern that arises in other contexts such as solving differential equations.  In practice for us, the separation of the solution of a consistent linear system into its particular solution plus a general solution to the homogeneous system (which may involve parameters) arises straight from Gauss-Jordan elimination.
\begin{example}
Express all solutions of the following system as a sum of a particular solution plus a solution of the associated homogeneous system.
\begin{align*}
  x_3+2x_4-x_5&= 4 \\ x_4-x_5 &= 3\\ x_3+3x_4-2x_5&=7\\ 2x_1+4x_2+x_3+7x_4&=7
\end{align*}

Solution:\\
The augmented matrix
\[\begin{bmatrix}[rrrrr|r]
    0 & 0 & 1 & 2 &-1 & 4\\
    0 & 0 & 0 & 1 &-1 & 3 \\
    0 & 0 & 1 & 3& -2 & 7 \\
    2 & 4 & 1 & 7 & 0 & 7
\end{bmatrix}\]
reduces via Gauss-Jordan elimination to the RREF and corresponding equivalent linear system
\[\begin{bmatrix}[ccccr|r]
    \circled{1} & 2 & 0 & 0 & 3 & -6\\
    0 & 0 & \circled{1} & 0 & 1 & -2\\
    0 & 0 & 0 & \circled{1}& -1 & 3\\
    0 & 0 & 0 & 0 & 0 & 0
  \end{bmatrix}~~\Leftrightarrow~~\parbox{10em}{
  \begin{align*}
    x_1+2x_2+3x_5 &=-6\\
    x_3+x_5 &=-2\\
    x_4-x_5 &=3\\
    0&=0
  \end{align*}}\]
The general solution is found by setting free variables $x_2$ and $x_5$ to parameters, $\boxed{x_2=s}$ and $\boxed{x_5=t}$, and solving by back-substitution the remaining (leading) variables:
\begin{itemize}
  \item $x_4-x_5 =3 \implies x_4-t=3 \implies \boxed{x_4=3+t}$
  \item $x_3+x_5 =-2 \implies x_3+t=-2 \implies \boxed{x_3=-2-t}$
  \item $x_1+2x_2+3x_5 =-6 \implies x_1+2s+3t=-6 \implies \boxed{x_1=-6-2s-3t}$.
\end{itemize}
Written as a vector the solution is
\[\lvec{x}=\begin{bmatrix}-6-2s-3t\\s\\-2-t\\3+t\\t\end{bmatrix}
=\begin{bmatrix*}[r]-6\\0\\-2\\3\\0\end{bmatrix*}
+\begin{bmatrix*}[r]-2s\\s\\0\\0\\0\end{bmatrix*}
+\begin{bmatrix*}[r]-3t\\0\\-t\\t\\t\end{bmatrix*}
=\underbrace{\begin{bmatrix*}[r]-6\\0\\-2\\3\\0\end{bmatrix*}}_{\lvec{x}_p}
+\underbrace{s\begin{bmatrix*}[r]-2\\1\\0\\0\\0\end{bmatrix*}
+t\begin{bmatrix*}[r]-3\\0\\-1\\1\\1\end{bmatrix*}}_{\lvec{x}_0}=\lvec{x}_p+\lvec{x}_0
\]
As seen in Example~\ref{example:homogeneous} the vector $\lvec{x}_0$ which involves the parameters is indeed the general solution of the homogeneous system. 
\end{example}
 Note that the particular solution $\lvec{x}_p$ is not unique when there
 are parameters.  In this problem we could introduce new parameters
 $\tilde{s}$ and $\tilde{t}$ by the substitutions $s=\tilde{s}+1$ and
 $t=\tilde{t}-2$ and the new particular solution would be, after
 collecting all the constants in one vector,
 $\lvec{x}_p=[-2\ 1\ 0\ 1\, -2]^T$\,.  The homogeneous solution with that substitution would have the same form with $s$ and $t$ replaced by $\tilde{s}$ and $\tilde{t}$.

 For linear systems with a unique solution (no parameters) $\lvec{x}_p$ will be that unique solution and the solution to the associated homogeneous system will just be $\lvec{x}_0=\lvec{0}$\,.

\section{Matrix Inversion}

We have seen we can write a linear system $A\lvec{x}=\lvec{b}$.  If we had the algebraic problem $ax=b$ where $a$ and $b$ were just real constants and $x$ were a variable we would just divide by $a$ (assuming it was non-zero), or equivalently multiply by $a^{-1}$ on both sides to get $(a)^{-1}ax=(a)^{-1}b$, or just $x=(a)^{-1}b$.  This raises the question of whether a \emph{matrix} multiplicative inverse can be found that we could similarly left-multiply to solve our matrix equation.  Even the algebra problem, however, suggests this may not always be possible since $a=0$ has no multiplicative inverse. 

\definition{Let $A$ be an $n\times n$ matrix. The \textbf{inverse of}~$\bm{A}$ is an $n\times n$ matrix denoted $A^{-1}$ satisfying:
  \[AA^{-1} = A^{-1}A = I\]
  where $I$ is the $n\times n$ identity matrix.}

\definition{If $A^{-1}$ exists, we say $A$ is \textbf{invertible} (or \textbf{non-singular}).  If $A$ does not have an inverse it is said to \textbf{noninvertible} or \textbf{singular}.}

\begin{example}If $A=\begin{bmatrix}7 & 2\\3 & 1\end{bmatrix}$ show $A^{-1}=\begin{bmatrix*}[r]1 & -2\\-3 & 7\end{bmatrix*}$ is an inverse of $A$.

  Solution:\\
  We have by direct calculation:
  \[AA^{-1}=\begin{bmatrix}7 & 2\\3 & 1\end{bmatrix}\begin{bmatrix*}[r]1 & -2\\-3 & 7\end{bmatrix*}=\begin{bmatrix}7-6 & -14+14\\3-3 & -6+7\end{bmatrix}=\begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}=I\,,\]
    \[A^{-1}A=\begin{bmatrix*}[r]1 & -2\\-3 & 7\end{bmatrix*}\begin{bmatrix}7 & 2\\3 & 1\end{bmatrix}=\begin{bmatrix}7-6 & 2-2\\-21+21 & -6+7\end{bmatrix}=\begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}=I\,.\]
      Thus $A^{-1}$ is an inverse of invertible matrix $A$\,.
\end{example}

\subsection*{Properties of the Inverse}
\theorem{If an $n\times n$ matrix $A$ has an inverse then that inverse is unique.}

Proof: \\
Suppose matrix $A$ has inverse $A^{-1}$ and that $B$ is another inverse of $A$ then, by definition,
\[AA^{-1} = A^{-1}A = I\]
and
\[AB = BA = I\,.\]
Using these properties and the associativity of matrix multiplication (Theorem~\ref{thm:matrixproperties}) we have:
\[B = BI = B(AA^{-1})= (BA)(A^{-1})= IA^{-1} = A^{-1}\,.\]
Therefore $B = A^{-1}$ and the inverse is unique.

\theorem{\label{thm:inverseofinverse}If an $n\times n$ matrix $A$ is invertible then $A^{-1}$ is invertible and the inverse of $A^{-1}$ is $A$\,. In symbols:
  \[ (A^{-1})^{-1}=A \,. \]}

Proof: \\
The defining property $AA^{-1} = A^{-1}A = I$ implies that left and right multiplying $A^{-1}$ by $A$ gives the identity $I$. 

\theorem{If $A$ is an $n\times n$ invertible matrix, and $c\neq0$ is a scalar then
  \[(cA)^{-1}=\frac{1}{c}A^{-1}\]}

Proof:\\
We must show that
\[(cA)\left(\frac{1}{c}A^{-1}\right)=\left(\frac{1}{c}A^{-1}\right)(cA)=I\]
Using the properties of scalar and matrix multiplication (Theorem~\ref{thm:matrixproperties}) we have:

\[(cA)\left(\frac{1}{c}A^{-1}\right)=c\left[A\left(\frac{1}{c}A^{-1}\right)\right]=c\left[\frac{1}{c}\left(AA^{-1}\right)\right]=c\left(\frac{1}{c}I\right)=\left(c\frac{1}{c}\right)I=1I=I\,,
\]
Similarly:
\[\left(\frac{1}{c}A^{-1}\right)(cA)=\frac{1}{c}\left[A^{-1}\left(cA\right)\right]=\frac{1}{c}\left[c\left(A^{-1}A\right)\right]=\frac{1}{c}\left(cI\right)=\left(\frac{1}{c}c\right)I=1I=I\,.
\]
Thus $\displaystyle(cA)^{-1}=\frac{1}{c}A^{-1}$\,.

\theorem{If $A$ and $B$ are $n\times n$ invertible matrices, then the product $AB$ is also invertible with
\[(AB)^{-1} = B^{-1}A^{-1}\,.\]}
Proof:\\
$A$ and $B$ invertible imply $A^{-1}$ and $B^{-1}$ exist satisfying
\[AA^{-1} = A^{-1}A = I\,,\]
\[BB^{-1} = B^{-1}B = I\,.\]
We must show that:
\[(AB)(B^{-1}A^{-1}) = (B^{-1}A^{-1})(AB) = I\,.\]
We have:
\[(AB)(B^{-1}A^{-1}) = A(BB^{-1})A^{-1} = AIA^{-1}= AA^{-1} = I\,.\]
Similarly
\[(B^{-1}A^{-1})(AB) = B^{-1}(A^{-1}A)B=B^{-1}IB = B^{-1}B = I\,.\]
Thus $(AB)^{-1} = B^{-1}A^{-1}$.

The previous theorem generalizes to a product of $k$ matrices.
\theorem{If $A_1,A_2,\ldots,A_k$ are $n\times n$ invertible matrices then the product $A_1A_2\cdots A_k$ is also invertible with
\[(A_1A_2\cdots A_k)^{-1} = A_k^{-1}\cdots A_2^{-1}A_1^{-1}\,.\]}

\theorem{If $A$ is a $n\times n$ invertible matrix, then $A^T$ is also invertible with
\[(A^T)^{-1} = (A^{-1})^T\,.\]}

Proof:\\
$A$ is invertible so $A^{-1}$ exists satisfying
\[AA^{-1} = A^{-1}A = I\,.\]
We must show that:
\[A^T(A^{-1})^T = (A^{-1})^T A^T = I\]
We have:
\[A^T(A^{-1})^T = (A^{-1}A)^T = I^T = I\,,\]
\[(A^{-1})^T A^T = (AA^{-1})^T = I^T = I\,.\]
Therefore $(A^T)^{-1} = (A^{-1})^T$\,.

\begin{example}

Simplify $(AB)^{-1}(AB^{-1})(BA^T)(DA^{-1})^T$\,.

Solution:
\begin{align*}
(AB)^{-1}(AB^{-1})(BA^T)(DA^{-1})^T &= (B^{-1}A^{-1})(AB^{-1})(BA^T)((A^{-1})^TD^T)\\
  &= B^{-1}(A^{-1}A)(B^{-1}B)(A^T(A^T)^{-1})D^T\\
  &= B^{-1}(I)(I)(I)D^T\\
  &= B^{-1}D^T\\
\end{align*}

\end{example}

\subsection{Orthogonal Matrices}
A special class of square matrices is defined in terms of the properties of its inverse.

\definition{A square matrix $A$ is \textbf{orthogonal} if $\boxed{A^{-1}=A^T}$\,.}

\begin{example}
  The square matrix $A=\frac{1}{\sqrt{2}}\begin{bmatrix*}[r] 1 & -1 \\ 1 & 1 \end{bmatrix*}$ is orthogonal since $A^T=\frac{1}{\sqrt{2}}\begin{bmatrix*}[r] 1 & 1 \\ -1 & 1 \end{bmatrix*}$ and
  \[AA^T=\left(\frac{1}{\sqrt{2}}\begin{bmatrix*}[r] 1 & -1 \\ 1 & 1 \end{bmatrix*}\right)\left(\frac{1}{\sqrt{2}}\begin{bmatrix*}[r] 1 & 1 \\ -1 & 1 \end{bmatrix*}\right)=\frac{1}{2}\begin{bmatrix*} 2 & 0 \\ 0 & 2 \end{bmatrix*}=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}=I\,.\]
  Similarly $A^TA=I$ and thus $A^{-1}=A^T$\,.
\end{example}

\subsection{Finding the Inverse}
The following example illustrates how to find the inverse using row operations.
\begin{example}

Find the inverse of $A =  \begin{bmatrix*}[r] -1 & 2 \\ -3 & 5 \end{bmatrix*}$\,.

Solution:\\
This solution needs expansion (as per the in-class example) and show the row operations.

If $A^{-1}$ exists, then $AA^{-1} = A^{-1}A = I$\\
Assume that $A^{-1}$ exists, given by $A = \begin{bmatrix} a&b\\c&d\end{bmatrix}$\\

$AA^{-1} = I$ implies

\[\begin{bmatrix}-1&2\\-3&5\end{bmatrix}\begin{bmatrix}a&b\\c&d\end{bmatrix} = \begin{bmatrix}1&0\\0&1\end{bmatrix}\]

\[\begin{bmatrix} -a + 2c & -b + 2d \\ -3a + 5c & -3b + 5d \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0& 1 \end{bmatrix}\]

Matrix equality gives four equations in the four unknowns ($a$, $b$, $c$, and $d$).  However the two equations arising from the first column involve only $a$ and $c$ and the two equations arising from the second column involve only $b$ and $d$.  Therefore we really need to solve two linear systems involving two unknowns, one per column.  The first column system solution is as follows.
\[\parbox{10ex}{\begin{align*}
    -a + 2c &= 1 \\
    -3a + 5c &= 0\end{align*}}
\ \ \Leftrightarrow\  \begin{bmatrix}[rr|r] -1 & 2 & 1 \\ -3 & 5 & 0\end{bmatrix}\]
  \[
\begin{bmatrix}[rr|r]
  -1 & 2 & 1\\
  -3 & 5 & 0
\end{bmatrix}\Rightarrow\rowopmatrix{\rowop{R_1}{-R_1}\\\rowop{R_2}{R_2-3R_1}}{\begin{bmatrix}[rr|r]
  1 & -2 & -1\\
  0 & -1 & -3
\end{bmatrix}}\Rightarrow\rowopmatrix{\rowop{R_1}{R_1-2R_2}\\\rowop{R_2}{-R_2}}{\begin{bmatrix}[rr|r]
  1 & 0 & 5\\
  0 & 1 & 3
\end{bmatrix}}
\Rightarrow\begin{matrix}
  a=5 \\
  c=3
\end{matrix}
  \]
  Similarly the second column system and solution is
  \[\parbox{10ex}{\begin{align*}
    -b + 2d &= 0 \\
    -3b + 5d &= 1\end{align*}}
\ \ \Leftrightarrow\  \begin{bmatrix}[rr|r] -1 & 2 & 0 \\ -3 & 5 & 1\end{bmatrix}\]
  \[
\begin{bmatrix}[rr|r]
  -1 & 2 & 0\\
  -3 & 5 & 1
\end{bmatrix}\Rightarrow\rowopmatrix{\rowop{R_1}{-R_1}\\\rowop{R_2}{R_2-3R_1}}{\begin{bmatrix}[rr|r]
  1 & -2 & 0\\
  0 & -1 & 1
\end{bmatrix}}\Rightarrow\rowopmatrix{\rowop{R_1}{R_1-2R_2}\\\rowop{R_2}{-R_2}}{\begin{bmatrix}[rr|r]
  1 & 0 & -2\\
  0 & 1 & -1
\end{bmatrix}}
\Rightarrow\begin{matrix}
  b=-2 \\
  d=-1
\end{matrix}
  \]

  Therefore $A^{-1}=\begin{bmatrix*}[r] 5 & -2 \\ 3 & -1\end{bmatrix*}$\,.
Comparison of the solutions for the two systems shows that the row operations to solve both systems will depend, in the event there is a unique solution, entirely on the coefficient matrix.  This suggests solving both systems simultaneously using the augmented matrix $[A|I]$ where $I$ is the identity matrix:
\[[A|I]=\begin{bmatrix}[rr|rr] -1 & 2 & 1 & 0\\ -3 & 5 & 0 & 1\end{bmatrix}\]
  Reducing to RREF gives
  \[
\begin{bmatrix}[rr|rr]
  -1 & 2 & 1 & 0\\
  -3 & 5 & 0 & 1
\end{bmatrix}\Rightarrow\rowopmatrix{\rowop{R_1}{-R_1}\\\rowop{R_2}{R_2-3R_1}}{\begin{bmatrix}[rr|rr]
    1 & -2 & -1 & 0\\ 0 & -1 & -3 & 1\end{bmatrix}}\Rightarrow
\rowopmatrix{\rowop{R_1}{R_1-2R_2}\\\rowop{R_2}{-R_2}}{
\begin{bmatrix}[rr|rr] 1 & 0 & 5 & -2\\ 0 & 1 & 3 & -1\end{bmatrix}}
\]
We see the inverse, after the operations have been completed, is the right-hand side of the final augmented matrix which has the form $[I|A^{-1}]$. Thus 
\[A^{-1} = \begin{bmatrix*}[r] 5 & -2 \\ 3 &-1 \end{bmatrix*}\]

In general we see that to find the inverse we do the reduction  $[A|I]\Rightarrow[I|A^{-1}]$\,. If the left hand side cannot reduce to $I$, then no inverse exists.
\end{example}

\subsection*{Steps for Finding the Inverse of a Matrix:}

\begin{enumerate}
  \item Write the identity matrix (of the same dimension as $A$) adjacent to the matrix $A$ to form an augmented matrix $[A|I]$.
  \item Perform row operations on this augmented matrix until the matrix that was $A$ is reduced to the identity matrix if possible.
  \[[I|A^{-1}]\]
  \item The matrix in the position of the original identity matrix is $A$'s inverse $A^{-1}$\,.
\end{enumerate}
In summary $[A|I]\Rightarrow[I|A^{-1}]$\,.  If the procedure cannot be successfully completed then $A$ is noninvertible.

The previous steps can be applied once and for all to the $2\times2$ matrix $\begin{bmatrix}a&b\\c&d\end{bmatrix}$ to find the following inverse which can then be confirmed by direct matrix multiplication.

\theorem{\label{thm:twodinverse}If $A = \begin{bmatrix}a&b\\c&d\end{bmatrix}$ is a $2\times2$ matrix with $ad-bc\neq0$, then $A^{-1}$ exists and
\[A^{-1} = \frac{1}{(ad-bc)}\begin{bmatrix*}[r]d&-b\\-c&a\end{bmatrix*}\,.\]}

\begin{example}
  Find $A^{-1}$ if $A = \begin{bmatrix*}[r] 2 & 5 \\ -3 &7 \end{bmatrix*}$.

  Solution:\\
  Since $a= 2$, $b=5$, $c=-3$, and $d= 7$ we have 
  \[ad-bc = 2(7)-5(-3) = 29\]
  which is nonzero so the inverse matrix $A^{-1}$ exists and equals
  \[A^{-1}=\frac{1}{(ad-bc)}\begin{bmatrix*}[r]d&-b\\-c&a\end{bmatrix*}=\frac{1}{29}\begin{bmatrix*}[r]7&-5\\3&2\end{bmatrix*}
    =\begin{bmatrix*}[r]\frac{7}{29}&-\frac{5}{29}\\[.2em]\frac{3}{29}&\frac{2}{29}\end{bmatrix*}\]
\end{example}


% Row operations need to be added below.
% This example is skipped in the slides and so I skipped it here
\begin{comment}
\begin{example}
Find the inverse of $A = \begin{bmatrix*}[r] 1 &1&2\\0&3&1\\1&-2&2\end{bmatrix*}$\,.

Solution:\\  
\[[A|I] =\begin{bmatrix}[rrr|rrr]  1&1&2 &1&0&0\\0&3&1&0&1&0\\1&-2&2&0&0&1              \end{bmatrix} \]
Perform the necessary row operations to get:
\[[A|I] =\begin{bmatrix}[rrr|rrr] 1&0&0&\frac{8}{3} &-2 &-\frac{5}{3}\\[.2em]0&1&0&\frac{1}{3}&0&-\frac{1}{3}\\[.2em]0&0&1&-1&1&1\end{bmatrix} \]
\[A^{-1} = \begin{bmatrix*}[r]\frac{8}{3}&-2&-\frac{5}{3}\\[.2em]\frac{1}{3}&0 &-\frac{1}{3}\\[.2em]-1&1&1\end{bmatrix*}\]
\end{example}
\end{comment}

\begin{example}\label{example:matrixinverse}
  Find the inverse of $A = \begin{bmatrix*}[r] 2 & 1 & 0 \\ -4 &-1 & -3 \\ 3 & 1 &2\end{bmatrix*}$\,.

    Solution:\\
    We reduce $[A|I]$ to RREF:
    \[[A|I] = \begin{bmatrix}[rrr|rrr]2&1&0&1&0&0\\-4&-1&-3&0&1&0\\3&1&2&0&0&1\end{bmatrix}\hspace{3em}\]
      \[\Downarrow\]
      \begin{flalign*}&\rowopmatrix[15.7em]{\\ \rowop{R_2}{R_2+2R_1} \\ \rowop{R_3}{R_3-\frac{3}{2}R_1}}{%
          \begin{bmatrix}[rrr|rrr]2&1&0&1&0&0\\0&1&-3&2&1&0\\0&-\frac{1}{2}&2&-\frac{3}{2}&0&1\end{bmatrix}}
      &\end{flalign*}
      \[\Downarrow\]
      \begin{flalign*}&\rowopmatrix[15.7em]{\\ \\ \rowop{R_3}{R_3+\frac{1}{2}R_2}}{%
          \begin{bmatrix}[rrr|rrr]2&1&0&1&0&0\\0&1&-3&2&1&0\\0&0&\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&1\end{bmatrix}}
      &\end{flalign*}
      \[\Downarrow\]
      \begin{flalign*}&\rowopmatrix[15.7em]{\rowop{R_1}{\frac{1}{2}R_1}\\ \\ \rowop{R_3}{2R_3}}{%
          \begin{bmatrix}[rrr|rrr]1&\frac{1}{2}&0&\frac{1}{2}&0&0\\0&1&-3&2&1&0\\0&0&1&-1&1&2\end{bmatrix}}
      &\end{flalign*}
      \[\Downarrow\]
      \begin{flalign*}&\rowopmatrix[15.7em]{ \\ \rowop{R_2}{R_2+3R_3}\\ }{%
          \begin{bmatrix}[rrr|rrr]1&\frac{1}{2}&0&\frac{1}{2}&0&0\\0&1&0&-1&4&6\\0&0&1&-1&1&2\end{bmatrix}}
      &\end{flalign*}
      \[\Downarrow\]
      \begin{flalign*}&\rowopmatrix[15.7em]{ \rowop{R_1}{R_1-\frac{1}{2}R_2}\\ \\ }{%
          \begin{bmatrix}[rrr|rrr]1&0&0&1&-2&-3\\0&1&0&-1&4&6\\0&0&1&-1&1&2\end{bmatrix}}=[I|A^{-1}]
      &\end{flalign*}
  Therefore $A$ is invertible with 
  \[A^{-1} = \begin{bmatrix*}[r]1&-2&-3\\-1&4&6\\-1&1&2\end{bmatrix*}\,.\]
\end{example}

\begin{example}
Find the inverse of $A =\begin{bmatrix*}[r]1&0&-3\\0&1&2\\1&2&1\end{bmatrix*}$\,.

\textbook{\newpage}
Solution:\\
Reducing $[A|I]$ gives
\begin{align*}[A|I] = \begin{bmatrix}[rrr|rrr] 1&0&-3&1&0&0\\0&1&2&0&1&0\\1&2&1&0&0&1\end{bmatrix}&\Rightarrow
  \rowopmatrix[7em]{\\ \\ \rowop{R_3}{R_3-R_1}}{\begin{bmatrix}[rrr|rrr] 1&0&-3&1&0&0\\0&1&2&0&1&0\\0&2&4&-1&0&1\end{bmatrix}}\\
&\Rightarrow
  \rowopmatrix[7em]{\\ \\ \rowop{R_3}{R_3-2R_2}}{%
    \begin{bmatrix}[rrr|rrr] 1&0&-3&1&0&0\\0&1&2&0&1&0\\0&0&0&-1&-2&1\end{bmatrix}}
\end{align*}

Here the bottom row coefficients are all zero so no identity occurs and therefore $A$ is noninvertible.
\end{example}

\subsection{Solving Linear Systems Using Matrix Inversion}

If $A$ is a $n\times n$ invertible matrix (ie. $A^{-1}$ exists), then the linear system
\[A\lvec{x}=\lvec{b}\]
can be solved using $A^{-1}$ as follows.  Left-multiplying both sides by $A^{-1}$ gives
\begin{align*}
A^{-1}A\lvec{x} &= A^{-1}\lvec{b}\\
I\lvec{x}&= A^{-1}\lvec{b}\\
\lvec{x}&=A^{-1}\lvec{b}
\end{align*}
Thus \boxed{\lvec{x}=A^{-1}\lvec{b}}\,. This process is known as \textbf{method of inverses}.  Note that this method cannot be used to solve a linear system $A\lvec{x}=\lvec{b}$ if $A$ is not square or if $A$ is noninvertible.

\begin{example}
  Solve the linear system by the method of inverses:
  \begin{align*} 2x+y&=-1\\
   -4x-y-3z&=2\\
   3x+y+2z&=1
   \end{align*}

Solution:
\[ A=
\begin{bmatrix*}[r]
    2&1&0\\-4&-1&-3\\3&1&2
\end{bmatrix*},\, \lvec{x}= \begin{bmatrix}x\\y\\z\end{bmatrix},\, \lvec{b}= \begin{bmatrix*}[r]-1\\2\\1\end{bmatrix*}\]
  In Example~\ref{example:matrixinverse} we found
  \[A^{-1} = \begin{bmatrix*}[r]
    1&-2&-3\\-1&4&6\\-1&1&2
  \end{bmatrix*}\]
  
  Therefore, using the method of inverses:
  \[\lvec{x} = A^{-1}\lvec{b}=\begin{bmatrix*}[r]
  1&-2&-3\\-1&4&6\\-1&1&2\end{bmatrix*} \begin{bmatrix*}[r]
       -1\\2\\1
     \end{bmatrix*} = \begin{bmatrix}
       -1-4-3\\1+8+6\\1+2+2
     \end{bmatrix} =\begin{bmatrix*}[r]
       -8\\15\\5
     \end{bmatrix*}\]
     So $x=-8$, $y=15$, and $z=5$\,.
\end{example}

We now state some conditions relating the invertibility of a square matrix $A$, to other matrix and linear system properties we have studied thus far.
\theorem{\label{thm:invertibleequivalents}If $A$ is an $n\times n$ matrix, the follow statements are equivalent:
\begin{enumerate}
  \item $A$ is invertible.
  \item $A\lvec{x}=\lvec{b}$ has a unique solution.
  \item $A\lvec{x}=\lvec{0}$ has the unique trivial solution $\lvec{x}=\lvec{0}$\,.
  \item $\rank{A}=n$\,.
  \item The reduced row echelon form of $A$ is $I$, the identity matrix.
\end{enumerate}}

Using our ability to find inverses as well as the basic properties of matrices (Theorem~\ref{thm:matrixproperties}) allows further methods for solving matrix equations.  Note that the properties $(A^T)^T=A$ for transposes (Theorem~\ref{thm:transposeproperties}) and the similar property $(A^{-1})^{-1}=A$ for inverses (Theorem~\ref{thm:inverseofinverse}) can be useful for isolating a matrix variable.

\begin{example}
Solve the following matrix equation for the matrix $A$\,.
\[(5A^T)^{-1}=\begin{bmatrix}2 & 8 \\ 1 & 5\end{bmatrix}\]
Solution:\\
Inverting both sides of the equation gives
\[\left((5A^T)^{-1}\right)^{-1}=\begin{bmatrix}2 & 8 \\ 1 & 5\end{bmatrix}^{-1}\,.\]
But $(B^{-1})^{-1}=B$ so the left-hand side simplifies to
\[5A^T=\begin{bmatrix}2 & 8 \\ 1 & 5\end{bmatrix}^{-1}\,.\]
Using Theorem~\ref{thm:twodinverse} the right-hand side may be directly evaluated.
\[5A^T=\frac{1}{(2)(5)-(8)(1)}\begin{bmatrix*}[r]5 & -8 \\ -1 & 2\end{bmatrix*}=\frac{1}{2}\begin{bmatrix*}[r]5 & -8 \\ -1 & 2\end{bmatrix*}\]
  Multiply both sides by $1/5$ to get
\[A^T=\frac{1}{10}\begin{bmatrix*}[r]5 & -8 \\ -1 & 2\end{bmatrix*}\,.\]
  Taking the transpose of both sides gives
  \[(A^T)^T=\left(\frac{1}{10}\begin{bmatrix*}[r]5 & -8 \\ -1 & 2\end{bmatrix*}\right)^T\]
    Using Theorem~\ref{thm:transposeproperties} the left-hand side simplifies to $A$ and one can pull the constant $1/10$ out of the transpose on the right-hand side to get
    \[A=\frac{1}{10}\begin{bmatrix*}[r]5 & -8 \\ -1 & 2\end{bmatrix*}^T\,.\]
      Evaluating the transpose gives
      \[A=\frac{1}{10}\begin{bmatrix*}[r]5 & -1 \\ -8 & 2\end{bmatrix*}\,,\]
      and one can, if desired, bring the scalar constant into the matrix:
       \[A=\begin{bmatrix*}[r]\frac{5}{10} & -\frac{1}{10} \\[.2em] -\frac{8}{10} & \frac{2}{10}\end{bmatrix*}=\begin{bmatrix*}[r]\frac{1}{2} & -\frac{1}{10} \\[.2em] -\frac{4}{5} & \frac{1}{5}\end{bmatrix*}\,.\]
       This solution can be checked in the original matrix equation.
\end{example}

\subsection*{An Application to Geometry}
As an interesting application of solving linear systems consider the following problem.  A common tool in computer drawing programs (such as the free software program \emph{xfig}) is a tool for drawing circular arcs.  The user enters three points and the program will then find a circular arc through those points.  Let us explore how this is calculated.  The equation for a circle of radius $2$ centred at the origin $(0,0)$ of a Cartesian Coordinate system is, using the Pythagorean Theorem,
\[x^2+y^2=2^2\,.\]
If the centre of the circle is at the point $(3,4)$ instead of the origin one would have the equation
\[(x-3)^2+(y-4)^2=2^2\,.\]
In general, a circle with radius $r$ centred at the point $(h,k)$ has the equation
\[(x-h)^2+(y-k)^2=r^2\,.\]
If this equation is expanded one gets
\[x^2-2xh+h^2+y^2-2yk+k^2=r^2\,.\]
If one rearranges this one has
\[x^2+y^2+(-2h)x+(-2k)y+(h^2+k^2-r^2)=0\]
By introducing three new constants, $a=-2h$, $b=-2k$ and $c=h^2+k^2-r^2$ one can replace $h$, $k$, and $r$ to get a new circle equation:
\[x^2+y^2+ax+by+c=0\,.\]
If we can therefore figure out $a$, $b$, and $c$ for this equation we could solve to get $h$, $k$, and $r$ and thereby find our circle.

Suppose we know a point $(x,y)=(-1,-3)$ sits on the desired circle.  For this to be true it must satisfy the circle equation and we have
\[(-1)^2+(-3)^2+a(-1)+b(-3)+c=0\,,\]
which can be rewritten
\[-a-3b+c=-10\,.\]
Now despite the equation of the circle being quadratic in the variables $x$ and $y$, this equation in terms of the unknown constants $a$, $b$, and $c$, is linear!  Having knowledge of two more points on the circle produces two more equations involving the unknown constants, thereby creating a determined linear system which we can solve.

\begin{example}
  Find the circle that goes through the three points $(-1,-3)$, $(5,5)$, and $(-2,4)$\,.

  Solution:\\
  Inserting the the $(x,y)$ values of each point into the equation
  \[x^2+y^2+ax+by+c=0\]
  produces the following determined linear system in constants $a$, $b$, and $c$\,:
  \begin{align*}
    (-1,-3)&: (-1)^2+(-3)^2+a(-1)+b(-3)+c=0 &\implies& &-a-3b+c&=-10\\
    (5,5)&: (5)^2+(5)^2+a(5)+b(5)+c=0 &\implies& &5a+5b+c&=-50\\
    (-2,4)&: (-2)^2+(4)^2+a(-2)+b(4)+c=0 &\implies& &-2a+4b+c&=-20
  \end{align*}
The system can be represented by $A\lvec{x}=\lvec{b}$ with matrices defined by
\[A=\begin{bmatrix*}[r]-1&-3&1 \\ 5 & 5 & 1 \\ -2 & 4 & 1 \end{bmatrix*}~~~~~\lvec{x}=\begin{bmatrix*}[c] a \\ b \\ c\end{bmatrix*}~~~~~\lvec{b}=\begin{bmatrix*}-10 \\ -50 \\ -20\end{bmatrix*}\,.\]
The quickest way to find $\lvec{x}$ is to reduce $[A|\lvec{b}]$ and back-substitute.  A longer method is to solve for the inverse $A^{-1}$ by reducing $[A|I]$ to $[I|A^{-1}]$ to get (show this!)
\[A^{-1}=\begin{bmatrix*}[r] \frac{1}{50} & \frac{7}{50} & -\frac{4}{25} \\[.3em]
-\frac{7}{50} & \frac{1}{50} & \frac{3}{25} \\[.3em]
 \frac{3}{5} & \frac{1}{5} & \frac{1}{5} \end{bmatrix*},
\]
and then use the method of inverses to find
\[\lvec{x}=\begin{bmatrix*}[c] a \\ b \\ c\end{bmatrix*}=A^{-1}\lvec{b}=\begin{bmatrix*}[r] \frac{1}{50} & \frac{7}{50} & -\frac{4}{25} \\[.3em]
-\frac{7}{50} & \frac{1}{50} & \frac{3}{25} \\[.3em]
\frac{3}{5} & \frac{1}{5} & \frac{1}{5} \end{bmatrix*}\begin{bmatrix*}-10 \\ -50 \\ -20\end{bmatrix*}
  =\begin{bmatrix*}[r]-\frac{1}{5}-7+\frac{80}{25} \\[.3em] \frac{7}{5}-1-\frac{60}{25} \\[.3em] -6-10-4\end{bmatrix*}=\begin{bmatrix*}[r]-4\\ -2 \\ -20\end{bmatrix*}\,.\]
  So $a=-4$, $b=-2$, and $c=-20$.  Next solve for constants $h$, $k$, and $r$ using the formulas from our previous discussion:
  \begin{itemize}
  \item $a=-4=-2h \implies \boxed{h=2}$
  \item $b=-2=-2k \implies \boxed{k=1}$
  \item $c=-20=h^2+k^2-r^2 \implies -20=(2)^2+(1)^2-r^2 \implies r^2=25 \implies \boxed{r=5}$
  \end{itemize}
  So the desired circle has centre $(h,k)=(2,1)$ and radius $r=5$.  Inserting these constants into $(x-h)^2+(y-k)^2=r^2$ gives the equation for the circle
  \[(x-2)^2+(y-1)^2=25\,.\]
  A plot verifies the circle is correct
  \begin{center}
   \newsavebox\circlebox
   \begin{lrbox}{\circlebox}
     \begin{asy}
       import graph;
       size(200,200);
       xaxis("$x$",xmax=8,Arrow(HookHead,size=4),above=true);
       yaxis("$y$",ymax=8,Arrow(HookHead,size=4),above=true);
       real f(real x) {return sqrt(25-(x-2)^2)+1;}
       pair F(real x) {return (x,f(x));}
       real g(real x) {return -sqrt(25-(x-2)^2)+1;}
       pair G(real x) {return (x,g(x));}
       draw(graph(f,-3,7,operator ..),red+2);
       draw(graph(g,-3,7,operator ..),red+2);
       xtick("$2$",2);
       ytick("$1$",1);
       dot((2,1),black+5);
       label("$(2,1)$",(2,1),NE);
       dot(F(-2),black+5);
       dot(F(5),black+5);
       dot(G(-1),black+5);
       label("$(-2,4)$",F(-2),NW);
       label("$(5,5)$",F(5),NE);
       label("$(-1,-3)$",G(-1),SW);
     \end{asy}
   \end{lrbox}
   \resizebox{2.5in}{!}{\usebox\circlebox}
   \end{center}
\end{example}

If three distinct points are collinear, like $(-1,0)$, $(0,0)$, and $(0,1)$, the linear system generated will be inconsistent. (Show this!)

\section{Elementary Matrices}

\definition{A square matrix is called an \textbf{elementary matrix} if it can be obtained from the identity matrix of the same dimension by performing a single elementary row operation.}

Since only a single row operation is allowed, this means an elementary matrix arises in one of three ways (and can be classified by this):
  \begin{enumerate}
  \item Multiplication of a row by a nonzero scalar.
  \item Addition of a multiple of one row to a different row.
  \item Interchanging of two rows.
  \end{enumerate}
  
\begin{example}
  Determine the elementary matrices for each of the following row operations for the square matrix of given size.
  
  \begin{enumerate}
    
  \item $\rowop{R_1}{2R_1},~~ 2\times 2$

    Solution:\\
    \[I = \begin{bmatrix}
      1&0\\0&1
    \end{bmatrix},~~ E = \begin{bmatrix}
      2&0\\0&1
    \end{bmatrix}\]

  \item $\rowop{R_2}{R_2 - 3R_1},~~ 4\times 4$

    Solution:\\
    \[I = \begin{bmatrix}
      1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1
    \end{bmatrix},~~ E = \begin{bmatrix*}[r]
      1&0&0&0\\-3&1&0&0\\0&0&1&0\\0&0&0&1
    \end{bmatrix*}\]

  \item $\rowswap{R_1}{R_3},~~ 3\times3$

    Solution:\\
    \[I = \begin{bmatrix}
      1&0&0\\0&1&0\\0&0&1
    \end{bmatrix},~~ E = \begin{bmatrix}
      0&0&1\\0&1&0\\1&0&0
    \end{bmatrix}\]

  \end{enumerate}
\end{example}


\begin{example}
Determine whether the given matrices are elementary matrices.  If they are write down the corresponding row operation.

\begin{enumerate}
  \item $E_1 = \begin{bmatrix*}[r]
    1&0&0\\0&1&0\\0&-2&1
  \end{bmatrix*}$

    Solution: Elementary, $\rowop{R_3}{R_3 - 2R_2}$

\textbook{\newpage}
  \item $E_2 = \begin{bmatrix}
    1&0&3\\0&1&0\\0&0&1
  \end{bmatrix}$
    
    Solution: Elementary, $\rowop{R_1}{R_1 + 3R_3}$


  \item $E_3 = \begin{bmatrix}
  1&0&0\\0&1&0\\0&0&1
  \end{bmatrix}$

    Solution: Elementary, $\rowop{R_1}{(1)R_1}$
    
  \item $E_4 = \begin{bmatrix*}[r]
    \,1&\,0&\,1&0\\0&1&0&0\\0&0&1&-2\\0&0&0&1
  \end{bmatrix*}$

    Solution: Not an elementary matrix
\end{enumerate}

\end{example}


\subsubsection{Elementary Matrix Notation and Inverse}
We can write a particular elementary matrix with the following notation for given $n\times n$ dimension.
\begin{enumerate}
\item $E_{ii}(c)$ is obtained from $I$ by multiplying $c\neq0$ times row $i$\,.
\item $E_{ij}(c), i\neq j$ is obtained from $I$ by adding $c$ times row $j$ to row $i$\,.
\item $P_{ij}$ is obtained from $I$ by interchanging rows $i$ and $j$\,.
\end{enumerate}

Consideration of how to undo the row operation underlying a given elementary matrix results in the following theorem.
\theorem{\label{thm:elementaryinverse}Every elementary matrix is invertible where the inverse is an elementary matrix given by:
\begin{align*}
(E_{ii}(c))^{-1} &= E_{ii}\left(\frac{1}{c}\right)\\
(E_{ij}(c))^{-1} &= E_{ij}(-c)~~~~~~(i\neq j)\\
(P_{ij})^{-1} &= P_{ij}~.
\end{align*}}

\begin{example}
  Find the inverse of the given elementary matrix.
  \begin{enumerate}
    \item $E = \begin{bmatrix}
      1&0\\2&1
    \end{bmatrix}$ 

      Solution:\\
      $E$ arises from $\rowop{R_2}{R_2 + 2R_1}$ therefore $E=E_{21}(2)$\,.\\[.5em]
      Thus $E^{-1} = E_{21}(-2)$ and $E^{-1} = \begin{bmatrix*}[r]
      1&0\\-2&1
      \end{bmatrix*}$\,.

    \item $E= \begin{bmatrix}
      1&0&0\\0&0&1\\0&1&0
    \end{bmatrix}$

      Solution:\\
    $E$ arises from $\rowswap{R_2}{R_3}$ therefore $E=P_{23}$\,.\\[.5em]
    Thus $E^{-1} = P_{23}$ and $E^{-1} = \begin{bmatrix}
      1&0&0\\0&0&1\\0&1&0
    \end{bmatrix}$\,.


  \item $E = \begin{bmatrix*}[r]
    1&0\\0&-2
  \end{bmatrix*}$

    Solution:\\
    $E$ arises from $\rowop{R_2}{(-2)R_2}$ therefore $E=E_{22}(-2)$\,.\\[.5em]
    Thus $E^{-1}= E_{22}\left(-\frac{1}{2}\right) = \begin{bmatrix*}[r]
      1&0\\0& -\frac{1}{2}
    \end{bmatrix*}$\,.
  \end{enumerate}
\end{example}

\subsection*{Row Operations by Matrix Multiplication}
The following theorem demonstrates the utility of elementary matrices.  They allow us to represent row operations using matrix multiplication.
\theorem{If the elementary matrix $E$ results from performing a certain elementary row operation on $I_m$ (the $m\times m$ identity matrix) and if $A$ is an $m\times n$ matrix, then the product $EA$ is the matrix that results when the same row operation is performed on~$A$\,.}

\begin{example} Given the elementary matrix $E$ and $A$, identify the row operation corresponding to $E$ and find the product $EA$ directly to verify the row operation is indeed performed on $A$\,.

  \begin{enumerate}
    \item  $E = \begin{bmatrix}
      1&0&0\\0&1&0\\3&0&1
    \end{bmatrix}~~ A= \begin{bmatrix*}[r]
       1&0&2&3\\2&-1&3&6\\1&4&4&0
    \end{bmatrix*}$

      Solution:\\
      $E$ corresponds to $\rowop{R_3}{R_3 + 3R_1}$\\[.2em]
      $EA =\begin{bmatrix}
      1&0&0\\0&1&0\\3&0&1
    \end{bmatrix}\begin{bmatrix*}[r]
       1&0&2&3\\2&-1&3&6\\1&4&4&0
    \end{bmatrix*}= \begin{bmatrix*}[r]
        1&0&2&3\\2&-1&3&6\\4&4&10&9
      \end{bmatrix*}$ which is $\rowop{R_3}{R_3+3R_1}$ acting on $A$\,.

    \item $E = \begin{bmatrix}
      1&0&0&0\\0&1&0&0\\0&0&2&0\\0&0&0&1
    \end{bmatrix}~~  A = \begin{bmatrix*}[r]
      1&0&1&5&0\\1&2&0&1&0\\-1&-3&-1&3&1\\2&1&1&-2&0
    \end{bmatrix*}$

      Solution:\\
      $E$ corresponds to $\rowop{R_3}{2R_3}$\\[.2em]
      $EA = \begin{bmatrix}
      1&0&0&0\\0&1&0&0\\0&0&2&0\\0&0&0&1
    \end{bmatrix}\begin{bmatrix*}[r]
      1&0&1&5&0\\1&2&0&1&0\\-1&-3&-1&3&1\\2&1&1&-2&0
    \end{bmatrix*}=\begin{bmatrix*}[r]
      1&0&1&5&0\\1&2&0&1&0\\-2&-6&-2&6&2\\2&1&1&-2&0
      \end{bmatrix*}$\\
      which is $\rowop{R_3}{2R_3}$ acting on $A$\,.

    \item $E = \begin{bmatrix}
      1&0&0\\0&0&1\\0&1&0
    \end{bmatrix}~~  A = \begin{bmatrix*}[r]
      2&-1&3\\-1&0&2\\1&1&5
    \end{bmatrix*}$

      Solution:\\
      $E$ corresponds to $\rowswap{R_2}{R_3}$\\[.2em]
      $EA =  \begin{bmatrix}
      1&0&0\\0&0&1\\0&1&0
    \end{bmatrix}\begin{bmatrix*}[r]
      2&-1&3\\-1&0&2\\1&1&5
    \end{bmatrix*}=\begin{bmatrix*}[r]
        2&-1&3\\1&1&5\\-1&0&2
      \end{bmatrix*}$ which is $\rowswap{R_2}{R_3}$ acting on $A$\,.
  \end{enumerate}
\end{example}

\begin{example}
  For each pair of matrices, find an elementary matrix such that $B = EA$\,.

  \begin{enumerate}
    \item $A = \begin{bmatrix*}[r]
      1&-1\\2&1
    \end{bmatrix*}~~  B= \begin{bmatrix*}[r]
      1&-1 \\ 4&2
    \end{bmatrix*}$

      Solution:\\
      Since $B$ arises from $A$ by the row operation $\rowop{R_2}{2R_2}$\,,\\[.5em]
      $E = \begin{bmatrix}
        1&0\\0&2
      \end{bmatrix}$

      Direct multiplication confirms $EA=B$.

    \item $A = \begin{bmatrix*}[r]
      1&1&-1\\2&1&2\\-1&1&0
    \end{bmatrix*}~~  B= \begin{bmatrix*}[r]
      1&1&-1\\2&1&2\\1&2&2
    \end{bmatrix*}$

      Solution:\\
      Since $B$ arises from $A$ by the row operation $\rowop{R_3}{R_3 + R_2}$\,,\\[.5em]
      $E = \begin{bmatrix}
      1&0&0\\0&1&0\\0&1&1
      \end{bmatrix}$

      Direct multiplication confirms $EA=B$.
  \end{enumerate}
\end{example}

\subsection*{Elementary Matrix Decomposition}
\theorem{\label{thm:elementarydecompositionofinverse} A matrix $A$ is invertible if and only if it can be written as a product of elementary matrices of the same dimension as $A$\,.}

To find the matrix product, recall the reduced row echelon form of $A$ is $I$.  Thus one can reduce $A$ to $I$ keeping track of the $k$ row operations required.  One then has
\[E_kE_{k-1}\cdots E_1 A=I\,.\]
for some $k$ elementary matrices $E_i$\,.  Then, considering $B=E_kE_{k-1}\cdots E_1$ one can multiply both sides by $B^{-1}$ to get:
\[A=(E_kE_{k-1}\cdots E_1)^{-1}I=(E_kE_{k-1}\cdots E_1)^{-1}=(E_1)^{-1}\cdots (E_{k-1})^{-1}(E_k)^{-1}\,.\]
Since each inverted elementary matrix is itself an elementary matrix one has the required product.  

\begin{example}
  If possible, write $A = \begin{bmatrix*}[r]
    1&-1&0\\1&-1&1\\0&1&1
  \end{bmatrix*}$ as a product of elementary matrices.\\

  Solution:\\[.5em]
  \hspace*{6.2em}$A = \begin{bmatrix*}[r]
    1&-1&0\\1&-1&1\\0&1&1
  \end{bmatrix*}$

  \hspace{11em}$\Downarrow$
  
  $\rowopmatrix[8em]{ \\ \rowop{R_2}{R_2 - R_1} \\ }{\begin{bmatrix*}[r]
    1&-1&0\\0&0&1\\0&1&1
    \end{bmatrix*}=E_{21}(-1)A}$\\
  
  \hspace{11em}$\Downarrow$
  
  $\rowopmatrix[8em]{ \\ \rowswap{R_2}{R_3} \\ }{\begin{bmatrix*}[r]
    1&-1&0\\0&1&1\\0&0&1
  \end{bmatrix*}=P_{23}E_{21}(-1)A}$\\

  \hspace{11em}$\Downarrow$
  
  $\rowopmatrix[8em]{ \\ \rowop{R_2}{R_2 - R_3} \\ }{\begin{bmatrix*}[r]
    1&-1&0\\0&1&0\\0&0&1
  \end{bmatrix*}=E_{23}(-1)P_{23}E_{21}(-1)A}$\\

  \hspace{11em}$\Downarrow$
  
  $\rowopmatrix[8em]{\rowop{R_1}{R_1 + R_2} \\ \\ }{\begin{bmatrix}
    1&0&0\\0&1&0\\0&0&1
  \end{bmatrix}=I=E_{12}(1)E_{23}(-1)P_{23}E_{21}(-1)A}$
  
  Having reduced $A$ to RREF, the matrix is invertible and the process of reduction can be written as follows:
  \[E_{12}(1)E_{23}(-1)P_{23}E_{21}(-1)A = I\]
  Remember that order is important here with the first row operation needing to act on $A$ first. Then we have
  \begin{align*}
    A &=\left(E_{12}(1)E_{23}(-1)P_{23}E_{21}(-1)\right)^{-1}I\\
    &= (E_{21}(-1))^{-1}(P_{23})^{-1}(E_{23}(-1))^{-1}(E_{12}(1))^{-1}\\
    &= E_{21}(1)P_{23}E_{23}(1)E_{12}(-1)\,.
  \end{align*}
\end{example}

\textbook{\newpage}
\begin{example}
  \label{example:elementarydecomposition}
  If possible, write $A = \begin{bmatrix*}[r]
    0&1&-2\\1&0&4\\0&0&3
  \end{bmatrix*}$ as a product of elementary matrices.

Solution:\\[.5em]
\hspace*{6.2em}$A = \begin{bmatrix*}[r]
    0&1&-2\\1&0&4\\0&0&3
\end{bmatrix*}$

  \hspace{11em}$\Downarrow$
  
$\rowopmatrix[8em]{ \rowswap{R_1}{R_2} \\ \\ \rowop{R_3}{\frac{1}{3}R_3}}{\begin{bmatrix*}[r]
    1 & 0& 4\\ 0&1&-2\\0&0&1
\end{bmatrix*}=P_{12}E_{33}\!\left(\frac{1}{3}\right)A}$

  \hspace{11em}$\Downarrow$
  
$\rowopmatrix[8em]{\rowop{R_1}{R_1 - 4R_3} \\ \rowop{R_2}{R_2 + 2R_3} \\ }{\begin{bmatrix}
    1&0&0\\0&1&0\\0&0&1
\end{bmatrix}=I=E_{13}(-4)E_{23}(2)P_{12}E_{33}\!\left(\frac{1}{3}\right)A}$

Then $A$ is invertible and one has
\[E_{13}(-4)E_{23}(2)E_{33}\!(1/3)P_{12}A = I\,.\]
Therefore:
\begin{align*}A & = (E_{13}(-4)E_{23}(2)E_{33}\!(1/3)P_{12})^{-1}I \\
  &= (P_{12})^{-1}(E_{33}\!(1/3))^{-1}(E_{23}(2))^{-1}(E_{13}(-4))^{-1}\\
  & = P_{12}E_{33}(3)E_{23}(-2)E_{13}(4)\,.
\end{align*}

Note that while the order of the matrices in general matters, the order of
\[P_{12}=\begin{bmatrix*}[r] 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix*}\ \ \text{and}\ \  E_{33}(1/3)=\begin{bmatrix*}[c] 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1/3 \end{bmatrix*}\]
could have been swapped as both were introduced at the same initial step.  That this is acceptable is because one can verify $P_{12}E_{33}(1/3)=E_{33}(1/3)P_{12}$, i.e. the two matrices commute.  Similarly $E_{13}(-4)$ and $E_{23}(2)$ could have been introduced in a swapped order at the second step.

\end{example}

\begin{example}
  If possible, write $A = \begin{bmatrix*}[r]
    1&-1&1\\-2&2&1\\0&0&1
  \end{bmatrix*}$ as a product of elementary matrices.

\textbook{\newpage}
  Solution:\\[.5em]
\hspace*{6.2em}$A=\begin{bmatrix*}[r]
   1&-1&1\\-2&2&1\\0&0&1
\end{bmatrix*}$

  \hspace{11em}$\Downarrow$
  
$\rowopmatrix[8em]{\\ \rowop{R_2}{R_2+2R_1} \\ }{\begin{bmatrix}
  1&-1&1\\0&0&3\\0&0&1
\end{bmatrix}=E_{21}(2)A}$

  \hspace{11em}$\Downarrow$
  
$\rowopmatrix[8em]{ \\ \rowswap{R_2}{R_3} \\ }{\begin{bmatrix}
  1&-1&1\\0&0&1\\0&0&3
\end{bmatrix}=P_{23}E_{21}(2)A}$

  \hspace{11em}$\Downarrow$
  
$\rowopmatrix[8em]{ \\ \\ \rowop{R_3}{R_3-3R_2}}{\begin{bmatrix}
  1&-1&1\\0&0&1\\0&0&0
\end{bmatrix}=E_{32}(-3)P_{23}E_{21}(2)A}$

The matrix $A$ cannot be reduced to the identity matrix, therefore $A$ is noninvertible and $A$ cannot be written as a product of elementary matrices.
\end{example}

We found, for an invertible matrix $A$, that we could reduce it by elementary row matrices to identity matrix $I$ by
\[\underbrace{E_kE_{k-1}\cdots E_1}_{=B} A=I\,.\]
Since $BA=I$ it follows that $B=A^{-1}$ and the elementary matrix expansion of $A^{-1}$, if desired, is therefore
\[A^{-1}=E_kE_{k-1}\cdots E_1\,.\]
In practice this mechanism is a complicated way to find the inverse due to the multiplication required.  As was already seen, augmenting $A$ to $[A|I]$ and reducing to $[I|A^{-1}]$ is an algorithmically superior solution.

Consider the more general problem of reducing an arbitrary $m\times n$ matrix $A$ to its reduced row echelon form.  Since this can be done by elementary row operations which can be represented by multiplication by elementary matrices we have
\[E_kE_{k-1}\cdots E_1 A=R\]
where $R$ is the RREF of matrix $A$ and the $E_i$ are $m\times m$ elementary matrices.  Defining $B=E_kE_{k-1}\cdots E_1$ we see that for any matrix $A$ we can find an invertible matrix $B$, written as a product of elementary matrices such that
\[BA=R\,.\]
In other words, we can reduce any matrix $A$ to its $RREF$ by matrix multiplication.  Now since $B$ is a product of elementary matrices which in turn are found by reducing $A$ to $R$ we could find $B$ by matrix multiplication.  However our experience with inverting matrices suggests that a more efficient mechanism to find $B$ is to augment the $m\times n$ matrix $A$ by the identity matrix $I_m$ and reduce as follows
\[[A|I]\Rightarrow[R|B]\,.\]
The desired product $B=E_kE_{k-1}\cdots E_1$ will then be found quickly.  The following example illustrates the procedure.
\begin{example}
  Given the matrix
  \[A=\begin{bmatrix*}[r]1 & 2 & 0 \\ 3 & 5 & -2\end{bmatrix*}\]
  find an invertible matrix $B$ such that $BA=R$, where $R$ is the reduced row echelon form of $A$, and express $B$ as a product of elementary matrices.

  Solution:\\
  Augment $A$ by $I_2$, the $2\times2$ identity matrix, and reduce to RREF keeping track of the row operations.
  
  \hspace*{4.9em}$[A|I]=\begin{bmatrix}[rrr|rr]1 & 2 & 0 & 1 & 0\\ 3 & 5 & -2 & 0 & 1\end{bmatrix}$

  \hspace{10em}$\Downarrow$
  
  $\rowopmatrix[8em]{ \\ \rowop{R_2}{R_2-3R_1}}{\begin{bmatrix}[rrr|rr]1 & 2 & 0 & 1 & 0\\ 0 & -1 & -2 & -3 & 1\end{bmatrix}=[E_1A|E_1]}$

  \hspace{10em}$\Downarrow$

  $\rowopmatrix[8em]{ \\ \rowop{R_2}{-R_2}}{\begin{bmatrix}[rrr|rr]1 & 2 & 0 & 1 & 0\\ 0 & 1 & 2 & 3 & -1\end{bmatrix}}=[E_2E_1A|E_2E_1]$

  \hspace{10em}$\Downarrow$

  $\rowopmatrix[8em]{ \rowop{R_1}{R_1-2R_2} \\ }{\begin{bmatrix}[rrr|rr]1 & 0 & -4 & -5 & 2\\ 0 & 1 & 2 & 3 & -1\end{bmatrix}}=[E_3E_2E_1A|E_3E_2E_1]=[R|B]$

  Thus the RREF of $A$ is
  \[R=\begin{bmatrix*}[r] 1 & 0 & -4 \\ 0 & 1 & 2 \end{bmatrix*}\,,\]
  and the matrix $B$ which reduces $A$, so that $BA=R$\,, is given by
  \[B=\begin{bmatrix*}[r] -5 & 2 \\ 3 & -1 \end{bmatrix*}\,.\]

  As a product of elementary matrices we have $B=E_3E_2E_1$, where, looking back at our row operations we have, calculating the elementary matrices by operating on the identity matrix,

  $\begin{bmatrix*}[r] 1 & 0 \\ 0 & 1 \end{bmatrix*} \Rightarrow
  \rowopmatrix{ \\  \rowop{R_2}{R_2-3R_1}}{\begin{bmatrix*}[r]
      1 & 0 \\ -3 & 1\end{bmatrix*}}=E_1=E_{21}(-3)$
  
  $\begin{bmatrix*}[r] 1 & 0 \\ 0 & 1 \end{bmatrix*} \Rightarrow
   \rowopmatrix{ \\ \rowop{R_2}{-R_2}}{\begin{bmatrix*}[r]
      1 & 0 \\ 0 & -1\end{bmatrix*}}=E_2=E_{22}(-1)$
  
  $\begin{bmatrix*}[r] 1 & 0 \\ 0 & 1 \end{bmatrix*} \Rightarrow
   \rowopmatrix{ \rowop{R_1}{R_1-2R_2} \\ }{\begin{bmatrix*}[r]
      1 & -2 \\ 0 & 1\end{bmatrix*}}=E_3=E_{12}(-2)$

   Thus as a product of elementary matrices we have 
   \[B=\begin{bmatrix*}[r] -5 & 2 \\ 3 & -1 \end{bmatrix*}=E_3E_2E_1=E_{12}(-2)E_{22}(-1)E_{21}(-3)=\begin{bmatrix*}[r]
   1 & -2 \\ 0 & 1\end{bmatrix*}
   \begin{bmatrix*}[r]
     1 & 0 \\ 0 & -1\end{bmatrix*}\begin{bmatrix*}[r]
       1 & 0 \\ -3 & 1\end{bmatrix*}\,.\]
        
        One can confirm by direct matrix multiplication that $BA=R$ and that $B=E_3E_2E_1$ for these matrices.
\end{example}

%TODO
% Note some texts call the reduction to REF ``Gaussian Elimination'' while
% others call this an ``algorithm'' and refer to Gaussian elimination as
% the ultimate solving of a linear system with back-substitution or indeed
% as the same as Gauss-Jordan elimination.  
% It may be good to clarify this.
% Others don't require REF to have a leading 1.
% Our terminology follows Howard Anton's Elementary Linear Algebra 5e.
% If we define REF to be without leading 1's as seems to be done.
% then we could save leading 1's for Gauss-Jordan step.  Note that
% Burden and Faires doesn't seem to require making leading 1's.  We should
% look at other Numerical algorithm books to see what most actually do.
% For REF to include a leading 1, however you really want Gaussian
% elimination to be defined to produce it, or indeed produce whichever
% definition of REF you use.
%
% We also need to be clear whether by Gaussian Elimination and Gauss-Jordan
% elimination we mean the process by which we modify the augmented matrix
% to REF or RREF respectively, or whether we mean the process by which we
% solve the linear system, since the latter has a few more steps.
%
% When writing row ops I've been writing R2->R2+2R1, etc., while others
% like Burden and Faires will write the opposite R2+2R1->R2.  Look more closely
% at is what is more standard/intuitive for writing these.  Currently
% all row ops are in a command and can be left as such.
%
% Consider using  dots or dashes, not bar in augmented matrix.
%
% Use case only for inline linear system, not elsewhere.  Be consistent at
% minimum.
%
% Put reference when decomposing A into columns back to Ax column matrix
% written out.
%
% Add discussion about only square matrices being invertible.
% Could add proof that if a right inverse exists it must be the left
% inverse but it must be the case that there are some left inverses
% which have no right inverse.
%
% Maybe show that general 2x2 matrix inverse really does multiply out
% to identity.  Or show row operations to get it as I do on looseleaf.
% The latter is a bit tricky because you could have a=0 etc. and then
% you need to think about it.  Just going ahead on the assumption
% a nonzero works and checking may be the way to go. Perhaps an assignment
% question?
%
% Maybe add the 3x3 inversion example I commented out here.
%
% Decide how to write elementary row operations with either the ``goes into''
% or ``becomes'' notation.  Note wikipedia seems to use the goes into version
% at least under elementary matrices.  We are using the becomes notation.
%
% In example when writing matrices as product of elementary row operations,
% put the row ops beside like I did in early example.  Also likely make these
% examples all part of one example.
%
% Matrix multiplication should be shown with indices and summations.
% Perhaps move this into an appendix where we could also introduce summation
% notation and perhaps prove the listed properties of matrices involving
% associativity, scalar multiplication, etc.
%
% Consider notation being used for elementary matrices since E_ii and E_ij
% are inconsistent and the former really only needs one index.  The
% advantage to two indices however is that when we later use E_i it refers
% to a single matrix.  Anyway this could be re-evaluated.
%
% We don't have notation for the element of a matrix in a compound expression
% Like (AB)_{ij} for the element of the product.  We could write
% AB=[\sum_k a_{ik}b_{kj}\] but this is a bit awkward.  We need to be consistent
% with submatrix notation used, like A_{ij}, which is not the ij entry.  We
% could also use [AB]_{ij} since we use square brackets for matrices but this
% suggests the object may actually be a matrix.  In
% general one could always put parentheses or brackets when trying to refer
% to an element of the matrix and, indeed we could use this when we do
% matrix addition and subtraction if desired.  Currently I am using this
% notation when defining the adjugate.  Matthews and Walker use parentheses
% but then they use parentheses when writing their matrices.  Arfken and Webber
% and other texts avoid the notation entirely.
%
% Define unipotent and nilpotent matrices, perhaps in problem sets.  Note
% that the definitions of these may vary from text to text.
