1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ $g(x) = x^T x = x^T I x$ for $I$ the square identity matrix. You need the gradient of $g,$ then solve $\nabla f = \lambda \nabla g$ under the constraint $g=1.$ By the way, actually $\nabla f = 2 A x$ as a column. $\endgroup$ – Will Jagy Apr 14 '14 at 20:35
  • $\begingroup$ Thank you- so from here I get $2A\mathbf x = \lambda 2 \mathbf x$ which we can cancel the 2's to get $A \mathbf x = \lambda \mathbf x$ which will give us $A = \lambda$ which means that the symmetric matrix A will just be the eigenvalues? I'm not sure if I'm drawing correct conclusions. $\endgroup$ – user2553807 Apr 14 '14 at 20:43
  • 1
    $\begingroup$ I don't know why you write $A = \lambda,$ the first refers to a square matrix and the second refers to a single real number. $Ax = \lambda x$ is correct, this is precisely the eigenvalue/eigenvector equation, and for symmetric matrices $\lambda$ will always be real. $\endgroup$ – Will Jagy Apr 14 '14 at 20:47
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The elements $x$ are matrices. Is one is allowed, mathematically, to take $\partial L/\partial x$. How does one define the derivation of a matrix by a matrix? Is that a well defined mathematical operation? $\endgroup$ – Alexandre H. Tremblay May 9 at 15:52
0
$\begingroup$

$g(x) = x^T x$ hence $\nabla g = 2x$.

$\endgroup$
  • $\begingroup$ $\nabla g = 2 x$ $\endgroup$ – Will Jagy Apr 14 '14 at 20:37
  • $\begingroup$ $2x$$\mbox{}$ $\ $ $\endgroup$ – Dirk Apr 14 '14 at 20:38
  • $\begingroup$ sure... I was mislead by the OP $\endgroup$ – Emanuele Paolini Apr 15 '14 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.