Linear Independence and Bases

Linear Independence

A set of vectors $\{\vec{v}_1, \ldots, \vec{v}_k\}$ from a vector space $V$ is linearly independent if the only way to write $\vec{0}$ as a linear combination is the trivial one:

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

If any non-trivial combination exists, the set is linearly dependent — at least one vector is redundant (it lies in the span of the others).

Testing for Independence

Form the matrix $A$ whose columns are $\vec{v}_1, \ldots, \vec{v}_k$ and row-reduce $[A \mid \vec{0}]$. The set is independent iff the only solution is $\vec{c} = \vec{0}$, i.e., iff every column contains a pivot (no free variables).

Dependency Relations

If the set is dependent, the reduction reveals the dependency: any free variable corresponds to a non-trivial combination equaling $\vec{0}$. This tells you exactly which vector is redundant and how to express it.

Example: are $\vec{v}_1 = (1,2,0)'$, $\vec{v}_2 = (0,1,1)'$, $\vec{v}_3 = (1,4,2)'$ independent?

$$\left[\begin{array}{rrr|r}1&0&1&0\\2&1&4&0\\0&1&2&0\end{array}\right] \to \left[\begin{array}{rrr|r}1&0&1&0\\0&1&2&0\\0&0&0&0\end{array}\right]$$

Free variable $c_3$: set $c_3 = 1$ to get $c_2 = -2$, $c_1 = -1$. So $\vec{v}_3 = \vec{v}_1 + 2\vec{v}_2$ — the set is dependent.

Basis

A basis for a vector space $V$ is a set of vectors $B = \{\vec{\beta}_1, \ldots, \vec{\beta}_n\}$ that simultaneously:

1. Spans $V$: every vector in $V$ is a linear combination of the $\vec{\beta}_i$
2. Is linearly independent: no vector is redundant

A basis is the minimal spanning set — remove any vector and it no longer spans. It is also the maximal independent set — add any vector and dependence appears.

Existence of Bases

Every vector space has a basis (this requires the Axiom of Choice for infinite-dimensional spaces, but is elementary for finite-dimensional ones). Starting from any spanning set, you can build a basis by removing redundant vectors one at a time until independence is achieved.

The Standard Basis for $\mathbb{R}^n$

The standard basis $\mathcal{E}_n = \{\vec{e}_1, \ldots, \vec{e}_n\}$ has $\vec{e}_i$ equal to the column of the identity matrix $I_n$ with a $1$ in position $i$:

$$\vec{e}_1 = \begin{pmatrix}1\\0\\\vdots\\0\end{pmatrix}, \quad \vec{e}_2 = \begin{pmatrix}0\\1\\\vdots\\0\end{pmatrix}, \quad \ldots, \quad \vec{e}_n = \begin{pmatrix}0\\0\\\vdots\\1\end{pmatrix}$$

Any vector $\vec{v} = (v_1, \ldots, v_n)'$ is uniquely expressed as $v_1\vec{e}_1 + \cdots + v_n\vec{e}_n$.

Other Bases for $\mathcal{P}_2$

The space of degree-$\leq 2$ polynomials has basis $\{1, x, x^2\}$ (standard) or equally $\{1, 1+x, 1+x+x^2\}$ — any three independent polynomials that span $\mathcal{P}_2$.

Unique Representation

The most important property of a basis is uniqueness of representation:

Theorem: if $B = \{\vec{\beta}_1, \ldots, \vec{\beta}_n\}$ is a basis for $V$, then every $\vec{v} \in V$ can be written as $c_1\vec{\beta}_1 + \cdots + c_n\vec{\beta}_n$ in exactly one way.

Proof: suppose $\vec{v} = \sum c_i\vec{\beta}_i = \sum d_i\vec{\beta}_i$. Subtracting: $\sum (c_i - d_i)\vec{\beta}_i = \vec{0}$. Independence forces $c_i = d_i$ for all $i$.

The coefficients $(c_1, \ldots, c_n)$ are the coordinates of $\vec{v}$ with respect to basis $B$, written $\mathrm{Rep}_B(\vec{v})$. Choosing a basis is choosing a coordinate system.

Why Bases Matter for ML

In machine learning, features are basis representations: the columns of a data matrix form (implicitly) a basis for the feature space. PCA changes basis to one aligned with the directions of maximum variance. Neural network weight matrices change basis between layers. Understanding what a basis is — a minimal, non-redundant, complete coordinate system — makes all of these operations transparent.

Testing Independence and Computing Representations

import numpy as np

# Columns of A are v1, v2, v3
A = np.array([[1., 0., 1.],
              [2., 1., 4.],
              [0., 1., 2.]])

# Rank via SVD: independent iff rank equals number of columns
_, S, Vh = np.linalg.svd(A, full_matrices=True)
rank    = int(np.sum(S > 1e-9))
nullity = A.shape[1] - rank
print('rank:', rank)        # 2  (< 3 → dependent)
print('nullity:', nullity)  # 1

# Null vector reveals the dependency: c1*v1 + c2*v2 + c3*v3 = 0
null_vec = Vh[-1]             # last row of Vh (smallest singular value)
c = null_vec / null_vec[-1]   # scale so c3 = 1
print('dependency (c1,c2,c3):', np.round(c, 4))  # [-1. -2.  1.] → v3 = v1 + 2*v2

# Coordinate representation Rep_B(v): solve B @ coords = v
B = np.array([[1., 0., 0.],
              [1., 1., 0.],
              [0., 1., 1.]])
v = np.array([2., 3., 1.])
coords = np.linalg.solve(B, v)
print('Rep_B(v):', np.round(coords, 4))
print('verify:  ', np.round(np.einsum('ij,j->i', B, coords), 4))

The einsum string 'ij,j->i' is the matrix–vector product $A\vec{x}$, identical in NumPy, PyTorch (torch.einsum), and TensorFlow (tf.einsum). The SVD-based null vector is in an orthonormal basis; c = null_vec / null_vec[-1] rescales it to the free-variable parameterization from the row-reduction.