¿Racimo por matrices de co-ocurrencia semidefinite positivo?

Question

Un clúster (aka una partición) matriz de co-ocurrencia $A$ $N$ $\{x_1, \dots x_n\}$ $N\times N$ matriz que codifica una división de estos puntos en $k$ grupos separados ($k\ge 1$) como sigue:

$A(i,j) = 1$ si $x_i$ $x_j$ pertenecen al mismo grupo, de lo contrario $A(i,j) = 0$

He visto los textos que dicen que $A$ es positivo semidefinite. Mi intuición me dice que esto tiene algo que ver con transitiva de la relación codificada en la matriz, es decir:

Si $A(i,j) = 1$, e $A(j,k) = 1$, luego $A(i,k) = 1$ $\forall (i,j,k)$

Pero no veo cómo la anterior puede ser derivada a partir de la definición de positivo semidefinite matrices, es decir,$z^T A z > 0$ $\forall z\in R^N$

Los pensamientos?

Answer 1

Aquí es otra manera de mirarlo: suponga que tiene un $(X_1,\dots,X_1,X_2,\dots,X_2,X_3,\dots,X_3,\dots\dots)$ de la tupla de variables aleatorias, cada una repetida tantas veces como miembros de un bloque correspondiente de la partición. Entonces la matriz de correlación es sólo la matriz que has descrito si $X_1,X_2,X_3,\dots$ son sin correlación. Y matrices de correlación son positivos semi definida.

Answer 2

Que $M$ ser una matriz de $N\times k$ definida por $B{ij} = 1$ si el punto $i$ es en cluster $j$ y $B{ij} = 0$ lo contrario. Entonces $A = M M'$ porque $(MM'){ij} = \sum{l=1}^k M{il} M{jl}$ es el número de clusters que contienen $i$ y $j$, que es por definición $A_{ij}$. Un producto de una matriz real y su transposición es siempre positivo semidefinite porque $x'Ax = x'MM'x = \lVert x'M\rVert_2^2\geq 0$ % todos $x\in\mathbb{R}^N$.

Answer 3

.. .y sin embargo, otra forma de verlo: una matriz de $n\times n$ que cada entrada es 1 es $n$ veces la matriz de la proyección ortogonal sobre el subespacio 1-dimensional generado por un vector columna de 1s. Sus valores propios son, por tanto, $n$, con multiplicidad 1 y 0, con multiplicidad de $n-1$. Ahora mira $\mathrm{diag}(A,B,C,\ldots)$, donde cada uno de $A,B,C,\ldots$ es una matriz cuadrada y tal con cada entrada igual a 1 (pero $A,B,C,\ldots$ generalmente son de diferentes tamaños.