7
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Srinivas K
    Mar 20, 2015 at 14:47
  • $\begingroup$ Please see the related question I just asked. math.stackexchange.com/questions/2446797/… $\endgroup$
    – Tony
    Sep 27, 2017 at 2:51

3 Answers 3

12
+200
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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}$ $\endgroup$
    – AbcXYZ
    Mar 21, 2015 at 23:48
  • $\begingroup$ Never mind. Sorry. I got it now. $\endgroup$
    – AbcXYZ
    Mar 21, 2015 at 23:54
  • $\begingroup$ @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) $\endgroup$ Mar 21, 2015 at 23:59
  • $\begingroup$ It gave me the most important idea to solve the entire problem :D Thanks so much!!! $\endgroup$
    – AbcXYZ
    Mar 22, 2015 at 0:02
3
$\begingroup$

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$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .