Symmetric matrices play a big role in solving optimization problems in machine learning. You’ll get a taste of this in Homework 10, Problem 6, which discusses ridge regression and regularization, ideas that we use to make sure that our models are not overfitting to training data.
Here, we’ll prove a related fact: if \(A\) is an \(n \times n\) symmetric matrix and all of its eigenvalues are non-negative, then \(A\) is positive semidefinite. A symmetric matrix \(A\) is positive semidefinite if and only if \(\boxed{\vec v^T A \vec v \geq 0}\) for all \(\vec v \in \mathbb{R}^n\). One interpretation: this means the quadratic form \(f(\vec v) = \vec v^T A \vec v\) is always greater than or equal to 0, no matter what \(\vec v\) is.
Let’s work through the proof step-by-step: we will do some of it for you, and you’ll complete the rest. (To be precise, we’re only proving one direction of the “if and only if” statement; the other direction is in Homework 10!) First, since \(A\) is symmetric, the spectral theorem tells us that \(A\) can be written as
$$ A = Q \Lambda Q^T $$
where \(Q\) is an orthogonal matrix and \(\Lambda\) is a diagonal matrix with the eigenvalues of \(A\) on the diagonal. This is the eigenvector decomposition of \(A\).
On top of that, suppose that all of \(A\)’s eigenvalues, \(\lambda_1, \lambda_2, \ldots, \lambda_n\), are non-negative.
Now, let \(\vec v\) be some arbitrary vector (not necessarily an eigenvector of \(A\)) in \(\mathbb{R}^n\). Then, eventually we need to show that \(\vec v^T A \vec v \geq 0\), regardless of what \(\vec v\) is. Let’s start by expanding \(\vec v^T A \vec v\) using the fact that \(A = Q \Lambda Q^T\).
$$ \vec v^T A \vec v = \vec v^T (Q \Lambda Q^T) \vec v = (\vec v^T Q) \Lambda (Q^T \vec v) $$
Suppose that \(\vec y = Q^T \vec v\). Then, \(\vec y^T = (Q^T \vec v)^T = \vec v^T Q\). This seems like an arbitrary maneuver, but it will be useful in a moment.
$$ \begin{align*} \vec v^T A \vec v &= \vec y^T \Lambda \vec y =\begin{bmatrix} y_1 & y_2 & \ldots & y_n \end{bmatrix} \begin{bmatrix} \lambda_1 & 0 & \ldots & 0 \\\\ 0 & \lambda_2 & \ldots & 0 \\\\ \vdots & \vdots & \ddots & \vdots \\\\ 0 & 0 & \ldots & \lambda_n \end{bmatrix} \begin{bmatrix} y_1 \\\\ y_2 \\\\ \vdots \\\\ y_n \end{bmatrix} \end{align*} $$
Your job is to complete the rest of the proof. Show that if \(A\) is an \(n \times n\) symmetric matrix and all of its eigenvalues are non-negative, then \(\vec v^T A \vec v \geq 0\) for all \(\vec v \in \mathbb{R}^n\).
Solution
$$ \begin{align*} \vec v^T A \vec v &= \vec y^T \Lambda \vec y \\\\ &= \begin{bmatrix} y_1 & y_2 & \ldots & y_n \end{bmatrix} \begin{bmatrix} \lambda_1 & 0 & \ldots & 0 \\\\ 0 & \lambda_2 & \ldots & 0 \\\\ \vdots & \vdots & \ddots & \vdots \\\\ 0 & 0 & \ldots & \lambda_n \end{bmatrix} \begin{bmatrix} y_1 \\\\ y_2 \\\\ \vdots \\\\ y_n \end{bmatrix} \\\\ &= \begin{bmatrix} y_1 & y_2 & \ldots & y_n \end{bmatrix} \begin{bmatrix} \lambda_1 y_1 \\\\ \lambda_2 y_2 \\\\ \vdots \\\\ \lambda_n y_n \end{bmatrix} \\\\ &= \sum_{i=1}^n \lambda_i y_i^2 \end{align*} $$
Remember that none of the \(\lambda_i\)’s are negative. So, each term \(\lambda_i y_i^2\) is non-negative too, meaning the entire sum \(\sum_{i=1}^n \lambda_i y_i^2\) is non-negative. What we’ve shown is that if \(\vec v\) is any vector in \(\mathbb{R}^n\), then \(\vec v^T A \vec v\) ends up being a sum of this form, which is always non-negative, so \(\vec v^T A \vec v \geq 0\), and thus \(A\) is positive semidefinite.
