Mathematical Foundations for Machine Learning

Matrix Decompositions, Vector Spaces, and Determinants

📅 Published: 2026-07-09

🎓 Level: postgraduate

👥 Audience: Postgraduate students in Mathematical Foundations for Machine Learning

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Determinant — Lecture 1 (1.6)
Eigenvectors and Eigenvalues — Lecture 1 (1.9, preview)
Vector Spaces — Lecture 3 (3.3) and Lecture 4 (4.3)
Span, Linear Combinations, Independence — Lecture 4 (4.6–4.8)
Basis and Dimension — Lecture 1 (1.12) and Lecture 4 (4.9)

Matrix Decompositions, Vector Spaces, and Determinants

7.1 Determinants via Minors and Cofactors

A square matrix holds many numbers. Yet a single scalar — the determinant — decides whether that matrix can be inverted. It also measures how much the transformation stretches space.

How does one number, computed from dozens of matrix entries, encode the "invertibility" of the whole system? If the determinant is zero, the matrix is singular — no inverse exists, and the transformation destroys information. Why does zero carry that weight?

You already know the 2×2 shortcut: for $[a c b d]$ , the determinant is $a d - b c$ . That formula was not chosen at random. It emerges from a deeper recursive method that works on matrices of any size.

Think of the determinant as the "area multiplier" of a transformation. Take a unit square on a sheet of rubber. Stretch and shear the rubber according to a matrix. The area of the resulting parallelogram equals the absolute value of the determinant. If the determinant is zero, the square flattens into a line segment or a point — area gone, original shape irrecoverable. The analogy breaks when the matrix rotates space in more than two dimensions: the determinant then measures volume (3D) or hypervolume (nD), not area.

With that geometric picture in mind, let's build the method properly. You will see that the 2×2 formula $a d - b c$ is just the cofactor expansion applied to the smallest nontrivial case.

7.1.1 Minor: Shrinking the Matrix by One Element

Pick any square matrix $A$ . Zoom in on one entry — call it $a_{ij}$ , the element in row $i$ and column $j$ . Now delete the entire row $i$ and the entire column $j$ . What remains is a smaller square matrix. Its determinant is called the minor, written $M_{ij}$ .

Minor ( $M_{ij}$ ). Given an

n \times n

matrix

A

, delete row

i

and column

j

. The remaining

(n - 1) \times (n - 1)

submatrix has a determinant. That determinant is the minor

M_{ij}

. In symbols:

M_{ij} = det (submatrix after deleting row i and column j)

For a 1×1 matrix — a single number

[a]

— the determinant is just

a

with no deletion possible. This is the base case of the recursion. For a 3×3 matrix:

A = a_{11} a_{21} a_{31} a_{12} a_{22} a_{32} a_{13} a_{23} a_{33}

Stand on

a_{11}

. Delete row 1 and column 1. You get:

M_{11} = det [a_{22} a_{32} a_{23} a_{33}] = a_{22} a_{33} - a_{23} a_{32}

Stand on

a_{23}

. Delete row 2 and column 3. You get:

M_{23} = det [a_{11} a_{31} a_{12} a_{32}] = a_{11} a_{32} - a_{12} a_{31}

Every element has its own minor. For an

n \times n

matrix, each minor is an

(n - 1) \times (n - 1)

determinant — the same operation, one level deeper. This is the recursion: you keep deleting rows and columns until you hit a 1×1.

The minor by itself is only half the story. The sign matters.

7.1.2 Cofactor: Attaching the Sign

A cofactor, written $C_{ij}$ , is the minor with a positional sign attached:

C_{ij} = (- 1)^{i + j} M_{ij}

The exponent $i + j$ depends on the element's position. When $i + j$ is even, the sign is positive. When $i + j$ is odd, the sign is negative.

For $a_{11}$ : $i + j = 1 + 1 = 2$ (even), so $C_{11} = + M_{11}$ .

For $a_{12}$ : $i + j = 1 + 2 = 3$ (odd), so $C_{12} = - M_{12}$ .

For $a_{21}$ : $i + j = 2 + 1 = 3$ (odd), so $C_{21} = - M_{21}$ .

This produces a checkerboard pattern across the matrix. For a 3×3:

+ - + - + - + - +

The pattern starts with a plus at the top-left and alternates. Memorize this pattern — it is the single most common source of sign errors in determinant calculations.

7.1.3 The Cofactor Expansion

Now you can compute the full determinant. Pick any one row or one column. Multiply each element in that row (or column) by its cofactor. Sum the results. Every choice of row or column gives the same answer.

Expanding along row $i$ :

det (A) = a_{i 1} C_{i 1} + a_{i 2} C_{i 2} + \dots + a_{in} C_{in}

Expanding along column $j$ :

det (A) = a_{1 j} C_{1 j} + a_{2 j} C_{2 j} + \dots + a_{nj} C_{nj}

Each term pairs an element from the chosen line with the determinant of what remains when that element's row and column are removed, signed by position. The result is a scalar — the determinant.

For a 2×2 matrix $[a c b d]$ , expand along the first row:

det (A) = a \cdot C_{11} + b \cdot C_{12} = a \cdot (- 1)^{1 + 1} \cdot det ([d]) + b \cdot (- 1)^{1 + 2} \cdot det ([c]) = a \cdot (+ 1) \cdot d + b \cdot (- 1) \cdot c = a d - b c

The 1×1 determinant of $[d]$ is just $d$ . The 1×1 determinant of $[c]$ is just $c$ . That is the full chain: the cofactor expansion collapses to the familiar formula.

7.1.4 Worked Example: 3×3 via First-Row Expansion

Compute the determinant of:

A = 321152406

by expanding along the first row. The first-row elements are $3, 1, 4$ with checkerboard signs $+, -, +$ .

Step 1 — Write the expansion with cofactor signs:

det (A) = a_{11} C_{11} + a_{12} C_{12} + a_{13} C_{13} = 3 \cdot (+ 1) \cdot det [5206] + 1 \cdot (- 1) \cdot det [2106] + 4 \cdot (+ 1) \cdot det [2152]

Step 2 — Compute each 2×2 sub-determinant:

det [5206] det [2106] det [2152] = 5 \cdot 6 - 0 \cdot 2 = 30 = 2 \cdot 6 - 0 \cdot 1 = 12 = 2 \cdot 2 - 5 \cdot 1 = 4 - 5 = - 1

Step 3 — Assemble with signs:

det (A) = 3 \cdot (+ 30) + 1 \cdot (- 12) + 4 \cdot (+ (- 1)) = 90 - 12 - 4 = 74

Sense-check: All sub-determinants are reasonable in magnitude. The final answer is a positive integer. Since no row or column is a multiple of another, a non-zero determinant makes sense — the matrix should be invertible.

7.1.5 Worked Example: Same 3×3 via First-Column Cross-Check

The same matrix, expanded along the first column instead. The first-column elements are $3, 2, 1$ with checkerboard signs $+, -, +$ .

Expansion along column 1:

det (A) = 3 \cdot (+ 1) \cdot det [5206] + 2 \cdot (- 1) \cdot det [1246] + 1 \cdot (+ 1) \cdot det [1540]

Sub-determinants:

det [5206] det [1246] det [1540] = 30 (same as before) = 1 \cdot 6 - 4 \cdot 2 = 6 - 8 = - 2 = 1 \cdot 0 - 4 \cdot 5 = 0 - 20 = - 20

Assemble:

det (A) = 3 \cdot (+ 30) + 2 \cdot (- (- 2)) + 1 \cdot (+ (- 20)) = 90 + 4 - 20 = 74

The result matches the row expansion. You may pick any row or column. Choose the one with the most zeros — it reduces the number of sub-determinants you must compute.

Scope: The cofactor expansion is defined only for square matrices. It does not apply to rectangular matrices. For a non-square matrix, the determinant is undefined. Expanding along different rows or columns must yield the same result — if your answers disagree, you made an arithmetic error. The method works for any

n \times n

matrix but becomes computationally expensive for large

n

; practical software uses LU or QR decomposition for

n > 3

Common Pitfalls

Forgetting the checkerboard sign. Students often compute the correct minor but forget to attach $(- 1)^{i + j}$ . Double-check: position (1,1) is always positive; (1,2) is always negative.
Using the wrong submatrix. When standing on $a_{ij}$ , you must delete row $i$ and column $j$ — not row $j$ and column $i$ . The indices matter.
Mixing signs within one column expansion. Every position has its own sign. For column 2 with a 3×3, the signs are $-, +, -$ — not all the same.
Stopping the recursion too early. A 2×2 determinant must be resolved to a scalar using $a d - b c$ . A 1×1 determinant is just the element itself. Do not leave a 2×2 as an uncomputed expression.

7.1.6 Student Questions and Answers

Q: How does the 2×2 determinant formula

a d - b c

connect to the general cofactor method? A: The formula

a d - b c

is the cofactor expansion applied to a 2×2 matrix along the first row. Stand at

a

(position 1,1). Delete row 1 and column 1. The only element left is

d

. Its cofactor sign is

(- 1)^{1 + 1} = + 1

, so the term is

+ a \cdot d

. Stand at

b

(position 1,2). Delete row 1 and column 2. The only element left is

c

. Its cofactor sign is

(- 1)^{1 + 2} = - 1

, so the term is

b \cdot (- c) = - b c

. Total:

a d - b c

. The general method and the shortcut agree.

Exam note: You must be able to compute a 3×3 determinant by cofactor expansion along any given row or column. The checkerboard sign pattern is the most common error source on exams — write it out explicitly above your matrix before you begin. If the problem allows choosing your expansion line, scan for rows or columns containing zeros to minimize arithmetic.

The cofactor expansion is the foundation for practical determinant computation in machine learning pipelines. When you compute the Jacobian determinant in a change-of-variables formula for probability density functions, you apply this same recursive method under the hood.

Principal Component Analysis (PCA) checks whether a covariance matrix has zero determinant. A zero means one dimension is redundant, and PCA can safely discard it without losing information. Cramer's rule for solving small linear systems also rests on this framework, though iterative solvers replace it at scale.

The determinant, built from minors and cofactors, gives you one scalar that reveals whether a square matrix is invertible. A zero determinant means the rows (or columns) are linearly dependent — the row space lacks full dimension. This sets up the next topic: understanding the row space and column space of a matrix in Section 7.2.

7.2 Row Space and Column Space

7.2.1 Hook

Every matrix hides two geometric shapes inside it. The rows sketch one picture. The columns sketch another. Here is the surprising part: both shapes always have the exact same number of independent directions — no matter how tall, wide, or lopsided the matrix is. Why is this forced to be true, and what does that shared number tell you?

7.2.2 Intuition and Analogy

The Dual View of a Spreadsheet. Open a spreadsheet where each row is a student and each column is an exam subject. The row space asks: "What grade profiles can I create by mixing students in different proportions?" The column space asks: "What subject-score distributions can I create by blending columns together?" Both views describe the same underlying data — just sliced in perpendicular directions. A physical analogy: the conveyor-belt factory. Imagine a factory with two assembly lines. On one line, raw recipes flow in horizontally — each recipe is a row telling you how much of each ingredient to use. Mix the recipes together, and you get the row space: the set of all build plans your factory can formulate. On the other line, finished-product ingredient profiles flow out vertically — each profile is a column. Combine the columns, and you get the column space: the set of all output profiles your factory actually ships. The plant manager reports one surprising fact: no matter how different the two lines look, they always carry the same number of independent product lines. That number is the factory's rank. Where the analogy breaks: In a real factory, the number of independent raw-material directions and finished-product directions could genuinely differ. In a matrix, they are mathematically forced to be equal — a theorem known as "row rank equals column rank." This is not a coincidence. It is a consequence of the deeper structure of linear transformations.

7.2.3 Formal Definition

Row Space. Let

A

be an

m \times n

matrix. Write its rows as the row vectors

r_{1}, r_{2}, \dots, r_{m}

, each having

n

components. The row space of

A

, denoted

row (A)

, is the set of all linear combinations of these row vectors:

row (A) = span {r_{1}, r_{2}, \dots, r_{m}}

A linear combination means

c_{1} r_{1} + c_{2} r_{2} + \dots + c_{m} r_{m}

for any scalars

c_{1}, \dots, c_{m} \in R

. The row space lives in

R^{n}

— it is a subspace of the same space the rows occupy. Column Space. Write the columns of

A

as the column vectors

c_{1}, c_{2}, \dots, c_{n}

, each having

m

components. The column space of

A

, denoted

col (A)

, is the span of these column vectors:

col (A) = span {c_{1}, c_{2}, \dots, c_{n}}

The column space lives in

R^{m}

— it is a subspace of the same space the columns occupy. Dimension and Rank. The dimension of a subspace is the number of linearly independent vectors needed to span it. A set of vectors is linearly independent if no vector in the set can be expressed as a linear combination of the others. The rank of

A

, denoted

rank (A)

, is the dimension of

row (A)

. Crucially, it also equals the dimension of

col (A)

dim (row (A)) = dim (col (A)) = rank (A)

This equality — row rank equals column rank — is a theorem, not a definition. For non-square matrices (

m \neq = n

), the row space and column space live in different ambient spaces, so they cannot even be compared as sets. But their dimensions match.

Symbol	Meaning	Type
$A$	An $m \times n$ matrix with real entries	Matrix
$m$	Number of rows	Integer
$n$	Number of columns	Integer
$r_{i}$	The $i$ -th row vector of $A$ ( $i = 1, \dots, m$ )	Row vector in $R^{n}$
$c_{j}$	The $j$ -th column vector of $A$ ( $j = 1, \dots, n$ )	Column vector in $R^{m}$
$row (A)$	Row space of $A$	Subspace of $R^{n}$
$col (A)$	Column space of $A$	Subspace of $R^{m}$
$span {\cdot}$	Set of all linear combinations of the given vectors	Subspace
$rank (A)$	Dimension of row space = dimension of column space	Integer

7.2.4 Worked Example

Part A: Row Space of a Matrix with Dependent Rows

Take the $2 \times 2$ matrix $A$ :

A = [1224]

Its rows are $r_{1} = [1, 2]$ and $r_{2} = [2, 4]$ .

Step 1 — Check for dependence. Compare $r_{2}$ to $r_{1}$ component by component: $2 = 2 \cdot 1$ and $4 = 2 \cdot 2$ . Every component of $r_{2}$ is exactly twice the corresponding component of $r_{1}$ . So $r_{2} = 2 \cdot r_{1}$ . These rows are linearly dependent — row two contributes no new direction.

Step 2 — Determine the span. Any linear combination of the rows has the form:

c_{1} [1, 2] + c_{2} [2, 4] = (c_{1} + 2 c_{2}) [1, 2]

The scalar factor $(c_{1} + 2 c_{2})$ can be any real number. Every combination is a scalar multiple of $[1, 2]$ . The row space is a single line through the origin in the direction of $[1, 2]$ :

row (A) = span {[1, 2]}

Step 3 — Dimension. Only one independent direction exists. $rank (A) = 1$

Sense-check: A $2 \times 2$ matrix with rank 1 is singular — its determinant must be zero. Compute: $det (A) = (1) (4) - (2) (2) = 4 - 4 = 0$ . ✓

Part B: Column Space of a Matrix with Independent Columns

Now take a different $2 \times 2$ matrix $B$ :

B = [1431]

Its columns are $c_{1} = [14]$ and $c_{2} = [31]$ .

Step 1 — Check for dependence. Is there a scalar $k$ such that $c_{2} = k \cdot c_{1}$ ? This requires $[3, 1]^{⊤} = k \cdot [1, 4]^{⊤}$ , meaning $3 = k$ and $1 = 4 k$ . The first equation gives $k = 3$ . Plugging into the second: $1 = 4 \cdot 3 = 12$ — a contradiction. No such $k$ exists. The columns are linearly independent.

Step 2 — Determine the span. Two independent vectors in $R^{2}$ span the entire plane. You can reach every point $(x, y)$ as a unique linear combination of these two columns:

col (B) = span {[14], [31]} = R^{2}

Step 3 — Dimension. Two independent directions fill $R^{2}$ completely. $rank (B) = 2$ — full rank.

Sense-check: A full-rank $2 \times 2$ matrix has nonzero determinant. Compute: $det (B) = (1) (1) - (3) (4) = 1 - 12 = - 11 \neq = 0$ . ✓

Key insight across both parts: The row space of $A$ is a line (1D). Its columns are $[1, 2]^{⊤}$ and $[2, 4]^{⊤}$ , which are also dependent — the column space is also 1D. The column space of $B$ is $R^{2}$ (2D), and its rows $[1, 3]$ and $[4, 1]$ are independent — the row space is also 2D. In every case, row rank equals column rank.

7.2.5 Assumptions and Scope

Scope: Row space and column space are defined for any matrix

A \in R^{m \times n}

with real entries. The theory extends to complex matrices using conjugate transposes, but we restrict to

R

here. For non-square matrices (

m \neq = n

), the row space lives in

R^{n}

and the column space lives in

R^{m}

— these are different ambient spaces; you cannot directly compare vectors from the row space with vectors from the column space unless

m = n

. The definition of span assumes all real linear combinations. If you restrict scalars to a subset (e.g., integers or a finite field), the span and its dimension may change. The equality

dim (row (A)) = dim (col (A))

holds for every matrix over any field — it is a theorem, not a convenience.

7.2.6 Visualizing Row Space and Column Space

Picture two 2D coordinate grids side by side, both with axes $x_{1}$ on the horizontal and $x_{2}$ on the vertical.

On the left grid, plot the row vectors of matrix $A = [1224]$ as arrows from the origin. $r_{1}$ points to $(1, 2)$ . $r_{2}$ points to $(2, 4)$ . Both arrows lie on the same straight line — the line $x_{2} = 2 x_{1}$ slicing diagonally upward through quadrants I and III. Shade this line red.

That red line is the row space: a one-dimensional subspace cutting through the 2D plane. Every linear combination of the rows lands on this line. No point off it is reachable.

On the right grid, plot the column vectors of matrix $B = [1431]$ as arrows from the origin. $c_{1}$ points to $(1, 4)$ — steep and narrow, climbing quickly. $c_{2}$ points to $(3, 1)$ — flat and wide, reaching far horizontally. These two arrows fan out in different, non-collinear directions. Shade the entire plane light blue.

The column space is the full $R^{2}$ . Any point $(x, y)$ in the plane is reachable as $a c_{1} + b c_{2}$ for some scalars $a, b$ .

The takeaway: the row space (a 1D red line) and the column space (a 2D blue plane) belong to different matrices in these visuals. But for any single matrix, the row space and column space always share the same dimension. If your rows span a line, your columns span a line too — just potentially in a different-looking direction. If your rows span a plane, so do your columns. The shapes may differ, but the dimension number is invariant.

7.2.7 Common Pitfalls

Pitfall 1 — Confusing the number of vectors with the dimension of the space. A

3 \times 3

matrix has three rows. You might assume the row space is 3-dimensional. That is wrong. The dimension of the row space equals the number of independent rows, not the total count. Three rows that are all multiples of each other span only a 1D line — rank 1, not rank 3. Pitfall 2 — Swapping where each space lives. For an

m \times n

matrix, the row space is a subspace of

R^{n}

because each row has

n

entries. The column space is a subspace of

R^{m}

because each column has

m

entries. Beginners often reverse this: they think the row space lives in

R^{m}

because there are

m

rows. Count the entries per vector, not the number of vectors. Pitfall 3 — Assuming row space equals column space for square matrices. For a square matrix, both spaces live in

R^{n}

, but they are different subspaces. Take

A = [0010]

. The row space is

span {[0, 1]}

— a horizontal line. The column space is

span {[1, 0]^{⊤}}

— a vertical line. Same dimension (rank 1) but completely different sets of vectors. Pitfall 4 — Forgetting that rank is a single number. You cannot have "row rank = 2, column rank = 3." The theorem that row rank equals column rank means the rank of a matrix is one well-defined integer. If your row-space calculation gives rank 2 but your column-space calculation gives rank 3, you made an arithmetic error — find it and fix it.

7.2.8 Recap and Bridge

Recap: The row space is what your matrix can build by mixing its rows — it lives in

R^{n}

. The column space is what your matrix can build by mixing its columns — it lives in

R^{m}

. Both always share the same dimension: the rank. Next, we meet their companion: the null space — the set of all vectors the matrix crushes to zero. Together with the row and column spaces, the null space completes the quartet of fundamental subspaces described by the Fundamental Theorem of Linear Algebra.

7.2.9 Real-World and Domain Connections

In machine learning, your design matrix $X$ has one row per training example and one column per feature. The row space tells you the set of all possible sample profiles you can create by mixing existing training examples. This is critical for understanding dataset diversity and for techniques like data augmentation.

The column space tells you the set of all reachable prediction targets. If your target vector $y$ lies outside the column space of $X$ , no linear model can achieve zero training error. The dimension of the column space — the rank — reveals the effective number of independent features your data carries.

A rank-deficient design matrix (rank < number of columns) signals multicollinearity: some features are redundant linear combinations of others. This breaks ordinary least squares regression because the normal equations $(X^{⊤} X) β^= X^{⊤} y$ become singular. The matrix $X^{⊤} X$ is rank-deficient and cannot be inverted.

Techniques like ridge regression, PCA-based dimension reduction, and feature selection all trace their motivation back to this observation. When your column space is cramped, your model is crippled. Understanding row and column spaces is the geometry of why your model can or cannot learn from the data you feed it.

7.3 Null Space and the Rank Nullity Theorem

7.3.1 Hook

Can a matrix completely erase information? Shout into a microphone that records nothing — your voice exists, the microphone runs, but the output stays silent. Matrices do the same thing: certain input vectors get completely annihilated, producing exactly zero output. Which inputs get destroyed, and what does that tell us about the matrix itself? That set of doomed inputs is the null space.

7.3.2 Intuition and Analogy

The shadow projector. Stand in sunlight. Your body is three-dimensional, but your shadow on the ground is flat — only two-dimensional. The direction from your head toward the sun collapses to a point in the shadow. That lost vertical direction is the null space of the projection. Every point along a vertical line through your body produces the same shadow point. The projection matrix maps that entire vertical direction to zero. The rank of the shadow (its 2D flatness) plus the nullity (the 1D lost height) sum to the full 3D space you occupy. What the sun erases, the null space captures.

7.3.3 Formal Definition

Null space (kernel). For an

m \times n

matrix

A

, the null space is the set of all vectors

x \in R^{n}

satisfying

ker (A) = {x ∣ A x = 0}

Every symbol:

ker (A)

denotes the null space, also called the kernel.

x

is a column vector with

n

entries — an input to the transformation.

0

is the zero vector in

R^{m}

— the output space. The condition

A x = 0

means the matrix

A

transforms

x

into nothing; the input is annihilated. Rank nullity theorem. For any

m \times n

matrix

A

rank (A) + dim (ker (A)) = n

rank (A)

counts the number of linearly independent rows (equivalently, columns).

dim (ker (A))

is the nullity — the dimension of the null space.

n

is the number of columns, i.e. the dimension of the input space

R^{n}

. The theorem partitions

R^{n}

into two pieces: directions preserved by

A

(rank) and directions collapsed to zero (nullity). Their sum always equals the total input dimension. Orthogonality of row space and null space. Every row of

A

is perpendicular to every vector in the null space. If

r_{i}

is the

i

-th row and

x \in ker (A)

, then

r_{i} \cdot x = 0

. This holds because each entry of

A x

is the dot product of a row with

x

, and

A x = 0

forces every such dot product to zero. The null space is the orthogonal complement of the row space — together they span

R^{n}

at right angles.

7.3.4 Worked Example — 2×2 Null Space

Find the null space of $A = [1224]$ .

Step 1 — Set up $A x = 0$ .

[1224] [x_{1} x_{2}] = [00]

Step 2 — Write the linear system.

x_{1} + 2 x_{2} 2 x_{1} + 4 x_{2} = 0 = 0

Step 3 — Spot row dependency. The second row equals $2 \times$ the first row. Both equations encode the same constraint: $x_{1} + 2 x_{2} = 0$ . The matrix has rank 1 — only one independent direction.

Step 4 — Solve. Isolate $x_{1} = - 2 x_{2}$ . Let $x_{2} = t$ be a free parameter sweeping all real numbers.

[x_{1} x_{2}] = t [- 2 1], t \in R

Answer. $ker (A) = span {[- 2 1]}$ — a line through the origin along the direction $[- 2, 1]^{⊤}$ . The nullity is 1.

Verify rank nullity. $rank (A) = 1$ . $dim (ker (A)) = 1$ . Sum: $1 + 1 = 2 = n$ . ✓

Verify orthogonality. Dot product of row $[1, 2]$ with null-space vector $[- 2, 1]$ : $1 (- 2) + 2 (1) = - 2 + 2 = 0$ . The row and the null-space direction are perpendicular. ✓

7.3.5 Assumptions and Scope

Scope: The rank nullity theorem applies to every real matrix

A \in R^{m \times n}

. The input space is

R^{n}

— indexed by the column count, not the row count. The theorem holds equally for square, tall (

m > n

), and wide (

m < n

) matrices. For complex matrices the identical statement holds over

C

. The null space is always a subspace: it contains the zero vector and is closed under addition and scalar multiplication. The perpendicular relationship between the row space and the null space relies on the standard Euclidean dot product in

R^{n}

7.3.6 Geometric Intuition — Perpendicular Subspaces

Picture $R^{n}$ as your ambient space. The row space of $A$ sits inside it as a subspace — a line, a plane, or a higher-dimensional flat — always passing through the origin. The null space is another subspace, also through the origin. These two subspaces meet only at zero and sit at perfect right angles. Pick any vector from the row space and any vector from the null space; their dot product is always zero.

For a concrete 3D example: take a rank-2 $3 \times 3$ matrix. Its row space spans a 2D plane through the origin. Its null space is a 1D line perpendicular to that plane, poking straight out like a flagpole. The entire 3D space is the direct sum of these two orthogonal pieces.

This geometric picture is why the dimensions add up to $n$ . The row space and null space form an orthogonal coordinate frame that exhausts $R^{n}$ . What one subspace misses, the other supplies — at a right angle.

7.3.7 Common Pitfalls

Pitfall 1 — Confusing $m$ with $n$ . The theorem uses

n

(number of columns, input dimension), not

m

(number of rows, output dimension). For a

5 \times 3

matrix,

n = 3

, so

rank (A) + dim (ker (A)) = 3

. The fact that the output lives in

R^{5}

is irrelevant to this equation. Pitfall 2 — Assuming the null space is always 1D. Nullity equals

n - rank (A)

. For a

3 \times 3

matrix of rank 1, the null space is a 2D plane — not a line. The fewer independent rows, the larger the null space. Pitfall 3 — Forgetting the zero vector.

0

always belongs to the null space because

A 0 = 0

. The null space is never empty. For a full-rank matrix, the null space is

{0}

— a zero-dimensional subspace, but still a valid subspace. Pitfall 4 — Mixing up row space and column space. The null space is orthogonal to the row space, not the column space. The row space lives in

R^{n}

(input side). The column space lives in

R^{m}

(output side). Orthogonality requires both subspaces to live in the same ambient space, so only the row space can be perpendicular to the null space.

7.3.8 Student Questions and Answers

Q: Can you explain the null space purely with a 2D perspective? A: Take a

2 \times 2

matrix like

[2142]

. Both rows are multiples of

[1, 2]

. The equation

A x = 0

reduces to the single line

x_{1} + 2 x_{2} = 0

with slope

- \frac{1}{2}

. Every point on this line is a null-space vector. The row space has direction

[1, 2]

with slope 2. These two lines are perpendicular — the product of their slopes is

- 1

. The entire 2D plane is exactly the span of the row-space line and the null-space line together. Q: When does the null space become a plane? A: The null space is a 2D plane whenever

n \geq 3

and

rank (A) = n - 2

. For a

3 \times 3

matrix, rank 1 gives nullity 2 — a plane through the origin. For a

4 \times 4

matrix, rank 2 also gives a 2D null space. The general formula is

dim (ker (A)) = n - rank (A)

. To get a plane specifically, you need exactly two collapsed dimensions, meaning the rank must be

n - 2

. Q: Is the maximum nullity always

n - 1

? A: For a non-zero matrix, yes. The rank is at least 1 (assuming

A

is not the zero matrix), so nullity cannot exceed

n - 1

. If

A

is the zero matrix — every entry is zero — then rank is 0 and nullity is

n

; the entire input space collapses. In practice, matrices in ML and data science are rarely the zero matrix, so the practical upper bound is

n - 1

7.3.9 Exam Guidance

Exam note: Terminology questions are common — define

ker (A)

, nullity, and rank precisely. Memorize the rank nullity theorem:

rank (A) + dim (ker (A)) = n

. Expect problems asking you to compute the null space of a small matrix (2×2 or 3×3) and verify the theorem. Conceptual question: "A

4 \times 4

matrix has rank 1. What is the dimension of its null space?" Answer:

4 - 1 = 3

. A square matrix is invertible if and only if its null space is

{0}

— nullity zero.

7.3.10 Recap and Bridge

The rank nullity theorem is the algebraic hinge between what a matrix preserves and what it destroys.

Recap: The null space collects every input vector that a matrix sends to zero. The rank nullity theorem states that the number of independent directions preserved (rank) plus the number collapsed (nullity) equals the input dimension

n

. The row space and null space are orthogonal partners that together span

R^{n}

. Bridge: This theorem is the foundation for all matrix factorizations that follow. Eigendecomposition, singular value decomposition, and QR decomposition all explicitly separate the directions a matrix preserves from the directions it destroys. Understanding the rank nullity split prepares you to see every factorization as a structured way to expose that split.

7.3.11 Real-World and Domain Connections

In machine learning, the null space surfaces wherever linear systems are underdetermined. Principal Component Analysis discards low-variance directions — those discarded eigenvectors form the null space of the reduced-rank approximation. In high-dimensional regression with more features than samples ( $p > n$ ), the design matrix has a non-trivial null space. That makes coefficients non-unique. Ridge regression penalizes large coefficients precisely in those null-space directions.

In compressed sensing, signals are recovered by exploiting their near-residence in the null space of a measurement matrix. In graph learning, the graph Laplacian's null space encodes the connected components. Its dimension equals the number of disconnected pieces in the graph. Recognizing what a matrix ignores is as powerful as understanding what it preserves.

7.4 Matrix Composition and Decomposition — The Big Picture

7.4.1 Hook + Intuition — Why Order Is Everything

Matrix multiplication reads right-to-left. In the product

A B

, the rightmost matrix

B

acts first, and

A

acts second. This surprises anyone who grew up with ordinary number multiplication, where order never matters. But matrices encode transformations, and transformations are sequences — order changes everything.

Think of a cooking recipe. You crack eggs into a bowl. You whisk them. You pour the mixture into a hot pan. You cannot pour raw eggs into the pan before cracking them. You cannot whisk after the eggs are already cooking. Each step depends on the previous one. Matrix multiplication works the same way: $A B$ means $B$ transforms your data first, then $A$ transforms the result. Decomposition is the reverse — given the finished omelette, identify the sequence of steps that produced it.

7.4.2 Formalize — What Composition and Decomposition Mean

Composition multiplies two or more transformation matrices. Writing

C = A B

means: apply

B

to your vectors, then apply

A

to the output. The product

C

now behaves as a single unified transformation. Decomposition factorizes a matrix into simpler pieces. You start with a complex matrix

M

and break it into a product like

M = LU

M = Q Λ Q^{- 1}

. Each factor does one elementary operation — stretch, shear, or rotate. Their product reconstructs the original exactly. Decomposition reveals the hidden structure inside any transformation.

7.4.3 Assumptions and Scope

Scope: This section provides a conceptual overview only. We assume matrices are square and real-valued unless stated otherwise. Cholesky requires symmetric positive definiteness. Eigendecomposition requires diagonalizability. SVD works on any rectangular matrix. We do not cover algorithms, numerical stability, or computational complexity here.

7.4.4 Visual Intuition — A Cube Under Transformation

Picture a unit cube sitting at the origin. Its vertices mark the corners of a neat, axis-aligned box. Apply a shear matrix. The cube warps — its right angles stretch into oblique angles, and the whole shape tilts sideways. Now apply a rotation matrix. The tilted, warped cube spins around some axis, landing in a completely different orientation. Reverse the order. Rotate the original cube first — it spins cleanly. Then shear the already-rotated cube. The shear now pulls in a direction that is itself rotated, producing a visibly different final shape. Same cube, same two transformations, different order, different result. That is what composition captures.

Now imagine the reverse problem. Someone hands you a mangled, rotated, stretched cube and asks: "Find the stretch, the shear, and the rotation that produced this." Decomposition solves exactly that. It identifies the hidden sequence of simple steps behind any complex transformation.

7.4.5 Comparison — Three Decompositions at a Glance

Decomposition	Form	What It Reveals	Key Requirement
Cholesky	$A = L L^{T}$	Fast factorization into lower-triangular times its transpose	Matrix must be symmetric positive definite
Eigendecomposition	$A = Q Λ Q^{- 1}$	Exposes eigenvalues and eigenvectors — the intrinsic stretch directions	Matrix must be square and diagonalizable
SVD	$A = U Σ V^{T}$	Factors any rectangular matrix into rotation, scaling, rotation	None — works on every matrix

Cholesky is specialized and fast. Eigendecomposition reveals intrinsic structure. SVD is the universal tool. Each serves a different purpose, and you will see all three in the sections ahead.

7.4.6 Pitfalls

Order dependency confuses intuition. Reading

A B

as "first

A

, then

B

" is the single most common mistake. Always read right to left. Not every matrix decomposes cleanly. A non-positive-definite matrix has no Cholesky factor. A non-diagonalizable matrix blocks Eigendecomposition. A decomposition that exists on paper may be numerically fragile. Ill-conditioned matrices amplify rounding errors, making computed factors unreliable in practice.

7.4.7 Recap and Bridge to Cholesky

Matrix composition chains transformations — right to left, order matters. Decomposition reverse-engineers the chain, revealing the elementary operations hidden inside a complex matrix. Cholesky, Eigendecomposition, and SVD are three different decomposition strategies, each suited to different matrix types and goals. Next, we begin with Cholesky — the fastest and most specialized of the three.

7.4.8 Real-World and Domain Connection

Decomposition powers nearly every corner of applied computation. In machine learning, SVD compresses images and reduces the dimensionality of feature spaces through Principal Component Analysis. In physics simulations, Cholesky factors solve the normal equations of least-squares regression in one efficient pass. In graph theory, Eigendecomposition of the Laplacian matrix reveals community structure via spectral clustering.

In computer graphics, any 3D object's movement comes from composing rotation, scaling, and translation matrices. This ranges from a video game character to a CAD model. Decomposition answers the inverse question: what sequence of moves brought this object here?

7.5 Cholesky Decomposition

7.5.1 The Matrix Square Root

Can you take the square root of a matrix? Just as √9 = 3 because 3 × 3 = 9, the Cholesky decomposition finds a matrix L such that L × L^T = A. You factor A into two triangular "halves" — one lower, one upper. This is the matrix analogue of a square root: a clean, structured factorization that simplifies everything downstream.

Think of factoring a number into primes: 12 = 2 × 2 × 3. You break a complex object into simpler building blocks. Cholesky does the same for matrices — it factors a symmetric positive definite matrix A into L L^T, where L is lower triangular. Each column of L acts like a cascade of simple operations, replacing one dense matrix with a product of two sparse, structured ones. Where prime factorization reveals the DNA of a number, Cholesky reveals the "skeleton" of a matrix.

7.5.2 Formal Definition

Cholesky Decomposition. If A is symmetric (A = A^T — mirroring across the diagonal leaves it unchanged) and positive definite (x^T A x > 0 for every nonzero vector x), then A factors uniquely as:

A = L L^{T}

where L is a lower triangular matrix — every entry above the main diagonal is zero. For an n × n matrix, L has the shape:

L = ℓ_{11} ℓ_{21} ℓ_{31} ⋮ ℓ_{n 1} 0 ℓ_{22} ℓ_{32} ⋮ ℓ_{n 2} 00 ℓ_{33} ⋮ ℓ_{n 3} \dots \dots \dots ⋱ \dots 000 ⋮ ℓ_{nn}

Every symbol named:

Symbol	Meaning	Type
A	Original matrix, must be symmetric positive definite	n × n matrix
L	Cholesky factor, lower triangular	n × n matrix
L^T	Transpose of L, upper triangular	n × n matrix
ℓ_ij	Entry of L at row i, column j; zero when i < j	Scalar
x^T A x > 0	Positive definiteness condition for all nonzero x	Scalar inequality

Key determinant shortcut. Because L is triangular, its determinant is simply the product of its diagonal entries:

det (A) = det (L L^{T}) = det (L) \cdot det (L^{T}) = (det (L))^{2} = (ℓ_{11} \cdot ℓ_{22} \cdot \dots \cdot ℓ_{nn})^{2}

This replaces an expensive O(n!) cofactor expansion with n multiplications. For a 100 × 100 matrix, the difference is between a microsecond and the age of the universe.

7.5.3 Worked Example: 2×2 Cholesky

Decompose A = [[2, 3], [3, 5]].

Step 1: Verify the conditions. A is symmetric because A^T = A (the off-diagonal entries are both 3). To check positive definiteness, compute the eigenvalues: solve det(A − λI) = (2 − λ)(5 − λ) − 9 = λ² − 7λ + 1 = 0. Both roots are positive (≈ 6.85 and ≈ 0.15). So A is symmetric positive definite — Cholesky applies.

Step 2: Set up the unknown L. Write L as a lower triangular matrix with unknowns:

L = [ℓ_{11} ℓ_{21} 0 ℓ_{22}], L L^{T} = [ℓ_{11}^{2} ℓ_{11} ℓ_{21} ℓ_{11} ℓ_{21} ℓ_{21}^{2} + ℓ_{22}^{2}]

Step 3: Match entries position by position. Equate L L^T with A:

ℓ_{11}^{2} ℓ_{11} ℓ_{21} ℓ_{21}^{2} + ℓ_{22}^{2} = 2 = 3 = 5 ⟹ ⟹ ⟹ ℓ_{11} = 2 ℓ_{21} = \frac{3}{ℓ _{11}} = \frac{3}{2} ℓ_{22}^{2} = 5 - (\frac{3}{2})^{2} = 5 - \frac{9}{2} = \frac{1}{2} ⟹ ℓ_{22} = \frac{1}{2}

Step 4: The Cholesky factor.

L = 2 \frac{3}{2} 0 \frac{1}{2}

Step 5: Apply the determinant shortcut. Compute det(A) directly from the diagonals of L:

det (A) = (ℓ_{11} \cdot ℓ_{22})^{2} = (2 \cdot \frac{1}{2})^{2} = 1^{2} = 1

Sense-check: The standard 2×2 determinant formula gives (2)(5) − (3)(3) = 10 − 9 = 1. The shortcut matches the direct calculation.

7.5.4 Scope and Pitfalls

Scope: Cholesky decomposition works only for matrices that are both symmetric (A = A^T) and positive definite (all eigenvalues strictly positive). If either condition fails, the algorithm breaks — you will encounter a negative number under a square root, which has no real solution. Indefinite matrices (mixed positive and negative eigenvalues), singular matrices, and non-symmetric matrices are all out of scope. For those cases, use LU decomposition or QR decomposition instead.

Visualise the L matrix as a scaffolding that constructs A from the ground up. Each column adds one more "layer" of structure. Column 1 sets the scale of the first variable. Column 2 introduces a contribution that depends on variable 1. Column 3 depends on variables 1 and 2.

You build the complete matrix by stacking these triangular layers. Lower triangular means each new variable can depend only on variables that came before it. This cascading dependency structure is what makes triangular systems so efficient to solve.

Common pitfalls. (1) Applying Cholesky to a non-SPD matrix. If A is not positive definite, you will hit a negative radicand — ℓ_jj² becomes negative, and the square root fails in the reals. Always test positive definiteness first by checking eigenvalues or confirming all leading principal minors are positive. (2) Sign errors on diagonal entries. The formula gives ℓ_jj = √(something). By convention, you take the positive square root. Choosing a negative root produces a valid factorization of a sort, but it breaks uniqueness and confuses downstream algorithms that assume positive diagonals. (3) Confusing L and L^T. L is lower triangular; its transpose is upper triangular. Multiplying in the wrong order (L^TL instead of LL^T) produces a completely different matrix. (4) Forgetting the square in the determinant formula. det(A) = (∏ ℓ_ii)², not ∏ ℓ_ii. Missing the square halves the true determinant.

7.5.5 Exam Guidance and Connections

Exam note: Cholesky decomposition appears very rarely in MFML exams. When it does appear, the question almost always targets the determinant shortcut: given a Cholesky factor L, compute det(A) as (ℓ₁₁ · ℓ₂₂ · ... · ℓ_nn)². Do not spend time memorising the full column-by-column algorithm. Focus on understanding why A = L L^T makes the determinant trivial, and practise applying the shortcut to a given 2×2 or 3×3 L.

Recap. You have seen that every symmetric positive definite matrix A factors uniquely as A = L L^T with L lower triangular. The triangular structure of L delivers two practical wins. Determinants drop from O(n!) to O(n). Solving linear systems Ax = b splits into two cheap triangular solves — forward substitution (Ly = b) then backward substitution (L^Tx = y). This is Cholesky as the "matrix square root": a clean, structured decomposition that exposes the inner scaffolding of A.

Bridge to Eigen decomposition. Cholesky is a special case of a broader idea — factoring a matrix into simpler pieces. Eigen decomposition generalises this: A = QΛQ^T, where Q is orthogonal (a rotation) and Λ is diagonal (a pure scaling). Where Cholesky gives you one triangular factor, eigen decomposition gives you a rotation, a stretch, and a rotation back. This unlocks principal component analysis, spectral clustering, and the geometry of quadratic forms — all coming up next.

Real-world impact. In Monte Carlo simulations, you need correlated random variables. Stock prices move together. Sensor networks share noise. Bayesian prior samples have known covariance. You start with uncorrelated standard normal noise z. Given a target covariance matrix Σ, you compute its Cholesky factor: Σ = L L^T. Then x = Lz produces a vector with covariance exactly Σ.

Every correlated simulation in quantitative finance, weather forecasting, and computational statistics leans on this technique. For solving large linear systems Ax = b, Cholesky is typically twice as fast as Gaussian elimination. That is why it underpins the numerical engines inside optimisation libraries, physics simulators, and machine learning frameworks.

7.6 Eigen Decomposition (Diagonalization)

7.6.1 Hook — What Stretches Without Turning?

What if a matrix only stretched vectors, never turned them?

Imagine stretching a rubber sheet. Pull one direction — the sheet elongates purely there. Pull another — it elongates purely there too. These special directions only stretch. But most directions on the sheet get sheared and stretched. A matrix is like that sheet. It twists most vectors. Yet hidden inside every square matrix are special directions that only get scaled — never rotated. Find those directions, and the entire transformation reduces to pure axis-aligned stretching after a simple change of viewpoint. That is eigen decomposition.

7.6.2 Formalizing Eigen Decomposition

Eigen decomposition factorizes a square matrix

A

into three matrices:

A = P D P^{- 1}

Build it from the core eigenvalue equation

A v = λ v

. Any nonzero vector

v

that only gets scaled by

A

(no rotation) is an eigenvector. The scalar

λ

is its eigenvalue. The two-step computation:

Solve the characteristic equation $det (A - λ I) = 0$ to find all eigenvalues $λ_{1}, λ_{2}, \dots, λ_{n}$ .
For each $λ_{i}$ , solve the nullspace equation $(A - λ_{i} I) v_{i} = 0$ to find eigenvector $v_{i}$ .

Every symbol named:

$λ_{i}$ — the $i$ -th eigenvalue. A scalar. Tells how much the matrix stretches along $v_{i}$ .
$v_{i}$ — the $i$ -th eigenvector. An $n \times 1$ vector. The invariant direction that only gets scaled.
$P$ — the $n \times n$ matrix whose columns are the eigenvectors $v_{1}, v_{2}, \dots, v_{n}$ .
$D$ — the $n \times n$ diagonal matrix. Entry $D_{ii} = λ_{i}$ . Every off-diagonal entry is zero.
$P^{- 1}$ — the inverse of $P$ . Reverses the change of basis that $P$ performs.
$P^{⊤}$ — the transpose of $P$ . Equals $P^{- 1}$ in the special symmetric-matrix case.

How does $A = P D P^{- 1}$ actually work? The transformation happens in three steps, applied right to left:

$P^{- 1}$ applies first. It shears the eigenvectors so they snap onto the standard coordinate axes. The arrows that used to point in the eigenvectors' directions now point along $x^$ and $y^$ .
$D$ applies next. Pure scaling. Axis $i$ stretches by $λ_{i}$ . A diagonal matrix cannot shear or rotate — it can only scale each axis independently.
$P$ applies last. It shears the axes back to point where the eigenvectors originally lived. The inverse of step 1.

Net effect: shear-to-axes → stretch → shear-back. Every linear transformation $A$ can be seen this way, provided $A$ is diagonalizable.

7.6.3 Worked Example — Full 2×2 Eigen Decomposition

Given the symmetric matrix

A = [2.5 - 1 - 1 2.5]

Step 1 — Characteristic equation. Solve $det (A - λ I) = 0$ :

det [2.5 - λ - 1 - 1 2.5 - λ] = (2.5 - λ)^{2} - 1 = 0

λ^{2} - 5 λ + 5.25 = 0 \Rightarrow (λ - 3.5) (λ - 1.5) = 0

λ_{1} = 3.5 λ_{2} = 1.5

Sense-check: sum $= 3.5 + 1.5 = 5 = tr (A)$ . ✓

Step 2 — Eigenvector for $λ_{1} = 3.5$ . Solve $(A - 3.5 I) v_{1} = 0$ :

[- 1 - 1 - 1 - 1] [x_{1} x_{2}] = [00] \Rightarrow x_{1} = - x_{2}

Take $x_{2} = 1$ , raw vector $[- 1, 1]^{⊤}$ . Normalize:

v_{1} = [- 1/ 2 1/ 2]

Step 3 — Eigenvector for $λ_{2} = 1.5$ . Solve $(A - 1.5 I) v_{2} = 0$ :

[1 - 1 - 1 1] [x_{1} x_{2}] = [00] \Rightarrow x_{1} = x_{2}

Take $x_{2} = 1$ , raw vector $[1, 1]^{⊤}$ . Normalize:

v_{2} = [1/ 2 1/ 2]

Sense-check: $v_{1} \cdot v_{2} = - \frac{1}{2} + \frac{1}{2} = 0$ . Orthonormal. ✓

Step 4 — Assemble $P$ and $D$ :

P = [- 1/ 2 1/ 2 1/ 2 1/ 2] D = [3.5 0 0 1.5]

Final answer: $A = P D P^{⊤}$ (spectral form — $A$ is symmetric). Multiply out to verify it recovers the original matrix.

When $A$ is symmetric ( $A^{⊤} = A$ ), the eigenvectors can be chosen orthonormal — unit length and mutually perpendicular. Then $P^{- 1} = P^{⊤}$ , and the decomposition simplifies to the spectral decomposition $A = P D P^{⊤}$ . This is not a separate topic. It is eigen decomposition applied to symmetric matrices. The formula is cleaner, but the computation is identical.

7.6.4 Dimension Reduction — Why Eigenvalues Matter

Eigenvalues measure importance. A large $λ_{i}$ means $A$ stretches heavily along $v_{i}$ . That direction carries most of the transformation's energy. A small $λ_{i}$ means barely any stretch. That direction barely matters.

Now think of data, not transformations. Your data matrix has samples as rows and features as columns — age, salary, account balance. Hundreds of features. Many are correlated. Age and experience move together. You do not need all of them.

Compute the data's covariance matrix. Find its eigenvectors. Each eigenvector is a new feature — a weighted combination of the originals. Its eigenvalue measures variance (spread) along that direction. Large eigenvalue = data varies heavily there. Small eigenvalue = data is nearly flat there.

Project onto the top few eigenvectors — those with the largest eigenvalues. You keep almost all the variance. You discard directions where the data barely moves. Result: 100 features become maybe 10. Faster models. Less noise. Minimal information loss.

This is the core of Principal Component Analysis (PCA). More on PCA in a later lecture.

7.6.5 Assumptions and Scope

Scope: Eigen decomposition applies only to square

n \times n

matrices. Rectangular matrices require SVD.

Not all square matrices are diagonalizable. A defective matrix has fewer than $n$ linearly independent eigenvectors. Then $P$ is not invertible and $A = P D P^{- 1}$ fails. Example: $[1011]$ has $λ = 1$ (a double eigenvalue) but only one eigenvector direction. It cannot be diagonalized.

For diagonalizable matrices, the decomposition is unique up to scaling of eigenvectors and ordering of eigenpairs. Reorder the columns of $P$ and you reorder the diagonal entries of $D$ the same way.

7.6.6 Visual Intuition — The 3D Cube

Picture a unit cube of vectors floating in 3D space. Apply $A$ and watch what happens — not all at once, but through the $P^{- 1} \to D \to P$ pipeline.

The cube first shears (tilts) under $P^{- 1}$ . Its volume stays constant — shear preserves volume. Then it stretches under $D$ along the principal axes, elongating or squashing. The volume changes here, and the change equals $det (A) = λ_{1} λ_{2} λ_{3}$ , the product of all eigenvalues. Finally the cube shears back under $P$ , tilting to its final orientation. The three-stage decomposition makes visible what the single matrix $A$ hides: the pure-stretch core sandwiched between two basis changes.

Common pitfalls:

Forgetting to normalize eigenvectors. Raw solutions from $(A - λ I) v = 0$ are not unit vectors. Always divide by the vector norm.
Sign errors in the characteristic polynomial. Double-check $(A - λ I)$ , not $(A + λ I)$ .
Mixing up eigenvalue–eigenvector ordering. $λ_{1}$ must pair with $v_{1}$ in column 1 of $P$ , not column 3. Match them column-wise.
Computing $P^{- 1}$ explicitly when $A$ is symmetric. Use $P^{⊤}$ instead. Saves time and avoids numerical error.
Confusing eigen decomposition (square only) with SVD (any shape). They are different — learn both.

7.6.7 Student Questions

Q: Is this called modal decomposition as well? I saw the term somewhere. A: No. Modal decomposition is a distinct technique with a different mathematical framework. Eigen decomposition and spectral decomposition (its symmetric special case) are separate from modal decomposition. Do not use the terms interchangeably. Q: If SVD works on any matrix, why study eigen decomposition at all? A: Eigen decomposition is the foundation. Historically, mathematicians discovered eigen decomposition first. It only works for square matrices. Then the question arose: how to decompose a rectangular matrix? The answer — convert it to square form via

A^{⊤} A

A A^{⊤}

, then apply eigen decomposition. That is exactly how SVD is built. Understand eigen decomposition and SVD becomes transparent rather than a black box.

7.6.8 Exam Guidance and Recap

Exam note: Eigen decomposition is standard exam material. Expect a full 2×2 or 3×3 pipeline. Start with the characteristic equation

det (A - λ I) = 0

. Solve for eigenvalues. Plug each into

(A - λ I) v = 0

. Solve for eigenvectors. Normalize. Assemble

P

and

D

. For symmetric matrices, use

P^{⊤}

instead of manually computing

P^{- 1}

. Spectral decomposition is the same process — not a separate exam topic.

Real-world applications span PCA (dimensionality reduction — keeping top eigenvectors), image compression (discarding small-eigenvalue SVD components), and vibration analysis in mechanical engineering. There, natural frequencies are eigenvalues and mode shapes are eigenvectors. Google's original PageRank uses the dominant eigenvector of the web graph. Quantum mechanics treats measurement outcomes as eigenvalues of observables.

The idea is always the same: find the directions that matter, rank them by importance, and discard or downweight the rest.

Recap: Eigen decomposition writes

A = P D P^{- 1}

. Eigenvectors

v_{i}

are pure-stretch directions. Eigenvalues

λ_{i}

are the stretch amounts. The shear→stretch→shear-back pipeline is the geometric interpretation. Symmetric matrices simplify to

P D P^{⊤}

(spectral decomposition). Eigenvalue-based dimension reduction leads to PCA. Next: Eigen decomposition is square-only. What about rectangular matrices? That is Singular Value Decomposition (SVD) — the generalization to any matrix shape, built directly on eigen decomposition principles.

7.7 Singular Value Decomposition (SVD)

7.7.1 The Rectangular Reality

Eigen decomposition needs a square matrix. But look around — most data is rectangular. A dataset with 1000 users and 10 features is

1000 \times 10

. An HD image is

1920 \times 1080

. Neither is square. What if your matrix is a rectangle?

Think of a rectangular photograph. You can still rotate it — stretch it — and rotate it back. The shape does not matter. SVD does exactly this: it decomposes any $m \times n$ matrix into two rotations and one stretch. This holds no matter how tall or wide the matrix is.

7.7.2 Formal Definition

Singular Value Decomposition: For any

m \times n

matrix

A

A = U Σ V^{⊤}

$U$ — $m \times m$ orthogonal matrix. Columns are left singular vectors. Rotation step one.
$Σ$ — $m \times n$ diagonal matrix. Entries $σ_{1} \geq σ_{2} \geq \dots \geq σ_{m i n (m, n)} \geq 0$ are the singular values. Always nonnegative, sorted largest to smallest. Stretch step.
$V^{⊤}$ — $n \times n$ orthogonal matrix, transposed. Rows are right singular vectors. Rotation step two.

Geometric pipeline: rotate (

V^{⊤}

) → stretch (

Σ

) → rotate (

U

7.7.3 Connection to Eigen Decomposition

SVD is eigen decomposition cleverly repurposed. Start with a rectangular $A$ . Square it up:

A^{⊤} A and A A^{⊤}

Both are square. Both are symmetric. Apply eigen decomposition. The eigenvectors of $A^{⊤} A$ become the right singular vectors $V$ . The eigenvectors of $A A^{⊤}$ become the left singular vectors $U$ . The singular values are square roots:

σ_{i} = λ_{i} (A^{⊤} A) = λ_{i} (A A^{⊤})

$A^{⊤} A$ and $A A^{⊤}$ share the same nonzero eigenvalues. SVD takes a rectangle, makes it square, runs eigen decomposition, and takes square roots. That is why eigen comes first — SVD stands on its shoulders.

7.7.4 Dimension Reduction with SVD

The singular values in $Σ$ are your compression dials. The largest ones capture dominant structure. The smallest ones carry noise.

Keep the top $k$ singular values. Zero out the rest. Multiply back: $A_{k} = U_{k} Σ_{k} V_{k}^{⊤}$ . The result is a rank- $k$ approximation of $A$ . It is the best possible rank- $k$ approximation — minimal Frobenius norm error, guaranteed by the Eckart–Young theorem. This one idea powers image compression, PCA, LoRA, and recommender systems.

7.7.5 Assumptions & Scope

Scope: SVD works on every matrix —

m \times n

, rectangular, tall, wide, sparse, dense. No symmetry required. No squareness required. No invertibility required. The SVD always exists for any real or complex matrix.

Singular values are always nonnegative: $σ_{i} \geq 0$ . For real matrices, $U$ and $V$ are real orthogonal matrices.

7.7.6 Visual Intuition

Imagine a 3D cloud of data points — a shapeless cluster. Apply $V^{⊤}$ : the cloud rotates in place. All relative distances stay fixed. Then $Σ$ : the cloud stretches along each coordinate axis. $σ_{1}$ pulls hard. $σ_{3}$ barely moves. The cloud flattens toward the dominant directions. Finally, $U$ rotates the flattened cloud to its final orientation.

The singular values tell you how much each axis stretches. If $σ_{1} = 5$ and $σ_{3} = 0.1$ , the first axis carries 50× more energy than the third. Discard the small axes and the cloud projects onto a lower-dimensional subspace — with almost nothing lost.

7.7.7 Common Pitfalls

Pitfalls to avoid:

Confusing singular values with eigenvalues. Unless $A$ is symmetric positive semidefinite, singular values and eigenvalues are different numbers. Singular values are $λ (A^{⊤} A)$ , not $λ (A)$ .
Forgetting the transpose on $V$ . The factorization is $U Σ V^{⊤}$ , not $U Σ V$ . The superscript matters. Multiplying $U Σ V$ gives a wrong result.
Using SVD on small square matrices. If $A$ is $3 \times 3$ and symmetric, eigen decomposition is simpler and faster. SVD adds unnecessary steps.
Truncating too aggressively. Dropping too many singular values discards real structure. Always check the singular value spectrum first — look for a gap.

7.7.8 Real-World Applications

SVD is everywhere once you look.

Image compression. A $1920 \times 1080$ image is just a matrix. Keep 50 singular values instead of 1080. Reconstruct. The image is nearly identical; the storage cost drops by orders of magnitude.

LoRA — Low-Rank Adaptation. Fine-tuning an LLM modifies a weight matrix $W$ . Instead of retraining every entry, LoRA approximates the update $Δ W$ as a product of two skinny matrices. These are $A \cdot B$ where $A \in R^{d \times r}$ and $B \in R^{r \times d}$ with $r ≪ d$ . This low-rank decomposition is directly inspired by SVD.

Recommender systems. The user–item rating matrix is huge (millions × thousands) and mostly empty. SVD collapses it into latent factors — hidden taste dimensions — that explain ratings with far fewer numbers.

PCA. Center your data. Compute its SVD. The right singular vectors are the principal components. PCA and SVD are the same algorithm under the hood.

7.7.9 Student Q&A

Q: If SVD works on any matrix and fixes the square-matrix limitation, why spend so much time on eigen decomposition? A: SVD runs on eigen decomposition. The matrices

A^{⊤} A

and

A A^{⊤}

are square — you apply eigen decomposition to them to get the singular vectors and values. Eigen is the engine. SVD is the vehicle built around it. Q: The geometric intuition makes sense, but we need practice with exam-style numerical problems to feel ready. Are problem sets coming? A: Topic-wise practice questions are being prepared. They will follow the lecture sequence so you can match problems to sections. For now, focus on internalizing the factorization and the rotation–stretch–rotation pipeline — the numerical steps become mechanical once that foundation is solid.

7.7.10 Exam Guidance & Lecture Recap

Exam note: Professor's prediction — high chance of an SVD question on the mid-semester. The past two semesters tested eigenvectors. The rotation suggests SVD is due. Know

A = U Σ V^{⊤}

cold. Know what each piece does geometrically:

V^{⊤}

rotates,

Σ

stretches,

U

rotates. Know the eigen connection:

σ_{i} = λ_{i} (A^{⊤} A)

. Lecture recap: We began with eigenvalues and eigenvectors (7.1–7.6) as the foundation — rotation and stretch for square matrices. Then we generalized to SVD (7.7) — the same geometric insight, now applied to every matrix through a clever square-then-decompose trick. The next lecture covers practical SVD applications with hands-on examples: image compression, dimension reduction, and PCA.

Exam Guidance Summary

Exam note: 3×3 Determinants by Cofactor Expansion (Topic 7.1) Know the 3×3 determinant via cofactor expansion along any row or column. The checkerboard sign pattern

(+, -, +, \dots)

is a common error source — mistakes happen when signs on cofactors are flipped. Always write out the sign grid explicitly before expanding:

+ - + - + - + - +

. Exam note: Row Space and Column Space Terminology (Topic 7.2) Terminology questions on row and column spaces are likely. Row space = span of the rows (subspace of

R^{n}

), column space = span of the columns (subspace of

R^{m}

), and the null space is always perpendicular to the row space. Be able to identify each from a given matrix. Exam note: Row, Column, and Null Space Definitions (Topic 7.3) Expect terminology questions covering row space, column space, and null space definitions. Key formula: the rank-nullity theorem —

rank (A) + nullity (A) = n

(the number of columns). Know what rank and nullity mean for different matrix types (full-rank, rank-deficient, wide vs. tall matrices). Exam note: Cholesky Decomposition (Topic 7.5) Cholesky decomposition is very rare in exams. The main takeaway is the determinant shortcut: for a positive definite matrix factorized as

A = L L^{T}

, the determinant is

det (A) = (\prod ℓ_{ii})^{2}

. Do not invest heavy revision time here. Exam note: Eigen Decomposition (Topic 7.6) Eigen decomposition is standard exam material. Expect a full 2×2 or 3×3 pipeline: characteristic equation

det (A - λ I) = 0

, solve for eigenvalues, plug each into

(A - λ I) v = 0

, normalize, assemble

P

and

D

. For symmetric matrices use

P^{⊤}

instead of computing

P^{- 1}

. Exam note: Singular Value Decomposition (Topic 7.7) High chance of an SVD question on the mid-semester. Know

A = U Σ V^{⊤}

cold. Know what each piece does geometrically:

V^{⊤}

rotates,

Σ

stretches,

U

rotates. Know the eigen connection:

σ_{i} = λ_{i} (A^{⊤} A)

Key Industry Applications

Image Compression (SVD-based)

The SVD factorizes an image (treated as a matrix of pixel intensities) into $U Σ V^{T}$ . By discarding smaller singular values — which capture only fine-grained detail — and retaining only the top $k$ singular values, the image can be reconstructed with a drastically reduced storage footprint. This principle underpins JPEG compression pipelines. It is also used in WhatsApp's image resizing to achieve near-lossless quality at a fraction of the original file size.

Low-Rank Adaptation (LoRA) for LLMs

When fine-tuning large language models like GPT or Gemini, updating the full weight matrix is prohibitively expensive. LoRA decomposes the weight update $Δ W$ into a low-rank product $B A^{T}$ where $B$ and $A$ are much smaller matrices. This is directly inspired by the SVD's ability to approximate a matrix with a low-rank factorization. It reduces trainable parameters by several orders of magnitude without sacrificing downstream task performance.

Recommender Systems (Netflix, Amazon, Spotify)

User–item interaction matrices are enormous and sparse: rows are millions of users, columns are millions of items, and most entries are empty. SVD factorizes this matrix into latent user-feature and item-feature vectors, discovering hidden patterns. For example, it groups users who like similar genres without explicitly knowing the genre labels. This latent factor approach powered the Netflix Prize-winning algorithm. It remains the backbone of modern recommendation engines.

Principal Component Analysis (PCA)

PCA reduces the dimensionality of high-dimensional datasets by projecting data onto the directions of maximum variance. These directions are the eigenvectors of the data covariance matrix, computed via eigen decomposition or equivalently via SVD of the centered data matrix. The resulting principal components form a new coordinate system where the first few axes capture most of the information. This enables visualization, noise reduction, and more efficient model training across all of machine learning.

MFML Lecture 07 notes · Matrix Decompositions, Vector Spaces, and Determinants

Mathematical Foundations for Machine Learning· postgraduate· 2026-07-09

Sections Breakdown

1Determinants via Minors and Cofactors

Compute determinants by cofactor expansion along any row or column using minors and the checkerboard sign pattern.

2Row Space and Column Space

Define row space and column space, and show they always share the same dimension — the rank.

3Null Space and the Rank Nullity Theorem

Define the null space (kernel) and prove rank plus nullity equals the number of columns.

4Matrix Composition and Decomposition — The Big Picture

Explain that matrix multiplication is right-to-left and that decomposition reverse-engineers a transformation.

5Cholesky Decomposition

Factor a symmetric positive definite matrix as A = LL^T and use the determinant shortcut.

6Eigen Decomposition (Diagonalization)

Factor a square matrix as A = PDP^{-1}; eigenvectors are pure-stretch directions, eigenvalues are stretch amounts.

7Singular Value Decomposition (SVD)

Factor any rectangular matrix as A = U Sigma V^T and connect it to eigen decomposition.

Postgraduate students in Mathematical Foundations for Machine Learning

Exam Revision Notes

Below is the distilled, exam-ready core of this lecture. Every entry is built from the full textbook notes above. Use this section for rapid review — but if something doesn't make sense, go back to the full explanation in the main content.

Determinants via Minors and Cofactors

Must-know: The determinant of a square matrix is computed by cofactor expansion along any row or column. The checkerboard sign pattern $(+, -, +, \dots)$ is the main exam error source — always write it out before expanding.

$det (A) = j = 1 \sum n a_{ij} (- 1)^{i + j} M_{ij} (expansion along row i)$

⚠️ Top pitfall: Forgetting the checkerboard sign $(- 1)^{i + j}$ when attaching the cofactor — a sign flip silently breaks the whole calculation.

Self-check: Expand a given 3×3 matrix along two different rows. Do both give the same determinant? If not, where is the sign error?

Connects to: Row space and column space, Eigen decomposition, Cholesky determinant shortcut.

Row Space and Column Space

Must-know: The row space (span of rows, lives in $R^{n}$ ) and the column space (span of columns, lives in $R^{m}$ ) always have the same dimension — the rank. This is a theorem, not a definition.

$dim (row (A)) = dim (col (A)) = rank (A)$

⚠️ Top pitfall: Swapping where each space lives — the row space is in $R^{n}$ (because each row has $n$ entries), not $R^{m}$ . Count entries per vector, not the number of vectors.

Self-check: A 2×2 matrix has dependent rows. What is its rank, and what does that imply about its column space?

Connects to: Null space and rank nullity, Determinants, Multicollinearity in regression.

Null Space and the Rank Nullity Theorem

Must-know: The null space is the set of vectors $A$ maps to zero. The rank-nullity theorem partitions the input dimension: rank (preserved directions) plus nullity (collapsed directions) equals $n$ , the number of columns.

$rank (A) + dim (ker (A)) = n$

⚠️ Top pitfall: Using $m$ (rows) instead of $n$ (columns) in the theorem. The sum always equals the input dimension $n$ , never the output dimension.

Self-check: A 4×4 matrix has rank 1. What is the dimension of its null space?

Connects to: Row space and column space, Eigen decomposition, PCA.

Matrix Composition and Decomposition

Must-know: Matrix multiplication reads right-to-left: in $A B$ , $B$ acts first, then $A$ . Decomposition reverse-engineers a complex transformation into elementary pieces (stretch, shear, rotate).

$C = A B means: apply B to your vectors, then apply A$

⚠️ Top pitfall: Reading $A B$ as "first $A$ , then $B$ ". Order changes everything for transformations — this is the single most common intuition error.

Self-check: For two 2×2 matrices, is $A B$ generally equal to $B A$ ? Why does order matter geometrically?

Connects to: Cholesky decomposition, Eigen decomposition, Singular Value Decomposition.

Cholesky Decomposition

Must-know: A symmetric positive definite matrix factors uniquely as $A = L L^{T}$ with $L$ lower triangular. The determinant becomes the square of the product of $L$ 's diagonal entries — dropping cofactor expansion from $O (n!)$ to $O (n)$ .

$det (A) = (i = 1 \prod n ℓ_{ii})^{2}$

⚠️ Top pitfall: Applying Cholesky to a non-symmetric or non-positive-definite matrix — you hit a negative radicand and the real square root fails. Always verify SPD first.

Self-check: Given a 2×2 Cholesky factor $L$ , how do you recover $det (A)$ without expanding the full matrix?

Connects to: Determinants, Eigen decomposition, Positive definite matrices.

Eigen Decomposition (Diagonalization)

Must-know: A diagonalizable square matrix factors as $A = P D P^{- 1}$ . Eigenvectors are the pure-stretch directions; eigenvalues are the stretch amounts. For symmetric matrices, $P^{- 1} = P^{o} p$ (spectral decomposition).

$A = P D P^{- 1}, with A v = λ v$

⚠️ Top pitfall: Forgetting to normalize eigenvectors, or mixing up eigenvalue–eigenvector pairing order. $λ_{1}$ must sit in column 1 of $P$ , paired with $v_{1}$ .

Self-check: For a symmetric matrix, what replaces $P^{- 1}$ in the decomposition, and why?

Connects to: Singular Value Decomposition, Determinants, PCA, Rank nullity.

Singular Value Decomposition (SVD)

Must-know: Any $mim es n$ matrix factors as $A = U Σ V^{o} p$ — two rotations and one stretch. Singular values are square roots of the eigenvalues of $A^{o} p A$ (or $A A^{o} p$ ). SVD is the universal tool; eigen decomposition is its engine.

$A = U Σ V^{⊤}, σ_{i} = λ_{i} (A^{⊤} A)$

⚠️ Top pitfall: Forgetting the transpose on $V$ (writing $U Σ V$ instead of $U Σ V^{o} p$ ), or confusing singular values with eigenvalues when $A$ is not symmetric positive semidefinite.

Self-check: Why does SVD work on a rectangular matrix when eigen decomposition does not?

Connects to: Eigen decomposition, PCA, Image compression, Low-rank approximation (LoRA).

Previous LectureLecture 06 · Eigenvalues, Eigenvectors, and Determinants

Next LectureLecture 08 · Singular Value Decomposition and Vector Calculus

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.