Condition Numbers From Extreme Singular Values

Conditioning and Singular Values

A matrix can stretch some directions much more than others. The largest singular value measures its greatest stretching of a unit vector, while the smallest positive singular value measures the least stretching in directions where the matrix does not erase information. Comparing these two extremes gives a useful measure of how unevenly the matrix acts. This comparison is the 2-norm condition number.

Work over \(\mathbb{C}\), with real matrices and vectors included as a special case. The Euclidean norm of a vector \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\) is \(\|\mathbf{x}\|=(\sum_{j=1}^n |x_j|^2)^{1/2}\). The matrix 2-norm, also called the operator 2-norm, is \(\|\mathbf{A}\|_2=\max_{\|\mathbf{x}\|=1}\|\mathbf{A}\mathbf{x}\|\). A singular value decomposition (SVD) writes an \(m\times n\) matrix as \(\mathbf{A}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}\), where \(\mathbf{U}\) and \(\mathbf{V}\) are unitary and the diagonal entries of \(\boldsymbol{\Sigma}\) are nonnegative. The singular values, listed in nonincreasing order, are \(\sigma_1\ge\cdots\ge\sigma_p\ge0\), where \(p=\min(m,n)\). The number of positive singular values is the rank of \(\mathbf{A}\).

For a square invertible matrix, all singular values are positive. For a tall full-column-rank matrix, all input directions are represented by positive singular values. For a wide full-row-rank matrix, the positive singular values describe the directions perpendicular to the null space, but the matrix still has input directions that it maps to zero. This distinction matters when interpreting the ratio.

Extreme Singular Values Give the Extreme Gains

Proof. Write \(\mathbf{A}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}\), and set \(\mathbf{y}=\mathbf{V}^{*}\mathbf{x}\). Unitary matrices preserve Euclidean norms, so \(\|\mathbf{x}\|=\|\mathbf{y}\|\) and \(\|\mathbf{A}\mathbf{x}\|=\|\boldsymbol{\Sigma}\mathbf{y}\|\). In coordinates, \(\|\boldsymbol{\Sigma}\mathbf{y}\|^2=\sum_{j=1}^{r}\sigma_j^2|y_j|^2\). Since \(\sigma_j\le\sigma_1\) for each \(j\), this sum is at most \(\sigma_1^2\sum_{j=1}^n|y_j|^2=\sigma_1^2\|\mathbf{x}\|^2\). If \(\mathbf{x}\in(\operatorname{Nul}\mathbf{A})^\perp\), its coordinates along the right singular vectors with zero singular value vanish. Thus \(\|\mathbf{x}\|^2=\sum_{j=1}^{r}|y_j|^2\), and \(\sum_{j=1}^{r}\sigma_j^2|y_j|^2\ge\sigma_r^2\sum_{j=1}^{r}|y_j|^2=\sigma_r^2\|\mathbf{x}\|^2\). Taking \(\mathbf{x}\) to be a right singular vector for \(\sigma_1\) attains the upper bound; taking one for \(\sigma_r\) attains the lower bound. Full column rank means there are no zero-singular-value input directions, so \((\operatorname{Nul}\mathbf{A})^\perp=\mathbb{C}^n\). \(\square\)

Consequently, \(\|\mathbf{A}\|_2=\sigma_1\). If \(\mathbf{A}\) has full column rank, its action on any input vector satisfies \(\sigma_n\|\mathbf{x}\|\le\|\mathbf{A}\mathbf{x}\|\le\sigma_1\|\mathbf{x}\|\). The ratio compares the largest and smallest possible gains. For a wide full-row-rank matrix, the upper bound still holds, and the lower bound holds on \((\operatorname{Nul}\mathbf{A})^\perp\); it cannot hold for all inputs because nonzero vectors in the null space have zero output.

Why the Square-Matrix Definition Is a Ratio

For an invertible square matrix, every input direction has a positive singular value. The condition number defined using the inverse is exactly the ratio of the largest to the smallest singular value.

Proof. The extreme-gain result gives \(\|\mathbf{A}\|_2=\sigma_1\). Let \(\mathbf{A}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}\). Invertibility makes every diagonal entry of \(\boldsymbol{\Sigma}\) positive, so \(\mathbf{A}^{-1}=\mathbf{V}\boldsymbol{\Sigma}^{-1}\mathbf{U}^{*}\), as multiplying this expression by \(\mathbf{A}\) on either side gives the identity. The diagonal entries of \(\boldsymbol{\Sigma}^{-1}\) are \(1/\sigma_1,\dots,1/\sigma_n\); its largest singular value is \(1/\sigma_n\). Hence \(\|\mathbf{A}^{-1}\|_2=1/\sigma_n\), and multiplying the two norms gives \(\kappa_2(\mathbf{A})=\sigma_1/\sigma_n\). \(\square\)

Full-Rank Rectangular Matrices

The positive-singular-value ratio also gives a useful condition measure when a matrix is rectangular and has full rank. A tall full-column-rank matrix has no nonzero null-space directions, so its smallest singular value is a lower bound on output size for every input. A wide full-row-rank matrix has a nontrivial null space, so the ratio concerns only the directions that are not erased.

What Rank Deficiency Changes

A rank-deficient matrix has at least one zero singular value among its \(p=\min(m,n)\) listed singular values. More fundamentally, its rank is less than \(n\), so its null space contains a nonzero vector: there is an input direction that the matrix erases. No finite constant \(C\) can satisfy \(\|\mathbf{x}\|\le C\|\mathbf{A}\mathbf{x}\|\) for all inputs, because for a nonzero \(\mathbf{x}\) in the null space the right side is zero. This is why a finite ratio of the positive singular values alone does not describe the full-map condition.

Condition Numbers and Relative Error

For an invertible square matrix, the condition number bounds how much a relative change in the right-hand side can affect the solution of \(\mathbf{A}\mathbf{x}=\mathbf{b}\). If \(\mathbf{b}\ne\mathbf{0}\) and it changes by \(\delta\mathbf{b}\), the corresponding solution changes by \(\delta\mathbf{x}=\mathbf{A}^{-1}\delta\mathbf{b}\). The definitions and norm inequalities give \(\|\delta\mathbf{x}\|\le\|\mathbf{A}^{-1}\|_2\|\delta\mathbf{b}\|\), while \(\|\mathbf{b}\|=\|\mathbf{A}\mathbf{x}\|\le\|\mathbf{A}\|_2\|\mathbf{x}\|\). Combining them yields \(\|\delta\mathbf{x}\|/\|\mathbf{x}\|\le\kappa_2(\mathbf{A})\|\delta\mathbf{b}\|/\|\mathbf{b}\|\). Thus a large condition number permits substantial relative solution changes even when the relative change in the data is small. The inequality is an upper bound, not a claim that every perturbation realizes it.

Common mistake: using only the smallest positive singular value for a rank-deficient matrix. For \(\mathbf{C}\) above, it is tempting to calculate \(4/2=2\) and call this the full condition number. That calculation ignores \(\sigma_3=0\) and the nonzero null vector \(\mathbf{e}_3\). The corrected conclusion is that \(2\) is the ratio on the nonzero singular directions, while the full-map condition is infinite. Conversely, for the full-row-rank matrix \(\mathbf{B}\), treating its zero singular value in the null direction as though it were a zero among the two positive singular values would incorrectly assign an infinite positive-singular-value ratio. State which directions and which condition measure are being considered.