Linear Algebra

We share a philosophy about linear algebra: we think basis-free, we write basis-free, but when the chips are down we close the office door and compute with matrices like fury.

Here is a puzzle that fits in a pocket. Twenty-five lights sit in a five-by-five grid. Pressing a light switches it (on becomes off, off becomes on), and it also switches its neighbours directly above, below, left and right. Some lights are on. Can you switch them all off?

If you played for a minute, you probably discovered two facts. The order of presses does not matter: in the end each light has simply been switched some number of times. And pressing the same button twice does nothing at all: the light and its neighbours flip, then flip back. Some boards also start to feel suspicious. Is every arrangement of lights solvable? When one is, how many different solutions does it have? And if one is not, how could you ever prove it, short of trying all $2^{25}=33,554,432$ possible sets of presses?

The answers turn out to be startlingly crisp. Exactly a quarter of all boards can be solved. Every solvable board has exactly four solutions. And two parity tests, each checkable in ten seconds, tell the solvable boards from the rest. All three answers come from one tool, linear algebra, the mathematics of things that can be added together and scaled. Engineers, statisticians and physicists use it every day, and for this book it is the engine room: almost every computation in homology is a computation in linear algebra.

Kaplansky was owning up for himself and his friend Paul Halmos, whose 1942 book Finite-Dimensional Vector Spaces is the classic of the coordinate-free style (Kaplansky 1991, p. 88). The confession describes the two halves of the subject. One half is pictures and ideas: arrows, grids, shadows, things crushed and things reached. The other half is tables of numbers, pushed around by rules until they give up their secrets. Each idea below gets its picture first; then we close the office door and compute.

Vectors: arrows, lists and switches

The word vector has three everyday meanings in mathematics: an arrow, a list of numbers and, less obviously, a row of switches. They look different, and the first job of this chapter is to convince you that they are one idea.

The first picture is an arrow: a displacement, such as “three steps east and one step north”. What matters is the length and direction of the trip, not where it starts, but we will usually draw arrows starting from a fixed point called the origin.

The second picture is a list of numbers. The trip above is recorded as $(3,1):$ three units along the horizontal axis, one unit up the vertical one. Lists of two numbers describe the plane, lists of three describe space, and nothing stops us from using lists of $n$ numbers for any whole number $n.$ The set of all such lists is written ${\mathbb{R}}^n,$ read “R-n” or “R to the n”. Here $\mathbb{R}$ stands for the real numbers, all the points of the number line, fractions and $\sqrt{2}$ and $\pi$ included. We print vectors in bold, like $\mathbf{u}$ and $\mathbf{v},$ to tell them apart from ordinary numbers, and we write $0$ for the zero vector $(0,0,\dots ,0),$ the trip that goes nowhere.

Arrows and lists can do two things, and the whole subject is built from these two:

• Add. To add arrows, put them tip to tail: walk along $\mathbf{u},$ then along $\mathbf{v}.$ To add lists, add entry by entry: $(3,1)+(-1,2)=(2,3).$ These are the same operation.
• Scale. To multiply an arrow by a number $c,$ stretch it by the factor $c,$ turning it around if $c$ is negative. To multiply a list by $c,$ multiply every entry: $1.5(3,1)=(4.5,1.5).$ Again, the same operation. The numbers we scale by are called scalars.

An expression built from these two operations, such as $2\mathbf{u}-3\mathbf{v},$ or $a\mathbf{u}+b\mathbf{v}$ for numbers $a$ and $b,$ is called a linear combination of $\mathbf{u}$ and $\mathbf{v}.$ Linear combinations are the sentences of linear algebra. Almost everything that follows is about which vectors can be written as linear combinations of which others.

The rules of the game

Arrows are not the only things that can be added and scaled. Polynomials can: $(x^2+1)+(3x-1)=x^2+3x.$ So can sound waves, temperature maps and, as we will see in a moment, sets of edges in a network. Rather than develop a separate theory for each, mathematicians list the rules that adding and scaling always obey, and call anything that obeys them a vector space. Every theorem proved from the rules then applies to all of these examples at once.

First we must say which numbers we may scale by. We want to add, subtract and multiply them, and above all to divide by anything except zero, with all the familiar rules of arithmetic still true.

The rational numbers $\mathbb{Q}$ (fractions) and the real numbers $\mathbb{R}$ are fields. The integers $\mathbb{Z}$ are not a field: the number $2$ has no reciprocal among the integers, because $\frac{1}{2}$ is not a whole number. Keep that failure in mind. It returns at the end of the chapter, where it is responsible for torsion.

Read slowly, the definition says only this: you can add vectors and scale them, and none of the usual algebra goes wrong. ${\mathbb{R}}^n$ is a vector space over $\mathbb{R},$ and ${\mathbb{Q}}^n,$ lists of fractions, is one over $\mathbb{Q}.$ Meet one non-example now, because it will matter later: the grid points ${\mathbb{Z}}^2,$ pairs of integers, can be added and form an abelian group (the free abelian group of §1.4 Abelian Groups and Formal Sums), but scaling by $\frac{1}{2}$ knocks $(1,0)$ off the grid. So ${\mathbb{Z}}^2$ is not a vector space over $\mathbb{Q}$ or $\mathbb{R}.$

Vectors that are switches: the field $\mathbb{Z}/2$

Now for a field you may not have met. In §1.3 Groups you saw clock arithmetic with two hours, $\mathbb{Z}/2=\left\{0,1\right\}$ (read “Z mod 2”), in which $1+1=0.$ Think “odd plus odd is even”. Multiplication is the obvious one: $0\cdot 0=0\cdot 1=0$ and $1\cdot 1=1.$ This tiny number system is a field, because its only nonzero number is $1,$ whose reciprocal is $1$ itself. So it is a perfectly good choice of scalars. Many books write it ${\mathbb{F}}_2,$ read “F-two”, the F standing for field; in this book we write $\mathbb{Z}/2.$

A vector over $\mathbb{Z}/2$ is a list of 0s and 1s, such as $(1,0,1,1,0,0).$ Picture it as a row of six switches, or as the set of positions that are switched on: label the positions $a,b,c,d,e,f,$ and this vector is the set $\left\{a,c,d\right\}.$ Adding two such vectors entry by entry, with $1+1=0,$ switches on exactly the positions that are on in one vector or the other but not in both. For sets this operation has a name: the symmetric difference.

Two features of $\mathbb{Z}/2$ are worth savouring. First, $\mathbf{v}+\mathbf{v}=0$ for every vector, so $-\mathbf{v}=\mathbf{v}:$ there are no minus signs, ever. Second, there are only finitely many vectors. Each of the $n$ entries is 0 or 1, so the space $(\mathbb{Z}/2{)}^n$ of lists of $n$ bits has exactly $2^n$ elements.

Both features are visible in Lights Out. A board is a list of 25 bits (on or off), so the boards form the vector space $(\mathbb{Z}/2{)}^{25}.$ A plan of presses, saying which buttons to press, is also a list of 25 bits, because the order of presses does not matter and pressing a button twice is the same as not pressing it, exactly as $1+1=0.$ Lights Out lives entirely in $\mathbb{Z}/2.$

Span, independence, basis, dimension

Given a few vectors, what can you build from them? That question organises the next four definitions.

Two pieces of notation appear here. In this set-builder notation the vertical bar is read “such that”: the span is the set of all sums such that the $a_i$ are scalars. And ${\sum }_i{a}_i{\mathbf{v}}_i,$ with a capital sigma, is shorthand for the sum $a_1{\mathbf{v}}_1+\cdots +a_k{\mathbf{v}}_k:$ “add up $a_i{\mathbf{v}}_i$ over all values of $i”.$ The span of a single nonzero vector $\mathbf{v}$ consists of its multiples $c\mathbf{v}:$ a line through the origin. The span of two vectors pointing in different directions is the whole plane, because any point can be reached by going some distance along one and then some distance along the other. But if the second vector lies on the line of the first, it adds nothing new, and the span is still only a line.

A span is always a subspace: a subset of a vector space that contains $0$ and is closed under addition and scaling, meaning that adding or scaling its vectors never leads out of it. In the plane the subspaces are the origin on its own, the lines through the origin, and the whole plane. A line that misses the origin is not a subspace, since it does not contain $0.$ Neither is the union of two different lines through the origin: add a vector from each line and you land on neither.

The right-hand panel shows waste: $\mathbf{w}$ is redundant. Redundancy has a precise form. There, $\mathbf{w}=-\frac{3}{4}\mathbf{v},$ so $\frac{3}{4}\mathbf{v}+\mathbf{w}=0:$ a combination of the vectors whose coefficients are not all zero produces the zero vector.

Dependent vectors always contain a redundant one. If $a_1{\mathbf{v}}_1+\cdots +a_k{\mathbf{v}}_k=0$ with, say, $a_j\ne 0,$ move $a_j{\mathbf{v}}_j$ to the other side and divide by $a_j$ (division, the field property, at work): this writes ${\mathbf{v}}_j$ as a combination of the others. For example, $(1,0)$ and $(0,1)$ are independent, while $(1,2)$ and $(2,4)$ are dependent, because $2(1,2)-(2,4)=(0,0).$

Over $\mathbb{Z}/2,$ the three vectors $(1,1,0),$ $(0,1,1)$ and $(1,0,1)$ are dependent: their sum is $(0,0,0),$ because each position is switched on exactly twice. Remember this little dependency. If the three positions are the corners of a triangle, and each vector is an edge (recorded as the set of its two endpoints), the dependency says that the three edges together close up into a loop: every corner is touched twice. Loops in this sense are what homology counts.

Two facts make this definition work. First, given a basis ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n,$ every vector can be written as $a_1{\mathbf{v}}_1+\cdots +a_n{\mathbf{v}}_n$ in exactly one way. There is at least one way, because a basis spans; and if there were two different ways, subtracting one from the other would give a combination equal to $0$ with coefficients not all zero, which independence forbids. The numbers $a_1,\dots ,a_n$ are the coordinates of the vector in that basis. Second, every basis of a given space has the same number of vectors. This is a genuine theorem, which we shall use without proof: an independent list is never longer than a spanning list, a fact often proved by an exchange lemma that swaps the vectors of one list into the other one at a time (Axler 2024, 2.22 and 2.34). It also shows that in a space of dimension $n,$ any $n+1$ vectors are dependent. So “the dimension” is well defined: it counts the degrees of freedom, the number of independent numbers you need to pin down a vector.

The standard basis of ${\mathbb{R}}^2$ is ${\mathbf{e}}_1=(1,0),$ ${\mathbf{e}}_2=(0,1),$ and in general $\dim {\mathbb{R}}^n=n.$ A line through the origin has dimension 1, a plane through the origin dimension 2, and the space $\left\{0\right\}$ dimension 0 (its basis is the empty list). Over $\mathbb{Z}/2,$ $\dim (\mathbb{Z}/2{)}^n=n,$ with a basis made of the lists that contain a single 1. A subspace of dimension $d$ over $\mathbb{Z}/2$ contains exactly $2^d$ vectors, one for each choice of its $d$ coordinates.

Linear maps: transformations that keep the grid

A vector space on its own just sits there. The action is in the functions between spaces, and the ones that matter here are those that respect adding and scaling. Picture the plane covered by a square grid, and imagine moving every point of the plane somewhere else. Most ways of doing this crumple the grid. The linear ones keep it a grid: lines stay straight, parallel lines stay parallel, evenly spaced lines stay evenly spaced, and the origin stays where it is. Such a map may rotate, stretch, shear, reflect or even flatten the plane, but it never bends anything.

Here $T:V\to W$ is read “T, from V to W”: $V$ is the domain, where the inputs live, and $W$ is the codomain, where the outputs live, as in §1.1 Sets and Functions. Taking $c=0$ shows that $T(0)=0:$ a linear map always fixes the origin. Combining the two rules gives $T(a\mathbf{u}+b\mathbf{v})=aT(\mathbf{u})+bT(\mathbf{v}):$ linear maps turn linear combinations into linear combinations. In particular a linear map is a homomorphism of the underlying abelian groups, as in §1.3 Groups, which in addition respects scaling.

Here is the fact that makes linear maps easy to handle: a linear map is completely determined by what it does to a basis. In the plane every vector is $x{\mathbf{e}}_1+y{\mathbf{e}}_2,$ so $$T(x{\mathbf{e}}_1+y{\mathbf{e}}_2)=xT({\mathbf{e}}_1)+yT({\mathbf{e}}_2).$$ Know where the two basis vectors land and you know where everything lands. So we record the two landing spots side by side, as the columns of a table of numbers. That table is the matrix of $T.$

Multiplying a matrix by a vector

A matrix with $m$ rows and $n$ columns, an “$m\times n$ matrix” (read “m by n”), describes a linear map ${\mathbb{R}}^n\to {\mathbb{R}}^m,$ with $n$ inputs and $m$ outputs. Its columns are the images of ${\mathbf{e}}_1,\dots ,{\mathbf{e}}_n,$ so they live in the codomain ${\mathbb{R}}^m.$ The entry in row $i$ and column $j$ is written $a_{ij}.$ To apply the map to a vector $\mathbf{x},$ take that combination of the columns: if ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_n$ are the columns, then $$A\mathbf{x}=x_1{\mathbf{a}}_1+x_2{\mathbf{a}}_2+\cdots +x_n{\mathbf{a}}_n.$$ For example, $$\begin{array}{rl}\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right)\left(\begin{array}{c}3\\ -1\end{array}\right)& =3\left(\begin{array}{c}1\\ 2\end{array}\right)-1\left(\begin{array}{c}2\\ 4\end{array}\right)\\ & =\left(\begin{array}{c}1\\ 2\end{array}\right).\end{array}$$ The same answer comes out row by row: entry $i$ of $A\mathbf{x}$ is $a_{i1}{x}_1+\cdots +a_{in}{x}_n,$ the dot product of row $i$ with $\mathbf{x}.$ Here $1\cdot 3+2\cdot (-1)=1$ and $2\cdot 3+4\cdot (-1)=2.$ The row way is how most people compute by hand; the column way is the one that explains things.

One number summarises how a map of the plane changes areas. The unit square, spanned by ${\mathbf{e}}_1$ and ${\mathbf{e}}_2,$ goes to the parallelogram spanned by the two columns. Its area, with a sign attached, is the determinant $$\det \left(\begin{array}{cc}a& b\\ c& d\end{array}\right)=ad-bc.$$ Every region’s area is multiplied by $\left|\det A\right|.$ The sign is negative when the map flips the plane over, like a mirror. And $\det A=0$ exactly when the parallelogram is squashed flat, which happens exactly when the two columns lie on one line, that is, when they are linearly dependent. (Determinants exist for square matrices of every size, where they measure volumes, but we will need only the $2\times 2$ case.)

Volumes lead to one of the oldest open questions about matrices. Fill a square table with $+1$s and $-1$s: how large can its determinant be? Think of the rows as the edges of a box. A box with edges of given lengths has the largest volume when its edges are perpendicular, and two rows are perpendicular when their dot product is $0.$ For $2\times 2$ tables the best is $\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),$ whose rows have dot product $1-1=0$ and whose determinant is $-2.$ Jacques Hadamard proved in 1893 that an $n\times n$ table of $\pm 1$s has $\left|\det \right|\le n^{n/2},$ with equality exactly when every two rows are perpendicular (Hadamard 1893). Tables like that are now called Hadamard matrices, and they are used to build error-correcting codes.

Everything works the same way over $\mathbb{Z}/2:$ a matrix is a table of 0s and 1s, and the arithmetic uses $1+1=0.$ Lights Out is our example. Pressing the buttons of a plan $\mathbf{x}$ changes the board by the sum of the effects of the individual buttons, because each light ends up switched once for each pressed button that touches it, and only the parity of that count matters. So “plan of presses $\mapsto$ change of lights” (the arrow $\mapsto$ is read “goes to”) is a linear map $(\mathbb{Z}/2{)}^{25}\to (\mathbb{Z}/2{)}^{25}.$ Its matrix $A$ is $25\times 25,$ and column $j$ is the plus-shaped pattern of lights switched by button $j.$ The figure in the Lights Out section below can show you this matrix.

Matrix multiplication is composition

Apply one linear map and then another: $\mathbf{x}\mapsto B\mathbf{x}\mapsto A(B\mathbf{x}).$ The result is again linear, so it has a matrix, which we call the product $AB.$ Since the columns of a matrix are the images of the basis vectors, column $j$ of $AB$ is $A$ applied to column $j$ of $B.$ Working this out entry by entry gives the familiar rule $$(AB{)}_{ij}=a_{i1}{b}_{1j}+a_{i2}{b}_{2j}+\cdots +a_{ik}{b}_{kj},$$ row $i$ of $A$ times column $j$ of $B.$ The sizes must fit: an $m\times k$ matrix times a $k\times n$ matrix is an $m\times n$ matrix, because the $k$ outputs of $B$ must be the $k$ inputs of $A.$

Notice the order. $AB$ means “first $B,$ then $A”,$ just like the composition $g\circ f$ of §1.1 Sets and Functions, read “g after f”. And order matters. With the rotation $R$ and the shear $S$ from the zoo, $$RS=\left(\begin{array}{cc}0& -1\\ 1& 1\end{array}\right)\ne \left(\begin{array}{cc}1& -1\\ 1& 0\end{array}\right)=SR:$$ shearing and then rotating is not the same as rotating and then shearing. The matrix that does nothing, with 1s down the diagonal and 0s elsewhere, is the identity matrix $I.$

Same dimension, same space

A linear map that is also a bijection is called an isomorphism. It pairs off the vectors of two spaces one for one and respects adding and scaling, so the two spaces are really one space with its vectors renamed. Coordinates hand us an isomorphism for free. If ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ is a basis of a space $V$ over a field $F,$ the map $F^n\to V,$ $(a_1,\dots ,a_n)\mapsto a_1{\mathbf{v}}_1+\cdots +a_n{\mathbf{v}}_n,$ is linear, and it is a bijection because every vector has exactly one list of coordinates. So every vector space of dimension $n$ is a copy of $F^n$. Two spaces over the same field are isomorphic exactly when they have the same dimension (an isomorphism carries a basis to a basis, so it cannot change the count). The polynomials $a+bx,$ the pairs $(a,b)$ and the arrows in the plane are one space in three costumes. For homology this is excellent news: over a field, each homology group will be pinned down completely by a single number, its dimension (§3.4 Computing Homology).

Kernel and image: what is crushed, what is reached

Every question about Lights Out is a question about two subspaces that come with any linear map. One lives in the domain and records what the map loses. The other lives in the codomain and records what the map can do.

Both are subspaces. If $A\mathbf{x}=0$ and $A\mathbf{y}=0,$ then $A(\mathbf{x}+\mathbf{y})=0+0=0$ and $A(c\mathbf{x})=c0=0,$ so the kernel is closed under adding and scaling; the image is similar. You met kernels and images of homomorphisms in §1.3 Groups. A linear map is a homomorphism, and these are the same kernel and image, now with dimensions attached.

The kernel deserves several pictures, because homology will lean on all of them.

• What gets crushed. The kernel is everything the map squashes onto the origin: the gold line in the playground above.
• Solutions of the homogeneous equation. The kernel is the set of solutions of $A\mathbf{x}=0,$ the equation with nothing on the right-hand side; “homogeneous” means exactly that.
• Quiet patterns. In Lights Out, the kernel is the set of plans of presses that change nothing at all. The $5\times 5$ board has a few of these, and they are the reason that not every board is solvable.

The image also has a concrete description. Since $A\mathbf{x}$ is a combination of the columns of $A,$ the image is the span of the columns, which is why it is also called the column space; the rank is the number of independent columns. In Lights Out, the image is the set of boards you can produce from the dark board by pressing buttons. Since pressing the same buttons again undoes them, it is exactly the set of boards that can be switched off: the solvable boards.

The kernel tells you exactly how much information a map destroys. If $A\mathbf{x}=A\mathbf{y},$ then $A(\mathbf{x}-\mathbf{y})=0,$ so $\mathbf{x}-\mathbf{y}$ lies in the kernel. Conversely, adding a kernel vector to an input never changes the output. So $A$ is injective (different inputs give different outputs) exactly when $\ker A=\left\{0\right\},$ and $A$ is surjective (every output is reached) exactly when $\mathrm{im}A$ is all of $W.$

Here is a picture that ties kernel and image together: a linear map from space to itself, of rank 2. It works like a shadow cast by slanted sunlight. Every point slides along one fixed direction until it reaches the floor.

Count dimensions in the picture. Space has 3. The floor, which is the image, has 2. The line that collapses, the kernel, has 1. And $3=2+1.$ That is no coincidence.

Rank–nullity already answers questions without any computation. A linear map ${\mathbb{R}}^5\to {\mathbb{R}}^3$ can never be injective: its rank is at most 3, so its nullity is at least $5-3=2.$ A linear map ${\mathbb{R}}^3\to {\mathbb{R}}^5$ can never be surjective: its rank is at most 3, short of 5. And a map from a finite-dimensional space to itself is injective exactly when it is surjective, since nullity 0 means rank equal to the full dimension.

Row reduction: the universal tool

So far we have found kernels by staring. That works for $2\times 2$ matrices and fails long before $25\times 25.$ We need a mechanical procedure that computes ranks, kernels and images of any matrix, over any field. It is called row reduction, or Gaussian elimination, and it is the same elimination you may have used at school to solve two equations in two unknowns.

A matrix stands for a system of equations. The matrix with rows $(1,2,1,3),$ $(2,4,0,2)$ and $(3,6,1,5)$ stands for the homogeneous system $$\begin{array}{rl}{x}_1+2x_2+x_3+3x_4& =0,\\ 2x_1+4x_2+2x_4& =0,\\ 3x_1+6x_2+x_3+5x_4& =0,\end{array}$$ whose solutions form the kernel. We may change the system in three ways without changing its solutions:

1. swap two rows (list the equations in a different order);
2. scale a row by a nonzero number (multiply an equation through);
3. add a multiple of one row to another (add a multiple of one equation to another).

Each operation can be undone by another of the same kind: swap back, scale by the reciprocal, subtract what you added. So no solution is ever created or lost, and the kernel does not change. Then, by rank–nullity, the rank (the number of columns minus the nullity) does not change either.

The goal is a staircase called the reduced row echelon form. Each nonzero row begins with a 1, called a pivot; each pivot sits to the right of the pivot above it; and each pivot is the only nonzero entry in its column. The recipe:

1. Go through the columns from left to right, keeping track of the first row that does not have a pivot yet.
2. In the current column, look for a nonzero entry in that row or below it. If there is none, the column gets no pivot: move on to the next column.
3. Otherwise, swap that entry’s row up into place and divide the row by the entry, so that the pivot is 1.
4. Subtract multiples of the pivot row from every other row to make the rest of the column 0. Then move on to the next row and the next column.

Let us run it on the system above. Column 1 already has a 1 in row 1, so we clear the rest of the column with $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3-3R_1$ (read: “replace row 2 by row 2 minus twice row 1”, and so on): $$\left(\begin{array}{cccc}1& 2& 1& 3\\ 2& 4& 0& 2\\ 3& 6& 1& 5\end{array}\right)\to \left(\begin{array}{cccc}1& 2& 1& 3\\ 0& 0& -2& -4\\ 0& 0& -2& -4\end{array}\right).$$ Column 2 has only zeros below row 1, so it gets no pivot. In column 3, the entry $-2$ in row 2 becomes a pivot after $R_2\leftarrow -\frac{1}{2}{R}_2,$ and then $R_1\leftarrow R_1-R_2$ and $R_3\leftarrow R_3+2R_2$ clear its column: $$\to \left(\begin{array}{cccc}1& 2& 1& 3\\ 0& 0& 1& 2\\ 0& 0& -2& -4\end{array}\right)\to \left(\begin{array}{cccc}1& 2& 0& 1\\ 0& 0& 1& 2\\ 0& 0& 0& 0\end{array}\right).$$ Column 4 has only a zero in the one remaining row, so it gets no pivot. Done: two pivots, in columns 1 and 3. You can replay every step in the figure.

Now read off the answers from the staircase.

• Rank = the number of pivots, here 2.
• Kernel. The columns without pivots belong to free variables, here $x_2$ and $x_4,$ which may take any values. The pivot rows then determine the rest: $x_1=-2x_2-x_4$ and $x_3=-2x_4.$ Setting one free variable to 1 and the others to 0 gives one kernel vector for each free variable, $$\begin{array}{rl}{x}_2=1,x_4=0& :(-2,1,0,0),\\ x_2=0,x_4=1& :(-1,0,-2,1),\end{array}$$ and these form a basis of the kernel. The nullity is the number of free variables, 2.
• Image. The pivot columns of the original matrix, here $(1,2,3)$ and $(1,0,1),$ form a basis of the image.
• Check. 4 columns = 2 pivot columns + 2 free columns. Rank–nullity is visible in the staircase.

Row reduction over $\mathbb{Z}/2$

Over $\mathbb{Z}/2$ the procedure is even simpler. The only nonzero number is 1, so there is never anything to divide by, and adding a row is the same as subtracting it. Row reduction becomes: find a 1, swap it into place, and add its row to every other row that has a 1 in that column. Here is the “triangle matrix”, whose columns are the three edges of a triangle, each edge recorded by its two corners: $$\begin{array}{rl}\left(\begin{array}{ccc}1& 1& 0\\ 1& 0& 1\\ 0& 1& 1\end{array}\right)& \stackrel{R_2\leftarrow R_2+R_1}{\to }\left(\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\\ 0& 1& 1\end{array}\right)\\ & \stackrel{\begin{array}{c}{R}_1\leftarrow R_1+R_2\\ R_3\leftarrow R_3+R_2\end{array}}{\to }\left(\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\\ 0& 0& 0\end{array}\right).\end{array}$$ Rank 2. The free variable $x_3$ gives the kernel vector $(1,1,1):$ all three edges together, the loop around the triangle. The kernel is $\left\{(0,0,0),(1,1,1)\right\}.$

Now switch the stepper to $\mathbb{Q},$ keeping the same matrix: it has rank 3, and its kernel is only $0.$ The same table of numbers can have different ranks over different fields. Here the culprit is the determinant of this $3\times 3$ matrix, which is $-2:$ that is not zero in $\mathbb{Q},$ but it is zero in $\mathbb{Z}/2.$ It is our first glimpse of something the last section explains: the number 2 behaves very differently in different number systems. (The signed version of the matrix, with $-1$s, which is the one homology will use, has rank 2 over both.)

Solving $A\mathbf{x}=\mathbf{b}$

Kernels answer the question “which inputs give zero?”. Most real questions ask instead: given a target $\mathbf{b},$ which inputs give $\mathbf{b}?$ In Lights Out, $\mathbf{b}$ is the board in front of you, and you want a plan $\mathbf{x}$ with $A\mathbf{x}=\mathbf{b}.$ Pressing $\mathbf{x}$ adds $A\mathbf{x}$ to the board, and $\mathbf{b}+\mathbf{b}=0$ over $\mathbb{Z}/2,$ so the board goes dark exactly when $A\mathbf{x}=\mathbf{b}.$ Two questions: is there a solution, and if so, how many?

Existence is a matter of definitions: there is a solution exactly when $\mathbf{b}$ lies in the image of $A.$

How many is answered by the kernel. Suppose ${\mathbf{x}}_p$ is one solution, a particular solution. If $\mathbf{k}$ is in the kernel, then $A({\mathbf{x}}_p+\mathbf{k})=\mathbf{b}+0=\mathbf{b},$ so ${\mathbf{x}}_p+\mathbf{k}$ is a solution too. Conversely, if $A\mathbf{x}=\mathbf{b},$ then $A(\mathbf{x}-{\mathbf{x}}_p)=\mathbf{b}-\mathbf{b}=0,$ so $\mathbf{x}$ is ${\mathbf{x}}_p$ plus a vector of the kernel. Therefore $$\left\{\mathbf{x}|A\mathbf{x}=\mathbf{b}\right\}={\mathbf{x}}_p+\ker A,$$ a copy of the kernel slid over to pass through ${\mathbf{x}}_p.$ In the language of §1.4 Abelian Groups and Formal Sums, the solution set is a coset of the kernel. All solutions differ by something invisible to $A.$

So over $\mathbb{R}$ or $\mathbb{Q}$ there are exactly three possibilities: no solution ($\mathbf{b}$ is not in the image), exactly one (the kernel is $\left\{0\right\}),$ or infinitely many (the kernel is a line or bigger). Over $\mathbb{Z}/2$ the count is finite: a kernel of dimension $d$ has $2^d$ elements, so a solvable equation has exactly $2^d$ solutions.

In practice we find solutions by row reducing the augmented matrix $[A\mid \mathbf{b}]:$ the matrix $A$ with $\mathbf{b}$ attached as an extra column, doing every operation to both. If a row of the form $[0\cdots 0\mid 1]$ appears, it says “$0=1”,$ and there is no solution. Otherwise, set the free variables to 0 and read off a particular solution.

Quotient spaces: blurring out a subspace

In the last figure, all the points of one dashed gold line are “the same” as far as $A$ is concerned, since $A$ sends them all to the same $\mathbf{b}.$ It is natural to treat each such line as a single object. You have done this kind of thing twice already: in §1.2 Equivalence and Quotients you formed quotient sets by declaring equivalent things equal, and in §1.4 Abelian Groups and Formal Sums you formed quotient groups $G/H$ by collapsing a subgroup. Vector spaces have quotients too, and they are where homology lives.

As with quotient groups, we must check that these operations are well defined: if we pick different representatives of the same cosets, the answer must not change. It does not, because $W$ is closed under adding and scaling. Changing $\mathbf{u}$ and $\mathbf{v}$ by elements of $W$ changes $\mathbf{u}+\mathbf{v}$ and $c\mathbf{v}$ by elements of $W$ too. So $V/W$ is again a vector space, and its zero is the coset $0+W,$ which is $W$ itself.

The figure illustrates the general rule. A quotient forgets the directions inside $W$ and remembers the rest, so dimensions subtract: $$\dim V/W=\dim V-\dim W.$$ To see it, extend a basis ${\mathbf{w}}_1,\dots ,{\mathbf{w}}_m$ of $W$ to a basis of $V$ by adding vectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_r;$ then the cosets ${\mathbf{v}}_1+W,\dots ,{\mathbf{v}}_r+W$ form a basis of $V/W$ (Axler 2024, 3.105). Over $\mathbb{Z}/2$ you can even count: the cosets split $V$ into pieces of $2^{\dim W}$ vectors each, so $V/W$ has $2^{\dim V}/2^{\dim W}$ elements. For instance, $(\mathbb{Z}/2{)}^3$ modulo $\left\{000,111\right\}$ has $8/2=4$ elements.

Look back at the shadow figure with this in mind. Each thin pale gold line, parallel to the kernel, is a coset of the kernel, and the map squashes each of them to a single point of the floor. Different lines land on different points, and every point of the floor is hit. So the cosets of the kernel correspond exactly to the points of the image: $$V/\ker A\cong \mathrm{im}A,$$ where $\cong$ is read “is isomorphic to”: sending each coset $\mathbf{v}+\ker A$ to $A\mathbf{v}$ is a linear bijection. This is the first isomorphism theorem of §1.4 Abelian Groups and Formal Sums, for vector spaces. Take the dimensions of both sides and you get $\dim V-\mathrm{nullity}A=\mathrm{rank}A:$ rank–nullity again, seen from a new angle.

Lights Out, solved

We now have every tool needed to settle the puzzle. Translate it into linear algebra over $\mathbb{Z}/2:$

• a board is a vector $\mathbf{b}$ in $(\mathbb{Z}/2{)}^{25},$ with 1 for on;
• a plan of presses is a vector $\mathbf{x}$ in $(\mathbb{Z}/2{)}^{25},$ with 1 for press;
• the effect of a plan is $A\mathbf{x},$ where column $j$ of the $25\times 25$ matrix $A$ is the plus-shaped set of lights around button $j;$
• the board can be switched off exactly when $A\mathbf{x}=\mathbf{b}$ has a solution.

Row reducing $A$ over $\mathbb{Z}/2$ takes a long afternoon by hand and a millisecond by machine. (This book’s code does it, and its tests check every number in this section.) The result is: rank 23, nullity 2. Everything else follows from the theorems we have proved.

1. Quiet patterns. The kernel has dimension 2, so it has $2^2=4$ elements: “press nothing” and three non-trivial quiet patterns, plans that leave every light exactly as it was. Show them in the figure below and press one: nothing changes, because every light is switched an even number of times.
2. Solvable boards. The image has dimension 23, so exactly $2^{23}$ of the $2^{25}$ boards are solvable: one board in four.
3. Number of solutions. The solutions of a solvable board form a coset of the kernel, so every solvable board has exactly 4 solutions. The figure’s solver uses the one with the fewest presses. The board with every light on, for instance, is solvable, and its shortest solution takes 15 presses.

Other sizes behave differently, and the figure lets you compare. On the $3\times 3$ board the matrix has rank 9 and nullity 0. There are no quiet patterns, so every board is solvable, in exactly one way. On the $4\times 4$ board the nullity is 4: sixteen quiet patterns, and only one board in sixteen is solvable. For $n\times n$ boards with $n=1,2,\dots ,9$ the nullities are $0,0,0,4,2,0,0,0,8,$ and the sequence continues irregularly: $0,6,0,0,4,0,8,2,\dots$ (OEIS 2009).

Duality: measurements and reversed arrows

One question is still open. When a board is not solvable, how can we be sure? “A computer row reduced a big matrix” is convincing, but it does not explain anything. We would like a certificate: a short reason that anyone can check by hand.

Certificates of impossibility

Here is one. Look at the twelve cells in columns 1, 3 and 5 of the board, leaving out the middle row: the cells of “check 1” in the Lights Out figure above. Every button’s plus shape covers an even number of these cells, either 0 or 2; check a few. So every press changes the number of lit lights among those twelve cells by an even amount, and the parity of that number, even or odd, never changes however you press. The dark board has 0 lights on there, an even number. So a board with an odd number of lit lights among those cells can never be switched off. Checking that takes ten seconds, however many plans of presses there are.

The count we just used is a linear measurement of the board: add up the bits in those twelve positions, in $\mathbb{Z}/2.$ Measuring the sum of two boards gives the sum of the two measurements, so this is a linear map from $(\mathbb{Z}/2{)}^{25}$ to $\mathbb{Z}/2.$ The certificate worked because the measurement gives 0 on everything the buttons can make, but not on our board. Measurements like this deserve a name and a space of their own.

Covectors: the dual space

($\phi$ and $\psi$ are the Greek letters phi and psi.) On ${\mathbb{R}}^2,$ every covector has the form $\phi (x,y)=ax+by$ for two numbers $a$ and $b,$ because, like any linear map, it is determined by its values on ${\mathbf{e}}_1$ and ${\mathbf{e}}_2.$ Its matrix is a single row, $\left(\begin{array}{cc}a& b\end{array}\right),$ and measuring a vector means multiplying that row by the column $\mathbf{v}.$ So vectors are columns and covectors are rows. On ${\mathbb{R}}^n$ a covector is a row of $n$ numbers, so $\dim V^{\ast }=\dim V$ for finite-dimensional spaces, which are the only ones we use.

How should we picture a covector? Not as an arrow. Draw instead the places where it takes the values $\dots ,-1,0,1,2,\dots .$ For $\phi (x,y)=ax+by$ these are evenly spaced parallel lines: a stack. The value $\phi (\mathbf{v})$ is the level that the tip of $\mathbf{v}$ reaches, starting from line 0 at its tail: it counts the lines the arrow crosses (with a sign, negative if it goes down the numbering), plus a fraction for the last partial step. The covector is a ruler, and the lines are its marks.

Given a basis ${\mathbf{e}}_1,\dots ,{\mathbf{e}}_n$ of $V,$ the most useful covectors are the coordinate readers: ${\mathbf{e}}_i^{\ast }$ reads off the $i$-th coordinate. They satisfy ${\mathbf{e}}_i^{\ast }({\mathbf{e}}_j)=1$ when $i=j$ and $0$ otherwise, and they form a basis of $V^{\ast },$ called the dual basis. On ${\mathbb{R}}^2$ with the standard basis, ${\mathbf{e}}_1^{\ast }(x,y)=x$ and ${\mathbf{e}}_2^{\ast }(x,y)=y.$

The transpose: pulling measurements back

Linear maps act on measurements too, but backwards. Suppose $A:V\to W,$ and $\phi$ is a measurement on $W.$ Then “first apply $A,$ then measure with $\phi ”$ is a measurement on $V:$ the composite $\phi \circ A.$ So $A$ gives a map going the other way, $$A^{\mathsf{T}}:W^{\ast }\to V^{\ast },$$$$\phi \mapsto \phi \circ A,$$ called the transpose, or dual map, of $A.$ The arrow reverses: $A$ carries vectors forward from $V$ to $W,$ and $A^{\mathsf{T}}$ carries measurements back from $W$ to $V.$ We say that $A^{\mathsf{T}}$ pulls back $\phi .$

In matrices: if $\phi$ is the row $\mathbf{y},$ then $\phi \circ A$ is the row $\mathbf{y}A.$ Written as a column, that is $A^{\mathsf{T}}\mathbf{y},$ where $A^{\mathsf{T}}$ is the matrix $A$ flipped across its diagonal: the entry in row $i$ and column $j$ of $A^{\mathsf{T}}$ is the entry in row $j$ and column $i$ of $A.$ So the transpose you may know as “swap rows and columns” is exactly the act of pulling measurements back.

Because the arrows reverse, so does the order of composition. Applying $B$ and then $A$ to vectors means pulling measurements back along $A$ first and then along $B:$ $$(AB{)}^{\mathsf{T}}=B^{\mathsf{T}}{A}^{\mathsf{T}}.$$ Think of socks and shoes: you put on your socks and then your shoes, but you take off your shoes and then your socks. One more fact, which row reduction makes visible: $\mathrm{rank}{A}^{\mathsf{T}}=\mathrm{rank}A.$ The rank of $A^{\mathsf{T}}$ is the number of independent rows of $A.$ Row operations do not change the span of the rows, and in the reduced row echelon form the nonzero rows, one per pivot, are visibly independent. So the number of independent rows is the number of pivots, which is $\mathrm{rank}A.$

Which targets can be reached?

Now we can state the theorem the Lights Out certificate was hinting at. If $\mathbf{b}=A\mathbf{x}$ can be reached, then any measurement $\phi$ that is blind to everything $A$ produces, meaning $\phi \circ A=0,$ or $A^{\mathsf{T}}\phi =0,$ is also blind to $\mathbf{b}.$ The surprise is the converse: if no such measurement sees $\mathbf{b},$ then $\mathbf{b}$ can be reached. Whenever something is impossible, a certificate of its impossibility exists.

In the figure on solving equations, the measurement $y(u,v)=2u-v$ gives 0 on both columns of $A=\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right),$ so $A^{\mathsf{T}}y=0,$ and every $\mathbf{b}$ with $y(\mathbf{b})\ne 0$ is out of reach. The theorem adds that when every such measurement gives 0, as it does on the teal line, a solution exists.

Over $\mathbb{R}$ you may have met this theorem in another costume. Tip every row over into a column, and it says that the column space of $A$ and the null space of $A^{\mathsf{T}}$ are perpendicular and together fill the codomain: half of what Gilbert Strang calls the fundamental theorem of linear algebra (Strang 1993). The version with measurements needs no angles, which is why it also works over $\mathbb{Z}/2;$ Axler (2024, 3.128) proves it in the same language.

For Lights Out the theorem becomes concrete, thanks to a symmetry: button $i$ switches light $j$ exactly when button $j$ switches light $i,$ since both say that the two cells are equal or neighbours. So the matrix equals its own transpose, $A^{\mathsf{T}}=A,$ and the measurements that are blind to every button are exactly the measurements “add up the lights in a quiet pattern”. Two quiet patterns span the kernel, so:

The third non-trivial quiet pattern is the sum of these two, so its check is the sum of their checks and tells us nothing new. The cells that belong to neither pattern are the centre and its four diagonal neighbours, and that is why a single light can be switched off on its own exactly there. Notice also the double role of a quiet pattern. As a set of presses, it is an element of the kernel of $A:$ it changes nothing. As a set of cells to count, it is a measurement in the kernel of $A^{\mathsf{T}}:$ it detects unsolvable boards. Only the symmetry $A=A^{\mathsf{T}}$ allows one pattern to play both parts.

The seed of cohomology

Here, in plain words, is why this section matters for the rest of the book. Homology will ask: which cycles are boundaries? That is a question about the image of a boundary map $\partial ,$ exactly like “which boards are solvable?”. Cohomology asks the dual question, with all the arrows reversed. Its objects, called cochains, are measurements on chains, and its basic map, the coboundary, is the transpose $\delta ={\partial }^{\mathsf{T}}.$ A measurement that gives 0 on every boundary but not on some cycle $z$ is a certificate that $z$ is not a boundary, that $z$ goes around a hole, in exactly the way that a parity check certifies that a board can never be switched off.

Linear algebra over $\mathbb{Z}:$ the Smith normal form

Everything so far relied on a field: we divided freely, for instance to turn pivots into 1s. But homology is most informative with integer coefficients. Chains will be formal sums with whole-number coefficients, elements of the free abelian groups of §1.4 Abelian Groups and Formal Sums, and boundary matrices will have integer entries. In $\mathbb{Z}$ we may not divide, and that changes the story.

The smallest example says it all: the $1\times 1$ matrix $(2),$ the map “multiply by 2”.

• Over $\mathbb{Q}$ it is invertible, since its inverse multiplies by $\frac{1}{2}:$ kernel 0, image everything.
• Over $\mathbb{Z}/2$ it is the zero map, because $2=0$ there: kernel everything, image 0.
• Over $\mathbb{Z}$ it is neither. The map $x\mapsto 2x$ is injective, but its image is the even numbers $2\mathbb{Z},$ and the leftover $\mathbb{Z}/2\mathbb{Z}=\mathbb{Z}/2$ is not zero. That leftover is a torsion group: it has a nonzero element, the class of 1, which becomes zero when doubled.

Torsion is information that division destroys. To keep it, we must work with integer operations only.

Which operations are allowed? The integer versions of the row operations, and now the same operations on columns as well:

1. swap two rows, or two columns;
2. multiply a row, or a column, by $-1$ (the only integers with integer reciprocals are $\pm 1);$
3. add an integer multiple of one row to another, or of one column to another.

Each of these can be undone by an operation of the same kind. Row operations change the basis of the codomain ${\mathbb{Z}}^m,$ and column operations change the basis of the domain ${\mathbb{Z}}^n.$ Why allow columns now? Because we are no longer solving one particular equation. We want the structure of the map, its kernel and its cokernel, and we are free to choose convenient bases at both ends. The cokernel of $A:{\mathbb{Z}}^n\to {\mathbb{Z}}^m$ is the quotient ${\mathbb{Z}}^m/\mathrm{im}A:$ the codomain with the image collapsed, “what is left over”.

This diagonal form is the Smith normal form, after the Oxford mathematician Henry John Stephen Smith, who introduced it in 1861 while studying systems of linear equations to be solved in whole numbers (Smith 1861). We abbreviate a diagonal matrix by listing its diagonal, as in $\mathrm{diag}(d_1,\dots ,d_r);$ the symbol $\oplus$ is the direct sum of §1.4 Abelian Groups and Formal Sums, and $\mathbb{Z}/1$ is the group with one element. Reading off the answer is easy once the matrix is diagonal, because the map then does independent things to independent coordinates: it multiplies the $i$-th coordinate by $d_i.$ A factor $d_i=1$ leaves nothing behind, since $\mathbb{Z}/1=0.$ A factor $d_i>1$ leaves the torsion $\mathbb{Z}/d_i.$ And each of the $m-r$ rows without a diagonal entry leaves a whole free copy of $\mathbb{Z}.$

The algorithm imitates row reduction, with division replaced by division with remainder. Move the smallest nonzero entry to the top-left corner. Subtract whole multiples of its row and column to shrink the other entries of that row and column to their remainders. If any remainder is nonzero, it is smaller than the pivot: make it the new pivot and repeat. Since the entries keep shrinking, this stops, leaving the pivot alone in its row and column. Then make sure that the pivot divides every remaining entry (if not, add a row to bring an offending entry into play and clear again), and move on to the rest of the matrix.

This is the algorithm behind the classification theorem of §1.4 Abelian Groups and Formal Sums: every finitely generated abelian group is ${\mathbb{Z}}^r\oplus \mathbb{Z}/d_1\oplus \cdots \oplus \mathbb{Z}/d_k$ with $d_1\mid d_2\mid \cdots .$ (There $r$ is the rank of the group, which is $m$ minus the rank of the relation matrix, and only the factors $d_i\ge 2$ are listed.) Describe the group by generators and relations, write the relations as the columns of a matrix, and the Smith normal form reads off the decomposition. For instance, the group ${\mathbb{Z}}^2/⟨(2,4),(6,8)⟩,$ integer pairs modulo the subgroup generated by $(2,4)$ and $(6,8),$ comes from the matrix with those two columns. Its Smith form is $\mathrm{diag}(2,4),$ so the group is $\mathbb{Z}/2\oplus \mathbb{Z}/4,$ with $8=\left|\det \right|$ elements.

It is also how homology finds torsion. In §2.2 Gluing Spaces Together the Klein bottle is made from a square by gluing its sides according to the word $aba{b}^{-1},$ and in §3.6 Exact Sequences and Mayer–Vietoris it is rebuilt from one vertex, two edges $a,b$ and one face. Walking around the face’s rim reads $a+b+a-b=2a+0b,$ so the boundary matrix is the single column $(2,0),$ already in Smith form with $d_1=2.$ With only one vertex, every combination of edges is a cycle, so the first homology, cycles modulo boundaries, is ${\mathbb{Z}}^2/\mathrm{im}{\partial }_2\cong \mathbb{Z}\oplus \mathbb{Z}/2:$ one ordinary loop, and one loop that becomes a boundary when it is traversed twice. The real projective plane, glued by the word $aa,$ gives the $1\times 1$ matrix $(2)$ and the torsion $\mathbb{Z}/2.$

Finally, the Smith form explains the puzzle of the triangle matrix. Over $\mathbb{Q},$ the rank of an integer matrix is the number of its invariant factors, since each $d_i$ can be divided away. Over $\mathbb{Z}/2,$ the even factors become 0, so the rank is the number of odd invariant factors. The triangle matrix has invariant factors $1,1,2:$ rank 3 over $\mathbb{Q},$ rank 2 over $\mathbb{Z}/2.$ Ranks over $\mathbb{Z}/2$ and over $\mathbb{Q}$ differ exactly when some $d_i$ is even, that is, when there is 2-torsion around. That is why mod-2 homology and rational homology can disagree, and why integer homology, which sees the $d_i$ themselves, knows more than either.

Exercises

Summary

Further reading

• Essence of Linear Algebra — 3Blue1Brown (Grant Sanderson) free

  Sixteen short animated lessons that think of matrices as transformations of a grid. Chapter 7 (column space and null space) and chapter 9 (dot products and duality) match this chapter almost picture for picture. The best first stop.
• Immersive Linear Algebra — J. Ström, K. Åström and T. Akenine-Möller free

  An online textbook in which every figure can be dragged and rotated. Excellent for building geometric intuition in two and three dimensions.
• Interactive Linear Algebra — Dan Margalit and Joseph Rabinoff free

  A complete first course with many small demonstrations. Particularly clear on row reduction and on solution sets as translated null spaces.
• Linear Algebra Done Right (4th edition) — Sheldon Axler free

  A clean, proof-based treatment, open access since its fourth edition. Read it after this chapter for full proofs of the exchange lemma, quotient spaces and duality.
• MIT 18.06 Linear Algebra — Gilbert Strang free

  Strang's famous lecture course. His picture of the 'four fundamental subspaces' of a matrix is the duality theorem of this chapter, drawn as a diagram.
• Turning Lights Out with Linear Algebra — Marlow Anderson and Todd Feil, Mathematics Magazine 71 (1998)

  The short classic article behind our Lights Out section: the puzzle as a linear system over ℤ/2, quiet patterns and all.
• Computing Homology — Jeremy Kun free

  A programmer's walk from boundary matrices to Betti numbers by row and column reduction: this chapter, put to work. Best read alongside Part III.
• Hodge Laplacians on graphs — Lek-Heng Lim free

  An elementary introduction that builds cohomology and Hodge theory on graphs out of nothing but matrices and their transposes. A rewarding read after Part IV.
• Graphical Linear Algebra — Paweł Sobociński free

  A playful blog that rebuilds linear algebra from string diagrams. A very different and eye-opening angle on matrices, kernels and duality.