3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Welcome to stackexchange if you write your works you will get more attention. (تلاشتون رو برای حل سوال نمایش بدید.) $\endgroup$ – Hoseyn Heydari Nov 2 '13 at 19:23
  • $\begingroup$ How can I type subscript and superscript in formulas? $\endgroup$ – 2012User Nov 2 '13 at 19:40
  • $\begingroup$ Did you test the hypothesis yourself? $\endgroup$ – Julien Nov 2 '13 at 19:44
  • $\begingroup$ No. For last question you can find your answer in meta.math.stackexchange.com $\endgroup$ – Hoseyn Heydari Nov 2 '13 at 19:48
  • $\begingroup$ 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 $\endgroup$ – 2012User Nov 2 '13 at 19:49
5
$\begingroup$

When $A$ and $B$ are square matrices, the inequality is true for every matrix norm (one that satisfies $\|AB\|\le \|A\|\,\|B\|$.) 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) $.

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – 2012User Nov 5 '13 at 0:25
  • 1
    $\begingroup$ @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)$. $\endgroup$ – user103402 Nov 5 '13 at 1:56
  • $\begingroup$ 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? $\endgroup$ – 2012User Nov 18 '13 at 22:35
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.