2

I'm looking for a clarification of an answer to

Showing that $x^{\top}Ax$ is maximized at $\max \lambda(A)$ for symmetric $A$

(This is a clarified formulation of my original question which I deleted)

The question at the given link asks for a proof that

Given a $n \times n$ symmetric matrix $A$,

$$ \max_{x : ||x||_2 = 1} x^{\top}Ax = \max \lambda(A), $$

where $\max \lambda(A)$ is the maximum eigenvalue of $A$.

I've approached solving the problem in exactly the same way as @Ryan at the above page. The main point is in the upper bound introduced as: $$ x^{\top}Ax = \sum_{i=1}^n \lambda_i \tilde{x}_i^2 \le \max \lambda(A)\sum_{i=1}^n \tilde{x}_i^2 $$

and this is correct.

However, this proves only that $ x^{\top}Ax \le \max \lambda(A),$ but not the original statement $$ \max_{x : ||x||_2 = 1} x^{\top}Ax = \max \lambda(A)$$

dnqxt
  • 1,227
  • 7
  • 7
  • 3
    The usual Lagrange multipliers proof (on the unit sphere) shows that at a maximum point $x$ (which must occur by compactness and continuity), $Ax=\lambda x$ for some constant $\lambda$. This, of course, means that $x$ is an eigenvector with eigenvalue $\lambda$. – Ted Shifrin Mar 06 '19 at 22:50
  • This exactly clarifies it! Many thanks. Only a true mathematician could answer this, and I'm not the one :) – dnqxt Mar 06 '19 at 22:58
  • 1
    You're welcome. Feel free to check out my various lectures on YouTube (linked in my profile) on multivariable calculus and linear algebra. – Ted Shifrin Mar 06 '19 at 23:24

3 Answers3

4

If $A$ is symmetric, then its eigenvalues are real. Moreover, we have (Rayleigh coefficient) $$ \frac{x^TAx}{||x||^2} = \lambda $$ and since $||x||^2=1$, we get $x^T A x = \lambda$. So, $$ \max_{||x||^2 = 1} x^T A x = \max \lambda. $$

Learn_and_Share
  • 1,060
3

Mazimize $x^TAx$, s.t. $x^Tx=1$. Using Lagrange multiplier $\lambda$ we have $$ \arg\max_{x}( x^TAx - \lambda( x^Tx-1)) $$ so taking derivative w.r.t. vector $x$ and equating to zero we have $$ 2Ax-2\lambda x=0 \to Ax=\lambda x. $$ Namely, the set of solutions of this maximization problem should satisfy $ Ax = \lambda x$, i.e., such vectors $x$s are vectors that multiplying $A$ by $x$ is the same as multiplying $x$ by a scalar. That is, by definition $x$ have to be the eigenvectors and thus $\lambda$ its corresponding eigenvalue. Now, you have a set of solutions $\{(\lambda_i, x_i)\}_{i=1}^n$ and you have to choose the pair the maximize the original function, so clearly $\max x^TAx = x ^T \lambda_{\max} x = \lambda_{\max} x^T x = \lambda_{\max}.$

Learn_and_Share
  • 1,060
V. Vancak
  • 16,444
0

Are you sure about this statement "then realized that only the strict inequality is justified in front of the upper bound."?

Take for example $A=I$

user605486
  • 1,062