El famoso teorema Birkhoff-von Neumann afirma que toda matriz doblemente estocástica puede escribirse como una combinación convexa de matrices de permutación.
La cuestión es señalar diferentes generalizaciones de este teorema, diferentes "no generalizaciones", es decir, casos en los que una generalización esperada es falsa, y describir brevemente el contexto de estas generalizaciones.
Una pregunta relacionada con el MO: Muestreo del politopo de Birkhoff
Hago un poco de trampa para dar esta respuesta, porque estoy bastante seguro de que es parte de la motivación de Gil al hacer la pregunta. La generalización más natural de la hipótesis de Birkhoff a la probabilidad cuántica sólo es cierta para los qubits. (También podría ser cierta para un tensor de qubits un sistema clásico; no he comprobado ese caso).
Un espacio cuantificable es un álgebra de von Neumann. Lo que más nos interesa es el caso de dimensión finita, donde clásicamente "espacio medible" es sólo un nombre elegante para las variables aleatorias en un conjunto finito. Un álgebra de von Neumann de dimensión finita es una suma directa de álgebras matriciales. En particular, $M_2$ se llama qubit y $M_d$ se denomina qudit.
Para abreviar, la hipótesis de Birkhoff puede afirmarse para una suma directa de $a$ copias de $M_b$ o $aM_b$ . En este entorno, un mapa doblemente estocástico $E$ es un mapa lineal desde $aM_b$ a sí mismo que preserva la traza, que preserva el elemento de identidad, y que es completamente positivo. En esta configuración, $E$ es completamente positiva si toma elementos semidefinidos positivos de $aM_b$ a elementos semidefinidos positivos, y si $E \otimes I$ también tiene esa propiedad en el álgebra $aM_b \otimes N$ para otro von Neumann o $C^*$ -Álgebra $N$ . El análogo natural de las matrices de permutación son los automorfismos del álgebra * de $aM_b$ . Se trata de permutaciones de los bloques de la matriz, compuestas con mapas de la forma $E(x) = uxu^*$ , donde $u$ es un elemento unitario de $aM_b$ . La cuestión, como antes, es si los mapas doblemente estocásticos son el casco convexo de los automorfismos.
Esta hipótesis de Birkhoff es cierta para $M_2$ , falso para $M_d$ para $d \ge 3$ y debería comprobarlo para $nM_2$ . Es cierto para $aM_1 = a\mathbb{C}$ porque entonces es el teorema habitual de Birkhoff-von Neumann.
Me queda la duda de dos versiones clásicas infinitas del teorema de Birkhoff, para las álgebras $\ell^\infty(\mathbb{N})$ y $L^\infty([0,1])$ . En el primer caso, uno se preguntaría si cualquier mapa estocástico que preserve la medida de recuento (aunque la medida de recuento no esté normalizada) es una suma convexa infinita de permutaciones de $\mathbb{N}$ . En este último caso, si cualquier mapa estocástico que preserva la medida de Lebesgue es una integral convexa de permutaciones que preservan la medida de $[0,1]$ . Adenda: Al menos el caso del infinito discreto se aborda, con resultados generalmente positivos, en esta revisión y en esta revisión más antigua . El documento más antiguo también plantea la cuestión continua, pero sin resultados. Sin embargo, buscando un poco más en Google, encontré este documento de contraejemplo .
Ya que Gil pide una referencia, una reciente es Canales cuánticos unitales - Estructura convexa y revivir el teorema de Birkhoff de Mendl y Wolf.
Aquí también hay una generalización combinatoria más ortodoxa del teorema de Birkhoff, y también otro caso que encontré una vez que está entre una generalización y una no-generalización. Como Gil ofrece ahora una recompensa, quizá sea mejor fusionar esta respuesta con la otra.
Una matriz doblemente estocástica puede interpretarse como un flujo a través de un grafo dirigido, con capacidades unitarias. (Véase Matriz unimodular en la Wikipedia; lo aprendí hace tiempo de Jesús de Loera). Cualquier gráfico de este tipo tiene un politopo de flujos, llamado politopo de flujos de red. Cualquier politopo de flujos de red tiene vértices enteros, porque es un politopo totalmente unimodular.
Un politopo totalmente unimodular es un politopo cuyas facetas tienen ecuaciones enteras, y con la propiedad de que cualquier colección máxima y linealmente independiente de facetas se interseca en un punto entero porque su matriz tiene determinante $\pm 1$ . En particular, los vértices son tales intersecciones, por lo que los vértices son todos integrales. Esta es una amplia generalización del teorema de Birkhoff que proviene de la generalización de una de las pruebas del teorema de Birkhoff.
Ejemplo: Una matriz de signo alterno equivale a una orientación de hielo cuadrado de una rejilla cuadrada. Las orientaciones del hielo cuadrado pueden definirse mediante un flujo de red, por lo que se obtiene un politopo de matriz de signo alterno. El teorema de Birkhoff generalizado en este caso dice que cada vértice del politopo es una matriz de signo alterno, de hecho que cada punto entero del $n$ -es una suma de $n$ matrices de signo alterno.
El otro caso que encontré fue el politopo de coincidencias perfectas fraccionadas de un conjunto no bipartito con $2n$ elementos. En cambio, el politopo de Birkhoff es el caso de un conjunto bipartito con $n$ elementos de cada tipo. Por definición, es el politopo de pesos no negativos asignados a las aristas del grafo completo en $2n$ vértices, de forma que el peso total en cada vértice sea 1. En sentido estricto, el teorema de Birkhoff es falso; no todos los vértices son una combinación perfecta. En su lugar, todos los vértices son combinaciones de pares emparejados, y los ciclos Impares con peso $\frac12$ .
A primera vista, esto parece una mala noticia para la aplicación del cálculo de un emparejamiento perfecto o del emparejamiento perfecto óptimo de un gráfico. En efecto, si se toma el casco convexo de los emparejamientos perfectos, el resultado es un politopo con un número exponencial de facetas. Sin embargo, existe un buen algoritmo de todos modos; hay una versión del algoritmo simplex que sólo utiliza polinomialmente muchas de las facetas.
He encontrado un artículo sobre una generalización del teorema Birkhoff-von Neumann aquí:
http://cowles.econ.yale.edu/conferences/2009/sum-09/theory/che.pdf ( La máquina del retroceso )
Los autores son Eric Budish, Yeon-Koo Che, Fuhito Kojima y Paul Milgram.
Este es el resumen:
El teorema de Birkhoff-von Neumann muestra que cualquier matriz bistocástica puede escribirse como una combinación convexa de matrices de permutación. En particular, en un n objetos deben ser asignados a n agentes, un objeto por agente, cualquier matriz de matriz de asignación aleatoria puede resolverse en una asignación determinista de acuerdo con la matriz de probabilidad especificada. Generalizamos el teorema para dar cabida a un complejo conjunto de restricciones que se encuentran en muchos problemas de diseño de mercados de la vida real. En concreto, el teorema puede extenderse a cualquier entorno en el que el conjunto de restricciones pueda puede dividirse en dos jerarquías. Además, demostramos que esta estructura de dos jerarquías constituye un dominio máximo para el teorema, y proporcionamos un algoritmo constructivo para implementar una asignación aleatoria bajo restricciones bijerárquicas. Proporcionamos varias aplicaciones, incluyendo (i) la asignación aleatoria de una sola unidad, como la elección de escuela; (ii) asignación aleatoria de múltiples unidades, como la asignación de cursos y la división equitativa; y (iii) problemas de emparejamiento de dos caras, como la asignación de cursos y la división equitativa. problemas de emparejamiento de dos caras, como la programación de partidos deportivos entre ligas. El método El mismo método también tiene aplicaciones más allá de la economía, ya que generaliza los resultados anteriores sobre de minimización de la duración de la vida en la literatura de ciencias de la computación.
También he encontrado una tesis de maestría que implicaba la generalización de una matriz a una hipermatriz, una matriz en dimensiones superiores. Así que un ejemplo sería una matriz cúbica de números en lugar de un cuadrado. Demuestra una generalización a las matrices tridimensionales que se llaman bloques. También hay algunas preguntas abiertas. Me pareció interesante ya que me he preguntado sobre la ampliación de las dos dimensiones de las matrices a tres coordenadas y ver qué pasaba. Está disponible aquí:
https://ritdml.rit.edu/dspace/bitstream/1850/5967/1/NReffThesis05-18-2007.pdf
Hay un artículo relevante de Gromova sobre las matrices de alta dimensión:
Gromova, M. B., The Birkhoff-von Neumann theorem for polystochastic matrices. (Ruso) Investigación de operaciones y simulación estadística, No. 2 (Ruso), pp. 3-15, 149. Izdat. Leningrado. Univ., Leningrado, 1974. Se tradujo al inglés a principios de los años 90.
La reseña de MR de George P. Barker dice lo siguiente: En la sección 1 el autor da las definiciones básicas e introduce una noción del espectro de una matriz multidimensional como un vector. A continuación se formula el teorema básico que da las condiciones necesarias y suficientes para que un vector sea el espectro de una matriz extrema. La condición necesaria del teorema básico consiste en una generalización directa del teorema de Birkhoff-von Neumann.
Un documento relacionado es: Brualdi, R. A.; Csima, J. Extremal plane stochastic matrices of dimension three. Linear Algebra and Appl. 11 (1975), no. 2, 105-133.
y un documento más antiguo con cierta relevancia es: Jurkat, W. B.; Ryser, H. J. Configuraciones extremas y teoremas de descomposición. I. J. Algebra 8 1968 194-222.
El caso restante es en realidad H4. Para este caso la conjetura es falsa, ya que encontré 1063 órbitas de facetas. En el mismo artículo se afirma que para F4 el casco convexo viene dado por los tensores de Birkhoff. Pero esto es falso ya que encontré otra órbita definida por una matriz de rango 3. Ver detalles allí ( La máquina del retroceso )
Dave Perkinson y sus coautores han estudiado los subpolitopos del politopo de Birkhoff-von Neumann, en el sentido de que consideran los cascos convexos de las matrices de permutación correspondientes a ciertos subgrupos de $S_n$ . Véase, por ejemplo su trabajo con Jeff Hood ( La máquina del retroceso ) para el caso $A_n$ .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
