Changes in singular values of matrix when rows are added

Question

I know that if a column is added to a matrix then the matrix largest signular value increases and the smallest singular value decreases. That is: Given matrix $A \in R^{m \text{x} n}$, $m>n$, and $z \in R^{m}$ then $$\sigma_{max}([A |z]) >= \sigma_{max}(A),$$ and $$\sigma_{min}([A |z]) <= \sigma_{min}(A),$$

But how do I show that when a row is added, the singular values of $A$ also change as follows: ($w \in R^{n}$)

$$\sigma_{n}(\left[\begin{matrix}A \\ w^{T} \end{matrix}\right])>=\sigma_{n}(A)$$

and $$\sigma_{1}(\left[\begin{matrix}A \\ w^{T} \end{matrix}\right])<=\sqrt{||A||_2^2 + ||w||_2^2}$$

Answer 1

Algebraic Pavel is wrong. Since $m>n$, the singular values of $A_1=\left[\begin{matrix}A \\ w^{*} \end{matrix}\right]$ are the square roots of the eigenvalues of $A_1^*A_1=A^*A+ww^*$. Clearly $A^*A+ww^*\geq A^*A$ that implies $\sigma_{max}(A_1)\geq \sigma_{max}(A)$ and $\sigma_{min}(A_1)\geq \sigma_{min}(A)$ (*).

For the second part (as Srinivas Eswar did) , $\sigma_{max}^2(A_1)=||A_1^*A_1||_2\leq ||A^*A||_2+||ww^*||_2=||A||_2^2+||w||_2^2$.

EDIT. Of course, the OP's inequality $\sigma_{min}([A |z]) \leq \sigma_{min}(A),$ is false. The correct inequality is $\sigma_{min}([A |z]) \geq\sigma_{min}(A)$. cf (*) above or consider the example: $A=[1],z=[2]$.

Answer 2

The singular values of $A$ are square roots of the eigenvalues of $AA^*$. Note that $$ \pmatrix{A\\w^*}\pmatrix{A\\w^*}^*=\pmatrix{AA^* & Aw\\w^*A^* & w^*w}. $$ So the question is equivalent to how do the eigenvalues of a symmetric (in this case also positive semidefinite) matrix change when we remove a row and a corresponding column. This is answered by the Cauchy interlacing theorem, which says (in the simplified form) that if $B$ is a symmetric matrix with eigenvalues $\beta_1\geq\beta_2\geq\cdots\geq\beta_n$ and $C$ is a principal submatrix of $B$ obtained by deleting a certain row and the corresponding column of $B$ with eigenvalues $\gamma_1\geq\gamma_2\geq\cdots\geq\gamma_{n-1}$, then $$ \beta_1\geq\gamma_1\geq\beta_2\geq\gamma_2\geq\cdots\geq\gamma_{n-1}\geq\beta_n. $$

Answer 3

I tried to solve the first part like so

Let $ B = \begin{bmatrix} A\\ w^T\end{bmatrix}$

Now

$ B^TB = A^TA + ww^T$

$ (B^TB)v_1 = \sigma_1^2(B)v_1$

$\implies \sigma_1^2(B)v_1 = (A^TA + ww^T)v_1$

$\implies \sigma_1^2(B)\frac{v_1}{\lVert v_1 \rVert} = (A^TA + ww^T)\frac{v_1}{\lVert v_1 \rVert}$

$\implies \lVert\sigma_1^2(B)\frac{v_1}{\lVert v_1 \rVert}\rVert = \lVert(A^TA + ww^T)\frac{v_1}{\lVert v_1 \rVert}\rVert$

$\implies \lVert\sigma_1^2(B)\rVert = \lVert(A^TA + ww^T)\rVert$

$\implies \lVert\sigma_1^2(B)\rVert \leq \lVert A^TA\rVert + \lVert ww^T\rVert$

$\implies \lVert\sigma_1^2(B)\rVert \leq \lVert A\rVert^2 + \lVert w\rVert^2$