Linear Algebra for ML · AI Engineering

Vectors, transforms, eigenvalues, SVD and Ax = b solvers. From-scratch Python and NumPy from the lessons.

SVD: rotate, scale, rotate

Nodes and connections

Node	Role	Kind
Input space	n-dim
V^T	rotate
Sigma	scale by sigma_i
U	rotate
A^T A	eigenvectors are V
A A^T	eigenvectors are U
Output space	m-dim

From	To	Connection
Input space	V^T
V^T	Sigma
Sigma	U
U	Output space
A^T A	V^T	V
A A^T	U	U

Sources

phases/01-math-foundations/11-singular-value-decomposition/docs/en.md

Gaussian elimination with partial pivoting

Pivot in column k, find the largest entry at or below row k.
Swap swap that row with row k. A small pivot amplifies rounding errors.
Check a pivot below 1e-12 raises ValueError.
Eliminate for each row i below k, compute m = A[i][k] / A[k][k]. Subtract m times row k.
Back substitute solve the last equation first, then go upward.
Reuse L stores the multipliers. U is the eliminated matrix. PA = LU.

Sources

Tasks in NumPy

Task	Code
Dot product and length	`np.dot(a, b)`, `np.linalg.norm(a)`
Matrix multiply	`A @ B`
Element-wise multiply	`A * B`
Rank	`np.linalg.matrix_rank(A)`
Eigenvalues and eigenvectors	`np.linalg.eig(A)`
Thin SVD	`np.linalg.svd(A, full_matrices=False)`
Least squares	`np.linalg.lstsq(A, b, rcond=None)[0]`
QR, check Q	`np.allclose(Q @ Q.T, np.eye(3))`

Sources

Truncate, compress and invert with SVD

U, S, Vt = np.linalg.svd(A, full_matrices=False)S sorted in decreasing order

A_k = U[:, :k] @ np.diag(S[:k]) @ Vt[:k, :]best rank-k approximation

compressed_size = k * (rows + cols + 1)storage for rank k

A_pinv = Vt.T @ np.diag(1.0 / S) @ U.Tpseudoinverse, nonzero S only

x_svd = A_pinv @ bleast-squares solution

x_pinv = np.linalg.pinv(A) @ bsame result from NumPy

U, S, V = svd_from_scratch(A)power iteration and deflation

A_pinv = pseudoinverse_via_svd(A, tol=1e-10)1/s only for s above tol

Sources

Solve Ax = b from scratch

x = gaussian_elimination(A, b)partial pivoting, O(n^3)

P, L, U = lu_decompose(A)PA = LU, pay O(n^3) one time

x = lu_solve(P, L, U, b)O(n^2) for each new b

L = cholesky(A)A = L L^T, symmetric positive definite only

x = cholesky_solve(L, b)forward, then back substitution

w_ols = least_squares_normal(X, y)solves A^T A x = A^T b

w_ridge = ridge_regression(X, y, lam=1.0)adds lam * np.eye(n)

x, iters = conjugate_gradient(A, b)SPD, at most n iterations

kappa = condition_number(A)S[0] / S[-1], inf if singular

Sources

Transformation matrices

Command	What it does
`rotation_2d(theta)`	[[c, -s], [s, c]]. Keeps distances. det 1
`scaling_2d(sx, sy)`	[[sx, 0], [0, sy]]. det is sx * sy
`shearing_2d(kx, ky)`	[[1, kx], [ky, 1]]. Rectangles become parallelograms
`reflection_y()`	[[-1, 0], [0, 1]]. Flips orientation. det -1
`reflection_x()`	[[1, 0], [0, -1]]. det -1
`mat_mul(S, R)`	Rotate first, then scale. Order matters
`eigenvalues_2x2(matrix)`	Roots of the characteristic equation. Complex if discriminant < 0
`eigenvector_2x2(matrix, eigenvalue)`	Unit eigenvector for one eigenvalue

Sources

Key formulas

Shapes: (m x n) @ (n x p) = (m x p). The inner dimensions must match.
Cosine: \cos\theta = \frac{a \cdot b}{\lvert a\rvert \lvert b\rvert}. 1 is the same direction, 0 is orthogonal.
Projection: \text{proj}_b a = \frac{a \cdot b}{b \cdot b} b. The residual is perpendicular to b.
Eigen: Av = \lambda v. Eigenvalues are roots of \det(A - \lambda I) = 0.
2x2 eigenvalues: \lambda^2 - (a+d)\lambda + (ad - bc) = 0.
SVD: A = U \Sigma V^T and A v_i = \sigma_i u_i. Rank is the count of nonzero \sigma_i.
Normal equations: A^T A x = A^T b. Ridge adds \lambda I to A^T A.
Condition number: \kappa = \sigma_{\max} / \sigma_{\min}.

Sources

Pick a solver

Command	What it does
Gaussian elimination	Square, nonsingular A. O(n^3). One solve
LU decomposition	Many solves with the same A. O(n^2) for each solve
QR decomposition	Least squares with m >= n. Numerically stable
Cholesky	Symmetric positive definite A. Twice as fast as LU
Normal equations	Overdetermined, small n. Linear regression
SVD / pseudoinverse	Rank-deficient A. Minimum-norm solution
Conjugate gradient	Large sparse SPD A. Iterative

Sources

phases/01-math-foundations/17-linear-systems/docs/en.md

Numbers and defaults

Setting	Default	Note
Zero test in `rank()`	1e-10	Smaller entries count as zero
Pivot test in elimination	1e-12	Smaller pivot raises ValueError
`power_iteration` `num_iters`	200	Stops early at `tol=1e-10`
`conjugate_gradient` `tol`	1e-10	`max_iter` defaults to n
Safe condition number	< 100	The solution is accurate
Meaningless for float64	10^{16}	The matrix is effectively singular
Image at rank k=50	14.6%	Of the 800 x 600 values
LoRA rank	16	131K parameters, not 16M

Sources

Troubleshooting

Symptom	Cause	Fix
Shape mismatch error	Inner dimensions differ	Write each shape before you multiply
`inverse_2x2` raises ValueError	Determinant is 0	Use the pseudoinverse
"Matrix is not positive definite"	A is not SPD	Add lambda I, or use LU
Weights swing on small input changes	Collinear features, rank deficient	Drop features or add regularization
Answer loses digits	kappa near 10^k loses k digits	Regularize, or use QR or SVD
`np.linalg.eig(A.T @ A)` is imprecise	It squares the condition number	Use `np.linalg.svd(A)`
Composition gives the wrong point	B @ A applies A first	Multiply in reverse order of application
Gram-Schmidt dots are not exactly 0	Floating point	Compare with a tolerance such as 1e-9

Sources

Questions

Why factor with LU?: The O(n^3) cost is paid one time. Each new b costs O(n^2).
When does Cholesky work?: A is symmetric positive definite. X^T X + \lambda I is SPD for \lambda > 0.
What does the determinant tell you?: The area scale. 0 crushes a dimension. -1 flips orientation.
Why is truncated SVD the best rank k?: Eckart-Young. The spectral error is \sigma_{k+1}.
What do eigenvalues say about stability?: Magnitude above 1 explodes. Below 1 vanishes.

Sources

Tips

PCA is SVD on centered data. The components are the right singular vectors V.
Explained variance for each component is sigma_i^2 / (n-1).
Look for a clear gap in the singular values. Keep the values above it to denoise.
Ridge improves the condition number to (\sigma_{\max} + \lambda) / (\sigma_{\min} + \lambda).
The pseudoinverse gives the solution with the smallest norm when many solutions exist.
Orthogonal initialization uses QR to make orthonormal weight columns.

Sources

Original source

---
id: linear-algebra
title: Linear Algebra for ML
code: LA
subtitle: Vectors, transforms, eigenvalues, SVD and Ax = b solvers. From-scratch Python and NumPy from the lessons.
hue: 230
sources: phases/01-math-foundations/01-linear-algebra-intuition, phases/01-math-foundations/02-vectors-matrices-operations, phases/01-math-foundations/03-matrix-transformations, phases/01-math-foundations/11-singular-value-decomposition, phases/01-math-foundations/17-linear-systems
source_hash: d0fc32de779910f0
---

## SVD: rotate, scale, rotate
type: architecture
from: phases/01-math-foundations/11-singular-value-decomposition/docs/en.md

```arch
node | x | 1,1 | Input space | n-dim
node | vt | 2,1 | V^T | rotate
node | sig | 3,1 | Sigma | scale by sigma_i
node | u | 4,1 | U | rotate
node | ata | 2,2 | A^T A | eigenvectors are V
node | aat | 3,2 | A A^T | eigenvectors are U
node | y | 4,2 | Output space | m-dim
edge | x | vt |
edge | vt | sig |
edge | sig | u |
edge | u | y |
edge | ata | vt | V
edge | aat | u | U
```

## Gaussian elimination with partial pivoting
type: flow
from: phases/01-math-foundations/17-linear-systems/docs/en.md, phases/01-math-foundations/17-linear-systems/code/linear_systems.py

1. **Pivot**: in column k, find the largest entry at or below row k.
2. **Swap**: swap that row with row k. A small pivot amplifies rounding errors.
3. **Check**: a pivot below `1e-12` raises `ValueError`.
4. **Eliminate**: for each row i below k, compute m = A[i][k] / A[k][k]. Subtract m times row k.
5. **Back substitute**: solve the last equation first, then go upward.
6. **Reuse**: L stores the multipliers. U is the eliminated matrix. PA = LU.

## Tasks in NumPy
type: task-table
from: phases/01-math-foundations/01-linear-algebra-intuition/docs/en.md, phases/01-math-foundations/02-vectors-matrices-operations/docs/en.md, phases/01-math-foundations/03-matrix-transformations/docs/en.md, phases/01-math-foundations/11-singular-value-decomposition/docs/en.md, phases/01-math-foundations/17-linear-systems/docs/en.md

| Task | Code |
|---|---|
| Dot product and length | `np.dot(a, b)`, `np.linalg.norm(a)` |
| Matrix multiply | `A @ B` |
| Element-wise multiply | `A * B` |
| Rank | `np.linalg.matrix_rank(A)` |
| Eigenvalues and eigenvectors | `np.linalg.eig(A)` |
| Thin SVD | `np.linalg.svd(A, full_matrices=False)` |
| Least squares | `np.linalg.lstsq(A, b, rcond=None)[0]` |
| QR, check Q | `np.allclose(Q @ Q.T, np.eye(3))` |

## Truncate, compress and invert with SVD
type: annotated-code
lang: python
from: phases/01-math-foundations/11-singular-value-decomposition/docs/en.md, phases/01-math-foundations/11-singular-value-decomposition/code/svd.py

```python
U, S, Vt = np.linalg.svd(A, full_matrices=False)  # S sorted in decreasing order
A_k = U[:, :k] @ np.diag(S[:k]) @ Vt[:k, :]  # best rank-k approximation
compressed_size = k * (rows + cols + 1)  # storage for rank k
A_pinv = Vt.T @ np.diag(1.0 / S) @ U.T  # pseudoinverse, nonzero S only
x_svd = A_pinv @ b  # least-squares solution
x_pinv = np.linalg.pinv(A) @ b  # same result from NumPy
U, S, V = svd_from_scratch(A)  # power iteration and deflation
A_pinv = pseudoinverse_via_svd(A, tol=1e-10)  # 1/s only for s above tol
```

## Solve Ax = b from scratch
type: annotated-code
lang: python
from: phases/01-math-foundations/17-linear-systems/docs/en.md, phases/01-math-foundations/17-linear-systems/code/linear_systems.py

```python
x = gaussian_elimination(A, b)  # partial pivoting, O(n^3)
P, L, U = lu_decompose(A)  # PA = LU, pay O(n^3) one time
x = lu_solve(P, L, U, b)  # O(n^2) for each new b
L = cholesky(A)  # A = L L^T, symmetric positive definite only
x = cholesky_solve(L, b)  # forward, then back substitution
w_ols = least_squares_normal(X, y)  # solves A^T A x = A^T b
w_ridge = ridge_regression(X, y, lam=1.0)  # adds lam * np.eye(n)
x, iters = conjugate_gradient(A, b)  # SPD, at most n iterations
kappa = condition_number(A)  # S[0] / S[-1], inf if singular
```

## Transformation matrices
type: command-table
from: phases/01-math-foundations/03-matrix-transformations/docs/en.md, phases/01-math-foundations/03-matrix-transformations/code/transformations.py

| Command | What it does |
|---|---|
| `rotation_2d(theta)` | [[c, -s], [s, c]]. Keeps distances. det 1 |
| `scaling_2d(sx, sy)` | [[sx, 0], [0, sy]]. det is sx * sy |
| `shearing_2d(kx, ky)` | [[1, kx], [ky, 1]]. Rectangles become parallelograms |
| `reflection_y()` | [[-1, 0], [0, 1]]. Flips orientation. det -1 |
| `reflection_x()` | [[1, 0], [0, -1]]. det -1 |
| `mat_mul(S, R)` | Rotate first, then scale. Order matters |
| `eigenvalues_2x2(matrix)` | Roots of the characteristic equation. Complex if discriminant < 0 |
| `eigenvector_2x2(matrix, eigenvalue)` | Unit eigenvector for one eigenvalue |

## Key formulas
type: concepts
from: phases/01-math-foundations/01-linear-algebra-intuition/docs/en.md, phases/01-math-foundations/02-vectors-matrices-operations/docs/en.md, phases/01-math-foundations/03-matrix-transformations/docs/en.md, phases/01-math-foundations/11-singular-value-decomposition/docs/en.md, phases/01-math-foundations/17-linear-systems/docs/en.md

- **Shapes**: (m x n) @ (n x p) = (m x p). The inner dimensions must match.
- **Cosine**: $\cos\theta = \frac{a \cdot b}{\lvert a\rvert \lvert b\rvert}$. 1 is the same direction, 0 is orthogonal.
- **Projection**: $\text{proj}_b a = \frac{a \cdot b}{b \cdot b} b$. The residual is perpendicular to $b$.
- **Eigen**: $Av = \lambda v$. Eigenvalues are roots of $\det(A - \lambda I) = 0$.
- **2x2 eigenvalues**: $\lambda^2 - (a+d)\lambda + (ad - bc) = 0$.
- **SVD**: $A = U \Sigma V^T$ and $A v_i = \sigma_i u_i$. Rank is the count of nonzero $\sigma_i$.
- **Normal equations**: $A^T A x = A^T b$. Ridge adds $\lambda I$ to $A^T A$.
- **Condition number**: $\kappa = \sigma_{\max} / \sigma_{\min}$.

## Pick a solver
type: command-table
from: phases/01-math-foundations/17-linear-systems/docs/en.md

| Command | What it does |
|---|---|
| Gaussian elimination | Square, nonsingular A. O(n^3). One solve |
| LU decomposition | Many solves with the same A. O(n^2) for each solve |
| QR decomposition | Least squares with m >= n. Numerically stable |
| Cholesky | Symmetric positive definite A. Twice as fast as LU |
| Normal equations | Overdetermined, small n. Linear regression |
| SVD / pseudoinverse | Rank-deficient A. Minimum-norm solution |
| Conjugate gradient | Large sparse SPD A. Iterative |

## Numbers and defaults
type: defaults
from: phases/01-math-foundations/01-linear-algebra-intuition/docs/en.md, phases/01-math-foundations/01-linear-algebra-intuition/code/vectors.py, phases/01-math-foundations/11-singular-value-decomposition/docs/en.md, phases/01-math-foundations/11-singular-value-decomposition/code/svd.py, phases/01-math-foundations/17-linear-systems/docs/en.md, phases/01-math-foundations/17-linear-systems/code/linear_systems.py

| Setting | Default | Note |
|---|---|---|
| Zero test in `rank()` | 1e-10 | Smaller entries count as zero |
| Pivot test in elimination | 1e-12 | Smaller pivot raises ValueError |
| `power_iteration` `num_iters` | 200 | Stops early at `tol=1e-10` |
| `conjugate_gradient` `tol` | 1e-10 | `max_iter` defaults to n |
| Safe condition number | < 100 | The solution is accurate |
| Meaningless for float64 | 10^{16} | The matrix is effectively singular |
| Image at rank k=50 | 14.6% | Of the 800 x 600 values |
| LoRA rank | 16 | 131K parameters, not 16M |

## Troubleshooting
type: troubleshooting
from: phases/01-math-foundations/01-linear-algebra-intuition/docs/en.md, phases/01-math-foundations/02-vectors-matrices-operations/docs/en.md, phases/01-math-foundations/03-matrix-transformations/docs/en.md, phases/01-math-foundations/11-singular-value-decomposition/docs/en.md, phases/01-math-foundations/17-linear-systems/docs/en.md

| Symptom | Cause | Fix |
|---|---|---|
| Shape mismatch error | Inner dimensions differ | Write each shape before you multiply |
| `inverse_2x2` raises ValueError | Determinant is 0 | Use the pseudoinverse |
| "Matrix is not positive definite" | A is not SPD | Add lambda I, or use LU |
| Weights swing on small input changes | Collinear features, rank deficient | Drop features or add regularization |
| Answer loses digits | kappa near 10^k loses k digits | Regularize, or use QR or SVD |
| `np.linalg.eig(A.T @ A)` is imprecise | It squares the condition number | Use `np.linalg.svd(A)` |
| Composition gives the wrong point | B @ A applies A first | Multiply in reverse order of application |
| Gram-Schmidt dots are not exactly 0 | Floating point | Compare with a tolerance such as 1e-9 |

## Questions
type: qa
from: phases/01-math-foundations/03-matrix-transformations/docs/en.md, phases/01-math-foundations/11-singular-value-decomposition/docs/en.md, phases/01-math-foundations/17-linear-systems/docs/en.md

- **Why factor with LU?** The O(n^3) cost is paid one time. Each new b costs O(n^2).
- **When does Cholesky work?** A is symmetric positive definite. $X^T X + \lambda I$ is SPD for $\lambda > 0$.
- **What does the determinant tell you?** The area scale. 0 crushes a dimension. -1 flips orientation.
- **Why is truncated SVD the best rank k?** Eckart-Young. The spectral error is $\sigma_{k+1}$.
- **What do eigenvalues say about stability?** Magnitude above 1 explodes. Below 1 vanishes.

## Tips
type: tips
from: phases/01-math-foundations/01-linear-algebra-intuition/docs/en.md, phases/01-math-foundations/11-singular-value-decomposition/docs/en.md, phases/01-math-foundations/17-linear-systems/docs/en.md

- PCA is SVD on centered data. The components are the right singular vectors V.
- Explained variance for each component is sigma_i^2 / (n-1).
- Look for a clear gap in the singular values. Keep the values above it to denoise.
- Ridge improves the condition number to $(\sigma_{\max} + \lambda) / (\sigma_{\min} + \lambda)$.
- The pseudoinverse gives the solution with the smallest norm when many solutions exist.
- Orthogonal initialization uses QR to make orthonormal weight columns.