Mostrando que una matriz es positiva (semi-)definitiva

Question

Deje $G = (V,E)$ ser un grafo conexo y $T$ uno de sus árboles de expansión. Deje $w \in[0,1]^{|V|-1}$ ser un peso para el árbol de expansión, es decir podemos asignar a cada uno de el árbol de expansión de los bordes de un número en $[0,1]$. Para $(i,j) \in V \times V$ deje $x_{ij}^T(w)$ es el mínimo de los pesos en el único camino de$i$$j$$T$. Para $i=j$ asignamos $x_{ij}^T(w) = 1$.

Teorema: El $|V| \times |V|$ real simétrica matriz $x_{ij}^T(w)$ es positivo semidefinite. Si asumimos $w \in [0,1[^{|V|-1}$ es incluso positiva definida.

Esta positividad de la propiedad es necesaria para la convergencia absoluta de la reconstrucción de la suma utilizando el Bucle Vértice de Expansión. Es la central de propiedad de la forestal fórmula, sin embargo, me pregunto: ¿existe una prueba simple no relacionados con el bosque de la fórmula?

//edit: La prueba ya sé que es en Rivasseau y Wang "Cómo Reanudarla Feynman Gráficos".

Answer 1

Diversión problema. Deje que los pesos de las aristas ser $w_1 \leq w_2 \leq \cdots \leq w_{n-1}$. Para mayor comodidad, definir $w_0=0$$w_1=1$. Vamos $e_1$, $e_2$, ..., $e_{n-1}$ se los bordes, en el mismo orden de las pesas. Deje $D$ ser la matriz en el problema.

Para $1 \leq k \leq n$, vamos a $D_k$ ser la matriz de donde $(D_k)_{ij}=1$ si $D_{ij} \geq w_k$ $(D_k)_{ij}=0$ lo contrario. Entonces $$D = \sum_{k=1}^n (w_k-w_{k-1}) D_k.$$ Por lo que es suficiente para mostrar que cada una de las $D_k$ es positivo semidefinite. Por otra parte, es suficiente para comprobar esto en el caso de que $w_k > w_{k-1}$, ya que de lo contrario el coeficiente de $D_k$$0$.

Así, supongamos $w_{k-1} < w_k$. Tenemos $(D_k)_{ij}=1$ si y sólo si el camino de $i$ $j$NO pasa a través de los bordes $e_1$, $e_2$, ..., $e_{k-1}$. En otras palabras, vamos a $F_k$ ser el bosque obtenidos mediante la eliminación de $e_1$, $e_2$, ..., $e_{k-1}$ de $T$; a continuación, $D_k$ es el bloque de matriz diagonal cuyos bloques se corresponden con los componentes conectados de $F_k$ e donde cada bloque es una matriz cuadrada totalmente hecho de $1$'s. Esta matriz es definitivamente positiva semi-definida.

Por otra parte, si $w_{n-1} <1$, $D_n$ es la matriz identidad, por lo que la suma es positiva definida.

Después de escribir esto, he comprobado la prueba en Rivasseau y Wang (Teorema 2.2) y esta es básicamente la misma cosa, así que no sé si le va a gustar nada mejor.