Linear Algebra I: Vector Spaces and Linear Maps

The matrix cannot see chemistry. It sees a column of atom counts, so any two species with the same atom counts give it the same column, and it is powerless to tell them apart.

That is not a defect, and §8.2 turns it into the point. Both -butane and isobutane have the formula , so they contribute identical columns to , and the isomerisation that turns one into the other changes not a single atom count. Element conservation therefore says nothing whatever about that reaction, which is the correct answer: no amount of atom counting can forbid it, and it happens. The reaction shows up in anyway, because the difference of two identical columns is zero. Two species, one column, and a reaction that conservation permits precisely because conservation cannot see it.

It earns its place for the reason Wilson gives and one more. An expression like mixes scalars and vectors in a single sum, and this series will go further and mix scalars, vectors, covectors and arrays in a single line. The weight of the type says which is which before the reader has parsed anything. It is also the handsomest of the four options, which is not an argument and is not nothing.

What it costs is the hand. Boldface is a property of a type case, and no one has ever produced it with chalk. Cajori, cataloguing the state of things in 1929, puts it exactly: bold-faced type is "satisfactory for print, but inconvenient for writing" [11]. So handwriting went and got its own ornaments, and the two in common use are the arrow and the rightward harpoon .

Neither has a documented origin, and that absence is itself informative. Cajori lists the rival conventions of the nineteenth century and dates every one of them, footnoting Argand in 1806, Möbius in 1827 and Bellavitis in 1837. The arrow he mentions without a date, without a name and without a footnote. The most diligent cataloguer the subject has had could not say where it came from, which suggests that by his time it had been anonymous for a long while.

The choice between the two is a matter of taste, and this series takes a side. The harpoon is the better mark on a board: it is quick, it is unmistakable, and its asymmetry survives being drawn badly at speed, which the arrow's two barbs do not. In print it turns fastidious. The arrow is not used here at all, being ungainly on the page and sitting above the letter rather than in it, decorating the symbol instead of being the symbol. A reader who prefers otherwise loses nothing, since every theorem below is indifferent to the ink.

One more story deserves a caveat rather than a citation. The underline that appears beneath vectors in handwritten notes is also the printer's mark instructing a compositor to set a letter in bold, and it is tempting to conclude that mathematicians underline vectors because they are silently marking up their own manuscripts. It is a tidy story. It appears to be documented nowhere, and the tidiness is precisely the reason to distrust it.

Two other conventions are worth considering. Each is a position someone took deliberately.

The first is to use no ornament at all. Halmos writes his vectors as plain italic and Axler does the same [2][1], and the practice is entirely defensible: in a careful text the sentence has already said what kind of object is, and a reader who needs the type to tell him has not been reading. This series declines it for the reason given above, that its whole subject is the difference between objects that the arrays make look alike.

The second is index notation, which abandons the object and names its slots: for a vector, for a covector, for a linear map. It came out of the absolute differential calculus that Ricci and Levi-Civita systematised in 1900 [12], and it acquired its summation convention from Einstein in 1916, who suppressed the summation sign and called the omission a great discovery in mathematics [13].

It is the most informative of the four, and boldface is hiding something it would show. A boldface tells you that an object is a vector. An index tells you how that object transforms, which is the thing that actually distinguishes a vector from a list of numbers. The transpose is where this bites first, and §4.1 shows exactly what the superscript is concealing. Part IV switches notation for good, and the reason it has to is the sentence from §0.1: an array has no transformation law, so it is not a tensor.

Nothing here mentions arrows, lengths, angles or coordinates. A vector space has no notion of the length of a vector and no notion of the angle between two of them; those arrive in Part III with an inner product, which is extra structure and is not free. Everything in this lecture is proved without them, which is why every theorem here holds for polynomial spaces and function spaces as readily as for .

Example 4 is the one to keep. The principle of superposition, which physics courses present as a physical fact about waves, is the statement that a certain solution set is a vector space. It is a theorem about the operator , namely that is linear and that its solution set is , which §3 proves is a subspace of the function space. Part II takes this apart in full and identifies the dimension of that solution space as the order of the equation.

The tuple is the list; the vector space is the list together with operations on it. Writing numbers in a row commits you to nothing, and the operations have to be earned. Two chemical lists show what earning them means.

The amounts of the four species in a flask form a tuple , and here the operations mean something: pour two flasks together and the amounts add, double the batch and they scale. Componentwise addition answers to an experiment.

The state of that same flask can be recorded as the tuple , and now componentwise addition answers to nothing. A flask at combined with one at does not give , and no laboratory operation doubles a temperature and a pH together. The vector-space structure on still exists, and nothing chemical answers to it.

Both lists sit in a Cartesian product. Only the first is a vector in any sense a chemist should accept. This is the same discipline [terminology] imposed on the word nonlinear: the structure has to be named before the word means anything.

The converse failure is the one this series will lean on. A polynomial in is a vector and is not a list of numbers. A solution of is a vector and is not a list of numbers. Such a vector acquires a list only when a basis is chosen, by [coordinates-unique] below, and a different basis hands the same vector a different list. The tuple is a label; the vector is the thing labelled. §4 is the long consequence.

and Euclidean -space are the same set with different amounts of structure, and the difference is exactly the dot product. Everything proved in this lecture is a statement about the vector space , and the dot product is never used. Part III adds it, under the name inner product, and pays for it.

The reason to keep them apart is that the extra structure is not always meaningful. In the species-amount space of §8, the formula can certainly be typed. What it asserts is that is orthogonal to , that a mixture has a length, and that two mixtures subtend an angle. No experiment answers to any of that. The standard basis is orthonormal by decree, and the decree is ours. That is why §5 declines to draw the four subspaces at right angles, and why the conservation laws of §8.2 are derived without one word about perpendicularity.

[coordinates-unique] is the entire content of the phrase "choose coordinates". A basis is a labelling scheme, chosen by us, and is the label. The vector is indifferent to it. Hold on to this: §4 is one long consequence.

This is what the kernel is for. For a general function, injectivity is a statement about every pair of points. For a linear map, it collapses to a statement about a single subspace, because linearity converts the difference of two collisions into one collision with zero.

[square-injective-surjective] fails without finite dimension. On the space of real sequences, the right shift is injective and not surjective. [eq:eq-rank-nullity] depends on dimension, and dimension is available to us only because [dimension-well-defined] made it well defined.

A row of numbers and a column of numbers hold the same data, and nothing in the two lists tells them apart. What tells them apart is what they do.

A column is a vector. A row is a function on vectors, namely

and that function is linear, so it is an element of . The space of linear functions from a space to its scalars is the dual space, its elements are covectors, and Part IV builds it properly. Columns are vectors, rows are covectors, and the transpose is the passage between them.

That passage looks free and is not. Turning the column into the row is a choice of which covector to attach to a given vector, and the choice made by the notation is the one licensed by the dot product of [euclidean-space]: the covector is the function . Withdraw the dot product and no vector has a preferred row attached to it at all. This is the sentence "a gradient is a covector until a metric intervenes" from §0.1, and it is why Part III has to work for something Part I gets by writing a superscript.

The chemistry is already built this way and nobody says so. The element-species matrix of §8.1 has one row per element, and row is the covector "count the atoms of element in this mixture": it eats an amounts column and returns a number. The rows of are not amounts of anything. They are functions on amounts, they live in a different space from the mixtures they measure, and §8.2 is the statement that the conserved quantities of a network are exactly the covectors annihilating every reaction. A conservation law is a row. That is the whole reason it is found in the null space of a transpose.

Boldface names an object and says nothing about its slots. Index notation names the slots and says nothing about the object, and on the subject of the transpose it is the more accurate of the two.

Give a vector an upper index and a covector a lower one, following [transpose] and the remark above:

The product is a scalar because an upper slot has been contracted with a lower one, and the two are of opposite kinds. In this notation a linear map is , one slot of each kind, since it eats a vector and returns a vector. A bilinear form is , two lower slots, since it eats two vectors and returns a scalar. Boldface writes both as a square array and hides the difference. Index notation cannot hide it, because the slots are written down.

The symbol is doing two different things.

For a map , the transpose is the dual map , which takes the covector on to the covector on . In indices it is the same array with its slots read in the other order, and not one entry has moved. This transpose is free. It asks for no inner product, no basis and no structure beyond linearity, and it is the transpose that §5 uses when it forms and calls its elements conservation laws.

For a map , written , the transpose asks for the array , which requires interchanging an upper slot with a lower one. No vector space provides that operation. It becomes legal only when a metric is present to lower the upper index and raise the lower one, and in the metric quietly supplied is the dot product of [euclidean-space]. So the innocent superscript conceals a choice, and the same choice, made in the same silence, is the one identified in the remark above: the passage from a column to a row.

Two consequences follow. A symmetric matrix and a self-adjoint operator are not the same statement: is a property of a bilinear form and needs nothing, while for an operator is a property relative to a metric, and Part III separates them. And the reason Part IV switches to index notation is now visible in miniature: what transforms, and how, is recorded by the position of a slot, and boldface has no place to write it. This is the same sentence as "an array has no transformation law, so it is not a tensor" from §0.1, and it is why the array is not the object.

Matrix multiplication is forced: it is the unique rule that makes the array of a composition equal the product of the arrays. The associativity of matrix multiplication, verified by index gymnastics in most courses, is the associativity of composition of functions, which is free.

Read [eq:eq-similarity] in those terms. The left side and the right side are two arrays of numbers with, in general, not a single entry in common. They represent one linear map. Nothing about changed when the basis was turned; only our description of it changed. Any number computed from that deserves to be a statement about must therefore be invariant under [eq:eq-similarity]. The trace and the determinant are two such numbers, and the eigenvalues are another, which is what Part II is about. The entries of are not.

The column space is the image, so is solvable exactly when : that is §7. The left null space is the set of linear relations satisfied by the rows of : a vector in it says that the combination vanishes. Read that sentence again in §8, where the rows will be reactions and the relations will be conservation laws.

Courses often draw these four subspaces with right angles between them, since and are orthogonal complements. That picture needs an inner product, which we do not have and do not need here. Orthogonality is deferred to Part III, and every statement below is proved without it.

Two names have just been given to one set. For a fixed , the null space is the kernel of the map in the sense of [kernel-image], so element for element, and every theorem in this section would survive the replacement of one symbol by the other. Anyone who tells you the two words mean different things about a given matrix is wrong. The distinction is in what each symbol takes as its argument.

takes a map. It is defined for any before a basis has been chosen, and is a subspace of itself. The word also belongs to algebra at large, where the kernel of a group homomorphism is a normal subgroup and the kernel of a ring homomorphism is an ideal, in each case the preimage of zero. takes an array. An array has no kernel at all until bases have been fixed at both ends, and is a space of coordinate columns sitting in , which is a different vector space from .

That is not a matter of taste, and the following makes it precise.

Read [eq:eq-null-space-transforms] against §4.3. One map , two bases, and the null spaces and are in general two different subspaces of , with not a vector in common beyond . The kernel did not move while that happened: [eq:eq-kernel-in-coordinates] says the two of them are one subspace of , namely , written down in two coordinate systems. The kernel is the object and the null space is its shadow, exactly as the map is the object and the matrix is its shadow. What is invariant is the dimension, and its name is the nullity. That is why the theorem of §3.2 is called rank-nullity and not rank-kernel: the quantity it counts is the one that both notations agree on.

Hence the convention followed from here on. is written when the object is a map, as in §3, and when the object is an array of numbers, as in the rest of this lecture, where , and arrive with their entries given and the standard bases understood. Where the bases are standard and no other basis is in play, the shadow is faithful and the choice of symbol costs nothing.

The word acquires a second and unrelated job the moment a bilinear form is present, which is Part III. Given a symmetric bilinear form with quadratic form , a null vector is one with , and those form a cone rather than a subspace: on with , both and are null while their sum is not. The subspace attached to a form is its radical, , and that one is a null space in the sense of [four-subspaces], being for the Gram matrix of . An inner product is the case in which the radical is and the null cone is as well, which is why the two senses of the word never collide in a first course, and why they collide immediately in relativity, where the null cone is the light cone and has nothing to do with any kernel.

The factorisation [eq:eq-rank-factorisation] is worth more than the theorem it just proved. It says every rank- matrix is a product of a tall matrix and a wide one, with the inner dimension equal to the rank. That is the shape of a low-rank approximation, of a bottleneck layer, and of the update in low-rank adaptation. Part V returns to it with the singular value decomposition, which picks the best such factorisation of each rank.

The bar is punctuation. [eq:eq-augmented] is an ordinary matrix, it has a rank and four subspaces like any other, and every theorem below applies to it with the bar erased. What the bar records is the reader's intention: columns through are coefficients of unknowns, column is data, and no unknown is ever solved for column . That intention has exactly one mathematical consequence, and it is [consistency]: the system is solvable precisely when the augmented column fails to be a pivot column, which is to say when adjoining adds no new direction to the column space.

Row of [eq:eq-augmented] is one equation. Write for it, and for the coefficients alone, which is row of ; the bold subscripted is reserved for the -th column of throughout. Then is the equation . The whole array is the list of equations, and the two facts to keep are that a row is an equation and a column is an unknown.

Row operations are left multiplications ([elementary-invertible]), so by [eq:eq-block-product] a sweep that carries to carries any block riding beside it to , whatever is. Choose the passenger and the same algorithm answers three different questions.

1. , with . The reduced system has the solutions of the original one, since is invertible, and §7 reads them off.
2. , since . The identity block is a recorder: it starts as , it undergoes every operation the left block does, and it therefore ends holding the product of all of them. This is where §6.5 gets the left null space, and, when is square and invertible, where and .
3. . Several right-hand sides, one sweep, since the left block does not know how many passengers it has.

An augmented matrix is not a new kind of object, and there is no separate theory of it. It is a matrix carrying a passenger, and [eq:eq-block-product] is why the passenger arrives at the right place.

Those are the two facts to carry out of this section. Elimination leaves the null space and the row space exactly where they were, which is why it can be trusted to compute them, and it moves the column space, which is why a basis of the column space must be read off the columns of the original and never off the columns of the reduced matrix. Courses state that rule. [row-ops-preserve] is the reason for it.

The figure is the row picture, where the planes move and their intersection does not. The column picture behaves in the opposite way, and the comparison is worth considering.

In the column picture, asks for as a combination of the columns of , and elimination hits every column with the same invertible . The columns therefore all move, and so does their span, which is [row-ops-preserve] again. What does not move is the set of coefficient relations among them: says precisely that a combination of the columns vanishing before the elimination is the same combination vanishing after it. carries the columns off to new positions and carries every dependence among them along unchanged.

So the row picture preserves a set and the column picture preserves the relations, and between them they explain the rule that looks arbitrary in every course that states it. A basis of is read from the pivot columns of because the columns of are in the wrong place, and the pivot positions are trustworthy because the relations that determine them were never disturbed. The coefficients come from , the columns come from , and [rref-bases] now reads like a description of what happened rather than a list of instructions.

Part 5 is the second use of [blocks-in-parallel]. Reduce and the recorder block ends holding , whose rows facing the zero rows of are the conservation laws of §8.2, extracted by bookkeeping. Reducing alone would compute the same and throw away.

[rank-nullity-counted] is [rank-nullity] again, and the proofs have nothing in common. The first extends a basis of the kernel to a basis of the domain and never mentions a number; the second sorts columns into two bins and counts them. The first is the stronger statement, because it holds for a linear map on any finite-dimensional space: the operator of [examples-vs] has a rank and a nullity, and there is no array to reduce. The second holds only where there is an array. This is the difference between a theorem about maps and an algorithm on matrices, and the series will keep them apart to the end.

Every operation above was performed in a field, exactly. On a computer in floating point the same algorithm can be badly behaved: dividing by a pivot that is nonzero and tiny amplifies rounding error, and the fix, choosing the largest available entry as the pivot, is partial pivoting. That is numerical linear algebra, it is a different subject with different theorems, and nothing in this series depends on it. The chemistry of §8 is done over , where the question does not arise.

A pivot in the last column is the row , which reads . The contradiction a student is taught to look for at the bottom of an elimination is the statement , and nothing more.

Permute the columns so that the pivot columns come first, which relabels the unknowns as and changes nothing else. Then [eq:eq-back-substitution] is one matrix equation, and the reduced array has the block shape

Every elimination in this series ends here. Solvability is , and then

which is [eq:eq-solution-set] with the particular solution and the null space spanned by the columns of , whose columns are the special solutions of [rref-bases]. Existence is the block , uniqueness is the width of , and the answer itself is . One array holds all three.

The word affine is the shortest true description of [eq:eq-solution-set], and it matters in three places.

The solution set of an inhomogeneous system is closed under no linear combination at all, except the ones whose coefficients sum to one: if then , which equals exactly when , which is the structure identified in [affine-not-linear]. It has a well-defined dimension, , and a well-defined direction space, , and no distinguished point: is any solution you happen to find, and a different one names the same set. That last property is what makes an extent of reaction a coordinate in §8 rather than a physical quantity, and it is what makes a particular solution of an inhomogeneous ODE a choice in Part II.

Look at the last two columns of . They are identical, both , because -butane and isobutane are the same atoms in a different arrangement, and [element-species] counts atoms. The element-species matrix is blind to isomerism, as promised in [chem-terminology].

The blindness is the right answer, and the second column of is why. The isomerisation is annihilated by because it is the difference of two identical columns, so element conservation permits it and says nothing else about it. Atom counting cannot forbid a rearrangement of atoms. It also cannot predict one: whether that isomerisation actually proceeds is a question for thermodynamics and kinetics, and no amount of linear algebra will answer it. What the linear algebra does deliver is the exact boundary of its own competence, which is more than the juggling ever offered.

The condition [eq:eq-equilibrium] is written as a power product of mole amounts. The true equilibrium condition is a power product of activities, and the two coincide only at the volume that makes the activities numerically equal to the amounts, effectively unit volume. Everything below is therefore a statement about that reference volume, and the numerical value of used here is an artefact of where the worked problem places equilibrium: it is not the measured equilibrium constant of ammonia synthesis at any real temperature. None of this touches the mathematics, because the degree contrast, one against four, is unchanged by any volume factor: a volume term multiplies [eq:eq-equilibrium] by a constant and leaves the polynomial degree in exactly where it was. The caveat is stated, and we move on.

Two objects sat in that table. [eq:eq-ice-affine] is degree one and is completely solved by §7: a line, a direction space, a coordinate, conservation laws read off a left null space. [eq:eq-haber-quartic] is degree four and is a different subject; we solved this instance only because a perfect square happened to be extractable, and the general case falls to a numerical root-finder. What linear algebra buys is the ability to see that the quartic is the only hard thing in the problem, and to hand it the simplest possible geometry to cut.