Valor propio de la matriz de bloques con bloques de diferente tamaño

Question

Estaba leyendo el periódico " Consistencia de la agrupación espectral en modelos de bloques estocásticos ", de J.Lei y A.Rinaldo ( Enlace arXiv ).

En la demostración del Corolario 3.2, el autor utiliza una igualdad $\gamma_k = n_{\min}\alpha_n\lambda$ . Estaba confundido acerca de cómo viene esta igualdad.

El modelo se muestra a continuación.

$$B=\alpha_{n} B_{0} ; \quad B_{0}=\lambda I_{K}+(1-\lambda) \mathbf{1}_{K} \mathbf{1}_{K}^{T}, \quad 0<\lambda<1$$ donde $I_K$ es el $K\times K$ matriz de identidad, y $\mathbf{1}_{K}$ es el $K\times 1$ vectores de $1$ 's. $\alpha_n$ y $\lambda$ son dos constantes.

Dejemos que $\Theta \in \mathbb{M}_{n, K}$ para cada nodo $i$ , dejemos que $g_i , (1 \le g_i \le K)$ sea su etiqueta comunitaria, de manera que el $i$ -en la fila de $\Theta$ es 1 en la columna $g_i$ y $0$ en otro lugar, lo que significa que sólo $K$ filas únicas en $\Theta$ . Sea $(n_1, \ldots, n_K)$ representa el número de filas de cada fila única.

Entonces, defina $P=\Theta B \Theta^{T}$ y $\gamma_k$ denota el $k$ el menor valor propio no nulo de $P$ en magnitud, $n_{\min} = \min_{i} n_i$ .

Un ejemplo sencillo de la $\Theta$ parecer, asumir $n = 10, K =3$ $$ \begin{bmatrix} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \\ \end{bmatrix}_{10 \times 3} $$ aquí, $n_1 = 3, n_2 = 3, n_3 = 4$ . (se permite la permutación de la fila).

Entonces, en este ejemplo, $\gamma_k = 3\cdot \alpha_n \cdot \lambda$

¿Cómo podemos conseguir el $\gamma_n = n_{\min}\alpha_n\lambda$ ?

Y también, si tenemos una matriz más general de $B$ como existe una entrada diagonal diferente o una entrada no diagonal diferente, ¿hay alguna relación similar?

Una de mis conjeturas es, para una matriz simétrica general $B$ .

Supongamos que $\max_i B_{ii} = \alpha_n$ y $ B_{ii} > B_{k\ell} $ para $ i \in 1, \ldots, 5 $ y $ k \neq \ell , k, \ell \in 1, \ldots, 5$

donde $B_{ii}$ es la entrada de la diagonal, $B_{k\ell}$ es la entrada de la fuera de la diagonal. Esto significa que la entrada de la diagonal debe ser mayor que la entrada de la fuera de la diagonal y la entrada de la diagonal está limitada por $\alpha_n$

$$ \gamma_k \ge C\cdot\alpha_n\cdot n_{min}\cdot(\min(B_{ii}) - \max(B_{k\ell})) $$

Como en el ejemplo siguiente, dejemos que $B$ sean los siguientes $$ \begin{bmatrix} 0.4 & 0.15 & 0.13 & 0.11 & 0.09\\ 0.15 & 0.35 & 0.07 & 0.05 & 0.055\\ 0.13 & 0.07 & 0.3 & 0.05 & 0.045\\ 0.11 & 0.05 & 0.05 & 0.25 & 0.04\\ 0.09 & 0.055 & 0.045 & 0.04 & 0.2\\ \end{bmatrix}_{5 \times 5} $$ El $n_1 = 100, n_2 = 80, n_3 = 60, n_4 = 40, n_5 =20$

He hecho una simulación añadiendo $0.05$ a todo el elemento diagonal de $B$ por iteración.

El resultado siguiente confirma mis conjeturas

Dejemos que $y = \gamma_k$ y $x = \alpha_n\cdot n_{min}\cdot(\min(B_{ii}) - \max(B_{k\ell}))$

La línea discontinua es la línea de regresión, la línea oscura es $y = x$ .

Pero no soy capaz de probarlo.

Answer 1

Una pista: Los valores propios no nulos de $AB$ son los mismos que los valores propios no nulos de $BA$ . Por lo tanto, ya que $P = (\Theta B) \Theta^T$ basta con considerar los valores propios de la $K \times K$ matriz $$ \Theta^T(\Theta B) = \operatorname{diag}(n_1,\dots,n_K)B. $$ Esto, a su vez, es similar a la matriz $$ M = \operatorname{diag}(n_1,\dots,n_K)^{-1/2}[\operatorname{diag}(n_1,\dots,n_K)B]\operatorname{diag}(n_1,\dots,n_K)^{1/2}\\ = \operatorname{diag}(\sqrt{n_1},\dots,\sqrt{n_K})B\operatorname{diag}(\sqrt{n_1},\dots,\sqrt{n_K}). $$

---

Por ahora, supongamos que $\alpha_n = 1$ . Tenemos

$$ M = \operatorname{diag}(\sqrt{n_1},\dots,\sqrt{n_K}) (\lambda I)\operatorname{diag}(\sqrt{n_1},\dots,\sqrt{n_K}) \\ \quad + \operatorname{diag}(\sqrt{n_1},\dots,\sqrt{n_K})(1 - \lambda I)11^T \operatorname{diag}(\sqrt{n_1},\dots,\sqrt{n_K}) = \\ \lambda \operatorname{diag}(n_1,\dots,n_K) + vv^T, $$ donde $v = \operatorname{diag}(\sqrt{n_1},\dots,\sqrt{n_K}) 1 = (\sqrt{n_1},\dots,\sqrt{n_K})$ .

Para las matrices semidefinidas positivas $P,Q$ se cumple que el menor valor propio de $P + Q$ es al menos igual al menor valor propio de $P$ . Así, el menor valor propio de $M$ es al menos igual al menor valor propio de $\lambda \operatorname{diag}(n_1,\dots,n_K)$ que es $\lambda n_{\min}$ .

Si el mínimo $n_\min$ se alcanza varias veces, entonces sí tenemos $\lambda n_{\min}$ como un valor propio. En particular, observamos que $$ M - \lambda n_{\min} I = \lambda \operatorname{diag}(n_1 - n_\min,n_2 - n_\min\dots,n_K - n_\min) + vv^T. $$ El primer término, $\lambda \operatorname{diag}(n_1 - n_\min,n_2 - n_\min\dots,n_K - n_\min)$ tiene un rango máximo de $K-2$ . Porque $\operatorname{rank}(A + B) \leq \operatorname{rank}(A) + \operatorname{rank}(B)$ , $M - \lambda n_{\min} I$ tiene un rango máximo de $K-1$ y por lo tanto es singular, lo que significa que $\lambda n_{\min}$ es un valor propio.

Más brevemente, también podríamos haber aplicado la desigualdad de Weyl.

En el caso restante, podemos comprobar si $\lambda n_{\min}$ es, de hecho, un valor propio de la siguiente manera Sin pérdida de generalidad, supongamos que $n_\min = n_1$ . Por lo tanto, tenemos $$ M - \lambda n_{\min} I = \lambda \operatorname{diag}(0,n_2 - n_\min\dots,n_K - n_\min) + vv^T. $$ Por el lema del determinante de la matriz tenemos $$ \det(\operatorname{diag}(0,n_2 - n_\min\dots,n_K - n_\min) + vv^T) \\= 0 + v^T\operatorname{adj}(\operatorname{diag}(0,n_2 - n_\min\dots,n_K - n_\min))v. $$ Calculamos $$ \operatorname{adj}(\operatorname{diag}(0,n_2 - n_\min\dots,n_K - n_\min)) = \operatorname{diag}(p,0,\dots,0), $$ donde $p = (n_2 - n_\min)\cdots (n_K - n_\min)$ . Así, encontramos que $$ \det(M - \lambda n_{\min} I) = v^T\operatorname{diag}(p,0,\dots,0)v = n_\min p \neq 0, $$ para que $\lambda n_{\min}$ no es un valor propio de $M$ .

Por la desigualdad de Weyl, tenemos $\gamma_k \leq \lambda \min_{n_j \neq n_\min} n_j$ .