Span and Linear Independence

Given a set of vectors, two fundamental questions arise:

1. What can we build? — What set of vectors can be expressed as linear combinations of our vectors?
2. Do we have redundancy? — Are some vectors expressible in terms of others, or is each essential?

The answers to these questions are span and linear independence—two of the most important concepts in all of linear algebra.

Span tells us the reach of our vectors: the complete set of destinations accessible via linear combinations. Linear independence tells us about efficiency: whether we're using the minimum number of vectors to achieve that reach, or whether we have unnecessary redundancy.

These concepts directly determine whether systems of equations have solutions, whether transformations are invertible, whether datasets have redundant features, and how neural networks can (or cannot) represent data.

Definition of span:

The span of a set of vectors ${\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k}$ is the set of all possible linear combinations of those vectors:

$$\text{span}(\mathbf{v}_1, \ldots, \mathbf{v}_k) = \left{ c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k ;|; c_1, c_2, \ldots, c_k \in \mathbb{R} \right}$$

In other words, span is every vector you can "reach" by combining the given vectors with any coefficients.

Key insight: The span is always a subspace—it includes the zero vector and is closed under addition and scalar multiplication.

Examples of span:

Single non-zero vector: The span of $\mathbf{v} = (1, 2)$ is all vectors of the form $c(1, 2) = (c, 2c)$—a line through the origin in the direction of $\mathbf{v}$.

Two non-parallel vectors in $\mathbb{R}^2$: The span of $\mathbf{e}_1 = (1, 0)$ and $\mathbf{e}_2 = (0, 1)$ is all of $\mathbb{R}^2$—any 2D vector can be written as $c_1\mathbf{e}_1 + c_2\mathbf{e}_2$.

Two parallel vectors: The span of $(1, 2)$ and $(2, 4)$ is just the line through $(1, 2)$—the second vector adds no new reach because it's a scalar multiple of the first.

Three vectors in $\mathbb{R}^3$ that aren't coplanar: The span is all of $\mathbb{R}^3$.

Three vectors in $\mathbb{R}^3$ that ARE coplanar: The span is just the plane containing them—less than all of $\mathbb{R}^3$.

Definition of linear independence:

A set of vectors ${\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k}$ is linearly independent if the only solution to:

$$c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k = \mathbf{0}$$

is the trivial solution $c_1 = c_2 = \cdots = c_k = 0$.

If there exists a non-trivial solution (at least one $c_i eq 0$), the vectors are linearly dependent.

Intuitive meaning:

• Independent: No vector can be expressed as a linear combination of the others. Each vector adds new "reach."
• Dependent: At least one vector is redundant—it can be written in terms of the others. Removing it doesn't reduce the span.

Equivalent characterizations of linear independence:

These are all equivalent ways to say vectors are linearly independent:

1. The only way to get zero is with all coefficients zero
2. No vector is a linear combination of the others
3. Each vector adds genuinely new directions not reachable from the remaining vectors
4. The span has dimension equal to the number of vectors
5. The matrix with these vectors as columns has full column rank

Geometric interpretation:

• 2 vectors are independent ⟺ They're not parallel (neither is a scalar multiple of the other)
• 3 vectors are independent ⟺ They're not coplanar (don't all lie in the same plane through origin)
• In general: k vectors are independent ⟺ They don't all lie in a (k-1)-dimensional subspace

Span and linear independence are deeply connected—they're two sides of the same coin.

Key relationship:

• Span tells us what we can reach (the set of destinations)
• Independence tells us how efficiently we reach it (no redundancy)

Together, they determine the concept of a basis: a set of vectors that is both:

1. Spanning: The span is the whole space (we can reach everything)
2. Independent: No vector is redundant (minimal spanning set)

The dimension connection:

For a vector space of dimension $n$:

• You need at least n independent vectors to span the entire space
• You cannot have more than n independent vectors in that space
• Exactly n independent vectors form a basis

Practical implications:

For solving equations $A\mathbf{x} = \mathbf{b}$:

• If columns of $A$ span the range containing $\mathbf{b}$: solution exists
• If columns of $A$ are independent: solution is unique when it exists
• If both: unique solution (invertible system)

For machine learning:

Computational detection:

The rank of a matrix equals:

• The dimension of the column space (span of columns)
• The maximum number of linearly independent columns
• The maximum number of linearly independent rows

If a matrix has fewer independent columns than total columns, the columns are dependent.

Several methods exist to test whether vectors are linearly independent.

Method 1: Determinant (square case)

For $n$ vectors in $\mathbb{R}^n$, form the matrix with vectors as columns:

• If $\det(A) eq 0$: vectors are independent
• If $\det(A) = 0$: vectors are dependent

This only works when the number of vectors equals the space dimension.

Method 2: Rank comparison

For any number of vectors:

• Form matrix $A$ with vectors as columns
• Compute $\text{rank}(A)$
• Independent ⟺ rank equals number of vectors

Method 3: Row reduction (Gaussian elimination)

Reduce the matrix to row echelon form:

• Independent ⟺ no row of zeros (each column has a pivot)
• Dependent ⟺ at least one row of zeros

Method 4: Solve the homogeneous system

Find all solutions to $A\mathbf{c} = \mathbf{0}$:

• Independent ⟺ only solution is $\mathbf{c} = \mathbf{0}$
• Dependent ⟺ non-zero solutions exist

In machine learning, we work with vectors in hundreds or thousands of dimensions. Geometric intuition from 2D/3D still applies, but we must think more abstractly.

High-dimensional span:

In $\mathbb{R}^{1000}$, a set of 10 independent vectors spans a 10-dimensional subspace:

• This subspace contains infinitely many vectors
• But it's a tiny fraction of the full 1000-dimensional space
• Most random vectors in $\mathbb{R}^{1000}$ are NOT in this span

High-dimensional independence:

In $\mathbb{R}^n$, you can have at most $n$ independent vectors. Random vectors are almost always independent (probability 1 in continuous distributions) until you exceed the space dimension.

ML implications:

Feature spaces: If you have 100 features but only 20 are independent (80 can be expressed from the 20), your effective dimensionality is 20. This is what PCA exploits—finding the intrinsic dimension of data.

Overparameterized models: Neural networks often have more parameters than training samples. The weight vectors live in a space where many solutions exist (underdetermined system). Regularization helps pick among equivalent solutions.

Embedding spaces: Word embeddings in $\mathbb{R}^{300}$ represent a vocabulary of 100,000 words. The 100,000 word vectors must be dependent (can't have 100,000 independent vectors in $\mathbb{R}^{300}$). This isn't a bug—it's how embeddings capture relationships (similar words have similar vectors).

Span and linear independence have direct, practical applications throughout machine learning.

1. Feature Selection and Multicollinearity

When features are linearly dependent (or nearly so), regression coefficients become unstable. This is called multicollinearity.

• Perfect collinearity: One feature is an exact linear combination of others → Matrix is singular, can't invert
• Near collinearity: Features are approximately dependent → Large coefficient variance, overfitting

Detection: Check if feature matrix has full column rank, or examine condition number.

2. Dimensionality Reduction (PCA)

PCA finds a new set of independent directions (principal components) that:

• Span the data's variability
• Are orthogonal (hence independent)
• Are ordered by importance

The effective dimension is how many components explain most variance.

3. Neural Network Expressivity

A linear layer with weight matrix $W \in \mathbb{R}^{m \times n}$:

• Maps $\mathbb{R}^n$ to a subspace of $\mathbb{R}^m$
• The dimension of that subspace is $\text{rank}(W)$
• If rank < m, some outputs are unreachable
• If rank < n, input information is lost (dimensionality reduction)

4. Embedding Quality

Good embeddings balance:

• Span: Covering the conceptual space (enough directions to represent all meanings)
• Independence: Each dimension captures distinct information (not redundant)

5. Model Identifiability

A model is identifiable if different parameter settings produce different outputs. Linear dependence in the feature/design matrix can make parameters non-identifiable (infinitely many equally good solutions).

Several fundamental properties and theorems govern span and linear independence.

Key properties:

Key theorems:

Theorem (Dimension Bound): In $\mathbb{R}^n$, any set of more than $n$ vectors must be linearly dependent.

Theorem (Unique Representation): If ${\mathbf{v}_1, \ldots, \mathbf{v}_k}$ is linearly independent and $\mathbf{w}$ is in their span, then the coefficients expressing $\mathbf{w}$ as a linear combination are unique.

Theorem (Span Absorption): If $\mathbf{w}$ is in the span of ${\mathbf{v}_1, \ldots, \mathbf{v}_k}$, then: $$\text{span}(\mathbf{v}_1, \ldots, \mathbf{v}_k, \mathbf{w}) = \text{span}(\mathbf{v}_1, \ldots, \mathbf{v}_k)$$

Adding vectors already in the span doesn't expand it.

Theorem (Extension): Any independent set in a finite-dimensional vector space can be extended to a basis by adding vectors.