Why is the identity the only symmetric $0$-$1$ matrix with all eigenvalues positive?
Solution 1:
Another way of putting it: if $A$ is positive definite, then so is the $2 \times 2$ submatrix consisting of rows and columns $i$ and $j$ (for any $i \ne j$). The determinant of this submatrix is $a_{ii} a_{jj} - a_{ij}^2$, and if the entries are in $\{0,1\}$ the only way to have $a_{ii} a_{jj} - a_{ij}^2 > 0$ is $a_{ii} = a_{jj} = 1$ and $a_{ij} = 0$.
Solution 2:
Here are two "bigger-picture" arguments that I found that I consider sufficient.
Let $A$ be a symmetric, $0$-$1$ matrix with all eigenvalues positive.
Proof 1: Correlation matrices.
Let $B$ be the diagonal matrix consisting of $1$'s where $A$ has $0$'s and $0$'s where $A$ has $1$'s. Then $A+B$ is a correlation matrix. Since adding nonnegative values to $A$'s diagonal can't decrease any of $A$'s eigenvalues (see, for example, Weyl's inequality), $A+B$ has all eigenvalues positive and is thus invertible. But the only invertible $0$-$1$ correlation matrix is the identity. (*) Since $A+B$ is the identity, $A$ must be a diagonal matrix. But the only invertible $0$-$1$ diagonal matrix is the identity. Therefore, $A$ is the identity matrix.
Proof 2: Linear transformations.
Since $A$ is a real symmetric matrix it is orthogonally diagonalizable, which means that it represents a linear transformation with scaling in mutually perpendicular directions. Since the eigenvalues are the scaling factors for the different directions, the scaling factors are all positive. This implies that for ${\bf x} \neq {\bf 0}$, $A$ cannot map ${\bf x}$ to a vector that is perpendicular to ${\bf x}$. (This follows geometrically, but you can also see this by remembering that positive definite implies something even stronger: $A {\bf x}$ must make an acute angle with ${\bf x}$.)
This non-orthogonality restriction between $A {\bf x}$ and ${\bf x}$ rules out any diagonal elements of $A$ being $0$, as otherwise $a_{ii} = 0$ would imply ${\bf e}_i$ and $A {\bf e}_i$ are orthogonal.
Since $A$ has all $1$'s along its diagonal, the non-orthogonality restriction now rules out any off-diagonal elements being $1$. Suppose otherwise; i.e., that $a_{ij} = a_{ji} = 1$ with $a_{ii} = a_{jj} = 1$. Then $A$ maps both ${\bf e}_i$ and ${\bf e}_j$ to the vector $(1,1)$ when the range of $A$ is restricted to the 2D subspace given by span$\{ {\bf e}_i, {\bf e}_j\}$. But this means that $A$ maps ${\bf e}_i - {\bf e}_j$ to the vector $(0,0)$ when the range of $A$ is restricted to span$\{ {\bf e}_i, {\bf e}_j\}$. Since ${\bf e}_i - {\bf e}_j$ is itself in span$\{ {\bf e}_i, {\bf e}_j\}$, this implies that ${\bf e}_i - {\bf e}_j$ and $A ({\bf e}_i - {\bf e}_j)$ are orthogonal, and we have our contradiction with the non-orthogonality restriction.
The only option left is that $A$ is the identity matrix.
(This second proof is mostly just a translation of my original proof into linear transformation terms.)
(*) Added: Marvis asked on my blog for an explanation of why the only invertible $0$-$1$ correlation matrix is the identity. Here is such a one. First, every correlation matrix has $1$'s on its diagonal. Second, a $0$-$1$ correlation matrix means that any of the underlying random variables are either uncorrelated or perfectly correlated. Distinct but perfectly correlated random variables (which means you have a $1$ off-diagonal) are scalar multiples of each other. This linear dependence carries over to the correlation matrix, which therefore can’t be invertible.