# Is $\sigma_n \|x\|_2 \leq \|Ax\|_2 \leq \sigma_1 \|x\|_2$?

It is known that if $A \in \mathbb{R}^{n \times n}$ has singular values $\sigma_1 \geq ... \geq \sigma_n$ then $\|Ax\|_2 \leq \|A\|_2\|x\|_2 = \sigma_1\|x\|$.

Is the "opposite" also true? I.e., is $\|Ax\|_2 \geq \sigma_n\|x\|_2$ ?

## 3 Answers

Yes.

Recall that by the singular value decomposition, $A = USV^T$, where $U$ and $V$ are unitary. Since unitary matrices like $U^T$ are rotations, and rotations preserve lengths, $|Ax| = |U^T Ax| = |SV^T x|$. Now since $x$ can be split into a linear combination of rows of $V$, $|SV^T x|$ is smallest when $x$ is a multiple of the row corresponding to $\sigma_n$, and largest when $x$ is the a multiple of the row corresponding to $\sigma_1$. So $\sigma_n |x| \le |Ax| \le \sigma_1 |x|$.

The singular values of $A$ are square roots of the eigenvalues of $A^TA$, which is positive semidefinite. That is, $\sigma_n = \sqrt{\lambda_n}$ where $\lambda_n$ is the smallest eigenvalue of $A^TA$. We have $$\lambda_n = \min_{\|x\|=1}x^TA^TAx = \min_{\|x\|=1} \|Ax\|_2^2$$ thus $$\sigma_n = \min_{\|x\|=1}\|Ax\|_2$$ The conclusion should be immediate then.

Let me explain more detail for @Timur's answer.

Consider SVD decomposition

$$A = USV^T$$ therefore $$U^TA = SV^T$$

we know that $$U$$ and $$V$$ are unit orthogonal matrix,and orthogonal transformation did not change the euclidian distance.

that is

$$||Ax|| = ||U^TAX|| = ||SV^Tx||$$

our main concern become $$||SV^Tx||$$

notice V is n by n Full rank matrix

and $$\boldsymbol{v_{r1}},\boldsymbol{v_{r2}},...,\boldsymbol{v_{rn}}$$ are the row vector of V.

therefore:

$$x = k_1\boldsymbol{v_{r1}} + ...+ k_n\boldsymbol{v_{rn}}$$ $$V^Tx = k_1V^T\boldsymbol{v_{r1}} + ...+ k_nV^T\boldsymbol{v_{rn}}=(k_1,k_2,...k_n)^T$$

left multiply an $$S$$

$$SV^Tx = S(k_1,k_2,...k_n)^T = (\sigma_1k_1, \sigma_2k_2, ...,\sigma_nk_n)^T$$

we know that $$\sigma_1$$ is the largest singular value of A

$$||SV^Tx|| = ||(\sigma_1k_1, \sigma_2k_2, ...,\sigma_nk_n)^T|| <= ||(\sigma_1k_1, \sigma_1k_2, ...,\sigma_1k_n)^T|| = \sigma_1 ||V^Tx||$$

Again, orthogonal transform action did not change the distance.

$$||V^Tx|| = ||x||$$

combine the last two formula

$$||Ax|| = ||SV^Tx|| <= \sigma_1||x||$$

the $$\sigma_n$$ term can be proved similarly.

• Why do you think we should be looking at $\sigma_r$ instead of $\sigma_n$? In fact, if $A$ fails to have full rank, then the best we can do on the left side of the inequality is $0$. Jul 31, 2016 at 11:17
• you are right. I should edit my answer.
– Long
Jul 31, 2016 at 13:04