Part V · Linear algebra Chapter 37 of 60
Vector spaces
Arrows, polynomials, sound signals and even magic squares are added and multiplied by numbers by the same rules. Eight axioms, and everything we know about arrows starts working in all these worlds at once.
Builds on: 36 · Gaussian elimination
You will learn
- recognise a vector space in polynomials, functions, solutions of equations and magic squares
- test linear independence and find a basis and the dimension
- change from one basis to another, and find the kernel and image of a linear map
The last chapter ended with a list of strange coincidences. We added the rows of a matrix like arrows. Solutions of a homogeneous system add and give solutions again. The two parabolas from the observation problem, $3 + 2t + t^2$ and $2 - t + t^2$, add up to $5 + t + 2t^2$, and its heights at the moments $1$, $2$, $3$ are $8$, $15$, $26$, the sums of the heights of the terms. Sound signals add when two instruments play: the air pressure at each moment is the sum of the pressures from each. And the volume knob multiplies a signal by a number.
These are all different things: an arrow has a length and a direction, a polynomial has roots and a degree, a signal has a timbre. But if you forget everything except two operations, adding and multiplying by a number, they turn out to be indistinguishable. Mathematicians acted shrewdly: they wrote down the rules for these two operations once, called everything that obeys them a vector space, and proved theorems for all of them at once. This chapter is a journey through such worlds. In each of them something new comes in handy, and each new notion works in all the others.
Bars instead of arrows
Let’s start with a bridge between worlds. The vector $(3, 1)$ from the chapter on vectors is an arrow in the plane. But it can also be drawn differently: two bars of heights $3$ and $1$. A vector in space is three bars. An arrow in ten-dimensional space can’t be drawn, but ten bars can, easily. Bars add the same way as coordinates: height to height.
Now increase the number of bars. A hundred bars, a thousand, and the picket fence turns into the graph of a function. A function is a vector with infinitely many coordinates: one for each point $t$. Adding two functions means adding their values at each point, “bar to bar”. A sound signal in a computer is exactly such a vector: in the CD format it’s forty-four thousand one hundred pressure values for each second of sound.
The passport: eight axioms
What rules are needed for new objects to be handled like arrows? Let’s write down what we’ve been using without thinking.
A vector space is a set $V$ in which addition (any $\mathbf u, \mathbf v \in V$ are assigned an element $\mathbf u + \mathbf v \in V$) and multiplication by a number (any $\alpha \in \mathbb R$ and $\mathbf v \in V$ are assigned an element $\alpha\mathbf v \in V$) are defined, and the eight axioms below hold. The elements of $V$ are called vectors, whatever their nature.
For any $\mathbf u, \mathbf v, \mathbf w \in V$ and any numbers $\alpha, \beta$:
- $\mathbf u + \mathbf v = \mathbf v + \mathbf u$;
- $(\mathbf u + \mathbf v) + \mathbf w = \mathbf u + (\mathbf v + \mathbf w)$;
- there’s a zero vector $\mathbf 0$: $\mathbf v + \mathbf 0 = \mathbf v$ for all $\mathbf v$;
- each $\mathbf v$ has an opposite $-\mathbf v$: $\mathbf v + (-\mathbf v) = \mathbf 0$;
- $1 \cdot \mathbf v = \mathbf v$;
- $\alpha(\beta\mathbf v) = (\alpha\beta)\mathbf v$;
- $(\alpha + \beta)\mathbf v = \alpha\mathbf v + \beta\mathbf v$;
- $\alpha(\mathbf u + \mathbf v) = \alpha\mathbf u + \alpha\mathbf v$.
The first four axioms are about addition, the last four about how it gets on with multiplication by numbers. The numbers here are real; sometimes complex or rational ones are taken, and then one speaks of a space over $\mathbb C$ or over $\mathbb Q$. Any field will do: what that is will be explained in chapter 42.
The axioms aren’t everything we know about arrows. For example, that $0 \cdot \mathbf v = \mathbf 0$ isn’t on the list. That’s no oversight: such facts follow from the axioms, and they can be proved once for all worlds.
In any vector space the zero vector is unique, the opposite of each vector is unique, and for all $\mathbf v$ and $\alpha$ we have $0 \cdot \mathbf v = \mathbf 0$, $\alpha \cdot \mathbf 0 = \mathbf 0$, $(-1) \cdot \mathbf v = -\mathbf v$.
Only the axioms may be used: no geometry. Each equation below is labelled with the number of its axiom.
Here’s a world where this lemma isn’t obvious at all. Take the positive numbers and call multiplication “addition”: $x \oplus y = xy$, and call raising to a power “multiplication by a number”: $\alpha \odot x = x^\alpha$. Check the axioms: for example, the seventh turns into $x^{\alpha + \beta} = x^\alpha x^\beta$, the eighth into $(xy)^\alpha = x^\alpha y^\alpha$. All eight hold. The zero vector here is the number $1$, since $x \oplus 1 = x$, and the opposite of $x$ is the number $\frac1x$. And the lemma works: $0 \odot x = x^0 = 1$ is the zero vector, and $(-1) \odot x = x^{-1}$ is the opposite. The logarithm from chapter 12 takes this world to the ordinary line: $\ln(xy) = \ln x + \ln y$, $\ln x^\alpha = \alpha\ln x$. The slide rule, on which multiplication is done by adding lengths, relies on exactly this.
Do the vectors of the plane with both coordinates non-negative form a vector space?
The zero vector $(0, 0)$ is in the set, and the sum of two vectors in the first quadrant stays there. But $(-1) \cdot (1, 2) = (-1, -2)$ leaves the first quadrant, while multiplication by any number must keep a vector in the space. There are no opposite vectors either.
A gallery of worlds
Checking eight axioms in every world would be dull. Fortunately, almost all interesting worlds live inside ones we already know, and then two checks are enough.
A non-empty subset $U$ of a vector space $V$ is called a subspace if together with any two vectors it contains their sum, and together with any vector all its multiples.
A subspace $U$ with the same addition and multiplication by a number is a vector space. In particular, the zero vector lies in it.
Addition and multiplication don’t take you out of $U$: that’s the definition of a subspace. Axioms 1, 2 and 5–8 are equations true for any vectors of $V$, and so for vectors of $U$ too. It remains to find the zero and the opposites in $U$. Take any $\mathbf u \in U$ (the set isn’t empty). Its multiple $0 \cdot \mathbf u$ lies in $U$, and by the lemma it equals $\mathbf 0$. The multiple $(-1)\mathbf u$ is in $U$ too, and by the lemma it’s $-\mathbf u$.
Now the gallery. In all the examples addition and multiplication by a number are “pointwise” or “coordinatewise”.
- $\mathbb R^n$: columns of $n$ numbers. Lines and planes through the origin are its subspaces. A line that doesn’t pass through the origin isn’t: it has no zero.
- Functions $\mathbb R \to \mathbb R$. Inside are the subspaces of continuous functions, differentiable functions, polynomials.
- Polynomials of degree at most $n$; we’ll call them $P_n$. Polynomials of degree exactly $2$ don’t form a space: $(t^2 + t) + (-t^2) = t$.
- The solutions of a homogeneous system $A\mathbf x = \mathbf 0$ are a subspace of $\mathbb R^n$: if $A\mathbf x = \mathbf 0$ and $A\mathbf y = \mathbf 0$, then $A(\mathbf x + \mathbf y) = \mathbf 0$ and $A(\alpha\mathbf x) = \mathbf 0$. But the solutions of a system $A\mathbf x = \mathbf b$ with $\mathbf b \ne \mathbf 0$ aren’t: the zero vector doesn’t satisfy it.
- The solutions of the oscillation equation $y'' + y = 0$: if $y_1$ and $y_2$ are solutions, then $(y_1 + y_2)'' + (y_1 + y_2) = 0$. We’ll look at this world more closely.
The solutions of the equation $y'' + y = 0$ are exactly the functions $y = a\cos t + b\sin t$, where $a$ and $b$ are any numbers.
The trick is a conserved “energy”. That such functions are solutions is checked by differentiating: $(\cos t)'' = -\cos t$ and $(\sin t)'' = -\sin t$. Conversely, let $y$ be a solution. Put $a = y(0)$, $b = y'(0)$ and consider the difference $z = y - a\cos t - b\sin t$. It’s a solution too, because the solutions form a space, and moreover $z(0) = 0$, $z'(0) = 0$. Take $E(t) = z^2 + (z')^2$. Its derivative is $E' = 2zz' + 2z'z'' = 2z'(z + z'') = 0$, so $E$ is constant and equals $E(0) = 0$. A sum of squares is zero, so $z(t) = 0$ for all $t$, that is, $y = a\cos t + b\sin t$.
The seemingly infinite world of solutions is built like a plane: each solution is given by two numbers $a$ and $b$, and solutions add like pairs of numbers. A physicist would say: the motion of a pendulum is determined by the initial position and the initial velocity. Differential equations are the subject of chapter 31.
What can be built
From a few vectors, by adding them with coefficients, many others can be built. We’ve already called such a sum $\alpha_1\mathbf v_1 + \dots + \alpha_k\mathbf v_k$ a linear combination.
The set of all linear combinations of the vectors $\mathbf v_1, \dots, \mathbf v_k$ is called their span and written $\langle \mathbf v_1, \dots, \mathbf v_k\rangle$.
The span $\langle \mathbf v_1, \dots, \mathbf v_k\rangle$ is a subspace, and any subspace containing $\mathbf v_1, \dots, \mathbf v_k$ contains it entirely.
The sum of two combinations is again a combination: the coefficients of each $\mathbf v_i$ add (axioms 1, 2 and 7 let us rearrange and group the terms). A multiple of a combination is a combination with multiplied coefficients (axioms 6 and 8). So the span is a subspace. And a subspace that contains all the $\mathbf v_i$ contains their multiples and sums of multiples, that is, all the combinations.
In space the span of one non-zero vector is a line, of two usually a plane, of three usually the whole space. The word “usually” decides everything: if the second vector lies on the line of the first, it adds nothing.
The vectors $\mathbf v_1, \dots, \mathbf v_k$ are called linearly independent if $\alpha_1\mathbf v_1 + \dots + \alpha_k\mathbf v_k = \mathbf 0$ only when $\alpha_1 = \dots = \alpha_k = 0$. Otherwise they’re linearly dependent.
The vectors $\mathbf v_1, \dots, \mathbf v_k$, $k \ge 2$, are linearly dependent if and only if one of them is a linear combination of the others.
Let $\alpha_1\mathbf v_1 + \dots + \alpha_k\mathbf v_k = \mathbf 0$ with a coefficient $\alpha_j \ne 0$. Move the other terms to the right and divide by $\alpha_j$: $\mathbf v_j = -\sum_{i \ne j} \frac{\alpha_i}{\alpha_j}\mathbf v_i$. Conversely, if $\mathbf v_j = \sum_{i \ne j} \beta_i\mathbf v_i$, then $\sum_{i \ne j} \beta_i\mathbf v_i - \mathbf v_j = \mathbf 0$: a combination equal to zero with the coefficient $-1 \ne 0$ in front of $\mathbf v_j$.
Testing for dependence is a homogeneous system. Are $(1, 2, 3)$, $(4, 5, 6)$, $(7, 8, 9)$ dependent? Put them as columns of a matrix and solve $A\boldsymbol\alpha = \mathbf 0$ by Gaussian elimination: the rank is $2$, one variable is free, and the solution $\boldsymbol\alpha = (1, -2, 1)$ gives the relation $\mathbf v_1 - 2\mathbf v_2 + \mathbf v_3 = \mathbf 0$. This is the very matrix whose rank we found in chapter 36. The rank is less than the number of vectors, so the vectors are dependent.
Basis and dimension
In the chapter on vectors we expanded a vector along two non-collinear arrows and promised a definition for any number of dimensions.
A basis of a vector space $V$ is a set of linearly independent vectors whose span is the whole of $V$.
The columns $\mathbf e_1, \dots, \mathbf e_n$ of the identity matrix are a basis of $\mathbb R^n$, called the standard basis. The polynomials $1, t, t^2$ are a basis of $P_2$: every polynomial of degree at most two is a combination of them, and the combination $\alpha + \beta t + \gamma t^2$ equals the zero polynomial only when the coefficients are zero. The solutions of the equation $y'' + y = 0$ have the basis $\cos t$, $\sin t$. A space has many bases, but, as we’ll now prove, they all have the same number of vectors.
If the vectors $\mathbf w_1, \dots, \mathbf w_m$ are linearly independent and each of them is a linear combination of the vectors $\mathbf v_1, \dots, \mathbf v_n$, then $m \le n$.
The trick is to exchange the vectors $\mathbf v$ for the vectors $\mathbf w$ one at a time, without shrinking the span. If there were more vectors $\mathbf w$, at some step the $\mathbf v$’s would run out before the $\mathbf w$’s.
If a space has a basis of $n$ vectors, then any other basis of it also has $n$ vectors.
Let $\mathbf v_1, \dots, \mathbf v_n$ and $\mathbf w_1, \dots, \mathbf w_m$ be two bases. The vectors $\mathbf w_j$ are independent and are expressed through the $\mathbf v_i$, since the span of the $\mathbf v_i$ is the whole space. By the exchange lemma $m \le n$. Swapping the roles of the bases, we get $n \le m$. So $m = n$.
The number of vectors in a basis is called the dimension of the space and written $\dim V$. If there’s no finite basis, the space is called infinite-dimensional.
$\dim \mathbb R^n = n$, $\dim P_n = n + 1$ (basis $1, t, \dots, t^n$), and the dimension of the space of solutions of the equation $y'' + y = 0$ is $2$. All polynomials together form an infinite-dimensional space: a finite set of polynomials can’t produce degrees higher than the largest of its own. Functions are infinite-dimensional too.
Let $\dim V = n$. Any set of independent vectors from $V$ can be extended to a basis. In particular, any $n$ independent vectors are a basis, and $n + 1$ vectors are always dependent.
The last statement is the exchange lemma: independent vectors are expressed through a basis of $n$ vectors, so there are at most $n$ of them. Now let the vectors $\mathbf u_1, \dots, \mathbf u_k$ be independent, but let their span not be all of $V$. Take a vector $\mathbf u \in V$ outside the span. The set $\mathbf u_1, \dots, \mathbf u_k, \mathbf u$ is independent too: in the equation $\alpha_1\mathbf u_1 + \dots + \alpha_k\mathbf u_k + \beta\mathbf u = \mathbf 0$ the coefficient $\beta$ can’t be non-zero, since otherwise $\mathbf u$ would lie in the span, and with $\beta = 0$ all the $\alpha_i$ turn out to be zero too. Keep adding vectors until the span becomes all of $V$. There are never more than $n$ independent vectors, so the process stops, and we get a basis. If there were $n$ vectors to begin with, there’s nothing to add: they’re already a basis.
Magic squares
According to a Chinese legend, a turtle came out of the river Luo, and on its shell was a pattern: a square of the numbers from $1$ to $9$ whose sums along every row, every column and both diagonals are equal to $15$:
$$\begin{pmatrix} 4 & 9 & 2 \\ 3 & 5 & 7 \\ 8 & 1 & 6 \end{pmatrix}.$$
This square is called the Lo Shu. Let’s allow any real numbers in the cells: call a $3 \times 3$ table magic if the sums along the three rows, three columns and two diagonals are all the same. The sum of two magic squares is a magic square, and so is a multiple: all eight sums add and multiply together. Magic squares form a subspace of the nine-dimensional space of all $3 \times 3$ tables. What’s its dimension?
The $3 \times 3$ magic squares form a space of dimension $3$. A basis of it is
$$J = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}, \quad M_1 = \begin{pmatrix} 1 & -1 & 0 \\ -1 & 0 & 1 \\ 0 & 1 & -1 \end{pmatrix}, \quad M_2 = \begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{pmatrix}.$$
The trick is in the lines through the centre: there are four of them, and each cell except the centre lies on exactly one.
For the Lo Shu $c = 5$, and it comes out as $4\,9\,2 / 3\,5\,7 / 8\,1\,6 = 5J - M_1 + 3M_2$. Three numbers, and the whole square. The dimension suggests something else too: three cells are usually enough to recover a magic square completely. But not any three.
Coordinates: one vector, different addresses
A basis turns any space into familiar columns of numbers.
If $\mathbf e_1, \dots, \mathbf e_n$ is a basis of $V$, then each vector $\mathbf v \in V$ can be written in the form $\mathbf v = x_1\mathbf e_1 + \dots + x_n\mathbf e_n$ in exactly one way.
There’s at least one way, because the span of the basis is all of $V$. If there are two, $\mathbf v = \sum x_i\mathbf e_i = \sum y_i\mathbf e_i$, subtracting gives $\sum (x_i - y_i)\mathbf e_i = \mathbf 0$. The basis is independent, so all the $x_i - y_i = 0$.
The numbers $x_1, \dots, x_n$ are called the coordinates of the vector $\mathbf v$ in the basis $\mathbf e_1, \dots, \mathbf e_n$. The polynomial $3 + 2t + t^2$ in the basis $1, t, t^2$ has coordinates $(3, 2, 1)$, the solution $5\cos t - \sin t$ in the basis $\cos t, \sin t$ has coordinates $(5, -1)$, and the Lo Shu in the basis $J, M_1, M_2$ has coordinates $(5, -1, 3)$. Adding vectors corresponds to adding coordinates, and multiplying by a number to multiplying coordinates.
A one-to-one map of one vector space onto another that preserves addition and multiplication by a number is called an isomorphism of vector spaces, and the spaces themselves are called isomorphic.
Passing to coordinates is an isomorphism between $V$ and $\mathbb R^n$. From the point of view of linear algebra all $n$-dimensional spaces are built the same way; they differ only in what we know about them besides addition and multiplication. The logarithm from the section on axioms is an isomorphism between the positive numbers with their strange operations and the ordinary line $\mathbb R^1$.
But coordinates depend on the basis. The same polynomial $3 + 2t + t^2$ in the basis $1, (t - 1), (t - 1)^2$ is written as $6 + 4(t - 1) + (t - 1)^2$: coordinates $(6, 4, 1)$. Check by multiplying out. How do you convert coordinates from one basis to another?
Suppose a space has an old basis and a new one, $\mathbf b_1, \dots, \mathbf b_n$. The change-of-basis matrix $P$ is the matrix whose $j$th column consists of the coordinates of the vector $\mathbf b_j$ in the old basis.
The idea: walk to the vector along the new basis vectors, and expand each of them in the old ones.
The matrices of maps change too. Suppose a map is given in the old coordinates by the matrix $A$: $\mathbf y = A\mathbf x$. Substitute $\mathbf x = P\mathbf x'$ and $\mathbf y = P\mathbf y'$: we get $P\mathbf y' = AP\mathbf x'$.
In a new basis with change-of-basis matrix $P$, the map with matrix $A$ is written with the matrix $A' = P^{-1}AP$.
For any vector with new coordinates $\mathbf x'$, its image has old coordinates $A\mathbf x = AP\mathbf x'$ (the change-of-coordinates formula for $\mathbf x$), and new ones $P^{-1}(AP\mathbf x')$ (the reverse conversion for the image). So the map in new coordinates is multiplication by $P^{-1}AP$.
Square matrices $A$ and $A' = P^{-1}AP$, where $P$ is invertible, are called similar. They’re the same map written in different bases.
Some bases make the matrix noticeably simpler. We’ll come back to this at the very end of the chapter.
What disappears and what remains
An $m \times n$ matrix $A$ takes vectors from $\mathbb R^n$ to $\mathbb R^m$. Some vectors it destroys, sending them to zero, and some vectors of the target it can reach.
The kernel of a matrix is the set $\ker A = \{\mathbf x : A\mathbf x = \mathbf 0\}$, that is, the solutions of the homogeneous system. The image is the set $\operatorname{im} A = \{A\mathbf x\}$ of all vectors that $A$ takes something to. The dimension of the kernel is called the nullity.
Both sets are subspaces. We saw this for the kernel in the gallery, and for the image $A\mathbf x + A\mathbf y = A(\mathbf x + \mathbf y)$ and $\alpha A\mathbf x = A(\alpha\mathbf x)$. The image coincides with the span of the columns: $A\mathbf x = x_1\mathbf a_1 + \dots + x_n\mathbf a_n$, where the $\mathbf a_j$ are the columns of $A$. So the system $A\mathbf x = \mathbf b$ is consistent exactly when $\mathbf b$ lies in the span of the columns: another view of the Rouché–Capelli theorem.
The columns of a matrix $A$ in which pivots appeared after reduction to echelon form are a basis of the image $\operatorname{im} A$. So $\dim \operatorname{im} A = \operatorname{rank} A$. Moreover, the non-zero rows of the echelon form are a basis of the span of the rows of $A$, so the dimension of the row span also equals the rank.
An idea from the proof of the uniqueness of the reduced form: elementary row operations don’t change the relations between the columns.
So how much disappears? The free unknowns from chapter 36 answer this question.
For a matrix $A$ with $n$ columns, $\dim \ker A + \operatorname{rank} A = n$.
The idea: Gaussian elimination gives a basis of the kernel, one vector for each free unknown.
Now it’s clear why in the general solution a particular solution was added to directions solving the homogeneous system. If $A\mathbf x_0 = \mathbf b$, then $A\mathbf x = \mathbf b$ exactly when $A(\mathbf x - \mathbf x_0) = \mathbf 0$, so all the solutions are $\mathbf x_0 + \ker A$: the kernel shifted so as to pass through $\mathbf x_0$. The line of solutions from chapter 36 is the line of the kernel shifted to the point $(3, 0, 1)$.
What’s the dimension of the space of polynomials $p$ of degree at most $3$ with $p(1) = 0$ and $p(-1) = 0$?
The map $p \mapsto (p(1), p(-1))$ takes $P_3$ to $\mathbb R^2$, and our space is its kernel. The image is all of $\mathbb R^2$: the polynomials $\frac{1 + t}{2}$ and $\frac{1 - t}{2}$ give $(1, 0)$ and $(0, 1)$, so the rank is $2$. By the rank–nullity theorem the dimension of the kernel is $4 - 2 = 2$. A basis: $t^2 - 1$ and $t(t^2 - 1)$.
The span of the vectors $(1, -1, 0)$, $(0, 1, -1)$, $(1, 0, -1)$ has dimension $2$. What’s the dimension of the kernel of the matrix whose columns are these vectors?
The rank of the matrix is the dimension of the span of its columns, that is, $2$. By the rank–nullity theorem $\dim\ker = 3 - 2 = 1$. The kernel is spanned by $(1, 1, -1)$: the first vector plus the second minus the third gives zero.
Where next
The kernel is the directions that a map multiplies by zero. Are there directions that it multiplies by $2$ or by $-1$, not turning them but only stretching? Take the matrix $\left(\begin{smallmatrix} 3 & 1 \\ 0 & 2 \end{smallmatrix}\right)$. It turns most vectors, but $(1, 0)$ goes to $(3, 0)$, the same vector stretched threefold, and $(1, -1)$ goes to $(2, -2)$, stretched twofold. Take these two vectors as a basis. The formula $P^{-1}AP$ with the change-of-basis matrix $P = \left(\begin{smallmatrix} 1 & 1 \\ 0 & -1 \end{smallmatrix}\right)$ gives $\left(\begin{smallmatrix} 3 & 0 \\ 0 & 2 \end{smallmatrix}\right)$: in this basis the map simply stretches one axis threefold and the other twofold. How to find such directions for any matrix, and what they give us, from the Fibonacci numbers to the Google search engine, is the subject of chapter 38.