Why does $f(x)=\frac{x^T Ax}{x^T x}$ always have a minimum value?

123 Views Asked by At

$f$ is defined for all $x\in\mathbb{R^n}-\{0\}$ nd $A$ is a symmetric matrix $n \times n$.

I have to proof that $f$ has a minimum $f(x^*)$ and write a formula for $x^*$ using the spectral decomposition of $A$.

My attempt

Since $A$ is symmetric, by the spectral decomposition theorem:

$$A = Q\Lambda Q^T, \text{where $Q$ is an orthogonal matrix and $\Lambda$ is a diagonal matrix }$$

Then:

$$\frac{x^T Ax}{x^T x} = \frac{x^T Q\Lambda Q^T x}{x^T x} = \frac{y^T \Lambda y}{y^T y} = \frac{\sum_{i=1}^{n}\lambda_i y_i^2 }{\sum_{i=1}^{n} y_i^2} $$

Where $y = Q^T x.$ It shows that $f(x)\leq \sum_{i=1}^{n} \lambda_i$. (I don't know if this inequality is helpful).

I'm stuck here. Any hint?

1

There are 1 best solutions below

0
On BEST ANSWER

Hints:

With what you have, try substituting where $x$ is an eigenvector (perhaps the eigenvectors whose corresponding eigenvalues are minimal and maximal). This corresponds to the case where $y_i$ is a standard basis vector.

Another way to prove that a minimum/maximum exists is via the following two facts: (1) $f(x)$ is scale invariant (in other words, if $\lambda\not=0$, then $f(\lambda x)=f(x)$. Therefore, $f(x)$ is really a function on an $n$-dimensional sphere. (2) An $n$-dimensional sphere is compact and continuous functions on compact sets attain their minimum and maximum (and are bounded).

Without using topology, but still thinking of this as a function on a sphere, you get that $\sum y_i^2=1$, so you're talking about $f(x)$ being a weighted sum of the $\lambda_i$'s, $\sum \lambda_iy_i^2$.