An Overview of Key Ideas

Vectors, then matrices, then subspaces

This session’s video is a little different: it’s Strang’s own review lecture on linear algebra, borrowed from his 18.085 course (Fall 2008), rather than a 2005 18.06 lecture — “the one and only review, you could say, of linear algebra.”

Strang opens with a claim about how the subject is organized. Linear algebra progresses “starting with vectors to matrices and then finally to subspaces.” That last step is the abstraction — but not a difficult one — and it’s the one that matters: “Until you see the idea of a subspace, you haven’t really got linear algebra.”

So: what do you do with vectors? “You take their linear combinations.” That’s the key operation — multiply by numbers (scalars) and add. The whole lecture is that one operation, examined from every side, using two carefully chosen examples. (Both, Strang notes, live on the 18.06 website under Starting with Two Matrices.)

Three vectors and their combinations

Take three vectors in $\mathbb{R}^3$:

$$\mathbf{u} = \begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix}, \qquad \mathbf{v} = \begin{bmatrix} 0 \\ 1 \\ -1 \end{bmatrix}, \qquad \mathbf{w} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}$$

Before using all three, Strang asks a “serious question” about the first two. Multiples of $\mathbf{u}$ alone fill a line — later he’d call that a one-dimensional subspace. Multiples of $\mathbf{v}$ fill another line. And all combinations $x_1\mathbf{u} + x_2\mathbf{v}$? You get a plane. Not all of 3-D — adding a point on one line to a point on the other can’t escape the plane the two lines span. The great thing about linear algebra is that this instinct survives into $n$ dimensions, “10-dimensional, 100-dimensional, where we can’t visualize, but yet, our instinct is right if we just follow.”

Now bring in $\mathbf{w}$. How do you take combinations of three vectors? Strang’s habit, and the course’s central move: put the vectors into the columns of a matrix.

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

Then $A\mathbf{x} = x_1(\text{column 1}) + x_2(\text{column 2}) + x_3(\text{column 3})$ — a matrix times a vector produces exactly the combination you wanted. That’s how matrix multiplication works, by columns, “and you don’t always see that,” because everyone computes a component at a time, row dotted with vector. Do it that way and the components come out as

$$A\mathbf{x} = \begin{bmatrix} x_1 \\ x_2 - x_1 \\ x_3 - x_2 \end{bmatrix}$$

It always helps to give names to things: $A$ is a difference matrix — a first difference matrix — because it takes differences of the $x$‘s. Feed it the squares, $\mathbf{x} = (1, 4, 9)$, and out come the odd numbers, $\mathbf{b} = (1, 3, 5)$: differences of squares are odd. (“That appealed to me in school somehow. That was already a bad sign, right?”)

Going backwards: the inverse is a sum matrix

The forward direction — input $\mathbf{x}$, output $\mathbf{b}$ — is easy and important. “But the more deep problem is, what if I give you $\mathbf{b}$ and ask for $\mathbf{x}$?” Now we’re solving $A\mathbf{x} = \mathbf{b}$: three equations, three unknowns.

$$x_1 = b_1, \qquad x_2 - x_1 = b_2, \qquad x_3 - x_2 = b_3$$

Because $A$ is lower triangular, we can march from the top, substituting down as we go:

$$x_1 = b_1, \qquad x_2 = b_1 + b_2, \qquad x_3 = b_1 + b_2 + b_3$$

Now the “good early step in linear algebra”: look at that solution and see a matrix multiplying $\mathbf{b}$. Read off the coefficients of $b_1, b_2, b_3$, column by column:

$$\mathbf{x} = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} \mathbf{b}$$

And this particular inverse has a name too. $A$ took differences, so $A^{-1}$ takes sums — call it $S$ for sum matrix; that’s why you see rows of 1’s. Check with the earlier numbers: differences of $(1, 4, 9)$ gave $(1, 3, 5)$, and sums of $(1, 3, 5)$ give back $(1, 4, 9)$.

One more observation to bank before moving on: for this matrix $A$, if $A\mathbf{x} = \mathbf{0}$ then $\mathbf{x} = \mathbf{0}$. To get zero out, you had to put zero in. Keep that in mind.

Change one entry: the matrix C

Second example, and the contrast is the whole point. Keep $\mathbf{u}$, keep $\mathbf{v}$, but replace $\mathbf{w}$ by $\mathbf{w}^* = (-1, 0, 1)$:

$$C = \begin{bmatrix} 1 & 0 & -1 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix}, \qquad C\mathbf{x} = \begin{bmatrix} x_1 - x_3 \\ x_2 - x_1 \\ x_3 - x_2 \end{bmatrix}$$

One new entry, a $-1$ in the corner. Now the first row takes $x_1 - x_3$: the difference equation has become circular — “you’ve sort of changed the boundary condition” — which is why Strang calls it $C$. Can we solve $C\mathbf{x} = \mathbf{b}$? “You’re guessing already, no we can’t do it.” The trouble shows up several ways:

Nonzero inputs give zero output. $C$ applied to $(1, 1, 1)$ gives zero — the differences of a constant vector all vanish. And not just that one vector: every multiple $(c, c, c)$ works. A whole line of solutions to $C\mathbf{x} = \mathbf{0}$ — later language would call that line a subspace. This is fatal for invertibility: “no $C^{-1}$ can bring you back… I can’t multiply zero by anything and get back to $\mathbf{x}$.”

The equations conspire. Add the three left-hand sides of $C\mathbf{x} = \mathbf{b}$: everything cancels, and you get $0 = b_1 + b_2 + b_3$ — not a fourth independent equation, but a consequence of the three. So $C\mathbf{x} = \mathbf{b}$ is solvable exactly when $b_1 + b_2 + b_3 = 0$, and hopeless otherwise. Strang gives the condition a mechanical meaning: if the $b$‘s are forces on masses in a cyclic arrangement of springs, solvability says the forces must add to zero — otherwise the system takes off.

The geometry. In the picture, $\mathbf{u}$ and $\mathbf{v}$ span a plane — and $\mathbf{w}^*$ lies in that plane. ”$\mathbf{w}^*$ gave us nothing new.”

Which $\mathbf{b}$‘s do the combinations of $\mathbf{u}, \mathbf{v}, \mathbf{w}^*$ reach? All combinations of the three columns is the same thing as all vectors $C\mathbf{x}$ — that’s just how matrix multiplication works. And every output of $C$ has components adding to zero. So the reachable $\mathbf{b}$‘s form exactly the plane $b_1 + b_2 + b_3 = 0$. Check it against the columns themselves: the components of $\mathbf{u}$ add to zero, of $\mathbf{v}$ add to zero, of $\mathbf{w}^*$ add to zero — so every combination does too. “That’s the equation of the plane.”

What a subspace is

The two examples earn the abstraction. A vector space is a bunch of vectors where you can take all their combinations — “that’s what linear algebra does.” A subspace is a vector space inside a bigger one; that’s why the prefix “sub-” is there. The plane $b_1 + b_2 + b_3 = 0$ is a typical subspace. A triangle drawn inside it is not, because $2\mathbf{u}$ would already escape the triangle. You get subspaces by taking all combinations, and the sizes can be anything: “a 7-dimensional subspace inside a 15-dimensional space” is no problem to work with, even if nobody can visualize it — seven vectors with 15 components each is a matrix with 105 entries, which MATLAB deals with instantly.

What are all the subspaces of $\mathbb{R}^3$? Planes through the origin and lines through the origin — “the real, the proper subspaces.” Plus two extreme possibilities that mathematics always counts: the whole space itself, and the smallest subspace of all, the origin alone. A single nonzero point can’t qualify — multiply its vector by five and you’ve left it — but the set containing just the zero vector can: “not empty. It’s got that one point but that’s all.” The dimensions run 3 for the whole space, 2 for a plane, 1 for a line, 0 for the origin.

Strang closes with a hint at what’s ahead. Matrices can be rectangular — a $7 \times 3$ matrix takes 3-dimensional space to 7-dimensional space, and “you can’t invert that.” What comes up every time with a rectangular $A$ is that sooner or later ”$A$ transpose sticks its nose in”: the course keeps meeting $A^{\mathsf{T}}A$, which always comes out square ($3 \times 7$ times $7 \times 3$ is $3 \times 3$) and always symmetric. Watch for it in applications of all kinds — in networks, $A$ is associated with Kirchhoff’s voltage law and $A^{\mathsf{T}}$ with Kirchhoff’s current law, and “they just teamed up together.”

Problems

The recitation video, where a TA works problem 13.1, is at https://youtu.be/OZxzHcW663g. Try it under exam conditions first — it appeared on an actual 18.06 quiz.

Problem 13.1 Session's recitation problem

(Quiz 1, Fall 1999, question 4.) The usual problem is turned upside down: you are told that all solutions to

$$A\mathbf{x} = \begin{bmatrix} 1 \\ 4 \\ 1 \\ 1 \end{bmatrix}$$

are given by

$$\mathbf{x} = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} + c \begin{bmatrix} 0 \\ 2 \\ 1 \end{bmatrix} \quad \text{for any number } c.$$

Say everything you can about the columns of the matrix $A$.

Show solution

Size of $A$. $A$ multiplies an $\mathbf{x}$ with three entries and produces a vector with four, so $A$ is $4 \times 3$: three columns $\mathbf{c}_1, \mathbf{c}_2, \mathbf{c}_3$, each in $\mathbb{R}^4$. Call the right-hand side $\mathbf{b}$.

Set up two equations. Write $\mathbf{x}_p = (0, 1, 1)$ (particular solution) and $\mathbf{x}_s = (0, 2, 1)$ (special solution). Since $\mathbf{x}_p + c\,\mathbf{x}_s$ solves $A\mathbf{x} = \mathbf{b}$ for every $c$: taking $c = 0$ gives $A\mathbf{x}_p = \mathbf{b}$; taking $c = 1$ gives $A\mathbf{x}_p + A\mathbf{x}_s = \mathbf{b}$, and subtracting, $A\mathbf{x}_s = \mathbf{0}$.

Solve for the columns. $A\mathbf{x}_p = \mathbf{b}$ says the combination of the columns with weights $(0, 1, 1)$ equals $\mathbf{b}$:

$$\mathbf{c}_2 + \mathbf{c}_3 = \mathbf{b}$$

and $A\mathbf{x}_s = \mathbf{0}$ with weights $(0, 2, 1)$ says

$$2\mathbf{c}_2 + \mathbf{c}_3 = \mathbf{0}$$

This is a linear system whose unknowns are vectors. The second equation gives $\mathbf{c}_3 = -2\mathbf{c}_2$; substituting into the first, $\mathbf{c}_2 - 2\mathbf{c}_2 = \mathbf{b}$, so

$$\mathbf{c}_2 = -\mathbf{b} = \begin{bmatrix} -1 \\ -4 \\ -1 \\ -1 \end{bmatrix}, \qquad \mathbf{c}_3 = 2\mathbf{b} = \begin{bmatrix} 2 \\ 8 \\ 2 \\ 2 \end{bmatrix}$$

The second and third columns are completely determined.

What about $\mathbf{c}_1$? The solution set has exactly one free parameter $c$, so the null space of $A$ has dimension 1 — there is just one special solution. Then $\operatorname{rank}(A) = 3 - 1 = 2$, so $A$ has exactly two linearly independent columns. Since $\mathbf{c}_2$ and $\mathbf{c}_3$ are both multiples of $\mathbf{b}$, the first column must supply the second independent direction: $\mathbf{c}_1$ is not a multiple of $\mathbf{b}$ — not any multiple, including the zero multiple. If it were, the rank would drop below 2 and a second free parameter would appear in the solution set. That is everything that can be said about $\mathbf{c}_1$.

Problem 13.2 Difference matrix forwards and back

Let $A$ be the first difference matrix from the lecture,

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

(a) Compute $A\mathbf{x}$ for $\mathbf{x} = (1, 8, 27)$, the first three cubes. (b) Solve $A\mathbf{x} = \mathbf{b}$ for $\mathbf{b} = (2, 3, 4)$ by working from the top equation down, and check your answer using the sum matrix $S = A^{-1}$.

Show solution

(a) $A\mathbf{x}$ takes differences: $(x_1,\ x_2 - x_1,\ x_3 - x_2) = (1,\ 8 - 1,\ 27 - 8) = (1, 7, 19)$.

(b) The equations are $x_1 = 2$, $x_2 - x_1 = 3$, $x_3 - x_2 = 4$. Because $A$ is lower triangular, substitute down from the top: $x_1 = 2$, then $x_2 = 2 + 3 = 5$, then $x_3 = 5 + 4 = 9$. So $\mathbf{x} = (2, 5, 9)$.

Check with the sum matrix — $\mathbf{x} = S\mathbf{b}$ takes running sums of $\mathbf{b}$:

$$\begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 2 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 2 \\ 5 \\ 9 \end{bmatrix} \checkmark$$

Sums undo differences — the difference-matrix / sum-matrix pairing from the lecture.

Problem 13.3 Solvability of the circular system

Let $C$ be the circular difference matrix from the lecture,

$$C = \begin{bmatrix} 1 & 0 & -1 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix}$$

(a) Decide whether $C\mathbf{x} = (1, -2, 1)$ is solvable, and if so find all solutions. (b) Decide the same for $C\mathbf{x} = (1, 1, 1)$.

Show solution

The solvability test from the lecture: adding the three equations makes every $x$ on the left cancel, leaving $0 = b_1 + b_2 + b_3$. A solution can exist only when the components of $\mathbf{b}$ add to zero.

(a) $1 + (-2) + 1 = 0$, so the system is solvable. The equations are

$$x_1 - x_3 = 1, \qquad x_2 - x_1 = -2, \qquad x_3 - x_2 = 1$$

Only differences of the $x$‘s appear, so fix $x_3 = 0$: then $x_1 = 1$ from the first equation and $x_2 = 1 - 2 = -1$ from the second; the third checks, $0 - (-1) = 1$. That gives a particular solution $(1, -1, 0)$. Since $C$ sends every constant vector $c\,(1, 1, 1)$ to zero, all solutions are

$$\mathbf{x} = \begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix} + c \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$$

— a whole line of solutions.

(b) $1 + 1 + 1 = 3 \neq 0$, so there is no solution: every output $C\mathbf{x}$ has components adding to zero, and $(1, 1, 1)$ does not lie in that plane.

Problem 13.4 Independence and basis

(a) Show that the lecture’s three vectors $\mathbf{u} = (1, -1, 0)$, $\mathbf{v} = (0, 1, -1)$, $\mathbf{w}^* = (-1, 0, 1)$ are dependent by exhibiting a nonzero combination of them that equals the zero vector. (b) Replace $\mathbf{w}^*$ by a vector of your choosing so that the three vectors form a basis for $\mathbb{R}^3$, and explain how you know your trio qualifies.

Show solution

(a) Add them: $\mathbf{u} + \mathbf{v} + \mathbf{w}^* = (1 + 0 - 1,\ -1 + 1 + 0,\ 0 - 1 + 1) = (0, 0, 0)$. A combination with nonzero coefficients ($1, 1, 1$) gives zero, so the vectors are dependent — equivalently, $\mathbf{w}^* = -\mathbf{u} - \mathbf{v}$ lies in the plane spanned by $\mathbf{u}$ and $\mathbf{v}$.

(b) Take $\mathbf{w} = (0, 0, 1)$, the lecture’s original third vector. The plane spanned by $\mathbf{u}$ and $\mathbf{v}$ consists of vectors whose components add to zero (both spanning vectors have that property, so every combination inherits it). The components of $(0, 0, 1)$ add to $1 \neq 0$, so $\mathbf{w}$ is not in that plane: the three vectors are independent. Three independent vectors in $\mathbb{R}^3$ form a basis — their combinations fill the whole space, and the matrix with these columns is invertible (the lecture even produced its inverse, the sum matrix). Any third vector whose components do not sum to zero would work equally well.