Condition number of a product of two matrices

Question

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}||$$

Answer 1

I'd like to clarify this slightly: the reasoning in user103402's answer isn't quite clear in the case where the matrices are not square, and it can make you think that something false is true as shown in loup blanc's answer.$ \newcommand{\sig}{\operatorname{\sigma}} \newcommand{\R}{\mathbb R} \newcommand{\norm}[1]{\lVert #1 \rVert} $

Let $A \in \R^{m \times n}, B \in \R^{n \times p}$. Then the question becomes $$ \operatorname{cond}(AB) = \frac{\sig_1(A B)}{\sig_{\min(m,p)}(A B)} \stackrel{?}{\le} \frac{\sig_1(A)}{\sig_{\min(m,n)}(A)} \frac{\sig_1(B)}{\sig_{\min(n,p)}(B)} = \operatorname{cond}(A) \operatorname{cond}(B) .$$ $\sig_1(AB) \le \sig_1(A) \sig_1(B)$ always holds; the question is whether $$ \sig_{\min(m,p)}(AB) \stackrel{?}{\ge} \sig_{\min(m,n)}(A) \sig_{\min(n,p)}(B) .$$

If we assume that $m \ge n \ge p$, it holds. We can see this because:

• If $B$ has a nontrivial null space, $\sigma_p(B) = 0$ and the inequality holds trivially. So assume it doesn't.

• In general note that, if $C \in \mathbb R^{q \times r}$ with $q \ge r$, then $$ \sig_r(C) = \sqrt{\lambda_{\min}(C^T C)} = \sqrt{\inf_{x \in \R^r_*} \frac{x^T C^T C x}{x^T x}} = \inf_{x \in \R^r_*} \frac{\norm{C x}}{\norm x} $$ where $\R^r_* = \R^r \setminus \{0\}$.

• Then we can do, because $B x \ne 0$ for $x \ne 0$, \begin{align*} \sig_p(A B) & = \inf_{x \in \R^p_*} \frac{\norm{A B x}}{\norm x} \\& = \inf_{x \in \R^p_*} \frac{\norm{A B x} \norm{B x}}{\norm{B x} \norm{x}} \\&\ge \left( \inf_{x \in \R^p_*} \frac{\norm{A B x}}{\norm{B x}} \right) \left( \inf_{x \in \R^p_*} \frac{\norm{B x}}{\norm{x}} \right) \\&\ge \left( \inf_{y \in \R^n_*} \frac{\norm{A y}}{\norm{y}} \right) \left( \inf_{x \in \R^p_*} \frac{\norm{B x}}{\norm{x}} \right) \\& = \sig_n(A) \sig_p(B) .\end{align*}

It holds for $m \le n \le p$ as well by just transposing everything.

But $$ A = \begin{bmatrix}1 & 0\end{bmatrix} \qquad B = \begin{bmatrix}0 \\ 1\end{bmatrix} \qquad A B = \begin{bmatrix}0\end{bmatrix} \qquad A^T B^T = \begin{bmatrix}0 & 1 \\ 0 & 0\end{bmatrix} $$ gives us a counterexample for both $m \le n \ge p$ and $m \ge n \le p$.

Answer 2

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) $.

Answer 3

The inequality is false for non-square matrices.

$||.||$ denotes the matricial $2$-norm; if $U\in M_{p,n}\setminus \{0\}$, then we put $cond(U)=||U||||U^+||$ where $U^+$ is the Moore-Penrose inverse of $U$.

More precisely, let $\sigma_1\geq \cdots\geq \sigma_k > 0,\cdots,0$ be the singular values of $U$. Then $||U||=\sigma_1,||U^+||=1/\sigma_k$ and (with respect to the definition above) $cond(U)=\sigma_1/\sigma_k$.

Counter-example to $n\not= p,A\in M_{n,p},B\in M_{p,n},cond(AB)\leq cond(A)cond(B)$.

Take $n=2,p=4$ and $A=\begin{pmatrix}99&-95.001&-25&76\\99&-95&-25&76\end{pmatrix},B=\begin{pmatrix}10&-62\\-44&-83\\26&9\\-3&88\end{pmatrix}$.

Note that $A$ is ill conditioned.

For more details, see my answer in

Counter example or proof that $\kappa(AB) \leq \kappa(A)\kappa(B) $