Span, basis and dimension

Take the two lists (1, 2) and (2, 1), double the first, retain the second, and add: (2, 4) + (2, 1) = (4, 5). Those two lists have produced a third, and they can produce a great many more.

The section question asks how few lists you need in order to build all the others. Here two lists did the work, and a third list is often pure surplus: add (3, 3) to the collection and it produces nothing new, since (3, 3) is the first two added together. The set of everything those lists can build is their span, and a sum of scaled copies such as the one above is a linear combination of them [S:23:110]. !Left: (1, 2) and (2, 1) are independent. The dashed path walks a second copy of the first, then one copy of the second, and lands on 2·(1, 2) + 1·(2, 1) = (4, 5). The list (3, 3) is one copy of each, so adding it to the stock introduces no direction the pair did not already reach. Right: (1, 2) and (2, 4) are proportional and reach only their own line, so (3, 3) is out of reach and one of the pair is surplus. Status: schematic.

!Both panels end at (1, 1). Against the standard arrows the recipe is one copy of each, and here the coordinate list and the vector happen to share their entries. Against (1, 2) and (2, 1) the recipe is a third of each, and the same vector wears the list (1/3, 1/3). The vector does not move when the stock changes. Status: schematic.

The display indicates two copies of the first list plus one copy of the second land on (4, 5), and the multipliers are the only freedom available.

A basis is a stock with two virtues simultaneously, because it spans the space and it contains no redundant member [S:23:131]. The pair (1, 2) and (2, 1) is a basis of the plane, while the pair (1, 2) and (2, 4) is not, because the second is twice the first and one of them is therefore surplus. A list is linearly independent when no member can be constructed from the others [S:21:99], and linear dependence is the failure of that test: some member can be built from the rest.

Different stocks can be bases of the same space, and they always contain the same number of vectors [S:24:58]. That fact is what lets mathematicians define the dimension of a space as the number of vectors in any basis of it [S:24:58]. The plane has dimension two, the space of three-entry lists has dimension three, and the dimension counts the stock rather than any particular choice of stock.

For a pair of two-entry lists the independence test is straightforward, because the pair fails exactly when one list is a multiple of the other. The lists (1, 2) and (2, 4) are proportional and therefore redundant, whereas (1, 2) and (2, 1) are not proportional and therefore independent. Three or more lists need an actual calculation, and a later section supplies a systematic one.

The bottom of the scale deserves a statement: no lists at all produce only the zero vector, which is why the empty collection qualifies as a basis of that single point. One list produces its multiples, which is a line through the origin — the point whose entries are all zero — and a line therefore has dimension one. Two linearly independent lists produce the entire plane, and a third list in the plane is a passenger that can be discarded without losing anything.

Now construct (1, 1) from the first pair by taking a third of each list and adding them.

The display says one third of the first list plus one third of the second reaches (1, 1). The thirds are the price of employing this pair rather than the obvious pair (1, 0) and (0, 1), which would have attained the same target in one step.

Three lists in the plane are always more than a basis needs. Any collection of three or more two-entry lists is linearly dependent [S:21:101], so at least one of them is redundant and can be discarded without shrinking the span. Here (3, 3) is exactly (1, 2) + (2, 1), so a collection of three collapses to a collection of two, and the same counting holds one level up, where every collection of four three-entry lists is dependent [S:21:101].

This accounting explains why the question matters outside geometry: if every row of a long table is a combination of two rows, you can retain the two rows and one pair of multipliers per line instead of the entire table. The compression is exact when the rows really are combinations and without value when they are not, which is the distinction a later section calls rank.

A coordinate list is a recipe written in the units of the basis, and the entry in each slot says how many copies of that basis vector to use. Against the standard basis — the lists with a single one and zeros elsewhere — the recipe for (1, 1) is one copy of each, while against (1, 2) and (2, 1) it is a third of each. The vector is the same object in both readings, and the entries are two different descriptions of it [S:27:57].

The idea therefore has a price: the numbers are not the vector. Change the basis and the entries change while the vector stays put, so a claim about the entries is a claim about the basis as much as about the vector. The next section writes down the matrix that turns one list into another, and that matrix inherits exactly this dependence on the basis you chose.

The formal statement. Let $S$ be a set of vectors in a vector space $V$. Its span is the set of all finite sums ${\sum }_i{c}_i{s}_i$, with each $s_i$ in $S$ and each $c_i$ a scalar [S:23:110]. The set $S$ is linearly independent when the only combination that gives the zero vector has every coefficient zero [S:21:99]. A basis is an independent list — an ordered sequence — that spans $V$ [S:23:131]. As an unordered set it is independent and spanning, but the coordinate recipe is unique only once the order is fixed. The theorem that makes dimension meaningful is this: any two bases of a finite-dimensional space contain the same number of vectors [S:24:58].

The derivation. The proof is an exchange, and the exchange is the step usually left to a picture. Suppose $u_1,\dots ,u_m$ are independent and $v_1,\dots ,v_n$ span $V$. Each $u$ is a combination of the $v$'s. The first $u$ uses at least one $v$ with a nonzero coefficient; drop that $v$ and keep $u_1$. The new list still spans, because the dropped $v$ is recoverable from $u_1$ and the vectors you kept. Repeat. Independence stops a new $u$ from already lying in the span of the list, so each replacement costs one $v$ and buys one $u$. If $m>n$ you run out of $v$'s with a $u$ still unplaced, and that $u$ would be a combination of the others, which contradicts independence. Hence $m\le n$, and running the argument both ways gives equality for two bases.

The edge case. L1's sentence "the space of three-entry lists has dimension three" can slide into "dimension counts the entries". It does not. The line spanned by $(0,1)$ is a subspace of the plane of dimension one, although each of its vectors has two entries [S:27:52]. Dimension counts the members of a basis, not the slots in a vector. The same confusion costs you in a data table: a table with forty columns and rank three has three independent patterns, and the forty is a property of how you recorded it.

What L1 hid. L1 presented a basis as a stock and a coordinate list as a recipe. The recipe is unique only when the basis is ordered. Swap two basis vectors and every coordinate list swaps two entries while the vector stays put [S:27:57]. L1 also treated "spans" and "no redundant member" as two separate virtues. They are equivalent halves of one condition: a finite set is a basis exactly when it is a maximal independent set, and exactly when it is a minimal spanning set [S:23:131].

Where the analogy breaks. A stock of materials suggests building in stages, with a pile left over. A basis builds every vector in one step, from finitely many members, with multipliers that may be negative or fractional. The "how few" in the section question counts members, not effort. In the compression reading, the saving is exact only when every dropped row really is a combination of the kept ones.

Where the idea comes from. Span and linear combination are Hefferon's terms: the span is the set of all linear combinations of vectors from a set [S:23:110]. A basis is a sequence that is both independent and spanning [S:23:131]. Axler states and proves, as theorem 2.34, that any two bases of a finite-dimensional vector space have the same length, and that result is what lets dimension be defined at all [S:24:58]. L1 counted three vectors in the plane as too many; the general statement is that any $n+1$ vectors in $n$ dimensions are dependent [S:21:101].

What the field has not settled. The intrinsic dimension of real data. Scaling-law arguments connect the exponent of a power law to the dimension of the data manifold, and the same lecture notes concede that estimators of intrinsic dimension are sketchy and the argument is not airtight [S:70:20]. Evidence that would settle it: several estimators agreeing with each other on data whose dimension is known by construction, and a measured exponent that follows that known dimension as you vary it. Until then, "the data lies on a low-dimensional manifold" is a hypothesis with a measurement problem attached.

What depends on it. Truncated SVD. Schmidt's approximation theorem — rediscovered by Eckart and Young, and usually called the Eckart–Young theorem — states that the best rank-$r$ approximation in the Frobenius norm is the leading $r$ terms of the SVD [S:52:28]. Every compression and latent-factor method in this book inherits the phrase "rank $r$" from that theorem. The theorem is about a rank you choose, not about a rank the data reveals, which is exactly the gap the previous paragraph describes.

What to read next. Read chapter 2 of Axler for the exchange argument behind the theorem [S:24:58]. Read chapter 2 of Hefferon for span, independence and basis with the proofs written out [S:23:110]. Read chapter 1 of Brunton and Kutz for the SVD and the rank-$r$ approximation [S:52:28]. Then compute the singular values of a table you care about, and ask where the last large gap sits.