Essence of Linear Algebra (5): Linear Systems and Column Space

Linear systems are among the most fundamental problems in linear algebra. When we ask "when does have a solution?", the answer lies in the matrix's column space— this space tells us all the vectors that the matrix can "reach." Understanding column space, null space, and the relationships between them is a crucial step in mastering linear algebra.

From Equations to Geometry: A Fresh Perspective

Remember solving systems of equations in high school? Faced with a system like:The teacher taught elimination: subtract twice the first equation from the second, get, then announce "infinitely many solutions."

But this mechanical computation completely obscures the essence. The truly profound question is: what does this system mean geometrically? Why are there infinitely many solutions?

Linear algebra provides an elegant answer: - Each equation represents a line (or a hyperplane in higher dimensions) - Solutions are the intersection points of these lines - The matrix's column space determines which vectorscan be "reached"

Imagine you're in a city where you can only walk east and north. If someone asks you to reach a point to the southwest, can you do it? The essence of this question is: is the target point within the space you can reach?

Matrix Form of Linear Systems

From Single Equations to Matrices

A linear equationessentially says: usecopies of "2" andcopies of "3" to make "5."

When we have multiple equations:We can write it in compact matrix form:Whereis ancoefficient matrix,is an-dimensional unknown vector, andis an-dimensional constant vector.

Real-Life Analogy: Recipes and Ingredients

Think of this matrix equation as a cooking problem. Suppose you want to make three dishes, each requiring different proportions of ingredients:

Dish	Eggs	Flour	Milk
Omelet	2	0g	50ml
Cake	3	200g	100ml
Pudding	1	0g	200ml

If you have 10 eggs, 400g flour, and 500ml milk, how many servings of each dish can you make?

Let each dish haveservings, giving the system:

This is the real-world meaning of linear systems: resource allocation problems.

Two Perspectives on Linear Systems

Row Perspective: Intersections of Hyperplanes

Consider the system:The row perspective views each equation as a line: - First line:(slope) - Second line:(slope)

The solution is the intersection of the two lines. Drawing them, you'll find they intersect at.

In 3D space, each equation represents a plane, and the solution is the intersection of three planes (or a line, or no intersection).

Column Perspective: Linear Combinations of Vectors

The same system can be reunderstood. Write it as:

Now the question becomes: how can we use linear combinations of and to represent ?

The column perspective's core insight is: -is the "amount used" of the first column vector -is the "amount used" of the second column vector - The goal is to find the right "recipe" to synthesize

Why the Column Perspective Is More Profound

While the row perspective is intuitive, it hides the matrix's internal structure. The column perspective directly reveals key concepts:

Column space: the set of all possiblethat can be synthesized
Linear independence: whether column vectors are redundant
Rank: essentially how many "directions" are available
Existence of solutions: whethercan be synthesized

Imagine you're a painter with only red, yellow, and blue paints. The column perspective asks: "Given these three basic colors, what colors can you mix?"— this is the concept of column space.

Gaussian Elimination: The Systematic Path to Solutions

Algorithm Philosophy

Gaussian elimination is the most basic and important algorithm for solving linear systems. Its core idea is simple: use elementary row operations to transform the matrix to a simpler form.

Elementary row operations are of three types: 1. Swap two rows 2. Multiply a row by a non-zero constant 3. Add a multiple of one row to another

These operations don't change the system's solutions! Why? Because they correspond to equivalent transformations of the equations.

From Augmented Matrix to Row Echelon Form

Take the system:Step 1: Write the augmented matrix:Step 2: Eliminate so the first column has only the first row nonzero (subtract 3 times row 1 from row 2):Step 3: Continue elimination (subtract 2 times row 2 from row 3):Now the matrix is in row echelon form— each row's first nonzero element (the pivot) is to the right of the previous row's pivot.

Step 4: Back substitution: - From row 3:, so - From row 2:, so - From row 1:, soSolution:.

Pivots and Free Variables

During elimination, pivots are the first nonzero elements in each row. Columns without pivots correspond to free variables.

Consider another example:Pivots are in columns 1 and 3, soare pivot variables, andare free variables.

Free variables can take any value, and pivot variables are determined by free variables. This is the case of infinitely many solutions.

Python Implementation of Gaussian Elimination

import numpy as np

def gaussian_elimination(A, b):
    """
    Gaussian elimination to solve Ax = b
    Returns: solution vector x, or None if no solution
    """
    n = len(b)
    # Build augmented matrix
    Ab = np.concatenate([A.astype(float), b.reshape(-1, 1).astype(float)], axis=1)
    
    # Forward elimination
    for col in range(n):
        # Find pivot (partial pivoting for numerical stability)
        max_row = col + np.argmax(np.abs(Ab[col:, col]))
        Ab[[col, max_row]] = Ab[[max_row, col]]  # Swap rows
        
        if np.abs(Ab[col, col]) < 1e-10:
            continue  # Skip zero pivot
        
        # Eliminate
        for row in range(col + 1, n):
            factor = Ab[row, col] / Ab[col, col]
            Ab[row, col:] -= factor * Ab[col, col:]
    
    # Back substitution
    x = np.zeros(n)
    for i in range(n - 1, -1, -1):
        if np.abs(Ab[i, i]) < 1e-10:
            if np.abs(Ab[i, -1]) > 1e-10:
                return None  # No solution
            continue
        x[i] = (Ab[i, -1] - np.dot(Ab[i, i+1:n], x[i+1:])) / Ab[i, i]
    
    return x

# Test
A = np.array([[1, 2, 1], [3, 8, 1], [0, 4, 1]])
b = np.array([2, 12, 2])
x = gaussian_elimination(A, b)
print(f"Solution: {x}")
print(f"Verify Ax = {A @ x}")

Column Space: Where the Matrix Can "Reach"

Definition and Intuition

The column space of matrix, denotedor, is defined as:Simply put,is the set of all possible linear combinations of's column vectors.

Intuitive understanding: If we viewas a "transformation machine," the column space is the set of all vectors this machine can output. Or, if you can move freely in the directions of's column vectors, all positions you can reach form the column space.

Real-Life Analogy: Music Mixer

Imagine a music mixer with three input channels (guitar, bass, drums), each with a volume fader.

Each instrument's sound is a "column vector"
Fader positionsare "coefficients"
The final mix is a linear combination of column vectors

Column space is all possible mixes you can produce. If guitar and bass have very similar tones (linearly dependent), the range of tones you can produce is smaller than expected.

Examples: Column Space in 2D and 3D

Example 1: A line consists of all vectors of form— a line inthrough the origin with direction.

Example 2: A planeThe two column vectorsandspan a plane in. This plane passes through the origin and is determined by these two vectors.

Example 3: The entire spaceThis is the identity matrix, with. Any 3D vector can be expressed as a linear combination of these three column vectors.

Core Theorem: Existence of Solutions

Theorem: The equationhas a solution if and only if.

Proof: - If, by definition, there existssuch that, i.e., a solution exists. - Conversely, if a solutionexists, thenis a linear combination of column vectors, so.

This theorem transforms "does the equation have a solution" into a geometric problem: "is the vector in a certain space."

Null Space: Vectors That Get "Killed"

Definition and Intuition

The null space of matrix, denotedor, is defined as:The null space is the set of all vectors thatmaps to the zero vector.

Intuitive understanding: The null space tells us which directions "disappear"— get "crushed" to the origin by the matrix. If the null space contains only the zero vector,is a "one-to-one" mapping with no information loss.

Real-Life Analogy: Steamroller

Imagine a steamroller rolling across the ground. Originally 3D objects are compressed to 2D.

Any vertical movement gets "crushed" to zero
The null space is the "vertical direction"— all directions that get crushed
Horizontal movements are unaffected — they're not in the null space

Example

Consider the matrix:Row 2 is 2 times row 1, so this matrix compresses the 2D plane to a line.

Finding the null space: Set:Both equations are equivalent, giving. Taking, we get basis vector.Geometrically,is the line inwith direction.

Null Space and Uniqueness of Solutions

Key observation: Ifis a solution to, then(where) is also a solution!

Corollary: - If (null space contains only zero vector), solution is unique - Ifcontains non-zero vectors, infinitely many solutions exist

Rank: The Essence of Dimension

Definition

The rank of matrix, denotedor, is defined as:I.e., the dimension of the column space, which also equals the maximum number of linearly independent column vectors.

Equivalently: - Rank = number of pivots in row echelon form - Rank = maximum number of linearly independent row vectors - Row rank = column rank (this is an important theorem)

Intuitive Understanding of Rank

Rank tells us how many "effective dimensions" the matrix has.

Amatrix with rank 3: transformation is "full," no dimension compressed
Amatrix with rank 2: 3D space compressed to a plane
Amatrix with rank 1: 3D space compressed to a line
Amatrix with rank 0: everything compressed to the origin (zero matrix)

Real-Life Analogy: Information Compression

Imagine describing a color photo over the phone.

If the other person can see red, green, and blue channels (rank=3), you can convey the image completely
If they can only see black and white (rank=1), lots of information is lost
Rank is the number of "information channels"

Rank Calculation Methods

Method 1: Gaussian elimination, count pivots

Two pivots, so .

Method 2: Use Python

import numpy as np

A = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
rank = np.linalg.matrix_rank(A)
print(f"Rank: {rank}")  # Output: Rank: 2

Rank and Solutions of Linear Systems

For anmatrix:

Condition	Meaning
	Full rank square matrix, unique solution
	Full column rank, at most one solution
	Full row rank, if solution exists then infinitely many
	Rank deficient, solution depends on

Rank-Nullity Theorem

Theorem Statement

For anmatrix:Column space dimension + null space dimension = number of columns

Intuitive Understanding

Think of the-dimensional input space as a cake. Matrixcuts it into two parts: - One part is "preserved," mapped to the column space (-dimensional) - One part is "crushed," becomes the null space (-dimensional)

The total size of the cake (-dimensional) doesn't change.

Application

Example:is amatrix with. Find the null space dimension.

Solution:This meanshas 3 free variables, and the null space is a 3-dimensional subspace.

Existence and Uniqueness of Solutions

Complete Analysis Framework

For equation(is anmatrix with rank):

Existence: Solution exists

Uniqueness: Solution is unique r = n$

Four Cases in Detail

Case 1:(full rank square matrix) -is invertible,exists - For any, unique solution - Column space, null space Case 2:(overdetermined system, full column rank) - More equations than unknowns, usually no solution - If, unique solution - In practice, use least squares to find "best approximation"

Case 3:(underdetermined system, full row rank) - More unknowns than equations, excess freedom - For any, solution exists () - Infinitely many solutions, null space dimension is Case 4:and(rank deficient) - Somehave no solution, some have infinitely many - Most "pathological" case, requires specific analysis

Structure of General Solution

Ifhas a solution, the general solution is:Where: -is any particular solution -is any vector in the null space

Geometric meaning: The solution set is an affine subspace obtained by translating the null space.

The Four Fundamental Subspaces

Overview

For anmatrix, there are four closely related subspaces:

Subspace	Symbol	Living in	Dimension
Column space
Null space
Row space
Left null space

Row Space

The row space ofis the column space of:Equivalently, all linear combinations of's row vectors.

Important property:(row rank = column rank)

Left Null Space

The left null space ofis the null space of:Why called "left" null space? Becausecan be seen asmultiplyingfrom the left.

Orthogonality Relations

Core theorem: The four subspaces are pairwise orthogonal!

-: null space and row space are orthogonal -: left null space and column space are orthogonal

Moreover, they're not just orthogonal but orthogonal complements:

- - Intuitive understanding: The-dimensional input space is split into two orthogonal parts — row space and null space. Matrixmaps row space to column space, and crushes null space to the origin.

Engineering Applications

Application 1: Circuit Analysis

Consider a simple circuit network. By Kirchhoff's Current Law (KCL), the sum of currents at each node is zero.

Suppose the circuit has 3 nodes and 5 branches. The incidence matrixdescribes connections between branches and nodes.

The equationdescribes KCL, whereis the branch current vector.gives all possible current distributions.

Practical meaning: The dimension of the null space tells us how many "independent loops" exist in the circuit.

Application 2: Least Squares and Data Fitting

When the systemhas no solution (overdetermined system), we find the "closest" solution.

Normal equation:This is the formula for the least squares solution.

Example: Linear Regression

Given data points, fit a line.4 equations, 2 unknowns, no exact solution. Least squares solution:

import numpy as np

A = np.array([[1, 1], [2, 1], [3, 1], [4, 1]])
b = np.array([2, 3, 5, 4])

# Normal equation
x = np.linalg.lstsq(A, b, rcond=None)[0]
print(f"Best fit: y = {x[0]:.2f}x + {x[1]:.2f}")

Application 3: Computer Graphics

3D graphics transformations are essentially matrix multiplication. When you rotate, scale, or project a model in modeling software,is happening.

Projection problem: Project 3D points to 2D screenThis matrix's null space is the-axis direction — all points along the-axis are projected to the same position.

Inverse problem: Recover 3D structure from 2D images. Since projection losesinformation (non-trivial null space), this problem is ill-posed and requires additional constraints.

Deep Understanding: Geometric Intuition

"Reachability" of Column Space

Imagine standing at the origin with several magic wands (column vectors). Each wand can be used in either direction and scaled to any length.

One wand: You can reach all points on a line
Two non-parallel wands: You can reach all points on a plane
Three non-coplanar wands: You can reach all points in 3D space

If one wand is a combination of others (linearly dependent), it's "redundant" and doesn't increase your reachable range.

"Loss" of Null Space

The null space describes "information loss." If you add any vector from the null space to the input, the output doesn't change.

This is like: - In black and white photos, red and green may be indistinguishable (certain color differences are in the null space) - In low-resolution images, fine details are erased (high-frequency information is in the null space)

"Information Dimension" of Rank

Rank is the "effective information dimension." Amatrix might have rank only 3, meaning it essentially carries only 3-dimensional information — the rest is redundant.

In data science, this gives rise to dimensionality reduction techniques — finding the "essential dimension" of data and discarding noise.

Exercises

Basic Problems

Problem 1: Determine ifis in the column space of.

Problem 2: Find the rank of matrix.

Problem 3: Find the null space of matrix.

Problem 4: Explain why the null space always contains the zero vector.

Problem 5: For amatrixwith, find.

Computation Problems

Problem 6: Use Gaussian elimination to solve:

Problem 7: Find bases for the column space and null space of.

Problem 8: Verify thatsatisfies the rank-nullity theorem.

Problem 9: Find the general solution:

Problem 10: Letbe anmatrix. Prove.

Proof Problems

Problem 11: Prove: Ifis anmatrix with, thenhas a solution for all.

Problem 12: Prove: The null space is orthogonal to the row space, i.e., ifand, then.

Problem 13: Prove: The equationhas a solution if and only ifis orthogonal to all vectors in.

Programming Problems

Problem 14: Implement a function that determines whether a systemhas no solution, unique solution, or infinitely many solutions.

def analyze_system(A, b):
    """
    Analyze the solution situation of linear system Ax = b
    Returns: 'no_solution', 'unique', or 'infinite'
    """
    # Implement this function
    pass

Problem 15: Write a program that computes and visualizes the four fundamental subspaces for a given matrix.

Thought Problems

Problem 16: Why does "row rank = column rank"? Try to explain using geometric intuition.

Problem 17: In machine learning, why is the rank of the feature matrix important? What problems does a rank-deficient feature matrix cause?

Problem 18: Consider image compression. Agrayscale image can be viewed as a-dimensional vector. Why in practice can we represent it with far fewer thannumbers? How does this relate to matrix rank?

Exercise Solutions

Basic Problems (1-11)

1. Column space = all possible outputs, represents "reachable" vectors.

2. Row reduce. If row () appears → no solution.

3. Not necessarily. Depends on rank: → unique; → infinitely many.

4..;. Check: ✓

5. Null space dim =. Possible: 4, 3, or 2.

6. Basis:.is plane in.

7. Different spaces! But (orthogonal complement).

8. Pivot columns: 1 & 3. (full row rank).

9. Null space dim =. 3D subspace "crushed" to zero.

10. General solution:.

11. → → solution exists for all.

Thought Problems (16-18)

16. Why row rank = column rank? Each row operation preserves column relationships; dimension of row space equals dimension of column space by the fundamental theorem.

17. Rank in ML: Rank-deficient feature matrix causes multicollinearity → unstable parameter estimates, non-invertible normal equations in least squares.

18. Image compression & rank: Natural images have low intrinsic dimensionality (redundancy, smoothness) → can be approximated by low-rank matrices. SVD/PCA exploits this to compress with minimal loss.

Summary and Outlook

Core Formulas

Mental Model

When facing a linear system, don't rush to eliminate and compute. First ask yourself three questions:

What is the column space? → Determines whichhave solutions
What is the null space? → Determines whether solution is unique
What is the rank? → Quantifies "effective information"

This is the essential thinking of linear algebra — understanding equations through spaces and dimensions.

References

Strang, G. (2019). Introduction to Linear Algebra. Chapters 3-4.
Lay, D. C. (2015). Linear Algebra and Its Applications. Chapter 2.
3Blue1Brown. Essence of Linear Algebra, Chapters 7-10.
MIT OpenCourseWare. 18.06 Linear Algebra, Lectures 5-11.

This is Chapter 5 of the 18-part "Essence of Linear Algebra" series.