📂Matrix Algebra

Constrained Extremum Theorem

Theorem¹

Constrained Extremum Theorem:

Let the matrix $A \in M_{n \times n}(\mathbb{R})$ be symmetric. Denote the eigenvalues of $A$ by $\lambda_{1} \ge \lambda_{2} \ge \cdots \ge \lambda_{n}$. Then the following holds.

(a) Under the constraint $\| \mathbf{x} \| = 1$, the quadratic form $\mathbf{x}^{\mathsf{T}} A \mathbf{x}$ attains a maximum and a minimum.

(b) The maximum and minimum are, respectively, $\lambda_{1}$ and $\lambda_{n}$.

Proof

Since $A$ is symmetric, by the principal axis theorem there exists an orthogonal matrix $P$ such that the following holds.

$$ \mathbf{x}^{\mathsf{T}} A \mathbf{x} = \lambda_{1}y_{1}^{2} + \cdots + \lambda_{n}y_{n}^{2}, \quad \mathbf{x} \in \mathbb{R}^{n} $$

Then $P$, as an orthogonal change of variables, yields $\mathbf{x} = P \mathbf{y}$. Since $P$ is orthogonal, it preserves the norm.

$$ \| \mathbf{x} \| = \| \mathbf{y} \| = y_{1}^{2} + \cdots + y_{n}^{2} $$

Therefore the following inequalities hold, so $\lambda_{1}$ and $\lambda_{n}$ are the upper bound and lower bound of $\mathbf{x}^{\mathsf{T}} A \mathbf{x}$.

$$ \begin{align*} \lambda_{n} &= \lambda_{n}(y_{1}^{2} + \cdots + y_{n}^{2}) \\ &\le \lambda_{1}y_{1}^{2} + \cdots + \lambda_{n}y_{n}^{2} = \mathbf{x}^{\mathsf{T}} A \mathbf{x} \\ &= \lambda_{1}(y_{1}^{2} + \cdots + y_{n}^{2}) \\ &= \lambda_{1} \end{align*} $$

$$ \implies \lambda_{n} \le \mathbf{x}^{\mathsf{T}} A \mathbf{x} \le \lambda_{1} $$

Let $\mathbf{x}_{1}$ be an eigenvector corresponding to $\lambda_{1}$. Then we have:

$$ \mathbf{x}_{1}^{\mathsf{T}} A \mathbf{x}_{1} = \lambda_{1} \mathbf{x}_{1}^{\mathsf{T}} \mathbf{x}_{1} = \lambda_{1} $$

Similarly, let $\mathbf{x}_{n}$ be an eigenvector corresponding to $\lambda_{n}$; then we obtain:

$$ \mathbf{x}_{n}^{\mathsf{T}} A \mathbf{x}_{n} = \lambda_{n} $$

Hence $\lambda_{1}$ and $\lambda_{n}$ are, respectively, the maximum and minimum of $\mathbf{x}^{\mathsf{T}} A \mathbf{x}$.

■