Matrix Norms & Condition Number

Matrix Norms & Condition Number

Mathematical Definition

For a matrix A and a vector norm ||·||, the induced matrix norm is defined as the maximum possible amplification of a non-zero vector x by A. The condition number of an invertible matrix A with respect to this norm measures how much relative errors can be amplified when solving linear systems.

Key Concepts

Vector Norms

Before defining matrix norms, it helps to understand vector norms. Common vector norms include:

• L1 Norm (Manhattan): Sum of absolute values: ||x||₁ = Σ |x_i|
• L2 Norm (Euclidean): Square root of sum of squares: ||x||₂ = √(Σ x_i²)
• L∞ Norm (Maximum): Maximum absolute value: ||x||_∞ = max |x_i|

Induced Matrix Norms

Matrix norms are typically "induced" by vector norms. The induced norm of a matrix A measures the maximum possible stretch it can apply to any non-zero vector x:

This leads to specific matrix norms:

• L1 Matrix Norm: Maximum absolute column sum.
• L∞ Matrix Norm: Maximum absolute row sum.
• L2 Matrix Norm: Largest singular value (σ₁) of A. It represents the major axis of the hyperellipse formed by transforming the unit hypersphere.

Frobenius Norm

The Frobenius norm is not an induced norm, but an entry-wise norm. It is simply the square root of the sum of the absolute squares of its elements (similar to the L2 vector norm applied to the flattened matrix).

Condition Number

The condition number κ(A) of an invertible matrix is defined as the product of the norm of A and the norm of its inverse:

Using the L2 norm, this simplifies to the ratio of the largest to the smallest singular value (σ₁ / σ_n). A matrix with a large condition number is called ill-conditioned, meaning a small error in input (like the vector b in Ax = b) can result in a massive error in the solution x.

Historical Context

The concept of the condition number was introduced by Alan Turing in 1948 in his seminal paper "Rounding-Off Errors in Matrix Processes." Turing formulated the condition number as a rigorous way to measure the impact of rounding errors during the computational process of solving linear systems, fundamentally shaping the field of numerical linear algebra. The broader abstraction of norms traces back to the development of functional analysis by mathematicians like Stefan Banach and Hermann Minkowski in the early 20th century.

Real-world Applications

• Numerical solution of Ax = b: Matrix norms and the condition number predict how rounding errors or small perturbations in b affect the computed solution x, guiding the choice of algorithms and preconditioners in scientific computing.
• Data fitting and regression: In least-squares problems and linear regression, an ill-conditioned design matrix leads to highly unstable parameter estimates; condition numbers are used to diagnose multicollinearity and sensitivity.
• Engineering simulations: Finite element and finite difference discretizations of differential equations produce large linear systems whose condition numbers determine the stability and accuracy of structural, fluid, and thermal simulations.
• Optimization and machine learning: The conditioning of Hessians or Jacobians affects convergence speed of gradient-based methods; matrix norms and condition numbers help select step sizes, regularization strength, and problem reformulations.

Related Concepts

• Singular Value Decomposition (SVD): SVD factors a matrix into UΣV^T, directly providing the singular values necessary to compute the L2 norm and condition number.
• Linear Transformations: Matrix norms quantify the geometric deformation caused by a linear transformation.
• Systems of Linear Equations: The condition number determines the numerical stability when solving systems like Ax = b.