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$.
Best Answer
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.