Matrix Spaces; Rank 1; Small World Graphs

Vector spaces that don’t contain vectors

At the end of lecture ten, Strang was working with vector spaces whose elements were not what we usually call vectors — they were matrices. This lecture picks that thread up, because the point deserves to sink in: we’ve been so specific about $n$-dimensional space, and “you really want to see that the same ideas work as long as you can add and multiply by scalars.”

Take $M$, the space of all $3 \times 3$ matrices. You can add two of them; you can multiply one by a scalar. (You can also multiply two matrices together — but that’s not part of the vector space picture. The vector space part is just adding and scaling.) Inside $M$ sit interesting subspaces:

• $S$ — the symmetric $3 \times 3$ matrices. Add two symmetric matrices and the sum is still symmetric. (Multiply two symmetric matrices and the product need not be symmetric — but we’re not multiplying, so we’re fine.)
• $U$ — the upper triangular $3 \times 3$ matrices. Add two upper triangulars, still upper triangular.

Both pass the subspace test. Now the natural questions, the same ones we always ask: what is a basis, and what is the dimension?

Bases and dimensions of matrix spaces

How many numbers does it take to specify a $3 \times 3$ matrix? Nine. So the dimension of $M$ is nine, and the most obvious basis is the “standard basis” of matrices with a single $1$ and eight zeros:

$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix},\; \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix},\; \ldots,\; \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

Nine of them. Our space is “practically the same as nine-dimensional space” — the nine numbers are just written in a square instead of a column. But it deserves to be thought of as natural for itself.

Now the subspaces. For a symmetric matrix, how many parameters do you choose freely? The three diagonal entries, plus the three entries above the diagonal — the three below are then forced. So $\dim S = 6$. For an upper triangular matrix, you choose the three diagonal entries and the three above: $\dim U = 6$ as well.

Here’s a subtlety worth noticing. Of the nine standard basis matrices, six happen to be upper triangular — so the big basis accidentally contains a basis for $U$. But only three of the nine are symmetric (the three diagonal ones), and three matrices can’t span a six-dimensional $S$. The lesson: a basis for the big space generally does not hand you a basis for a subspace. You have to think it over again.

Intersections and sums of subspaces

What subspaces can we build from $S$ and $U$? First, their intersection $S \cap U$ — the matrices that are symmetric and upper triangular. Symmetric and upper triangular forces every off-diagonal entry to be zero, so $S \cap U = D$, the diagonal matrices, and $\dim(S \cap U) = 3$.

What about the union — matrices that are symmetric or upper triangular? That is not a subspace. It’s like taking a couple of lines in the plane and stopping there: two six-dimensional subspaces of a nine-dimensional space, headed in different directions. Add a symmetric matrix to an upper triangular one and you generally land outside both. We can’t just put the two subspaces together — we have to fill in.

What do you get from a symmetric plus an upper triangular? Anything — every $3 \times 3$ matrix can be written that way. So $S + U = M$ and $\dim(S + U) = 9$. And now Strang sees a nice formula sitting in the numbers: $6 + 6 = 3 + 9$.

A vector space from a differential equation

One more vector space that doesn’t have vectors in it — this one comes from differential equations. Look at all solutions of

$$\frac{d^2 y}{dx^2} + y = 0.$$

$y = \cos x$ is a solution. $y = \sin x$ is a solution. ($y = e^{ix}$ too, but you don’t need to add it separately — it’s already a combination of these.) The complete solution is

$$y = c_1 \cos x + c_2 \sin x.$$

That set of solutions is a vector space. What Strang wants you to see: this is really a null space — the null space of a differential equation. And $\cos x$, $\sin x$ are a basis: every solution is a combination of them, just as the special solutions were a basis for the null space of $A\mathbf{x} = \mathbf{0}$. The dimension of the solution space is two, because the equation is second order. ($e^{ix}$ and $e^{-ix}$ would be another perfectly good basis — lots of bases.)

Rank one matrices: the building blocks

Back to the key number attached to a matrix: its rank (never bigger than $m$ or $n$). Strang singles out rank one matrices because they ought to be simple — “if the rank is only one, the matrix can’t get away from us.”

Their determinants will be easy, their eigenvalues will be interesting — rank one matrices will keep coming back.

That raises a subspace question. Inside the space of all $5 \times 17$ matrices, do the matrices of rank four (or less) form a subspace? No. If you add two rank four matrices, the sum is usually not rank four — in fact the general rule is

$$\operatorname{rank}(A + B) \le \operatorname{rank}(A) + \operatorname{rank}(B),$$

so the sum of two rank fours could go up to rank five here (never more than $m = 5$). Same for rank one: add two rank one matrices and you most likely get rank two. Not a subspace.

One more subspace, all four ways

A more likely exam-style example. In $\mathbb{R}^4$, take

$$S = \left\{ \mathbf{v} : v_1 + v_2 + v_3 + v_4 = 0 \right\}.$$

Is it a subspace? Yes: multiply a vector whose components add to zero by six and they still add to zero; add two such vectors and the sums add to zero. Its dimension? Three — and here’s the systematic way to see it. $S$ is exactly the null space of the $1 \times 4$ matrix

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

since $A\mathbf{v} = 0$ says precisely that the components add to zero. The rank of $A$ is one, so $\dim N(A) = n - r = 4 - 1 = 3$. A basis: the three special solutions. The pivot variable is $v_1$; the free variables are $v_2, v_3, v_4$. Set each free variable to $1$ in turn, and a $-1$ in the first slot makes the sum zero:

$$\begin{bmatrix} -1 \\ 1 \\ 0 \\ 0 \end{bmatrix},\quad \begin{bmatrix} -1 \\ 0 \\ 1 \\ 0 \end{bmatrix},\quad \begin{bmatrix} -1 \\ 0 \\ 0 \\ 1 \end{bmatrix}$$

Not the only possible basis, but “those are the special three.”

Now kill the example by finding all four fundamental subspaces of $A$. The row space is one-dimensional in $\mathbb{R}^4$: all multiples of $\begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}$. The null space is the three-dimensional $S$; check $1 + 3 = 4 = n$. The column space: the columns have only one component, so $C(A)$ lives in $\mathbb{R}^1$ — and all multiples of the column $1$ give all of $\mathbb{R}^1$, so $C(A) = \mathbb{R}^1$, dimension one. The null space of $A^T$: the only combination of the rows giving the zero row is the zero combination, so $N(A^T) = \{\mathbf{0}\}$, dimension zero; check $1 + 0 = 1 = m$. And a nice point of hygiene: the subspace containing only the zero vector has dimension zero, and its basis is the empty set — zero members, dimension zero.

Small world graphs

Five minutes on the topic that leads into the next lecture. A graph here isn’t a sine curve from calculus — the word means something completely different: a set of nodes and edges connecting them. Strang draws five nodes and six edges, and promises that some $5 \times 6$ matrix will tell us everything about that graph — next time.

The graph he’s interested in: let every person in the room be a node, with an edge between two people if they’re friends. Scale it up to the whole country — 260 million nodes, edges between friends. The question: how far apart can two people be in this friendship graph? Strang’s own distance to Clinton is two — he went to college with a senator who knows Clinton. Your distance to Clinton is then at most three, “I take credit for reducing your Clinton distance to three.”

That’s the meaning behind the phrase six degrees of separation (the movie title, the book title): in the friendship graph, roughly six steps connect almost anybody to anybody. Sit next to a stranger on an airplane, start hunting for mutual friends, and you’ll often connect in two or three or four steps — “it’s a small world,” and that’s where the expression comes from. The mathematical point, saved for lecture twelve: with a few shortcuts added, distances in such graphs come down dramatically. The graph of the World Wide Web — nodes are sites, edges are links — is the fantastic example everyone wants to model.

Problems

Work these before revealing the solutions. Everything you need is in the lecture.

Problem 11.1 Dimensions of matrix subspaces

In the space of all $4 \times 4$ matrices, find the dimensions of: (a) the whole space $M$; (b) the subspace $S$ of symmetric matrices; (c) the subspace $U$ of upper triangular matrices; (d) $S \cap U$; (e) $S + U$. Verify the formula $\dim S + \dim U = \dim(S \cap U) + \dim(S + U)$.

Show solution

(a) A $4 \times 4$ matrix has $16$ entries, so $\dim M = 16$.

(b) A symmetric matrix is fixed by its diagonal ($4$ entries) plus the entries above the diagonal ($6$ entries): $\dim S = 10$.

(c) Upper triangular: the diagonal and above, again $4 + 6 = 10$, so $\dim U = 10$.

(d) Symmetric and upper triangular forces all off-diagonal entries to zero: $S \cap U$ is the diagonal matrices, $\dim(S \cap U) = 4$.

(e) Every matrix is a symmetric plus an upper triangular, so $S + U = M$ and $\dim(S + U) = 16$.

Check: $10 + 10 = 4 + 16 = 20$. ✓

Problem 11.2 Solution space as null space

Consider all solutions of $y'' - y = 0$. Show that they form a vector space, give a basis, and state the dimension. Then give a second basis for the same space.

Show solution

If $y_1'' = y_1$ and $y_2'' = y_2$, then $(c_1 y_1 + c_2 y_2)'' = c_1 y_1'' + c_2 y_2'' = c_1 y_1 + c_2 y_2$ — combinations of solutions are solutions, so the solution set is a vector space (the “null space” of the operator $y \mapsto y'' - y$).

$y = e^{x}$ and $y = e^{-x}$ are solutions, and every solution is $y = c_1 e^{x} + c_2 e^{-x}$. Since neither is a multiple of the other, they are independent: $\{e^{x}, e^{-x}\}$ is a basis and the dimension is $2$ (a second order equation).

A second basis: $\cosh x = \tfrac{1}{2}(e^x + e^{-x})$ and $\sinh x = \tfrac{1}{2}(e^x - e^{-x})$. Both solve the equation, they are independent, and $e^{\pm x} = \cosh x \pm \sinh x$ shows they span the same space. Lots of bases.

Problem 11.3 Rank one factorization

Write the matrix

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

in the form $\mathbf{u}\mathbf{v}^T$. Then give bases for its row space and column space, and find the dimension of its null space.

Show solution

Every row is a multiple of $\begin{bmatrix} 1 & 2 & -1 \end{bmatrix}$ — rows one, two, three are $3$, $1$, $2$ times it. So

$$A = \begin{bmatrix} 3 \\ 1 \\ 2 \end{bmatrix} \begin{bmatrix} 1 & 2 & -1 \end{bmatrix} = \mathbf{u}\mathbf{v}^T.$$

The rank is one. Basis for the row space: $\begin{bmatrix} 1 & 2 & -1 \end{bmatrix}$. Basis for the column space: $\begin{bmatrix} 3 \\ 1 \\ 2 \end{bmatrix}$ (every column is a multiple of it: $1$, $2$, $-1$ times).

Null space dimension: $n - r = 3 - 1 = 2$.

Problem 11.4 Is it a subspace?

Inside the space of all $3 \times 3$ matrices, decide whether each subset is a subspace. Give a reason or a counterexample. (a) The matrices of rank one, together with the zero matrix. (b) The matrices whose nine entries add to zero.

Show solution

(a) Not a subspace. Take $A = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}\begin{bmatrix} 1 & 0 & 0 \end{bmatrix}$ and $B = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}\begin{bmatrix} 0 & 1 & 0 \end{bmatrix}$ — each has rank one, but $A + B$ has two independent rows, so its rank is two. Adding two rank one matrices most likely gives rank two; the set is not closed under addition. (In general $\operatorname{rank}(A+B) \le \operatorname{rank}(A) + \operatorname{rank}(B)$, but the sum’s rank can exceed one.)

(b) A subspace. If the entries of $A$ add to zero and the entries of $B$ add to zero, the entries of $A + B$ add to $0 + 0 = 0$, and the entries of $cA$ add to $c \cdot 0 = 0$. One linear condition on the nine entries — exactly like $v_1 + \cdots + v_4 = 0$ in $\mathbb{R}^4$ — so it is a null space in disguise, of dimension $9 - 1 = 8$.

Problem 11.5 Four subspaces of a one-row matrix

Let $A = \begin{bmatrix} 1 & 2 & 2 \end{bmatrix}$, a $1 \times 3$ matrix. Find the dimension of each of the four fundamental subspaces, and give a basis for the null space $N(A)$.

Show solution

The rank is $r = 1$ (one nonzero row).

• Row space $C(A^T)$: dimension $1$ in $\mathbb{R}^3$; basis $\begin{bmatrix} 1 & 2 & 2 \end{bmatrix}$.
• Null space $N(A)$: dimension $n - r = 3 - 1 = 2$.
• Column space $C(A)$: dimension $1$ — it is all of $\mathbb{R}^1$.
• Null space of $A^T$: dimension $m - r = 1 - 1 = 0$ — only the zero vector, with the empty set as basis.

For $N(A)$: the pivot variable is $v_1$; free variables are $v_2, v_3$. The condition is $v_1 + 2v_2 + 2v_3 = 0$. Special solutions: set $v_2 = 1, v_3 = 0$ giving $v_1 = -2$; set $v_2 = 0, v_3 = 1$ giving $v_1 = -2$:

$$\begin{bmatrix} -2 \\ 1 \\ 0 \end{bmatrix},\qquad \begin{bmatrix} -2 \\ 0 \\ 1 \end{bmatrix}.$$

Check: $1 + 2 = 3 = n$ and $1 + 0 = 1 = m$. ✓