3
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ The eigendecomposition theorem allows $A$ to be factored as $A = V \Lambda V^T$, not $A = V V^T \Lambda$. $\endgroup$
    – littleO
    Sep 30, 2014 at 20:58
  • $\begingroup$ Thanks @littleO but $\Lambda$ is diagonal, so doesn't it commute with any other matrix? $\endgroup$
    – Hirek
    Sep 30, 2014 at 21:07
  • $\begingroup$ Oh gosh you're right! @littleO $\endgroup$
    – Hirek
    Sep 30, 2014 at 21:09

1 Answer 1

7
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .