Proof of Entry Bounds for Positive Semidefinite Matrices

Write $e_1,\dots,e_k$ for the standard basis vectors of $\mathbb{R}^{k}$, so that with the dot product and matrix-vector product, $e_i\cdot(Pe_j)=P_{ij}$ (the matrix-vector product selects column $j$, the dot product selects row $i$).

Claim 1. Taking $x=e_i$ in the positive semidefiniteness condition gives $P_{ii}=e_i\cdot(Pe_i)\ge0$. For $i=j$ the first two inequalities read $|P_{ii}|\le P_{ii}\le P_{ii}$, which hold. Let $i\ne j$ and let $\lambda$ be real. With $x=e_i+\lambda e_j$, bilinearity of the finite sums defining the dot product and the matrix-vector product gives

using the symmetry $P_{ji}=P_{ij}$ from Symmetric, Positive Semidefinite, and Positive Definite Real Matrices and Transpose of a Real Matrix.

If $P_{jj}=0$: then $P_{ii}+2\lambda P_{ij}\ge0$ for every real $\lambda$, which forces $P_{ij}=0$ (otherwise choose $\lambda$ with $2\lambda P_{ij}<-P_{ii}$); the asserted chain holds with both extreme sides. If $P_{jj}>0$: take $\lambda=-P_{ij}/P_{jj}$ to get $P_{ii}-P_{ij}^{2}/P_{jj}\ge0$, that is $P_{ij}^{2}\le P_{ii}P_{jj}$, whence $|P_{ij}|\le\sqrt{P_{ii}P_{jj}}$ with the nonnegative square root (which is monotone: $0\le u\le v$ implies $\sqrt u\le\sqrt v$, since otherwise squaring the reverse strict inequality contradicts $u\le v$). Finally $0\le(\sqrt{P_{ii}}-\sqrt{P_{jj}})^{2}=P_{ii}+P_{jj}-2\sqrt{P_{ii}P_{jj}}$ gives $\sqrt{P_{ii}P_{jj}}\le\tfrac12(P_{ii}+P_{jj})$, and the average of two of the numbers $P_{ll}$ is at most their maximum.

Claim 2. By the semidefinite order, $Q-P$ is positive semidefinite, so by claim 1 its diagonal entries are nonnegative: $Q_{ii}-P_{ii}\ge0$. Combining with claim 1 for $P$: