The condition number kappa_p(A) = ||A||_p ||A^{-1}||_p of a nonsingular linear system

Let $n\in \mathbb{N}$ with $n\ge 1$, let either $p\in \mathbb{Q}$ with $p\ge 1$ or $p=\mathrm{\infty }$, and let $A\in {\mathrm{GL}}_n(\mathbb{R})$ be an invertible real matrix (Invertible matrices and the general linear group ${\mathrm{GL}}_n(F)$), so that the linear system $Ax=b$ has the unique solution $x=A^{-1}b$ for every right-hand side $b\in {\mathbb{R}}^n$. The condition number of the linear system (equivalently, of the matrix $A$) with respect to the induced $p$-norm of The matrix norm induced by a published vector p-norm, using its separately defined infinity case when $p=\mathrm{\infty }$, is

${\kappa }_p(A):=\parallel A{\parallel }_p\parallel A^{-1}{\parallel }_p\in [1,+\mathrm{\infty })\mathrm{.}$

The value is at least one and is never infinite. The inverse $A^{-1}$ is the unique two-sided inverse of $A$ (Invertible matrices and the general linear group ${\mathrm{GL}}_n(F)$), so $A{A}^{-1}=I_n$ and $A^{-1}A=I_n$. For rational finite $p$, submultiplicativity and normalisation are Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1. For $p=\mathrm{\infty }$, the same properties follow directly from the defining supremum: $\parallel Ax{\parallel }_{\mathrm{\infty }}\le \parallel A{\parallel }_{\mathrm{\infty }}\parallel x{\parallel }_{\mathrm{\infty }}$ and applying this estimate twice gives submultiplicativity, while $I_{n}x=x$ gives $\parallel I_n{\parallel }_{\mathrm{\infty }}=1$. Hence in either case

$1=\parallel I_n{\parallel }_p=\parallel A{A}^{-1}{\parallel }_p\le \parallel A{\parallel }_p\parallel A^{-1}{\parallel }_p={\kappa }_p(A)\mathrm{.}$

Equivalently, ${\kappa }_p(A)$ is the product of the largest factor by which $A$ stretches a nonzero vector and the largest factor by which $A^{-1}$ stretches one. Applying the same estimate to $A^{-1}$ in place of $A$ gives ${\kappa }_p(A^{-1})={\kappa }_p(A)$.

• The matrix must be square and invertible. For a rectangular or singular matrix $A$ there is no $A^{-1}$ in the sense of Invertible matrices and the general linear group ${\mathrm{GL}}_n(F)$ and the displayed product is not defined; the rectangular least-squares case uses the singular-value ratio ${\sigma }_{\max }\mathrm{/}{\sigma }_{\min }$ instead, as in For full-column-rank A, the normal equations square the spectral condition number.

• The subscript names the norm. ${\kappa }_1$, ${\kappa }_2$ and ${\kappa }_{\mathrm{\infty }}$ are different numbers attached to the same matrix; the dependence on the norm is genuine: for $A=\left(\begin{array}{ccc}1& 2& 0\\ 0& 3& 1\\ 0& 0& 4\end{array}\right)$ one has ${\kappa }_1(A)=5$ and ${\kappa }_{\mathrm{\infty }}(A)=22\mathrm{/}3$, while the diagonal rescaling $D=\mathrm{diag}(10,1,1)$ changes ${\kappa }_1$ from $5$ to $23$.

• A system is well or ill conditioned, an algorithm is stable or unstable. The condition number is a property of the problem $Ax=b$ and its norms; it is computed without any algorithm. The separate notion of stability is Forward and backward stability for a problem family under an arithmetic model.