# 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. (تلاشتون رو برای حل سوال نمایش بدید.) Commented Nov 2, 2013 at 19:23
• How can I type subscript and superscript in formulas? Commented Nov 2, 2013 at 19:40
• Did you test the hypothesis yourself? Commented Nov 2, 2013 at 19:44
• No. For last question you can find your answer in meta.math.stackexchange.com Commented 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 Commented Nov 2, 2013 at 19:49

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

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)? Commented 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)$. Commented 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? Commented Nov 18, 2013 at 22:35

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