1.20 Rank and linear independence: study notes

Learn AI by Story

1. The idea in one sentence

A set of vectors is linearly independent when none of them can be built from the others, and the rank of a matrix counts how many independent directions its columns really contain, which is the number of dimensions its output can reach.

2. The story from the video

Nia works in a library of ideas where every shelf holds a direction. She is told that she can walk along any shelf, as far as she likes, and combine walks. Two shelves labelled (1, 2) and (2, 4) point the same way, because the second is just double the first, so together they only ever reach one straight corridor. Two shelves labelled (1, 2) and (3, 1) point in different directions, and by combining them Nia can reach every spot on the whole floor. She learns that the number of truly different shelves, not the number of labels on the wall, decides how much of the library she can explore.

3. Key definitions

Vector: an arrow from the origin, written as a list of numbers such as (1, 2). Plain meaning: a direction and a distance.
Linear combination: a vector made by scaling some vectors and adding them. For example 2 x (1, 2) + 3 x (3, 1) = (11, 7). Plain meaning: a mix of walks along the given directions.
Span: the set of all linear combinations of a set of vectors. Plain meaning: everywhere those vectors can take you. For two non-parallel 2D vectors the span is the entire plane; for two lined-up vectors it is only a line through the origin.
Linearly dependent set: a set where at least one vector is redundant, meaning it can be written as a combination of the others; equivalently, some combination with not-all-zero scalars adds up to the zero vector. Plain meaning: someone on the team is doing work that others already cover.
Linearly independent set: a set where no vector is redundant, so each one adds a new dimension to the span; the only combination that gives the zero vector uses all-zero scalars. Plain meaning: every vector brings something new.
Trivial and nontrivial combination: the trivial combination uses all zeros as scalars. A nontrivial one has at least one nonzero scalar. Dependence means a nontrivial combination hits zero.
Basis: a set of linearly independent vectors whose span is the whole space (or, in the MIT wording, a set of vectors, as few as possible, whose combinations produce all vectors in the space). Plain meaning: the shortest possible list of directions that can describe everything.
Dimension: the number of vectors in a basis. Plain meaning: how many independent directions the space has.
Column space: the span of the columns of a matrix, which is the set of all possible outputs. Plain meaning: everywhere the matrix can send things.
Rank: the number of dimensions of the column space, which equals the number of linearly independent columns (the largest number of independent columns). Plain meaning: how many directions survive the motion.
Full rank: the rank equals the number of columns. Only the zero vector maps to the origin. Plain meaning: nothing is wasted.
Rank deficient: rank is less than the number of columns. Plain meaning: some columns are copies or mixes of others.
Null space (kernel): the set of vectors the matrix sends to the zero vector. Plain meaning: the directions that get crushed away.
Collinear and collinearity: vectors (or data columns) lying on one line, or one data column being a multiple of another. Plain meaning: two features saying the same thing. The video called this "repeated" features.
Multicollinearity: a feature that is (nearly) a linear combination of several other features. Plain meaning: redundancy hidden among a crowd of columns. The video did not use this term.
Low-rank: having a rank much smaller than the matrix's size. Plain meaning: simple structure hidden inside a big table.
Numerical rank: the rank computed by a program, which counts singular values above a small threshold because floating-point rounding almost never gives exact zeros. The video did not use this term.

4. Step-by-step explanation

Step 1: start with directions and mixes. A vector is a direction. If you scale it and add it to another scaled vector, you make a combination. Everything you can reach this way is the span.

Step 2: one vector gives a line, two can give a plane, three can give a space. One nonzero vector spans a line through the origin. Two vectors that point in different directions span a flat plane. In 3D, three vectors that are not all in the same flat sheet span all of 3D.

Step 3: redundancy appears when a vector sits inside the span of the others. If the third vector already lies inside the span of the first two, adding it gives nothing new. That vector is redundant, and the set is dependent. If you can drop it without shrinking the span, it was redundant.

Step 4: the zero-sum test. To test dependence, ask whether some nonzero mix of the vectors adds up to the zero vector. For (1, 2) and (2, 4): 2 x (1, 2) - 1 x (2, 4) = (2, 4) - (2, 4) = (0, 0). A nonzero mix gives zero, so the vectors are dependent. For (1, 2) and (3, 1) no such mix exists (we show why in section 6), so they are independent.

Step 5: from vectors to matrices. Put the vectors in as columns. The matrix sends the first basis vector i-hat to the first column, and so on (1.18). The set of outputs is the column space, the span of the columns. So the rank, the dimension of the column space, is the number of independent columns.

Step 6: connect to the determinant (1.19). For a square matrix, a zero determinant means the transformation squashes space into fewer dimensions, so some columns must be dependent and the rank drops below the full size. A nonzero determinant means no squashing, so the columns are independent and the matrix has full rank. A 2x2 matrix of rank 2 has a nonzero determinant. For example, columns (1, 2) and (3, 1) give 1 x 1 - 3 x 2 = -5, which is nonzero.

Step 7: rank as the dimension of the output. Rank 3 in 3D means the output is a solid space. Rank 2 means a flat sheet, rank 1 means a line, rank 0 means only the origin. The rank tells you how many dimensions survive the motion.

Step 8: why the rank matters for solving equations. If a matrix is full rank and square, it is invertible and A x = v has exactly one solution. If it is rank deficient, then either v is outside the column space (no solution) or inside it (infinitely many solutions, because the null space can be added). So rank tells you what kind of answer to expect.

Step 9: compute rank by machine. In practice you do not test all subsets of columns. The cost of checking every subset grows exponentially with the number of columns, which is why the Dive into Deep Learning text calls that inefficient. NumPy computes rank with the singular value decomposition: rank is the number of singular values larger than a small tolerance. This is the same SVD as in 1.15.

5. Everything the video skipped

Rank is also about data tables. A data table with rows as examples and columns as features is a matrix too. Its rank tells you how many truly independent features it holds. If column 5 is exactly 2 times column 1, that column adds nothing and the rank is at most 4.

Exact versus numerical rank. With real measurements, columns are almost never exactly dependent, and floating-point errors mean even exact copies produce tiny nonzero singular values. The NumPy documentation explains that the default threshold is the largest singular value times max(M, N) times the machine epsilon, and that for data with uncertainty larger than floating-point epsilon one should choose a tolerance near that uncertainty. So "rank" in code is a judgement call about what counts as zero.

Near-dependence. Columns that are almost, but not exactly, dependent give a matrix that is technically full rank but nearly singular, and regression with it is unstable. The Dive into Deep Learning text notes that explicit inversion is often avoided because it is numerically unstable, especially for matrices close to low rank.

Basis and dimension. A basis is the minimum number of vectors needed to reach everything. The number of vectors in a basis is the dimension. Independent columns of a matrix form a basis for its column space. This idea is the main topic of 1.21.

Rank and the null space, in the example. In the 3 by 3 example below, the matrix has rank 2 and the null space is the line through (1, 1, -1). That is 3 columns = 2 independent directions + 1 crushed direction. We confirm this by computation in this note. The general statement connecting these numbers is a standard theorem that we did not verify against an opened source, so we treat it as a go-deeper item.

Row rank. A matrix also has rows, and the number of independent rows is equal to the number of independent columns. We did not open a source for this, so we mention it only as something to look up.

Rank of a product and low-rank factorization. A big matrix with low rank can be written as a product of two skinny matrices. This is the idea behind LoRA and behind compressing a table with SVD. The skinny factors hold far fewer numbers than the original.

Links across the roadmap. Earlier: 1.15 Eigenvectors and SVD (singular values reveal numerical rank), 1.18 Linear transformations (columns as landing spots), 1.19 Determinant and inverse (zero determinant means rank drops). Later: 1.21 Basis and change of basis, and 1.22 Orthogonality and projections.

History note. We make no historical claims, because we did not confirm any dates in the sources we opened.

6. Worked examples

All numbers were checked in Python.

Example 1: dependent pair

Vectors u = (1, 2) and w = (2, 4).

Is w a multiple of u? Yes: w = 2 u.
Zero-sum test: 2 x (1, 2) - 1 x (2, 4) = (2 - 2, 4 - 4) = (0, 0), a nonzero mix that gives zero.
As columns, the matrix has rows (1, 2) and (2, 4). Its determinant is 1 x 4 - 2 x 2 = 0.
Its rank is 1. The column space is a line through the origin, and the other direction is lost.

Example 2: independent pair

Vectors p = (1, 2) and q = (3, 1).

Suppose a x (1, 2) + b x (3, 1) = (0, 0). The first coordinate gives a + 3b = 0, so a = -3b. The second gives 2a + b = 0. Substituting: 2 x (-3b) + b = -5b = 0, so b = 0 and then a = 0. Only the trivial mix gives zero, so p and q are independent.
The matrix with columns p and q has rows (1, 3) and (2, 1). Its determinant is 1 x 1 - 3 x 2 = -5, which is nonzero.
Rank is 2, so the span is the whole plane. For instance (11, 7) = 2 x (1, 2) + 3 x (3, 1), since (2 + 9, 4 + 3) = (11, 7).

Example 3: three vectors in 3D, one redundant

Columns c1 = (1, 0, 2), c2 = (0, 1, 1), c3 = (1, 1, 3).

Spot the relationship: c1 + c2 = (1 + 0, 0 + 1, 2 + 1) = (1, 1, 3) = c3. So c1 + c2 - c3 = (0, 0, 0), a nonzero mix giving zero.
The matrix with these columns has determinant 0 and rank 2 (computed numerically).
The output is a flat sheet: every output is a x c1 + b x c2 = (a, b, 2a + b).
The null space contains (1, 1, -1): the matrix sends it to (1 - 1, 1 - 1, 2 + 1 - 3) = (0, 0, 0).
Reading: 3 columns, 2 independent directions, 1 crushed direction.

Example 4: more vectors than dimensions

Take (1, 2), (3, 1) and (2, 4) in the plane. The rank of the matrix with these as columns is 2 (computed), because the plane has only 2 dimensions. With 3 vectors in 2D, at least one must be redundant. Here (2, 4) = 2 x (1, 2) + 0 x (3, 1). So the three are dependent, even though two of them are independent.

Example 5: a data table (illustrative)

Build a table with 100 rows and 5 columns of random numbers, then replace column 5 with 2 times column 1. Computed with NumPy, the rank of the whole table is 4, and the rank of just the first four columns is also 4. The table looks 5 features wide but holds only 4 independent ones. This data is illustrative, not real.

Example 6: LoRA arithmetic (illustrative)

A weight matrix of size 4096 by 4096 has 4096 x 4096 = 16,777,216 numbers. A rank-8 update is written as B times A, with B of size 4096 by 8 and A of size 8 by 4096. These hold 2 x 4096 x 8 = 65,536 numbers. That is 65,536 / 16,777,216 = 0.39 percent of the full count, which is 256 times fewer. This is a teaching calculation for one matrix, not the paper's reported numbers.

7. Comparison table

Concept	What it counts or says	Test	Example from this note
Linearly independent set	No vector is built from the others	Only the zero mix gives zero	(1, 2) and (3, 1)
Linearly dependent set	Some vector is redundant	A nonzero mix gives zero	(1, 2) and (2, 4)
Span	Everything reachable by combinations	Try all mixes	Independent pair spans the plane
Basis	Independent vectors that span the space	Independent plus spanning	(1, 0) and (0, 1)
Rank	Independent columns, output dimension	Machine: count singular values above a tolerance	Rank 2 for the 3 by 3 example
Full rank	Rank equals number of columns	Nothing maps to zero except zero	Rows (1, 3), (2, 1)
Null space	Directions crushed to zero	Solve A x = 0	The line through (1, 1, -1)

8. Common mistakes and myths

Mistake: counting columns instead of independent columns. A table with 5 columns can have rank 4 or less.
Myth: independent means perpendicular. Independent only means not on the same line or sheet; perpendicular vectors are a special, convenient case.
Mistake: concluding that three vectors in 2D can be independent. There are always too many vectors for the room available.
Mistake: checking only pairs. In Example 3 no two vectors are parallel, yet the three are dependent because one is the sum of the other two.
Myth: the zero vector causes no trouble. Any set containing the zero vector is dependent, since 1 times the zero vector is a nonzero mix that equals zero.
Mistake: trusting exact equality on real data. Use a tolerance and look at singular values.
Mistake: thinking low rank means low quality. Low rank often means useful structure that can be compressed.

9. Real-life uses

Regression. Repeated or collinear features make the problem unstable or undefined, because the matrix in the normal equation becomes singular.
LoRA fine-tuning. The abstract of Hu and colleagues says the method freezes the pre-trained weights and injects trainable rank decomposition matrices into each layer of the Transformer, and that compared with full fine-tuning of GPT-3 175B with Adam it can reduce the number of trainable parameters by 10,000 times and the GPU memory requirement by 3 times.
PCA and compression. Many data tables live close to a low-rank subspace, so a few directions capture most of the table (illustrative reasoning, linked to SVD in 1.15).
Solving equations. Rank tells you whether a system has one answer, none, or infinitely many.
Feature checking. Before training, a rank check can reveal that two columns carry the same information.

10. Self-check questions

What does it mean for two vectors to be linearly dependent? One is a multiple of the other, or equivalently a nonzero mix of them adds to zero.
Are (1, 2) and (2, 4) independent? No, because 2 x (1, 2) - (2, 4) = (0, 0).
Are (1, 2) and (3, 1) independent? Yes; the determinant 1 x 1 - 3 x 2 = -5 is nonzero.
What is the span of two independent 2D vectors? The whole plane.
What is the rank of a matrix? The number of independent columns, equal to the dimension of the column space.
What is the rank of the matrix with columns (1, 0, 2), (0, 1, 1), (1, 1, 3)? 2, since the third column is the sum of the first two.
Why can three vectors in 2D never be independent? The plane has only 2 dimensions, so at least one vector is redundant.
A 100 by 5 table has column 5 equal to 2 times column 1. What is its rank? 4 (in the illustrative example).
How does a zero determinant relate to rank? For a square matrix it means rank is less than full, since space is squashed.
A 4096 by 4096 matrix gets a rank-8 update. How many numbers are trained? 2 x 4096 x 8 = 65,536, about 0.39 percent of 16,777,216.

11. Key takeaways, go-deeper list, next roadmap ID

Key takeaways

Independent = nobody is redundant; dependent = a nonzero mix gives zero.
Span = everything reachable; basis = independent vectors that span.
Rank = independent columns = dimension of the output.
Zero determinant means rank below full size.
In practice, rank is computed with SVD and a tolerance.
Low rank is both a danger (collinear features) and an opportunity (LoRA, compression).

Go deeper

Row rank equals column rank.
The relation between rank and null-space size.
Low-rank approximation with SVD.
Regularization for near-collinear features.
Rank of products of matrices.

Next roadmap ID: 1.21 Basis and change of basis.

12. Sources and further reading

Accuracy note: every figure was computed in Python or taken from the pages above, and items labelled "illustrative" are teaching examples, not measurements.

Search This Blog