Quadratic Form Inequalities

Why

How big can a quadratic form be? How small?

Result

Suppose $A \in \mathbfsf{S} ^n$ has real eigenvalues $\lambda _1 \geq \lambda _2 \geq \cdots \geq \lambda _n$. Then

\[ \lambda _n x^\top x \leq x^\top A x \leq \lambda _1 x^\top x, \]

for all $x \in \R ^n$.

Since $A$ is symmetric, there exists an orthogonal matrix $Q \in \R ^{n \times n}$ with $A = Q\Lambda Q^\top $. Express

\[ \begin{aligned} x^\top A x = x^\top Q \Lambda Q^\top x &= (Q^\top x)^\top \Lambda (Q^\top x) \\ &= \sum_{i = 1}^{n} \lambda _i (q_i^\top x)^2 \\ &= \lambda _1 \sum_{i = 1}^n (q_i^\top x) = \lambda _1 \norm{Q^\top x}^2 = \lambda _1 \norm{x}^2. \end{aligned} \]

Similarly,

\[ \begin{aligned} x^\top A x &= \sum_{i = 1}^{n} \lambda _i (q_i^\top x)^2 \\ &\geq \lambda _n \sum_{i = 1}^n (q_i^\top x) = \lambda _n \norm{Q^\top x}^2 = \lambda _n \norm{x}^2. \end{aligned} \]

Notation

For this reason, it is common to order the eigenvalues of $A \in \mathbfsf{S} ^n$ by magnitude with $\lambda _1 \geq \lambda _2 \geq \cdots \geq \lambda _n$. $\lambda _1$ is sometimes denoted $\lambda _{\max}$ and $\lambda _n$ is sometimes denoted $\lambda _{\min}$.

Optimization implication

If $z = \alpha x$, then $z^\top A z = \alpha ^2 x^\top A x$. Consider finding $x \in \R ^n$ to maximize

\[ \begin{aligned} \text{ maximize } & \quad x^\top A x \\ \text{ subject to } & \quad \norm{x} = 1. \end{aligned} \]

Since the objective is $x^\top A x \leq \lambda _1$ for all $x \in \R ^n$ with $\norm{x} = 1$, a solution of this problem is the eigenvector $q_1 \in \R ^n$ corresponding to $\lambda _1$. In other words, these inequalities are tight.