Spectral Theorem / Quadratic Form Minimization Problem

Question

Here is the problem:

Let $A$ be an $n \times n$ symmetric matrix.

Let $S = \{ \mathbf x \in \mathbb R^n : ||\mathbf x|| = 1 \} $ denote the unit sphere.

Let $Q(\mathbf x) = \mathbf x ^TA\mathbf x $ denote the quadratic form associated to $A$.

Show that if $\mathbf x_0 \in S$ is a point where $Q$ achieves its global minimum on $S$, then $\mathbf x_0$ is an eigenvector for $A$. What is the corresponding eigenvalue?

I do not even know where to begin with this problem. This is apparently a Spectral Theorem problem, but I don't see it. Any help would be appreciated. Thanks.

Answer 1

If $A$ is symmetric, than the answer follows from spectral theorem indeed. First notice, if $A$ is symmetric we diagonalize the matrix with respect to an orthonormal basis and therefore: $\min\limits_{||x||=1} x^TAx = \min\limits_{||x||=1} x^TQ^T\Lambda Qx = \min\limits_{||z||=1} z\Lambda z$, where $\Lambda := \text{diag}(\lambda_1,\lambda_2, ... ,\lambda_n)$. We used the fact that $Q$ are isometries (unitary matrices), hence $z = Qx$ implies $||z|| = ||Qx||$. Now $\min\limits_{||z||=1} z\Lambda z = \min\limits_{\sum_i z^2_i=1} \sum\limits^n_{i=1} \lambda_i z^2_i = \min\limits_{j} \lambda_j=\lambda_{min}$. With $j^*$ being the corresponding index, the minimizing $z$ has the entries $z_{j^*} = 1$ and else $z_{j\neq j^*} = 0$. Using $z = Qx$ to find the corresponding minimizer $x$, we find that $x^*$ is the eigenvector of unit length to that corresponding minimum eigenvalue $\lambda_{min} = \lambda_{j^*}$.

Notice that with the same argument we can see that $\max\limits_{||x||=1} x^TAx =\lambda_{max} $, with the maximizing $x$ being the eigenvector to that maximum eigenvalue.

The required result would not hold, if $A$ is not symmetric. Instead another result would hold: Noticing, that $A$ can be decomposed into a symmetric and skew-symmetric matrix, $A = A_{sym} + A_{skew} = \frac{1}{2}(A^T+A) + \frac{1}{2}(A^T-A^T)$ and that $x^TAx = x^TA_{sym}x$, we can see that $\min\limits_{||x||=1} x^TAx$ or $\max\limits_{||x||=1} x^TAx$ would be the $\lambda_{min}$ and $\lambda_{max}$ of the matrix $A_{sym}$ with minimizer and maximizer being the corresponding eigenvectors of $A_{sym}$. Those eigenvectors and eigenvalues do NOT relate back to $A$ without any further assumption.

Answer 2

I think $A$ is supposed to be symmetric. In that case:

Using the spectral theorem, $A=S^{-1}DS$ where $S$ is orthogonal and D is a diagonal matrix. $D=diag(d_1,\dots, d_n)$

Let $k_1,\dots,k_r \in \{1,\dots,n\}$ such that: $d_{k_1}=\dots=d_{k_r}=\min\limits_{1\leq i\leq n}\{d_i\}=d$

So $$ Q(\mathbf x) = \mathbf x^TS^TDS\mathbf x= (S\mathbf x)^TD(S\mathbf x) $$ Let $\mathbf y= S\mathbf x = \begin{bmatrix} y_1 \\ \vdots \\ y_n \end{bmatrix}$

Note that since $S$ is orthogonal, $||\mathbf y||=||\mathbf x||=1$

We also have $A\mathbf x=$

And $Q(\mathbf x)= \sum\limits_{i=1}^n d_iy_i^2\geq d$

$$\begin{align} Q(\mathbf x)=d & \iff \mathbf y \in \operatorname{span}(\mathbf e_{k_1},\dots,\mathbf e_{k_r}) \\ & \iff \mathbf y \text{ is an eigenvector of D, with the eigenvalue d} \\ & \iff D \mathbf y=d\mathbf y \\ & \iff S^TDS \mathbf x = dS^TS\mathbf x \\ & \iff A\mathbf x= d\mathbf x \end{align}$$

Which means that $Q$ attains its minimum on the eigenvectors of its smallest eigenvalue.

Answer 3

Using the Spectral Theorem is circular reasoning, since the proof of the spectral theorem uses this fact!

One way to prove this without invoking the spectral theorem is to use Lagrange Multipliers.

Observe that

$\begin{align*} Q(x+v) &= \langle x+v, Ax +Av \rangle\\ &=\langle x, Ax \rangle + \langle v, Ax \rangle+\langle x, Av \rangle+\langle v, Av\rangle\\ &=Q(x)+\langle v, 2Ax\rangle+\langle v, Av\rangle \end{align*}$

where in the last line we have used $\langle v, Ax \rangle = \langle x, Av \rangle$ since $A$ is symmetric.

By the definition of the derivative, we have that $\nabla Q(x) = 2Ax$.

We are trying to minimize $Q$ on the unit sphere $g(x) = 0$, where $g= |x|^2$. We can compute that $\nabla g(x) = 2x$.

We know the minimum exists since the unit sphere is compact. Lagrange multipliers tells us that at the minimum we have

$$\nabla f(p) = \lambda \nabla g(p)$$ for some $\lambda$ at the minimum $p$.

But using our computations above this says

$$Ap = \lambda p$$, so $p$ was actually an eigenvector. Moreover $Q(p) = p \cdot \lambda p = \lambda$.

Note that this proves the hardest part of the Spectral theorem: that there is at least one eigenvector. To complete the proof, observe that if $v$ is an eigenvector, then $A$ restricts to a linear map from $v^\perp \to v^\perp$, since for all $x \in v^\perp$, $\langle v, Ax \rangle = \langle Av, x \rangle = \lambda \langle v, x \rangle = 0 $, since $x \perp v$.

We can then view $A$ as operating on a vector space ($v^\perp$) of dimension $n-1$, so induction instantly solves the problem.