Independence Basis Dimension

Linear-Algebra tutorial · PySpark.in

1. Linear Independence

In Section 3.1 we hinted at independence — the idea that columns of a matrix point in 'genuinely different directions'. Now we make this precise.

A set of vectors v₁, v₂, ..., vₖ is linearly independent if the only way to make a zero linear combination of them is to use all-zero coefficients. In other words:

c₁v₁ + c₂v₂ + ... + cₖvₖ = 0 only when c₁ = c₂ = ... = cₖ = 0

If there exist coefficients, not all zero, that produce the zero vector, then the vectors are linearly dependent. Dependence means at least one vector is redundant — it can be expressed as a combination of the others.

Vectors are independent when none of them can be made from the others. Dependence means at least one vector is 'already covered' by the rest — it adds no new direction.

How do we test independence? Put the vectors as columns of a matrix A and solve Ax = 0. If the only solution is x = 0 (no free variables, r = n), the columns are independent. If there is a nonzero solution (at least one free variable), the columns are dependent.

2. Three Examples to Build Intuition

Example A — Independent vectors in R³

v₁ = (1,0,0), v₂ = (0,1,0), v₃ = (0,0,1)

These are the standard basis vectors. No one of them can be formed from the others — they each point along a different axis. The matrix with these as columns is the identity I, and Ix = 0 has only the solution x = 0. They are independent.

Example B — Dependent vectors

u₁ = (1,2), u₂ = (2,4)

Here u₂ = 2u₁. The second vector is just a scaled copy of the first. The combination 2u₁ − u₂ = 0 with nonzero coefficients. They are dependent. As columns of a matrix, this gives rank 1.

Example C — A trickier case

w₁ = (1,0,0), w₂ = (0,1,0), w₃ = (1,1,0)

Here w₃ = w₁ + w₂. All three vectors lie in the xy-plane. The combination w₁ + w₂ − w₃ = 0. They are dependent, even though no single one is a scaled copy of another — the dependence involves all three together.

3. Span — What Can We Reach?

The span of a set of vectors is the set of all linear combinations of those vectors. It is the largest space you can reach using those vectors as building blocks.

Span{v₁, v₂, ..., vₖ} = { c₁v₁ + c₂v₂ + ... + cₖvₖ for all scalars c₁,...,cₖ }

The span is always a subspace (it passes through zero, and is closed under addition and scaling). The column space C(A) is exactly the span of the columns of A.

Here is the tension that the concept of 'basis' resolves: adding more vectors to a set can enlarge its span — unless those vectors are already in the span (they are dependent). A dependent vector wastes a spot. An independent vector genuinely expands the reach.

4. Basis — The Perfect Description of a Subspace

A basis for a subspace S is a set of vectors that simultaneously does two things: it spans S (every vector in S can be reached) and it is independent (no vector in the basis is redundant).

A basis is the most efficient description of a subspace: enough vectors to reach everything, but none wasted.

A basis for a subspace S is a set of vectors that (1) spans S and (2) is linearly independent. Every subspace has infinitely many possible bases, but they all have the same number of vectors. That number is the dimension of S.

The standard basis for Rⁿ consists of the n unit vectors e₁ = (1,0,...,0), e₂ = (0,1,...,0), ..., eₙ = (0,...,0,1). But there are infinitely many other valid bases for Rⁿ — any n linearly independent vectors in Rⁿ form a basis.

For the column space C(A), a natural basis is given by the pivot columns of A (not the pivot columns of U or R — go back to the original A and pick the columns that correspond to pivot positions). For the row space, a basis is given by the nonzero rows of R.

5. Dimension — The Size of a Subspace

The dimension of a subspace S is the number of vectors in any basis for S. This number is well-defined — you can choose different bases, but they always have the same size. This is the content of the Basis Theorem:

If v₁,...,vₖ span a subspace S and w₁,...,wₗ are independent vectors in S, then l ≤ k. All bases for S have the same number of vectors. That number is the dimension of S.

Some familiar dimensions:

dim(Rⁿ) = n

dim({0}) = 0 (the zero subspace has dimension zero)

dim(C(A)) = r (rank of A)

dim(N(A)) = n - r (nullity of A)

A line through the origin always has dimension 1 (one basis vector), regardless of which line. A plane through the origin always has dimension 2. These numbers are intrinsic properties of the subspace — they do not depend on how you describe the subspace.

6. The Four Fundamental Subspaces

Every matrix A of size m×n gives rise to four fundamental subspaces. Together they reveal the complete structure of the linear map x ↦ Ax.

1. Column space C(A) ⊆ Rᵐ dim = r

2. Row space C(Aᵀ) ⊆ Rⁿ dim = r

3. Nullspace N(A) ⊆ Rⁿ dim = n-r

4. Left nullspace N(Aᵀ) ⊆ Rᵐ dim = m-r

Notice the beautiful symmetry: the column space and left nullspace both live in Rᵐ and have dimensions r and m−r (adding to m). The row space and nullspace both live in Rⁿ and have dimensions r and n−r (adding to n).

Even more: the column space and left nullspace are perpendicular to each other inside Rᵐ — they are orthogonal complements. Similarly, the row space and nullspace are orthogonal complements inside Rⁿ. This is the content of the Fundamental Theorem of Linear Algebra, which we will meet fully in Chapter 4.

Think of the four subspaces as the four directions of a compass for a matrix. Knowing their dimensions and bases gives you a complete map of what the matrix does: which inputs produce zero (nullspace), which outputs are reachable (column space), and where they live relative to each other.

7. Rank and the Full Picture

We can now summarise the role of rank r in the complete story of Ax = b:

r = rank(A) = dim(C(A)) = dim(C(Aᵀ)) = number of pivots

The rank tells you how much of the input space is 'used' by A. Of the n input dimensions, r are mapped to output, and n−r are sent to zero (the nullspace). Of the m output dimensions, r are reachable from A, and m−r are never reachable (the left nullspace).

Rank is invariant: row operations, column operations, transposing — none of these change the rank. It is a fundamental property of the matrix, not of how it is written.

Final summary: rank r tells you the dimension of four subspaces at once. r = dim C(A) = dim C(Aᵀ). And n-r = dim N(A), m-r = dim N(Aᵀ). The rank-nullity theorem r + (n-r) = n and its column-space twin r + (m-r) = m are the bookkeeping behind all of linear algebra.

References & Further Reading

Gilbert Strang. Introduction to Linear Algebra, 5th ed. Wellesley-Cambridge Press, 2016. (Chapter 3.4)

3Blue1Brown. Essence of Linear Algebra, Chapter 2: Linear Combinations, Span, and Basis Vectors. YouTube, 2016.

Khan Academy. Basis of a subspace. khanacademy.org/math/linear-algebra

End of Blog 7 — Linear Algebra Series