# Minimum of a quadratic form

If $\bf{A}$ is a real symmetric matrix, we know that it has orthogonal eigenvectors. Now, say we want to find a unit vector $\bf{n}$ that minimizes the form: $${\bf{n}}^T{\bf{A}}\ {\bf{n}}$$ How can one prove that this vector is given by the eigenvector corresponding to the minimum eigenvalue of $\bf{A}$?

I have a proof of my own, but it's rather unelegant - how would you go about proving this?

• orthogonally diagonalize $A$ – Will Jagy Mar 26 '14 at 19:12
• Equally interesting: What vector $x$ maximizes $x^tAX$? – Brad S. Mar 26 '14 at 19:47

Let $A=UDU^T$ be its eigen decomposition. Then $D$ is a diagonal matrix with all the eigenvalues as diagonal entries. Then we have \begin{align} \min_{n^Tn=1}~n^TAn\\&=\min_{u^Tu=1}u^TDu ~~~\{u=Un\} \\ &=\min_{x\in\mathbb{S}}\sum_{i}x_iD_{ii}~~~~~~~~~ \end{align} where $$\mathbb{S}=\{(x_1,\dots,x_N)\in\mathbb{R}^N\mid x_i\geq 0,~~\sum_{i}x_i=1\}$$ The last step is equivalent to \begin{align} \min_{x\in\mathbb{S}}\sum_{i}x_iD_{ii}=\min_{i}D_{ii} \end{align} and also note that \begin{align} \max_{x\in\mathbb{S}}\sum_{i}x_iD_{ii}=\max_{i}D_{ii} \end{align}

• Where does the equivalence come from? – nbubis Mar 27 '14 at 6:32
• Note that $\sum_{i}x_iD_{ii}$ is a convex combination of set of numbers $D_{ii}$ on the real line. Thus it stays between the largest number and the smallest number. – dineshdileep Mar 27 '14 at 9:50

Proof that the minimum value of the quadratic form $$n^T A n$$ is the minimum eigenvalue of a real symmetric matrix $$A$$ for a unit vector $$n$$:

Let $$A=UDU^T$$ be its eigen decomposition. Then $$D$$ is a diagonal matrix with all the eigenvalues as diagonal entries. Let $$D_{ii} = \lambda_i$$Then we have \begin{align} \min_{|n|=1}~n^TAn\\&=\min_{|n|=1}~n^T(UDU^T)n\\&=\min_{|n|=1}~(U^Tn)^TD(U^Tn)\\&=\min_{|U^Tn|=1}(U^Tn)^TD(U^Tn) ~~~\tag{1} \\ &=\min_{|y|=1}~y^TDy, y:=U^Tn\\ &=\min_{|y|=1}\sum_{i}y_i^2D_{ii}\\ &=\min_{|y|=1}\sum_{i}y_i^2 \lambda_{i}~~~~~~~~~ \end{align}

Let $$\lambda_j := \min \{\lambda_1, ..., \lambda_n\} = \min_i \{\lambda_i\}$$ for some $$j = 1, ..., n$$.

Observe the following lower bound for the quadratic form

$$\sum_{i}y_i^2 \lambda_{i} \ge \sum_{i}y_i^2 \lambda_j = \lambda_j \sum_{i}y_i^2 = \lambda_j (1) = \lambda_j \tag{2}$$

• This is actually the greatest lower bound, i.e. infimum, because the RHS of $$(2)$$ does not depend on $$y$$: for any $$y$$, the quadratic form is greater than or equal to $$\lambda_j$$.

• This is actually the minimum because the quadratic form can achieve the infimum for $$y$$ s.t. $$y_j=1$$ and $$y_i=0$$ for the $$i$$'s that aren't $$j$$ ($$\forall \ i \ne j$$).

QED

By the way if $$A^T=A^{-1}$$, then $$\lambda_j=-1$$ because Can we prove that the eigenvalues of an $$n\times n$$ orthogonal matrix are $$\pm 1$$ by only using the definition of orthogonal matrix?

$$(1)$$ Observe that $$|U^Tn|=1$$ because $$|n|=1$$.

Pf: $$|U^Tn|=(U^Tn)^T U^Tn = n^T U U^T n = n^T (I) n = n^T n = |n| = 1$$ QED

For a symmetric matrix A, there exists a diagonal matrix D and an orthonormal matrix S such that $S^{-1}AS=D$ where the diagonal entries of D are the eigenvalues of A and the rows of S are the eigenvectors of A. so if we let $n$ be the eigenvector corresponding to the smallest eigenvalue of A then $n^TAn=\lambda$

To push this proof further;

A unit eigenvector $v$ with corresponding eigenvalue $\lambda$ satisfies;

$Av=\lambda v \Rightarrow v^TAv=\lambda$

• and why is this the minimal value of $n^TAn$? – Thomas Mar 26 '14 at 19:15
• @ellya - that doesn't quite answer the question, though I think I see how a proof could be completed from there. – nbubis Mar 26 '14 at 19:18
• @ellya surely, the eigen vectors of $A$ must be placed in the columns of $S$ – Brad S. Mar 26 '14 at 19:21
• Yes Brad, I think you're right, I forgot it was $S ^ { - 1 }$ on the left. – Ellya Mar 26 '14 at 19:24