Linear combinations, span and independence

Adding and scaling are the only two operations available, so applying them repeatedly to a fixed set of vectors generates everything that set can reach, and a system of equations asks whether a particular target is reachable.

This lesson needs only the previous one: a vector is a list that can be added componentwise and multiplied by a number, and the two operations have a geometric reading as arrows joined tip to tail and arrows stretched. Everything below is those two operations applied several times.

One question instead of many equations

A linear combination of the vectors $v_{1}, \dots, v_{k}$ is any vector of the form

c_{1} v_{1} + c_{2} v_{2} + \dots + c_{k} v_{k}

with the $c_{i}$ any real numbers. Because only addition and scaling are used, that expression is the most general thing that can be built out of a set of vectors, and everything in the rest of the course is a linear combination of something.

Recall the system solved two lessons ago, $2 x + y - z = 8$ , $- 3 x - y + 2 z = - 11$ and $- 2 x + y + 2 z = - 3$ . Read down the columns rather than along the rows and it says

x (2, - 3, - 2) + y (1, - 1, 1) + z (- 1, 2, 2) = (8, - 11, - 3)

which is one vector equation in place of three scalar ones. The solution found there was $x = 2$ , $y = 3$ , $z = - 1$ , and substituting gives $(4, - 6, - 4) + (3, - 3, 3) + (1, - 2, - 2) = (8, - 11, - 3)$ , componentwise, as required.

The restatement is worth taking seriously, because it changes the question. Instead of asking which numbers satisfy three separate constraints, it asks: is the target vector a linear combination of the columns, and if so, in what amounts? That is a question about the columns, and it has a geometric answer.

Span

The span of a set of vectors is the set of all their linear combinations. It is written $span {v_{1}, \dots, v_{k}}$ and is best thought of as everything reachable from those vectors using the two permitted operations.

Some spans are easy to see. The span of a single non-zero vector $v$ is ${c v}$ , an infinite straight line through the origin in the direction of $v$ . The span of the two vectors $(1, 0)$ and $(0, 1)$ is the whole plane, since $(a, b) = a (1, 0) + b (0, 1)$ for any pair. The span of the empty set, and the span of ${0}$ , is just the origin.

Two vectors in three-dimensional space usually span a plane through the origin: the combinations $c_{1} v_{1} + c_{2} v_{2}$ sweep out a flat sheet containing both arrows and the origin. But not always. If $v_{2}$ happens to be a multiple of $v_{1}$ , say $(2, 4, 6)$ against $(1, 2, 3)$ , then every combination is a multiple of $v_{1}$ and the span collapses to a line. Two vectors span a plane when they point in genuinely different directions, and a line when they do not, and that distinction is the whole content of the next section.

Notice that a span always contains the origin, taking every coefficient zero, and that it is closed under the two operations: any combination of things in the span is again in the span. A span is therefore flat and unbounded, a line or a plane or a higher-dimensional analogue, always through the origin, and never a curve, a disc or a shifted plane.

Example. Is $(4, 5, 6)$ in the span of $(1, 1, 1)$ and $(1, 2, 3)$ ?

The question asks for numbers $a$ and $b$ with $a (1, 1, 1) + b (1, 2, 3) = (4, 5, 6)$ , which is three equations: $a + b = 4$ , $a + 2 b = 5$ , $a + 3 b = 6$ . Subtracting the first from the second gives $b = 1$ , so $a = 3$ . The third equation is a consistency check rather than a way of finding anything, and it holds: $3 + 3 = 6$ . So yes, and $(4, 5, 6) = 3 (1, 1, 1) + 1 (1, 2, 3)$ .

Now you. Is $(7, 8, 9)$ in the same span, and is $(4, 5, 7)$ ?

Answer

For $(7, 8, 9)$ : $a + b = 7$ and $a + 2 b = 8$ give $b = 1$ and $a = 6$ , and the third equation checks, $6 + 3 = 9$ . So it is in the span. For $(4, 5, 7)$ the first two equations still give $a = 3$ and $b = 1$ , but the third would need $3 + 3 = 7$ , which is false, so it is not in the span. Both points lie in three-dimensional space, and the span is only a plane, so most points miss it.

Dependence and independence

A set of vectors is linearly dependent when some non-trivial combination of them gives the zero vector, meaning

c_{1} v_{1} + \dots + c_{k} v_{k} = 0

with at least one $c_{i}$ not zero. It is linearly independent when the only combination producing $0$ is the one with every coefficient zero. The word "non-trivial" carries the whole definition: taking all the coefficients zero always works and says nothing.

The definition looks technical, and it is equivalent to something plainer: a set is dependent exactly when one of its members is a combination of the others. If $c_{1} \neq 0$ in a dependent relation, divide by it and rearrange to get $v_{1} = - (c_{2} / c_{1}) v_{2} - \dots - (c_{k} / c_{1}) v_{k}$ , so $v_{1}$ is a combination of the rest. Conversely, if $v_{1} = d_{2} v_{2} + \dots + d_{k} v_{k}$ , move everything to one side to get a relation with $c_{1} = - 1$ , which is certainly not zero. So dependence means redundancy: at least one vector adds nothing to the span, because it was already reachable from the others.

The zero-vector version of the definition is preferred despite being less intuitive, for two reasons. It treats all the vectors symmetrically, whereas "one is a combination of the others" invites the false belief that the guilty vector is identifiable, and it is directly a homogeneous system of the kind elimination solves.

Take $v_{1} = (1, 1, 2)$ , $v_{2} = (2, 1, 3)$ and $v_{3} = (3, 2, 5)$ . Adding the first two gives $(3, 2, 5)$ exactly, so $v_{1} + v_{2} - v_{3} = 0$ with coefficients $(1, 1, - 1)$ , and the set is dependent. The span of all three is therefore no bigger than the span of the first two: a plane, not all of space.

Now take $(1, 0, 0)$ , $(1, 1, 0)$ and $(1, 1, 1)$ . A combination is $(c_{1} + c_{2} + c_{3}, c_{2} + c_{3}, c_{3})$ , and setting it to zero forces $c_{3} = 0$ from the last component, then $c_{2} = 0$ from the middle, then $c_{1} = 0$ . Only the trivial combination works, so the set is independent and its span is all of $R^{3}$ .

Example. Are $(1, 2, 3)$ , $(2, 1, 0)$ and $(4, 5, 6)$ independent?

Set $a (1, 2, 3) + b (2, 1, 0) + c (4, 5, 6) = 0$ , which is $a + 2 b + 4 c = 0$ , $2 a + b + 5 c = 0$ and $3 a + 6 c = 0$ . The last gives $a = - 2 c$ . Substituting into the first, $- 2 c + 2 b + 4 c = 0$ , so $b = - c$ . The second is then $- 4 c - c + 5 c = 0$ , satisfied automatically. Taking $c = 1$ gives the relation $- 2 (1, 2, 3) - (2, 1, 0) + (4, 5, 6) = 0$ , which is checkable directly: $2 (1, 2, 3) + (2, 1, 0) = (4, 5, 6)$ . The set is dependent, and the third vector was redundant.

Now you. Are $(1, 0, 1)$ , $(0, 1, 1)$ and $(1, 1, 2)$ independent?

Answer

Adding the first two gives $(1, 1, 2)$ , which is the third, so $(1, 0, 1) + (0, 1, 1) - (1, 1, 2) = 0$ and the set is dependent. Their span is the plane through the first two, not all of $R^{3}$ .

The three outcomes, seen

The first lesson found by algebra that a linear system has no solution, exactly one, or infinitely many. In the language of this lesson those are three statements about the columns of the system and the target vector $b$ .

There is at least one solution exactly when $b$ lies in the span of the columns. If the columns of a three by three system span all of $R^{3}$ , every target is reachable and the system is solvable whatever $b$ is. If they span only a plane, then targets off that plane are unreachable, which is the inconsistent case: the algebra reported $0 = - 1$ , and the geometry says $b$ was never in the span to begin with.

There is at most one solution exactly when the columns are independent. Suppose two different combinations both produce $b$ . Subtracting them gives a combination equal to $0$ whose coefficients are not all zero, since the two solutions differed, and that is dependence. Run the argument backwards and dependence produces infinitely many solutions: add any multiple of the dependence relation to a solution and it remains a solution, because the added part contributes $0$ .

So independence controls uniqueness and span controls existence, and the two are separate questions. The example above with $(1, 2, 3)$ , $(2, 1, 0)$ and $(4, 5, 6)$ has dependent columns, so any system built from them has either no solutions or an infinite line of them, and never one.

Example. The columns of a system are $(1, 2)$ , $(2, 4)$ and $(3, 6)$ , and $b = (5, 10)$ . How many solutions?

Every column is a multiple of $(1, 2)$ , so the span is the line through $(1, 2)$ . The target $(5, 10) = 5 (1, 2)$ is on that line, so solutions exist. The columns are wildly dependent, so there are infinitely many: $x + 2 y + 3 z = 5$ is the single condition, and any $(x, y, z)$ satisfying it works, for example $(5, 0, 0)$ or $(0, 1, 1)$ .

Now you. Same three columns, but $b = (5, 11)$ . How many solutions?

Answer

None. Every reachable vector has its second component exactly twice its first, and $11 \neq 10$ . The target is off the line that the columns span, so no combination reaches it.

Counting

One counting fact does a great deal of work later, and it follows from elimination without any new machinery: any set of more than $n$ vectors in $R^{n}$ is dependent.

Here is why. Testing $k$ vectors in $R^{n}$ for dependence means solving $c_{1} v_{1} + \dots + c_{k} v_{k} = 0$ , which written out is $n$ equations in $k$ unknowns, one equation per component. Elimination clears one unknown per equation at most, so it can pin down at most $n$ of the unknowns. If $k > n$ then at least $k - n$ unknowns are never pinned down and are free to take any value, and choosing a non-zero value for one of them produces a non-trivial relation. Since $0$ is always a solution, the system is never inconsistent, so those free choices really do deliver solutions.

Three vectors in the plane are therefore always dependent, however they are chosen, and so are $1001$ vectors in $R^{1000}$ . The converse direction is the same statement read the other way: fewer than $n$ vectors can never span $R^{n}$ , since $n$ equations in $k < n$ unknowns cannot be solvable for every right hand side. Between those two bounds sits the case of exactly $n$ vectors, which is the useful one, and the next lesson is about it.

Honest limits

Independence is a property of a set, not of any individual vector in it. Saying "the third vector is dependent" is meaningless: in the worked example above, any one of the three could be written in terms of the other two, and nothing distinguishes a culprit.

The more serious limit is numerical. Independence is a yes or no question in exact arithmetic and a matter of degree in practice. The vectors $(1, 0)$ and $(1, 0.000001)$ are genuinely independent, and their span is genuinely the whole plane, but reaching $(0, 1)$ requires the combination $- 1000000 (1, 0) + 1000000 (1, 0.000001)$ , in which two enormous quantities nearly cancel. Any measurement error in the data is magnified by a factor of about a million. Sets like this are called ill-conditioned, and the number quantifying the trouble is introduced in the lesson on orthogonality. The theory presented here remains exactly true; it just stops being the only thing worth knowing.

A dependent set describes its span wastefully, using more vectors than the span requires. The next lesson removes the waste, and finds that what is left over has a size that does not depend on how the removing was done.