Matrices & Determinants
Learning Objectives
- Understand the fundamental concepts of Matrices & Determinants
- Apply key formulas and techniques to solve problems
- Practice with exam-level questions to build speed and accuracy
Introduction to Matrices and Basic Operations
1.1 Definition and Notation
A matrix is a rectangular array of numbers arranged in rows and columns, and it serves as a compact way to represent linear transformations and systems of linear equations. The size of a matrix is described by its order m × n, where m denotes the number of rows and n the number of columns; for example, a 3 × 2 matrix has three rows and two columns. Individual entries are denoted by aij, where the first subscript indicates the row and the second the column. Two matrices are equal only when they have the same order and each corresponding entry is identical, a fact that underpins every algebraic manipulation that follows.
1.2 Addition, Subtraction and Scalar Multiplication
Matrix addition and subtraction are defined entry‑wise and therefore require the operands to share the same order; the result is a matrix of that order whose each element is the sum or difference of the corresponding elements. Scalar multiplication multiplies every entry of a matrix by a constant k, producing a matrix of the same order. These operations satisfy the familiar commutative, associative and distributive laws, which means that the set of all m × n matrices over a field forms a vector space. The zero matrix, whose every entry is zero, acts as the additive identity, and the additive inverse of a matrix A is simply –A, obtained by multiplying each entry by –1.
1.3 Matrix Multiplication
Unlike addition, matrix multiplication is not defined entry‑wise; the product AB of an m × p matrix A and a p × n matrix B is an m × n matrix whose (i, j) entry equals the sum over k = 1 to p of aik bkj. This definition captures the composition of linear maps, which explains why multiplication is associative but generally not commutative; AB ≠ BA in most cases, and the order of factors matters critically when solving equations. The identity matrix In of order n has ones on the main diagonal and zeros elsewhere, and it satisfies AI = IA = A for any compatible square matrix A. The transpose of a matrix A, denoted AT, interchanges rows and columns, and it obeys (AB)T = BTAT, a property frequently used in proofs involving symmetric and orthogonal matrices.
Determinants and Their Properties
2.1 Definition of the Determinant
The determinant is a scalar value associated with a square matrix that encodes important geometric and algebraic information, such as whether the matrix is invertible and the volume scaling factor of the linear transformation it represents. For a 1 × 1 matrix [a] the determinant is simply a. For a 2 × 2 matrix [[a, b], [c, d]] the determinant is ad – bc. For higher orders the determinant can be defined recursively by cofactor expansion along any row or column: det(A) = Σj=1n (–1)i+j aij det(Mij), where Mij is the (n–1) × (n–1) submatrix obtained by deleting row i and column j. This Laplace expansion shows that the determinant is a multilinear alternating function of the rows (or columns).
2.2 Elementary Row Operations and Determinant Behaviour
Elementary row operations affect the determinant in predictable ways: swapping two rows multiplies the determinant by –1; multiplying a row by a non‑zero scalar k multiplies the determinant by k; adding a multiple of one row to another leaves the determinant unchanged. These rules allow the determinant to be computed efficiently by reducing the matrix to upper triangular form, where the determinant equals the product of the diagonal entries. Because the determinant of a triangular matrix is the product of its diagonal elements, the computation becomes straightforward once the matrix is in echelon form, and the sign changes from row swaps are tracked separately.
2.3 Important Properties and Theorems
Several fundamental theorems govern determinants. The determinant of a product equals the product of the determinants: det(AB) = det(A) det(B). Consequently, a square matrix is invertible if and only if its determinant is non‑zero. The determinant of the transpose equals the determinant of the original matrix: det(AT) = det(A). For a scalar k and an n × n matrix A, det(kA) = kn det(A). The adjugate matrix, denoted adj(A), satisfies A adj(A) = adj(A) A = det(A) I, linking determinants directly to inverses. Cramer's rule expresses the solution of a linear system AX = B in terms of determinants, provided det(A) ≠ 0, giving xi = det(Ai) / det(A) where Ai is A with its i‑th column replaced by B.
Adjoint, Inverse and Rank of a Matrix
3.1 Adjoint and the Formula for the Inverse
The adjoint (or adjugate) of a square matrix A is the transpose of its cofactor matrix; each cofactor Cij equals (–1)i+j det(Mij). The defining relation A adj(A) = adj(A) A = det(A) I holds for every square matrix. If det(A) ≠ 0, the inverse exists and is given by A–1 = (1/det(A)) adj(A). This formula is theoretically important because it expresses the inverse entirely in terms of determinants, but for numerical computation it is usually less efficient than Gaussian elimination, especially for large matrices.
3.2 Properties of the Inverse
The inverse of a product reverses the order: (AB)–1 = B–1A–1. The inverse of the transpose is the transpose of the inverse: (AT)–1 = (A–1)T. If A is invertible, then (A–1)–1 = A. For a non‑zero scalar k, (kA)–1 = (1/k) A–1. These identities are frequently used to simplify expressions involving multiple inverses and transposes, and they also underlie the proof that the set of invertible n × n matrices forms the general linear group GL(n).
3.3 Rank and Its Determination
The rank of a matrix is the maximum number of linearly independent rows (or columns); it equals the order of the largest non‑zero minor. Row‑equivalence preserves rank, so the rank can be found by reducing the matrix to row‑echelon form and counting the non‑zero rows. The rank–nullity theorem states that for an m × n matrix A, rank(A) + nullity(A) = n, where nullity is the dimension of the solution space of AX = 0. A square matrix is invertible precisely when its rank equals its order, which is equivalent to having a non‑zero determinant. Rank also determines the consistency of a linear system: the system AX = B is consistent iff rank(A) = rank([A|B]), where [A|B] is the augmented matrix.
Solution of Systems of Linear Equations
4.1 Gaussian Elimination and Row‑Echelon Form
Gaussian elimination systematically applies elementary row operations to transform the augmented matrix [A|B] into row‑echelon form, from which the solutions can be read by back‑substitution. The process proceeds column by column, selecting a pivot (a non‑zero entry) and using it to eliminate entries below. If a column lacks a pivot, the corresponding variable is free, leading to infinitely many solutions parameterised by the free variables. The algorithm terminates when all rows are processed; the resulting triangular system is straightforward to solve. The method works for any rectangular system and reveals the rank of the coefficient matrix simultaneously.
4.2 Gauss‑Jordan Elimination and Reduced Row‑Echelon Form
Gauss‑Jordan elimination continues the reduction until the matrix reaches reduced row‑echelon form, where each pivot is 1 and is the only non‑zero entry in its column. This form yields the solution directly without back‑substitution and also provides a basis for the null space of A. The reduced form is unique for a given matrix, which makes it a canonical representation useful for theoretical arguments. While Gauss‑Jordan requires more arithmetic operations than Gaussian elimination, it is often preferred when the inverse of a matrix is needed, because augmenting A with the identity and reducing to [I|A–1] produces the inverse in one pass.
4.3 Cramer's Rule, Matrix Inversion and Comparative Efficiency
Cramer's rule gives an explicit formula for each variable as a ratio of determinants, but it requires the computation of n+1 determinants of order n, which is computationally prohibitive for n > 3. Matrix inversion solves AX = B by computing X = A–1B, which is efficient when the same coefficient matrix is used with many different right‑hand sides, because the inverse (or an LU factorisation) can be reused. For a single system, Gaussian elimination is generally the method of choice due to its O(n³) complexity with a smaller constant factor. Understanding the trade‑offs among these methods is essential for selecting the appropriate technique in both theoretical problems and numerical implementations.
| Method | Complexity (asymptotic) | Best Use Case | Limitations |
|---|---|---|---|
| Gaussian Elimination | O(n³) | Single system, general matrices | Requires back‑substitution |
| Gauss‑Jordan Elimination | O(n³) with larger constant | Finding inverse, multiple RHS | More arithmetic than Gaussian |
| Cramer's Rule | O(n·n!) (determinant expansion) | Small n (≤3), symbolic parameters | Impractical for large n |
| Matrix Inversion (via LU) | O(n³) for factorisation, O(n²) per RHS | Repeated solves with same A | Inverse may be ill‑conditioned |
Applications and Special Types of Matrices
5.1 Symmetric, Skew‑Symmetric and Orthogonal Matrices
A symmetric matrix satisfies A = AT; its eigenvalues are real and it can be orthogonally diagonalised by the spectral theorem. A skew‑symmetric matrix satisfies A = –AT; its diagonal entries are zero and its non‑zero eigenvalues occur in pure imaginary conjugate pairs. An orthogonal matrix Q fulfills QTQ = QQT = I, so its inverse equals its transpose; orthogonal matrices preserve lengths and angles, making them central to rotations and reflections in Euclidean space. The determinant of an orthogonal matrix is either +1 (proper rotation) or –1 (improper rotation including a reflection).
5.2 Diagonal, Triangular and Block Matrices
A diagonal matrix has non‑zero entries only on the main diagonal; its determinant is the product of the diagonal entries, and its inverse (when it exists) is obtained by inverting each diagonal entry. Upper (or lower) triangular matrices have zeros below (or above) the diagonal; their determinants are likewise the product of diagonal entries, and they are easily inverted by forward or backward substitution. Block matrices partition a large matrix into submatrices; operations such as multiplication and inversion can sometimes be performed block‑wise, provided the blocks are conformable and certain submatrices are invertible. The Schur complement arises naturally in block inversion and is a powerful tool in numerical linear algebra and statistics.
5.3 Eigenvalues, Eigenvectors and Diagonalisation
An eigenvalue λ of a square matrix A is a scalar for which there exists a non‑zero vector v (the eigenvector) satisfying Av = λv. The characteristic polynomial det(A – λI) = 0 yields the eigenvalues; its degree equals the order of the matrix. A matrix is diagonalisable if it possesses a basis of eigenvectors, which is guaranteed when it has n distinct eigenvalues or, more generally, when the algebraic multiplicity of each eigenvalue equals its geometric multiplicity. Diagonalisation simplifies many computations: powers of A become Ak = PDkP–1, where D is the diagonal matrix of eigenvalues and P the matrix of eigenvectors. This property underlies the solution of linear differential equations, Markov chains, and principal component analysis.
| Class | Defining Condition | Determinant | Inverse | Typical Eigenvalues |
|---|---|---|---|---|
| Symmetric | A = AT | Real, product of eigenvalues | Exists iff no zero eigenvalue | All real |
| Skew‑Symmetric | A = –AT | Zero for odd order; square of Pfaffian for even | Exists iff order even and Pfaffian ≠ 0 | Pure imaginary pairs, zero |
| Orthogonal | QTQ = I | ±1 | Q–1 = QT | Complex numbers of modulus 1 |
| Diagonal | aij=0 for i≠j | Product of diagonal entries | Diagonal of reciprocals (if non‑zero) | Diagonal entries themselves |
Mastery of matrices and determinants equips a student to tackle a wide spectrum of problems in algebra, geometry, physics and engineering, because these objects encode linear relationships in a form that is both conceptually clear and computationally tractable.
LU Decomposition and Its Variants
LU decomposition factorises a square matrix A into the product of a lower‑triangular matrix L (with unit diagonal) and an upper‑triangular matrix U, i.e. A = LU. The factorisation exists uniquely when all leading principal minors of A are non‑zero; otherwise row permutations are required, giving the PA = LU form where P is a permutation matrix. The algorithm proceeds by Gaussian elimination without back‑substitution, storing the multipliers in L and the resulting upper triangle in U. Computational cost is O(n³) with a smaller constant than full Gauss‑Jordan, making LU the workhorse for solving multiple right‑hand sides AX = B.
Doolittle, Crout and Cholesky Variants
In the Doolittle scheme L has unit diagonal; in Crout the diagonal resides in U. Both are algebraically equivalent but differ in numerical stability when pivoting is omitted. For symmetric positive‑definite matrices the Cholesky factorisation A = LLᵀ (or A = UᵀU) halves the arithmetic and guarantees stability without pivoting because all pivots are positive. The Cholesky factor L is obtained by the recurrence lii = √(aii − Σk<i lik²) and lji = (aji − Σk<i ljklik) / lii for j > i.
Block LU and Sparse Implementations
Large sparse systems exploit block LU where the matrix is partitioned into sub‑blocks; the Schur complement of the leading block appears naturally and can be factorised recursively. Modern sparse direct solvers (e.g. multifrontal methods) combine symbolic analysis to predict fill‑in with numerical factorisation, preserving sparsity patterns. Incomplete LU (ILU) preconditioners drop small entries during factorisation to keep the factors sparse, trading exactness for memory efficiency in iterative solvers.
| Variant | Diagonal Placement | Pivoting Requirement | Typical Use |
|---|---|---|---|
| Doolittle | Unit diagonal in L | Partial pivoting (PA=LU) | General dense matrices |
| Crout | Unit diagonal in U | Partial pivoting | General dense matrices |
| Cholesky | L = Lᵀ, positive diagonal | None (SPD guarantee) | Symmetric positive‑definite |
| Block LU | Block‑wise | Block pivoting | Large sparse / parallel |
QR Decomposition and Least Squares
The QR decomposition writes an m × n matrix A (with m ≥ n) as A = QR, where Q is m × m orthogonal (QᵀQ = I) and R is m × n upper‑triangular (the bottom m−n rows are zero). Two numerically stable constructions dominate: Householder reflections and Givens rotations. Householder reduces a column to a multiple of the first basis vector by reflecting across a hyperplane; the product of n such reflectors yields Q. Givens rotates a pair of rows to zero a single entry, useful for sparse or banded matrices.
Solving Linear Least Squares
For an overdetermined system Ax ≈ b, the normal equations AᵀAx = Aᵀb square the condition number. QR avoids this: substitute A = QR to obtain Rx = Qᵀb (using the first n rows of Qᵀb). Since R is triangular, back‑substitution gives the minimum‑norm solution in O(mn²) operations with excellent stability. If A is rank‑deficient, the rank‑revealing QR (with column pivoting) produces AP = QR where the diagonal of R decays, allowing a truncated solution.
Economy‑Size QR and Updating
When only the first n columns of Q are needed, the economy QR stores Q₁ (m × n) and R (n × n), reducing memory. Rank‑one updates (adding a row or column) can be performed in O(n²) using Givens rotations on the existing factors, a key ingredient in recursive least squares and Kalman filtering.
Step 1: First column a₁ = [1,3,5]ᵀ. Compute v = a₁ − ||a₁|| e₁ = [1,3,5]ᵀ − √35 [1,0,0]ᵀ = [1−√35, 3, 5]ᵀ. Normalise u = v/||v||. Householder H₁ = I − 2uuᵀ. Apply H₁A → first column becomes [√35, 0, 0]ᵀ, second column becomes some vector c.
Step 2: Work on submatrix rows 2‑3, column 2. Let c₂ be the 2‑vector from rows 2‑3 of column 2. Build 2×2 Householder H₂' to zero its second entry. Embed into 3×3 as H₂ = diag(1, H₂'). Then Q = H₁H₂, R = H₂H₁A.
Numerically: ||a₁|| = √35 ≈ 5.91608. v = [−4.91608, 3, 5]ᵀ, ||v|| ≈ 7.54983. u ≈ [−0.651, 0.397, 0.662]ᵀ. H₁A yields R₁₁ = 5.91608, R₁₂ ≈ 10.141. Submatrix column 2 rows 2‑3 ≈ [−0.828, −1.656]ᵀ. Its norm ≈ 1.851. Householder gives R₂₂ ≈ 1.851, R₂₃ = 0. Thus R = [[5.916, 10.141], [0, 1.851], [0, 0]].
Compute Qᵀb: Qᵀ = H₂H₁. Applying to b = [7,8,9]ᵀ gives y = Qᵀb ≈ [15.652, −0.540, 0.0]ᵀ. Solve Rx = y₁:₂ → 5.916 x₁ + 10.141 x₂ = 15.652; 1.851 x₂ = −0.540 → x₂ ≈ −0.292, x₁ ≈ (15.652 − 10.141(−0.292))/5.916 ≈ 3.148. Least‑squares solution x ≈ [3.148, −0.292]ᵀ.
Singular Value Decomposition and Applications
The singular value decomposition (SVD) factorises any real m × n matrix A as A = UΣVᵀ, where U (m × m) and V (n × n) are orthogonal, and Σ (m × n) is diagonal with non‑negative singular values σ₁ ≥ σ₂ ≥ … ≥ σr > 0 (r = rank(A)). The columns of U are left singular vectors (eigenvectors of AAᵀ), columns of V are right singular vectors (eigenvectors of AᵀA), and σi² are the common non‑zero eigenvalues. SVD exists for every matrix, unlike eigendecomposition which requires square and diagonalizable matrices.
Low‑Rank Approximation and Eckart‑Young Theorem
The best rank‑k approximation (in both Frobenius and spectral norms) is obtained by truncating Σ to its first k singular values and corresponding singular vectors: Ak = UkΣkVkᵀ. The approximation error equals σk+1 (spectral) or √(Σi>k σi²) (Frobenius). This underpins principal component analysis (PCA), image compression, and latent semantic indexing.
Pseudoinverse and Least Squares via SVD
The Moore‑Penrose pseudoinverse A⁺ = VΣ⁺Uᵀ, where Σ⁺ replaces each non‑zero σi by 1/σi and transposes the shape. The minimum‑norm least‑squares solution of Ax = b is x = A⁺b. SVD reveals the condition number κ = σ₁/σr; a large κ warns of numerical sensitivity. Regularised solutions (Tikhonov) replace 1/σi by σi/(σi²+λ²).
Computational Aspects
Full SVD costs O(mn²) (or O(n³) for square) via bidiagonalisation followed by QR iteration on the bidiagonal matrix. For large sparse matrices, randomised SVD or Lanczos bidiagonalisation compute only the leading singular triplets in O(mn log k) time.
Positive Definite Matrices, Cholesky Decomposition and Quadratic Forms
A symmetric matrix A is positive definite (PD) iff xᵀAx > 0 for all non‑zero x. Equivalent characterisations: all eigenvalues > 0; all leading principal minors > 0 (Sylvester’s criterion); there exists a non‑singular B with A = BᵀB. Positive semidefinite (PSD) relaxes strict inequality to ≥ 0, allowing zero eigenvalues.
Cholesky Factorisation
For PD A, the unique Cholesky factor L (lower‑triangular with positive diagonal) satisfies A = LLᵀ. The algorithm computes lii = √(aii − Σk<i lik²) and lji = (aji − Σk<i ljklik) / lii. Cost is ⅓ n³ flops, half of LU. Cholesky fails (square‑root of negative) if A is not PD, providing a practical test.
Quadratic Forms and Sylvester’s Law of Inertia
A quadratic form q(x) = xᵀAx can be diagonalised by an orthogonal change of variables x = Py giving q = Σ λi yi². Sylvester’s law states that the numbers of positive, negative, and zero eigenvalues (the inertia) are invariant under any non‑singular congruence transformation A → CᵀAC. This classifies conics and quadrics: PD → ellipsoid, indefinite → hyperboloid, PSD → paraboloid/cylinder.
Applications in Optimisation and Statistics
In Newton’s method, the Hessian must be PD for a descent direction; if indefinite, a modified Cholesky (adding a multiple of identity) yields a PD approximation. In statistics, covariance matrices are PSD; their Cholesky factors generate correlated random vectors via x = Lz with z ∼ N(0,I). The Mahalanobis distance d² = (x−μ)ᵀΣ⁻¹(x−μ) uses the inverse covariance, efficiently computed via Cholesky solves.
Matrix Exponential and Linear Differential Equations
The matrix exponential is defined by the convergent power series eA = Σk=0∞ Ak/k! for any square A. It satisfies d/dt etA = A etA = etA A and e0 = I. For a constant‑coefficient linear system dx/dt = Ax, the solution is x(t) = etA x(0). If A is diagonalizable (A = PDP⁻¹), then eA = P eD P⁻¹ where eD is diagonal with entries eλi.
Computing the Exponential
Direct series summation is rarely used. For small matrices, scaling and squaring combined with Padé approximants (the “expm” algorithm) is standard. For large sparse systems, Krylov subspace methods (Arnoldi) approximate etAv without forming the full exponential. When A is nilpotent (Ak=0), the series terminates after k terms.
General Solution of Inhomogeneous Systems
For dx/dt = Ax + f(t), variation of parameters gives x(t) = etA x(0) + ∫0t e(t−s)A f(s) ds. If f(t) is a polynomial, exponential, or sinusoid, the integral can be evaluated analytically using the matrix exponential or by augmenting the system.
Stability and Lyapunov Exponents
The zero solution of dx/dt = Ax is asymptotically stable iff all eigenvalues of A have negative real parts. The matrix exponential norm ‖etA‖ decays exponentially at rate equal to the spectral abscissa max Re(λi). For discrete‑time xk+1 = Axk, stability requires ρ(A) < 1 (spectral radius). These criteria are central in control theory and numerical analysis of stiff ODEs.
- Confusing LU with Cholesky: Cholesky requires symmetric positive‑definite matrices; applying it to indefinite matrices produces a square‑root of a negative pivot.
- Assuming QR always yields a square Q: economy QR returns Q₁ (m×n) and R (n×n); the full Q is m×m and often unnecessary.
- Treating singular values as eigenvalues: singular values are square roots of eigenvalues of AᵀA (or AAᵀ) and are always non‑negative, whereas eigenvalues can be negative or complex.
- Using normal equations for least squares without checking condition number: squaring the condition number amplifies rounding errors; QR or SVD is safer.
- Believing every matrix has a matrix logarithm: only non‑singular matrices with no eigenvalues on the negative real axis (principal logarithm) admit a real logarithm; otherwise complex branches appear.
- Neglecting the inertia when classifying quadratic forms: congruence transformations preserve the numbers of positive, negative, and zero eigenvalues, not the eigenvalues themselves.
- Overlooking that the matrix exponential of a non‑diagonalizable matrix involves Jordan blocks and polynomial factors in t, not just exponentials of eigenvalues.
These advanced topics extend the core toolkit and appear frequently in higher‑level problem papers and research‑oriented examinations.