Suppose A is a symmetric matrix. Show that the maximum and minimum of $\mathbf x ^T A \mathbf x$ subject to the constraint $\mathbf x ^T \mathbf x=1$ are the maximum and minimum eigenvalues of A.
I haven't had much experience with Lagrange multipliers so my ideas written below might be off. Please feel free to help me sort through things!
A symmetric implies $A^T = A$ and $A^{-1}A^T=1$
Here are my ideas- I'm not sure if I'm on the right track…
I need to find $\nabla f=-\lambda \nabla g$ and I know that if if $f(x) = \mathbf x ^T A \mathbf x$ then $\nabla f= A \mathbf x$ and $g(x) = 1$ (the $g(x)$ is the constraint, right?) so then I will get $A \mathbf x = -\lambda$.
Any help would be great! Thanks.
Best Answer
Let's form the Lagrangian first:
$$L(x,\lambda)=x^TAx-\lambda x^Tx-\lambda=x^T(A-\lambda I)x-\lambda$$
Now, if you take derivative with respect to $x$, and set to zero you get:
$$\frac{\partial}{\partial x}L(x,\lambda)=\frac{\partial}{\partial x} (x^TAx-\lambda x^Tx-\lambda)=2(A-\lambda I)x=0$$
$$\Rightarrow Ax=\lambda x$$
Therefore, $\lambda $ should be the eigen value of $A$, and $x$ should be an eigen vector.
Now, w.l.g, let $\lambda_1\geq \lambda_2\geq\ldots\geq\lambda_n$, be the eigenvalues of $A$, and $x_1,x_2,\ldots,x_n$ be the corresponding eigenvectors, then you have:
$$Ax_i=\lambda_i x_i$$ $$\Rightarrow x_i^TAx_i=x_i^T\lambda_i x_i=\lambda_i x_i^Tx_i=\lambda_i.1=\lambda_i$$
Therefore, $x_1^TAx_1=\lambda_1$ is the maximum achievable value, and $x_n^TAx_n=\lambda_n$ is the minumum.