Matrix Condition Number

• categories: Linear algebra, Definition

Definition

The condition number of a matrix $A\in {\mathbb{R}}^{n\times n}$ is a measure of how sensitive the solution of a linear system $A\mathbf{x}=\mathbf{b}$ is to changes in $\mathbf{b}$ or perturbations in $A$. It is defined as:

$$\kappa (A)=\Vert A\Vert \cdot \Vert A^{-1}\Vert ,$$

where $\Vert \cdot \Vert$ is a matrix norm, commonly the Spectral Norm ($\Vert A{\Vert }_2$) or Frobenius Norm ($\Vert A{\Vert }_F$).

For the spectral norm (2-norm), the condition number can be expressed in terms of the singular values ${\sigma }_{\max }$ and ${\sigma }_{\min }$ of $A$:

$${\kappa }_2(A)=\frac{{\sigma }_{\max }}{{\sigma }_{\min }},$$

where ${\sigma }_{\max }$ and ${\sigma }_{\min }$ are the largest and smallest singular values of $A$.

Intuition

• The condition number describes how much the output (solution $\mathbf{x}$) of the system $A\mathbf{x}=\mathbf{b}$ changes for a small change in the input $\mathbf{b}$.
• A large condition number indicates that the matrix is ill-conditioned, meaning it amplifies numerical errors and leads to unstable solutions.
• A small condition number indicates the matrix is well-conditioned, and solutions are stable under perturbations.

Properties

1. Range of Values:

   • $\kappa (A)\ge 1$ for all invertible matrices $A$.
   • $\kappa (A)=1$ if and only if $A$ is a scalar multiple of an orthogonal matrix (e.g., rotations, reflections).

2. Invariance Under Scaling:

   • $\kappa (cA)=\kappa (A)$ for any scalar $c\ne 0$.

3. Relation to Matrix Singular Values:

   • $\kappa (A)\to \infty$ as ${\sigma }_{\min }\to 0$, indicating near-singularity.

4. Sensitivity to Perturbations:

   • For small perturbations $\Delta A$, the relative change in the solution $\mathbf{x}$ satisfies: $$\frac{\Vert \Delta \mathbf{x}\Vert }{\Vert \mathbf{x}\Vert }\le \kappa (A)\frac{\Vert \Delta \mathbf{b}\Vert }{\Vert \mathbf{b}\Vert }.$$

Examples

1. Diagonal Matrix:
   For $A=\text{diag}(1,2,10)$, the singular values are $\{1,2,10\}$:

   $${\kappa }_2(A)=\frac{{\sigma }_{\max }}{{\sigma }_{\min }}=\frac{10}{1}=10.$$

2. Orthogonal Matrix:
   If $A$ is an orthogonal matrix ($A^{T}A=I$), then ${\sigma }_{\max }={\sigma }_{\min }=1$:

   $${\kappa }_2(A)=1.$$

3. Nearly Singular Matrix:
   For $A=\left[\begin{array}{cc}1& 1\\ 1& 1.0001\end{array}\right]$, ${\kappa }_2(A)\approx 10^4$, indicating instability in solutions.