\section{ Inverse Matrix }


\begin{definition}
A square matrix $M$ is \emph{invertible} (or \emph{nonsingular})\index{Invertible}\index{Nonsingular} if there exists a matrix $M^{-1}$ such that
\[
M^{-1}M=I=M^{-1}M.
\]
\end{definition}



\begin{remark}[Inverse of a $2\times 2$ Matrix] Let $M$ and $N$ be the matrices:
\[
M=\begin{pmatrix}
a & b \\
c & d \\
\end{pmatrix},\qquad N=\begin{pmatrix}
d & -b \\
-c & a \\
\end{pmatrix}
\]
Multiplying these matrices gives:
\[
MN=\begin{pmatrix}
ad-bc & 0 \\
0 & ad-bc \\
\end{pmatrix}=(ad-bc)I
\]

Then $M^{-1}=\frac{1}{ad-bc}\begin{pmatrix}
d & -b \\
-c & a \\
\end{pmatrix}$, so long as $ad-bc\neq 0$.    
\end{remark}


\subsection{Three Properties of the Inverse}

\begin{enumerate}
\item If $A$ is a square matrix and $B$ is the inverse of $A$, then $A$ is the inverse of $B$, since $AB=I=BA$.  Then we have the identity:
\[
(A^{-1})^{-1}=A
\]

\item Notice that $B^{-1}A^{-1}AB=B^{-1}IB=I=ABB^{-1}A^{-1}$.
Then:
\[
(AB)^{-1}=B^{-1}A^{-1}
\]
Then much like the transpose, taking the inverse of a product \emph{reverses} the order of the product.

\item Finally, recall that $(AB)^T=B^TA^T$.  Since $I^T=I$, then $(A^{-1}A)^T=A^T(A^{-1})^T=I$.  Similarly, $(AA^{-1})^T=(A^{-1})^TA^T=I$.  Then:
\[
(A^{-1})^T=(A^T)^{-1}
\]
As such, we could even write $A^{-T}$ for the inverse of the transpose of $A$ (or equivalently the transpose of the inverse).
\end{enumerate}

\subsection{Finding Inverses}

Suppose $M$ is a square matrix and $MX=V$ is a linear system with unique solution $X_0$.  Since there is a unique solution, $M^{-1}V$, then the reduced row echelon form of the linear system has an identity matrix on the left:
\[
\begin{amatrix}{1}
M & V
\end{amatrix}
\sim
\begin{amatrix}{1}
I & M^{-1}V
\end{amatrix}
\]
Solving the linear system $MX=V$ then tells us what $M^{-1}V$ is.  

To solve many linear systems at once, we can consider augmented matrices with a matrix on the right side instead of a column vector, and then apply Gaussian row reduction to the left side of the matrix.  Once the identity matrix is on the left side of the augmented matrix, then the solution of each of the individual linear systems is on the right.

To compute $M^{-1}$, we would like $M^{-1}$, rather than $M^{-1}$ to appear on the right side of our augmented matrix.
This is achieved by  solving the collection of systems $MX=e_k$, where $e_k$ is the column vector of zeroes with a $1$ in the $k$th entry.  
{\it I.e.} the$n\times n$ identity matrix can be viewed as a bunch of column vectors $I_n=(e_1 \ e_2 \ \cdots e_n)$. So, putting the $e_k$'s together into an identity matrix, we get:
\[
\begin{amatrix}{1}
M & I
\end{amatrix}
\sim
\begin{amatrix}{1}
I & M^{-1}I
\end{amatrix}
=\begin{amatrix}{1}
I & M^{-1}
\end{amatrix}
\]


\begin{example}
Find $\begin{pmatrix}
-1 & 2 & -3 \\
2 & 1 & 0 \\
4 & -2 & 5 \\
\end{pmatrix}^{-1}
$.
Start by writing the augmented matrix, then apply row reduction to the left side.

\begin{eqnarray*}
\begin{pmat}{ccc|ccc}
-1 & 2 & -3 & 1 & 0 & 0 \\[1mm]
2  & 1 &  0 & 0 & 1 & 0 \\[1mm]
 4 & -2 & 5 & 0 & 0 & 1 \\[1mm]
\end{pmat} & \sim & \begin{pmat}{ccc|ccc}
1  & -2&  3  & 1 & 0 & 0 \\[1mm]
0  & 5 &  -6 & 2 & 1 & 0 \\[1mm]
 0 & 6 & -7  & 4 & 0 & 1 \\[1mm]
\end{pmat} \\
& \sim & \begin{pmat}{ccc|ccc}
1  & 0 &  \frac{3}{5}  & \frac{-1}{4} & \frac{2}{5} & 0 \\[1mm]
0  & 1 &  \frac{-6}{5} & \frac{2}{5} & \frac{1}{5}  & 0 \\[1mm]
 0 & 0 &  \frac{1}{5}  & \frac{4}{5} & \frac{-6}{5} & 1 \\[1mm]
\end{pmat} \\
& \sim & \begin{pmat}{ccc|ccc}
1  & 0 &  1  & -5 & 4 & 0 \\[1mm]
0  & 1 &  0  & 10 & -7 & 6 \\[1mm]
 0 & 0 &  1  & 8 & -6 & 5 \\[1mm]
\end{pmat} \\
\end{eqnarray*}
At this point, we know $M^{-1}$ assuming we didn't goof up\index{Goofing up}.  However, row reduction is a lengthy and arithmetically involved process, so we should~\emph{check our answer,} by confirming that $MM^{-1}=I$ (or if you prefer $M^{-1}M=I$):
\[MM^{-1} = 
\begin{pmatrix}
-1 & 2 & -3 \\
2 & 1 & 0 \\
4 & -2 & 5 \\
\end{pmatrix}\begin{pmatrix}
-5 & 4 & 0 \\
10 & -7 & 6 \\
 8 & -6 & 5 \\
\end{pmatrix}
\]  
The product of the two matrices is indeed the identity matrix, so we're done.
\end{example}

\subsection{Linear Systems and Inverses}

If $M^{-1}$ exists and is known, then we can immediately solve linear systems associated to $M$.

\begin{example}
Consider the linear system:

\[
      \begin{linsys}{2}
            -x & +2y & -3z         &=& 1  \\[1mm]
            2x & +y  &             &=& 2 \\[1mm]
            4x & -2y & +5z         &=& 0  
      \end{linsys}
\]
The associated matrix equation is $MX=\colvec{1\\2\\0}$.  Then:

\[
\colvec{x\\y\\z}=\begin{pmatrix}
-1 & 2 & -3 \\
2 & 1 & 0 \\
4 & -2 & 5 \\
\end{pmatrix}^{-1}\colvec{1\\2\\0}
=\begin{pmatrix}
-5 & 4 & 0 \\
10 & -7 & 6 \\
 8 & -6 & 5 \\
\end{pmatrix}\colvec{1\\2\\0}
=\colvec{3\\-4\\-4}
\]
Then $\colvec{x\\y\\z}=\colvec{3\\-4\\-4}$.  
In summary, when $M^{-1}$ exists, then $$MX=V \Rightarrow X=M^{-1}V\, .$$
\end{example}

\subsection{Homogeneous Systems}

\begin{theorem}
A square matrix $M$ is invertible if and only if the homogeneous system $$MX=0$$ has no non-zero solutions.
\end{theorem}

\begin{proof}
First, suppose that $M^{-1}$ exists.  Then $MX=0 \Rightarrow X=M^{-1}0=0$.  Thus, if $M$ is invertible, then $MX=0$ has no non-zero solutions.

On the other hand, $MX=0$ always has the solution $X=0$.  If no other solutions exist, then $M$ can be put into reduced row echelon form with every variable a pivot.  In this case, $M^{-1}$ can be computed using the process in the previous section.
\end{proof}


\subsection{Bit Matrices}\index{Bit matrices}
In computer science, information is recorded using binary strings of data.  For example, the following string contains an English word:
\[
011011000110100101101110011001010110000101110010
\]
A \emph{bit} is the basic unit of information, keeping track of a single one or zero.  Computers can add and multiply individual bits very quickly.

Consider the set $\Z_2=\{0,1 \}$ with addition and multiplication given by the following tables:
\[
\begin{array}{c|cc}
+ & 0 & 1 \\ \hline
0 & 0 & 1 \\
1 & 1 & 0 \\
\end{array}
\qquad
\begin{array}{c|cc}
\cdot & 0 & 1 \\ \hline
0 & 0 & 0 \\
1 & 0 & 1 \\
\end{array}
\]
Notice that $-1=1$, since $1+1=0$.

It turns out that $\Z_2$ is just as good as the real or complex numbers (they are all \emph{fields}), so we can apply all of the linear algebra we have learned thus far to matrices with $\Z_2$ entries.  A matrix with entries in $\Z_2$ is sometimes called a \emph{bit matrix}.

\begin{example}
$\begin{pmatrix}
1 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 1 \\
\end{pmatrix}$ is an invertible matrix over $\Z_2$:

\[\begin{pmatrix}
1 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 1 \\
\end{pmatrix}^{-1}=\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 1 \\
\end{pmatrix}
\]

This can be easily verified by multiplying:

\[\begin{pmatrix}
1 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 1 \\
\end{pmatrix}\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 1 \\
\end{pmatrix}=\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{pmatrix}
\]
\end{example}

\begin{remark}[Application: Cryptography]  
A very simple way to hide information is to use a substitution cipher, in which the alphabet is permuted and each letter in a message is systematically exchanged for another.  For example, the ROT-13 cypher just exchanges a letter with the letter thirteen places before or after it in the alphabet.  For example, HELLO becomes URYYB.  Applying the algorithm again decodes the message, turning URYYB back into HELLO.  Substitution ciphers are easy to break, but the basic idea can be extended to create cryptographic systems that are practically uncrackable.  For example, a \emph{one-time pad} is a system that uses a different substitution for each letter in the message.  So long as a particular set of substitutions is not used on more than one message, the one-time pad is unbreakable.

English characters are often stored in computers in the ASCII format.  In ASCII, a single character is represented by a string of eight bits, which we can consider as a vector in $\Z_2^8$ (which is like vectors in $\Re^8$, where the entries are zeros and ones).  One way to create a substitution cipher, then, is to choose an $8\times 8$ invertible bit matrix $M$, and multiply each letter of the message by $M$.  Then to decode the message, each string of eight characters would be multiplied by $M^{-1}$.  

To make the message a bit tougher to decode, one could consider pairs (or longer sequences) of letters as a single vector in $\Z_2^{16}$ (or a higher-dimensional space), and then use an appropriately-sized invertible matrix.

For more on cryptography, see ``The Code Book,'' by Simon Singh (1999, Doubleday).
\end{remark}


\section*{References}

Hefferon: Chapter Three, Section IV.2

Wikipedia:
\href{http://en.wikipedia.org/wiki/Invertible_matrix}{Invertible Matrix}






\section*{Review Questions}
\begin{enumerate}

\item Let $M$ be a square matrix.  Explain why the following statements are equivalent:
\begin{itemize}
\item[$i.$] $MX=V$ has a \emph{unique} solution for every column vector $V$.
\item[$ii.$] $M$ is non-singular.
\end{itemize}
(Show that $(i)\Rightarrow (ii)$ and $(ii)\Rightarrow (i)$.)

\item Find formulas for the inverses of the following matrices, when they are not singular:
\begin{itemize}
\item[$i.$] $\begin{pmatrix}
1 & a & b \\
0 & 1 & c \\
0 & 0 & 1 \\
\end{pmatrix}$
\item[$ii.$] $\begin{pmatrix}
a & b & c \\
0 & d & e \\
0 & 0 & f \\
\end{pmatrix}$
\end{itemize}
When are these matrices singular?

\item Write down all $2\times 2$ bit matrices and decide which of them are singular.  For those which are not singular, pair them with their inverse.


\end{enumerate}

\newpage


