# Prove diagonal entries of positive definite matrices cannot be smaller than the eigenvalues

The aim is to prove that the diagonal entries of a positive definite matrix cannot be smaller than any of the eigenvalues.

I know a positive definite matrix must have eigenvalues that are > 0, and that just because a matrix has all positive values, does not make it a positive definite matrix. I've also looked at the wikipedia for Positive-definite matrices and understand the definition given there, but am having a hard time convincing myself that the diagonal entries have to be greater than the eigenvalues.

The starting point of the proof should be to consider $A−a_{ii}I$, where $A=A^T$, and A is the positive definite matrix.

Can anyone help push me in the right direction to complete the proof?

The proposition as stated is false. Consider the positive definite matrix $$A=\left[ \begin{array}{cc} 1 & 0 \\ 0 & 2 \\ \end{array}\right]$$ It has eigenvalues $1$ and $2$. It has diagonal elements $1$ and $2$. Certainly, $a_{11} = 1 < 2 = \lambda_2$, the eigenvalue corresponding to the eigenvector $[0~1]^T$.

One can prove that it's impossible for every eigenvalue to be smaller than every diagonal element.

• Thanks, that makes sense. Would it make sense to say that the diagonal entries have to be greater than or equal to the smallest eigenvalue, rather than all of the eigenvalues? – mandib Dec 6 '17 at 6:09
• The trace of a matrix is equal to the sum of its eigenvalues. Every diagonal element of a (strictly) positive definite matrix matrix is (strictly) positive. So is every of its eigenvalues. Hence the smallest diagonal entry cannot be larger than the biggest eigenvalue. And the smallest eigenvalue cannot be larger that the largest diagonal entry. I don't know if more can be said. – Eric Fisher Dec 6 '17 at 6:15

Hint:

It suffices to prove that $\min_{\|x\|=1} x^TAx = \lambda_1$ where $\lambda_1$ is the smallest eigenvalue.

Once you proved that, can you think of a $y$ of unit length such that $y^TAy=a_{ii}$? If so, then $$a_{ii}=y^TAy \geq \min_{\|x\|=1} x^TAx = \lambda_1$$

Remark: Eric Fisher is right that the current proposition is false. My current hint intend for you to prove that the diagonal entries cannot be smaller than the smallest eigenvalue.

• Is my answer incorrect, Siong? – Eric Fisher Dec 6 '17 at 6:01
• You are indeed correct. I misread the question but I guess the intention is to prove that the diagonal cannot be smaller than the smallest eigenvalue. – Siong Thye Goh Dec 6 '17 at 6:02
• Perfect!. Thank you. – Eric Fisher Dec 6 '17 at 6:03
• Thanks for pointing out the mistake. I really missed that earlier. – Siong Thye Goh Dec 6 '17 at 6:05

The most general statement I know in this direction is that the diagonal elements of a symmetric matrix are majorized by its eigenvalues. We say that a vector $x \in \mathbb{R}^n$ is majorized by a vector $y \in \mathbb{R}^n$ if, for every $i$, $1 \le i \le n$,

$$x_{(1)} + \ldots + x_{(i)} \le y_{(1)} + \ldots + y_{(i)},$$ where $x_{(i)}$ is the $i$-th largest entry of $x$, and similarly for $y_{(i)}$, and $x_1 + \ldots + x_n = y_1 + \ldots + y_n$. This is written as $x \prec y$. An equivalent characterization of majorization is that $x \prec y$ if and only if $x$ is a convex combination of vectors obtained by permuting coordinates of $y$.

Let $a$ be the vector of diagonal entries of the matrix $A$, and $\lambda$ the vector of its eigenvalues. Then $a \prec \lambda$, and, in particular, $a$ is a convex combination of permutations of $\lambda$. This strengthens the following facts:

• the largest diagonal entry is at most the largest eigenvalues
• the smallest diagonal entry is at least the smallest eigenvalue
• the sum of diagonal entries is equal to the sum of the eigenvalues

To prove that $a \prec \lambda$, you can use the following formula, valid for any $1 \le k \le n$:

$$\lambda_{(1)} + \ldots + \lambda_{(k)} = \max\mathrm{Tr}(U^T A U),$$

where the maximum is over $n \times k$ matrices $U$ such that $U^T U = I_k$, the $k\times k$ identity matrix.

In fact, the Schur-Horn theorem shows that $a$ is the vector of diagonal entries of a matrix with eigenvalues $\lambda$ if and only if $a \prec \lambda$. So, in this sense, there is nothing more you can say than this.

We know that, if $\lambda$ is an eigenvalue of $A$, then $\lambda - p$ is an eigenvalue of $A-pI$.
So if $\lambda$ is an eigenvalue of $A$, then $\lambda - a{_i}{_i}$ is an eigenvalue of $A-a{_i}{_i}I$. Now, if $a{_i}{_i}$ is smaller than all the eigenvalues of $A$, then each $\lambda - a{_i}{_i}$ is positive and that makes $A-a{_i}{_i}I$ a positive definite matrix.
But $A-a{_i}{_i}I$ contains $0$ as its diagonal element on row $i$. So $A-a{_i}{_i}I$ cannot be positive definite and so $a{_i}{_i}$ cannot be smaller than all the eigenvalues of $A$