Changes in singular values of matrix when rows are added 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}$$
 A: 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.
$$ 
A: 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$  
A: 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]$.
