¿Cuánto álgebra lineal se puede hacer con gráficos?

Question

Sea G ser finito, dirigida gráfico acíclico, con fuentes de $A=\{a_1,\ldots,a_n\}$ y se hunde $B=\{b_1,\ldots,b_n\}$, con borde de pesos $w_{ij}$. El peso de una trayectoria P es el producto de los pesos de las aristas en P. Set
$e(a,b)= \sum\limits_{P\colon\, a\to b}w(P).$
Podemos formar una matriz de $M=\left(e(a_i,b_j)\right)_{i,j}$, y el Lindström-Gessel-Viennot(-Karlin-MacGregor) Lema nos dice que el determinante de M es el firmado suma de todas las n-tuplas de la no-caminos se cruzan de a a B.
$\det(M)=\sum\limits_{(P_1,\ldots,P_n)\colon\,A\to B} \mathrm{sign}(\sigma(P))\prod\limits_{i=1}^n w(P_i)$.

Este es un muy buen resultado, y de hecho, tiene sentido tomar como la definición del determinante (tal vez Kasteleyn-Percu es aún mejor). En el contexto de quantum de la topología, los gráficos de producirse de forma natural, y a mí me parece que los factores determinantes aparecen porque son (o deberían ser) conteo de n-tuplas de la ponderación de los no-caminos se cruzan.
Si este es el caso, entonces mi pregunta, en cierto sentido, es por eso que necesitamos de las matrices a todos. Finito dirigidos acíclicos ponderado de los gráficos de llevar a más información que la mera matrices, aparecen de forma natural, y parece una vergüenza para cambiarlos por insignificantes matrices sólo en el fin de hacer algo de álgebra lineal. Así que me gustaría preguntar si puedo hacer todos los álgebra lineal que necesito directamente de la gráfica:

Pregunta 1: El lema anterior nos da una gráfica-definición teórica de los determinantes. Hay un correspondiente puramente gráfico-definición teórica de autovalores? Es algo conocido más allá de las determinantes? Edit: Lo que realmente quiero es la firma y el rango - el resto es sólo la pesca por lo que es posible.

En el contexto en el que estoy más interesada, los pesos son valorados en un no-conmutativa (skew-poder-de la serie) del anillo. Es el Lindström-Gessel-Viennot Lema válida en este contexto? ¿Hay alguna referencia? (Mi ingenuo búsqueda en Zentralblatt y MathSciNet no llegar a nada).

Pregunta 2: Más de un sesgo de potencia de la serie de anillo (o un poco más general de la clase de niza no conmutativa de los anillos), no la firmó suma de todas las n-tuplas de la no-caminos se cruzan de a a B y recuperar la K₁-clase de M?

Finalmente, para entender el panorama un poco mejor, hay una referencia de lo que Qiaochu dijo sobre el significado de la (Lindström-Gessel-Viennot) determinante, como proveniente de algún tipo de mecánica cuántica de la imagen, donde "las entradas de la matriz de describir la transición de las amplitudes y que el determinante es una corriente alterna suma de amplitudes de transición en el que la "historia" de n partículas pueden constructiva o destructivamente interferir."? Qué hacer (física?) sentido decir algo así como "Grafo G es un diagrama de Feynman. Brillar la luz a través de las fuentes. El factor determinante es la cantidad de luz que se ve en los lavabos."?

Answer 1

Así, a diferencia de los determinantes, los autovalores de una matriz de enteros no son números enteros, así que no sé cuánto esperar aquí, tan lejos, pues, como una combinatoria de interpretación de cualquier tipo. Sin embargo, no siempre es la siguiente: si $A$ es la matriz de adyacencia de un número finito de gráfico, a continuación, $\text{tr } A^n$ es el número de caminos de longitud $n$, y es también la suma de los $n^{th}$ poderes de los autovalores. Por lo que conocer esta secuencia es equivalente a conocer el conjunto múltiple de autovalores, y ambas son equivalentes a saber lo que creo que se llama la "ruta de la función zeta" $\frac{1}{\det(I - At)}$ de la gráfica (que he escrito un poco sobre el aquí y aquí). No sé exactamente lo que usted desea autovalores para así no estoy seguro de si esto es útil.

Answer 2

Para responder a su primera pregunta, siempre puede interpretar vectores como los pesos en los vértices. En este caso, $\lambda$ es un valor propio con vector propio $v$ si para cada vértice, la suma de los pesos de los vecinos de los vértices es el producto del peso de los vértices y el autovalor.

$$\lambda v_i = \sum_{j \text{ neighbour of } i} v_j$$

No hay mucho conocimiento acerca de los valores propios de los gráficos. Tenemos una buena comprensión de la mayor autovalor (el Perron-Frobenius) y la comprensión de la segunda se refiere a la noción de expansión, pero por lo que yo sé, todo esto se hace usando álgebra lineal y no la otra manera alrededor.

Answer 3

Voy a tratar de aportar una respuesta parcial. En primer lugar quiero comentar sobre el Lindstrom-Gessel-Viennot determinantes próximos de la mecánica cuántica cosas, en física se conoce como el determinante de Slater, dando la fórmula para la función de onda de un multi-fermionic sistema. Esto le da una buena imagen a pensar de LGV como otro ejemplo de la Bosón-Fermión correspondencia. En el bosón de caso, permite que todos los caminos y se obtiene el número total como la permanente de la LGV de la matriz (esto es evidente a partir de la definición de la permanente), y en el fermión caso se obtiene un sistema con los estados contado por el determinante de la LGV de la matriz. Por supuesto, la no intersección parte entra en juego porque fermiones además de satisfacer el principio de exclusión de Pauli, por lo tanto ellos no pueden ocupar el mismo sitio al mismo tiempo.

Ahora, el linfogranuloma venéreo y sus resultados tienen una historia muy interesante, incluso en otros campos de la combinatoria. Fisher, en "los caminos de las Paredes, Humectación y Fusión" de 1984, considerado el vicioso caminantes en el modelo de la mecánica estadística, que considera mutuamente evitar dirigida entramado de caminos. Desde esta perspectiva es interesante echar un vistazo a algunas de las configuraciones que no se resuelven por la costumbre LGV, teorema de, por ejemplo, cuando los caminos se permite que se cruzan en los vértices, pero no los bordes, o cuando dos caminos se permite que se cruzan en la mayoría de los 2 vértices consecutivos (la terminología de esta clasificación es $n$-friendly caminantes, ver aquí). Viennot y los demás considerados como tales variantes después de que la relación entre la combinatoria de entramado de caminos y de la mecánica estadística se estableció, resulta que algunos de estos modelos también tienen determinantal las fórmulas asociadas a ellos. Una de las principales, el artículo es "De la Bethe Ansatz para la Gessel-Viennot Teorema" por R. Brak, J. W. Essam, y A. L. Owczarek, el punto aquí es que el LGV relacionados con los resultados puede ser probada mediante la matriz de transferencia, los métodos, que es un poderoso punto de vista a la luz de los modelos que he mencionado anteriormente donde la habitual LGV falla (es decir, fuera de los seis vértices del modelo).

Ahora bien, si necesitas algo más rigurosas relativas LGV matrices para fermión modelos, esto se puede hacer, pero no parece haber sido escrito muy bien en cualquier lugar. A veces esto se menciona en la literatura que en el caso de los grafos como $\mathbb Z^2$, véase, por ejemplo, "Domino embaldosados y los seis vértices del modelo en su libre fermión punto" por P. L. Ferrari y H. Spohn, pero creo que debería ser más generales de configuración para hablar de esto. Si se toma el punto de vista de que Greg Kuperberg mencionó en su respuesta a la anterior MO pregunta, que Kasteleyn-Percu matrices son esencialmente equivalentes a LGV matrices, entonces creo que hay más literatura sobre la interpretación de estos como modelos de fermiones de Majorana que viven en el gráfico. El artículo que estoy pensando es "Dímero Modelos, Libre de Fermiones y Super Mecánica Cuántica" por Dijkgraaf, Orlando y Reffert.

Como última nota, yo quería decir que no entiendo su motivación para querer identificar a cada ocurrencia de la determinante con un LGV (o Kasteleyn-Percu) contexto, teniendo en cuenta que incluso dentro de la teoría de grafos existen familias de objetos (incluso las rutas o caminos aleatorios, como se mencionó anteriormente), los cuales son contados por los factores determinantes de un tipo diferente de sabor. En cuanto a la pregunta acerca de la no-conmutativa de pesos para el linfogranuloma venéreo, que no puede ofrecer ninguna pista, excepto tal vez para sugerir que buscan en el trabajo anterior sobre la no-conmutativa extensiones de la LGV teorema, tales como la extensión demostrado en "no conmutativa Schur Funciones y sus Aplicaciones" por el Fomin y Greene (disponible desde el sitio web del Fomin). Pero esto probablemente no es muy útil, ya que en su caso, el anillo es casi conmutativa.

---

Con respecto a tu pregunta sobre el rango y la firma, no es mucho lo que uno podría explorar. Como empezar, si usted mira el Laplaciano de la matriz asociada a un grafo, entonces el rango tiene un claro combinatoria es decir, que mide el número de componentes conectados de la gráfica (así, el número máximo de aristas en una acíclicos abarca subgrafo, para ser más precisos), pero no hay mucho que decir acerca de la firma ya que todos los valores propios de la Laplaciano son no negativos. Cuando se trata de la matriz de adyacencia del grafo, la conexión a la combinatoria de las cantidades pone aún más débil (pero es un área de investigación), por ejemplo, el rango de la matriz de adyacencia de conjeturó que tiene algo que ver con la cromática número de la gráfica, pero la relación puede no ser tan agradable como fue demostrado por Alon y Seymour. Ha habido algunos trabajos sobre la interpretación de la firma de la matriz de adyacencia así, con algunos de los primeros artículos de Torgasev (por ejemplo aquí), pero es de la misma naturaleza. Uno puede calcular el rango y la firma fácilmente por los métodos del álgebra lineal y por lo tanto espera utilizar estas obligado a teoría de grafos quatities, pero al parecer no la otra manera alrededor.