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?
 A: Let $M$ be an $N\times k$ matrix defined by $B_{ij} = 1$ if point $i$ is in cluster $j$ and $B_{ij} = 0$ otherwise.  Then $A = M M'$ because $(MM')_{ij} = \sum_{l=1}^k M_{il} M_{jl}$ is the number of clusters containing both $i$ and $j$, which is by definition $A_{ij}$.  A product of a real matrix and its transpose is always positive semidefinite because $x'Ax = x'MM'x = \lVert x'M\rVert_2^2\geq 0$ for all $x\in\mathbb{R}^N$.
A: Here's another way to look at it: Suppose you have a tuple $(X_1,\dots,X_1,X_2,\dots,X_2,X_3,\dots,X_3,\dots\dots)$ of random variables, each repeated as many times as there are members of a corresponding block of the partition.  Then the correlation matrix is just the matrix you've described if $X_1,X_2,X_3,\dots$ are uncorrelated.  And correlation matrices are positive semi-definite.
A: ....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.
