Is the matrix corresponding to an equivalence relation positive semidefinite? Let $|X| < \infty$ and $(X,R)$ be an equivalence relation. Define the $|X| \times |X|$ matrix $A$ by
$$(A)_{ij} = \begin{cases}1 & (i,j) \in R,\\0 & \text{ otherwise}.\end{cases}$$
Is this matrix positive semidefinite? Is there a simple way to prove it?

Notice that $A$ is equal to $I$ plus the adjacency matrix of a graph consisting of a disjoint union of cliques. The eigenvalues of a clique $K_n$ are well-known to be $n-1$ and $-1$ and the spectrum of a disjoint union of graphs is the union of the spectra of the connected components. It follows that $A$ is positive semidefinite.
