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?