# 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}$$

• Adding a row to $A$ can be treated as adding a column to $A^T$ and we know that $A$ and $A^T$ have same singular values. Commented Mar 20, 2015 at 14:47
– Tony
Commented Sep 27, 2017 at 2:51

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

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

• But the theorem requires that $B$ and $C$ are both square matrix. In this case, $A$ is NOT. $A \in R^{m \text{x} n}$ Commented Mar 21, 2015 at 23:48
• Never mind. Sorry. I got it now. Commented Mar 21, 2015 at 23:54
• @abcXYZ Actually I'm not sure now if you should accept this answer. I've found that it actually does not answer it :) (or it does just a half of it) Commented Mar 21, 2015 at 23:59
• It gave me the most important idea to solve the entire problem :D Thanks so much!!! Commented Mar 22, 2015 at 0:02

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$