Linear Algebra

Every embedding is a vector, every layer is a matrix, every attention score is a dot product; the destination is that attention is two matmuls with a softmax between them.

Vectors, norms, cosine

• Vector: ordered list of numbers, an arrow in R^n. Norm: length; must be zero only at 0, scale as ||cx|| = |c|·||x||, obey triangle inequality.
• Norms of x=(3,-4,0,12): L0=3 (nonzero count, not a real norm, target of sparsity), L1=19 (taxicab), L2=13 (Euclidean), Linf=12 (worst coord).
• Ordering, every vector: Linf <= L2 <= L1 <= sqrt(p)·L2. Last step is Cauchy-Schwarz |a·b| <= ||a||·||b||. L1/L2 gap grows with spread, the root of sparsity.
• Dot product a·b = sum_i a_i·b_i = ||a||·||b||·cos(theta). Zero = orthogonal. Cosine similarity = (a·b)/(||a||·||b||) in [-1,1]; discards magnitude, keeps direction (undefined for the zero vector).
• On unit vectors ||a-b||^2 = 2 - 2·(a·b), so cosine, inner product, and Euclidean rank identically. Vector DBs normalize at write time, use raw inner product (cheapest).
• Pooling dilution: swap 1 token in 200 near-orthonormal vectors moves cosine by only 0.005; why dense search misses a rare literal and BM25 (weights rarity) complements it.

Matrices as linear maps

• m × n matrix = linear map R^n -> R^m: A(x+y)=Ax+Ay, A(cx)=c·Ax. Columns are the images of the basis vectors: A·e_i = column i.
• Matmul = composition: A·B means “B first, then A.” Non-commutative because composition is. (AB)^T = B^T·A^T.
• Orthogonal Q: square with Q^T Q = I; preserves every length and angle (rotations/reflections). ||Qx|| = ||x||.
• Rank = independent directions the output reaches (dim of column space). Null space = inputs sent to 0. Rank-nullity: rank(A) + dim(null(A)) = n.
• Exact rank deficiency = perfect multicollinearity -> X^T X singular, no unique solution (e.g. full one-hot + intercept; drop one level).
• Low rank for data: p columns but only r << p real directions. What PCA, embeddings, recsys, LoRA, distillation all bet on. Diagnostic: how fast singular values decay.

Matmul cost and attention

• Cost of (m×k)(k×n): m·n·k MACs = 2·m·n·k FLOPs (output has m·n entries, each a length-k dot product).
• Attention = two matmuls with a row-wise softmax between: softmax(Q·K^T / sqrt(d_k))·V. A matmul IS a table of dot products, so all n^2 scores are one product Q·K^T. sqrt(d_k) keeps softmax from saturating.
• Associativity: same value, different cost. Without softmax, Q(K^T V) is 4·n·d^2 vs (QK^T)V at 4·n^2·d; ratio n/d (e.g. 64×) = linear attention. Softmax is what you give up.
• Score matrix at n=8192, bf16: 8192^2·2 = 134 MB/head, ×32 = 4.3 GB. The number FlashAttention avoids by tiling.
• Batching: B rows share one weight read. Arithmetic intensity = 2·B·d^2 / 2·d^2 = B FLOPs/byte. Machine balance ~300; B<300 memory-bound, B>300 compute-bound.
• So output > input token cost: prefill (thousands of tokens, compute-bound, fast) vs decode (one token/seq, memory-bound, slow).

Eigenvalues, PCA, SVD

• Eigenvector: A·v = lambda·v, v != 0; direction only stretched, not turned. Found via det(A - lambda·I) = 0. Free checks: trace = sum of eigenvalues, det = product.
• A^k v = lambda^k v, so largest |lambda| dominates repeated application (power iteration, PageRank, vanishing/exploding gradients).
• Spectral theorem: real symmetric -> real eigenvalues + orthonormal eigenbasis, A = Q·D·Q^T. Covariance, Hessian, Gram are all symmetric.
• PCA = maximize w^T C w s.t. ||w||=1; Lagrange gives C·w = lambda·w. Directions of max variance ARE eigenvectors of covariance C = X^T X / n; variance captured equals the eigenvalue. Explained ratio lambda_k / sum lambda_j. Center first, usually standardize.
• SVD: every matrix X = U·S·V^T = rotate, scale (singular values s_1 >= s_2 >= ... >= 0), rotate. The only three things a linear map does.
• SVD to PCA: X^T X = V·S^2·V^T, so PCA eigenvalues = s_i^2/n. Real code runs SVD on X, never forms X^T X (squares the condition number).
• Eckart-Young: truncated rank-k SVD is the optimal rank-k fit, error = sum_{i>k} s_i^2. Rank 50 of 1000 (with s_i ∝ 1/i): 10% storage, 98.9% energy, 10× faster matvec.
• LoRA: learn update dW = B·A of rank r; 2·d·r vs d^2 = 0.78% at d=4096, r=16. A rank claim about the update.

SVD:  x  --V^T-->  rotate  --S-->  SCALE by s_i  --U-->  rotate  -->  Xx
      only S changes anything measurable; rank/conditioning all live in S

Positive definiteness and conditioning

• PD: symmetric M, x^T M x > 0 for all x != 0 <=> all eigenvalues > 0 (bowl opens up everywhere). PSD: >= 0. Covariance is always PSD; a negative eigenvalue in a correlation matrix is a data bug (usually pairwise deletion).
• Hessian classifies critical points: all + = min, all - = max, mixed = saddle. P(all d eigenvalues > 0) = 2^-d, so in deep nets saddles/plateaus stall training, not local minima (momentum escapes along the negative direction).
• Convex <=> Hessian PSD everywhere. Condition number kappa = lambda_max/lambda_min: 1 = circular bowl, large = narrow ravine. GD error shrinks by (kappa-1)/(kappa+1) per step.
• Standardizing fixes scale-induced kappa; only whitening (rotate to PCA basis, divide by sqrt(lambda_i)) fixes correlation-induced kappa.
• Cholesky M = L·L^T exists iff M is PD; the attempt is the test. n^3/3 flops, computes no eigenvalues.

Matrix calculus and backprop

• Shape rule: dL/dW has the shape of W. Turns every backprop formula into shape analysis.
• Key gradients: f=a^T x -> a; f=x^T A x -> (A+A^T)x (= 2Ax if symmetric); f=||Xw-y||^2 -> 2·X^T(Xw-y) (normal equations); softmax+cross-entropy -> dL/dz = p - y (why the last line of every classifier is probs - onehot).
• Linear layer Y = X·W + b, upstream G = dL/dY: dL/dW = X^T·G, dL/dX = G·W^T, dL/db = sum of G over rows. The only contractions with the right shapes.
• Backprop is reverse-mode: one scalar output, millions of inputs. Right-to-left keeps a row vector, L·d^2; left-to-right needs full Jacobians, L·d^3 (~1000× more at d=1024).

Regularization geometry

• L2 is the only p-norm invariant under rotation: ||Qx||_2 = ||x||_2. A rotation-invariant penalty can’t tell the axes apart, so ridge (L2) can never zero a coefficient.
• L1 is not rotation-invariant (L1 of (1,0) grows 41% under a 45° turn), so it privileges the original basis and produces exact zeros. Right when columns are meaningful features.
• Ridge in SVD basis: shrink direction i by s_i^2/(s_i^2 + lambda). Deletes low-variance directions (fixes collinearity), leaves high-variance ones untouched. Effective df = sum_i s_i^2/(s_i^2+lambda). Needs standardized inputs (singular values carry units).