Largest Singular value of a Matrix

Question

Prove that if $A\in \mathbb{R}^{m\times n}$, then

$$\sigma_{\text{max}} (A) = \underset{y\in\mathbb{R}^m\\x\in \mathbb{R}^n}{\text{max}}\frac{y^TAx}{\Vert{x}\Vert_2\Vert y\Vert_2}.$$

Answer 1

First note that using the Cauchy-Schwarz inequality, we have (for nonzero $x$ and $y$) $$ \frac{y^TAx}{\|x\|_2\|y\|_2}\leq\frac{\|y\|_2\|Ax\|_2}{\|y\|_2\|x\|_2}=\frac{\|Ax\|_2}{\|x\|_2}. $$ If one picks $y=Ax$, it gives $$ \left.\frac{y^TAx}{\|x\|_2\|y\|_2}\right|_{y=Ax}=\frac{x^TA^TAx}{\|x\|_2\|Ax\|_2} =\frac{\|Ax\|_2^2}{\|x\|_2\|Ax\|_2}=\frac{\|Ax\|_2}{\|x\|_2}. $$ Since the quotient can be bounded from above independently of $y$ and this bound is attained by some $y$, we have that $$ \max_{x,y}\frac{y^TAx}{\|x\|_2\|y\|_2}=\max_{x}\frac{\|Ax\|_2}{\|x\|_2}. $$ Now this is the standard variational characterisation of $\sigma_{\max}(A)$: $$ \max_x\frac{\|Ax\|_2^2}{\|x\|_2^2}=\max_x\frac{x^T(A^TA)x}{x^Tx}=\lambda_{\max}(A^TA)=\sigma_{\max}^2(A). $$