Linear Algebra – Condition Number of a Product of Two Matrices

condition numberlinear algebramatricesnormed-spaces

Given two square matrices $A$ and $B$, is the following inequality
$$\operatorname{cond}(AB) \leq \operatorname{cond}(A)\operatorname{cond}(B),$$ where $\operatorname {cond}$ is the condition number, true?

Is this still true for rectangular matrices?

I know this is true:

$$||AB|| \leq ||A|| \cdot ||B||$$

The definition of condition number of matrix is as follows:

$$\operatorname{cond}(A)=||A|| \cdot ||A^{-1}||$$

Best Answer

When $A$ and $B$ are square matrices, the inequality is true for every matrix norm (which satisfies $\|AB\|\le \|A\|\,\|B\|$, by definition.) Indeed, $$ \operatorname{cond}(AB)=\|AB\|\,\|(AB)^{-1} \| \le \|A\|\,\|B\|\,\|B^{-1}\|\,\|A^{-1} \| =\operatorname{cond}(A)\,\operatorname{cond}(B) $$ If $A$ and $B$ are non-square, then $A^{-1}$ is not meaningful, and the condition number has to be defined differently. The one definition I know for this case (which agrees with the above when the operator norm is used), is $$ \operatorname{cond}(A)=\frac{\sigma_1(A)}{\sigma_n(A)} = \frac{\max\{|Ax|:|x|=1\}}{\min \{|Ax| : |x|=1\}} $$ (Here $\sigma_1$ and $\sigma_n$ are the greatest and smallest singular values of $A$, defined in the quotient on the right). This definition is of interest only when the kernel is trivial. The submultiplicative inequality still holds, because $\sigma_1(AB)\le \sigma_1(A)\sigma_1(B)$ and $\sigma_n(AB)\ge \sigma_n(A)\sigma_n(B) $.