Smallest singular value of a matrix.

Question

Let $A\in\mathbb{R}^{m\times n}$ be a matrix and $\sigma_n$ be its smallest singular value. Prove that $$\sigma_n^2=\min_{x\neq 0} \frac{x^TA^TAx}{x^Tx}.$$ From Proving that the norm of a Matrix is bigger or equal to it's smallest singular value multiplied by a vector., I know that $$\sigma_n^2\leq \frac{x^TA^TAx}{x^Tx}\ \text{for all}\ x \neq 0.$$ How to prove that minimum is actually attained?

Answer 1

$\def\p#1#2{\frac{\partial #1}{\partial #2}}$ Given a symmetric matrix $M$, consider the scalar function $$\mu(x) = x^TMx \quad\implies\quad \p{\mu}{x} = 2\,Mx$$ The objective function is a ratio of such functions, therefore $$\eqalign{ \lambda &= \frac{x^TA^TAx}{x^Tx} \;\doteq\; \frac{\alpha}{\beta} \\ \p{\lambda}{x} &= 2\beta^{-1}(A^TAx-\lambda x) \\ }$$ Setting the gradient to zero yields an eigenvalue equation, whose solutions are the extrema of the objective $$\eqalign{ A^TAx &= \lambda x \\ }$$ Since $(A^TA)$ is SPD, its eigenvalues and singular values coincide. So the minimum of the objective function corresponds to the smallest singular value.