Why are cluster co-occurrence matrices positive semidefinite? A cluster (aka a partition) co-occurrence matrix $A$ for $N$ points $\{x_1, \dots x_n\}$ is an $N\times N$ matrix that encodes a partitioning of these points into $k$ separate clusters ($k\ge 1$) as follows:
$A(i,j) = 1$ if $x_i$ and $x_j$ belong to the same cluster, otherwise $A(i,j) = 0$
I have seen texts that say that $A$ is positive semidefinite. My intuition tells me that this has something to do with transitive relation encoded in the matrix, i.e.:
If $A(i,j) = 1$, and $A(j,k) = 1$, then $A(i,k) = 1$ $\forall (i,j,k)$
But I don't see how the above can be derived from the definition of positive semidefinite matrices, i.e. $z^T A z > 0$ $\forall z\in R^N$
Any thoughts?

....and yet another way to view it: an $n\times n$ matrix whose every entry is 1 is $n$ times the matrix of the orthogonal projection onto the 1-dimensional subspace spanned by a column vector of 1s.  Its eigenvalues are therefore $n$, with multiplicity 1, and 0, with multiplicity $n-1$.  Now look at $\mathrm{diag}(A,B,C,\ldots)$, where each of $A,B,C,\ldots$ is such a square matrix with each entry equal to 1 (but $A,B,C,\ldots$ are generally of different sizes.
