Linear Algebra I: Vector Spaces and Linear Maps

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

§8.2 turns this limit into the point. Both -butane and isobutane have the formula and contribute identical columns to . The isomerisation between them changes no atom count. Element conservation therefore permits the reaction. Atom counting cannot forbid it and it happens. The reaction lies in because the difference of two identical columns is zero.

Wilson's reason applies and so does another. The sum mixes scalars and vectors, and this series mixes scalars, vectors, covectors and arrays in a single line. The weight of the type says which is which before the reader has parsed anything. Boldface is also the handsomest of the four conventions this section surveys: boldface, the handwritten ornaments, plain letters and indices.

Boldface does not suit the hand. It belongs to a type case and no one has produced it with chalk. Cajori's 1929 catalogue puts it exactly: bold-faced type is "satisfactory for print, but inconvenient for writing" [11]. Handwriting acquired its own ornaments, and the two in common use are the arrow and the rightward harpoon .

Neither has a documented origin. Cajori lists the rival conventions of the nineteenth century and dates each and footnotes Argand in 1806, Möbius in 1827 and Bellavitis in 1837. He mentions the arrow without a date, a name or a footnote. The most diligent cataloguer the subject has had could not say where it came from so it had probably 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 and unmistakable, and its asymmetry stays clear when drawn badly at speed where the arrow's two barbs blur. The arrow is ungainly on the page and sits above the letter as a decoration. This series omits it. Every theorem below is indifferent to the ink.

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

Two other conventions are in use. Each is a deliberate position.

The first uses no ornament. Halmos writes his vectors as plain italic and Axler does the same [2][1]. In a careful text the sentence has already said what kind of object is. This series declines the practice because its subject is the difference between objects that arrays make look alike.

The second is index notation, which names the slots of an object: 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]. Einstein added the summation convention in 1916 by suppressing the summation sign [13], and later remarked to a friend that he had made "a great discovery in mathematics" by doing so [14].

Index notation is the most informative of the four conventions. A boldface says that an object is a vector. An index says how the object transforms, and that distinguishes a vector from a list of numbers. The transpose is where this matters first, and §4.1 shows what the superscript conceals. Part IV switches notation for good because of 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 length for a vector and no angle between two of them. Those arrive in Part III with an inner product. An inner product is extra structure. Everything in this lecture is proved without them so every theorem here holds for polynomial spaces and function spaces as for .

The principle of superposition, which physics courses present as a physical fact about waves, states that a certain solution set is a vector space. The operator is linear and its solution set is . §3 proves that this set is a subspace of the function space. Part II identifies the dimension of that solution space as the order of the equation.

A tuple is a list and a vector space is a list together with operations on it. Writing numbers in a row commits you to nothing and the operations need a meaning. Two chemical lists show what that 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 matters more to this series. A polynomial in is a vector and not a list of numbers. A solution of is a vector and 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 gives the same vector a different list. The tuple is a label and the vector is the thing labelled. §4 draws the consequences.

and Euclidean -space are the same set with different structure. The difference is the dot product. Everything proved in this lecture concerns the vector space and never uses the dot product. Part III adds it under the name inner product.

The extra structure is not always meaningful. In the species-amount space of §8 the formula can be typed. It asserts 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. So §5 does not draw the four subspaces at right angles and the conservation laws of §8.2 are derived without a 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. §4 is one long consequence.

For a general function injectivity is a statement about every pair of points. For a linear map it is 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 only because [dimension-well-defined] made it well defined.

A row of numbers and a column of numbers contain 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 the space 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. The notation makes the choice licensed by the dot product of [euclidean-space]: the covector is the function . Without the dot product no vector has a preferred row. This is the sentence "a gradient is a covector until a metric intervenes" from §0.1. Part III must work for what 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 and live in a different space from the mixtures they measure. §8.2 states that the conserved quantities of a network are exactly the covectors annihilating every reaction. A conservation law is a row, and that is why 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 on the transpose it is the more accurate of the two.

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

The product is a scalar because an upper slot is contracted with a lower one of the opposite kind. 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 shows 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 no entry moves. This transpose is free. It needs no inner product, no basis and no structure beyond linearity. §5 uses it to form and §8.2 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 when a metric lowers the upper index and raises the lower one, and in the metric quietly supplied is the dot product of [euclidean-space]. So the superscript conceals a choice: the passage from a column to a row identified in the remark above.

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

Matrix multiplication is forced. It is the unique rule that makes the array of a composition equal the product of the arrays. Its associativity, verified by index gymnastics in most courses, is the associativity of composition of functions.

Read [eq:eq-similarity] in those terms. The two sides are arrays of numbers that in general share no entry. They represent one linear map. Turning the basis changed our description of and nothing about . Any number computed from that is 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, the subject of Part II. The entries of are not.

The column space is the image, so is solvable exactly when . §7 treats this. The left null space is the set of linear relations satisfied by the rows of : a vector in it says that the combination vanishes. §8 takes for a matrix whose columns are reactions and reads these relations as 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 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 remains true when one symbol replaces the other. 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 , a different vector space from .

The following makes the distinction precise.

Read [eq:eq-null-space-transforms] against §4.3. For one map and two bases the null spaces and are in general different subspaces of with no vector in common beyond . The kernel did not move: [eq:eq-kernel-in-coordinates] says the two are one subspace of , namely , written in two coordinate systems. The kernel is the object and the null space is its shadow, as the map is the object and the matrix is its shadow. The invariant is the dimension, named the nullity. So the theorem of §3.2 is called rank-nullity: it counts the quantity on which both notations agree.

The convention from here on is that 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 makes no difference.

The word has a second and unrelated use once a bilinear form is present, in Part III. Given a symmetric bilinear form with quadratic form , a null vector is one with , and those form a cone: 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] since it equals for the Gram matrix of . For an inner product the radical and the null cone are both so the two senses never collide in a first course. 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] 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, a bottleneck layer and 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 with a rank and four subspaces like any other, and every theorem below applies to it with the bar erased. The bar records the reader's intention: columns through are coefficients of unknowns, column is data and no unknown is ever solved for column . That intention has one mathematical consequence, [consistency]: the system is solvable precisely when the augmented column is not a pivot column, equivalently 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, 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. 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 takes to takes any block 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 , undergoes every operation the left block does and ends as the product of all of them. §6.5 gets the left null space from it. When is square and invertible and .
3. . Several right-hand sides need one sweep because the left block does not know how many passengers it has.

An augmented matrix is an ordinary matrix with a passenger, and [eq:eq-block-product] is why the passenger arrives at the right place.

Elimination leaves the null space and the row space where they were so it computes them correctly. It moves the column space so 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 oppositely.

In the column picture asks for as a combination of the columns of , and elimination applies the same invertible to every column. The columns therefore all move, and so does their span. This 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. moves the columns to new positions and keeps every dependence among them unchanged.

The row picture preserves a set and the column picture preserves the relations. Together 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 and the columns come from , so [rref-bases] describes what happened.

Part 5 is the second use of [blocks-in-parallel]. Reduce and the recorder block ends as , 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 derivative on of [examples-vs] has the constants as kernel and as image, and with no array to reduce. The second holds only where there is an array. The difference is that between a theorem about maps and an algorithm on matrices, and the series keeps them apart.

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 of choosing the largest available entry as the pivot is partial pivoting. That is numerical linear algebra, 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 .

Permute the columns so that the pivot columns come first. This 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 , the special solutions of [rref-bases]. Existence is the block , uniqueness is the width of , and the answer itself is .

The word affine is the shortest true description of [eq:eq-solution-set].

The solution set of an inhomogeneous system is closed only under the linear combinations whose coefficients sum to one: if then , which equals exactly when . This 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 makes an extent of reaction a coordinate in §8 and 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 correct, as the second column of shows. 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 proceeds is a question for thermodynamics and kinetics, and no amount of linear algebra will answer it.

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 (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 and is not the measured equilibrium constant of ammonia synthesis at any real temperature. None of this touches the mathematics. A volume term multiplies [eq:eq-equilibrium] by a constant and leaves the polynomial degree in unchanged so the contrast of degree one against degree four stands.

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. Linear algebra shows that the quartic is the only hard thing in the problem and gives it the simplest possible geometry to cut.