On one property of positive semidefinite matrices

Question

This question reveals some important properties of positive semidefinite matrices. It would be very useful in solving the SDP problem (where I encountered it). The question is quite straightforward.

Let $A$ be an $n \times n$ positive semidefinite matrix with positive diagonal elements. Is it possible that any of its $2 \times 2$ submatrices defined as:

$$ \begin{bmatrix} a_{ii} & a_{ij} \\a_{ji} & a_{jj}\end{bmatrix} $$

is not positive semidefinite?

And if every this $2\times2$ submatrix is positive semidefinite, is A necessarily positive semidefinite?

Answer 1

The submatrix you mention is necessarily positive semidefinite. In particular, if $e_1,\dots,e_n$ are the standard basis vectors, then it suffices to note that $$ (x_ie_i + x_je_j)^TA(x_ie_i + x_je_j) = \pmatrix{x_i&x_j} \pmatrix{a_{ii} & a_{ij}\\ a_{ji} & a_{jj}}\pmatrix{x_i\\x_j}\geq 0 $$ for any choice of $x_i,x_j$.