Showing the Relationship between singular values for two matrices

Question

Let $A\in \mathbb{C}^{m\times n}$ with $m> n,$ $z \in \mathbb{C}^{m\times 1}, \ B = [{A \ z}].$ Where $\sigma_i$ are the singular values.

Show:

(a) $\sigma_1 (B)\ge \sigma_1 (A)$ and

(b) $\sigma_{n+1}(B) \le \sigma_n (A)$

I tried solving part (a) but even with that I am not confident in my solution. I therefore, rely on benevolent members to give me a helping hand if possible, for (a) and (b).

I know that the singular value for $\|A\|_2 = \sigma_1$ and $\min_{x\not=0} = \frac{\|Ax\|_2}{\|x\|} = \sigma_p$

So, $\|B y\|_2 = \|U\Sigma V^* y\|_2 = \|\Sigma y\|_2 = \left[\sum_{i=1}^n (\sigma_i y_i)^2 \right]^\frac{1}{2} = \sqrt{\sigma_1^2 y_1^2 + \ldots + \sigma_m^2 y_m^2}.$

Then I conclude that $\sigma_1 (B) \ge \sigma_1(A)$

Answer 1

There's a relatively simple answer if you know about eigenvalue interlacing for Hermitian Matrices. You can simplify this by exploiting the fact that singular values are all real non-negative.

Since $B:=\bigg[\begin{array}{c|c|c|c|c}A & \mathbf z_m \end{array}\bigg]$, we have
$BB^* = AA^* + \mathbf z_m\mathbf z_m^*$
(use the outer product formulation of matrix multiplication to confirm this)
This has eigenvalues
$\gamma_{m}\leq \gamma_{m-1}\leq ... \leq \gamma_1$

The eigenvalues of a Hermitian matrix interlace with that of a rank-one PSD Hermitian update to said matrix. So we have
$\lambda_{m}\leq \gamma_{m}\leq \cdots \leq \lambda_{n+1}\leq \gamma_{n+1}\leq \lambda_n \leq \gamma_n\leq \cdots \leq \gamma_{m-1}\leq ...\lambda_1\leq \gamma_1$

taking square roots
$\lambda_1 \leq \gamma_1 \implies \sigma_1 (A)\leq \sigma_1 (B)$ and
$\gamma_{n+1}\leq \lambda_n\implies \sigma_{n+1}(B) \le \sigma_n (A)$

Footnote:
the non-zero singular values of an $m\times n$ matrix $Y$ are the given by the square roots of the non-zero eigenvalues of $YY^*$ or $Y^*Y$. Conventions vary somewhat but given that $A$ is tall and skinny we have $A=U\Sigma V^*$ with square (unitary) $U$ and $V$ with $\Sigma$ being $m\times n$ and thus having exactly $n$ elements on its diagonal -- i.e. $n$ singular values. Running essentially the same argument on $B$ tells us that it has exactly $n+1$ singular values. Thus values like $\lambda_m$ must be zero and don't directly map to singular values of $A$ -- they are 'filler'. A different way to finish this then is to take
$\lambda_{m}\leq \gamma_{m}\leq \cdots \leq \lambda_{n+1}\leq \gamma_{n+1}\leq \lambda_n \leq \gamma_n\leq \cdots \leq \gamma_{m-1}\leq ...\lambda_1\leq \gamma_1$

and observe that $AA^*$ and $A^*A$ have the same non-zero eigenvalues (and the same for $BB^*$ and $B^*B$) so checking dimensions this implies
$\gamma_{n+1}\leq \lambda_n \leq \gamma_n\leq \cdots \leq \gamma_{m-1}\leq ...\lambda_1\leq \gamma_1$
for the eigenvalues of $B^*B$ and $A^*A$ respectively. The square roots of these give the singular values of $B$ and $A$.