4
$\begingroup$

Let $\mbox{cond} (M) := \frac{\sigma_1 (M)}{\sigma_n (M)}$ be the condition number of matrix $M$. Is $$\mbox{cond} ([A,B]) \leq \mbox{cond}(A) + \mbox{cond}(B)$$

true? And is this true for $n \times m$ rectangular matrices? Let's consider $3$ different cases:

  1. $n<m$

  2. $n=m$

  3. $n>m$

$\endgroup$

1 Answer 1

7
$\begingroup$

This could be true if $n\leq m$ at least in the case when all matrices involved have full rank equal to $n$. Because the singular values of $[A,B]$ are the square roots of the eigenvalues of $AA^T+BB^T$, then we have $$ \begin{split} \sigma_n^2([A,B]) &= \lambda_n(AA^T+BB^T) =\min_{\|x\|_2=1}x^T(AA^T+BB^T)x\\&\geq\min_{\|x\|_2=1}x^TAA^Tx=\lambda_n(AA^T)=\sigma_n^2(A) \end{split} $$ Similarly, $$ \begin{split} \sigma_n^2([A,B]) &= \lambda_n(AA^T+BB^T) =\min_{\|x\|_2=1}x^T(AA^T+BB^T)x\\&\geq\min_{\|x\|_2=1}x^TBB^Tx=\lambda_n(BB^T)=\sigma_n^2(B) \end{split} $$ and hence $$ \sigma_n([A,B])\geq\max\{\sigma_n(A),\sigma_n(B)\}. $$ Similarly, variational characterisation of singular values also implies that $$ \sigma_1^2([A,B])\leq\sigma_1^2(A)+\sigma_1^2(B). $$ Indeed, $$ \begin{split} \sigma_1^2([A,B]) &= \lambda_1(AA^T+BB^T) =\max_{\|x\|_2=1}x^T(AA^T+BB^T)x\\&\leq\max_{\|x\|_2=1}x^TAA^Tx+\max_{\|x\|_2=1}x^TBB^Tx=\lambda_1(AA^T)+\lambda_1(BB^T)\\&=\sigma_1^2(A)+\sigma_1^2(B) \end{split} $$ Hence $$ \mathrm{cond}^2([A,B])\leq\frac{\sigma_1^2(A)+\sigma_1^2(B)}{\max\{\sigma_n^2(A),\sigma_n^2(B)\}}\leq\frac{\sigma_1^2(A)}{\sigma_n^2(A)}+\frac{\sigma_1^2(B)}{\sigma_n^2(B)}\leq\mathrm{cond}^2(A)+\mathrm{cond}^2(B) $$ and $$ \mathrm{cond}([A,B])\leq\sqrt{\mathrm{cond}^2(A)+\mathrm{cond}^2(B)} \leq\mathrm{cond}(A)+\mathrm{cond}(B). $$

For $n>m$, it's generally not true (still assuming full rank of both $A$, $B$, and $[A,B]$). As an extreme example, take $m=1$. Then $\mathrm{cond}(A)=\mathrm{cond}(B)=1$ but $\mathrm{cond}([A,B])$ can be arbitrarily large. Consider, e.g., $A=[1,0]^T$ and $B=[1,0.001]^T$.

The rank-deficient case is a bit more difficult if you considered $\mathrm{cond}(A)=\sigma_1(A)/\sigma_r(A)$, where $r$ is the rank of $A$ (this is how the condition number is usually defined when $A$ does not have full rank). The trouble here is not with the upper bound on $\sigma_1([A,B])$ but with the lower bound which does not generally hold. Again, as an extreme example, consider $A$ and $B$ of the case 1) and 2) and augment them with a sufficient number of zero rows to convert it to the case 3) (which we know where the statement is false).

$\endgroup$
21
  • $\begingroup$ What did you mean by the big bracket?, Sum of them? Is this what you meant? $min_{\|x\|=1}$$[ x^T(AA^T)x+x^T(BB^T)x ]$ $\geq$ $\sigma_n^2(A)$+ $\sigma_n^2(B)$ $\geq$$max$ {$\sigma_n^2(A)$ , $\sigma_n^2(B)$} which leaves $min$ {$a+b$} $\geq$ $min$ {$a$} + $min$ {$b$} $\geq$ $max$ {$min${$a$},$min${$b$}} I don't get it!!! $\endgroup$
    – 2012User
    Nov 13, 2013 at 4:39
  • $\begingroup$ @User1986 I thought it was obvious since you accepted the answer already :D I've edited the answer to make it less "compact" and avoid the confusion. $\endgroup$ Nov 13, 2013 at 10:39
  • $\begingroup$ Thank You again :) How do you conclude: $\sigma_n([A,B])$$\geq$$max$ {$\sigma_n(A)$ , $\sigma_n(B)$} ==> $\sigma_n([A,B])$$\leq$$min$ {$\sigma_n(A)$ , $\sigma_n(B)$} for the inequality to be true? $\endgroup$
    – 2012User
    Nov 13, 2013 at 11:54
  • 1
    $\begingroup$ Edited... I've just realised that the sum of cond's can be replaced by the square root of the sum of their squares, leading to a possible improvement. $\endgroup$ Nov 13, 2013 at 15:53
  • 1
    $\begingroup$ More or less: $\max_{x\in S}(f(x)+g(x))\leq\max_{x\in S}f(x)+\max_{x\in S}g(x)$. $\endgroup$ Nov 13, 2013 at 16:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .