17.79 min read

Lagrange Applied to Quadratics — Eigenvalues Appear

Let us apply the Lagrange theorem to a beautiful constrained quadratic: minimize $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^t A \mathbf{x}$ subject to $g(\mathbf{x}) = \frac{1}{2}\mathbf{x}^t \mathbf{x} = 1$ (the unit sphere), where $A$ is a symmetric $n \times n$ matrix.

The Jacobians are $Df(\mathbf{x}) = \mathbf{x}^t A$ (using symmetry of $A$ ) and $Dg(\mathbf{x}) = \mathbf{x}^t$ . The Lagrange condition $\lambda Dg = Df$ becomes $\lambda \mathbf{x}^t = \mathbf{x}^t A$ .

Transposing: $\lambda \mathbf{x}^{*} = A \mathbf{x}^{*}$ . But this is exactly the definition of an eigenvector equation! The constrained minimum $\mathbf{x}^{*}$ must be an eigenvector of $A$ , with Lagrange multiplier $\lambda$ as its eigenvalue.

So to solve this constrained quadratic, look at the eigenvectors of $A$ . The minimum value of $f$ on the sphere is the smallest eigenvalue of $A$ divided by 2: $f(\mathbf{x}^{*}) = \frac{1}{2}\lambda_{\min}$ .

Formal View

Theorem 17.4 — Quadratic Lagrange → Eigenvalue

Let

A

be a symmetric

n \times n

matrix. The constrained problem:

\min_{\mathbf{x}} \frac{1}{2}\mathbf{x}^t A \mathbf{x} \quad \text{s.t.} \quad \frac{1}{2}\mathbf{x}^t \mathbf{x} = 1

has the Lagrange condition

\lambda \mathbf{x}^{*} = A \mathbf{x}^{*}

— so any constrained minimum

\mathbf{x}^{*}

is an eigenvector of

A

with eigenvalue

\lambda

Why This Matters

This shows that eigenvalue problems are naturally constrained optimization problems. PCA, spectral clustering, and many other algorithms are instances of this.

Principal Component Analysis: first PC maximizes variance on the unit sphere — eigenvector of the covariance matrix
Google PageRank: finding the dominant eigenvector of a stochastic matrix
Quantum mechanics: energy eigenstates are constrained minimizers of the Hamiltonian
Spectral graph algorithms: eigenvectors of graph Laplacians solve clustering problems

Learning Resources

Lagrange multipliers introduction

3Blue1Brown

Lays the groundwork for the quadratic constrained problem derivation.

13 min

Eigenvalues and eigenvectors

3Blue1Brown

Reviews eigenvalues to contextualize the Lagrange → eigenvector connection.

14 min

Quiz

Question 1

In the constrained quadratic problem $\min \frac{1}{2}\mathbf{x}^t A \mathbf{x}$ s.t. $\|\mathbf{x}\|^2 = 2$ , a constrained minimum $\mathbf{x}^{*}$ must be:

Question 2

What does the Lagrange multiplier $\lambda$ represent in the quadratic constrained problem?

Question 3

The Jacobian of $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^t A \mathbf{x}$ (with $A$ symmetric) is $Df = \mathbf{x}^t A$ .

Question 4

The minimum value of $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^t A \mathbf{x}$ on the unit sphere is:

Question 5

In Principal Component Analysis (PCA), what plays the role of $A$ ?

Common Mistakes

Forgetting to use the symmetry of $A$ when computing $Df$ — symmetry is what makes $Df(\mathbf{x}) = \mathbf{x}^t A$ work.
Confusing the Lagrange multiplier $\lambda$ (an eigenvalue) with the minimum value of $f$ ( $\frac{1}{2}\lambda$ ).
Thinking this shows symmetric matrices always have real eigenvalues — we still need to argue existence (next section).