A square matrix $A$ is invertible when some $A^{-1}$ undoes it: $AA^{-1}=A^{-1}A=I$. Every row operation is multiplication by an elementary matrix, and row reducing $\left[\begin{array}{c|c}A&I\end{array}\right]$ to $\left[\begin{array}{c|c}I&A^{-1}\end{array}\right]$ finds the inverse.
To solve $5x=15$ you multiply both sides by $\tfrac15$, the number that undoes multiplication by $5$. Can we do the same with a matrix equation $A\mathbf{x}=\mathbf{b}$ โ find a matrix that undoes $A$ and simply multiply by it? For many square matrices the answer is yes, and the undoing matrix is called the inverse $A^{-1}$. It gives a formula for the solution, $\mathbf{x}=A^{-1}\mathbf{b}$, which is especially handy when the same system has to be solved for many different right-hand sides: a nutritionist planning many diets from the same foods, an engineer testing a structure under many loads, or a code that has to be locked and unlocked over and over.
But not every matrix can be undone, just as $0$ has no reciprocal โ and with matrices there are many more "zeros". In this section we find out which matrices are invertible, compute their inverses with the row reduction of Chapter 1, and discover that each row operation is itself a matrix multiplication. That idea ties everything together in the Invertible Matrix Theorem, a list of conditions that are all true or all false at once.
Invertible Matrices
๐ Definition 2.7 โ Invertible matrix
An $n\times n$ matrix $A$ is invertible (or non-singular) if there is an $n\times n$ matrix $C$ with
$$AC=I_n\quad\text{and}\quad CA=I_n .$$
Such a $C$ is called an inverse of $A$. A square matrix that has no inverse is called singular. Only square matrices are called invertible or singular.
๐ Theorem 2.5 โ The inverse is unique
If $A$ is invertible, it has exactly one inverse. We call it $A^{-1}$, so $AA^{-1}=A^{-1}A=I$.
Proof. Suppose $C$ and $D$ are both inverses of $A$. Then, using associativity, $C=CI=C(AD)=(CA)D=ID=D$. $\square$
For $2\times2$ matrices there is a quick formula. The number $ad-bc$ that appears in it is the determinant of the matrix, studied in Chapter 3.
๐ Theorem 2.6 โ Inverse of a $2\times2$ matrix
Let $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$. If $ad-bc\ne0$, then $A$ is invertible and
$$A^{-1}=\frac{1}{ad-bc}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}.$$
If $ad-bc=0$, then $A$ is singular.
Why. Multiplying out, $\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}=\begin{bmatrix}ad-bc&0\\0&ad-bc\end{bmatrix}=(ad-bc)I$, and the same holds in the other order; divide by $ad-bc$. If $ad-bc=0$, this product is $O$; were $A$ invertible, multiplying on the left by $A^{-1}$ would give $\begin{bmatrix}d&-b\\-c&a\end{bmatrix}=O$, so $a=b=c=d=0$ and $A=O$, which is certainly not invertible.
โ๏ธ Example 1 โ Checking and computing $2\times2$ inverses
(a) Show that $C=\begin{bmatrix}3&-5\\-1&2\end{bmatrix}$ is the inverse of $A=\begin{bmatrix}2&5\\1&3\end{bmatrix}$.
(b) Find the inverse of $B=\begin{bmatrix}4&7\\2&5\end{bmatrix}$.
(c) Show that $S=\begin{bmatrix}6&-4\\-9&6\end{bmatrix}$ is singular.
๐ก Show solutionโถ
(a) $$AC=\begin{bmatrix}6-5&-10+10\\3-3&-5+6\end{bmatrix}=I,\qquad CA=\begin{bmatrix}6-5&15-15\\-2+2&-5+6\end{bmatrix}=I.$$ Both products are $I$, so $C=A^{-1}$.
(b) $ad-bc=4(5)-7(2)=6\ne0$. Swap the diagonal entries, change the signs of the others, divide by $6$: $$B^{-1}=\frac16\begin{bmatrix}5&-7\\-2&4\end{bmatrix}=\begin{bmatrix}\tfrac56&-\tfrac76\\-\tfrac13&\tfrac23\end{bmatrix}.$$
(c) $ad-bc=36-36=0$, so $S$ is singular. Notice the second row is $-\tfrac32$ times the first: the columns point along the same line, so $S$ squashes the plane onto a line and nothing can undo it.
๐ Theorem 2.7 โ Solving $A\mathbf{x}=\mathbf{b}$ with the inverse
If $A$ is an invertible $n\times n$ matrix, then for every $\mathbf{b}$ in $\mathbb{R}^n$ the equation $A\mathbf{x}=\mathbf{b}$ has exactly one solution, namely $\mathbf{x}=A^{-1}\mathbf{b}$.
Proof. It is a solution: $A\left(A^{-1}\mathbf{b}\right)=\left(AA^{-1}\right)\mathbf{b}=\mathbf{b}$. It is the only one: if $A\mathbf{u}=\mathbf{b}$, multiply on the left by $A^{-1}$ to get $\mathbf{u}=A^{-1}\mathbf{b}$. $\square$
โ๏ธ Example 2 โ One inverse, many diets
One serving of food P contains $3$ g of protein and $1$ g of fat; one serving of food Q contains $5$ g of protein and $2$ g of fat. How many servings $x_1$ of P and $x_2$ of Q give (a) $34$ g protein and $13$ g fat; (b) $29$ g protein and $11$ g fat?
๐ก Show solutionโถ
Model Protein: $3x_1+5x_2$; fat: $x_1+2x_2$. So $A\mathbf{x}=\mathbf{b}$ with $A=\begin{bmatrix}3&5\\1&2\end{bmatrix}$ (columns = nutrients per serving of each food).
Inverse $ad-bc=6-5=1$, so $A^{-1}=\begin{bmatrix}2&-5\\-1&3\end{bmatrix}$.
(a) $\mathbf{x}=A^{-1}\begin{bmatrix}34\\13\end{bmatrix}=\begin{bmatrix}68-65\\-34+39\end{bmatrix}=\begin{bmatrix}3\\5\end{bmatrix}$: $3$ servings of P and $5$ of Q. Check: protein $9+25=34$ g โ, fat $3+10=13$ g โ.
(b) $\mathbf{x}=A^{-1}\begin{bmatrix}29\\11\end{bmatrix}=\begin{bmatrix}58-55\\-29+33\end{bmatrix}=\begin{bmatrix}3\\4\end{bmatrix}$: $3$ servings of P and $4$ of Q. The inverse was computed once and reused โ that is its main practical advantage.
๐ Theorem 2.8 โ Properties of inverses
Let $A$ and $B$ be invertible $n\times n$ matrices, $c\ne0$ a scalar and $k$ a positive integer. Then
$A^{-1}$ is invertible and $\left(A^{-1}\right)^{-1}=A$;
$AB$ is invertible and $(AB)^{-1}=B^{-1}A^{-1}$ (the order reverses);
$A^{T}$ is invertible and $\left(A^{T}\right)^{-1}=\left(A^{-1}\right)^{T}$;
$cA$ is invertible with $(cA)^{-1}=\tfrac1c A^{-1}$, and $A^k$ is invertible with $\left(A^k\right)^{-1}=\left(A^{-1}\right)^k$.
Proof of 2 and 3. $(AB)\left(B^{-1}A^{-1}\right)=A\left(BB^{-1}\right)A^{-1}=AIA^{-1}=AA^{-1}=I$, and similarly $\left(B^{-1}A^{-1}\right)(AB)=I$. For 3, by Theorem 2.4, $A^{T}\left(A^{-1}\right)^{T}=\left(A^{-1}A\right)^{T}=I^{T}=I$, and similarly in the other order. $\square$
โ ๏ธ Common mistakes with inverses
1. Socks and shoes. You put on socks, then shoes; to undo, take off the shoes first. So $(AB)^{-1}=B^{-1}A^{-1}$, not $A^{-1}B^{-1}$ (these differ whenever $A^{-1}$ and $B^{-1}$ do not commute).
2. No formula for sums. $(A+B)^{-1}\ne A^{-1}+B^{-1}$ in general; $A+B$ may not even be invertible (take $B=-A$).
3. Not "one over each entry". The inverse of $\begin{bmatrix}2&0\\0&4\end{bmatrix}$ is $\begin{bmatrix}\tfrac12&0\\0&\tfrac14\end{bmatrix}$, but the inverse of $\begin{bmatrix}1&2\\3&4\end{bmatrix}$ is $\begin{bmatrix}-2&1\\\tfrac32&-\tfrac12\end{bmatrix}$, not $\begin{bmatrix}1&\tfrac12\\\tfrac13&\tfrac14\end{bmatrix}$.
4. Never divide by a matrix. "$\dfrac{B}{A}$" is meaningless: $A^{-1}B$ and $BA^{-1}$ are usually different. To solve $AX=B$ multiply on the left: $X=A^{-1}B$; to solve $XA=B$ multiply on the right: $X=BA^{-1}$.
Elementary Matrices
Row reduction in Chapter 1 used three kinds of elementary row operations: replacement ($R_i\to R_i+cR_j$), interchange ($R_i\leftrightarrow R_j$) and scaling ($R_i\to cR_i$ with $c\ne0$). Remarkably, each of them can be carried out by a matrix multiplication.
๐ Definition 2.8 โ Elementary matrix
An elementary matrix is a matrix obtained by performing a single elementary row operation on an identity matrix $I_n$. For example, in the $3\times3$ case,
$$E_1=\begin{bmatrix}1&0&0\\-3&1&0\\0&0&1\end{bmatrix}\ (R_2\to R_2-3R_1),\quad E_2=\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix}\ (R_1\leftrightarrow R_3),\quad E_3=\begin{bmatrix}1&0&0\\0&1&0\\0&0&5\end{bmatrix}\ (R_3\to5R_3).$$
๐ Theorem 2.9 โ Row operations are left multiplications
If an elementary row operation is performed on an $m\times n$ matrix $A$, the result is $EA$, where $E$ is the $m\times m$ elementary matrix obtained by performing the same operation on $I_m$.
Every elementary matrix $E$ is invertible, and $E^{-1}$ is the elementary matrix of the reverse operation: $R_i\to R_i+cR_j$ is undone by $R_i\to R_i-cR_j$; $R_i\leftrightarrow R_j$ by itself; $R_i\to cR_i$ by $R_i\to\tfrac1cR_i$.
Why. By the row view of products, row $i$ of $EA$ is (row $i$ of $E$)$\,A$, a combination of the rows of $A$ with weights from row $i$ of $E$. The rows of $E$ are rows of $I$ altered by the operation, so they pick out exactly the altered rows. For part 2, if $F$ is the matrix of the reverse operation, then $FE$ is "do the operation, then undo it" applied to $I$, which gives $I$; likewise $EF=I$.
โ๏ธ Example 3 โ Elementary matrices at work
Let $A=\begin{bmatrix}1&2&0\\3&-1&4\\2&0&1\end{bmatrix}$ and let $E_1,E_2,E_3$ be the matrices of Definition 2.8. Compute $E_1A$, $E_2A$, $E_3A$, and write down $E_1^{-1}$, $E_2^{-1}$, $E_3^{-1}$.
๐ก Show solutionโถ
$E_1A$ $$E_1A=\begin{bmatrix}1&2&0\\0&-7&4\\2&0&1\end{bmatrix}:$$ row 2 became $(3,-1,4)-3(1,2,0)=(0,-7,4)$ โ exactly $R_2\to R_2-3R_1$.
$E_2A$, $E_3A$ $$E_2A=\begin{bmatrix}2&0&1\\3&-1&4\\1&2&0\end{bmatrix}\ (\text{rows 1 and 3 swapped}),\qquad E_3A=\begin{bmatrix}1&2&0\\3&-1&4\\10&0&5\end{bmatrix}\ (\text{row 3 times }5).$$
Inverses Reverse each operation: $$E_1^{-1}=\begin{bmatrix}1&0&0\\3&1&0\\0&0&1\end{bmatrix}\ (R_2\to R_2+3R_1),\quad E_2^{-1}=E_2,\quad E_3^{-1}=\begin{bmatrix}1&0&0\\0&1&0\\0&0&\tfrac15\end{bmatrix}.$$
Check $E_1^{-1}E_1$: row 2 is $(3,1,0)E_1=(3-3,1,0)=(0,1,0)$, so $E_1^{-1}E_1=I$ โ.
Interactive 1 โ An Elementary Matrix Acting on the Plane
A $2\times2$ elementary matrix $E$ moves every point $\mathbf{x}$ of the plane to $E\mathbf{x}$ โ on the vector $\mathbf{x}=(x,y)$ it performs its row operation. Press Play: the letter F and the unit square are first transformed by $E$, then $E^{-1}$ (the reverse row operation) brings everything back exactly. The red and green segments are the images of $(1,0)$ and $(0,1)$ โ the columns of the current matrix. Change the operation and the number $k$. Try scaling with $k=0$.
1.5
$E$โ
row operationโ
$E^{-1}$โ
reverse operationโ
now showingโ
Elementary matrices let us record a whole row reduction as a product. If $E_1,E_2,\dots,E_k$ are the matrices of the operations used, in order, then reducing $A$ to $U$ means $E_k\cdots E_2E_1A=U$. Read right to left: $E_1$ acts first.
โ๏ธ Example 4 โ Recording a row reduction
Row reduce $A=\begin{bmatrix}1&2\\3&4\end{bmatrix}$ to $I$, record the elementary matrices, and use them to find $A^{-1}$ and to write $A$ as a product of elementary matrices.
Record $E_1=\begin{bmatrix}1&0\\-3&1\end{bmatrix}$, $E_2=\begin{bmatrix}1&0\\0&-\tfrac12\end{bmatrix}$, $E_3=\begin{bmatrix}1&-2\\0&1\end{bmatrix}$, and $E_3E_2E_1A=I$.
Inverse $E_3E_2E_1$ times $A$ is $I$, so $$A^{-1}=E_3E_2E_1=\begin{bmatrix}1&-2\\0&1\end{bmatrix}\begin{bmatrix}1&0\\\tfrac32&-\tfrac12\end{bmatrix}=\begin{bmatrix}-2&1\\\tfrac32&-\tfrac12\end{bmatrix}.$$ Check with Theorem 2.6: $ad-bc=-2$ and $\tfrac{1}{-2}\begin{bmatrix}4&-2\\-3&1\end{bmatrix}=\begin{bmatrix}-2&1\\\tfrac32&-\tfrac12\end{bmatrix}$ โ.
Factor $A$ Multiply $E_3E_2E_1A=I$ on the left by $E_3^{-1}$, then $E_2^{-1}$, then $E_1^{-1}$: $$A=E_1^{-1}E_2^{-1}E_3^{-1}=\begin{bmatrix}1&0\\3&1\end{bmatrix}\begin{bmatrix}1&0\\0&-2\end{bmatrix}\begin{bmatrix}1&2\\0&1\end{bmatrix}.$$ Multiplying out gives $\begin{bmatrix}1&0\\3&-2\end{bmatrix}\begin{bmatrix}1&2\\0&1\end{bmatrix}=\begin{bmatrix}1&2\\3&4\end{bmatrix}$ โ.
Computing $A^{-1}$ by Row Reduction
Example 4 contains a general method. If row operations $E_1,\dots,E_k$ turn $A$ into $I$, then $A^{-1}=E_k\cdots E_1=E_k\cdots E_1I$: the same operations, applied to $I$, produce $A^{-1}$. So we row reduce $A$ and $I$ side by side.
๐ Theorem 2.10 โ Invertibility and row reduction
An $n\times n$ matrix $A$ is invertible if and only if $A$ is row equivalent to $I_n$. In that case, any sequence of elementary row operations that reduces $A$ to $I_n$ also transforms $I_n$ into $A^{-1}$:
$$\left[\begin{array}{c|c}A&I\end{array}\right]\ \longrightarrow\ \left[\begin{array}{c|c}I&A^{-1}\end{array}\right].$$
Proof. If $E_k\cdots E_1A=I$, each $E_i$ is invertible (Theorem 2.9), so $A=(E_k\cdots E_1)^{-1}$ is invertible (Theorem 2.8) with $A^{-1}=E_k\cdots E_1$. Conversely, if $A$ is invertible, then $A\mathbf{x}=\mathbf{0}$ has only the solution $\mathbf{x}=A^{-1}\mathbf{0}=\mathbf{0}$, so there are no free variables: every column of $A$ has a pivot, and a square matrix with $n$ pivots reduces to $I_n$. $\square$
Write the $n\times2n$ matrix $\left[\begin{array}{c|c}A&I\end{array}\right]$.
Row reduce, working column by column: get a pivot $1$ (swap a lower row up if the pivot position holds $0$; scale), then clear every other entry of that column. Apply each operation to the whole row, both halves.
If the left half becomes $I$, the right half is $A^{-1}$. If a row of zeros appears in the left half, stop: $A$ is singular.
Check: multiply $A$ by your answer; you should get $I$ (checking one or two entries catches most slips).
โ๏ธ Example 5 โ A $3\times3$ inverse
Find the inverse of $A=\begin{bmatrix}1&2&1\\2&5&4\\1&1&0\end{bmatrix}$.
๐ก Show solutionโถ
Set up $$\left[\begin{array}{ccc|ccc}1&2&1&1&0&0\\2&5&4&0&1&0\\1&1&0&0&0&1\end{array}\right]$$
Check Row 1 of $A$ times the columns of $A^{-1}$: $-4+8-3=1$, $1-2+1=0$, $3-4+1=0$ โ; row 3: $-4+4+0=0$, $1-1+0=0$, $3-2+0=1$ โ. Interactive 2 replays this reduction step by step and shows each elementary matrix.
Interactive 2 โ Step Through $\left[\begin{array}{c|c}A&I\end{array}\right]\to\left[\begin{array}{c|c}I&A^{-1}\end{array}\right]$
Each step performs one row operation on the whole augmented matrix (exact fractions). The red row is being changed, the blue row is the pivot row used to change it, and the purple box marks the pivot. Below, $E$ is the elementary matrix of the step โ multiplying by it on the left does the same thing. Notice that the right half is always the product of all the $E$'s so far.
stepโ
row operationโ
left halfโ
โ๏ธ Example 6 โ Detecting a singular matrix
Is $A=\begin{bmatrix}1&2&-1\\2&3&1\\3&5&0\end{bmatrix}$ invertible? If not, find a non-zero solution of $A\mathbf{x}=\mathbf{0}$.
๐ก Show solutionโถ
Reduce $R_2\to R_2-2R_1$, $R_3\to R_3-3R_1$, then $R_3\to R_3-R_2$: $$\begin{bmatrix}1&2&-1\\2&3&1\\3&5&0\end{bmatrix}\to\begin{bmatrix}1&2&-1\\0&-1&3\\0&-1&3\end{bmatrix}\to\begin{bmatrix}1&2&-1\\0&-1&3\\0&0&0\end{bmatrix}.$$
Conclude A zero row appears, so there are only $2$ pivots: $A$ is not row equivalent to $I_3$ and, by Theorem 2.10, $A$ is singular. (In fact row 3 = row 1 + row 2.) There is no need to carry the right half along once this happens.
Null solution $x_3=t$ is free; row 2 gives $-x_2+3t=0$, so $x_2=3t$; row 1 gives $x_1=-2x_2+x_3=-5t$. Taking $t=1$: $\mathbf{x}=(-5,3,1)$.
Check $A\mathbf{x}=(-5+6-1,\ -10+9+1,\ -15+15+0)=(0,0,0)$ โ. A non-zero vector sent to $\mathbf{0}$ can never be recovered โ another way to see that no inverse exists.
The Invertible Matrix Theorem
We now have many ways of describing the same property of a square matrix. The next theorem says they are all equivalent โ knowing any one of them tells you all of the others. More conditions will be added in Chapters 3, 5 and 7.
๐ Theorem 2.11 โ The Invertible Matrix Theorem (first version)
Let $A$ be a square $n\times n$ matrix. The following statements are equivalent (all true or all false):
$A$ is invertible.
$A$ is row equivalent to $I_n$.
$A$ has $n$ pivot positions.
The equation $A\mathbf{x}=\mathbf{0}$ has only the trivial solution $\mathbf{x}=\mathbf{0}$.
The equation $A\mathbf{x}=\mathbf{b}$ has at least one solution for every $\mathbf{b}$ in $\mathbb{R}^n$.
The equation $A\mathbf{x}=\mathbf{b}$ has exactly one solution for every $\mathbf{b}$ in $\mathbb{R}^n$.
$A$ is a product of elementary matrices.
There is an $n\times n$ matrix $C$ with $CA=I$.
There is an $n\times n$ matrix $D$ with $AD=I$.
$A^{T}$ is invertible.
Why they are equivalent. (a)โ(h) is clear. (h)โ(d): if $A\mathbf{x}=\mathbf{0}$ then $\mathbf{x}=CA\mathbf{x}=C\mathbf{0}=\mathbf{0}$. (d)โ(c): no free variables means a pivot in every one of the $n$ columns. (c)โ(b): a square matrix with $n$ pivots has reduced echelon form $I_n$. (b)โ(g)โ(a): Example 4 and Theorem 2.10 โ $A=E_1^{-1}\cdots E_k^{-1}$ is a product of invertible matrices. (a)โ(f)โ(e): Theorem 2.7. (e)โ(i): solve $A\mathbf{x}=\mathbf{e}_j$ for each column $\mathbf{e}_j$ of $I$ and use the solutions as the columns of $D$. (i)โ(a): transposing $AD=I$ gives $D^{T}A^{T}=I$, so $A^{T}$ satisfies (h), hence (a); then $A=\left(A^{T}\right)^{T}$ is invertible by Theorem 2.8. Finally (a)โ(j) by Theorem 2.8.
โ ๏ธ Reading the Invertible Matrix Theorem
1. Square matrices only. For a $2\times3$ matrix, $A\mathbf{x}=\mathbf{b}$ may be solvable for every $\mathbf{b}$ while $A\mathbf{x}=\mathbf{0}$ has non-zero solutions โ the theorem says nothing about non-square matrices.
2. One side is enough. By (h) and (i), for square matrices it suffices to check $CA=I$ or $AD=I$; the other product is then automatically $I$ too.
3. Use the negations. The theorem is just as useful backwards: if $A\mathbf{x}=\mathbf{0}$ has a non-zero solution, or the echelon form has a zero row, then $A$ is singular and $A\mathbf{x}=\mathbf{b}$ fails to have a solution for some $\mathbf{b}$.
Exercises
I
$2\times2$ inverses.
1 Find the inverse of $\begin{bmatrix}3&1\\5&2\end{bmatrix}$.
2 Find the inverse of $\begin{bmatrix}2&-4\\1&3\end{bmatrix}$.
3 Is $\begin{bmatrix}6&4\\3&2\end{bmatrix}$ invertible? Explain.
4 Show that the rotation matrix $R_\theta=\begin{bmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{bmatrix}$ is invertible for every $\theta$, that $R_\theta^{-1}=R_\theta^{T}$, and that $R_\theta^{-1}=R_{-\theta}$. Interpret geometrically.
5 For which values of $k$ is $\begin{bmatrix}k&4\\1&k\end{bmatrix}$ invertible?
6 Use part 1 to solve $3x_1+x_2=4$, $5x_1+2x_2=7$.
7 Use part 1 to find the matrix $X$ with $\begin{bmatrix}3&1\\5&2\end{bmatrix}X=\begin{bmatrix}1&0\\2&1\end{bmatrix}$.
4 $ad-bc=\cos^2\theta+\sin^2\theta=1\ne0$, so $R_\theta^{-1}=\begin{bmatrix}\cos\theta&\sin\theta\\-\sin\theta&\cos\theta\end{bmatrix}=R_\theta^{T}$, and since $\cos(-\theta)=\cos\theta$, $\sin(-\theta)=-\sin\theta$, this is $R_{-\theta}$. Undoing a rotation by $\theta$ is rotating back by $\theta$.
5 $ad-bc=k^2-4$, so the matrix is invertible exactly when $k\ne2$ and $k\ne-2$.
7 Multiply on the left by the inverse: $X=\begin{bmatrix}2&-1\\-5&3\end{bmatrix}\begin{bmatrix}1&0\\2&1\end{bmatrix}=\begin{bmatrix}0&-1\\1&3\end{bmatrix}$.
II
Inverses by row reduction. Find the inverse, or show that the matrix is singular.
7Challenge. For which values of $c$ is $\begin{bmatrix}1&1&1\\1&2&4\\1&c&c^2\end{bmatrix}$ invertible?
Check: replay the reduction of $\left[\begin{array}{c|c}A&I\end{array}\right]$ for your exercise
stepโ
row operationโ
left halfโ
๐ก Show solutionsโถ
1 A tidy route: $R_1\leftrightarrow R_2$; $R_2\to R_2-2R_1$; $R_2\to-R_2$; $R_1\to R_1-R_2$, $R_3\to R_3-R_2$; $R_1\to R_1+R_3$, $R_2\to R_2-2R_3$. Result: $$A^{-1}=\begin{bmatrix}2&-3&1\\-3&6&-2\\1&-2&1\end{bmatrix}.$$ (Any correct sequence of operations gives the same inverse โ it is unique.)
2 The $(1,1)$ entry is $0$, so start with $R_1\leftrightarrow R_2$; then $R_3\to R_3-4R_1$, $R_3\to R_3+3R_2$, $R_3\to\tfrac12R_3$, $R_1\to R_1-3R_3$, $R_2\to R_2-2R_3$: $$A^{-1}=\begin{bmatrix}-\tfrac92&7&-\tfrac32\\-2&4&-1\\\tfrac32&-2&\tfrac12\end{bmatrix}.$$ Check row 1 of $A$ with column 1: $0(-\tfrac92)+1(-2)+2(\tfrac32)=1$ โ.
4 Already upper triangular with $1$s on the diagonal: $R_1\to R_1-2R_2$, then $R_1\to R_1+5R_3$, $R_2\to R_2-4R_3$: $$A^{-1}=\begin{bmatrix}1&-2&5\\0&1&-4\\0&0&1\end{bmatrix}.$$
5 Scale each row: $A^{-1}=\begin{bmatrix}\tfrac12&0&0\\0&-1&0\\0&0&\tfrac15\end{bmatrix}$. A diagonal matrix is invertible exactly when every diagonal entry is non-zero, and then its inverse is diagonal with the reciprocals.
6 Clear below each pivot in turn: $R_2\to R_2-2R_1$; $R_3\to R_3-3R_2$; $R_4\to R_4-4R_3$ (applied to the right half as it stands at each step): $$A^{-1}=\begin{bmatrix}1&0&0&0\\-2&1&0&0\\6&-3&1&0\\-24&12&-4&1\end{bmatrix}.$$
7 $R_2\to R_2-R_1$, $R_3\to R_3-R_1$ give rows $(0,1,3)$ and $(0,c-1,c^2-1)$; then $R_3\to R_3-(c-1)R_2$ gives $(0,0,c^2-1-3(c-1))=(0,0,(c-1)(c-2))$. A third pivot exists iff $(c-1)(c-2)\ne0$: invertible exactly when $c\ne1$ and $c\ne2$ (for $c=1$ or $2$ two rows are equal).
III
Elementary matrices.
1 Which are elementary matrices? (a) $\begin{bmatrix}1&0\\0&-3\end{bmatrix}$ (b) $\begin{bmatrix}1&2\\0&1\end{bmatrix}$ (c) $\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}$ (d) $\begin{bmatrix}1&1\\1&0\end{bmatrix}$ (e) $\begin{bmatrix}2&0\\0&2\end{bmatrix}$ (f) $\begin{bmatrix}1&0&0\\0&1&0\\-4&0&1\end{bmatrix}$
2 Write down the $3\times3$ elementary matrices for $R_3\to R_3+4R_1$, $R_2\leftrightarrow R_3$ and $R_1\to-2R_1$, and their inverses.
3 Let $A=\begin{bmatrix}1&3\\2&8\end{bmatrix}$. Find elementary matrices $E_1,E_2,E_3$ with $E_3E_2E_1A=I$, and hence $A^{-1}$.
4 Write the matrix $A$ of part 3 as a product of elementary matrices.
5 A $2\times n$ matrix $B$ is obtained from $A$ by $R_1\leftrightarrow R_2$ followed by $R_2\to R_2+5R_1$. Find the single matrix $F$ with $B=FA$.
6 Compute $AE$ for $A=\begin{bmatrix}1&2\\3&4\end{bmatrix}$ and $E=\begin{bmatrix}1&0\\-2&1\end{bmatrix}$. What does multiplying by an elementary matrix on the right do?
๐ก Show solutionsโถ
1 (a) yes, $R_2\to-3R_2$; (b) yes, $R_1\to R_1+2R_2$; (c) yes, $R_1\leftrightarrow R_2$; (d) no โ it needs more than one operation on $I$; (e) no โ two scalings ($R_1\to2R_1$ and $R_2\to2R_2$); (f) yes, $R_3\to R_3-4R_1$.
2 $\begin{bmatrix}1&0&0\\0&1&0\\4&0&1\end{bmatrix}$ with inverse $\begin{bmatrix}1&0&0\\0&1&0\\-4&0&1\end{bmatrix}$; $\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix}$, its own inverse; $\begin{bmatrix}-2&0&0\\0&1&0\\0&0&1\end{bmatrix}$ with inverse $\begin{bmatrix}-\tfrac12&0&0\\0&1&0\\0&0&1\end{bmatrix}$.
3 $E_1=\begin{bmatrix}1&0\\-2&1\end{bmatrix}$ ($R_2\to R_2-2R_1$) gives $\begin{bmatrix}1&3\\0&2\end{bmatrix}$; $E_2=\begin{bmatrix}1&0\\0&\tfrac12\end{bmatrix}$ gives $\begin{bmatrix}1&3\\0&1\end{bmatrix}$; $E_3=\begin{bmatrix}1&-3\\0&1\end{bmatrix}$ gives $I$. Then $A^{-1}=E_3E_2E_1=\begin{bmatrix}4&-\tfrac32\\-1&\tfrac12\end{bmatrix}$ (check: $\tfrac12\begin{bmatrix}8&-3\\-2&1\end{bmatrix}$ by Theorem 2.6 โ).
4 $A=E_1^{-1}E_2^{-1}E_3^{-1}=\begin{bmatrix}1&0\\2&1\end{bmatrix}\begin{bmatrix}1&0\\0&2\end{bmatrix}\begin{bmatrix}1&3\\0&1\end{bmatrix}$. Check: the first two give $\begin{bmatrix}1&0\\2&2\end{bmatrix}$, and times the third, $\begin{bmatrix}1&3\\2&8\end{bmatrix}$ โ.
5 $F=E_bE_a$ with $E_a=\begin{bmatrix}0&1\\1&0\end{bmatrix}$ first and $E_b=\begin{bmatrix}1&0\\5&1\end{bmatrix}$ second: $F=\begin{bmatrix}1&0\\5&1\end{bmatrix}\begin{bmatrix}0&1\\1&0\end{bmatrix}=\begin{bmatrix}0&1\\1&5\end{bmatrix}$. (Apply the two operations to $I$ to check.)
6 $AE=\begin{bmatrix}1-4&2\\3-8&4\end{bmatrix}=\begin{bmatrix}-3&2\\-5&4\end{bmatrix}$: column 1 became column 1 $-\,2\times$ column 2. Right multiplication by an elementary matrix performs a column operation (because $AE=\left(E^{T}A^{T}\right)^{T}$).
IV
Properties, the Invertible Matrix Theorem, and applications. All matrices are $n\times n$.
1 Let $A$, $B$ be invertible. (a) Solve $AXB=C$ for $X$. (b) Simplify $\left(B^{-1}A\right)^{-1}B^{-1}$.
2 For $A=\begin{bmatrix}3&1\\5&2\end{bmatrix}$ verify that $\left(A^{T}\right)^{-1}=\left(A^{-1}\right)^{T}$.
3 Prove: if $A$ is invertible and $A^2=A$, then $A=I$.
4 Prove: if $A^3=O$, then $I-A$ is invertible with $(I-A)^{-1}=I+A+A^2$. Check it for $A=\begin{bmatrix}0&1&2\\0&0&3\\0&0&0\end{bmatrix}$.
5 True or false? (a) If $A\mathbf{x}=\mathbf{0}$ has a non-zero solution, then $A$ is singular. (b) If $AB=I$ for square $A$, $B$, then $BA=I$. (c) The sum of two invertible matrices is invertible. (d) A square matrix with a row of zeros is singular.
6Cryptography. Code letters as $A=1,\ B=2,\dots,Z=26$, split a message into pairs, and send each pair $\mathbf{p}$ as $K\mathbf{p}$ with key $K=\begin{bmatrix}3&5\\1&2\end{bmatrix}$. (a) Encode HI. (b) Decode the received vectors $(44,15)$ and $(100,36)$.
7Challenge. Let $A$ be a $2\times2$ matrix with integer entries. Prove that $A^{-1}$ exists and has integer entries if and only if $ad-bc=\pm1$.
๐ก Show solutionsโถ
1 (a) Multiply on the left by $A^{-1}$ and on the right by $B^{-1}$: $X=A^{-1}CB^{-1}$. (b) $\left(B^{-1}A\right)^{-1}=A^{-1}\left(B^{-1}\right)^{-1}=A^{-1}B$, so the expression is $A^{-1}BB^{-1}=A^{-1}$.
2 $A^{T}=\begin{bmatrix}3&5\\1&2\end{bmatrix}$ has $ad-bc=1$ and inverse $\begin{bmatrix}2&-5\\-1&3\end{bmatrix}$; also $A^{-1}=\begin{bmatrix}2&-1\\-5&3\end{bmatrix}$, whose transpose is $\begin{bmatrix}2&-5\\-1&3\end{bmatrix}$ โ.
3 Multiply $AA=A$ on the left by $A^{-1}$: $A=I$. (Without invertibility this fails: $\begin{bmatrix}1&0\\0&0\end{bmatrix}^2$ equals itself.)
4 $(I-A)(I+A+A^2)=I+A+A^2-A-A^2-A^3=I-A^3=I$, and the product in the other order is the same; by the Invertible Matrix Theorem one side suffices anyway. For the given $A$: $A^2=\begin{bmatrix}0&0&3\\0&0&0\\0&0&0\end{bmatrix}$, $A^3=O$, and $I+A+A^2=\begin{bmatrix}1&1&5\\0&1&3\\0&0&1\end{bmatrix}$; multiplying by $I-A=\begin{bmatrix}1&-1&-2\\0&1&-3\\0&0&1\end{bmatrix}$ gives $I$ โ.
5 (a) True, by (d) of Theorem 2.11. (b) True for square matrices, by (i)โ(a). (c) False: $I+(-I)=O$. (d) True: the echelon form has at most $n-1$ pivots, so (c) of Theorem 2.11 fails.
6 (a) HI $=(8,9)$: $K\mathbf{p}=(24+45,\ 8+18)=(69,26)$. (b) $ad-bc=1$, $K^{-1}=\begin{bmatrix}2&-5\\-1&3\end{bmatrix}$: $K^{-1}(44,15)=(88-75,\ -44+45)=(13,1)$ = MA and $K^{-1}(100,36)=(200-180,\ -100+108)=(20,8)$ = TH. The message is MATH.
7 Let $\Delta=ad-bc$. If $\Delta=\pm1$, Theorem 2.6 gives $A^{-1}=\pm\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$, with integer entries. Conversely, if $A^{-1}=\tfrac1\Delta\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$ has integer entries, then $\Delta$ divides each of $a,b,c,d$, so $\Delta^2$ divides $ad-bc=\Delta$; hence $\Delta$ divides $1$, i.e. $\Delta=\pm1$. (This is why the key in part 6 was chosen with $ad-bc=1$.)
๐ฌ ResearchโTeaching NexusResearch-tutored ยท optional, about 30 minutes
Research question. How can a matrix lock and unlock a message โ and why do practical matrix codes work with remainders modulo $26$ instead of ordinary arithmetic?
Why it matters. In 1929 the mathematician Lester Hill proposed encrypting blocks of letters by multiplying them by an invertible key matrix. Modern ciphers such as AES (used in every secure web connection and mobile payment) still contain a step that multiplies blocks of data by a fixed invertible matrix, over a finite number system, to spread each input symbol across many output symbols. Decryption is possible only because that matrix has an inverse.
What to do.
With the key $K=\begin{bmatrix}3&5\\1&2\end{bmatrix}$ of Exercise IV.6, encode a short word of your own (pad with X if it has an odd number of letters).
Explain why a key such as $\begin{bmatrix}2&4\\1&2\end{bmatrix}$ is useless. Find two different message pairs that it encodes to the same vector.
Ordinary encoding makes the numbers grow (HI became $(69,26)$), which leaks information. Read about the Hill cipher, where every entry is reduced modulo $26$. Encode HI with $K$ modulo $26$, and decode it using $K^{-1}=\begin{bmatrix}2&-5\\-1&3\end{bmatrix}$ modulo $26$.
Why does $ad-bc=\pm1$ (Exercise IV.7) guarantee that decoding works with whole numbers? Which condition on $ad-bc$ is needed modulo $26$?
Tools: Paper and pencil; optionally a spreadsheet with MMULT and MOD.
Hand in: Your encoded word, the two colliding messages for the singular key, the modulo-$26$ encoding and decoding of HI, and three sentences on why invertibility is essential for any encryption step.
Going further. A Hill cipher can be broken if an attacker knows a few plaintextโciphertext pairs: stacking them gives $KP=C$, so $K=CP^{-1}$. Try it with two known pairs, and look up the "MixColumns" step of AES.
Instructor note: the singular key sends $(1,1)$ and $(3,0)$ both to $(6,3)$ (any two pairs differing by a multiple of $(2,-1)$ collide). HI $=(8,9)\mapsto(69,26)\equiv(17,0)\pmod{26}$, i.e. QZ with Z for $0$; decoding $(17,0)$: $(34,-17)\equiv(8,9)$ โ. Modulo $26$ the key must have $ad-bc$ with no common factor with $26$ (odd and not a multiple of $13$).
๐งช Self-check quiz
0/5 correct
Q1. The inverse of $\begin{bmatrix}2&1\\5&3\end{bmatrix}$ is
Q2. If $A$ and $B$ are invertible $n\times n$ matrices, then $(AB)^{-1}=$
Q3. $E=\begin{bmatrix}1&0\\3&1\end{bmatrix}$ performs $R_2\to R_2+3R_1$. Its inverse is
Q4. For a square matrix $A$, which statement does not guarantee that $A$ is invertible?
Q5. While row reducing $\left[\begin{array}{c|c}A&I\end{array}\right]$ a row of zeros appears in the left half. Then