I've read both of
Prove that the largest singular value of a matrix is greater than the largest eigenvalue and Singular value proofs 2.)
However, the later question is asked about nonsingular matrix A.
And in my case the question is about general case(any matrix A).
I'm reading the following file containing the proof:
http://math.mit.edu/classes/18.095/2016IAP/lec2/SVD_Notes.pdf
page 389, (9th page), section "worked examples", example 7.1.B
But I need more detailed explanations in:
$$\left\lVert A\mathbf x \right\rVert = \left\lVert U\Sigma V^T\mathbf x \right\rVert=\left\lVert \Sigma V^T\mathbf x \right\rVert \le \sigma_1\left\lVert V^T\mathbf x \right\rVert=\sigma_1\left\lVert \mathbf x \right\rVert$$
the tricky part for me is:
$$\left\lVert \Sigma V^T\mathbf x \right\rVert \le \sigma_1\left\lVert V^T\mathbf x \right\rVert$$
Maybe I'm just tired, but I can't understand why this inequality is true.
$\Sigma$ is m by n(matrix of singular values), $\sigma_1$ is the largest singular value of A. A is m by n, V is n by n, U is m by m.
Best Answer
Just to clarify the "tricky part," $\Sigma$ is a "diagonalized" matrix containing the singular values $\sigma_1$, $\sigma_2$, ... $\sigma_n$ where by the problem statement we take $\sigma_1$ to be the largest of these values $\left(\sigma_1\geq\sigma_2\geq\dots\geq\sigma_n\geq 0\right)$. The vector $V^T \bf{x}$ is then multiplied by the diagonal matrix $\Sigma$ such that \begin{align*} \left\Vert\Sigma V^T \textbf{x}\right\Vert &= \left\Vert\begin{pmatrix} \sigma_1 & 0 & \dots & 0 \\ 0 & \sigma_2 &\dots &0 \\ \vdots &\vdots & \ddots & \vdots \\ 0 &0& \dots & \sigma_n \end{pmatrix} V^T \textbf{x}\right\Vert \\ & \leq \left\Vert\begin{pmatrix} \sigma_1 & 0 & \dots & 0 \\ 0 & \sigma_1 &\dots &0 \\ \vdots &\vdots & \ddots & \vdots \\ 0 &0& \dots & \sigma_1 \end{pmatrix} V^T \textbf{x}\right\Vert \\ &= \left\Vert\sigma_1\begin{pmatrix} 1 & 0 & \dots & 0 \\ 0 & 1 &\dots &0 \\ \vdots &\vdots & \ddots & \vdots \\ 0 &0& \dots & 1 \end{pmatrix} V^T \textbf{x}\right\Vert \\ &= \vert\sigma_1\vert\left\Vert V^T\textbf{x}\right\Vert \\ &=\sigma_1 \left\Vert V^T\textbf{x}\right\Vert \end{align*}
I hope this helps you understand the proof.