Transposes, Permutations, Vector Spaces

Finishing elimination: PA = LU

This lecture completes the chapter: two loose ends from last time — permutations and transposes — and then, as Strang puts it, “the beginning of real linear algebra”: vector spaces.

First, permutations. A permutation matrix $P$ executes row exchanges. We may have a perfectly good invertible matrix $A$, but during elimination a zero shows up in a pivot position — and then we must reach below and swap in a row with a proper pivot, maybe more than once. The clean factorization $A = LU$ — ones on the diagonal of $L$, multipliers below; zeros below the diagonal of $U$ — quietly assumed no exchanges were ever needed. How do we account for them?

A moment of reality: a human checks whether the pivot is zero, but Matlab checks whether it is big enough, because pivots close to zero are numerically bad. Matlab does row exchanges that algebra doesn’t require — accuracy requires them. We’re doing algebra, so we exchange only when we have to.

Permutation matrices: the inverse is the transpose

What is $P$, exactly? A permutation matrix is the identity matrix with reordered rows — where “reordered” includes the do-nothing reordering, so the identity itself counts. For $n \times n$ matrices there are

$$n! = n(n-1)(n-2)\cdots(3)(2)(1)$$

of them — that counts all the possible reorderings of $n$ rows. So there are $24$ permutations of size $4 \times 4$, and $5! = 120$ of size $5 \times 5$ — listing those “would be not so much fun.” With four rows the possibilities get interesting: you might exchange all four in one big cycle, one to two, two to three, three to four, four to one.

Every permutation matrix is invertible — we can always bring the rows back to normal order — and the matrix that undoes $P$ is simply its transpose:

$$P^{\mathsf{T}}P = I, \qquad \text{that is,} \qquad P^{-1} = P^{\mathsf{T}}.$$

Multiply a permutation by its transpose and the ones hit the ones, producing the identity.

Transposes and symmetric matrices

Strang realizes he hasn’t actually transposed a matrix on the board yet, so he’d better do it. Take a rectangular matrix, $3 \times 2$, and flip it across its main diagonal:

$$\begin{bmatrix} 1 & 3 \\ 2 & 3 \\ 4 & 1 \end{bmatrix}^{\mathsf{T}} = \begin{bmatrix} 1 & 2 & 4 \\ 3 & 3 & 1 \end{bmatrix}$$

Three rows and two columns become two rows and three columns — “short and wider.” Each column becomes a row, each row becomes a column. In symbols:

Now the best matrices, the ones that show up in a lot of applications: symmetric matrices, the ones that transposing doesn’t change — $A^{\mathsf{T}} = A$. For example,

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

Whatever sits above the diagonal — the $1$, the $7$, the $9$ — had better sit in the mirror position below; transpose it and you get the same matrix back. Where the transpose gave the inverse was highly important but not simple to see — this one is totally simple to see.

Where do symmetric matrices come from? Our rectangular matrix above is absolutely far from symmetric — its transpose isn’t even the same shape. But here’s a way to manufacture symmetry out of it. Call the rectangular matrix $R$; then multiply.

Vector spaces: what the word “space” demands

Now the lecturer takes a breath, because chapter three begins: vector spaces and subspaces. The main things we do with vectors are add them and multiply them by numbers (scalars): $\mathbf{v} + \mathbf{w}$ and $3\mathbf{v}$. Those two operations, combined, give linear combinations — and they are what vectors are for.

The first examples: $\mathbb{R}^2$ is all two-dimensional real column vectors, such as $\begin{bmatrix} 3 \\ 2 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} \pi \\ e \end{bmatrix}$ — the whole $xy$-plane. (“I never drew $(\pi, e)$ before.”) Then $\mathbb{R}^3$, all vectors with three real components — note that $(3, 2, 0)$ lives in $\mathbb{R}^3$, not $\mathbb{R}^2$: one component happens to be zero, but it has three components. And the big example, $\mathbb{R}^n$: all column vectors with $n$ real components. (Complex numbers come much later.)

Why is the zero vector “the most important” one? Try removing it — the $xy$-plane with a puncture at the origin. That would be awful: multiplying $(3, 2)$ by the scalar zero must land in the space, and adding $(3, 2)$ to its opposite $(-3, -2)$ lands there too. Every vector space contains the zero vector.

And here’s a set that is not a vector space: the quarter of the plane with both components nonnegative. Adding is safe — $(3,2)$ plus $(5,6)$ stays in the quarter — but there’s a heck of a problem with scalars: multiply $(3, 2)$ by $-5$ and you’re way outside. The set is not closed under multiplication by all real numbers — closed is the right word — so it’s not a vector space.

Subspaces

Can a vector space live inside $\mathbb{R}^2$ — following all the rules, but not needing the whole plane? Yes: a subspace. Suppose a subspace of $\mathbb{R}^2$ contains one nonzero vector. Then it must contain twice that vector, half of it, minus a half of it, zero times it — every multiple. One vector forces the whole line through the origin. Addition then checks out: something on the line plus something else on the line is still on the line.

Not just any line, though. A dashed line that misses the origin fails immediately: multiply any of its vectors by zero and you land at the origin, off the line. Every subspace must contain the zero vector.

So we can list all the subspaces of $\mathbb{R}^2$:

1. All of $\mathbb{R}^2$ — the whole space counts as a subspace of itself.
2. Any line through the zero vector, infinitely far in both directions. (It looks a lot like $\mathbb{R}^1$, but it is not $\mathbb{R}^1$ — its vectors have two components.)
3. The zero vector alone — Strang calls this subspace $Z$. It’s “too dumb to tell you” why it works: add zero to itself, still there; multiply by seventeen, still there. The littlest subspace.

For $\mathbb{R}^3$ the list is: all of $\mathbb{R}^3$ at one extreme, a plane through the origin, a line through the origin, and the zero vector alone at the bottom.

The column space: a subspace built from a matrix

Now the reality — where do subspaces come from? They come out of matrices. Take

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

The two columns are vectors in $\mathbb{R}^3$, and we want them in our subspace. But two columns alone are not a subspace — what else must be there? Their multiples: $(0,0,0)$ has to be in. Their sum: $(4, 5, 5)$ has to be in. One of the first plus three of the second. All the linear combinations — multiply each column by a number and add, the two operations of linear algebra. Include all the results, and the job is done: it’s guaranteed to be a subspace.

Geometrically: draw the column $(1, 2, 4)$ somewhere in 3-space, draw $(3, 3, 1)$ somewhere else. All combinations fill out the whole line through each — and everything in between, because we may add something from one line to something from the other. We get a plane through the origin. More than a line, less than all of $\mathbb{R}^3$. That’s the picture you have to see.

This is the central idea of the lecture — got a few vectors, not satisfied with a few vectors, we want a space of vectors — and it’s linear algebra at a higher level. Next lecture opens with the question this sets up: what does $A\mathbf{x} = \mathbf{b}$ mean in the language of column spaces, and what other subspaces hide in $A$?

Problems

Work these with the lecture’s tools: the transpose rules, the closure test, and the column-space construction.

Problem 5.1 Permutations and PA = LU

Elimination on

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

hits a zero in the first pivot position. Write down a permutation matrix $P$ that fixes this by exchanging rows 1 and 2, compute $PA$, and verify that $P^{\mathsf{T}}P = I$.

Show solution

The permutation that exchanges rows 1 and 2 is the identity with those rows swapped:

$$P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \qquad PA = \begin{bmatrix} 2 & 4 & 1 \\ 0 & 1 & 3 \\ 1 & 1 & 1 \end{bmatrix}$$

Now the first pivot is $2 \neq 0$ and elimination can proceed to $LU$.

For the check: $P$ is its own transpose here (swapping rows 1 and 2 of $I$ gives a symmetric matrix), and

$$P^{\mathsf{T}}P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = I.$$

The ones hit the ones, so $P^{-1} = P^{\mathsf{T}}$.

Problem 5.2 Building symmetry

Let

$$R = \begin{bmatrix} 2 & 1 & 0 \\ 1 & 0 & 3 \end{bmatrix}.$$

Write down $R^{\mathsf{T}}$, compute $R^{\mathsf{T}}R$, and confirm it is symmetric. Then explain in one line, using the transpose rule for products, why $R\,R^{\mathsf{T}}$ is also symmetric (no computation needed).

Show solution

Transposing swaps rows and columns:

$$R^{\mathsf{T}} = \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ 0 & 3 \end{bmatrix}, \qquad R^{\mathsf{T}}R = \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ 0 & 3 \end{bmatrix}\begin{bmatrix} 2 & 1 & 0 \\ 1 & 0 & 3 \end{bmatrix} = \begin{bmatrix} 5 & 2 & 3 \\ 2 & 1 & 0 \\ 3 & 0 & 9 \end{bmatrix}$$

The entry in row 1, column 2 is $(2)(1) + (1)(0) = 2$, and the entry in row 2, column 1 is $(1)(2) + (0)(1) = 2$ — the same numbers in the other order. The matrix equals its transpose: symmetric.

For $R\,R^{\mathsf{T}}$: transposes reverse order, so

$$\left(R\,R^{\mathsf{T}}\right)^{\mathsf{T}} = \left(R^{\mathsf{T}}\right)^{\mathsf{T}} R^{\mathsf{T}} = R\,R^{\mathsf{T}},$$

unchanged by transposing, hence symmetric.

Problem 5.3 Subspace or not?

Which of the following subsets of $\mathbb{R}^2$ are subspaces? For each failure, produce a specific vector and operation that leaves the set.

(a) All vectors on the line $y = 4x$. (b) All vectors on the line $y = x + 1$. (c) All vectors whose first component is nonnegative.

Show solution

(a) Subspace. The line passes through the origin: vectors have the form $c\begin{bmatrix} 1 \\ 4 \end{bmatrix}$. Adding two of them, $c_1\begin{bmatrix} 1 \\ 4 \end{bmatrix} + c_2\begin{bmatrix} 1 \\ 4 \end{bmatrix} = (c_1 + c_2)\begin{bmatrix} 1 \\ 4 \end{bmatrix}$, stays on the line; any scalar multiple stays on the line. Closed under both operations.

(b) Not a subspace. The line misses the origin: multiply the vector $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$ (which is on the line, since $1 = 0 + 1$) by the scalar $0$ and you get $\begin{bmatrix} 0 \\ 0 \end{bmatrix}$, which is not on the line ($0 \neq 0 + 1$). Every subspace must contain the zero vector, and this one doesn’t.

(c) Not a subspace. This is a half-plane, like the quarter-plane in lecture. It’s closed under addition, but not under all scalars: $\begin{bmatrix} 3 \\ 2 \end{bmatrix}$ is in the set, yet $-5\begin{bmatrix} 3 \\ 2 \end{bmatrix} = \begin{bmatrix} -15 \\ -10 \end{bmatrix}$ has negative first component and leaves the set.

Problem 5.4 Column space geometry

Describe the column space of each matrix as a subspace of $\mathbb{R}^3$ — the zero vector alone, a line, a plane, or all of $\mathbb{R}^3$:

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

Show solution

For $A$: the second column is exactly twice the first, $\begin{bmatrix} 2 \\ 4 \\ 6 \end{bmatrix} = 2\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}$, so both columns lie on the same line through the origin. Every combination $x_1\mathbf{c}_1 + x_2\mathbf{c}_2 = (x_1 + 2x_2)\mathbf{c}_1$ is a multiple of the first column. $C(A)$ is a line in $\mathbb{R}^3$ — all multiples of $(1, 2, 3)$.

For $B$: the columns $(1, 2, 3)$ and $(0, 1, 0)$ do not lie on one line — neither is a multiple of the other. Taking all combinations fills out both lines and everything in between: $C(B)$ is a plane through the origin in $\mathbb{R}^3$. It cannot be all of $\mathbb{R}^3$: two vectors can never combine to fill three-dimensional space, just as the lecture’s two columns gave a plane, not everything.