← mapVector Spaces

Linear Independence

⚗ Dr. Möbius, from the lab

Last node I promised to exterminate deadweight. Here is the damn exterminator. A list of vectors is linearly independent when nobody in it is freeloading off the others — when the only way to combine them into zero is the cowardly all-zeros way. Get this concept wrong and basis, dimension, and rank all collapse into mush. Get it right and half of linear algebra becomes obvious. No pressure.

THE BIG IDEA

A list of vectors is linearly independent when the only linear combination equal to zero is the one with all coefficients zero — equivalently, no vector is in the span of the others.

The definition that actually matters

In the Span node we saw redundancy: sometimes a vector is already reachable from the others and adds nothing to the span. We need a clean test for "no redundancy." Here it is, and it's deceptively small.

Vectors $v_1, \dots, v_k$ are linearly independent if the only solution to $c_1 v_1 + c_2 v_2 + \cdots + c_k v_k = \mathbf{0}$ is $c_1 = c_2 = \cdots = c_k = 0$ .

If there's any other solution — any way to hit $\mathbf{0}$ with not-all-zero coefficients — the vectors are linearly dependent.

The all-zeros combination always gives $\mathbf{0}$ ; that's the free lunch nobody can take away (it's the trivial combination). Independence says: that's the only lunch. Dependence says: there's a sneaky second way, a nontrivial combination that secretly cancels to zero. The whole concept is "is zero reachable in a non-stupid way?" That one question controls everything downstream.

Why this captures "no freeloaders"

The definition looks abstract; let's prove it means exactly what we want.

Theorem. $v_1, \dots, v_k$ are linearly dependent $\iff$ at least one $v_j$ lies in the span of the others.

Proof. ( $\Rightarrow$ ) Suppose dependent: there's a nontrivial $c_1 v_1 + \cdots + c_k v_k = \mathbf{0}$ with some $c_j \ne 0$ . Solve for that $v_j$ — legal because $c_j \ne 0$ lets us divide: $v_j = -\frac{c_1}{c_j} v_1 - \cdots - \frac{c_{j-1}}{c_j} v_{j-1} - \frac{c_{j+1}}{c_j} v_{j+1} - \cdots - \frac{c_k}{c_j} v_k.$ The right side is a linear combination of the other vectors, so $v_j \in \operatorname{span}(\text{others})$ .

( $\Leftarrow$ ) Suppose some $v_j = \sum_{i \ne j} a_i v_i$ . Move everything to one side: $a_1 v_1 + \cdots + (-1)v_j + \cdots + a_k v_k = \mathbf{0}.$ The coefficient of $v_j$ is $-1 \ne 0$ , so this is a nontrivial combination equal to $\mathbf{0}$ — the vectors are dependent. $\blacksquare$

So "linearly dependent" and "somebody is a combination of the rest" are literally the same statement. The freeloader is real, and the $c_j \ne 0$ is the receipt that catches them.

Testing independence = solving a homogeneous system

Here's the marriage with the Matrices stratum, on full display. Write the vectors as columns of a matrix $A$ . Then $c_1 v_1 + \cdots + c_k v_k = \mathbf{0}$ is precisely $A\mathbf{c} = \mathbf{0},$ the homogeneous system from the Subspaces node. Independence is the demand that this system has only the trivial solution $\mathbf{c} = \mathbf{0}$ .

From the Matrices stratum you know exactly when that happens: row-reduce $A$ and check the pivots. The system $A\mathbf{c} = \mathbf{0}$ has only the trivial solution iff every column has a pivot (no free variables — every variable is forced to zero). So: $\{v_1, \dots, v_k\} \text{ independent} \iff \text{the matrix with these columns has a pivot in every column.}$ A free variable is a freeloader given a name. Independence = no free variables = a pivot in every column. That's the whole computational test, and it's just Gaussian elimination wearing a new hat — the same damn machine from two lessons ago, still running the show.

The geometric pictures

In $\mathbb{R}^2$ : two vectors are dependent $\iff$ they're parallel (one is a scalar multiple of the other). Independent means they point in genuinely different directions.
In $\mathbb{R}^3$ : three vectors are dependent $\iff$ they lie in a common plane through the origin (or worse, a line). Independent means they "fill out" all three dimensions.
Any list containing $\mathbf{0}$ is automatically dependent. Why? The combination $1\cdot \mathbf{0} + 0\cdot v_2 + \cdots + 0\cdot v_k = \mathbf{0}$ is nontrivial (the coefficient on $\mathbf{0}$ is $1 \ne 0$ ) yet equals $\mathbf{0}$ . The zero vector is the ultimate freeloader — it contributes nothing but breaks independence on sight.

The pigeonhole hammer: too many vectors must be dependent

Now a theorem you'll lean on constantly, and it's pure counting — ruthlessly elegant.

Theorem. Any list of more than $n$ vectors in $\mathbb{R}^n$ is linearly dependent.

Proof (via pivots). Suppose you have $k > n$ vectors in $\mathbb{R}^n$ . Stack them as columns of an $n \times k$ matrix $A$ . Independence would require a pivot in every one of the $k$ columns. But pivots live in rows, and there are only $n$ rows — so at most $n$ pivots exist. Since $k > n$ , at least one column has no pivot, meaning a free variable, meaning a nontrivial solution to $A\mathbf{c} = \mathbf{0}$ . Therefore the vectors are dependent. $\blacksquare$

That's pigeonhole reasoning from the Sets stratum (more columns than rows, pivots can't cover them all) deciding a geometric fact — no computation required. Five vectors in $\mathbb{R}^3$ ? Dependent, guaranteed, before you even look at the numbers. This caps how big an independent set can get, and it's precisely what makes dimension well-defined next node. When I said counting controls everything, I was not bullshitting you.

🔬 SPECIMENS (worked examples)

Worked example 1 — two vectors, independent or not?▸

Are $(1, 2)$ and $(3, 5)$ linearly independent in $\mathbb{R}^2$ ?

Set up the test: solve $c_1(1,2) + c_2(3,5) = (0,0)$ , i.e. $\begin{cases} c_1 + 3c_2 = 0 \\ 2c_1 + 5c_2 = 0 \end{cases}$ From the first equation $c_1 = -3c_2$ . Substitute into the second: $2(-3c_2) + 5c_2 = -6c_2 + 5c_2 = -c_2 = 0$ , so $c_2 = 0$ , and then $c_1 = 0$ .

The only solution is $c_1 = c_2 = 0$ — the trivial one. So $(1,2)$ and $(3,5)$ are linearly independent. Geometric sanity check: is one a scalar multiple of the other? $(3,5) = c(1,2)$ would need $c = 3$ (first coord) and $c = 5/2$ (second) — contradiction. Not parallel, so independent. Both methods agree.

Worked example 2 — three vectors via pivots▸

Are $(1,0,0)$ , $(1,1,0)$ , $(1,1,1)$ linearly independent in $\mathbb{R}^3$ ?

Stack them as columns and check for a pivot in each column: $A = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}.$ This is already in upper-triangular form with nonzero diagonal entries $1, 1, 1$ — a pivot in every column. By the pivot test, the homogeneous system $A\mathbf{c} = \mathbf{0}$ has only the trivial solution, so the vectors are linearly independent.

Double-check by hand: $c_1(1,0,0) + c_2(1,1,0) + c_3(1,1,1) = \mathbf{0}$ reads, bottom coordinate first, $c_3 = 0$ , then $c_2 + c_3 = 0 \Rightarrow c_2 = 0$ , then $c_1 + c_2 + c_3 = 0 \Rightarrow c_1 = 0$ . Back-substitution forces everything to zero — independent. Three independent vectors in $\mathbb{R}^3$ : they fill the whole space.

Worked example 3 — the trap: three vectors that look fine and are absolutely not▸

Are $(1, 2, 3)$ , $(4, 5, 6)$ , $(7, 8, 9)$ linearly independent?

The trap: three distinct, nonzero, non-parallel-looking vectors in $\mathbb{R}^3$ — surely independent? No. Look for a hidden relation. Notice $(7,8,9) = 2\cdot(4,5,6) - (1,2,3): \quad (8,10,12) - (1,2,3) = (7,8,9). \;✓$ So the third vector is a combination of the first two — a freeloader. By our theorem, the list is linearly dependent. The nontrivial relation: $1\cdot(1,2,3) - 2\cdot(4,5,6) + 1\cdot(7,8,9) = \mathbf{0},$ with coefficients $(1, -2, 1)$ , not all zero. These three vectors all lie in a common plane through the origin, so they can't fill $\mathbb{R}^3$ . Lesson: "three different-looking vectors" proves nothing — you must actually run the test. Equally spaced rows like $1,2,3 / 4,5,6 / 7,8,9$ are always dependent for exactly this reason.

☠ KNOWN HAZARDS

Confusing "spans" with "independent". Spanning is about reaching everything; independence is about no redundancy. A set can do one without the other. A basis (next node) does both, and getting here confused will wreck the whole stratum for you.
Forgetting that $\{\mathbf{0}, \dots\}$ is always dependent. The zero vector poisons any list instantly. If you spot $\mathbf{0}$ , stop — it's dependent, no computation needed. Don't waste time on the rest.
Thinking the all-zeros solution proves dependence. $c_1=\cdots=c_k=0$ always works for any vectors — it proves nothing. Dependence requires a solution where some coefficient is nonzero. The trivial solution is not evidence of anything.
Believing " $k$ vectors in $\mathbb{R}^k$ are automatically independent". Only if they're not redundant — only if every column gets a pivot. Three vectors in $\mathbb{R}^3$ can still be coplanar and dependent, as worked example 3 demonstrates with gleeful cruelty.

TL;DR

▸
$v_1, \dots, v_k$ are linearly independent iff $c_1 v_1 + \cdots + c_k v_k = \mathbf{0}$ forces every $c_i = 0$ . The trivial combination is the only one hitting zero.
▸
Dependent $\iff$ some vector is in the span of the others (proved by dividing through the nonzero coefficient). Dependence = a freeloader exists.
▸
Testing independence $=$ checking that the homogeneous system $A\mathbf{c}=\mathbf{0}$ (columns $=$ the vectors) has only the trivial solution $\iff$ a pivot in every column (no free variables).
▸
Two vectors dependent $\iff$ parallel. Any list containing $\mathbf{0}$ is dependent. Independence means pointing in genuinely different directions.
▸
More than $n$ vectors in $\mathbb{R}^n$ are always dependent (pigeonhole: only $n$ rows, so $\le n$ pivots, so a column goes pivotless). This caps independent sets and sets up dimension.

unlocks

Basis & Dimension →