# Condition number of a block matrix

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$

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).
• 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!!! Nov 13, 2013 at 4:39
• 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? Nov 13, 2013 at 11:54
• More or less: $\max_{x\in S}(f(x)+g(x))\leq\max_{x\in S}f(x)+\max_{x\in S}g(x)$. Nov 13, 2013 at 16:27