# If $A=(a_{ij})$ is positive semidefinite, prove that $a_{ij}^2 \leq a_{ii}a_{jj}$ for all $i \neq j$

If $A=(a_{ij})$ is positive semidefinite, prove that $a_{ij}^2 \leq a_{ii}a_{jj}$ for all $i \neq j$.
I don't even know how to get started, any hint is appreciated, thanks a lot.

-
see related math.stackexchange.com/questions/235170/… – Will Jagy Nov 20 '12 at 18:06

Hint: By Cauchy-Schwarz you have $(x^tAy)^2 \le (x^tAx)(y^t Ay)$ for any $x,y \in \mathbb R^d$.

You can of course try to mimic the proof of Cauchy-Schwarz and start with $$0 \le (e_i + se_j)^tA(e_i + se_j) = a_{ii} + 2sa_{ij} + s^2a_{jj}$$ Now let $s = -\frac{a_{ij}}{a_{jj}}$. You of course have to consider the case $a_{jj} = 0$ seperately.

-
Is there any alternative approach that does not require the use of this inequality? – drawar Nov 20 '12 at 11:04
@drawar Why do you not want to use Cauchy-Schwartz? – martini Nov 20 '12 at 11:08
Actually I'm practicing for my exam and Cauchy-Schwarz Inequality is not covered in my course so I'm not supposed to use it. – drawar Nov 20 '12 at 11:14
@user1551: My bad. Thanks! – drawar Nov 20 '12 at 11:15

You need $(x^tAx)\geq0$ for all $x$ and $x$. Now if you set $x=e_i+te_j$, you get a quadratic polynomial in $t$ which must be non-negative for all $t$. So this polynomial cannot have any non-repeated roots, as polynomials must be positive on one side of these and negative on the other.

So the discriminant of this polynomial (i.e. $b^2-4ac$ if your polynomial is $at^2+bt+c$) must be non-positive - when you work out what the coefficients are in terms of the matrix entries, this will be the inequality you want.

-
The discriminant must be non-positive. – Jack D'Aurizio Nov 20 '12 at 12:42
@Jack Indeed - thanks! – Matthew Pressland Nov 20 '12 at 14:30
Your first line should be You need $(x^t A x) \geq 0$ for all $x.$ – Will Jagy Nov 20 '12 at 18:09
@WillJagy Also true, thanks! – Matthew Pressland Nov 20 '12 at 18:10

Another approach, since it has not been mentioned:

A matrix $A$ is positive semidefinite if and only if every principal submatrix of $A$ is positive semidefinite. Thus, if $A$ is positive definite, then every principal submatrix must have a non-negative determinant.

Note that $$\pmatrix{ a_{ii}&a_{ij}\\ a_{ji}&a_{jj} }$$ is a principal submatrix of $A$, so its determinant must be non-negative. Note that since $A$ is positive semidefinite, it is symmetric so that $a_{ji} = a_{ij}$. The conclusion follows.

-