Decomposing a positive semi-definite matrix with all -1,+1 elements Claim.$\,$ A matrix $\,X \in \{-1,1\}^{n\times n}\,$ is positive semi-definite if and only if it is of the form $X= xx^{T}$, for some $x \in \{-1,1 \}^n$.
How can I prove this? Proving the 'if' part is easy since $y^Txx^Ty = (x^Ty)^T(x^Ty) \geq 0$ for any $y \in \mathbb{R}^n$. But, the other way around is not that straightforward. 
Notice that, $X$ has all ones diagonal since diagonal of a psd matrix cannot have negative elements. 
 A: Let $A$ be our matrix. The corresponding quadratic form should look like
$$
p(x_1,\ldots,x_n)=\boldsymbol x^tA\boldsymbol x=x_1^n+\cdots+x_n^2+2\sum_{1\le i<j\le n}\varepsilon_{ij}x_ix_j, \tag{1}
$$
where $\varepsilon=\pm 1$ and $\boldsymbol x=(x_1,\ldots,x_n)$. We shall show that $p$ is positive semi-definite (psd), then
$$
p(x_1,\ldots,x_n)=(\varepsilon_1 x_1+\cdots+\varepsilon_n x_n)^2, \tag{2}
$$
for suitable $\varepsilon_j=\pm 1$, $j=1,\ldots,n$, in which case 
$A=(\varepsilon_1,\ldots,\varepsilon_n)(\varepsilon_1,\ldots,\varepsilon_n)^t$. 
If the expression $(1)$ is psd, then $$
\varepsilon_{ij}\varepsilon_{jk}=\varepsilon_{ik},\quad\text{for all $i\ne j\ne k\ne i$.}
\tag{3}
$$ 
If $(3)$ fails, and for some $i,j,k$, we have 
$\varepsilon_{ij}\varepsilon_{jk}=-\varepsilon_{ik}$, then letting $\boldsymbol x\in \mathbb R$ be the vector having $\varepsilon_{jk},\varepsilon_{ik},\varepsilon_{ij}$ in the posistions $i,j,k$, respectively, and zero everywhere else, it can be readily seen that
$$
\boldsymbol x^tA\boldsymbol x=\varepsilon_{jk}^2
+\varepsilon_{ik}^2+\varepsilon_{ij}^2+2
(\varepsilon_{ij}\varepsilon_{jk}+\varepsilon_{ij}\varepsilon_{ik}
+\varepsilon_{jk}\varepsilon_{ik})=3-6=-3<0.
$$
But if $(3)$ holds, then
$$
x_1^n+\cdots+x_n^2+2\sum_{1\le i<j\le n}\varepsilon_{ij}x_ix_j=(x_1+\varepsilon_{12}x_2+\varepsilon_{12}\varepsilon_{23}x_3+\cdots+\varepsilon_{12}\cdots\varepsilon_{n-1,n}x_n)^2
$$ 
Note. Another proof is based on the Pigeonhole Principle. There exist exactly $2^{n-1}$ symmetric matrices in $\{-1,1\}^{n\times n}\,$ which satisfy $(3)$ and $\varepsilon_{ii}=1$, for all $i$. Also, there exist exactly $2^{n-1}$ matrices of the form $\boldsymbol x\cdot\boldsymbol x^t$, where $\boldsymbol x$ contains elements in $\{-1,1\}$.
