Norms measure size. Condition numbers measure how much a problem can amplify errors before any algorithmic mistakes are made.
Vector norms and matrix norms
Definition. A norm on a vector space is a function \(\|\cdot\|\) satisfying positivity, homogeneity, and the triangle inequality. A matrix norm is a norm on a matrix space. A matrix norm is subordinate to vector norms if \[ \|A\|=\max_{x\ne0}\frac{\|Ax\|}{\|x\|}. \]
Example. Common vector norms are \(\|x\|_1=\sum_i|x_i|\), \(\|x\|_2=(\sum_i|x_i|^2)^{1/2}\), and \(\|x\|_\infty=\max_i|x_i|\). Their subordinate matrix norms include the maximum column-sum norm, the spectral norm, and the maximum row-sum norm.
Spectral and Frobenius norms
Proposition. If \(A\) has singular values \(\sigma_1\ge\cdots\), then \[ \|A\|_2=\sigma_1, \qquad \|A\|_F=\left(\sum_i\sigma_i^2\right)^{1/2}=\big(\operatorname{tr}(A^*A)\big)^{1/2}. \] The spectral norm is subordinate to the Euclidean vector norm; the Frobenius norm comes from an inner product on matrices.
Proof. Use the SVD \(A=U\Sigma V^*\). Unitary factors preserve Euclidean norm, so \(\|Ax\|=\|\Sigma V^*x\|\le\sigma_1\|x\|\), with equality at the first right singular vector. The Frobenius formula follows from \(\operatorname{tr}(A^*A)=\operatorname{tr}(V\Sigma^*\Sigma V^*)=\sum_i\sigma_i^2\).
Equivalence of norms
Theorem. On a finite-dimensional vector space, any two norms are equivalent: for norms \(\|\cdot\|_a\) and \(\|\cdot\|_b\), there exist constants \(c,C\gt0\) such that \[ c\|x\|_a\le\|x\|_b\le C\|x\|_a \] for all \(x\).
Proof. Identify the space with \(F^n\). The unit sphere for \(\|\cdot\|_a\) is compact in Euclidean coordinates, and \(\|x\|_b\) is continuous. It therefore attains a positive minimum and finite maximum on that sphere. Homogeneity extends the inequalities to all nonzero vectors.
Condition number of a linear system
Definition. For an invertible matrix \(A\), the condition number in a subordinate norm is \[ \kappa(A)=\|A\|\|A^{-1}\|. \] In the Euclidean norm, \(\kappa_2(A)=\sigma_{\max}(A)/\sigma_{\min}(A)\).
Theorem. If \(Ax=b\), \(A(x+\delta x)=b+ \delta b\), and \(A\) is invertible, then \[ \frac{\|\delta x\|}{\|x\|}\le \kappa(A)\frac{\|\delta b\|}{\|b\|}. \] Thus \(\kappa(A)\) bounds the relative amplification of data error.
Proof. Since \(\delta x=A^{-1}\delta b\), \(\|\delta x\|\le\|A^{-1}\|\|\delta b\|\). Also \(\|b\|=\|Ax\|\le\|A\|\|x\|\), so \(1/\|x\|\le\|A\|/\|b\|\). Multiplying gives the bound.
Near singularity
Remark. A large condition number means the matrix is close to singular relative to its scale. In the spectral norm, the distance from \(A\) to the set of singular matrices is \(\sigma_{\min}(A)\). Thus ill conditioning is not an algorithmic defect; it is geometric instability in the problem itself.
Forward error, backward error, and conditioning
For \(Ax=b\) with \(A\) invertible, perturb \((A+\Delta A)(x+\Delta x)=b+\Delta b\). If \(\|A^{-1}\Delta A\|<1\), then \[ \frac{\|\Delta x\|}{\|x\|} \le \frac{\kappa(A)} {1-\kappa(A)\|\Delta A\|/\|A\|} \left( \frac{\|\Delta A\|}{\|A\|} +\frac{\|\Delta b\|}{\|b\|} \right), \] where \(\kappa(A)=\|A\|\|A^{-1}\|\).
Proof. Rearrangement gives \[ (I+A^{-1}\Delta A)\Delta x =A^{-1}(\Delta b-\Delta A\,x). \] The Neumann-series estimate \[ \|(I+E)^{-1}\|\le(1-\|E\|)^{-1} \] and \(\|b\|\le\|A\|\|x\|\) yield the bound.
Conditioning belongs to the mathematical problem; backward stability belongs to the algorithm. A backward-stable solver returns the exact solution to nearby data. Its forward error is small only when the underlying problem is also well conditioned.
Proposition. In the spectral norm, \[ \kappa_2(A)=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)} \] and \[ \operatorname{dist}_2(A,\{\text{singular matrices}\}) =\sigma_{\min}(A). \]
Proof. The SVD gives \(\|A\|_2=\sigma_{\max}\) and \(\|A^{-1}\|_2=\sigma_{\min}^{-1}\). Subtracting \(\sigma_{\min}u_nv_n^*\) makes \(A\) singular. Conversely, if \(A+E\) is singular, choose unit \(x\) with \((A+E)x=0\); then \(\|E\|_2\ge\|Ax\|\ge\sigma_{\min}\).