Linear Algebra – How to Maximize the Value of $v^{T}Av$

eigenvalues-eigenvectorslinear algebranon-convex-optimizationqcqp

Let $A$ be a symmetric, real matrix. The goal is to find a unit vector $v$ such that the value $v^{T}Av$ is

  1. maximized, and
  2. minimized.

The answer is that $v$ should be the eigenvector of $A$ with

  1. largest eigenvalue, and
  2. smallest eigenvalue.

Could anyone give an explanation why? What do eigenvectors have to do with maximizing such a number?

Please make it as 'step by step' as possible, express it using very basic algebra (if possible). I don't quite understand MooS' answer.

Best Answer

There is an orthogonal matrix $T$, such that $T^tAT$ is diagonal.

Because of $v^t(T^tAT)v=(Tv)^tA(Tv)$ and $\|Tv\|=\|v\|$ one can $A$ assume to be diagonal and in this case the assertion is immediate, since $v^tAv = \sum_{i} v_i^2\lambda_i$ with the $\lambda_i$ being the diagonal elements (eigenvalues).

Let me provide some more details:

First of all we show $\|Tv\|=\|v\|$: We have $T^tT=1$ (by definition), hence $$\|Tv\|^2=(Tv)^t(Tv)=v^t(T^tT)v=v^tv=\|v\|^2$$

For the rest: We have to consider the numbers $v^tAv$, where $v$ runs through all vectors of length $1$. Since $T$ is orthogonal, it is a bijection on the unit sphere by our above argument, hence $Tv$ runs through all vectors of length $1$, if $v$ does so.

So considering the numbers $v^tAv$ is the same as considering the numbers $(Tv)^tA(Tv)$. Now the computation $$(Tv)^tA(Tv) = v^t(T^tAT)v$$ shows that we have to consider the numbers $v^t(T^tAT)v$, where $v$ runs through all vectors of length $1$. Since $T^tAT$ is diagonal, we are in the starting situation, but the matrix is diagonal now. So we could have assumed from the start that $A$ is diagonal, hence $A = \mathrm{diag}(\lambda_1, \dotsc, \lambda_n)$.

But in this case, the result is easy, since we have $v^tAv = \sum_{i} v_i^2\lambda_i$. Maximizing or minimizing this expression with respect to $\sum_i v_i^2=1$ is an easy task: The minimum is the minimal $\lambda_i$ and the maximum is the maximal $\lambda_i$.

You should really get used to such 'diagonalization arguments': It is the main reason, why diagonalizing matrices is such an important tool.

Related Question