Bounds for singular values of block matrices

Question

Let \begin{align} M = \begin{pmatrix} A \\ v^T \end{pmatrix} \end{align} with $A \in \mathbb{R}_{\geq 0}^{n \times k}$, $n\geq k$, $\text{rank}(A) = k$, and $v^T \in \mathbb{R}_{\geq 0}^{1 \times k}$. Moreover, I know bounds for the sum of every row $A_i$ of $A$ and for $v^T$, i.e., \begin{align} \varepsilon &\leq \sum_j A_{i,j} \leq \sqrt{2} \quad \forall i=1,...,n \\ \varepsilon &\leq \sum_jv^T_j \leq \sqrt{2} \end{align}

I'm interested in the condition number of $M$, i.e. \begin{align} \text{cond}(M) := \frac{\sigma_{max}(M)}{\sigma_{min}(M)}, \end{align} where $\sigma_{max}(M)$ and $\sigma_{min}(M)$ represent the largest and smallest non-zero singular value of $M$, respectively.

Question

Is it possible to bound $\text{cond}(M)$ by information that I have regarding $A$ and $v^T$? It seems (numerical experiment) that \begin{align} \text{cond}(A) \not \leq \text{cond}{M}, \end{align} which I hoped for at first. I guess it makes sense that this does not hold true; I'd have to include information regarding $v^T$. The relation $\sigma_k(M) = \sqrt{\lambda_k(M^T M )} = \sqrt{\lambda_k(A^T A + vv^T )} $ seems useful but didn't help me. Even with (I hope this is correct) \begin{align} \sigma_{max}(M) \leq \sigma_{max}(A) + \sigma_{max}(v^T) = \sigma_{max}(A) + ||v^T||_2 \end{align} I only have an upper bound for the enumerator, but no lower bound for the denominator (of the expression for the condition number).

Answer 1

Your upper bound is correct, but we can do better. In particular, for any $x \in \Bbb R^k$, we have $$ \|Mx\|_2^2 = \left\|\pmatrix{A \\ v^T} x \right\|_2^2 = \left\|\pmatrix{Ax \\ v^Tx} \right\|_2^2 = \|Ax\|_2^2 + \|v^Tx\|_2^2 \leq [\sigma_\max(A)^2 + \|v\|_2^2] \cdot \|x\|_2^2. $$ With that, we can conclude that $$ \sigma_\max(M) = \max_{x \neq 0} \frac{\|Mx\|_2}{\|x\|_2} \leq \sqrt{\sigma_\max(A)^2 + \|v\|_2^2}. $$ We can apply a to get the lower bound $\sigma_\max(M) \geq \max\{\|v\|_2, \sigma_\max(A)\}$.

For lower bounds, we can apply similar ideas. Note that $\sigma_\min(M) = \min_{x \neq 0} \frac{\|Mx\|_2}{\|x\|_2}$. Using the ideas above, we can reach the conclusion that $$ \sigma_\min(A) \leq \sigma_\min(M) \leq \sqrt{\sigma_\min(A)^2 + \|v\|_2^2}. $$ Putting everything together, we can conclude that $$ \frac{\sigma_\max(A)}{\sqrt{\sigma_\min(A)^2 + \|v\|_2^2}}\leq \operatorname{cond}(M) \leq \frac{\sqrt{\sigma_\max(A)^2 + \|v\|_2^2}}{\sigma_\min(A)}. $$