# Showing the Relationship between singular values for two matrices

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

• I have edited it. Thanks Sep 7, 2021 at 14:13

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