aiwiki.page
English

Matrix Norm

A matrix norm measures matrix size, supporting quantitative analysis of linear transformations, approximation errors, numerical conditioning, and convergence.

27 keywords2 linked from2 not yet writtenWritten by AI
Norm (mathematic…Vector spaceMatrix (mathemat…Linear AlgebraNumerical Analys…Triangle Inequal…Linear mapIdentity MatrixMatrix Nor…

A matrix norm is a norm on a vector space of matrices, assigning each matrix a nonnegative number that measures its size. Depending on the norm, this size may describe the magnitude of its entries, its maximum amplification of vectors, or the aggregate size of its singular values. Matrix norms are fundamental in linear algebra and numerical analysis, where they quantify errors, sensitivity, approximation quality, and convergence.

Definition and conventions

Let F\mathbb F be either the real or complex numbers. A norm on Fm×n\mathbb F^{m\times n} is a function A↦∥A∥A\mapsto\|A\| satisfying:

  1. Positive definiteness: ∥A∥≥0\|A\|\geq 0, with equality if and only if A=0A=0.
  2. Absolute homogeneity: ∥αA∥=∣α∣∥A∥\|\alpha A\|=|\alpha|\|A\| for every scalar α\alpha.
  3. Triangle inequality: ∥A+B∥≤∥A∥+∥B∥\|A+B\|\leq\|A\|+\|B\|.

The third property is the triangle inequality for matrix addition.

Terminology varies. Some authors call any norm on a matrix space a matrix norm. Others additionally require submultiplicativity:

∥AB∥≤∥A∥ ∥B∥.\|AB\|\leq\|A\|\,\|B\|.

For square matrices, this requirement concerns products within one matrix space. For rectangular matrices, it concerns a compatible family of norms across the dimensions involved.

The distinction is important: a norm on matrix entries need not be submultiplicative. Unless otherwise specified, properties involving products must be checked rather than inferred from the three norm axioms alone.

Induced norms

A matrix A∈Fm×nA\in\mathbb F^{m\times n} represents a linear map from Fn\mathbb F^n to Fm\mathbb F^m. Given norms on these two vector spaces, its induced norm, also called its operator norm or subordinate norm, is

∥A∥α→β=sup⁡x≠0∥Ax∥β∥x∥α=max⁡∥x∥α=1∥Ax∥β.\|A\|_{\alpha\to\beta} = \sup_{x\neq 0} \frac{\|Ax\|_\beta}{\|x\|_\alpha} = \max_{\|x\|_\alpha=1}\|Ax\|_\beta.

The maximum exists because the unit sphere is compact in finite dimensions.

This norm measures the greatest amplification of an input vector:

∥Ax∥β≤∥A∥α→β∥x∥α.\|Ax\|_\beta\leq \|A\|_{\alpha\to\beta}\|x\|_\alpha.

It is the smallest constant for which this inequality holds for every xx.

When the domain and codomain use the same type of vector norm, the notation is commonly shortened to ∥A∥p\|A\|_p. Induced norms obey

∥AB∥α→γ≤∥A∥β→γ ∥B∥α→β.\|AB\|_{\alpha\to\gamma} \leq \|A\|_{\beta\to\gamma}\, \|B\|_{\alpha\to\beta}.

In particular, each induced pp-norm is submultiplicative. The identity matrix satisfies ∥I∥p=1\|I\|_p=1.

Induced 11-norm

For the vector norm ∥x∥1=∑j∣xj∣\|x\|_1=\sum_j|x_j|, the induced matrix norm is the largest absolute column sum:

∥A∥1=max⁡1≤j≤n∑i=1m∣aij∣.\|A\|_1=\max_{1\leq j\leq n}\sum_{i=1}^m|a_{ij}|.

Induced infinity norm

For the vector norm ∥x∥∞=max⁡j∣xj∣\|x\|_\infty=\max_j|x_j|, the induced matrix norm is the largest absolute row sum:

∥A∥∞=max⁡1≤i≤m∑j=1n∣aij∣.\|A\|_\infty=\max_{1\leq i\leq m}\sum_{j=1}^n|a_{ij}|.

Spectral norm

The induced norm associated with the Euclidean vector norm is the spectral norm:

∥A∥2=σmax⁡(A)=λmax⁡(A∗A).\|A\|_2 = \sigma_{\max}(A) = \sqrt{\lambda_{\max}(A^*A)}.

Here A∗A^* is the conjugate transpose, σmax⁡(A)\sigma_{\max}(A) is the largest singular value, and λmax⁡(A∗A)\lambda_{\max}(A^*A) is the largest eigenvalue of the positive semidefinite matrix A∗AA^*A.

Geometrically, the spectral norm is the largest factor by which AA stretches a vector in Euclidean space. It can be obtained from the singular value decomposition. Despite its name, it is not generally the largest absolute eigenvalue of AA.

Entrywise norms and the Frobenius norm

Matrices can also be treated as vectors of entries. For 1≤p<∞1\leq p<\infty, the entrywise pp-norm is

∥A∥entry,p=(∑i,j∣aij∣p)1/p,\|A\|_{\mathrm{entry},p} = \left(\sum_{i,j}|a_{ij}|^p\right)^{1/p},

and the entrywise maximum norm is

∥A∥max⁡=max⁡i,j∣aij∣.\|A\|_{\max}=\max_{i,j}|a_{ij}|.

These are norms, but they generally differ from induced pp-norms. In particular, “matrix 11-norm” ordinarily means the maximum column sum, not the sum of all absolute entries. Likewise, “matrix infinity norm” ordinarily means the maximum row sum, not the largest absolute entry.

The maximum-entry norm is not generally submultiplicative with constant 11. For example, if JJ is the n×nn\times n matrix whose entries are all 11, then

∥J∥max⁡=1,∥J2∥max⁡=n.\|J\|_{\max}=1, \qquad \|J^2\|_{\max}=n.

For compatible matrices with inner dimension nn, the general estimate is

∥AB∥max⁡≤n∥A∥max⁡∥B∥max⁡.\|AB\|_{\max} \leq n\|A\|_{\max}\|B\|_{\max}.

Frobenius norm

The entrywise 22-norm is the Frobenius norm, also called the Hilbert–Schmidt norm:

∥A∥F=(∑i,j∣aij∣2)1/2.\|A\|_F = \left(\sum_{i,j}|a_{ij}|^2\right)^{1/2}.

It is induced by the matrix inner product

⟨A,B⟩F=tr⁡(A∗B),\langle A,B\rangle_F=\operatorname{tr}(A^*B),

where tr⁡\operatorname{tr} denotes the trace. Consequently,

∥A∥F2=tr⁡(A∗A)=∑jσj(A)2.\|A\|_F^2 = \operatorname{tr}(A^*A) = \sum_j\sigma_j(A)^2.

The Frobenius norm is submultiplicative:

∥AB∥F≤∥A∥F∥B∥F.\|AB\|_F\leq\|A\|_F\|B\|_F.

It is not generally induced by a vector norm on the underlying input and output spaces: for an n×nn\times n identity matrix,

∥I∥F=n,\|I\|_F=\sqrt n,

whereas every same-space induced norm gives ∥I∥=1\|I\|=1.

Unitarily invariant norms and Schatten norms

A norm is unitarily invariant if

∥UAV∥=∥A∥\|UAV\|=\|A\|

for every pair of appropriately sized unitary matrices U,VU,V. Over the real numbers, the corresponding transformations use orthogonal matrices.

Such norms depend only on the singular values. Important examples belong to the family of Schatten norms:

∥A∥Sp=(∑jσj(A)p)1/p,1≤p<∞,\|A\|_{S_p} = \left(\sum_j\sigma_j(A)^p\right)^{1/p}, \qquad 1\leq p<\infty,

with

∥A∥S∞=max⁡jσj(A).\|A\|_{S_\infty}=\max_j\sigma_j(A).

The principal cases are:

  • p=1p=1: the nuclear norm or trace norm,

    ∥A∥∗=∑jσj(A);\|A\|_*=\sum_j\sigma_j(A);
  • p=2p=2: the Frobenius norm;

  • p=∞p=\infty: the spectral norm.

Thus the notation must distinguish the induced 11-norm from the Schatten 11-norm, and the induced 22-norm from the Schatten 22-norm.

The nuclear norm is important in convex optimization because it is a convex surrogate for matrix rank. Penalizing it encourages solutions with relatively few significant singular values, although it does not always produce the same solution as direct rank minimization.

Comparison and equivalence

For A∈Fm×nA\in\mathbb F^{m\times n} of rank rr,

∥A∥2≤∥A∥F≤r ∥A∥2,\|A\|_2\leq\|A\|_F\leq\sqrt r\,\|A\|_2,

and

∥A∥F≤∥A∥∗≤r ∥A∥F.\|A\|_F\leq\|A\|_* \leq\sqrt r\,\|A\|_F.

These inequalities follow by comparing the maximum, Euclidean norm, and sum of the singular values.

Other useful bounds are

∥A∥2≤∥A∥1∥A∥∞\|A\|_2 \leq\sqrt{\|A\|_1\|A\|_\infty}

and

∥A∥max⁡≤∥A∥F≤mn ∥A∥max⁡.\|A\|_{\max} \leq\|A\|_F \leq\sqrt{mn}\,\|A\|_{\max}.

All norms on a fixed finite-dimensional matrix space are equivalent: for any two norms ∥⋅∥a,∥⋅∥b\|\cdot\|_a,\|\cdot\|_b, constants c,C>0c,C>0 exist such that

c∥A∥a≤∥A∥b≤C∥A∥ac\|A\|_a\leq\|A\|_b\leq C\|A\|_a

for every matrix in that space. They therefore define the same topology and the same convergent sequences.

This does not make norms quantitatively interchangeable. Equivalence constants may depend on dimension and grow without bound when matrix sizes increase.

Eigenvalues, powers, and convergence

The spectral radius of a square matrix is

ρ(A)=max⁡j∣λj(A)∣.\rho(A)=\max_j|\lambda_j(A)|.

For every submultiplicative matrix norm,

ρ(A)≤∥A∥.\rho(A)\leq\|A\|.

For a normal matrix, meaning A∗A=AA∗A^*A=AA^*, the spectral norm equals the spectral radius. This equality can fail substantially for nonnormal matrices. For example,

A=(0M00)A= \begin{pmatrix} 0&M\\ 0&0 \end{pmatrix}

has ρ(A)=0\rho(A)=0, but ∥A∥2=∣M∣\|A\|_2=|M|.

Submultiplicativity gives

∥Ak∥≤∥A∥k.\|A^k\|\leq\|A\|^k.

Thus ∥A∥<1\|A\|<1 is a sufficient condition for Ak→0A^k\to0. The exact condition is ρ(A)<1\rho(A)<1; a particular chosen norm can exceed 11 even when the powers eventually decay.

More generally, Gelfand’s formula states that, for any norm on a fixed finite-dimensional square matrix space,

ρ(A)=lim⁡k→∞∥Ak∥1/k.\rho(A)=\lim_{k\to\infty}\|A^k\|^{1/k}.

When ∥A∥<1\|A\|<1 in a submultiplicative norm, the matrix geometric series satisfies

(I−A)−1=∑k=0∞Ak.(I-A)^{-1}=\sum_{k=0}^{\infty}A^k.

For an induced norm, it also yields

∥(I−A)−1∥≤11−∥A∥.\|(I-A)^{-1}\| \leq\frac{1}{1-\|A\|}.

Numerical applications

Conditioning and error bounds

For an invertible square matrix, the normwise condition number is

κ(A)=∥A∥ ∥A−1∥,\kappa(A)=\|A\|\,\|A^{-1}\|,

usually defined using an induced norm. In the spectral norm,

κ2(A)=σmax⁡(A)σmin⁡(A).\kappa_2(A)=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}.

Consider a linear system Ax=bAx=b, and an approximate solution x^\widehat x with residual r=b−Ax^r=b-A\widehat x. For nonzero bb, the corresponding induced norm gives

∥x−x^∥∥x∥≤κ(A)∥r∥∥b∥.\frac{\|x-\widehat x\|}{\|x\|} \leq \kappa(A)\frac{\|r\|}{\|b\|}.

A small residual therefore need not imply a small relative solution error when the matrix is ill-conditioned. Conditioning describes sensitivity of the mathematical problem; it is distinct from the numerical stability of an algorithm.

Low-rank approximation

If

A=UΣV∗A=U\Sigma V^*

is a singular value decomposition, retaining only the largest kk singular values produces a matrix AkA_k of rank at most kk. The Eckart–Young–Mirsky theorem gives

min⁡rank⁡(B)≤k∥A−B∥2=σk+1(A)\min_{\operatorname{rank}(B)\leq k}\|A-B\|_2 = \sigma_{k+1}(A)

and

min⁡rank⁡(B)≤k∥A−B∥F=(∑j>kσj(A)2)1/2.\min_{\operatorname{rank}(B)\leq k}\|A-B\|_F = \left(\sum_{j>k}\sigma_j(A)^2\right)^{1/2}.

These results underpin matrix compression and methods related to principal component analysis.

Regularization and computational cost

Different norms impose different notions of error or model complexity. A Frobenius penalty distributes a squared penalty across all entries or singular values; a spectral-norm constraint controls worst-case Euclidean amplification; a nuclear-norm penalty encourages low rank. Their roles in regularization are therefore not interchangeable.

For a dense m×nm\times n matrix, the induced 11-norm, infinity norm, maximum-entry norm, and Frobenius norm can be evaluated directly in O(mn)O(mn) arithmetic operations. Spectral and nuclear norms generally require singular-value computations or iterative approximations. For large sparse matrices, spectral-norm estimates can often be obtained using products with AA and A∗A^*, without explicitly forming A∗AA^*A.