Symmetric Binary Matrix - Can I prove it is positive semi definite?

Question

I have a symmetric real matrix $A$ of the form $$ A = \begin{pmatrix} 1 & a_{1,2} & a_{1,3} & \ldots & a_{1,n} \\ a_{2,1} & 1 & \cdots & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots& \vdots \\ a_{n,1} & a_{n,2} & \dots & \dots & 1 \end{pmatrix} $$ where $a_{i,j}=1$ or $0$ - I do not know in advance how many are zero or one.

Is it possible to prove that the matrix is positive semi-definite. I can do so numerically, but is it obvious analytically. Note that I cannot assume that the diagonal is dominant.

Edit: Oops! I omitted to mention that the off-diagonal elements have an internal structure of the form $a_{i,j}=b_i b_j$ where $b_i$ is binary and so $b_i=0$ or $b_i=1$.

Answer 1

No, you cannot prove it is semi definite.

$$ \left( \begin{array}{rrr} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{array} \right) $$

Characteristic polynomial is $x^3 - 3 x^2 + x + 1 = (x-1)(x^2 - 2x - 1).$ Eigenvalues are $1, 1 + \sqrt 2, 1- \sqrt 2 .$ The eigenvector with a negative eigenvalue is $(-1, \sqrt 2, -1).$

Answer 2

Now that you've specified the structure of the off diagonal entries, it is possible to show that $A$ is positive semidefinite.

Let $b = \begin{bmatrix}b_1\\b_2\\\vdots\\b_n\end{bmatrix}$ and let $D = \begin{bmatrix}1-b_1^2 & & & \\ & 1-b_2^2 & & \\ & & \ddots & \\ & & & 1-b_n^2\end{bmatrix}$.

Then, $bb^T = \begin{bmatrix}b_1^2 & b_1b_2 & \cdots &b_1b_n\\ b_2b_1 & b_2^2 & \cdot & b_2b_n \\\vdots & \vdots & \ddots & \vdots \\ b_nb_1 & b_nb_2 & \cdots & b_n^2\end{bmatrix}$, and so, $D+bb^T = \begin{bmatrix}1 & b_1b_2 & \cdots &b_1b_n\\ b_2b_1 & 1 & \cdot & b_2b_n \\\vdots & \vdots & \ddots & \vdots \\ b_nb_1 & b_nb_2 & \cdots & 1\end{bmatrix} = A$.

So for any vector $x$, we have $x^TAx = x^T(D+bb^T)x = x^TDx+x^Tbb^Tx = x^TDx + (b^Tx)^2 \ge 0$ since $D$ is clearly positive semidefinite and $(b^Tx)^2$ can't be negative.

Thus, $A = D+bb^T$ is positive semidefinite.