# Bounds for singular values of block matrices

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

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