Condition number of a product of two matrices

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

• Welcome to stackexchange if you write your works you will get more attention. (تلاشتون رو برای حل سوال نمایش بدید.) Nov 2, 2013 at 19:23
• How can I type subscript and superscript in formulas? Nov 2, 2013 at 19:40
• Did you test the hypothesis yourself? Nov 2, 2013 at 19:44
• No. For last question you can find your answer in meta.math.stackexchange.com Nov 2, 2013 at 19:48
• Yes, I ran this code in matlab many times. It's always true.for i=1:10 b=rand(3); a=rand(3); [cond(b)*cond(a) cond(a*b)] end Nov 2, 2013 at 19:49

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

• Thank You. But I'm pretty sure the submultiplicative inequality of condition number doesn't hold for rectangular matrices. Is there a proof for σn(AB)≥σn(A)σn(B)? Nov 5, 2013 at 0:25
• @Abbas For every unit vector $x$, $|Bx|\ge \sigma_n(B)$. Letting $y=Bx$, we get $|Ay|\ge \sigma_n(A) |y|$. Hence, $|ABx|\ge \sigma_n(A)\sigma_n(B)$. Nov 5, 2013 at 1:56
• Hi user103402. How did you conclude this? : $\sigma_n(A)\leq\frac{\|Ay\|}{\|y\|}$ ,(where $y$ is not necessarily a unit vector). and if we take that for granted we have: $\sigma_n(A).\|Bx||\leq\|ABx\|$ of course we can say $\sigma_n(A).\sigma_n(B)\leq\|ABx\|$ how does it make $\sigma_n(A).\sigma_n(B)\leq \sigma_n(AB)$ possible? Nov 18, 2013 at 22:35


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

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