I read that we can have, for a column vector $d \in R^N$,
\begin{eqnarray}
min_d = \frac{d' A d}{d'd} = \lambda_{min}
\end{eqnarray}
, where $\lambda_{min}$ is the smallest eigenvalue of the symmetric, pos. def. matrix $A \in R^{n \times n}$.
Now, why can we say that? When I apply the eigendecomposition theorem, I obtain:
\begin{eqnarray}
\frac{d' V \Lambda V' ~d}{d'd},
\end{eqnarray}
where $\Lambda$ is a diagonal matrix stuffed with the eigenvalues and $V$ is the matrix of eigenvectors. So I can see where this is going by picking the elements of $d$ such that we pick out the smallest eigenvalue but I am disturbed by the $V$ matrices that somehow don't seem to go away.
$A$ is symmetric and positive definite. I would greatly appreciate some guidance.
Thank you so much!
Hirek
Best Answer
The spectral theorem states that $A$ can be factored as $A = V \Lambda V^T$, where $\Lambda \in \mathbb R^{n \times n}$ is diagonal and $V \in \mathbb R^{n \times n}$ is orthogonal.
\begin{align} \inf_{d \neq 0} \, \frac{d^T A d}{d^T d} &= \inf_{d \neq 0} \, \frac{d^T V \Lambda V^T d}{d^T d} \\ &= \inf_{d \neq 0} \, \frac{d^T V \Lambda V^T d}{d^T V V^T d} \tag{$\heartsuit$}\\ &= \inf_{y \neq 0} \, \frac{y^T \Lambda y}{y^T y} \tag{ $\spadesuit$}\\ &= \inf_{\|y\|=1} \, y^T \Lambda y. \end{align}
(In step ($\heartsuit$), we used the fact that $V V^T = I$. In step ($\spadesuit$), we made the change of variable $y = V^T d$.)
Let the diagonal entries of $\Lambda$ be $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$. Note that \begin{align} y^T \Lambda y &= \lambda_1 y_1^2 + \cdots + \lambda_n y_n^2 \\ &\geq \lambda_n y_1^2 + \cdots + \lambda_n y_n^2 \\ &= \lambda_n, \end{align} assuming that $\|y\| = 1$. Moreover, when $y = \begin{bmatrix} 0 & \cdots & 0 & 1 \end{bmatrix}^T$, we have that $y^T \Lambda y = \lambda_n$.
Thus, \begin{equation} \inf_{d \neq 0} \, \frac{d^T A d}{d^T d} = \lambda_n. \end{equation}
Here is a slightly different way to look at it. Let $v_1,\ldots, v_n$ be an orthonormal basis of eigenvectors of $A$, with corresponding eigenvalues $\lambda_1 \geq \cdots \geq \lambda_n$. Given $d \in \mathbb R^n, d \neq 0$, decompose $d$ as $d = c_1 v_1 + \cdots + c_n v_n$. Then \begin{align} \frac{d^T A d}{d^T d} &= \frac{(c_1 v_1 + \cdots + c_n v_n)^T(c_1 \lambda_1 v_1 + \cdots + c_n \lambda_n v_n)}{c_1^2 + \cdots + c_n^2} \\ &= \frac{\lambda_1 c_1^2 + \cdots + \lambda_n c_n^2}{c_1^2 + \cdots + c_n^2} \\ &\geq \frac{\lambda_n c_1^2 + \cdots + \lambda_n c_n^2}{c_1^2 + \cdots + c_n^2} \\ &= \lambda_n. \end{align} It follows that \begin{equation} \inf_{d \neq 0} \,\frac{d^T A d}{d^T d} \geq \lambda_n. \end{equation} Moreover, we have equality when $d = v_n$.