Matrix Norms and Condition Numbers

Definition Choose a norm on $\mathbb{F}^n$ and a norm on $\mathbb{F}^m$, both written $\lVert \cdot \rVert$, and let $A \in \mathbb{F}^{m \times n}$. The induced matrix norm, or operator norm, of $A$ is

The two maxima agree because the ratio does not change when $x$ is multiplied by a nonzero scalar. They are attained, not just suprema, because the unit sphere of $\mathbb{F}^n$ is compact in finite dimensions and $x \mapsto \lVert Ax \rVert$ is continuous. This is a norm on $\mathbb{F}^{m \times n}$. It is zero only for the zero matrix, it satisfies $\lVert cA \rVert = \lvert c \rvert \, \lVert A \rVert$, and the triangle inequality $\lVert A + B \rVert \le \lVert A \rVert + \lVert B \rVert$ follows from the triangle inequality for each output $(A + B)x$. The value depends on the vector norms. With the Euclidean norm $\lVert x \rVert_2 = (x^{*}x)^{1/2}$ on both sides it is written $\lVert A \rVert_2$ and called the spectral norm. With $\lVert x \rVert_\infty = \max_i \lvert x_i \rvert$ on both sides it equals the largest absolute row sum, and with $\lVert x \rVert_1 = \sum_i \lvert x_i \rvert$ on both sides the largest absolute column sum.

The Frobenius norm is a different matrix norm,

It treats the entries as one long vector. For square matrices of size $n \ge 2$ it is not the norm induced by any vector norm on $\mathbb{F}^n$, because such an induced norm gives $\lVert I \rVert = 1$, while $\lVert I_n \rVert_F = \sqrt{n}$.

Definition Let $A \in \mathbb{F}^{m \times n}$ and $B \in \mathbb{F}^{n \times p}$, with norms chosen on $\mathbb{F}^p$, $\mathbb{F}^n$ and $\mathbb{F}^m$ and the induced matrix norms they give. For every $x \in \mathbb{F}^n$,

and the norms are submultiplicative,

provided the norm on $\mathbb{F}^n$ that measures the outputs of $B$ is the same norm that measures the inputs of $A$. The first inequality is immediate for $x = 0$. For $x \ne 0$ the vector $x / \lVert x \rVert$ has norm $1$, so its image has norm at most $\lVert A \rVert$, and multiplying by $\lVert x \rVert$ gives the claim. Applying it twice gives $\lVert ABx \rVert \le \lVert A \rVert \, \lVert Bx \rVert \le \lVert A \rVert \, \lVert B \rVert \, \lVert x \rVert$, and taking the maximum over unit vectors $x$ proves the second inequality. In particular $\lVert A^k \rVert \le \lVert A \rVert^k$ for a square matrix when one norm on $\mathbb{F}^n$ measures both its inputs and its outputs. The Frobenius norm satisfies

Column $j$ of $AB$ is $Ab_j$, where $b_j$ is column $j$ of $B$, and adding the inequalities $\lVert Ab_j \rVert_2^2 \le \lVert A \rVert_2^2 \lVert b_j \rVert_2^2$ over all $j$ gives the first inequality. The second uses $\lVert A \rVert_2 \le \lVert A \rVert_F$, which is proved with singular values below.

Definition Let $A \in \mathbb{F}^{m \times n}$ have a full singular value decomposition $A = U\Sigma V^{*}$, with $U \in \mathbb{F}^{m \times m}$ and $V \in \mathbb{F}^{n \times n}$ unitary (orthogonal when $\mathbb{F} = \mathbb{R}$) and singular values $\sigma_1 \ge \cdots \ge \sigma_p \ge 0$ on the diagonal of $\Sigma \in \mathbb{R}^{m \times n}$, where $p = \min(m, n)$. Then

For the first formula, write a unit vector as $x = Vc$ with $\lVert c \rVert_2 = 1$. Unitary matrices preserve Euclidean length, so

with equality at the first right singular vector $x = v_1$. For the second, the $j$th diagonal entry of $A^{*}A$ is the sum of $\lvert a_{ij} \rvert^2$ down column $j$, and $A^{*}A = V(\Sigma^{\mathsf{T}}\Sigma)V^{*}$ has the same trace as $\Sigma^{\mathsf{T}}\Sigma$. Consequently $\sigma_1 \le \lVert A \rVert_F \le \sqrt{r}\,\sigma_1$, where $r$ is the rank of $A$. If $A$ is square and invertible, then $A^{-1} = V\Sigma^{-1}U^{*}$ has singular values $1/\sigma_n \ge \cdots \ge 1/\sigma_1$, so $\lVert A^{-1} \rVert_2 = 1/\sigma_n$.

The norm of the adjoint is the same, $\lVert A^{*} \rVert_2 = \lVert A \rVert_2$, also for rectangular $A$, because $A^{*} = V\Sigma^{\mathsf{T}}U^{*}$ has the same singular values. A direct proof uses the dual description of length. By Cauchy-Schwarz, $\lVert z \rVert_2 = \max_{\lVert y \rVert_2 = 1} \lvert \langle y, z \rangle \rvert$, attained at $y = z / \lVert z \rVert_2$ when $z \ne 0$. Hence

and since $\lvert y^{*}Ax \rvert = \lvert \langle A^{*}y, x \rangle \rvert$, the same maximum computes $\lVert A^{*} \rVert_2$ with the roles of $x$ and $y$ exchanged. The conjugate transpose is needed here, because $y^{*}Ax$ is the inner product of $y$ and $Ax$ in the course convention. The equality uses the Euclidean norm on both spaces. With the max norm on both sides, the real matrix with rows $(1, 1)$ and $(0, 0)$ has induced norm $2$, while its transpose, which is also its adjoint, has induced norm $1$. For other norms the equality survives when the adjoint is measured in the dual norms. For example, the largest absolute column sum of $A^{*}$ is the largest absolute row sum of $A$, so $\lVert A^{*} \rVert_1 = \lVert A \rVert_\infty$ for every $A$.

Definition Let $A \in \mathbb{F}^{n \times n}$ be invertible, and fix one norm on $\mathbb{F}^n$, used for inputs and outputs alike, with its induced matrix norm. The condition number of $A$ in that norm is

It satisfies $\kappa(A) \ge 1$, because $1 = \lVert I \rVert = \lVert AA^{-1} \rVert \le \lVert A \rVert \, \lVert A^{-1} \rVert$. It also satisfies $\kappa(cA) = \kappa(A)$ for every scalar $c \ne 0$, and $\kappa(A^{-1}) = \kappa(A)$. In the Euclidean norm the singular value formulas give

the largest singular value divided by the smallest. This number measures the sensitivity of solving $Ax = b$ when $A$ is fixed and $b$ is perturbed, in the declared norm, as the perturbation bound below makes precise. It is not a measure of everything about $A$. The sensitivity of eigenvalues, of least-squares solutions, or of solutions when the entries of $A$ are uncertain each needs its own formulation. A singular square matrix has no inverse, and its condition number for this problem is not finite. It is often set to $\infty$.

Definition Let $A \in \mathbb{F}^{n \times n}$ be invertible, let $b \ne 0$, and let $Ax = b$, so that $x \ne 0$. Suppose only the right-hand side changes, and $A(x + \delta x) = b + \delta b$. Then, in any norm on $\mathbb{F}^n$ with its induced matrix norm,

Subtracting the two equations gives $A\,\delta x = \delta b$, so $\delta x = A^{-1}\delta b$ and $\lVert \delta x \rVert \le \lVert A^{-1} \rVert \, \lVert \delta b \rVert$. Also $\lVert b \rVert = \lVert Ax \rVert \le \lVert A \rVert \, \lVert x \rVert$, so $1/\lVert x \rVert \le \lVert A \rVert / \lVert b \rVert$. Multiplying the two inequalities gives the bound. It is a worst-case bound. In the Euclidean norm it is attained when $b$ is a multiple of the first left singular vector $u_1$ and $\delta b$ a multiple of the last one $u_n$, and it can be far from attained for other perturbations. Changes in $A$ itself need a separate argument.

Definition A condition number depends on the norm, and the Euclidean norm of raw coordinates depends on the units. Measuring the equations or the unknowns in other units replaces $Ax = b$ by

where $D_1$ and $D_2$ are diagonal with positive diagonal entries. The solution describes the same physical quantities, but $\kappa_2(D_1AD_2)$ can differ from $\kappa_2(A)$. Submultiplicativity, applied to $D_1AD_2$ and to $A = D_1^{-1}(D_1AD_2)D_2^{-1}$, shows that the ratio of the two condition numbers lies between $1/c$ and $c$, where $c = \kappa_2(D_1)\,\kappa_2(D_2)$ and $\kappa_2(D)$ is the largest diagonal entry of $D$ divided by the smallest. Two kinds of change leave $\kappa_2$ unchanged. Scaling by one nonzero number gives $\kappa_2(cA) = \kappa_2(A)$, and a unitary change of coordinates gives $\kappa_2(UAV) = \kappa_2(A)$ for unitary $U$ and $V$, because it preserves singular values. Choosing a scaling is part of the error model. It decides which changes of the data count as equally large.