Linear Algebra: Quick recap

00 Linear algebra in plain words

A matrix moves space. Its column $j$ is $Ae_j$ , and $Ax = x_1 a_1 + \dots + x_n a_n$ .
Span = everything reachable by combinations; basis = independent vectors that span; dimension = the size of a basis.
Rank = the number of independent directions that survive; $\operatorname{rank} A + \dim N(A) = n$ .
$u^\top v = \|u\|\,\|v\|\cos\theta$ : positive for acute angles, zero for perpendicular vectors, negative for obtuse angles.
An eigenvector stays on its own line: $Av = \lambda v$ . The eigenvalue $\lambda$ can be negative, zero or complex.
$\det A$ is the signed volume factor; $\det A = 0$ means a direction is lost and $A$ cannot be undone.
Every matrix has an SVD $A = U\Sigma V^\top$ : rotate or reflect, stretch by the singular values, rotate or reflect. Singular values are not eigenvalues in general.
PCA is the SVD of the centered data matrix; a symmetric matrix is positive definite when $x^\top S x > 0$ for all $x \ne 0$ , that is, when all its eigenvalues are positive.

01 Matrices as maps, span and basis

Column $j$ of $A$ is $Ae_j$ . The columns fix the whole linear map: $Ax = x_1 a_1 + \dots + x_n a_n$ .
A $2 \times 2$ matrix can stretch, rotate, shear, reflect or flatten the plane. Parallel columns flatten it.
Span = all combinations. Independent = only the zero combination gives $0$ . Basis = independent and spanning. Dimension = size of any basis.
Test independence with the null space: the columns of $V$ are independent exactly when $Vc = 0$ forces $c = 0$ .
More than $m$ vectors in $\mathbb{R}^m$ are always dependent; every basis of a subspace has the same size.
Four views of $AB$ : entries (dot products), columns ( $Ab_j$ ), rows ( $\alpha_i^\top B$ ), and a sum of rank-1 outer products $\sum_k a_k \beta_k^\top$ .

02 Rank and the four subspaces

The rank of $A$ is $\dim C(A)$ : the number of independent columns, which equals the number of pivots after elimination.
A basis of $C(A)$ is the pivot columns of the original $A$ ; a basis of the row space is the nonzero rows of the echelon form.
$A = CR$ ( $C$ = pivot columns of $A$ , $R$ = nonzero rows of $\operatorname{rref}(A)$ ), so row rank = column rank.
Rank–nullity: $\operatorname{rank}(A) + \dim N(A) = n$ for an $m \times n$ matrix; the special solutions are a basis of $N(A)$ .
The four subspaces: $C(A)$ (dim $r$ ) and $N(A^\top)$ (dim $m - r$ ) in $\mathbb{R}^m$ ; $C(A^\top)$ (dim $r$ ) and $N(A)$ (dim $n - r$ ) in $\mathbb{R}^n$ .
$N(A)$ and $C(A^\top)$ are orthogonal complements in $\mathbb{R}^n$ ; $C(A)$ and $N(A^\top)$ are orthogonal complements in $\mathbb{R}^m$ .
$Ax = b$ is solvable exactly when $y^\top b = 0$ for every $y$ in the left null space $N(A^\top)$ .
$N(A^\top A) = N(A)$ , so $\operatorname{rank}(A^\top A) = \operatorname{rank}(A)$ .

03 Inverse, determinant and projection

A square matrix is invertible exactly when it loses no direction: $N(A) = \{0\}$ ⇔ $\operatorname{rank} A = n$ ⇔ $\det A \ne 0$ ⇔ 0 is not an eigenvalue.
For square matrices one side is enough: $BA = I$ implies $AB = I$ . To solve $Ax = b$ , factor and solve; do not form $A^{-1}$ .
$\det A$ is the signed volume factor of the map; elimination gives $\det A = (-1)^{\#\text{exchanges}} \times$ (product of the pivots).
$\det(AB) = \det A \det B$ , $\det A = \lambda_1 \cdots \lambda_n$ and $\operatorname{tr} A = \lambda_1 + \dots + \lambda_n$ ; a tiny determinant alone does not mean "nearly singular".
$u^\top v = \|u\|\|v\|\cos\theta$ (length of $u$ times the signed shadow of $v$ ), and Cauchy–Schwarz says $|u^\top v| \le \|u\|\|v\|$ .
The projection of $b$ onto the line through $a$ is $p = \dfrac{a^\top b}{a^\top a}\,a$ ; the error $b - p$ is perpendicular to $a$ .
The projection onto $C(A)$ (independent columns) is $p = A\hat x$ with $A^\top A\hat x = A^\top b$ , so $P = A(A^\top A)^{-1}A^\top$ , and $P^2 = P = P^\top$ .

04 Orthogonal matrices and change of basis

Put the basis vectors as the columns of $M$ . Then $x = Mc$ and $c = M^{-1}x$ : $M$ turns new coordinates into standard ones.
In the basis given by the columns of $M$ , the map $A$ has the matrix $B = M^{-1}AM$ . Read it from right to left: $M$ , then $A$ , then $M^{-1}$ .
Similar matrices share the characteristic polynomial, so the eigenvalues, trace and determinant; they also share the rank.
Similarity does not keep eigenvectors ( $v$ becomes $M^{-1}v$ ), singular values or symmetry, and equal eigenvalues do not imply similarity (the shear and $I$ ).
An orthogonal $Q$ has $Q^\top Q = I$ , so $Q^{-1} = Q^\top$ ; it keeps dot products, lengths and angles. $\det Q = \pm 1$ , and every eigenvalue has $|\lambda| = 1$ .
Orthogonal does not mean rotation: $\det Q = -1$ means the map contains a reflection.
A unitary $U$ has $U^*U = I$ , with the conjugate transpose $U^*$ ; the normalized DFT matrix is unitary.
Orthogonal factors keep singular values: $\sigma(Q_1AQ_2) = \sigma(A)$ and $\kappa_2(Q) = 1$ , which is why stable algorithms are built from orthogonal steps.

05 Eigenvalues and Jordan form

$\lambda$ is an eigenvalue of $A$ exactly when $A - \lambda I$ is singular, that is, $\det(A - \lambda I) = 0$ ; the eigenvectors are the nonzero vectors of $N(A - \lambda I)$ .
For a $2 \times 2$ matrix, $p(\lambda) = \lambda^2 - (\operatorname{tr}A)\lambda + \det A$ . In every size, the eigenvalues add up to the trace and multiply to the determinant.
A real matrix can have complex eigenvalues $a \pm bi$ ; for a $2 \times 2$ matrix this means a rotation by $\theta$ and a scaling by $|\lambda| = \sqrt{\det A}$ in a suitable real basis, so no real direction is kept.
$A = X\Lambda X^{-1}$ exactly when $A$ has $n$ independent eigenvectors; then $A^k = X\Lambda^kX^{-1}$ . Distinct eigenvalues are enough for this.
Power iteration converges to the dominant eigenvector line with error of order $|\lambda_2/\lambda_1|^k$ , using only products with $A$ .
Geometric multiplicity $g(\lambda) = n - \operatorname{rank}(A - \lambda I)$ is at most the algebraic multiplicity $a(\lambda)$ ; $A$ is defective when $g < a$ for some $\lambda$ , like the shear.
A Jordan block $\lambda I + N$ has one eigenvector line; its powers contain the growing term $k\lambda^{k-1}$ . The Jordan form jumps under tiny perturbations, so libraries use the Schur form.

06 Spectral theorem and Rayleigh quotient

Spectral theorem: a real matrix is symmetric exactly when $S = Q\Lambda Q^\top = \sum_i \lambda_i q_iq_i^\top$ with $Q$ orthogonal and $\Lambda$ real.
A symmetric matrix has real eigenvalues; for $2\times2$ the discriminant is $(a - c)^2 + 4b^2 \ge 0$ . Eigenvectors of different eigenvalues are orthogonal.
A symmetric matrix always has $n$ orthonormal eigenvectors: if $Sq_1 = \lambda_1 q_1$ , then $S$ maps $q_1^\perp$ into itself, and the argument repeats in one dimension less.
The Rayleigh quotient $R(x) = x^\top Sx / x^\top x$ is a weighted average of the eigenvalues, so $\lambda_{\min} \le R(x) \le \lambda_{\max}$ , with the max and min at the extreme eigenvectors.
The critical points of $R$ are exactly the eigenvectors; middle eigenvectors are saddle points.
Courant–Fischer: $\lambda_k = \max_{\dim U = k} \min_{x \in U} R(x)$ , the best weakest value of $R$ over $k$ -dimensional subspaces.
Weyl: for symmetric $A$ and $E$ , $|\lambda_k(A + E) - \lambda_k(A)| \le \|E\|_2$ . Without symmetry, eigenvalues can move like $\sqrt{\|E\|_2}$ .

07 Positive definite matrices and Cholesky

A symmetric $S$ is positive definite when $x^\top S x > 0$ for every $x \ne 0$ , that is, when all its eigenvalues are positive; PSD allows $\ge 0$ .
Five equivalent PD tests: all eigenvalues $> 0$ ; energy $> 0$ ; $S = A^\top A$ with independent columns; all leading minors $> 0$ ; all pivots $> 0$ . The pivots are $d_k = D_k / D_{k-1}$ .
Leading minors $\ge 0$ do not prove PSD; PSD needs all principal minors $\ge 0$ (counterexample $\operatorname{diag}(0, -1)$ ).
Every covariance and every Gram matrix $\Phi\Phi^\top$ is PSD, because $w^\top \Sigma w = \operatorname{Var}(w^\top x) \ge 0$ and $c^\top \Phi\Phi^\top c = \|\Phi^\top c\|^2 \ge 0$ .
Cholesky $S = LL^\top$ ( $L$ lower triangular, positive diagonal) exists and is unique exactly when $S \succ 0$ ; its radicands are the pivots, and it costs $n^3/3$ flops.
If $z \sim \mathcal N(0, I)$ , then $\mu + Lz \sim \mathcal N(\mu, LL^\top)$ ; any $M$ with $MM^\top = S$ gives the same distribution.
Schur test: $\begin{pmatrix} A & B \\ B^\top & C \end{pmatrix} \succ 0 \iff A \succ 0$ and $C - B^\top A^{-1}B \succ 0$ ; the Schur complement is the covariance of a Gaussian conditional.
The Loewner order $A \preceq B$ ( $B - A \succeq 0$ ) is a partial order, not a total one: $\operatorname{diag}(2,1)$ and $\operatorname{diag}(1,2)$ are incomparable.

08 The SVD

Every real $m \times n$ matrix has an SVD $A = U\Sigma V^\top$ : $U$ and $V$ orthogonal, $\Sigma$ diagonal with $\sigma_1 \ge \sigma_2 \ge \dots \ge 0$ , and $Av_i = \sigma_i u_i$ .
The $\sigma_i^2$ are the eigenvalues of $A^\top A$ ; the $v_i$ are its eigenvectors, and $u_i = Av_i/\sigma_i$ . The number of nonzero $\sigma_i$ is the rank.
The SVD gives orthonormal bases of all four subspaces, $\|A\|_2 = \sigma_1$ and $\|A\|_F = \sqrt{\sum_i \sigma_i^2}$ .
Eckart–Young–Mirsky: the truncated SVD $A_k = \sum_{i \le k}\sigma_i u_i v_i^\top$ is a best approximation of rank at most $k$ , with error $\sigma_{k+1}$ in the spectral norm and $\sqrt{\sum_{i>k}\sigma_i^2}$ in the Frobenius norm.
Polar decomposition: $A = QP$ with $Q = UV^\top$ (the nearest orthogonal matrix) and $P = V\Sigma V^\top = (A^\top A)^{1/2}$ .
Pseudoinverse: $A^+ = V\Sigma^+U^\top$ , and $A^+b$ is the least-squares solution with the smallest norm. In floating point, treat tiny $\sigma_i$ as zero (rcond).
Compute the SVD from $A$ itself, never from $A^\top A$ : forming $A^\top A$ squares the condition number.

09 PCA and randomized SVD

PC1 is the unit vector $w$ that maximizes the variance $w^\top S w$ of the projected, centered data. It is the top eigenvector of $S = X_c^\top X_c/(N-1)$ , and the maximum variance is $\lambda_1$ .
With samples as rows and $X_c = U\Sigma V^\top$ : the principal directions are the columns of $V$ , the variances are $\lambda_i = \sigma_i^2/(N-1)$ , and the scores are $X_cV = U\Sigma$ .
Maximum captured variance = minimum reconstruction error. The best $k$ -dimensional subspace is spanned by the top $k$ right singular vectors, with error $\sum_{j>k}\sigma_j^2$ .
Always center: without centering, the top direction turns toward the mean. $N$ samples give at most $N - 1$ components with nonzero variance.
PCA is not scale invariant: standardize features that have different units.
Use the SVD of $X_c$ rather than the covariance when accuracy matters or when $d \gg N$ : forming $X_c^\top X_c$ squares the condition number.
Randomized SVD: $Y = A\Omega$ with $\ell = k + p$ Gaussian columns, $Q = \operatorname{orth}(Y)$ , $B = Q^\top A$ , a small SVD of $B$ , then $U = Q\tilde U$ . It reads $A$ in $2q + 2$ passes.
Oversampling ( $p \approx 5$ – $10$ ) protects against unlucky random vectors; power iterations ( $q = 1$ – $2$ , with a QR after each product) help when the spectrum decays slowly.

10 Factorizations and LU

A factorization writes $A$ as a product of triangular, orthogonal or diagonal matrices: factor once (about $n^3$ flops), then each use costs about $n^2$ .
$PA = LU$ records Gaussian elimination: $P$ the row swaps, $U$ the upper-triangular result with the pivots on its diagonal, $L$ the multipliers $\ell_{ij}$ in their positions.
The multipliers go into $L$ unchanged because each pivot row is already final: row $i$ of $A$ = row $i$ of $U$ + $\sum_{j<i} \ell_{ij}$ (row $j$ of $U$ ).
Partial pivoting picks the largest $|a_{ik}|$ as pivot, so $|\ell_{ij}| \le 1$ ; it makes LU work for every square matrix and keeps it accurate in practice.
Never form $A^{-1}$ to solve $Ax = b$ : LU costs $\tfrac23 n^3$ once and $2n^2$ per right-hand side, the inverse about $2n^3$ and gives less accurate answers. Cholesky costs $\tfrac13 n^3$ .
Every matrix has an SVD; $A = X\Lambda X^{-1}$ needs $n$ independent eigenvectors; $Q\Lambda Q^\top$ needs symmetry; least squares uses QR.
Woodbury: $(A + UCV)^{-1} = A^{-1} - A^{-1}U(C^{-1} + VA^{-1}U)^{-1}VA^{-1}$ updates an inverse after a rank- $k$ change with a $k\times k$ inverse; it turns $d\times d$ ridge into an $n\times n$ solve.
Each general factorization of an $n\times n$ matrix has $n^2$ free parameters, each symmetric one $n(n+1)/2$ .

11 Norms of vectors and matrices

A norm satisfies three rules: $\|x\| = 0$ only for $x = 0$ , $\|cx\| = |c|\,\|x\|$ , and the triangle inequality. $\ell_p$ is a norm for $p \ge 1$ ; $\ell_p$ with $p < 1$ and the count " $\ell_0$ " are not.
For every vector, $\|x\|_\infty \le \|x\|_2 \le \|x\|_1 \le \sqrt n\,\|x\|_2$ .
$\ell_1$ gives exact zeros: the $\ell_1$ ball has corners on the axes, and soft-thresholding $S_\lambda(z) = \operatorname{sign}(z)\max(|z| - \lambda, 0)$ sets every $|z| \le \lambda$ to 0. Ridge only shrinks: $z/(1 + \lambda)$ .
The spectral, Frobenius and nuclear norms are the $\ell_\infty$ , $\ell_2$ and $\ell_1$ norms of the singular values: $\sigma_1$ , $\sqrt{\sum_i\sigma_i^2}$ and $\sum_i\sigma_i$ (Schatten $p = \infty, 2, 1$ ).
The induced norms $\|A\|_1$ and $\|A\|_\infty$ are the largest absolute column sum and the largest absolute row sum. Frobenius and nuclear norms are not induced, because $\|I_n\|_F = \sqrt n \ne 1$ .
The Lipschitz constant of $x \mapsto Wx$ is $\sigma_1(W)$ . For a network with 1-Lipschitz activations, $\prod_l\|W_l\|_2$ is an upper bound, often loose; spectral normalization divides each $W_l$ by an estimate of $\sigma_1$ .
The rank is not convex; the nuclear norm is its standard convex surrogate, and singular value soft-thresholding gives low rank.

12 QR and least squares

Least squares $\min_x\|Ax - b\|_2$ is the orthogonal projection of $b$ onto $C(A)$ : the residual satisfies $A^\top(b - A\hat x) = 0$ (the normal equations).
Every $A$ with independent columns has a unique $A = QR$ with $Q^\top Q = I$ and $R$ upper triangular with positive diagonal. Gram–Schmidt builds it: $r_{jk} = q_j^\top a_k$ , $v_k = a_k - \sum_{j<k} r_{jk}q_j$ , $r_{kk} = \|v_k\|$ , $q_k = v_k/r_{kk}$ .
With $A = QR$ , least squares is one back substitution: $R\hat x = Q^\top b$ .
The normal equations square the condition number, $\kappa(A^\top A) = \kappa(A)^2$ , so their error is about $\varepsilon\kappa^2$ ; Householder QR gives about $\varepsilon\kappa$ .
Loss of orthogonality $\|Q^\top Q - I\|$ : about $\varepsilon\kappa^2$ for classical Gram–Schmidt, $\varepsilon\kappa$ for modified Gram–Schmidt, $\varepsilon$ for Householder. A small $\|A - QR\|$ says nothing about it.
A Householder reflection $H = I - 2vv^\top/(v^\top v)$ with $v = x + \operatorname{sign}(x_1)\|x\|e_1$ maps $x$ to $-\operatorname{sign}(x_1)\|x\|e_1$ without cancellation; a Givens rotation zeros one chosen entry.
For an underdetermined full-row-rank system, the minimum-norm solution is $x^+ = A^\top(AA^\top)^{-1}b = A^+b$ , the only solution in the row space. For rank-deficient $A$ , use the SVD or column-pivoted QR.

13 Floating point and conditioning

A binary float is $\pm(1.f)_2 \times 2^e$ with $p$ significant bits. The gap between neighbours grows with $|x|$ , but rounding to nearest has relative error at most $u = 2^{-p}$ ( $2^{-53} \approx 1.1\times10^{-16}$ in double).
Subtracting nearly equal rounded numbers amplifies their old errors by $(|x| + |y|)/|x - y|$ (catastrophic cancellation). The fix is a different formula: $2\sin^2(x/2)$ , log1p, expm1, Vieta's formula, Welford's variance.
A running sum stops growing once half the gap at $s$ exceeds the term: in fp16 $2048 + 1 = 2048$ , in bf16 $256 + 1 = 256$ . So 16-bit training accumulates in fp32 and keeps fp32 master weights.
bf16 has the range of fp32 but only 8 significant bits; fp16 has 11 bits but overflows above 65504 and underflows below about $6\times10^{-8}$ , so only fp16 needs loss scaling.
$\kappa_2(A) = \sigma_{\max}/\sigma_{\min}$ , and $\|\delta x\|/\|x\| \le \kappa(A)\,\|\delta b\|/\|b\|$ ; the bound is attained for $b$ along $u_1$ and $\delta b$ along $u_n$ .
$\kappa_2(A^\top A) = \kappa_2(A)^2$ : the normal equations lose twice as many digits as QR.
The backward error of $\hat x$ is the smallest relative data change that makes $\hat x$ exact; for $Ax = b$ it is a relative residual. Forward error $\lesssim \kappa \times$ backward error, so a backward-stable solver loses about $\log_{10}\kappa$ digits.

14 Eigenvalue algorithms and Krylov methods

Inverse iteration with shift $\sigma$ converges to the eigenvector whose eigenvalue is closest to $\sigma$ , at the rate $|\lambda_J - \sigma|/|\lambda_K - \sigma|$ ; Rayleigh quotient iteration updates the shift every step and converges cubically for symmetric $A$ .
The QR algorithm ( $A_k = Q_kR_k$ , $A_{k+1} = R_kQ_k$ ) is simultaneous power iteration: $A_k = \underline Q_k^\top A\underline Q_k$ and $A^k = \underline Q_k\underline R_k$ . Without shifts, entry $(j+1, j)$ decays like $|\lambda_{j+1}/\lambda_j|^k$ .
Practical eigensolvers reduce once to Hessenberg (tridiagonal if symmetric) form, then use shifted QR steps (Wilkinson shift) with deflation; each step costs $O(n^2)$ , or $O(n)$ if tridiagonal.
The SVD is computed from a bidiagonal form (Golub–Kahan), never from $\operatorname{eig}(A^\top A)$ , which loses all singular values below about $\sqrt\varepsilon\,\sigma_1$ .
Arnoldi builds an orthonormal basis $Q_k$ of $\mathcal K_k(A, b) = \operatorname{span}\{b, Ab, \dots, A^{k-1}b\}$ with $AQ_k = Q_{k+1}\tilde H_k$ ; for symmetric $A$ , $H_k$ is tridiagonal (Lanczos). Ritz values converge to the extreme eigenvalues first.
CG minimizes $\|x - x^*\|_A$ over $x_0 + \mathcal K_k$ ; its error is $p_k(A)e_0$ with $p_k(0) = 1$ , so $\|e_k\|_A/\|e_0\|_A \le 2\big(\tfrac{\sqrt\kappa - 1}{\sqrt\kappa + 1}\big)^k$ : $O(\sqrt\kappa)$ iterations versus $O(\kappa)$ for steepest descent.
With $d$ distinct eigenvalues CG is exact after at most $d$ steps; clustered eigenvalues and preconditioning make it fast. GMRES minimizes $\|b - Ax\|_2$ for any nonsingular $A$ but needs long recurrences.

15 Autodiff, LoRA, tensors, attention

A JVP $Jv$ gives one column of the Jacobian and a VJP $u^\top J$ gives one row. The full $m\times n$ Jacobian needs $n$ forward passes or $m$ reverse passes.
Reverse mode multiplies the chain of Jacobians starting at the output. For a scalar loss every intermediate result is a row vector, so one backward pass gives the whole gradient at a few times the cost of the forward pass; the price is the memory for the stored activations.
For a linear layer $y = Wx$ : $\bar x = W^\top\bar y$ and $\bar W = \bar yx^\top$ (rank 1); for a batch $Y = WX$ , $\bar W = \bar YX^\top$ . Every gradient has the shape of its variable.
LoRA learns $W_0 + \tfrac{\alpha}{r}BA$ with $r(d + k)$ trainable numbers; $B = 0$ at the start, so training starts at $W_0$ and the update always has rank at most $r$ .
GaLore trains all weights but keeps Adam's state in a rank- $r$ subspace of the gradient that is refreshed every few hundred steps, so its total update can have full rank.
The mode- $n$ unfolding $X_{(n)}$ has the mode- $n$ fibers as columns; the multilinear rank is $(\operatorname{rank}X_{(1)}, \operatorname{rank}X_{(2)}, \operatorname{rank}X_{(3)})$ . A rank- $R$ CP model has $R(I + J + K)$ parameters.
The truncated HOSVD (top singular vectors of each unfolding) is within a factor $\sqrt N$ of the best Tucker approximation; tensors have no Eckart–Young theorem.
An attention head has logits $x_i^\top W_{QK}x_j/\sqrt{d_h}$ and output $W_{OV}XA^\top$ , where $W_{QK} = W_Q^\top W_K$ and $W_{OV} = W_OW_V$ have rank at most $d_h$ ; the attention matrix $A$ itself is usually full rank.

16 Matrix calculus and matrix functions

The differential $df$ is the part of $f(X + dX) - f(X)$ that is linear in $dX$ . If $df = \operatorname{tr}(G^\top dX)$ for every $dX$ , then $\nabla_X f = G$ , a matrix with the shape of $X$ .
The product rule keeps the order: $d(FG) = dF\,G + F\,dG$ . So $d(X^{-1}) = -X^{-1}\,dX\,X^{-1}$ , not $-X^{-2}dX$ .
Three gradients to know: $\nabla\operatorname{tr}(AX) = A^\top$ , $\nabla x^\top Ax = (A + A^\top)x$ and $\nabla\log\det X = X^{-\top}$ (from $d\log\det X = \operatorname{tr}(X^{-1}dX)$ ).
A correct derivative leaves an $O(t^2)$ error in $f(X + t\,dX) \approx f(X) + t\,df$ (slope 2 on a log–log plot); a wrong one leaves an $O(t)$ error.
The softmax Jacobian is $J = \operatorname{diag}(s) - ss^\top$ : symmetric, PSD, rows summing to 0, rank $n - 1$ . The cross-entropy gradient is $s - e_y$ , and the VJP costs $O(n)$ .
For a symmetric $S = Q\Lambda Q^\top$ , $f(S) = Qf(\Lambda)Q^\top$ : the function acts on the eigenvalues, not on the entries. $e^{A+B} = e^Ae^B$ holds when $AB = BA$ .
$x' = Ax$ has the unique solution $x(t) = e^{At}x_0$ ; it decays for every $x_0$ exactly when all $\operatorname{Re}\lambda_i(A) < 0$ .
$\operatorname{vec}(AXB) = (B^\top\otimes A)\operatorname{vec}X$ ; $A\otimes B$ has the eigenvalues $\lambda_i\mu_j$ and the Kronecker sum $A\otimes I + I\otimes B$ has $\lambda_i + \mu_j$ .

17 Perturbation theory

Weyl: for symmetric $A$ and $E$ , $|\lambda_k(A + E) - \lambda_k(A)| \le \|E\|_2$ for every $k$ . Symmetric eigenvalues have condition number 1.
Weyl for singular values: $|\sigma_k(A + E) - \sigma_k(A)| \le \|E\|_2$ for any matrices of the same shape; it follows from the symmetric embedding $\begin{pmatrix} 0 & A \\ A^\top & 0 \end{pmatrix}$ , whose eigenvalues are $\pm\sigma_i(A)$ and zeros.
Non-symmetric matrices have no such bound: Bauer–Fike allows $\kappa(X)\|E\|_2$ , and a perturbed $n\times n$ Jordan block moves its eigenvalues by $\|E\|_2^{1/n}$ .
Principal angles between subspaces: $\cos\theta_i = \sigma_i(\hat V^\top V)$ , and $\|\sin\Theta\|_2 = \|VV^\top - \hat V\hat V^\top\|_2$ . Two planes in $\mathbb{R}^3$ always have $\theta_1 = 0$ .
To first order, $\lambda_k$ moves by $q_k^\top Eq_k$ and $q_k$ mixes in $q_j$ with weight $q_j^\top Eq_k/(\lambda_k - \lambda_j)$ : the condition number of an eigenvector is 1/gap.
Davis–Kahan (Yu–Wang–Samworth form): $\sin\theta(\hat q_k, q_k) \le 2\|E\|_2/\delta_k$ , where $\delta_k$ is the gap of $\lambda_k$ to its neighbours in $A$ .
For a block of eigenvectors only the gap between the block and the rest matters, so a cluster of close eigenvalues has a stable subspace but unstable single eigenvectors.

18 Sketching, JL and random matrices

A Gaussian map $x \mapsto Gx/\sqrt k$ keeps one squared length with relative error about $\sqrt{2/k}$ , whatever the original dimension $D$ is.
Johnson–Lindenstrauss: $k \ge (4\ln n + 2\ln(1/\delta))/(\varepsilon^2/2 - \varepsilon^3/3)$ Gaussian rows keep all squared pairwise distances of $n$ points within $1 \pm \varepsilon$ , with probability at least $1-\delta$ ; $k$ does not depend on $D$ .
$S$ is an $\varepsilon$ -subspace embedding for $\operatorname{range}(U)$ ( $U$ orthonormal) exactly when $\|I - U^\top S^\top SU\|_2 \le \varepsilon$ , that is, all singular values of $SU$ lie in $[\sqrt{1-\varepsilon}, \sqrt{1+\varepsilon}]$ ; a $d$ -dimensional subspace needs about $d/\varepsilon^2$ Gaussian rows.
Sketch-and-solve least squares gives a residual within $\sqrt{(1+\varepsilon)/(1-\varepsilon)}$ of the optimum, but $\tilde x$ can be far from $x^*$ when $A$ is ill-conditioned.
Sketch-and-precondition uses $SA = QR$ to make $\kappa(AR^{-1}) \le \sqrt{(1+\varepsilon)/(1-\varepsilon)}$ ; LSQR then reaches full accuracy in a few dozen iterations, whatever $\kappa(A)$ is.
For pure noise with variance $\sigma^2$ and $\gamma = p/n \le 1$ , the eigenvalues of $X^\top X/n$ fill the Marchenko–Pastur support $[\sigma^2(1-\sqrt\gamma)^2, \sigma^2(1+\sqrt\gamma)^2]$ , although every true eigenvalue is $\sigma^2$ .
A spike $\theta$ is visible to PCA only if $\theta > \sqrt\gamma$ (BBP transition); then the top eigenvalue tends to $\sigma^2(1+\theta)(1+\gamma/\theta)$ , which overestimates the true variance, and the eigenvector is tilted.
In $\mathbb{R}^d$ , random Gaussian vectors have norm $\approx \sqrt d$ and random directions are at $90°$ up to about $57.3°/\sqrt d$ ; this allows many more almost-orthogonal directions than $d$ (superposition).

19 Structured matrices in ML

A circulant $C(c)$ is diagonalized by the DFT: $Cf_k = \hat c_k f_k$ with $\hat c = \mathrm{fft}(c)$ , so a circular convolution costs $O(n\log n)$ with the FFT.
A linear map commutes with the cyclic shift exactly when it is a circulant: shift-equivariant linear layers are circular convolutions.
An FNO Fourier layer is a learned circulant truncated to $k_{\max}$ modes; its $k_{\max}d_v^2$ complex weights do not depend on the grid size $n$ , so it can run on any uniform grid that resolves the input.
The graph Laplacian $L = D - A$ is PSD with $x^\top Lx = \sum_{\text{edges}} A_{ij}(x_i - x_j)^2$ ; the multiplicity of the eigenvalue 0 is the number of connected components, and the signs of the Fiedler vector $u_2$ split the graph.
GCN: a first-order Chebyshev filter with $\lambda_{\max} \approx 2$ , one parameter and the renormalization trick gives $H' = \sigma(\hat AHW)$ with $\hat A = \tilde D^{-1/2}(A+I)\tilde D^{-1/2}$ , whose eigenvalues lie in $(-1, 1]$ ; many layers over-smooth.
$f$ is equivariant when $f(\rho(g)x) = \rho'(g)f(x)$ ; equivariant linear maps form a null space, for example $aI + b\mathbf 1\mathbf 1^\top$ for permutations of $\mathbb{R}^n$ .
$\operatorname{St}(n, p) = \{X : X^\top X = I_p\}$ has dimension $np - p(p+1)/2$ ; a Riemannian gradient step projects the gradient onto the tangent space and then retracts (normalize for $p = 1$ , QR or polar factor in general).
$\operatorname{Gr}(n, p) = \operatorname{St}(n, p)/O(p)$ is the set of $p$ -dimensional subspaces, of dimension $p(n-p)$ ; PCA is an optimization problem on it.