A matrix is a machine

A machine — a rule that turns each input list into an output list — takes the list (4, 5) and returns the list (13, 19). Nothing in the input announces where the thirteen came from. The machine is described by four numbers arranged in two rows, with 2 and 1 on the first and 1 and 3 on the second.

The section question asks what such a table does to a vector, and the answer is that it produces a new vector by pairing each row with the input. The table is a matrix, a rectangular array of numbers with rows and columns [S:24:83]. Read as a machine rather than as a table of stored data, it is a linear map, which is a rule that turns one list into another while preserving addition and scaling. !Left: each row of the table is paired with (4, 5), giving 2·4 + 1·5 = 13 and 1·4 + 3·5 = 19. Right: the same answer is four copies of the first column (2, 1) plus five copies of the second (1, 3), drawn as the dashed path and the gold sum. The rows compute the answer and the columns explain it, and the two routes cannot disagree. Status: schematic.

The rule is mechanical: take the first row, multiply it entry by entry with the input, and add the results, so two times four plus one times five gives thirteen. Repeat the same pairing with the second row, where one times four plus three times five gives nineteen.

The display says each output entry is one row paired with the input list, so you multiply matching entries and add the resulting products together.

A table of four numbers looks like an arbitrary gadget, and it is not. Feed the machine the two standard basis lists, (1, 0) and (0, 1), and it returns (2, 1) and (1, 3). Those two answers are exactly the columns of the table, and they determine every other answer [S:24:83]. The values a linear map assigns to a basis determine the values it assigns everywhere, because every input is a combination of the basis lists and linearity pushes that combination through [S:24:83]. That is why four numbers can stand in for a rule about every list in the plane.

The two routes to (13, 19) necessarily agree, and observing their agreement is the central idea of the section. The input (4, 5) is four copies of (1, 0) plus five copies of (0, 1). Send the copies through the machine and add the results: four times (2, 1) is (8, 4), five times (1, 3) is (5, 15), and the sum is (13, 19). The row rule and the column picture are the same arithmetic performed in two orders.

The display says the answer is fixed by where the machine sends the two measuring lists, (1, 0) and (0, 1), because the input is constructed from those lists. A second input checks both readings at once: feed (1, 1) and the rows produce (3, 4), while the columns produce (2, 1) + (1, 3) = (3, 4).

A scaled input scales the output. The list (2, 0) is two copies of (1, 0), so the machine sends it to (4, 2), twice the first column. The list (0, 3) is three copies of (0, 1), so it goes to (3, 9), three times the second column.

The columns are therefore the important part of the table. Column one records where (1, 0) goes, column two records where (0, 1) goes, and read this way the table maps a list of coordinates to a list of coordinates [S:27:57]. The rows are a convenient way to compute the same answer, and the two readings never disagree [S:27:58].

Linearity is a strong demand, and it shows first at the origin: sending the zero list through gives zero from every row, so a linear machine must leave the origin where it is. Adding two inputs adds their outputs, and the scaling check above is the other half. A machine that adds one to every entry fails the initial test, because it moves the origin to (1, 1), and no table of the kind above can imitate it.

Two tables are worth recognising by sight. The table with one on the diagonal — the entries running from top-left to bottom-right — and zero everywhere else returns every input unchanged, and the table with two on the diagonal doubles every entry. The table with one in the top-left corner and zeros elsewhere keeps the first entry of the input and discards the second, which is the first hint that a machine can lose information.

The lab for this section, which you can open beside this page, draws a square grid on a rubber sheet, pins the origin, and lets a table move every point of the grid. For an invertible table, straight lines stay straight, parallel lines stay parallel, and the squares become parallelograms. A singular table collapses the grid onto a line or a point, so squares become segments or points; §7.4 meets one. The picture is the machine's action on the whole plane, and the four numbers are enough to describe it because the grid is built from the same two standard basis lists.

The table records only machines that respect scaling and addition, which is a real restriction rather than a technicality. A machine that adds one to every entry is useful and has no matrix, because it shifts the origin and a linear machine cannot. The table is also written against a chosen basis, so the same machine wears different tables under different basis lists, and the next three sections read the table for what it reveals about the machine's inputs and outputs.

The formal statement. Let $V$ and $W$ be vector spaces. A map $T:V\to W$ is linear when $T(u+v)=T(u)+T(v)$ and $T(cu)=cT(u)$ for all $u,v$ in $V$ and every scalar $c$. Fix an ordered basis $B=(b_1,\dots ,b_n)$ of $V$ and an ordered basis $C$ of $W$. The matrix of $T$ in these bases has, as its $j$-th column, the coordinate list of $T(b_j)$ written in the basis $C$ [S:27:57]. Call that matrix $A$. Then for every $x$ in $V$,

$$[T(x){]}_C=A[x{]}_B.$$

The display says the coordinate list of the output is the matrix times the coordinate list of the input, so the table and the map agree everywhere once they agree on a basis.

The derivation. Write $x={\sum }_j{a}_j{b}_j$. Linearity gives $T(x)={\sum }_j{a}_{j}T(b_j)$. Write each $T(b_j)$ in the basis $C$; the coefficients you get are column $j$ of $A$. Collect the coefficient of each $c_i$, and you have row $i$ of $A$ paired with the list of $a_j$. That is the row rule of L1, and the derivation shows it follows from linearity rather than from a convention about tables. The step left out is the existence and uniqueness of coordinates, which is Section 7.2.

Composition is the next consequence. Let $D$ be another matrix of the right shape. Applying the map with matrix $D$ and then the map with matrix $A$ sends $x$ to $A(Dx)$, and the rule for multiplying tables is chosen so that $(AD)x=A(Dx)$ for every $x$. Matrix multiplication is composition written in coordinates.

The edge case. Change the basis of the domain by an invertible $S$ and the table becomes $AS$; change the basis of the output by an invertible $T$ and it becomes $T^{-1}A$. Change both and it becomes $\tilde{A}=T^{-1}AS$ [S:27:60], which for a square map with the same change $P$ on both sides reads $P^{-1}AP$. That is the exact version of L1's remark that the machine "wears different tables under different basis lists", and the lesson is that the same map has many matrices. If you take the four numbers as the machine, you will compare two tables and conclude that the machines differ. In a data table the columns may be measurements in different units, and rescaling a unit is a change of basis: the entries move, the map does not.

What L1 hid. L1 defined the matrix as a table and then read the map off the row rule. The order is the other way. Linearity is the definition, and the table is one representation of it, tied to a choice of bases. L1 also said that a shift has no matrix because it moves the origin. That is right, and the sharper statement is that an affine map is a linear map plus a translation, so it becomes linear only after you append one coordinate fixed at $1$.

Where the analogy breaks. A machine suggests a process with a duration and a cost. A linear map has neither. The table is also not the algorithm: you can compute the same product by rows, by columns or by blocks, and the answers agree while the running times do not.

Where the idea comes from. The correspondence is the transformation matrix. Fix ordered bases of the input and the output, and the $j$-th column of the matrix records the coordinates of the image of the $j$-th basis vector [S:27:57]. Axler supplies the object on its own, as a rectangular array of elements of a field [S:24:83]. Deisenroth, Faisal and Ong state the consequence that L1's column picture uses: the matrix maps coordinates in the input basis to coordinates in the output basis [S:27:58]. The table has one column per input basis vector and one row per output basis vector, so its shape reports the dimensions of the two spaces.

What the field has not settled. The exponent of matrix multiplication. Strassen's algorithm reduces the product of two $n\times n$ matrices to seven products of half the size and runs in $O(n^{2.807355})$ [S:1:335]. As of 2018 the fastest known ran in $O(n^{2.372864})$. Erickson's footnote calls the minimum time a long-standing open problem and records the belief that a nearly quadratic algorithm exists [S:1:335]. Evidence that would settle it is either such an algorithm with a proof, or a lower bound above quadratic.

What depends on it. Structured matrices. An account of state-space models observes that linear attention is fast exactly when its mixing matrix is structured, which by definition means it admits fast matrix-vector multiplication [S:397:14]. That sentence is the matrix-as-machine idea doing real work: the same abstraction covers attention, recurrence and the algorithms that make either affordable.

What to read next. Read section 2.7 of Mathematics for Machine Learning for the transformation matrix and the change of coordinates [S:27:57]. Read Axler's chapter on linear maps for the map-first treatment [S:24:83]. Read section 9.7 of Erickson for Strassen and the open problem [S:1:335]. Then write the two-column table of a map you already know and check one input by the row route and by the column route.