Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
1  
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)? –  user815423426 Jul 25 '11 at 19:10
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. –  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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.