¿Cuáles son las aplicaciones de los inmanantes?

Question

Definiciones de determinante:

$\det(A) = \sum_{\sigma \in S_n}\operatorname{sgn} \sigma\prod_{i}a_{i, \sigma(i)}$

y permanente:

$\mathrm{per}(A) = \sum_{\sigma \in S_n}\prod_{i}a_{i, \sigma(i)}$

admite una generalización en la forma de immanant:

$\mathrm{Imm}_{\lambda}(A) = \sum_{\sigma \in S_n}\chi_{\lambda}(\sigma)\prod_{i}a_{i, \sigma(i)}$

donde $\lambda$ etiquetas irreductible representaciones de $S_n$ e $\chi_{\lambda}$ es el carácter. Determinante y permanente se ve fácilmente a casos especiales de $\mathrm{Imm}_{\lambda}$.

Mientras que los factores determinantes son omnipresentes en las matemáticas y las permanentes también tienen muchas aplicaciones, esp. en problemas de combinatoria, otros tipos de immanants parece ser rara vez se utiliza. Hay algún problema en que el uso de $\mathrm{Imm}_{\lambda}$ otros de $\det$ e $\operatorname{per}$ es natural?

Answer 1

Sí, la immanants de positiva definida matrices son muy naturales y sus estudios de volver a I. Schur (1918). Empezar con "la Positividad de los Problemas y Conjeturas en la Combinatoria Algebraica" de la encuesta por R. Stanley y sigue las referencias, en particular "Immanants de la combinatoria de las matrices" por I. P. Goulden y D. M. Jackson, y "Hecke Álgebra Personajes y Immanant Conjeturas" por M. Haiman, y varios trabajos de J. Stembridge. Debo mencionar que en los últimos años ha habido varios avances en esta dirección (véase, por ejemplo, este papel por B. Rhoades y M. Skandera, y un número de seguimiento de trabajos).

Answer 2

Un problema con la aplicación de immanants es que después de expresar algo en términos de immanants, no podría estar más cerca de cálculo, y no se puede manipular fácilmente las expresiones de immanants. Por ejemplo, supongamos que usted desea para contar los ciclos Hamiltonianos en un gráfico (positividad resuelve el ciclo Hamiltoniano del problema). Se observa que esta se puede expresar como una combinación lineal de immanants de la matriz de adyacencia:

$$\sum_{\sigma \in S_n} f(\sigma)\prod_{i}a_{i, \sigma(i)} $$

donde $f(\sigma) = 1$ al $\sigma$ es $n$-ciclo y $0$ lo contrario. Desde $f$ es constante en las clases conjugacy, se puede descomponer como una combinación lineal de los personajes. Sin embargo, el ciclo Hamiltoniano problema es NP-completo, por lo que no sería sorprendente si había una forma rápida de calcular esta combinación lineal de immanants. Tampoco hay muchos términos para calcular, o de estos términos son difíciles de calcular, o ambos, incluso si usted está tratando de determinar si el resultado es positivo.

Answer 3

Creo que Immanants también son importantes en la teoría de la complejidad, ya que proporcionan un espectro de problemas con casos extremos de calcular el determinante (tiempo polinomio) para el cómputo de la permanente (#P-completo). P. Burgisser tiene algunos artículos en esta dirección, por ejemplo, "La complejidad computacional de Immanants". Ver también "la Complejidad y la integridad de Immanants" por J-L. Brylinski y R. Brylinski.

Answer 4

Este es un comentario, pero demasiado largo, así que la he puesto aquí abajo.

He encontrado el siguiente enlace que muestra varios documentos de debate sobre Immanants y conjeturas relacionadas con ellos. La mayoría de las aplicaciones mencionadas parecen ser gráfico teórico.

Enlace a la entrada en Immanants

El único lugar donde he visto anteriormente Immanants es el famoso *Permanente en la parte Superior" conjetura, que establece que para cualquier positivo semidefinite matriz $A$, tenemos

$$\text{per}(A) \ge \overline{\text{Imm}}_\chi(A),$$ donde $\overline{\text{Imm}}_\chi(A)$ denota la normalizado Immanant.

Pero no creo que eso cuenta como una "aplicación".