# 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

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

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