\section{ Elementary Matrices  and Determinants  }

Given a square matrix, is there an easy way to know when it is invertible?  Answering this fundamental question is our next goal.

For small cases, we already know the answer.  If $M$ is a $1\times 1$ matrix, then $M=(m) \Rightarrow M^{-1}=(1/m)$.  Then $M$ is invertible if and only if $m\neq 0$.

For $M$ a $2\times 2$ matrix, we showed in Section 10 that if $M=\begin{pmatrix}
m^1_1 & m^1_2 \\
m^2_1 & m^2_2 \\
\end{pmatrix}$, then $M^{-1}=\frac{1}{m^1_1m^2_2-m^1_2m^2_1}\begin{pmatrix}
m^2_2 & -m^1_2 \\
-m^2_1 & m^1_1 \\
\end{pmatrix}$.  Thus $M$ is invertible if and only if $$m^1_1m^2_2-m^1_2m^2_1\neq 0\, .$$  For $2\times 2$ matrices, this quantity is called the \emph{determinant of $M$}\index{Determinant!$2\times 2$ matrix}.
\[
\det M = \det \begin{pmatrix}
m^1_1 & m^1_2 \\
m^2_1 & m^2_2 \\
\end{pmatrix} = m^1_1m^2_2-m^1_2m^2_1
\]

\begin{example}
For a $3\times 3$ matrix, $M=\begin{pmatrix}
m^1_1 & m^1_2 & m^1_3\\
m^2_1 & m^2_2 & m^2_3\\
m^3_1 & m^3_2 & m^3_3\\
\end{pmatrix}$, then (by the first review question) $M$ is non-singular if and only if\index{Determinant!$3\times 3$ matrix}:
\[
\det M= 
m^1_1m^2_2m^3_3 
- m^1_1m^2_3m^3_2 
+ m^1_2m^2_3m^3_1
- m^1_2m^2_1m^3_3  
+ m^1_3m^2_1m^3_2
- m^1_3m^2_2m^3_1
\neq 0.
\]

Notice that in the subscripts, each ordering of the numbers $1$, $2$, and $3$ occurs exactly once.  Each of these is a \emph{permutation} of the set $\{1,2,3\}$.
\end{example}



\subsection{Permutations}
Consider $n$ objects labeled $1$ through $n$ and shuffle them.  Each possible shuffle is called a \emph{permutation} $\sigma$\index{Permutation}.  
For example, here is an example of a permutation of $5$:
\[
\sigma = \begin{bmatrix}
1 & 2 & 3 & 4 & 5 \\
4 & 2 & 5 & 1 & 3 
\end{bmatrix} =
\begin{bmatrix}
1 & 2 & 3 & 4 & 5 \\
\sigma(1) & \sigma(2) & \sigma(3) & \sigma(4) & \sigma(5)
\end{bmatrix}
\]
We can consider $\sigma$ as a function, and write $\sigma(3)=5$, for example.  Since the top line of $\sigma$ is always the same, we can omit the top line and just write:
\[
\sigma = \begin{bmatrix}
\sigma(1) & \sigma(2) & \sigma(3) & \sigma(4) & \sigma(5)
\end{bmatrix}=
\begin{bmatrix}
4 & 2 & 5 & 1 & 3 
\end{bmatrix} 
\]

The mathematics of permutations is extensive and interesting; there are a few properties of permutations that we'll need.

\begin{itemize}
\item There are $n!$ permutations of $n$ distinct objects, since there are $n$ choices for the first object, $n-1$ choices for the second once the first has been chosen, and so on.

\item Every permutation can be built up by successively swapping pairs of objects.  For example, to build up the permutation $\begin{bmatrix} 3 & 1 & 2 \end{bmatrix}$ from the trivial permutation $\begin{bmatrix} 1 & 2 & 3 \end{bmatrix}$, you can first swap $2$ and $3$, and then swap $1$ and $3$.

\item For any given permutation $\sigma$, there is some number of swaps it takes to build up the permutation.  (It's simplest to use the minimum number of swaps, but you don't have to: it turns out that \emph{any} way of building up the permutation from swaps will have have the same parity of swaps, either even or odd.) 
If this number happens to be even, then $\sigma$ is called an \emph{even permutation};\index{Even permutation} if this number is odd, then $\sigma$ is an \emph{odd permutation}\index{Odd permutation}.  In fact, $n!$ is even for all $n\geq 2$, and exactly half of the permutations are even and the other half are odd.  It's worth noting that the trivial permutation (which sends $i\rightarrow i$ for every $i$) is an even permutation, since it uses zero swaps.
\end{itemize}

\begin{definition}
The \emph{sign function}\index{Sign function} is a function $\text{sgn}(\sigma)$ that sends permutations to the set $\{-1,1\}$, defined by:
\[ \text{sgn}(\sigma) = 
\left\{ \begin{array}{ll}
1 & \mbox{if $\sigma$ is even};\\
-1 & \mbox{if $\sigma$ is odd}.\end{array} \right.
\]
\end{definition}
We can use permutations to give a definition of the determinant.

\begin{definition}For an $n \times n$ matrix $M$, the \emph{determinant}\index{Determinant} of $M$ (sometimes written $|M|$) is given by:
\[
\det M = \sum_{\sigma} \text{sgn}(\sigma)\,  m^1_{\sigma(1)}m^2_{\sigma(2)}\ldots m^n_{\sigma(n)}.
\]
The sum is over all permutations of $n$.  Each summand is a product of a single entry from each row, but with the column numbers shuffled by the permutation $\sigma$.
\end{definition}

The last statement about the summands yields a nice property of the determinant:
\begin{theorem}
If $M$ has a row consisting entirely of zeros, then $m^i_{\sigma(i)}=0$ for every $\sigma$.  Then
$\det M=0$.
\end{theorem}


\begin{example}
Because there are many permutations of $n$, writing the determinant this way for a general matrix gives a very long sum.  For $n=4$, there are $24=4!$ permutations, and for $n=5$, there are already $120=5!$ permutations.

For a $4\times 4$ matrix, $M=\begin{pmatrix}
m^1_1 & m^1_2 & m^1_3 & m^1_4\\
m^2_1 & m^2_2 & m^2_3 & m^2_4\\
m^3_1 & m^3_2 & m^3_3 & m^3_4\\
m^4_1 & m^4_2 & m^4_3 & m^4_4\\
\end{pmatrix}$, then $\det M$ is:
\begin{eqnarray*}
\det M &=& 
 m^1_1m^2_2m^3_3m^4_4
-m^1_1m^2_3m^3_2m^4_4
-m^1_1m^2_2m^3_4m^4_3 \\
& -&m^1_2m^2_1m^3_3m^4_4
+m^1_1m^2_3m^3_4m^4_2
+m^1_1m^2_4m^3_2m^4_3 \\
&+ & m^1_2m^2_3m^3_1m^4_4
+m^1_2m^2_1m^3_4m^4_3
\pm \text{16 more terms}.
\end{eqnarray*}
\end{example}
This is very cumbersome.

Luckily, it is very easy to compute the determinants of certain matrices.  For example, if $M$ is diagonal, then $M^i_j=0$ whenever $i\neq j$.  Then all summands of the determinant involving off-diagonal entries vanish, so:
\[
\det M = \sum_{\sigma} \text{sgn}(\sigma) m^1_{\sigma(1)}m^2_{\sigma(2)}\ldots m^n_{\sigma(n)}= m^1_{1}m^2_{2}\ldots m^n_{n}.
\]
Thus, the determinant of a diagonal matrix is just the product of its diagonal entries.

Since the identity matrix is diagonal with all diagonal entries equal to one, we have:
\[
\det I=1.
\]

We would like to use the determinant to decide whether a matrix is invertible or not.  Previously, we computed the inverse of a matrix by applying row operations.  As such, it makes sense to ask what happens to the determinant when row operations are applied to a matrix.

\begin{remark}[Swapping Rows]

Swapping rows $i$ and $j$ (with $i<j$) in a matrix changes the determinant.  For a permutation $\sigma$, let $\hat{\sigma}$ be the permutation obtained by swapping $i$ and $j$.  The sign of $\hat{\sigma}$ is the opposite of the sign of $\sigma$.  Let $M$ be a matrix, and $M'$ be the same matrix, but with rows $i$ and $j$ swapped.  Then the determinant of $M'$ is:
\begin{eqnarray}
\det M' & = & \sum_{\sigma} \text{sgn}(\sigma)\, m^1_{\sigma(1)}\ldots m^j_{\sigma(i)}\ldots m^i_{\sigma(j)} \ldots m^n_{\sigma(n)} \nonumber \\
& = & \sum_{\sigma} \text{sgn}(\sigma) \,m^1_{\sigma(1)}\ldots m^i_{\sigma(j)}\ldots m^j_{\sigma(i)} \ldots m^n_{\sigma(n)} \nonumber \\
& = & \sum_{\sigma}(-\text{sgn}(\hat{\sigma})) \,m^1_{\hat{\sigma}(1)}\ldots m^i_{\hat{\sigma}(j)}\ldots m^j_{\hat{\sigma}(i)} \ldots m^n_{\hat{\sigma}(n)} \nonumber \\
& = & - \sum_{\hat{\sigma}} \text{sgn}(\hat{\sigma}) \,m^1_{\hat{\sigma}(1)}\ldots m^i_{\hat{\sigma}(j)}\ldots m^j_{\hat{\sigma}(i)} \ldots m^n_{\hat{\sigma}(n)} \nonumber \\
& = & -\det M.\nn
\end{eqnarray}
Thus we see that swapping rows changes the sign of the determinant. {\it I.e.} $$\det S^i_j M = - \det M\, .$$
Applying this result to $M=I$ (the identity matrix) yields
$$\det S^i_j=-1\, .$$

This implies another nice property of the determinant.  If two rows of the matrix are identical, then swapping the rows changes the sign of the matrix, but leaves the matrix unchanged.  Then we see the following:
\begin{theorem}
If $M$ has two identical rows, then $\det M = 0$.
\end{theorem}

\end{remark}


\subsection{Elementary Matrices}\index{Elementary matrix}

Our next goal is to find matrices that emulate the Gaussian row operations on a matrix.  In other words, for any matrix $M$, and a matrix $M'$ equal to~$M$ after a row operation, we wish to find a matrix $R$ such that $M'=RM$.

We will first find a matrix that, when it multiplies a matrix $M$,  rows $i$ and $j$ of $M$ are swapped.

Let $R^1$ through $R^n$ denote the rows  of $M$, and let $M'$ be the matrix $M$ with rows $i$ and $j$ swapped.  Then $M$ and $M'$ can be regarded as a block matrices:
\[
M=\colvec{\vdots \\ R^i \\ \vdots \\ R^j \\ \vdots} \, ,\text{ and }
M'=\colvec{\vdots \\ R^j \\ \vdots \\ R^i \\ \vdots}.
\]
Then notice that:
\[
M'=\colvec{\\ \vdots \\ R^j \\ \vdots \\ R^i \\ \vdots\\ \\  }= 
\begin{pmatrix}
1 & & & & & & \\
& \ddots & & & & & \\
& & 0 & & 1 & & \\
& & & \ddots & & & \\
& & 1 & & 0 & & \\
& & & & & \ddots & \\
& & & & & & 1 \\
\end{pmatrix}
\colvec{\\ \vdots \\ R^i \\ \vdots \\ R^j \\ \vdots \\ \\  }
\]
The matrix is just the identity matrix with rows $i$ and $j$ swapped.  This is called an \emph{elementary matrix} $E^i_j$\index{Elementary matrix!swapping rows}.  Then, symbolically, 

\[
M'=E^i_jM
\]
Because $\det I=1$ and swapping a pair of rows changes the sign of the determinant, we have found that 
\[
\det E^i_j = -1
\]



\section*{References}
Hefferon, Chapter Four, Section I.1 and I.3

Wikipedia:
\begin{itemize}
\item \href{http://en.wikipedia.org/wiki/Determinant}{Determinant}
\item \href{http://en.wikipedia.org/wiki/Permutation}{Permutation}
\item \href{http://en.wikipedia.org/wiki/Elementary_matrix}{Elementary Matrix}
\end{itemize}



\section*{Review Questions}

\begin{enumerate}
\item Let $M=\begin{pmatrix}
m^1_1 & m^1_2 & m^1_3\\
m^2_1 & m^2_2 & m^2_3\\
m^3_1 & m^3_2 & m^3_3\\
\end{pmatrix}$.  Use row operations to put $M$ into \emph{row echelon form}.  For simplicity, assume that $m_1^1\neq 0 \neq m^1_1m^2_2-m^2_1m^1_2$.

Prove that $M$ is non-singular if and only if:
\[
m^1_1m^2_2m^3_3 
- m^1_1m^2_3m^3_2 
+ m^1_2m^2_3m^3_1 
- m^1_2m^2_1m^3_3 
+ m^1_3m^2_1m^3_2
- m^1_3m^2_2m^3_1
\neq 0
\]

\item 
\begin{itemize}
\item[$i.$] What does the matrix $E^1_2=\begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix}$ do to $M=\begin{pmatrix}
a & b \\
d & c
\end{pmatrix}$ under left multiplication?  What about right multiplication?
\item[$ii.$] Find elementary matrices $R^1(\lambda)$ and $R^2(\lambda)$ that respectively multiply rows $1$ and $2$ of $M$ by $\lambda$ but otherwise leave $M$ the same under left multiplication.
\item[$iii.$] Find a matrix $S^1_2(\lambda)$ that adds a multiple $\lambda$ of row $2$ to row $1$ under left multiplication.
\end{itemize}

\item Let $M$ a matrix and $E^i_j$ the elementary matrix swapping two rows.  Explain every line of the series of equations proving that $\det M = -\det (E^i_jM)$.

\item The \emph{inversion number}\index{Inversion number} of a permutation $\sigma$ is the number of pairs $i<j$ such that $\sigma(i)>\sigma(j)$; it's the number of ``numbers that appear left of smaller numbers'' in the permutation.  For example, for the permutation $\sigma=[4,2,3,1]$, the inversion number is $5$.  $4$ comes before $2,3,$ and $1$, and $2$ and $3$ both come before $1$.

\begin{itemize}
\item[$i.$] What is the inversion number of the permutation $\tau_{i,j}$ that exchanges $i$ and $j$ and leaves everything else alone?  Is $\tau_{i,j}$ an even or an odd permutation?  What is $\tau_{i,j}^2$?

\item[$ii.$] Given a permutation $\sigma$, we can make a new permutation $\tau_{i,j} \sigma$ by exchanging the $i$th and $j$th entries of $\sigma$.  If $\sigma$ has $N$ inversions and $\tau_{i,j} \sigma$ has $M$ inversions, \emph{show} that $N$ and $M$ have different parity.  In other words, applying a transposition to $\sigma$ changes the number of inversions by an odd number.

\item[$iii.$] Show that $(-1)^N=\sgn(\sigma)$, where $\sigma$ is a permutation with $N$ inversions.  \emph{(Hint: How many inversions does the identity permutation have?  Also, recall that $\sigma$ can be built up with transpositions.) }
\end{itemize}
\end{enumerate}



\newpage