¿Por qué el cuadrado permanentes suma a 1?

Question

Considere la posibilidad de una $n^2$ $n^2$ real ortogonal de la matriz $M$. Deje $M'$ $n^2$ $n$ matriz creada por la selección de la primera $n$ columnas de $M$.

Ahora considere todos los $n$ $n$ matrices $A_i$ creado por seleccionar exactamente $n$ no necesariamente distintos filas de $M'$ con reemplazo. Hay ${n^2+n-1 \choose n}$ tal matricex $A_i$.

Deje $s_1,\dots,s_k$ ser el número de veces que cada fila seleccionada y deje $\tau = \prod_i s_i!$.

Como un ejemplo, si $n=2$ $A_i$ está formado por la elección de la fila $1$ dos veces de $M'$ $A_i$ $2$ $2$ matriz con dos filas iguales. Tenemos $s_1 = 2$$\tau = 2$.

Deje $\operatorname{perm}$ ser la función que calcula la permanente de una matriz.

¿Por qué es el verdadero?

$$\sum \frac{\operatorname{perm}(A_i)^2}{\tau} = 1?$$

Answer 1

Supongamos que nos fueron a recoger $n$ filas con el reemplazo, pero ahora con el fin de importar. En otras palabras, debemos elegir un orden de $n$-tupla de filas $(r_1, r_2, \dots, r_n)$ (ya tenemos $n^2$ opciones para cada fila, no $n^{2n}$ total de maneras de escoger las filas). A continuación, para un determinado $s_1, s_2, \dots, s_k$, el número de maneras de escoger las filas de modo que la fila $i$ es elegido exactamente $s_i$ veces es entonces $\frac{n!}{\tau}$. Así, en este nuevo marco, podemos expresar el resultado estamos tratando de mostrar como

$$\sum_{r_1, \dots, r_n} \textrm{perm}(A)^2 = n!.$$

Podemos escribir la permanente como una suma de más de permutaciones, es decir, $$\textrm{perm}(A)=\sum_{\sigma} \prod_{i=1}^n A_{i, \sigma(i)} = \sum_{\sigma} \prod_{i=1}^n M_{r_i, \sigma(i)}$$ Cuando nos cuadrado de $\textrm{perm}(A)$, podemos ver como una suma de más de dos permutaciones, de modo que el lado izquierdo de la primera muestra de la ecuación puede ser escrita como $$\sum_{r_1, \dots, r_n} \sum_{\sigma} \sum_{\tau} \prod_{i=1}^n M_{r_i, \sigma(i)} M_{r_i, \tau(i)} = \sum_{\sigma} \sum_{\tau} \sum_{r_1, \dots, r_n} \prod_{i=1}^n M_{r_i, \sigma(i)} M_{r_i, \tau(i)}$$ El interior de la suma y el producto factorizar! Tenemos $$\sum_{r_1, \dots, r_n} \prod_{i=1}^n M_{r_i, \sigma(i)} M_{r_i, \tau(i)} = \prod_{i=1}^n \left(\sum_{j=1}^{n^2} M_{j, \sigma(i)} M_{j, \tau(i)}\right)$$ Ahora el interior de la suma es sólo el producto interior entre columnas $\sigma(i)$$\tau(i)$$M$. En particular, si $\sigma(i) \neq \tau(i)$, interior la suma (y por lo tanto el producto) es $0$.

Si, por otro lado, $\sigma=\tau$, entonces el interior de la suma es $1$ por cada $i$, y el producto es igual a $1$. Así que cada permutación contribuye exactamente $1$, y la totalidad de la suma es $n!$, que es lo que estamos buscando.