Multiplication and Inverse Matrices

The standard rule: row times column

Strang has been multiplying matrices for two lectures already, but it’s “certainly time to discuss the rules.” The interesting part, he says, is the many ways you can do it — they all give the same answer, and they’re all important.

Start with the way everyone learns first. Suppose $A$ times $B$ gives $C$. The entry of $C$ in row $i$, column $j$ — always row number first, then column number — is written $c_{ij}$. To make it concrete, take $c_{34}$: it comes from row 3 of $A$ dotted with column 4 of $B$. Walk along the row and down the column, multiplying and accumulating:

$$c_{34} = a_{31}b_{14} + a_{32}b_{24} + \cdots = \sum_{k=1}^{n} a_{3k}\,b_{k4}$$

The first entry of row 3 is $a_{31}$; the first entry at the top of column 4 is $b_{14}$; the running index $k$ marches together along the row and down the column. Most of the course uses whole vectors, Strang admits — he very seldom gets down to individual entries — “but here we’d better do it.”

When is the multiplication even allowed? Let $A$ be $m \times n$ ($m$ rows, $n$ columns). The number of rows of $B$ — the entries we meet coming down a column — has to match the $n$ entries going across a row of $A$. So $B$ must be $n \times p$, and the result $C$ is $m \times p$: it inherits its $m$ rows from $A$ and its $p$ columns from $B$. That’s $mp$ little numbers, each one a row-times-column dot product.

Second and third ways: whole columns, whole rows

Now the same calculation seen with whole columns. Strang builds on what we already know: how to multiply a matrix by one column. So think of $B$ as $p$ columns “just resting next to each other.” Then

$$A\,\begin{bmatrix} \mathbf{b}_1 & \mathbf{b}_2 & \cdots & \mathbf{b}_p \end{bmatrix} = \begin{bmatrix} A\mathbf{b}_1 & A\mathbf{b}_2 & \cdots & A\mathbf{b}_p \end{bmatrix}$$

$A$ times the first column of $B$ is the first column of $C$ — none of the other columns enter that part of the answer. And what does that tell us? Since $A$ times a vector is a combination of the columns of $A$:

The third way is that row statement: a row of $A$ multiplies all of $B$ and produces a row of the product, taking a combination of the rows of $B$ as it goes. In the answer $C$, you can see where the pieces come from — its columns come from the columns of $A$, its rows come from the rows of $B$.

Fourth way: columns times rows

A row times a column gave a number. So what’s left? A column times a row. A column of $A$ is $m \times 1$; a row of $B$ is $1 \times p$. The inner sizes match — they have length one — so the product is legal, and it’s not petite at all: it’s a full $m \times p$ matrix.

The fourth way, then: $AB$ is a sum of (columns of $A$) times (rows of $B$) — first column times first row, plus second column times second row, and so on. His example:

$$\begin{bmatrix} 2 & 7 \\ 3 & 8 \\ 4 & 9 \end{bmatrix} \begin{bmatrix} 1 & 6 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 2 \\ 3 \\ 4 \end{bmatrix}\begin{bmatrix} 1 & 6 \end{bmatrix} + \begin{bmatrix} 7 \\ 8 \\ 9 \end{bmatrix}\begin{bmatrix} 0 & 0 \end{bmatrix} = \begin{bmatrix} 2 & 12 \\ 3 & 18 \\ 4 & 24 \end{bmatrix}$$

The second piece is all zeros, so we’re back to the special matrix above.

Fifth way: blocks

One more, useful enough that Strang won’t skip it: block multiplication. Cut $A$ and $B$ into blocks whose sizes match properly — say both are $20 \times 20$, chopped into four $10 \times 10$ blocks:

$$\begin{bmatrix} A_1 & A_2 \\ A_3 & A_4 \end{bmatrix} \begin{bmatrix} B_1 & B_2 \\ B_3 & B_4 \end{bmatrix} = \begin{bmatrix} A_1 B_1 + A_2 B_3 & \;\cdots \\ \cdots & \cdots \end{bmatrix}$$

The top-left block of the answer is $A_1 B_1 + A_2 B_3$ — block rows times block columns, exactly as if the blocks were numbers. “Nobody, I think, not even Gauss could see instantly that it works,” but check it through and all five ways are doing the same multiplications, just organized differently.

Inverses: when a matrix has none

On to the second topic. Take a square matrix $A$. It may or may not have an inverse — and whether it does is “the most important question you can ask about the matrix.”

Strang hates to be negative, but the singular case comes first. His example:

$$A = \begin{bmatrix} 1 & 3 \\ 2 & 6 \end{bmatrix}$$

Why is there no inverse? Several ways to see it. If you know determinants (which you’re not supposed to yet), it’s zero. Better, think columns: if $A$ times some matrix gave $I$, the columns of $I$ would be combinations of the columns of $A$. But both columns of $A$ lie on the same line — every combination stays on that line, and $(1, 0)$ is not on it. No way to reach the identity.

Then the reason Strang likes best. A matrix has no inverse exactly when there is a nonzero vector $\mathbf{x}$ with $A\mathbf{x} = \mathbf{0}$. Here, take $\mathbf{x} = (3, -1)$: three of column one minus one of column two is the zero column. (Picking $\mathbf{x} = \mathbf{0}$ is no achievement — that always works. It’s the nonzero solution that matters.)

Gauss-Jordan: finding the inverse

Back to the positive side. Change the $6$ to a $7$ — “seven is a lucky number” —

$$A = \begin{bmatrix} 1 & 3 \\ 2 & 7 \end{bmatrix}$$

Determinant fans see it isn’t zero; column fans see two columns pointing in different directions, so combinations reach anything. Now find $A^{-1} = \begin{bmatrix} a & c \\ b & d \end{bmatrix}$: four numbers, from $A A^{-1} = I$. Read that equation by columns. The first column satisfies

$$A \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \qquad A \begin{bmatrix} c \\ d \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$$

In general: $A$ times column $j$ of $A^{-1}$ equals column $j$ of the identity. Finding the inverse means solving $n$ systems with the same matrix $A$ and the columns of $I$ as right-hand sides. We’re back to Gauss — and this is where Jordan comes in. Jordan’s idea, as Strang tells it: solve them all together. Instead of tacking on one extra column as the augmented matrix, tack on the whole identity:

Why the identity turns into the inverse

The mechanics are one thing; why did $A^{-1}$ show up? Every elimination step is multiplication by an elimination matrix $E$ — that’s what last lecture established. Here there were just two: one that subtracted $2\times$ row 1 from row 2, one that subtracted $3\times$ row 2 from row 1. Call their product — the overall elimination matrix — $E$. Then the whole process is

$$E \left[\, A \;\middle|\; I \,\right] = \left[\, EA \;\middle|\; EI \,\right] = \left[\, I \;\middle|\; E \,\right]$$

Start with the double-length matrix $[\,A \mid I\,]$, eliminate until the first half is down to $I$, and the second half must be $A^{-1}$. That’s Gauss-Jordan: solving $n$ equations at once, with the $n$ columns of the inverse coming up together.

Problems

Practice all five multiplications and the Gauss-Jordan mechanics — the lecture’s methods are everything you need.

Problem 3.1 Entry formula & column way

Let

$$A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, \qquad B = \begin{bmatrix} 5 & 1 \\ 2 & 0 \end{bmatrix}.$$

Compute the entry $c_{21}$ of $C = AB$ from the summation formula, then find all of $C$ column by column ($A$ times each column of $B$).

Show solution

Entry formula: $c_{21} = \sum_k a_{2k} b_{k1} = a_{21}b_{11} + a_{22}b_{21} = (3)(5) + (4)(2) = 23$.

By columns: $A \begin{bmatrix} 5 \\ 2 \end{bmatrix} = 5\begin{bmatrix} 1 \\ 3 \end{bmatrix} + 2\begin{bmatrix} 2 \\ 4 \end{bmatrix} = \begin{bmatrix} 9 \\ 23 \end{bmatrix}$ and $A \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \end{bmatrix}$.

So $C = \begin{bmatrix} 9 & 1 \\ 23 & 3 \end{bmatrix}$ — and the $(2,1)$ entry agrees: $23$.

Problem 3.2 Column times row

Compute the column-times-row product

$$\begin{bmatrix} 1 \\ 2 \\ 5 \end{bmatrix} \begin{bmatrix} 2 & 4 \end{bmatrix}$$

and describe its row space and its column space, in the lecture’s language.

Show solution

$$\begin{bmatrix} 1 \\ 2 \\ 5 \end{bmatrix} \begin{bmatrix} 2 & 4 \end{bmatrix} = \begin{bmatrix} 2 & 4 \\ 4 & 8 \\ 10 & 20 \end{bmatrix}$$

Every row is a multiple of $(2, 4)$, so the row space is the line through $(2, 4)$. Every column is a multiple of $(1, 2, 5)$, so the column space is the line through $(1, 2, 5)$. A minimal matrix: all its rows on one line, all its columns on another.

Problem 3.3 Recognizing the singular case

Show that

$$A = \begin{bmatrix} 2 & 4 \\ 3 & 6 \end{bmatrix}$$

has no inverse, by finding a nonzero vector $\mathbf{x}$ with $A\mathbf{x} = \mathbf{0}$ and running the lecture’s argument.

Show solution

Column two is twice column one, so take $\mathbf{x} = \begin{bmatrix} 2 \\ -1 \end{bmatrix}$: then $2\begin{bmatrix} 2 \\ 3 \end{bmatrix} - 1\begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$, and $\mathbf{x} \neq \mathbf{0}$.

Now suppose $A^{-1}$ existed. Multiply $A\mathbf{x} = \mathbf{0}$ on the left by $A^{-1}$: the left side is $A^{-1}A\mathbf{x} = \mathbf{x}$, the right side is $A^{-1}\mathbf{0} = \mathbf{0}$. So $\mathbf{x} = \mathbf{0}$ — but $\mathbf{x} = (2, -1)$ is not zero. Contradiction: no $A^{-1}$ exists. (Column picture: both columns lie on one line, so no combination reaches $(1, 0)$, and the identity is unreachable.)

Problem 3.4 Gauss-Jordan by hand

Use Gauss-Jordan elimination on the long matrix $[\,A \mid I\,]$ to invert

$$A = \begin{bmatrix} 1 & 2 \\ 3 & 7 \end{bmatrix},$$

then check your answer by multiplying.

Show solution

$$\left[\begin{array}{cc|cc} 1 & 2 & 1 & 0 \\ 3 & 7 & 0 & 1 \end{array}\right] \;\xrightarrow{R_2 - 3R_1}\; \left[\begin{array}{cc|cc} 1 & 2 & 1 & 0 \\ 0 & 1 & -3 & 1 \end{array}\right] \;\xrightarrow{R_1 - 2R_2}\; \left[\begin{array}{cc|cc} 1 & 0 & 7 & -2 \\ 0 & 1 & -3 & 1 \end{array}\right]$$

So $A^{-1} = \begin{bmatrix} 7 & -2 \\ -3 & 1 \end{bmatrix}$. Check:

$$\begin{bmatrix} 7 & -2 \\ -3 & 1 \end{bmatrix}\begin{bmatrix} 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} \checkmark$$

Problem 3.5 Sum of columns times rows

Compute

$$\begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} \begin{bmatrix} 7 & 8 \\ 0 & 1 \end{bmatrix}$$

the fourth way — as (column 1)(row 1) + (column 2)(row 2) — and confirm one entry with the standard row-times-column rule.

Show solution

$$\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}\begin{bmatrix} 7 & 8 \end{bmatrix} + \begin{bmatrix} 4 \\ 5 \\ 6 \end{bmatrix}\begin{bmatrix} 0 & 1 \end{bmatrix} = \begin{bmatrix} 7 & 8 \\ 14 & 16 \\ 21 & 24 \end{bmatrix} + \begin{bmatrix} 0 & 4 \\ 0 & 5 \\ 0 & 6 \end{bmatrix} = \begin{bmatrix} 7 & 12 \\ 14 & 21 \\ 21 & 30 \end{bmatrix}$$

Standard check of the $(2,2)$ entry: row 2 of the first matrix dot column 2 of the second, $(2)(8) + (5)(1) = 21$. Agrees.