4
$\begingroup$

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?

3 Answers 3

3

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

  • 3
    @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.2011-07-25
1

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.

1

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