1 Introduction: Understanding Vector Space Architecture
In the previous lesson, we learned how to solve systems of linear equations using Gaussian elimination and matrix equations $A\mathbf{x} = \mathbf{b}$. However, when scaling up to high-dimensional datasets in computer science, robotics, and machine learning, deeper structural questions emerge:
- • Redundancy: Given a collection of vectors, can some of them be synthesized entirely as combinations of the others?
- • Information Content: Does every column or feature in a dataset contribute genuinely distinct, non-overlapping information?
- • Minimal Basis: What is the smallest set of independent coordinate axes required to span the entire space without gaps or excess?
Linear algebra answers these questions through three deeply intertwined concepts:
The minimal generating set of linearly independent vectors needed to span a vector space without redundancy.
The number of vectors in any basis of the space, representing its intrinsic degrees of freedom.
The maximal number of linearly independent row or column vectors in a matrix.
2 Linear Combinations and Span
Before formalizing basis and dimension, we must firmly establish two foundational building blocks: Linear Combinations and Span.
Linear Combinations
Multiplying a collection of vectors by scalar constants and adding the results produces a Linear Combination.
Consider two 2D vectors:
Scaling $\mathbf{u}$ by 2 and $\mathbf{v}$ by 3 yields:
The vector $\begin{bmatrix} 11 \\ 7 \end{bmatrix}$ is a linear combination of $\mathbf{u}$ and $\mathbf{v}$. More generally, for $k$ vectors, any linear combination takes the form $\sum_{i=1}^k c_i \mathbf{v}_i$ where $c_i \in \mathbb{R}$.
Span (The Reach of a Vector Set)
The collection of all possible linear combinations that can be synthesized from a set of vectors forms their Span:
3 Linear Independence vs. Linear Dependence
Does every vector in a set contribute a genuine new direction, or are some redundant? This is measured via Linear Independence.
Formal Definition
A set of vectors $\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n\}$ is Linearly Independent if the equation:
has only the trivial solution: $c_1 = c_2 = \dots = c_n = 0$. If there exists any non-trivial solution (where at least one $c_i \ne 0$), the set is Linearly Dependent.
$\mathbf{u} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \mathbf{v} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$
$c_1 \begin{bmatrix} 1 \\ 0 \end{bmatrix} + c_2 \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} \implies c_1 = 0, c_2 = 0$
Neither vector can be expressed in terms of the other. Both contribute unique spatial directions.
$\mathbf{u} = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \mathbf{v} = \begin{bmatrix} 2 \\ 4 \end{bmatrix}$
Notice: $\mathbf{v} = 2\mathbf{u} \implies 2\mathbf{u} - \mathbf{v} = \mathbf{0}$
Here $c_1 = 2, c_2 = -1 \ne 0$. Vector $\mathbf{v}$ adds no new direction beyond what $\mathbf{u}$ already provides.
4 Basis: The Minimal Generating Coordinate Skeleton
A Basis $\mathcal{B} = \{\mathbf{v}_1, \dots, \mathbf{v}_k\}$ for a vector space $V$ is a set of vectors that simultaneously satisfies two strict criteria:
The Standard Basis
In Cartesian space $\mathbb{R}^2$, the canonical Standard Basis consists of the elementary coordinate unit vectors:
Any vector $\begin{bmatrix} a \\ b \end{bmatrix}$ is expressed uniquely as $a\mathbf{e}_1 + b\mathbf{e}_2$. In $\mathbb{R}^3$, the standard basis consists of $\mathbf{e}_1 = (1, 0, 0), \mathbf{e}_2 = (0, 1, 0), \mathbf{e}_3 = (0, 0, 1)$.
5 Dimension: Degrees of Freedom in a Vector Space
Definition of Dimension
The Dimension of a vector space $V$ is defined as the number of vectors in any of its bases: $$\dim(V) = |\mathcal{B}|$$
| Geometric Space / Subspace | Number of Basis Vectors | Dimension ($\dim$) |
|---|---|---|
| Origin Point ($\{\mathbf{0}\}$) | 0 | 0 |
| Line through origin | 1 | 1 |
| Plane through origin | 2 | 2 |
| Full 3D Euclidean Space ($\mathbb{R}^3$) | 3 | 3 |
| $n$-Dimensional Real Space ($\mathbb{R}^n$) | $n$ | $n$ |
Ambient Dimension vs. Intrinsic Dimension: In machine learning, a dataset with 100 features resides in 100-dimensional ambient space. However, if strong correlations exist, the data points may actually lie on a 5-dimensional hyperplane or manifold. The true intrinsic dimension of the data is 5, not 100.
6 Matrix Rank: Quantifying Non-Redundant Information
The Rank of a matrix is the maximum number of linearly independent column vectors (Column Rank) or row vectors (Row Rank) it contains.
Fundamental Theorem of Rank:
For any rectangular or square matrix $A \in \mathbb{R}^{m \times n}$, the Row Rank equals the Column Rank: $$\operatorname{Rank}(A) = \dim(\operatorname{Col}(A)) = \dim(\operatorname{Row}(A))$$ The rank is bounded by the smallest dimension: $0 \le \operatorname{Rank}(A) \le \min(m, n)$.Computing Rank via Gaussian Elimination
To determine matrix rank, perform elementary row operations until the matrix is in Row Echelon Form (REF). The number of non-zero rows (or pivot positions) equals the rank:
Step 1: Eliminate beneath the first pivot ($R_2 \leftarrow R_2 - 2R_1$ and $R_3 \leftarrow R_3 - R_1$):
Step 2: Swap Rows 2 and 3 ($R_2 \leftrightarrow R_3$) to bring non-zero rows to the top:
Despite having 3 rows and 3 columns, the matrix collapses 3D space into a 2D plane. Column 3 is a linear combination of Columns 1 and 2: $\mathbf{col}_3 = -\mathbf{col}_1 + 2\mathbf{col}_2$.
7 The Four Fundamental Subspaces & Rank-Nullity
Every $m \times n$ matrix $A$ defines four fundamental subspaces that partition vector spaces $\mathbb{R}^n$ and $\mathbb{R}^m$:
The Rank-Nullity Theorem
Total input dimensions ($n$) = output dimensions preserved ($r$) + input dimensions collapsed to zero ($n - r$).
8 Using Rank to Diagnose Linear Systems (Rouché–Capelli)
We can now formally classify any linear system $A\mathbf{x} = \mathbf{b}$ by comparing the rank of $A$ with the rank of augmented matrix $[A \mid \mathbf{b}]$:
Full column rank. Vector $\mathbf{b}$ lies within the column space, and no free variables exist.
Consistent system, but fewer pivots than variables. Exactly $n - r$ free variables parametrize the solution manifold.
Inconsistent system. The target vector $\mathbf{b}$ lies entirely outside the column space $\operatorname{Col}(A)$.
9 Computing Rank and Subspaces in Python
In computational code, `np.linalg.matrix_rank` calculates rank via Singular Value Decomposition (SVD), automatically handling numerical tolerances:
import numpy as np
from scipy.linalg import null_space
# Define 3x3 matrix
A = np.array([
[1, 2, 3],
[2, 4, 6],
[1, 1, 1]
], dtype=float)
# 1. Compute Matrix Rank
r = np.linalg.matrix_rank(A)
print("Rank of A:", r) # Output: 2
# 2. Compute Null Space Basis
ns = null_space(A)
print("Null Space Basis:\n", ns)
nullity = ns.shape[1]
print("Nullity:", nullity) # Output: 1
# 3. Verify Rank-Nullity Theorem (n = 3)
print("Rank + Nullity == n:", r + nullity == A.shape[1]) # True (2 + 1 = 3)10 Real-World Applications in Computer Science & AI
Rank and dimension analysis govern the compression and efficiency of modern machine learning systems:
1. Principal Component Analysis (PCA)
PCA finds the orthonormal basis along directions of maximum variance in high-dimensional datasets, discarding noisy or redundant dimensions to reduce storage and training time.
2. Low-Rank Image Compression
Digital images are 2D pixel matrices. Low-rank matrix approximations (via Truncated SVD) reconstruct the image using a handful of singular vectors, preserving 90%+ perceptual fidelity at a fraction of file size.
3. Recommender Systems (Netflix Prize)
Massive user-movie rating matrices have billions of entries but are modeled as low-rank matrices ($R \approx U V^T$), recovering hidden user preference factors.
4. Multicollinearity Detection
When dataset features are linearly dependent, $X^T X$ becomes singular (rank-deficient), breaking Ordinary Least Squares. Rank diagnostics indicate when feature elimination or regularization (L2) is required.
11 8 Common Pitfalls & Traps
Pitfall 1: Confusing Span with Basis
The Span is the entire infinite vector space generated. The Basis is the minimal set of independent vectors used to generate it.
Pitfall 2: Assuming a Unique Basis
Every vector space possesses infinitely many distinct bases. Only the number of vectors (the dimension) is unique.
Pitfall 3: Picking Columns from the REF
When writing a basis for $\operatorname{Col}(A)$, locate pivot columns in the Row Echelon Form, but choose the corresponding columns from the ORIGINAL matrix!
Pitfall 4: Including $\mathbf{0}$ in a Basis
A basis can never contain the zero vector. Including $\mathbf{0}$ immediately renders the set linearly dependent ($1 \cdot \mathbf{0} = \mathbf{0}$).
Pitfall 5: Ambient Dimension vs. Matrix Rank
A $3 \times 3$ matrix lives in $\mathbb{R}^3$, but its rank can be 1 or 2 if rows/columns are redundant.
Pitfall 6: Assuming Row Rank $\ne$ Column Rank
Even for highly non-square rectangular matrices, Row Rank and Column Rank are always identical.
Pitfall 7: More Vectors $\implies$ More Dimensions
Supplying 4 vectors in $\mathbb{R}^2$ cannot create 4 dimensions; they are guaranteed to be dependent, and the dimension remains 2.
Pitfall 8: Exact Zero Checking in Floating-Point Code
Roundoff noise in computers creates tiny non-zero floats (e.g. `1e-17`). Always use a tolerance threshold when checking rank.
Basis, Dimension & Rank Workbench
Experiment live with vector independence, matrix rank reduction, and PCA projection.
Project 2D data points onto a 1D basis axis. Rotate the basis angle to maximize preserved variance and minimize reconstruction error!
Key Takeaways
Synthesizing new vectors by scaling and summing existing vectors.
The complete subspace formed by all possible linear combinations of a vector set.
No vector in the set can be expressed as a linear combination of the remaining vectors.
The minimal linearly independent generating set that spans the entire vector space.
The invariant number of basis vectors required to navigate a vector space.
The number of independent rows or columns; equals the number of pivots in Row Echelon Form.
Total columns ($n$) = Output rank dimension ($r$) + Null space collapsed dimension ($n - r$).
A linear system is consistent if and only if $\operatorname{Rank}(A) = \operatorname{Rank}([A \mid \mathbf{b}])$.
Low-rank matrix approximations compress data and remove noise along principal basis directions.