Largest value of $\mathbf x^{\mathrm T} \mathbf V \mathbf x$ at condition $\mathbf x^{\mathrm T} \mathbf x = 1$; here $\mathbf V$ is +ve definite

Question

Question: Consider positive definite matrix $\mathbf V$ of dimension $p × p$ is given. Determine the largest value of $\mathbf x^{\mathrm T} \mathbf V \mathbf x$ at condition $\mathbf x^{\mathrm T} \mathbf x = 1$ and describe the vector $\mathbf x \in \mathbb R^p$ for which this largest value is realized.

I have no idea how to deal with it.

My guess: I suppose only that formula $\mathbf x^{\mathrm T} \mathbf V \mathbf x = \mathrm{trace}(\mathbf V \mathbf x \mathbf x^{\mathrm T})$ may be useful. However, I am not very sure.

Any hints will be much appreciated!

Answer 1

We can assume that $V$ that symmetric. All symmetric matrices can be factorized as follows

$ V = R D R^T $

where $D$ is a diagonal matrix of eigenvalues, and $R$ is orthogonal (i.e. $R^T R = R R^T= I$ ) and its columns are the eigenvectors corresponding to the diagonal entries of $D$. Since $V$ is positive definite, then all the diagonal entries of $D$ are positive.

Now,

$x^T V x = x^T R D R^T x = y^T D y $

where $ y = R^T x $ , i.e. $x = R y $

If $ x^T x = 1 $ then $ y^T R^T R y = y^T y = 1 $

So,

$ f = x^T V x = y^T D y = \displaystyle \sum_{i=1}^n D_{ii} y_i^2 $

Now, we want to maximize $f$ subject to $ \displaystyle \sum_{i=1}^p y_i^2 = 1 $

The corresponding Lagrange multiplier function is

$ f = y^T D y + \sigma (y^T y - 1 ) $

Take the gradient of this function with respect to the vector $y$

$ \nabla_y f = 2 D y + \sigma ( 2y ) = 0 $

and take the derivative of the function with respect to $\lambda$

$ f_{\sigma} = y^T y - 1 = 0 $

From the first equation,

$ (D + \sigma I) y = 0 $

This is the well-known eigenvalue-eigenvector equation, it has $p$ solutions. That is, there are $p$ possible values for $\sigma$ which are the negative of the eigenvalues of $D$, i.e. $\sigma_i = - \lambda_i$. Using the second equation, it follows that the $y$'s must be the corresponding unit eigenvectors of $D$. Substitute these solutions into $f$, and remember that for each solution, $y^T y - 1=0$, then

$ f = y^T D y $

Since $y$ is an eigenvector of $D$ corresponding to $ \lambda_i = - \sigma_i $, then

$f = y^T (\lambda_i) y = \lambda_i y^T y = \lambda_i $

Therefore, the maximum of $f$ is the maximum eigenvalue of $D$ (which is the maximum eigenvalue of $V$) and this maximum is achieved when $y$ the eigenvector of $D$ corresponding to this maximum eigenvalue. Now since

$ D \ y = \lambda_{Max} \ y $

Then

$ D \ R^T \ x = \lambda_{Max} \ R^T x $

so that

$ R D R^T \ x = \lambda_{Max} \ x $

i.e.

$ V \ x = \lambda_{Max} \ x $

That is to say the maximizing vector $x$ of $f$, is the eigenvector of $V$ corresponding to the maximum eigenvalue of $V$.