Matrix Decompositions and Spectral Methods

Introduction and Context

Matrices provide the central language for representing structured data, linear transformations, systems of equations and statistical relationships. In data science, a data matrix may contain observations by variables, an image may be represented as a matrix of pixel intensities, and a recommender system may store user–item interactions in a sparse matrix. Matrix decompositions rewrite a matrix as a product of simpler matrices. This often exposes hidden structure, reduces computational cost and improves numerical stability.

Spectral methods are based primarily on eigenvalues and eigenvectors. They are useful when the geometry of a problem is determined by a symmetric matrix, such as a covariance matrix, a graph Laplacian or a kernel matrix. Singular value decomposition extends these ideas to every real or complex matrix and is especially important for dimensionality reduction, latent-factor modelling, information retrieval and recommendation systems.

This chapter develops determinants, eigen-analysis, positive-definite matrices, eigendecomposition, singular value decomposition (SVD), pseudoinverses and their practical use in postgraduate data science.

Learning Objectives

By the end of this chapter, you should be able to:

1. Interpret determinants, eigenvalues and eigenvectors geometrically and algebraically.
2. Distinguish positive-definite, positive-semidefinite and indefinite matrices.
3. Compute and interpret eigendecompositions of suitable matrices.
4. Explain and use the singular value decomposition.
5. Construct the Moore–Penrose pseudoinverse and solve least-squares problems.
6. Apply spectral methods to principal component analysis, latent-factor models and recommendation.
7. Evaluate approximation error, rank selection and numerical conditioning.
8. Identify limitations, modelling risks and responsible-use issues in spectral methods.

1. Matrix Foundations for Data Science

A matrix A ∈ ℝ^m×n is a rectangular array with m rows and n columns. Its element in row i and column j is written a_ij. A vector is a matrix with one column or one row. Matrix multiplication AB is defined when the number of columns of A equals the number of rows of B.

The transpose A^T interchanges rows and columns. A square matrix is symmetric if A = A^T. The identity matrix I_n has ones on its main diagonal and zeros elsewhere. A matrix is invertible if there exists A^-1 such that AA^-1 = A^-1A = I. Inversion is defined only for square, nonsingular matrices; in data science it is usually preferable to solve systems directly rather than explicitly forming an inverse.

Determinants

The determinant is a scalar defined for a square matrix. For a 2 × 2 matrix,

For an n×n matrix, the determinant can be defined recursively by cofactor expansion, although numerical software generally uses factorisation-based algorithms. Important properties include:

• det(AB) = det(A)det(B).
• det(A^T) = det(A).
• A is invertible if and only if det(A) ≠ 0.
• Multiplying a matrix by a scalar c gives det(cA) = cⁿ det(A) for an n×n matrix.

Geometrically, the absolute determinant is the factor by which the linear transformation changes volume. A negative determinant also reverses orientation. In statistical modelling, determinants appear in multivariate Gaussian densities and covariance-volume calculations. However, a determinant close to zero is not by itself a reliable numerical measure of instability, because its scale depends strongly on matrix dimension and units. The condition number is usually more informative.

2. Eigenvalues and Eigenvectors

For a square matrix A ∈ ℝ^n×n, a nonzero vector v is an eigenvector with eigenvalue λ if

Thus, the transformation A changes the length and possibly direction of v but does not rotate it to a different line. Rearranging gives

A nonzero solution exists only when A − λI is singular:

This equation is the characteristic equation. Its roots are the eigenvalues. The eigenspace associated with λ is the null space of A − λI. Algebraic multiplicity counts how many times an eigenvalue occurs as a root; geometric multiplicity is the dimension of its eigenspace. A matrix is diagonalizable when it has a basis of eigenvectors. Repeated eigenvalues do not automatically prevent diagonalization.

For a real symmetric matrix, the spectral theorem guarantees an orthonormal eigenbasis. Therefore,

where Q is orthogonal, Q^TQ = I, and Λ is diagonal with real eigenvalues. This decomposition is central in covariance analysis and PCA.

Worked Example: A Symmetric Matrix

Consider

The characteristic polynomial is

The eigenvalues are λ₁ = 3 and λ₂ = 1. For λ₁ = 3, an eigenvector is (1,1)^T; its unit version is q₁ = (1/√2)(1,1)^T. For λ₂ = 1, an eigenvector is (1,−1)^T; its unit version is q₂ = (1/√2)(1,−1)^T. Hence Q = [q₁\ q₂] is orthogonal and Λ = diag(3,1). The direction q₁ is stretched by a factor of 3, while q₂ is stretched by a factor of 1.

For a general nonsymmetric matrix, eigenvalues may be complex, eigenvectors need not be orthogonal and a complete eigenbasis may not exist. Consequently, eigendecomposition is not the universal factorisation for data matrices; SVD is.

3. Positive-Definite Matrices

A real symmetric matrix A is positive definite (PD) if

It is positive semidefinite (PSD) if x^TAx ≥ 0 for every x. A symmetric matrix is PD exactly when all its eigenvalues are strictly positive; it is PSD exactly when all eigenvalues are nonnegative.

Equivalent tests for a real symmetric matrix include:

• PD if and only if all eigenvalues are positive.
• PD if and only if all leading principal minors are positive (Sylvester’s criterion).
• PD if and only if it has a Cholesky factorisation A = LL^T, where L is lower triangular with positive diagonal entries.

Positive-definite matrices define inner products and ellipsoidal quadratic forms. If Σ is a covariance matrix, positive semidefiniteness is required because variances of all linear combinations must be nonnegative:

A covariance matrix is often singular when variables are linearly dependent. Adding a small ridge term αI, with α > 0, produces Σ + αI, which is positive definite when Σ is PSD. This is regularisation, not a claim that the original covariance structure was nonsingular.

4. Spectral Geometry and Quadratic Forms

If a symmetric matrix has eigendecomposition A = QΛQ^T, define y = Q^Tx. Since Q is orthogonal,

This expression makes definiteness transparent. It also shows that the eigenvectors provide principal directions of the quadratic form, while eigenvalues determine curvature or scale along those directions.

The spectral norm of a symmetric matrix is the largest absolute eigenvalue. For a PSD matrix it is simply the largest eigenvalue. The trace equals the sum of eigenvalues:

The determinant equals their product:

These identities apply to square matrices and are particularly useful for covariance matrices: the trace is total variance, while the determinant is proportional to squared volume of the covariance ellipsoid.

5. Singular Value Decomposition

For every real matrix A ∈ ℝ^m×n, there exist orthogonal matrices U ∈ ℝ^m×m and V ∈ ℝ^n×n and a rectangular diagonal matrix Σ such that

The diagonal entries σ₁ ≥ σ₂ ≥ … ≥ σ_r ≥ 0 are the singular values, where r = rank(A). The columns of U are left singular vectors and those of V are right singular vectors. A compact SVD retains only the nonzero singular directions:

The singular values satisfy

Thus, right singular vectors are eigenvectors of A^TA, and left singular vectors are eigenvectors of AA^T. Unlike direct eigendecomposition, SVD is defined for rectangular, rank-deficient and nonsymmetric matrices. It is also numerically more reliable than explicitly forming A^TA, which squares the condition number.

Geometric Interpretation

For a unit vector v_i,

The matrix maps orthogonal input directions v_i to orthogonal output directions u_i, scaling them by σ_i. The image of the unit sphere is an ellipsoid whose semiaxis lengths are the singular values. Zero singular values correspond to directions lost by the transformation.

Eckart–Young Optimality

The best rank-k approximation to A in both the Frobenius norm and the spectral norm is obtained by truncating its SVD:

For the Frobenius norm,

where ||A||_F = √(∑_i,ja_ij²). The spectral-norm error is ||A − A_k||₂ = σ_k+1. These results assume an exact mathematical SVD; practical data also require a judgement about noise, scale and interpretability.

6. Principal Component Analysis

Suppose X ∈ ℝ^n×p contains n observations and p variables. PCA normally begins by centring each column:

where μ is the vector of column means and 1_n is an n-element vector of ones. Scaling to unit variance may also be appropriate when variables have different units or vastly different variances.

The sample covariance matrix is

PCA finds eigenvectors of S. Equivalently, if

then the columns of V are principal directions and the principal scores are Z = X_cV. The variance of component i is

The explained-variance ratio of the first k components is

PCA is an unsupervised linear method. It maximises variance, not predictive accuracy, fairness or causal relevance. Components are identifiable only up to sign: v and −v represent the same axis. With repeated eigenvalues, the individual directions within the repeated subspace are not uniquely identified.

Choosing the Number of Components

Common approaches include a target explained-variance threshold, a scree plot, cross-validation for downstream performance, information criteria and domain constraints. Retaining 95% of variance is not universally optimal: low-variance variables may be important for prediction, and high-variance directions may reflect measurement scale or nuisance variation.

7. Pseudoinverses and Least Squares

When A is rectangular or singular, an ordinary inverse does not exist. The Moore–Penrose pseudoinverse A^+ is defined uniquely by the four conditions:

If A = UΣV^T, then

where Σ^+ is formed by transposing Σ and replacing each nonzero singular value σ_i with 1/σ_i. Singular values equal to zero remain zero.

For an overdetermined system Ax ≈ b, the least-squares solution minimises

The minimum-norm least-squares solution is

If A has full column rank, this reduces algebraically to

but this normal-equation expression should generally not be computed literally because it can worsen numerical conditioning. QR or SVD-based solvers are preferred.

For an underdetermined system with infinitely many solutions, A^+b is the solution with minimum Euclidean norm. The matrix AA^+ projects onto the column space of A, while A^+A projects onto its row space.

Numerical Stability and Conditioning

The 2-norm condition number of a nonzero matrix is

where σ_min is the smallest nonzero singular value for a full-rank problem. A large condition number means that small input or rounding errors can cause large changes in the solution. If σ_min = 0, the matrix is rank-deficient and the condition number is infinite.

The normal equations effectively square the condition number:

for full-column-rank A. This explains why forming A^TA can be unstable. In SVD-based pseudoinversion, very small singular values may be truncated using a tolerance. This creates a controlled bias in exchange for lower variance and better stability.

8. Latent-Factor Modelling and Recommendation

Many data matrices are approximately low rank. A user–item rating matrix R can be modelled as

where P ∈ ℝ^m×k contains latent user factors, Q ∈ ℝ^n×k contains latent item factors and k is much smaller than both dimensions. The predicted rating is

A regularised objective over observed ratings Ω is

where λ ≥ 0 controls shrinkage. Bias terms may be added for the global mean, user tendencies and item tendencies. Alternating least squares and stochastic-gradient methods are common optimisation approaches.

SVD applied directly to a complete, centred matrix gives an optimal low-rank approximation under squared reconstruction error. Real recommendation data are usually sparse and missingness is not random. Treating every unobserved entry as a zero or a negative preference can introduce severe bias. A model should distinguish an unobserved interaction from an observed dislike and should evaluate using temporally separated, user-aware validation data.

9. Graph Spectral Methods

For a weighted undirected graph, let A be the adjacency matrix and D the diagonal degree matrix, with D_ii = ∑_j A_ij. The unnormalised graph Laplacian is

For any vector x,

so L is PSD. The multiplicity of eigenvalue zero equals the number of connected components. The smallest nonzero eigenvectors can reveal community structure and are used in spectral clustering. Normalised alternatives include D^-1/2LD^-1/2, provided the relevant degrees are positive.

Graph-based dimensionality reduction and semi-supervised learning use these eigenvectors to encourage nearby or strongly connected points to receive similar representations. Their quality depends on the graph construction, distance metric, scale parameter and robustness to noisy or unfair connectivity patterns.

10. Detailed Application: PCA for Sensor-Fault Monitoring

Background

Consider an illustrative manufacturing process with 1,000 time-window observations and 12 sensors measuring temperature, pressure, flow and vibration. The goal is to compress the measurements and detect unusual operating states.

Problem

The sensors are correlated, measured in different units and affected by occasional faults. A monitoring team needs a lower-dimensional representation that preserves normal operating variation while identifying observations that do not conform to the learned structure.

Analysis and Approach

First, engineers remove impossible readings and decide how to treat missing values without using future information. They centre the training observations. Because units differ substantially, they standardise each sensor using training-set means and standard deviations. They then compute an SVD of the scaled matrix rather than explicitly forming a covariance matrix.

Suppose the first four singular values are 41.2, 18.6, 11.4 and 8.0, and the total sum of squared singular values is 2,500. The variance retained by four components is

Thus, four components retain approximately 89.5% of the scaled variation. The team examines loadings rather than assigning automatic physical meanings to components. A reconstruction residual for observation x is

when x is represented in centred coordinates and V_k contains the retained right singular vectors. A large residual may indicate a fault, a new operating regime or a data-quality problem; it is not automatically evidence of equipment failure.

Outcome

The reduced representation supports visual monitoring and lowers the cost of downstream anomaly models. Thresholds are calibrated on historical normal data and checked across operating conditions. The system is deployed with an audit trail, human review and a fallback to raw sensor diagnostics.

Learning Points

1. Scaling decisions determine which directions PCA considers important.
2. Variance retention is a descriptive criterion, not a guarantee of fault-detection performance.
3. Components require domain interpretation and may change after process redesign.
4. Validation must respect time order and avoid leakage from future faults.
5. Anomaly alerts should support engineering judgement rather than replace it.

11. Limitations, Governance and Best Practices

Statistical and Computational Limitations

PCA and truncated SVD are linear. Nonlinear manifolds may require kernel methods, autoencoders or other nonlinear approaches, each with additional assumptions and interpretability costs. Outliers can dominate covariance estimates. Robust PCA and robust covariance estimators may help, but they also require tuning and may fail under adversarial contamination.

Singular vectors can be unstable when singular values are close. A small perturbation in the data may change individual vectors substantially even when the associated subspace remains stable. Rank selection is therefore uncertain, especially when the singular-value spectrum has no clear gap.

SVD can be expensive for very large matrices. Randomised and truncated SVD algorithms reduce computational cost by approximating dominant subspaces. Their accuracy should be checked using reconstruction error, residual tests and reproducibility across random seeds.

Governance and Ethical Issues

Dimensionality reduction can obscure protected attributes without removing their information. A latent factor may encode gender, ethnicity, disability, socioeconomic status or other sensitive characteristics through correlated variables. Removing explicit identifiers is not sufficient to ensure fairness.

Recommendation systems can amplify popularity bias, reduce exposure for minority creators and create feedback loops: recommendations influence behaviour, which becomes future training data. Teams should document data provenance, missingness assumptions, model version, rank and regularisation choices, evaluation populations and known failure modes. Privacy-preserving analysis may require aggregation, access controls, differential privacy or secure computation, depending on the context and applicable law.

Best Practices

• Centre and scale using training data only; apply the same transformation to validation and deployment data.
• Use QR, Cholesky or SVD solvers rather than explicit matrix inverses.
• Inspect singular values, condition numbers, residuals and sensitivity to perturbation.
• Select rank using both statistical evidence and the downstream purpose.
• Preserve metadata and document how missing values are represented.
• Validate on temporally or operationally appropriate data.
• Assess subgroup performance and possible disparate impact.
• Communicate that latent components are mathematical directions, not necessarily real-world causes.

Contemporary Developments

Modern large-scale systems use streaming, randomised and distributed matrix factorisation. Incremental PCA updates a subspace as new observations arrive, while sketching methods compress matrices before decomposition. Tensor decompositions extend factorisation beyond two-way data such as users × items × time. Neural representation learning often uses matrix-factorisation ideas implicitly: embeddings are low-dimensional latent coordinates, and contrastive or reconstruction objectives shape their geometry.

Research increasingly focuses on uncertainty in spectral embeddings, robust decomposition under missing-not-at-random data, fairness-aware recommendation and domain adaptation. These developments do not eliminate the need for classical linear algebra; they make correct formulation, conditioning analysis and validation more important.

Chapter Summary

Determinants describe invertibility and volume scaling, but numerical conditioning is generally a better indicator of sensitivity. Eigenvalues and eigenvectors identify invariant directions of square transformations. For symmetric matrices, the spectral theorem gives an orthonormal eigendecomposition, and positive-definite matrices provide well-behaved quadratic forms, covariance structures and optimisation objectives.

SVD applies to every real matrix and expresses a transformation through orthogonal input and output directions and nonnegative singular values. Truncated SVD gives the optimal rank-constrained approximation, forming the mathematical basis of PCA, compression and many latent-factor models. PCA is obtained from the SVD of centred data and identifies directions of maximum variance, although its results depend on scaling, outliers and the chosen objective.

The Moore–Penrose pseudoinverse provides minimum-norm least-squares solutions for rectangular or rank-deficient systems. SVD exposes small singular values and therefore helps diagnose ill-conditioning and control numerical instability. These tools support recommendation, graph learning, anomaly detection and dimensionality reduction, but responsible practice requires careful treatment of missingness, fairness, privacy, temporal leakage and interpretability.

Key Terms

Determinant: A scalar describing invertibility and signed volume scaling of a square linear transformation.

Eigenvalue: A scalar λ for which a nonzero vector satisfies Av = λv.

Eigenvector: A nonzero invariant-direction vector associated with an eigenvalue.

Characteristic polynomial: The polynomial det(A − λI) whose roots are eigenvalues.

Eigendecomposition: Representation of a diagonalizable matrix using eigenvectors and eigenvalues.

Spectral theorem: The result that every real symmetric matrix has an orthonormal eigenbasis.

Positive-definite matrix: A symmetric matrix satisfying x^TAx > 0 for every nonzero x.

Positive-semidefinite matrix: A symmetric matrix satisfying x^TAx ≥ 0 for every x.

Quadratic form: An expression of the form x^TAx.

Singular value: A nonnegative scale factor in the SVD of a matrix.

Singular value decomposition: The factorisation A = UΣV^T.

Rank: The dimension of the column space, equivalently the number of nonzero singular values.

Truncated SVD: An SVD retaining only the largest selected singular values.

Principal component: A direction in PCA ordered by explained variance.

Pseudoinverse: The unique Moore–Penrose generalisation of a matrix inverse.

Condition number: A measure of sensitivity, often κ₂(A)=σ_max/σ_min.

Latent factor: An unobserved low-dimensional variable used to explain observed relationships.

Graph Laplacian: The matrix L=D−A encoding graph connectivity and smoothness.

Regularisation: A deliberate constraint or penalty used to reduce overfitting or instability.

Review Questions

Short Answer Questions

1. What does the determinant of a square matrix indicate about invertibility?
2. State the defining equation for an eigenvector and eigenvalue.
3. Distinguish positive-definite from positive-semidefinite matrices.
4. Why is SVD applicable to rectangular matrices whereas ordinary eigendecomposition is not generally applicable?
5. What is the role of small singular values in numerical instability?

Long Answer Questions

1. Derive the eigendecomposition of a real symmetric matrix and explain the geometric meaning of its eigenvalues and eigenvectors.
2. Explain the SVD, including the relationships between singular vectors and eigenvectors of A^TA and AA^T.
3. Develop PCA from a centred data matrix and derive the explained-variance ratio.
4. Explain the Moore–Penrose pseudoinverse and its role in overdetermined and underdetermined systems.
5. Critically evaluate low-rank matrix factorisation for recommender systems, including missingness, regularisation and fairness.

Analytical / Application Questions

1. A covariance matrix has eigenvalues 6, 2, 1 and 0. Is it positive definite or positive semidefinite? What proportion of total variance is explained by the first two components?
2. A matrix has singular values 10, 4, 0.5 and 0.01. Discuss its conditioning and explain which singular values might be truncated in a stable low-rank model.
3. Design a validation and governance plan for a PCA-based industrial anomaly detector whose data arrive continuously and include several protected operational groups.

Multiple Choice Questions with Answers

Question 1

For a real symmetric matrix, which statement is guaranteed by the spectral theorem?

A. It has only positive eigenvalues.

B. It has an orthonormal basis of eigenvectors.

C. It must be invertible.

D. It must be rectangular.

Correct Answer: B. It has an orthonormal basis of eigenvectors.

Question 2

A symmetric matrix with eigenvalues 4, 2 and 0 is:

A. Positive definite

B. Negative definite

C. Positive semidefinite

D. Indefinite

Correct Answer: C. Positive semidefinite

Question 3

If the singular values of a matrix are 5, 3 and 1, what is the squared Frobenius norm?

A. 9

B. 15

C. 25

D. 35

Correct Answer: D. 35

Question 4

Which factorisation is defined for every real matrix, including rectangular matrices?

A. SVD

B. Cholesky factorisation

C. A standard inverse

D. A determinant factorisation

Correct Answer: A. SVD

Question 5

In PCA, the variance of component i obtained from an SVD of centred X is:

A. σ_i

B. σ_i²

C. σ_i²/(n−1)

D. (n−1)σ_i²

Correct Answer: C. σ_i²/(n−1)

Question 6

What does the Moore–Penrose pseudoinverse provide for an overdetermined system?

A. A maximum-norm exact solution in every case

B. A minimum-norm least-squares solution

C. A guarantee that every equation is satisfied exactly

D. A covariance matrix

Correct Answer: B. A minimum-norm least-squares solution

Question 7

Why can forming AᵀA be numerically undesirable?

A. It always changes the rank to one.

B. It squares the 2-norm condition number.

C. It makes all eigenvalues negative.

D. It prevents least-squares estimation.

Correct Answer: B. It squares the 2-norm condition number.

Question 8

For a graph Laplacian of an undirected graph, the multiplicity of eigenvalue zero equals the number of:

A. Edges

B. Vertices

C. Connected components

D. Nonzero singular values

Correct Answer: C. Connected components

Question 9

If the first three squared singular values sum to 900 and the total sum of squared singular values is 1,000, the first three components explain:

A. 9%

B. 10%

C. 90%

D. 900%

Correct Answer: C. 90%

Question 10

In a latent-factor recommender model, the predicted interaction p_uᵀq_i is determined by:

A. The determinant of the rating matrix

B. The inner product of user and item factor vectors

C. The largest covariance eigenvalue only

D. The number of missing entries alone

Correct Answer: B. The inner product of user and item factor vectors