¿Escribir la matriz laplaciana de los grafos dirigidos como producto?

Question

Le site Matriz laplaciana de un gráfico no dirigido puede escribirse como $M^TM$ con $M$ siendo la matriz de incidencia del gráfico. Esto hace que la prueba (de otro modo tediosa) de Teorema de Kirkhoff en una hermosa aplicación de la Fórmula de Cauchy-Binet (y de hecho, esta es una de las pruebas en "Pruebas de EL LIBRO").

Si el gráfico es dirigido, $M^TM$ ya no funciona; la diagonal de la matriz resultante contiene el grado total de los vértices, mientras que para que el teorema de Kirkhoff funcione, sólo debería aparecer el indegree.

Así que mi pregunta es la siguiente: ¿se puede salvar este enfoque con una definición ligeramente diferente de $M$ que se me escapa, ¿o es que la prueba "tediosa" es necesaria y Cauchy-Binet simplemente no se puede utilizar aquí?

Answer 1

Creo que he encontrado una manera de escribir el Laplaciano como un producto. Primero recordemos la definición en el caso del gráfico dirigido: El laplaciano de $G=(V,E)$ es una matriz de tamaño $|V|\times |V|$ tal que $L_{ii}$ es el grado interior de $v_i$ y $L_{ij}$ para $i\ne j$ es menos el número de aristas de $v_i$ a $v_j$ .

Como el laplaciano no tiene que ser simétrico en el caso dirigido, no se puede escribir como $M^{T}M$ . Sin embargo, se puede escribir como $AB^T$ para dos matrices muy similares:

Defina que tanto A como B son $n\times m$ matrices, donde cada fila representa un vértice y cada columna representa una arista de $G$ . Ahora, para cada arista $e_k = v_i\to v_j$ :

1. $A_{ik} = 1, A_{jk} = -1$
2. $B_{ik} = 0, B_{jk} = -1$

El resto de las entradas son 0.

A menos que tenga algún error de cálculo, tenemos $L=AB^T$ .