Linear Algebra

Canonical T1 reference. Companion deep notes:

• linear-algebra-essentials — hands-on operational treatment (vectors, matrices, dot/cross products, four subspaces, computational examples).
• numerical-linear-algebra — backward stability, conditioning, LU/QR/Cholesky/eigensolvers as software.
• svd-pca-spectral — SVD/PCA/spectral decompositions in depth.
• eigenvalue-problems — eigenvalue solvers, Krylov, perturbation theory.
• tensor-calculus — multilinear generalizations.

1. At a glance

Linear algebra is the theory of vector spaces, linear maps between them, and the decompositions that expose their structure. It is the most reused mathematical machinery in applied science:

• Numerical computing — every PDE discretisation, every regression, every neural-network forward pass reduces to matrix-vector multiplication, factorisation, or eigenvalue extraction.
• Geometry + graphics + robotics — rigid transforms are 4×4 matrices; rotations live in SO(3); cameras are projective maps.
• Statistics + ML — covariance matrices, design matrices, kernel Gram matrices, attention’s QKᵀ all sit at the centre of inference.
• Quantum mechanics — observables are Hermitian operators on Hilbert spaces; time evolution is unitary.
• Networks + graphs — adjacency + Laplacian matrices encode connectivity; their spectra determine clustering, diffusion, and centrality.

This note is the conceptual spine. For computational depth on any sub-topic, follow the cross-links to the companion notes above.

Three views of a matrix A ∈ ℝᵐˣⁿ

Master all three; switch fluidly depending on the question:

1. Linear map — $A:{\mathbb{R}}^n\to {\mathbb{R}}^m$, $x\mapsto Ax$. Captures what A does to space. Dominant for geometry, dynamics, change of basis.
2. Column collection — $A=[a_1\mid a_2\mid \cdots \mid a_n]$, with $Ax={\sum }_i{x}_i{a}_i$. Captures what outputs are reachable. Dominant for solving $Ax=b$.
3. Bilinear form coefficients — $(x,y)\mapsto x^{\top }Ay$. Captures quadratic energy / inner products / quadratic constraints. Dominant for optimisation, statistics (precision matrices), physics (Hamiltonians).

A fourth less common view — data table (rows = samples, columns = features) — emerges in statistics and ML. SVD blurs the distinction by treating rows and columns symmetrically.

2. Vector spaces and subspaces

A vector space V over a field F (almost always ℝ or ℂ) is a set with an addition $+:V\times V\to V$ and scalar multiplication $\cdot :F\times V\to V$ satisfying eight axioms — associativity and commutativity of $+$, distributivity, identity 0 and scalar 1, additive inverses, and compatibility of $\cdot$. The axioms abstract the operational behaviour of arrows in ℝⁿ.

Canonical examples.

• ${\mathbb{R}}^n$ — n-tuples of reals; the prototype.
• ${\mathbb{C}}^n$ — complex vectors; the natural setting for spectral theory.
• ${\mathrm{Mat}}_{m\times n}(\mathbb{R})$ — matrices themselves form a vector space of dimension $mn$.
• ${\mathcal{P}}_n$ — polynomials of degree $\le n$; dimension $n+1$, basis $\{1,t,t^2,\dots ,t^n\}$.
• $C^k(I)$ — k-times continuously differentiable functions on an interval; infinite-dimensional. The natural home of differential operators (see functional-analysis).
• ${\ell }^2$ — square-summable sequences; the discrete prototype of a Hilbert space.

A subspace $W\subseteq V$ is a non-empty subset closed under addition and scalar multiplication. Equivalently: contains 0, closed under linear combinations.

Operations on subspaces.

• Sum — $W_1+W_2=\{w_1+w_2:w_i\in W_i\}$.
• Intersection — $W_1\cap W_2$ is always a subspace; union is not (it fails closure).
• Direct sum — $V=W_1\oplus W_2$ iff $V=W_1+W_2$ and $W_1\cap W_2=\{0\}$, equivalently every $v\in V$ has a unique decomposition $v=w_1+w_2$. Dimension is additive: $\dim (W_1\oplus W_2)=\dim W_1+\dim W_2$.
• Quotient — $V/W$ is the set of cosets $v+W$; useful in algebraic geometry, homological algebra, and the abstract construction of tangent spaces.

3. Linear independence, basis, dimension

A set $\{v_1,\dots ,v_k\}\subset V$ is linearly independent iff ${\sum }_i{c}_i{v}_i=0$ forces all $c_i=0$. Otherwise linearly dependent — some $v_j$ is a linear combination of the others.

The span of a set is the subspace of all finite linear combinations; the smallest subspace containing the set.

A basis for V is a linearly independent set whose span is V. Equivalently: every $v\in V$ has a unique representation as a linear combination of basis vectors.

Dimension theorem (Hamel). Every vector space has a basis (in finite dimensions: choose a maximal independent set; in infinite dimensions: Zorn’s Lemma; see mathematical-logic-and-foundations). Any two bases of V have the same cardinality — that cardinality is the dimension $\dim V$.

Standard basis of ℝⁿ. $e_i$ has a 1 in coordinate i and 0 elsewhere. Any $x\in {\mathbb{R}}^n$ decomposes as $x={\sum }_i{x}_i{e}_i$; the components $x_i$ are the coordinates in the standard basis.

Change of basis. If $B=\{b_1,\dots ,b_n\}$ is another basis, the change-of-basis matrix $P$ has columns $b_i$ in standard coordinates; for any $v$, $[v{]}_{\mathrm{std}}=P[v{]}_B$ and $[v{]}_B=P^{-1}[v{]}_{\mathrm{std}}$. Linear maps transform by similarity: $[T{]}_B=P^{-1}[T{]}_{\mathrm{std}}P$. This is the algebraic content of “choose better coordinates”.

4. Linear transformations and matrix representation

A linear transformation $T:V\to W$ satisfies $T(\alpha u+\beta v)=\alpha T(u)+\beta T(v)$. Given bases $\{v_j\}$ of V and $\{w_i\}$ of W, T is encoded by the matrix $A$ whose j-th column is $T(v_j)$ written in the W-basis. Then $T(v)$ in coordinates equals $A[v]$.

Composition = product. If $T:V\to W$ and $S:W\to U$, then $[S\circ T]=[S]\cdot [T]$. The non-commutativity of matrix multiplication is the non-commutativity of function composition.

Kernel and image.

• $\ker T=\{v\in V:T(v)=0\}$ — the null space in matrix terms, written $N(A)$.
• $\mathrm{im}T=\{T(v):v\in V\}$ — the column space (range) $C(A)$ in matrix terms.

Both are subspaces. The kernel measures how much T collapses; the image measures how much T can reach.

5. Rank-nullity theorem

For $A\in {\mathbb{R}}^{m\times n}$:

$$\dim N(A)+\dim C(A)=n$$

i.e. nullity + rank = number of columns. Equivalently: $\mathrm{rank}(A)=n-\dim N(A)$. The theorem expresses conservation: every input dimension either contributes to the output (rank) or gets collapsed (nullity).

Corollaries.

• A square $A\in {\mathbb{R}}^{n\times n}$ is invertible iff $\mathrm{rank}(A)=n$ iff $N(A)=\{0\}$ iff columns are linearly independent iff $\det A\ne 0$.
• $\mathrm{rank}(A)=\mathrm{rank}(A^{\top })$ — row rank equals column rank. Provable by Gaussian elimination or by recognising both as the number of nonzero singular values.

6. The four fundamental subspaces (Strang)

For $A\in {\mathbb{R}}^{m\times n}$, every vector in ${\mathbb{R}}^n$ decomposes into the row space $C(A^{\top })$ and null space $N(A)$; every vector in ${\mathbb{R}}^m$ decomposes into the column space $C(A)$ and left null space $N(A^{\top })$. The four spaces and their dimensions:

Subspace	Lives in	Dimension	Orthogonal complement
Column space $C(A)$	${\mathbb{R}}^m$	$r$	$N(A^{\top })$
Row space $C(A^{\top })$	${\mathbb{R}}^n$	$r$	$N(A)$
Null space $N(A)$	${\mathbb{R}}^n$	$n-r$	$C(A^{\top })$
Left null space $N(A^{\top })$	${\mathbb{R}}^m$	$m-r$	$C(A)$

where $r=\mathrm{rank}(A)$.

Geometric interpretation. A maps the row space isomorphically onto the column space; it sends the null space to 0. Every $x\in {\mathbb{R}}^n$ splits as $x=x_{\mathrm{row}}+x_{\mathrm{null}}$, and $Ax=A{x}_{\mathrm{row}}$.

This four-subspace picture (Strang 1980s) is the conceptual heart of the singular value decomposition: SVD is the algorithm that produces orthonormal bases for all four spaces at once, with the singular values measuring the gain along each row-space → column-space direction.

7. Determinants

For $A\in {\mathbb{R}}^{n\times n}$, the determinant $\det A$ is the unique alternating multilinear function on the columns satisfying $\det I=1$.

Geometric meaning. $|\det A|$ is the volume of the image of the unit cube under A; $\det A>0$ iff A preserves orientation; $\det A<0$ iff it reverses it. For 2×2: $|\det A|$ is the area of the parallelogram spanned by the columns. For 3×3: the signed volume of the parallelepiped.

Algebraic properties.

• $\det (AB)=\det A\cdot \det B$.
• $\det A^{\top }=\det A$.
• $\det A^{-1}=(\det A{)}^{-1}$.
• $\det (\alpha A)={\alpha }^n\det A$ (n-homogeneity).
• Swapping two rows or columns negates the determinant.

Computation.

• Cofactor expansion along any row or column — pedagogical, $O(n!)$, impractical for $n>4$.
• LU decomposition — $\det A=\det L\cdot \det U={\prod }_i{u}_{ii}$ (with sign for row swaps). $O(n^3)$, the standard numerical method.
• Volumes via Gram determinant — $\det (V^{\top }V)=(\mathrm{vol}{)}^2$ for V the matrix of column vectors.

Practical note. In numerical work the determinant is rarely what you want. For invertibility, check the condition number; for volumes, accumulate log-determinants (avoiding overflow); for linear systems, never solve $Ax=b$ via Cramer’s rule.

8. Eigenvalues and eigenvectors

A scalar $\lambda \in \mathbb{C}$ is an eigenvalue of $A\in {\mathbb{R}}^{n\times n}$ if there exists a nonzero $v$ with $Av=\lambda v$; v is the corresponding eigenvector. The set of eigenvalues is the spectrum $\sigma (A)$.

Characteristic polynomial. $p_A(\lambda )=\det (\lambda I-A)$ is a degree-n monic polynomial whose roots are exactly the eigenvalues (with algebraic multiplicity). By the fundamental theorem of algebra, A always has n complex eigenvalues counted with multiplicity.

Eigenspaces and geometric multiplicity. $E_{\lambda }=N(A-\lambda I)$ is the eigenspace at $\lambda$; its dimension is the geometric multiplicity $g(\lambda )$. Always $1\le g(\lambda )\le m(\lambda )$ where $m(\lambda )$ is algebraic multiplicity. When $g<m$ the matrix is defective and not diagonalisable.

Trace and determinant.

• $\mathrm{tr}(A)={\sum }_i{\lambda }_i$ (sum of eigenvalues with algebraic multiplicity).
• $\det A={\prod }_i{\lambda }_i$.

Spectral theorem (real symmetric / complex Hermitian case). If $A=A^{\top }$ (real) or $A=A^{\ast }$ (complex), then:

1. All eigenvalues are real.
2. Eigenvectors for distinct eigenvalues are orthogonal.
3. A admits an orthonormal eigenbasis: $A=Q\Lambda Q^{\top }$ where Q is orthogonal and $\Lambda$ is diagonal.

This is the single most important theorem in linear algebra. It guarantees that symmetric problems — covariance matrices, Hessians at minima, Hamiltonians, kernel Gram matrices — have a clean orthogonal eigendecomposition.

Normal matrices. $A{A}^{\ast }=A^{\ast }A$ — the broadest class admitting a unitary diagonalisation. Includes Hermitian, skew-Hermitian, unitary, and (real) orthogonal matrices.

For non-symmetric matrices, see also eigenvalue-problems for Krylov methods, Schur decomposition, and the more delicate perturbation theory.

9. Diagonalisation and Jordan form

Diagonalisation. $A$ is diagonalisable iff there exists invertible P with $A=P\Lambda P^{-1}$, $\Lambda$ diagonal. The columns of P are the eigenvectors; the diagonal of $\Lambda$ are the eigenvalues. Equivalent conditions:

• A has n linearly independent eigenvectors.
• Geometric multiplicity equals algebraic multiplicity for every eigenvalue.
• The minimal polynomial has only simple roots.

When diagonalisation works. Symmetric / Hermitian / normal matrices always diagonalise (with orthonormal P). Generic matrices over ℂ diagonalise (the non-diagonalisable matrices form a measure-zero set), but generic matrices over ℝ may have complex eigenvalues, requiring a real block-diagonal form with 2×2 rotation-scaling blocks for complex conjugate pairs.

Jordan canonical form (Jordan 1870). Over ℂ, every matrix is similar to a Jordan form

$$J=\mathrm{diag}(J_{n_1}({\lambda }_1),J_{n_2}({\lambda }_2),\dots ),J_k(\lambda )=\left(\begin{array}{cccc}\lambda & 1& & \\ & \lambda & \ddots & \\ & & \ddots & 1\\ & & & \lambda \end{array}\right)$$

where each Jordan block $J_k(\lambda )$ is a $k\times k$ upper bidiagonal block. Diagonalisable matrices are the special case where every block is 1×1. The Jordan form is theoretically unique up to block order but numerically unstable — tiny perturbations split a Jordan block into nearby diagonal entries. In computation, use the Schur form $A=QT{Q}^{\ast }$ (Q unitary, T upper triangular) instead.

Matrix functions via diagonalisation. If $A=P\Lambda P^{-1}$ then $A^k=P{\Lambda }^k{P}^{-1}$ and more generally $f(A)=Pf(\Lambda )P^{-1}$ for any analytic f, where $f(\Lambda )=\mathrm{diag}(f({\lambda }_i))$. This is how matrix exponentials, square roots, and logarithms are defined and computed.

10. Inner products and orthogonality

An inner product on a real vector space V is a map $⟨\cdot ,\cdot ⟩:V\times V\to \mathbb{R}$ that is:

• Bilinear — linear in each argument.
• Symmetric — $⟨u,v⟩=⟨v,u⟩$.
• Positive definite — $⟨v,v⟩\ge 0$ with equality iff $v=0$.

For complex spaces, replace symmetry with Hermitian symmetry $⟨u,v⟩=\overline{⟨v,u⟩}$ and bilinearity becomes sesquilinearity (conjugate-linear in one argument).

Canonical example. Dot product on ℝⁿ: $⟨x,y⟩=x^{\top }y={\sum }_i{x}_i{y}_i$. Induces the Euclidean norm $\Vert x\Vert =\sqrt{⟨x,x⟩}$.

General inner products. $⟨x,y{⟩}_M=x^{\top }My$ for any symmetric positive definite M defines an inner product (the Mahalanobis inner product when $M={\Sigma }^{-1}$, a covariance inverse). On function spaces, $⟨f,g⟩=\int fg$ defines the $L^2$ inner product (see functional-analysis).

Orthogonality. $u\perp v$ iff $⟨u,v⟩=0$. A set $\{u_i\}$ is orthonormal iff $⟨u_i,u_j⟩={\delta }_{ij}$.

Cauchy-Schwarz inequality. $|⟨u,v⟩|\le \Vert u\Vert \cdot \Vert v\Vert$ with equality iff u, v are colinear. The single most-used inequality in analysis.

Triangle inequality. $\Vert u+v\Vert \le \Vert u\Vert +\Vert v\Vert$.

Gram-Schmidt orthogonalisation

Given linearly independent $\{v_1,\dots ,v_k\}$, produce orthonormal $\{q_1,\dots ,q_k\}$ with the same span:

$$\begin{array}{rl}{\tilde{q}}_j& =v_j-\sum _{i<j}⟨v_j,q_i⟩q_i,\\ q_j& ={\tilde{q}}_j/\Vert {\tilde{q}}_j\Vert .\end{array}$$

Each step subtracts the projection of $v_j$ onto the span of earlier $q_i$, leaving the orthogonal component. Classical Gram-Schmidt as written is numerically unstable; Modified Gram-Schmidt (subtract projections sequentially as you build them) is the working algorithm. Even better numerically: Householder reflections (the basis of practical QR; see numerical-linear-algebra).

The output of Gram-Schmidt on the columns of A is the QR decomposition: $A=QR$ with Q orthogonal and R upper triangular. QR is the standard tool for least squares and for the QR-algorithm for eigenvalues.

11. Projections

Given a subspace $W\subseteq V$, the orthogonal projection $P_W:V\to W$ sends $v$ to the closest point in W:

$$P_{W}v=\arg \underset{w\in W}{\min }\Vert v-w\Vert .$$

If $\{q_1,\dots ,q_k\}$ is an orthonormal basis of W and $Q=[q_1\mid \cdots \mid q_k]$, then $P_W=Q{Q}^{\top }$. If $A\in {\mathbb{R}}^{n\times k}$ has linearly independent columns spanning W (not necessarily orthonormal), $P_W=A(A^{\top }A{)}^{-1}{A}^{\top }$.

Properties.

• $P^2=P$ (idempotent).
• $P=P^{\top }$ (symmetric — this is what makes the projection orthogonal vs oblique).
• $\mathrm{rank}(P)=\dim W$; eigenvalues are 0 and 1.
• $I-P$ projects onto $W^{\perp }$.

Orthogonal decomposition. $V=W\oplus W^{\perp }$ and every $v=P_{W}v+(I-P_W)v$. Pythagoras: $\Vert v{\Vert }^2=\Vert P_{W}v{\Vert }^2+\Vert (I-P_W)v{\Vert }^2$.

Projections are the geometric content of least squares: minimise $\Vert b-Ax{\Vert }^2$ over x; the optimal $\hat{b}=A\hat{x}$ is the projection of b onto $C(A)$.

12. Singular value decomposition (SVD)

Theorem (Eckart-Young-style statement; existence due to Beltrami 1873, Jordan 1874). Every $A\in {\mathbb{R}}^{m\times n}$ factorises as

$$A=U\Sigma V^{\top }$$

where:

• $U\in {\mathbb{R}}^{m\times m}$ is orthogonal; columns are left singular vectors.
• $V\in {\mathbb{R}}^{n\times n}$ is orthogonal; columns are right singular vectors.
• $\Sigma \in {\mathbb{R}}^{m\times n}$ is “diagonal” with nonnegative entries ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_{\min (m,n)}\ge 0$ — the singular values.

Connection to eigendecompositions. $A^{\top }A=V{\Sigma }^{\top }\Sigma V^{\top }$ — the right singular vectors are eigenvectors of $A^{\top }A$; singular values are square roots of its eigenvalues. Symmetrically, left singular vectors are eigenvectors of $A{A}^{\top }$.

Four subspaces from SVD. Let $r$ = number of nonzero singular values. Then:

• Columns 1..r of U = orthonormal basis of $C(A)$.
• Columns r+1..m of U = orthonormal basis of $N(A^{\top })$.
• Columns 1..r of V = orthonormal basis of $C(A^{\top })$.
• Columns r+1..n of V = orthonormal basis of $N(A)$.

The SVD produces orthonormal bases of all four fundamental subspaces simultaneously — this is its geometric punchline.

Computation

Practical SVD: bidiagonalise A by Householder reflections from both sides, then run a divide-and-conquer or QR-style iteration on the bidiagonal form. $O(\min (m{n}^2,m^{2}n))$ operations. LAPACK routines ?gesdd (divide-and-conquer) and ?gesvd (Golub-Reinsch) are the standard implementations. See numerical-linear-algebra for details; for truncated SVD on very large matrices, use randomised methods (Halko, Martinsson, Tropp 2011) or Lanczos bidiagonalisation.

Low-rank approximation (Eckart-Young 1936)

The best rank-k approximation to A in both Frobenius and spectral norm is

$$A_k=\sum _{i=1}^k{\sigma }_i{u}_i{v}_i^{\top }.$$

Errors:

• $\Vert A-A_k{\Vert }_F^2={\sum }_{i>k}{\sigma }_i^2$
• $\Vert A-A_k{\Vert }_2={\sigma }_{k+1}$

This is the only deterministic optimal low-rank approximation; PCA, latent semantic analysis, image compression, recommender systems all use it. See svd-pca-spectral for the application landscape.

Pseudoinverse (Moore 1920, Penrose 1955)

$$A^{+}=V{\Sigma }^{+}{U}^{\top },{\Sigma }^{+}=\mathrm{diag}(1/{\sigma }_1,\dots ,1/{\sigma }_r,0,\dots ,0)$$

The Moore-Penrose pseudoinverse generalises the inverse to rectangular and rank-deficient matrices. The minimum-norm least-squares solution to $Ax=b$ is $x^{\ast }=A^{+}b$. Characterised by four axioms: $A{A}^{+}A=A$, $A^{+}A{A}^{+}=A^{+}$, $(A{A}^{+}{)}^{\top }=A{A}^{+}$, $(A^{+}A{)}^{\top }=A^{+}A$.

13. Least squares

Problem. Given $A\in {\mathbb{R}}^{m\times n}$ (often $m>n$, overdetermined) and $b\in {\mathbb{R}}^m$, find x minimising $\Vert Ax-b{\Vert }_2$.

Normal equations. Setting $\nabla \Vert Ax-b{\Vert }^2=0$ gives $A^{\top }Ax=A^{\top }b$. If A has full column rank, $A^{\top }A$ is invertible and $\hat{x}=(A^{\top }A{)}^{-1}{A}^{\top }b$.

Geometric reading. $\hat{x}$ is the unique $x$ such that $A\hat{x}=P_{C(A)}b$ — the projection of b onto the column space of A. The residual $b-A\hat{x}$ is orthogonal to $C(A)$.

Numerical caveat. Never solve via normal equations when A is even moderately ill-conditioned: $\kappa (A^{\top }A)=\kappa (A{)}^2$, so you double the condition number’s penalty. Two stable alternatives:

• QR-based: $A=QR$, then solve $Rx=Q^{\top }b$ by back-substitution. $O(m{n}^2)$.
• SVD-based: $A=U\Sigma V^{\top }$, then $\hat{x}=V{\Sigma }^{+}{U}^{\top }b$. More expensive but exposes near-rank-deficiency and lets you regularise by truncating tiny singular values.

Regularised least squares (Tikhonov / ridge). Minimise $\Vert Ax-b{\Vert }^2+\lambda \Vert x{\Vert }^2$ for $\lambda >0$. Closed form: $\hat{x}=(A^{\top }A+\lambda I{)}^{-1}{A}^{\top }b$. Always well-posed regardless of $A$‘s rank.

14. Positive (semi)definite matrices and Cholesky

A symmetric $M\in {\mathbb{R}}^{n\times n}$ is positive definite (PD) iff $x^{\top }Mx>0$ for all $x\ne 0$, equivalently iff all eigenvalues are positive. Positive semidefinite (PSD) allows $x^{\top }Mx\ge 0$ and eigenvalues $\ge 0$.

Characterisations of PD M.

1. All eigenvalues positive.
2. All leading principal minors positive (Sylvester’s criterion).
3. $M=L{L}^{\top }$ for some invertible L with positive diagonal (Cholesky).
4. $M=B^{\top }B$ for some B with full column rank.
5. Quadratic form $x\mapsto x^{\top }Mx$ has a strict minimum at 0.

Where PD/PSD matrices appear.

• Covariance matrices — always PSD; PD iff data spans the full space.
• Hessians at minima — PD at strict local minima (and PSD generally).
• Gram matrices — $G_{ij}=⟨v_i,v_j⟩$ is PSD; PD iff $\{v_i\}$ linearly independent.
• Kernel matrices in ML — PSD by Mercer’s theorem.

Cholesky decomposition (Cholesky ca. 1910)

For PD $M$, the unique factorisation $M=L{L}^{\top }$ with L lower triangular, positive diagonal, can be computed in $O(n^3/3)$ operations — half the cost of LU. Algorithm: process columns left-to-right, computing $L_{jj}=\sqrt{M_{jj}-{\sum }_{k<j}{L}_{jk}^2}$ and $L_{ij}=(M_{ij}-{\sum }_{k<j}{L}_{ik}{L}_{jk})/L_{jj}$.

Used pervasively as:

• Cheapest way to solve $Mx=b$ when M is symmetric PD.
• Square root of a PSD matrix (in the lower-triangular sense; cf. the symmetric matrix square root $M^{1/2}$ from the eigendecomposition).
• Drawing samples from a multivariate Gaussian: $x=Lz+\mu$ with $z\sim N(0,I)$ gives $x\sim N(\mu ,M)$.
• Sequential Monte Carlo, Kalman filtering covariance updates (“square-root Kalman” forms).

15. Condition number and numerical stability

For an invertible $A\in {\mathbb{R}}^{n\times n}$ the condition number in the 2-norm is

$${\kappa }_2(A)=\Vert A{\Vert }_2\Vert A^{-1}{\Vert }_2={\sigma }_1/{\sigma }_n.$$

It governs the worst-case amplification of relative input error to relative output error when solving $Ax=b$:

$$\frac{\Vert \Delta x\Vert }{\Vert x\Vert }\le \kappa (A)\cdot \frac{\Vert \Delta b\Vert }{\Vert b\Vert }.$$

Rough rule of thumb: solving $Ax=b$ in IEEE double precision (machine epsilon $\approx 10^{-16}$) loses ${\log }_{10}(\kappa (A))$ digits. $\kappa \approx 10^{16}$ means you may have zero correct digits.

Forward vs backward stability. Modern algorithms (LU with partial pivoting, QR via Householder, Cholesky, SVD via Golub-Reinsch) are backward stable: the computed answer is the exact answer for a slightly perturbed input. Forward error then bounds by $\kappa (A)\cdot$ machine epsilon. See numerical-linear-algebra for the analysis.

Ill-conditioning is a property of the problem, not the algorithm. No clever algorithm can rescue badly conditioned data; you need to reformulate (regularise, change basis, drop redundant features).

16. Catalogue of matrix decompositions

Decomposition	Form	When it exists	Cost	Primary use
LU	$A=LU$ ($P$ for pivoting)	Square invertible	$O(\frac{2}{3}{n}^3)$	Solving linear systems
QR	$A=QR$	Any $A$	$O(2m{n}^2)$	Least squares, eigenvalue iteration
Cholesky	$A=L{L}^{\top }$	Symmetric PD	$O(\frac{1}{3}{n}^3)$	SPD systems, Gaussian sampling
LDL${}^{\top }$	$A=LD{L}^{\top }$	Symmetric (allowing indefinite)	$O(\frac{1}{3}{n}^3)$	Symmetric indefinite systems
Eigen (symmetric)	$A=Q\Lambda Q^{\top }$	Symmetric	$O(n^3)$	Spectral analysis, diagonalisation
Eigen (general)	$A=PJ{P}^{-1}$	Always (Jordan) over ℂ	$O(n^3)$	Theoretical; numerically use Schur
Schur	$A=QT{Q}^{\ast }$	Any square	$O(n^3)$	Practical eigenvalue extraction
SVD	$A=U\Sigma V^{\top }$	Any matrix	$O(\min (m{n}^2,m^{2}n))$	Rank, pseudoinverse, low-rank approx
Polar	$A=UP$ ($U$ orthogonal, $P$ PSD)	Square	$O(n^3)$	Procrustes, robotics rotation extraction
Hessenberg	$A=QH{Q}^{\ast }$ ($H$ upper Hessenberg)	Any	$O(\frac{10}{3}{n}^3)$	Pre-step for QR-algorithm eigenvalues
Bidiagonal	$A=UB{V}^{\top }$ ($B$ bidiagonal)	Any	$O(\frac{4}{3}{n}^3)$	Pre-step for SVD

For algorithmic detail see numerical-linear-algebra; for spectral applications see svd-pca-spectral and eigenvalue-problems.

17. Norms

A norm $\Vert \cdot \Vert :V\to [0,\infty )$ satisfies positivity, homogeneity, and the triangle inequality. Common vector norms on ℝⁿ:

• p-norms ($p\ge 1$): $\Vert x{\Vert }_p=({\sum }_i|x_i{|}^p{)}^{1/p}$.
  • $p=1$: Manhattan / Taxicab norm — sparsity-inducing in optimisation (LASSO).
  • $p=2$: Euclidean norm — the geometric default.
  • $p=\infty$: max norm $\Vert x{\Vert }_{\infty }={\max }_i|x_i|$.

Common matrix norms on ${\mathbb{R}}^{m\times n}$:

• Operator (induced) p-norms: $\Vert A{\Vert }_p={\sup }_{x\ne 0}\Vert Ax{\Vert }_p/\Vert x{\Vert }_p$.
  • $\Vert A{\Vert }_2={\sigma }_1$ (largest singular value).
  • $\Vert A{\Vert }_1={\max }_j{\sum }_i|a_{ij}|$ (max column sum).
  • $\Vert A{\Vert }_{\infty }={\max }_i{\sum }_j|a_{ij}|$ (max row sum).
• Frobenius norm: $\Vert A{\Vert }_F=\sqrt{{\sum }_{i,j}{a}_{ij}^2}=\sqrt{\mathrm{tr}(A^{\top }A)}=\sqrt{{\sum }_i{\sigma }_i^2}$.
• Nuclear norm (Schatten-1): $\Vert A{\Vert }_{\ast }={\sum }_i{\sigma }_i$. Used as a convex surrogate for rank in matrix completion.
• Schatten p-norms: $\Vert A{\Vert }_{S_p}=({\sum }_i{\sigma }_i^p{)}^{1/p}$. Generalises Frobenius ($p=2$), nuclear ($p=1$), spectral ($p=\infty$).

Equivalence of norms (finite-dimensional spaces). Any two norms $\Vert \cdot {\Vert }_a,\Vert \cdot {\Vert }_b$ on a finite-dimensional space satisfy $c\Vert x{\Vert }_a\le \Vert x{\Vert }_b\le C\Vert x{\Vert }_a$ for fixed constants. So they induce the same topology — convergence in one means convergence in all. In infinite-dimensional spaces this fails, and the choice of norm matters profoundly (see functional-analysis).

18. Special matrix classes

Class	Definition	Key property
Diagonal	$a_{ij}=0$ for $i\ne j$	Trivial algebra; $A^k$ entry-wise
Triangular	Zero above/below diagonal	Linear systems by back/forward substitution
Permutation	One 1 per row and column, else 0	Orthogonal, $P^{-1}=P^{\top }$
Orthogonal ($\mathbb{R}$)	$Q^{\top }Q=I$	Preserves Euclidean norm; columns orthonormal
Unitary ($\mathbb{C}$)	$U^{\ast }U=I$	Complex analogue of orthogonal
Symmetric	$A=A^{\top }$	Real spectrum; orthogonal eigenbasis
Skew-symmetric	$A=-A^{\top }$	Pure imaginary spectrum; exponential is orthogonal
Hermitian	$A=A^{\ast }$	Complex analogue of symmetric
Normal	$A{A}^{\ast }=A^{\ast }A$	Unitarily diagonalisable
Positive definite	$x^{\top }Ax>0$	All eigenvalues positive; Cholesky factor exists
Stochastic (row)	Rows nonneg, sum to 1	Largest eigenvalue is 1 (Perron-Frobenius)
Sparse	Most entries zero	Specialised storage and algorithms
Toeplitz	Constant along diagonals	FFT-accelerated multiplication
Circulant	Each row is rotated previous	Diagonal in Fourier basis
Hankel	Constant along anti-diagonals	Signal processing, system identification
Vandermonde	$V_{ij}=x_i^{j-1}$	Polynomial interpolation; often ill-conditioned
Hilbert	$H_{ij}=1/(i+j-1)$	Canonical ill-conditioned example
Hadamard	$\pm 1$ entries, orthogonal	Combinatorial designs, fast transforms
Tridiagonal	Nonzero only on main and adjacent diagonals	Thomas algorithm $O(n)$ solver
Banded	Nonzero in $k$-band around diagonal	Generalised Thomas

19. Block matrices and Schur complements

A block matrix

$$M=\left(\begin{array}{cc}A& B\\ C& D\end{array}\right)$$

with A invertible has Schur complement $S=D-C{A}^{-1}B$. Then

• $\det M=\det A\cdot \det S$.
• $M$ invertible iff S is.
• Inverse:

$$M^{-1}=\left(\begin{array}{cc}{A}^{-1}+A^{-1}B{S}^{-1}C{A}^{-1}& -A^{-1}B{S}^{-1}\\ -S^{-1}C{A}^{-1}& S^{-1}\end{array}\right)$$

Schur complements appear in: block LU decomposition; conditioning of multivariate Gaussians (the conditional covariance of $X_2\mid X_1$ is the Schur complement of ${\Sigma }_{11}$ in $\Sigma$); KKT systems in optimisation; and the Sherman-Morrison-Woodbury identity

$$(A+UCV{)}^{-1}=A^{-1}-A^{-1}U(C^{-1}+V{A}^{-1}U{)}^{-1}V{A}^{-1}$$

— invaluable when A is easy to invert and $UCV$ is a low-rank update (Kalman filter covariance updates, online learning, leave-one-out diagnostics).

20. Tensor extension — a one-paragraph pointer

Linear algebra deals with $V$ and $V\otimes V^{\ast }$ (vectors and matrices). Multilinear algebra generalises: a tensor of type $(p,q)$ is an element of $V^{\otimes p}\otimes (V^{\ast }{)}^{\otimes q}$, equivalently a multilinear map taking $p$ covectors and $q$ vectors to a scalar. Coordinates carry $p$ upper and $q$ lower indices; transformations between coordinate systems use the Jacobian and its inverse the appropriate number of times.

Tensors live everywhere: stress and strain in continuum mechanics (rank-2), the Riemann curvature tensor (rank-4) in general relativity, neural-network parameter banks (high-rank, but typically just multidimensional arrays without intrinsic linear-algebraic structure). Tensor decompositions (CP, Tucker, tensor-train) generalise SVD but have very different computational character — most are NP-hard in the worst case. See tensor-calculus for the index-notation, transformation-law treatment.

21. Key applications across the Compendium

• Optimisation — gradient and Hessian are linear-algebraic objects; convex problems’ KKT systems are linear; Newton’s method solves linear systems at each step. convex-optimization, gradient-descent-variants.
• Statistics + ML — OLS, ridge, PCA, GLMs, kernel methods, deep learning forward/backward passes all reduce to matrix operations. probability-and-statistics, bayesian-inference.
• PDEs — discretisation yields huge sparse linear systems; multigrid, Krylov methods, preconditioning. pde-methods, numerical-linear-algebra.
• Signal processing — DFT/FFT are unitary transforms; filtering is matrix-vector; system identification is rank decomposition. fft-spectral.
• Robotics — SO(3), SE(3) are matrix Lie groups; Jacobians are linear maps between tangent spaces. lie-groups-so3-se3.
• Networks — adjacency and Laplacian spectra drive PageRank, spectral clustering, expander graphs. graph-theory.
• Quantum — observables are Hermitian operators on Hilbert spaces; gates are unitary matrices.
• Coding theory — linear codes are subspaces over finite fields; generator and parity-check matrices.

22. Pitfalls and folklore

• Never invert a matrix to solve $Ax=b$. Use LU/QR/Cholesky on the system directly; explicit $A^{-1}$ is rarely needed and always less accurate.
• Avoid normal equations for ill-conditioned least squares. Use QR or SVD.
• Cholesky over LU for SPD problems — half the work, more numerically robust.
• The Jordan form is not for computation. Use Schur form instead.
• Single precision can be enough if your problem is well-conditioned and you’re OK with ~$10^{-6}$ accuracy; many ML training runs successfully use bf16 or fp16. Conditioning is the deciding factor.
• det A’s magnitude is not a useful “near-singular” diagnostic — a well-conditioned matrix can have $\det \approx 0$ (e.g. $\mathrm{diag}(10^{-3},10^{-3},\dots )$). Use the condition number or the smallest singular value.
• Block-matrix tricks beat brute force in many problems with low-rank structure; learn Woodbury, Schur complements, and matrix-determinant lemma early.
• Eigen-decomposition is not unique when eigenvalues coincide — eigenvectors within a degenerate eigenspace can be rotated arbitrarily. Numerical algorithms return some basis; do not interpret individual eigenvector entries as physically meaningful in degenerate cases.

23. Originators and key references

• Cayley (1858), Sylvester (1850s) — matrix algebra named and formalised.
• Jordan (1870) — Jordan canonical form.
• Frobenius (1870s-90s) — matrix theory, characteristic polynomial, rank, normal forms.
• Beltrami (1873), Jordan (1874), Sylvester (1889), Autonne (1915) — independent derivations of SVD.
• Schmidt (1907), Gram (earlier) — Gram-Schmidt orthogonalisation.
• Cholesky (ca. 1910, published 1924 posthumously by Benoît) — Cholesky decomposition.
• Moore (1920), Penrose (1955) — pseudoinverse.
• Eckart-Young (1936) — optimal low-rank approximation theorem.
• Wilkinson (1965), Golub + Van Loan (1983, 1989, 1996, 2013) — modern numerical linear algebra.
• Strang (1976 onward) — the four-subspace pedagogy and MIT 18.06.
• Trefethen + Bau (1997) — Numerical Linear Algebra, the modern textbook.

24. Further reading

• Strang, Introduction to Linear Algebra (6th ed.) — the standard undergraduate text emphasising the four-subspace picture.
• Axler, Linear Algebra Done Right (4th ed.) — finite-dimensional theory without determinants; clean and proof-oriented.
• Trefethen + Bau, Numerical Linear Algebra (1997) — the practitioner’s bible. 40 short, dense lectures.
• Golub + Van Loan, Matrix Computations (4th ed.) — the encyclopaedic reference.
• Horn + Johnson, Matrix Analysis (2nd ed.) — exhaustive theoretical reference.
• Boyd + Vandenberghe, Introduction to Applied Linear Algebra (2018) — modern data-and-vectors-first treatment.

25. Companion notes in this library

• linear-algebra-essentials — operational, computational hands-on.
• numerical-linear-algebra — algorithms and stability.
• svd-pca-spectral — SVD, PCA, spectral methods.
• eigenvalue-problems — solvers, Krylov methods, perturbation.
• tensor-calculus — multilinear extensions.
• functional-analysis — infinite-dimensional linear algebra.
• group-theory-and-representation — symmetry via linear actions.
• lie-groups-so3-se3 — matrix Lie groups for robotics.
• convex-optimization — quadratic forms, KKT, duality.
• probability-and-statistics — covariance, regression, multivariate Gaussians.