Las interpretaciones de permanente

Question

La interpretación estándar de la permanente de una $0/1$ matriz si se considera como un biadjacency matriz de un grafo es bipartito número de perfecto matchings de la gráfica o si se considera como una matriz de adyacencia de un grafo dirigido es el número de vértices disjuntos ciclo cubre.

Dada la importancia de la permanente como una $\#P$ completar problema que se presenta en diversos contextos, tales como celosías y poliedros hay otros que no trivial interpretaciones de la permanente?

Yo estaría interesado en cualquiera de las interpretaciones de la teoría de los números (conozco a ninguno, y si hay uno que sería muy interesante) o la geometría algebraica (aunque tenue que puede ser), particularmente desde que el último se contempla la posibilidad de ser útil en el estudio de la Permanente-Determinante problema.

Me atrevería a considerar esto como una interpretación especial de las matrices. Permanente representa números naturales en una forma canónica a través de las matrices Es cada entero positivo permanente de algunos 0-1 de la matriz?. Sin embargo, si hay alguna multiplicativo y aditivo de la propiedad que viene junto con él que iba a ser muy grande y hasta ahora yo no lo veo pero parece que debe ser manejable para inventar interesantes las clases de matrices que han interpretaciones específicas.

Answer 1

En la física cuántica, el estado de no-interacción de las partículas que son fermiones es representado por un determinante, mientras que para los bosones es permanente. La complejidad computacional de la evaluación de un permanente explica por qué es posible el diseño de un ordenador cuántico con óptica lineal (LOQC) --- así que con noninteracting de los fotones, que son bosones. Si el ordenador cuántico sería la evaluación de determinantes no habría speedup con respecto a un clásico de la computadora, de modo que los electrones (que son fermiones), será necesario recurrir a las interacciones de lograr alguna ganancia.

Answer 2

Si usted no está consciente de ello, entonces el siguiente, ampliamente conocido 'interpretaciones' de la permanente debe ser señalado.

0. Una definición de la interpretación y generalización (permanentes son especiales immanants). Deje $\mathbb{L}_n$ denotar el entramado de los subgrupos del grupo simétrico $\mathfrak{S}_n$. Para cada finito de permutación grupo $G\in\mathbb{L}_n$ y cualquier irreductible carácter $\chi\colon G\rightarrow\mathbb{C}^\times$, la función

$f_\chi^G\colon\color{white}{(a_{i,j})_{(i,j)\in n\times n}}\mathbb{C}^{n\times n}\rightarrow\mathbb{C}$

${\quad}{\quad}\quad\ \ \ (a_{i,j})_{(i,j)\in n\times n}\mapsto \sum_{g\in G}\quad \chi(g)\cdot\prod_{i\in n} a_{i,g(i)}$

se llama la immanant¹ w.r.t. $\chi$.

Si $\chi$ es la función que está en constante $1$, también se llama el personaje principal, entonces el immanant $f_\chi^{\mathfrak{S}_n}$ es sólo la permanente de $(a_{i,j})_{(i,j)\in n\times n}$.

En ese sentido: cada permanente es un immanant.

(Uno puede contar esto como una 'interpretación', una especie de. Digo 'definición' de arriba, ya que aquí la definición de "permanente" se interpreta en el sentido de la construcción de una mayor definición que la permanente no es sino una instancia de.)

1.Una hipótesis de interpretación (Lieb del Permantal Dominio Conjetura: los permanentes están en la parte superior de los elementos de un poset en el conjunto de todos los irreducibles de caracteres del grupo simétrico en $n$ elementos; no debe confundirse con el llamado, al parecer, todavía abierto). Para cada una de las $G\in\mathbb{L}_n$ deje $\mathbb{K}_G$ denota el conjunto de todos los irreductible de caracteres complejos de $G$. A continuación, $\mathbb{K}_G$ tiene las siguientes poset estructura $\leq$, en otras palabras, es parcialmente ordenado por la siguiente definición.

Deje $\chi_0\leq \chi_1$ si y sólo si (usando la notación de 0.)

para todos los Hermitian positivo-semidefinite matrices $A\in\mathbb{C}^{n\times n}$ tenemos $\frac{f_{\chi_0}^G(A)}{\chi_0(\mathrm{id})}\leq\frac{f_{\chi_1}^G(A)}{\chi_1(\mathrm{id})}$.

Se trata de un famoso teorema² de la Issai Schur que la alternancia de carácter $\mathrm{sgn}$ es un fondo de los elementos de la poset $(\mathbb{K}_{\mathfrak{S}_n},\leq)$.

(Y el immanant w.r.t. $\mathrm{sgn}$ es sólo el factor determinante.)

Un notorio conjetura (y esto es lo que quiero decir por "conjetural de interpretación' de la permanente) es si por cualquier $G\in\mathbb{L}_n$ alguna, el personaje principal es un elemento de la parte superior de la poset $(\mathbb{K}_G,\leq)$.

Esto va por el nombre de 'Permanental Dominio Conjetura'.

Explícitamente, el (al parecer, todavía abierto) Permanental Dominio Conjetura de³ estados:

Para cada Hermitian positivo semidefinite $A\in\mathbb{C}^{n\times n}$

para cada subgrupo $G$ de % de $\mathfrak{S}_n$

para cada carácter irreductible $\chi\colon G\rightarrow\mathbb{C}^\times $

tenemos $\frac{1}{\chi(\mathrm{id})}\sum_{g\in G}\chi(g)\prod_{i\in n}a_{i,g(i)}\leq\mathrm{per}(A)$.

Para $n=4$, una explícita Hermitian positivo-semidefinite matriz es conocido que logra la igualdad en la hipótesis de igualdad. (Estoy escribiendo de memoria aquí; una vez vi a esta matriz, sin embargo, no encuentro ahora).

Una 2016 encuesta sobre conjeturas sobre las desigualdades que implican permanentes es Fuzhen Zhang: Una actualización de algunos de carácter permanente conjeturas. Volumen 4, Número 1 (Agosto De 2016). De Zhang de trabajo que tome las siguientes:

al final de la cual vemos aparecer lo que vino a ser conocido por el (a mi juicio) un poco sillily nombre y engañosamente-nfamed Permanente En la parte Superior Conjetura' publicado por Soules en 1966 su tesis. La conjetura de los estados que la permanente de un Hermitian positiva semi-definida la matriz de $A$ es igual a la (necesidad real) mayor autovalor de la Schur potencia de la matriz de $A$.

Tenga en cuenta que Zhang hace hincapié en algo que suena como que las máquinas electrónicas son necesarias para controlar Shchesnovich del contraejemplo.

De Zhang encima de la encuesta también me tome el siguiente 'diagrama' (en el informal, en el sentido cotidiano de 'diagrama'):

en 'Soules OLLA", un poco de goofily (creo que⁴), se refiere a la "Permanente En la parte Superior' conjetura, y en 'Lieb por dom" se refiere a abierto 'Permanental Dominio Conjetura', y en el cual he de color rojo lo que parece ahora ser conocido para ser semánticamente falso, de color amarillo, lo que parece ser abierto conjeturas, y de color verde el material sintáctico implicaciones que se sabe que existen. (Soules, Bapat y Sunder puede tomar consuelo en el hecho de que hay son muchos matemáticos que encontrar material implicaciones al menos tan interesante como la semántica de la verdad de los valores; y también, desde lo que yo entiendo de esto hasta ahora, la certificación de Shchesnovich la refutación parece ser un interesante y útil problema en sí mismo.⁵)

EDIT: Como un ejercicio en el método importante de criticar, y, a continuación, la mejora de la propia respuestas, permítanme añadir el siguiente

A la luz de Ryo Taba la publicación, parece incorrecto decir que la permanente puede ser interpretado como el elemento de la parte superior de un poset estructura. De una buena interpretación exijo que se haga a través de y (como es, por ejemplo, la interpretación de el ritmo del día y de la noche como el efecto de un eje inclinado de la revolución), que esta interpretación no parece ser: es demasiado débil una declaración en la dimensión $n=3$, como Taba más aguda estimación de la muestra.

¹ _{Idioma-peligro: la ortografía correcta en la contemporánea discurso matemático son como los que se dan aquí: imman$\mathbf{a}$nt, sin embargo, perman$\mathbf{e}$nt. Tenga en cuenta que 'imman$\mathbf{e}$nt' léxicamente también existe. Tenga en cuenta también que hay es la siguiente aleatoriedad: en el caso de 'permanente' habitual del adjetivo también se hizo el sustantivo. En el caso de 'inmanente', por alguna razón la gente evitado que el adjetivo al sustantivo, y se utiliza la variante ortográfica 'immanant'.}

² _{Issai Schur: Uber endliche Gruppen und Hermitische Formen, Mathematische Zeitschrift 1, pág. 184-207.}

³ _{se me señaló hace poco (que no había cumplido con esto, se parte de la escritura de lo que me acordé de lo que yo aprendí cuando trabajé en el recuento de inicio de sesión matrices, y no era consciente de este 2015 del desarrollo, cuando escribí mi respuesta) que una refutación de 'Soules OLLA' ha sido recientemente publicado: Valery S. Shchesnovich: La permanente-on-top conjetura es falsa. Álgebra lineal y sus Aplicaciones Volumen 490, 1 de febrero de 2016, las Páginas 196-201 El contraejemplo es dado en la dimensión $n=5$. También, hay una impresionante primaria de la prueba por Ryo Tabata en Hiroshima Matemática Diario 40 (2010), 205-213 que el Permanental Dominio Conjetura es "más que la verdad' en la dimensión $n=3$ e $\large \text{for $G=$alternating group on $n$ elements}$: descuento de la introducción y referencias, Ryo Tabata en un mero cinco páginas ofrece una prueba, legible por que nadie se entere de alta escuela de cálculo y álgebra lineal sobre $\mathbb{C}$, de un extraño fortalecimiento de la Permantental Domimance Conjetura, en sustitución de la cota superior de la $\mathrm{per}(A)$ por $\lambda\cdot \mathrm{per}(A) + (1-\lambda)\cdot \mathrm{det}(A)$ donde $\lambda=\frac{1}{\sqrt[3]{2}}$. I. e., un trivial combinación lineal convexa de la permanente y el determinante es un límite superior en la dimensión $n=3$. $\large \text{Again, please note that Tabata's proof was formulated for characters of the alternating group only.}$}

En la dimensión $n=4$, incluso la verdad de 'Soules OLLA', parece ser un problema abierto. (Cf. comentarios de Zhang en la loc. cit. para el efecto de que Shchesnovich intentado desacreditarla)

⁴ _{creo que es justo decir que el editor de la encuesta cito debería haber dado Zhang mejor editorial de asesoramiento y servicios. Uno lingüística infelicity persigue a la siguiente. No es el autor quien es la culpa.}

⁵ _{Esto no es poner en duda la exactitud de Shchesnovich del resultado. Me llevó a escribir esto porque parece que no ha utilizado los cálculos numéricos cuando la comprobación de Shchesnovich del resultado. Y los cálculos numéricos son una ciencia importante de su propio, lleno de trampas.}