Left and Right Inverses; Pseudoinverse

Four possibilities for an m×n matrix of rank r

This lecture is the first step of the final review, and Strang organizes it around “the most fundamental picture in linear algebra” — the four subspaces. For an $m \times n$ matrix of rank $r$: the row space and null space are orthogonal complements in $\mathbb{R}^n$ (dimensions $r$ and $n-r$), and the column space and null space of $A^T$ are orthogonal complements in $\mathbb{R}^m$ (dimensions $r$ and $m-r$). “Nobody could forget that picture, right? When you’re my age, even, you’ll remember the row space and the null space.”

The question of the day: what kinds of inverses can $A$ have? There are four cases, and each one is a statement about the ranks:

1. Two-sided inverse: $r = m = n$. Square, full rank — the nice case chapter two was all about. One matrix $A^{-1}$ produces the identity from either side.
2. Left inverse: $r = n < m$. Full column rank — independent columns, probably more rows than columns.
3. Right inverse: $r = m < n$. Full row rank — independent rows, more columns than rows.
4. Pseudoinverse: $r$ smaller than both $m$ and $n$. The completely general case, where both null spaces are alive — and it’s those null spaces “that are screwing up inverses.”

A rectangular matrix can never have a two-sided inverse: if $m \neq n$, then either $A$ or $A^T$ has free variables, so one of them has a genuine null space. And “if a matrix takes a vector to zero, well, there’s no way an inverse can, like, bring it back to life.”

Full column rank: the left inverse

Suppose $r = n$: the $n$ columns are independent. Then the null space of $A$ contains only the zero vector, and the row space is all of $\mathbb{R}^n$. Consequence for equations: $A\mathbf{x} = \mathbf{b}$ has zero or one solutions. If a particular solution exists, it is the solution — there’s nothing in the null space to add on. But since the rows are probably not independent, elimination can produce rows where zero must equal something nonzero, so for some right-hand sides there is no solution at all.

Now the key combination of the course: $A^T A$. If the rank of $A$ is $n$, then $A^T A$ — an $n \times n$ symmetric matrix — also has rank $n$. “That’s the beautiful fact.” So $A^T A$ is invertible, and that hands us a one-sided inverse of $A$ itself:

Why does it work? Put the parentheses in the right place: $\big[(A^T A)^{-1} A^T\big] A = (A^T A)^{-1}(A^T A) = I$. This was “the totally crucial case for least squares,” because the central least-squares equation $A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$ has $A^T A$ as its coefficient matrix — and with full column rank, that matrix is invertible and we’re go.

Note what’s good and what’s bad in this case: $A^T A$ is invertible, but $A A^T$ is not — the bad product for this case.

Full row rank: the right inverse

Now the mirror image, $r = m$: the $m$ rows are independent, the columns are not. The null space of $A^T$ contains only zero — no combination of the rows gives the zero row. So elimination never produces a zero row, we never hit the “zero equals one” problem, and $A\mathbf{x} = \mathbf{b}$ always has a solution — but too many. There are $n$ variables and $m$ pivots, hence $n - m$ free variables: infinitely many solutions.

Everything flips. Now $A A^T$ is the good, invertible matrix ($m \times m$, full rank), and the right inverse comes out completely parallel to the left one:

There are other left inverses and other right inverses — these formulas are just “our favorite” ones. (The pseudoinverse will turn out to be the minimal choice, with no extra stuff.)

Put the inverse on the wrong side: a projection

Before leaving the one-sided cases, Strang asks the question you should ask: the left inverse gives $I$ when it multiplies from the left — but what if we multiply in the other order? Compute

$$A\, A^{-1}_{\text{left}} = A (A^T A)^{-1} A^T$$

Everybody in the room ought to recognize that matrix: it’s $P$, the projection onto the column space. “It’s trying to be the identity matrix, right? A projection matrix tries to be the identity matrix, but you’ve given it an impossible job.” It is the identity where it can be — on the column space — and zero elsewhere.

Same story on the other side. Put the right inverse on the left:

$$A^{-1}_{\text{right}}\, A = A^T (A A^T)^{-1} A$$

That’s another projection — the same shape of formula with $A$ and $A^T$ reversed — this time the projection onto the row space. Again it’s trying to be the identity, “but there’s only so much the matrix can do.”

The pseudoinverse: A is perfect from row space to column space

Now the general case: rank $r$ smaller than both $m$ and $n$. What’s a reasonable inverse? Look at the picture. Take a vector $\mathbf{x}$ in the row space and multiply by $A$. Where is $A\mathbf{x}$? Always in the column space — $A\mathbf{x}$ is a combination of the columns. Almost every vector in $\mathbb{R}^n$ has a row space component and a null space component, and $A$ kills the null space component. But restrict attention to the row space alone, and something remarkable happens: the map from row space to column space is one-to-one. We’ve got a chance, because both spaces have the same dimension $r$.

Strang calls the proof “a perfect question on a final exam,” because it’s exactly what chapters three and four teach. Suppose the conclusion failed: $A\mathbf{x} = A\mathbf{y}$, which is the same as $A(\mathbf{x} - \mathbf{y}) = \mathbf{0}$. Then $\mathbf{x} - \mathbf{y}$ is in the null space. But $\mathbf{x}$ and $\mathbf{y}$ are both in the row space, and the row space is a vector space, so $\mathbf{x} - \mathbf{y}$ is also in the row space. A vector in both the null space and the row space — orthogonal complements — must be the zero vector. So $\mathbf{x} = \mathbf{y}$: start from two different vectors, get two different vectors.

Why does anyone need this? Statisticians “discovered, oh boy, this is the thing that we needed all our lives.” They live on least squares — linear regression — and least squares only works when $A$ has full column rank. But experiments get repeated; measurements fail to be independent; and then $A^T A$ goes singular and the whole machine breaks. The pseudoinverse “just arrived at the right moment, and it’s the right quantity.”

Computing A⁺ from the SVD

How do you actually find $A^+$? Start from the Singular Value Decomposition,

$$A = U \Sigma V^T$$

with $U$ and $V$ orthogonal and $\Sigma$ diagonal. The diagonal matrix $\Sigma$ is “the best example, the simplest example we could ever have of our general setup”: $m \times n$, rank $r$, with $\sigma_1, \ldots, \sigma_r$ on the diagonal and zeroes everywhere else.

Now assemble $A^+$ from the factors. In $A = U\Sigma V^T$, the orthogonal matrices are perfectly invertible — the inverse of $V^T$ is $V$, the inverse of $U$ is $U^T$. All the trouble, all the null space, lives in $\Sigma$, and we just found its pseudoinverse. So:

$$A^+ = V\, \Sigma^+\, U^T$$

The beauty of the SVD here is that “it puts all the problems into this diagonal matrix where it’s clear what to do.” One could pad $\Sigma^+$ with extra entries that multiply the zero blocks and change nothing essential, but the good pseudoinverse is the one with no extra stuff — the minimal matrix that gives the best result, $\Sigma\Sigma^+$ equal to $r$ ones.

One administrative note Strang makes twice: the pseudoinverse lives at the end of chapter seven and won’t appear on the final. But everything it’s built from — rank, free variables, the four subspaces, projections, orthogonality of row space and null space — “is all what the course was about, chapters one, two, three, four.”

Problems

Work these before revealing the solutions — the lecture’s formulas and the four-subspace picture are all you need.

Problem 32.1 Computing a left inverse

The matrix

$$A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix}$$

has full column rank ($r = n = 2$, $m = 3$). Find its left inverse $A^{-1}_{\text{left}} = (A^TA)^{-1}A^T$ and verify that $A^{-1}_{\text{left}}\,A = I$.

Show solution

First the good matrix:

$$A^T A = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}, \qquad (A^TA)^{-1} = \frac{1}{3}\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}$$

Then

$$A^{-1}_{\text{left}} = \frac{1}{3}\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} = \frac{1}{3}\begin{bmatrix} 2 & 1 & -1 \\ -1 & 1 & 2 \end{bmatrix}$$

Check:

$$A^{-1}_{\text{left}}\,A = \frac{1}{3}\begin{bmatrix} 2 & 1 & -1 \\ -1 & 1 & 2 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix} = \frac{1}{3}\begin{bmatrix} 3 & 0 \\ 0 & 3 \end{bmatrix} = I$$

A $2 \times 3$ matrix times a $3 \times 2$ matrix giving the $2 \times 2$ identity — exactly the left-inverse pattern.

Problem 32.2 Right inverse and the wrong-order product

The matrix $A = \begin{bmatrix} 1 & 2 & 2 \end{bmatrix}$ has full row rank ($r = m = 1$, $n = 3$). Find its right inverse $A^{-1}_{\text{right}} = A^T(AA^T)^{-1}$, verify $A\,A^{-1}_{\text{right}} = I$, and identify the matrix $A^{-1}_{\text{right}}\,A$.

Show solution

The good matrix is $AA^T = 1 + 4 + 4 = 9$, so $(AA^T)^{-1} = \frac{1}{9}$ and

$$A^{-1}_{\text{right}} = \frac{1}{9}\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}$$

Check: $A\,A^{-1}_{\text{right}} = \frac{1}{9}(1 + 4 + 4) = 1 = I$ (the $1\times 1$ identity).

In the wrong order:

$$A^{-1}_{\text{right}}\,A = \frac{1}{9}\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}\begin{bmatrix} 1 & 2 & 2 \end{bmatrix} = \frac{1}{9}\begin{bmatrix} 1 & 2 & 2 \\ 2 & 4 & 4 \\ 2 & 4 & 4 \end{bmatrix}$$

This is $A^T(AA^T)^{-1}A$ — the projection onto the row space of $A$, the line through $(1, 2, 2)$ in $\mathbb{R}^3$. It’s symmetric and squares to itself, but it is not the identity: it can’t be, because $A$ has a two-dimensional null space.

Problem 32.3 The final-exam proof

Let $A$ be any $m \times n$ matrix, and suppose $\mathbf{x}$ and $\mathbf{y}$ are two vectors in the row space of $A$ with $A\mathbf{x} = A\mathbf{y}$. Prove that $\mathbf{x} = \mathbf{y}$. Which two facts about the four subspaces does the proof use?

Show solution

From $A\mathbf{x} = A\mathbf{y}$ we get $A(\mathbf{x} - \mathbf{y}) = \mathbf{0}$, so $\mathbf{x} - \mathbf{y}$ lies in the null space of $A$.

Since $\mathbf{x}$ and $\mathbf{y}$ are both in the row space, and the row space is a subspace (closed under subtraction), $\mathbf{x} - \mathbf{y}$ also lies in the row space.

The row space and null space are orthogonal complements in $\mathbb{R}^n$, so their intersection is the zero vector alone: a vector orthogonal to itself has $\|\mathbf{x}-\mathbf{y}\|^2 = 0$. Therefore $\mathbf{x} - \mathbf{y} = \mathbf{0}$, i.e. $\mathbf{x} = \mathbf{y}$.

The two facts used: subspaces are closed under linear combinations, and the row space is the orthogonal complement of the null space. This is exactly why $A$ is a one-to-one (invertible) map from row space to column space — the fact that defines the pseudoinverse.

Problem 32.4 Pseudoinverse of a diagonal matrix

Find the pseudoinverse of

$$\Sigma = \begin{bmatrix} 5 & 0 \\ 0 & 0 \\ 0 & 0 \end{bmatrix}$$

and compute both products $\Sigma\,\Sigma^+$ and $\Sigma^+\,\Sigma$. What is each product, and what space does each project onto?

Show solution

Here $m = 3$, $n = 2$, $r = 1$. Invert the nonzero singular value and take the transposed shape:

$$\Sigma^+ = \begin{bmatrix} \tfrac{1}{5} & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} \quad (2 \times 3)$$

Then

$$\Sigma\,\Sigma^+ = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} \ (3 \times 3), \qquad \Sigma^+\,\Sigma = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} \ (2 \times 2)$$

Neither is the identity — each has $r = 1$ ones and then zeroes. $\Sigma\Sigma^+$ is the projection onto the column space of $\Sigma$ (the first coordinate axis in $\mathbb{R}^3$), and $\Sigma^+\Sigma$ is the projection onto the row space (the first coordinate axis in $\mathbb{R}^2$). That is the best any pseudoinverse can do.

Problem 32.5 Pseudoinverse via the SVD

The rank-one matrix

$$A = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$$

has SVD $A = U\Sigma V^T$ with $\sigma_1 = 2$ and $\mathbf{u}_1 = \mathbf{v}_1 = \frac{1}{\sqrt{2}}(1, 1)$. Use $A^+ = V\Sigma^+U^T$ to find $A^+$, and check that $AA^+$ is the projection onto the column space.

Show solution

Since only one singular value is nonzero, $\Sigma^+$ has the single entry $\frac{1}{2}$, and

$$A^+ = \mathbf{v}_1 \cdot \frac{1}{\sigma_1} \cdot \mathbf{u}_1^T = \frac{1}{2} \cdot \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \end{bmatrix} \cdot \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \end{bmatrix} = \frac{1}{4}\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$$

So $A^+ = \frac{1}{4}A$. Check the product:

$$A A^+ = \frac{1}{4}\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} = \frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$$

That is exactly $\mathbf{u}_1\mathbf{u}_1^T$, the projection onto the line through $(1,1)$ — the column space of $A$. (By symmetry $A^+A$ is the same matrix here, projecting onto the row space, which is the same line.) Note $A$ itself is singular, with no left or right inverse — but its pseudoinverse exists and does the best an inverse can do.