# 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?

-

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$.

-
This is really the same thing, but I like to think of the matrix $M$ as assigning a $k$-vector $M_i$ to each point $i$, where the $j^{\rm th}$ coordinate tells you if $i$ is in cluster $j$. In this language, $A$ is the Gram matrix of the set of vectors $M_1, \ldots, M_n$. Finally, we know that any Gram matrix is PSD. – Srivatsan Jul 25 '11 at 18:33
Thank you Noah and @Srivatsan. I like and understand these explanations. Is there a way to make an explicit connection between these arguments and the transitive relation that I presume is encoded in the co-ocurrence matrix (see my post)? – Amelio Vazquez-Reina Jul 25 '11 at 19:10
@AmV: Let a matrix $A$ encode a reflexive, symmetric relation on the set $\{1,\ldots,n\}$ in the manner you have specified. If the relation is transitive, then it is an equivalence relation so the argument given in my original answer shows that $A$ is positive semidefinite. If it is not transitive, then there are some $r$, $s$, $t$ such that the principal minor of $A$ corresponding to $\{r,s,t\}$ is $\begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 1\\ 0 & 1 & 1\end{bmatrix}$, which has determinant $-1$, so $A$ is not positive semidefinite. – Noah Stein Jul 25 '11 at 21:36

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.

-

....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.

-