Puntos fijos de grupos de permutación

Como en muchos casos donde una variable aleatoria es igual al número de ocurrencias de varios eventos, una técnica fructífera es escribir esa variable aleatoria como una suma de variables aleatorias indicadoras.

Dejar$X_i$ser una variable aleatoria que es$1$si$\sigma(i)=i$, y$0$de lo contrario. Alquiler$X=X_1+\dots+X_n$, esto significa que$f(\sigma)=X$. Resulta que

$$E[f(\sigma)]=E[X]=E[X_1]+\dots+E[X_n]=nE[X_1],$$ $$E[f(\sigma)^2]=E[(X_1+\dots+X_n)^2]\stackrel{*}=nE[X_1^2]+n(n-1)E[X_1X_2]$$ En$\stackrel{*}=$, me expandí$(X_1+\dots+X_n)^2$, distribuyó el$E[]$, y luego recolectó términos distribuidos idénticamente.

Todo lo que queda es calcular$E[X_1]$,$E[X_1^2]$, y$E[X_1X_2]$. Estas variables aleatorias solo toman los valores$0$y$1$, por lo que calcular sus expectativas implica calcular una cierta probabilidad. Te dejo el resto.

Dejar$G$ser un grupo,$X$un conjunto, y:

$$\begin{alignat}{1} G\times X&\longrightarrow& X \\ (g,x)&\longmapsto& gx \\ \tag 1 \end{alignat}$$ a$G$-acción sobre$X$. Entonces:

Reclamo _ Para$X_i=X$ $(i=1,\dots,k)$,$\Pi X:=\prod_{i=1}^kX_i$, y$\bar x:=(x_1,\dots,x_k)\in\Pi X$, el mapa:

$$\begin{alignat}{2} G\times\Pi X&\longrightarrow &&\space\Pi X \\ (g,\bar x)&\longmapsto &&\space g\star \bar x:=(gx_1,\dots,gx_k) \\ \tag 2 \end{alignat}$$

es un$G$-acción sobre$\Pi X$.

prueba _ Tenemos que confirmar que el mapa "$\star$" cumple las dos propiedades para una acción de grupo. De hecho:

1. $$\begin{alignat}{1} e\star\bar x &= (ex_1,\dots,ex_k) \\ &= (x_1,\dots,x_k) \\ &= \bar x \end{alignat}$$ $\forall\bar x\in \Pi X$;
2. $$\begin{alignat}{1} g\star(h\star\bar x) &= g\star(hx_1,\dots,hx_k) \\ &= (g(hx_1),\dots,g(hx_k)) \\ &= ((gh)x_1,\dots,(gh)x_k) \\ &=(gh)\star\bar x \\ \end{alignat}$$ $\forall g,h\in G, \forall\bar x\in \Pi X$.$\space\space\space\Box$

El estabilizador puntual para la acción "$\star$" se lee:

$$\begin{alignat}{1} \operatorname{Stab}_\star(\bar x) &= \{g\in G\mid g\star\bar x=\bar x\} \\ &= \{g\in G\mid (gx_1=x_1)\wedge\dots\wedge(gx_k=x_k)\} \\ &=\bigcap_{i=1}^k\operatorname{Stab}(x_i) \\ \tag 3 \end{alignat}$$

Además:

$$\begin{alignat}{1} \operatorname{Fix}_\star(g) &= \{\bar x\in \Pi X\mid g\star\bar x=\bar x\} \\ &= \{\bar x\in \Pi X\mid (gx_1=x_1)\wedge\dots\wedge(gx_k=x_k)\} \\ \tag 4 \end{alignat}$$

De dónde$\bar x\in \operatorname{Fix}_\star(g)\iff x_i\in\operatorname{Fix}(g), i=1,\dots,k$. Entonces, cada$k$-tupla ($=$ disposición ordenada de$k$elementos de un conjunto, donde se permite la repetición ) de elementos de$\operatorname{Fix}(g)$da lugar a un$\bar x\in \operatorname{Fix}_\star(g)$, y viceversa. Así, para finitos$X$:

$$\left|\operatorname{Fix}_\star(g)\right|=\left|\operatorname{Fix}(g)\right|^k \tag 5$$

(ver esta página Wiki , sección " Permutaciones con repetición ").

Para tu caso b , toma$G=S_n$,$X=\{1,\dots,n\}$y$k=2$. Por$(3)$,$\operatorname{Stab}_\star((i,j))=\operatorname{Stab}(i)\cap\operatorname{Stab}(j)$, de donde$\left|\operatorname{Stab}_\star((i,j))\right|=(n-1)!$para$j=i$, y$\left|\operatorname{Stab}_\star((i,j))\right|=(n-2)!$para$j\ne i$. Por lo tanto, debe haber precisamente dos órbitas para la acción "$\star$"$^\dagger$. Ahora, aplicando el Lema de Burnside a la acción "$\star$":

$$\frac{1}{|S_n|}\sum_{\sigma\in S_n}\left|\operatorname{Fix}_\star(\sigma)\right|=2 \tag 6$$

y finalmente, recordando$(5)$:

$$\frac{1}{|S_n|}\sum_{\sigma\in S_n}\left|\operatorname{Fix}(\sigma)\right|^2=2 \tag 7$$

cual es tu punto b . (Su punto a es el mismo resultado aplicado a la acción transitiva en una sola copia de$X$.)

---

$^\dagger$De hecho, por el Teorema del Estabilizador de Órbita,$\left|\operatorname{Stab}_\star((i,j))\right|=(n-1)!$implica$\left|O_\star((i,j))\right|=n$, y$\left|\operatorname{Stab}_\star((i,j))\right|=(n-2)!$implica$\left|O_\star((i,j))\right|=n(n-1)$. Pero el conjunto de órbitas es una partición del conjunto actuado, cuyo tamaño es$n^2$, de donde$kn+ln(n-1)=n^2$o equivalente,$k+l(n-1)=n$. Para$n=2$, esto produce$k+l=2$; para$n>2$,$l=\frac{n-k}{n-1}$entero implica$k=1$, lo que a su vez implica$l=1$, y luego otra vez$k+l=2$. Entonces, la acción "$\star$" tiene dos órbitas para cada$n\ge 2$.

Aquí hay una prueba basada en álgebra lineal. Utiliza productos Kronecker (indicados$\otimes$) y tiene un toque de teoría de la representación, pero realmente no requiere ningún conocimiento más que la teoría básica de grupos y un álgebra lineal algo sofisticada.

notación:$P_g$para$g\in S_n$denota el estándar ($n\times n$) representación de matriz de permutación para alguna permutación$g$.

Parte 1: Idempotencia
$Z := \Big(\frac{1}{\vert S_n\vert}\sum_{g\in S_n}P_g\otimes P_g\Big)$
Entonces$Z$es idempotente.

Prueba:
$Z^2$
$=\Big(\frac{1}{\vert S_n\vert}\sum_{g\in S_n}P_g\otimes P_g\Big) \Big(\frac{1}{\vert S_n\vert}\sum_{g'\in S_n}P_{g'}\otimes P_{g'}\Big)$
$=\frac{1}{\vert S_n\vert^2}\sum_{g\in S_n}\Big(\big(P_g\otimes P_g\big) \sum_{g'\in S_n}P_{g'}\otimes P_{g'}\Big)$
$=\frac{1}{\vert S_n\vert^2}\sum_{g\in S_n}\Big( \sum_{g'\in S_n}(P_gP_{g'})\otimes (P_gP_{g'})\Big)$
$=\frac{1}{\vert S_n\vert^2}\sum_{g\in S_n}\Big( \sum_{g''\in S_n}(P_{g''})\otimes (P_{g''})\Big)$
$=\frac{1}{\vert S_n\vert^2}\sum_{g\in S_n}\Big( \vert S_n\vert\cdot Z\Big)$
$=Z$

entonces$Z$tiene todos los valores propios$0$o$1$y
$\text{trace}\big(Z\big) = \frac{1}{\vert S_n\vert}\sum_{g\in S_n}\text{trace}\big(P_g\otimes P_g\big) = \frac{1}{\vert S_n\vert}\sum_{g\in S_n}\text{trace}\big(P_g\big)^2= \frac{1}{\vert S_n\vert}\sum_{g\in S_n}f\big(g\big)^2$cuenta el número de valores propios iguales a 1 para la matriz$Z$. Nuestro objetivo es mostrar esto$=2$. en particular desde$Z$es una suma de matrices reales no negativas, por lo que es real no negativa y podemos usar la teoría de Perron-Frobenius.

Parte 2: Raíces de Perron / Órbitas
a través del examen de (forma de matriz de)$S_n$la acción de sobre los vectores base estándar para el espacio vectorial$\mathbb R^{n\times n}$

Considere el conjunto ordenado$M$, que contiene los vectores base estándar para el espacio vectorial$\mathbb R^{n\times n}$, con el primero$n$ $m_i$siendo los 'simétricos' (es decir, con la traza 1).

Ahora considere cómo$S_n$actúa sobre$M$por conjugación. Nuevamente usando nuestra representación de permutación estándar tenemos, por$X\in M$
$P_gX P_g^{-1} = P_g X P_g^T\in M$.

En particular, la acción por conjugación sobre$M$es una transformación lineal, por lo que podemos escribir
$\mathbf M =\bigg[\begin{array}{c|c|c|c|c}M_1 & M_2 \end{array}\bigg]$dónde$M_1$tiene el primero$n$vectores colocados uno al lado del otro y$M_2$tiene los demás, observando el orden antes mencionado

para$g\in S_n$
$T_g\mathbf M = \mathbf MU_g$
dónde$U_g$es la matriz de permutación asociada con$T_g$la acción de$\mathbf M$. Centrándonos en la acción de conjugación por matrices elementales de tipo 2, podemos demostrar que todos los vectores en$M_1$están en la misma clase de conjugación (una sola acción elemental de tipo 2 lo hará) y todos los vectores en$M_2$están en la misma clase de conjugación (componer la conjugación por 2 matrices elementales de tipo 2 lo hará).

Entonces$S_n$actúa transitivamente sobre$M_1$y transitivamente en$M_2$, es decir
$\frac{1}{\vert S_n\vert}\sum_{g\in S_n}T_g\mathbf M = \mathbf M \big(\frac{1}{\vert S_n\vert}\sum_{g\in S_n}U_g\big)=\begin{bmatrix}C_n & \mathbf 0 \\ \mathbf 0 & B_{n^2-n \times n^2-n} \end{bmatrix}$
es decir, una matriz diagonal de bloques con 2 bloques en la diagonal, cada uno de los cuales es una matriz positiva. La teoría de Perron-Frobenius nos dice que el RHS tiene exactamente 2 vectores de Perron ortonormales, uno para cada clase comunicante, y dado que el RHS es una combinación convexa de matrices doblemente estocásticas, sabemos que el RHS es doblemente estocástico. Por eso$C_n\mathbf 1_n = 1 \cdot \mathbf 1_n$y$B_{n^2-n \times n^2-n}\mathbf 1_{n^2-n}=1 \cdot \mathbf 1_{n^2-n}$.

Haciendo uso del operador vec y los productos de Kronecker, podemos cerrar concretamente explotando la identidad
$\text{vec}\big({ABC}\big) = \big( C^T \otimes A\big)\text{vec}\big( {B}\big)$. Es decir, aplicando el operador vec a cada$X\in M$y colocándolos en el mismo orden que antes, llamando a esta nueva base$\mathbf M'$, tenemos

$T_g\mathbf M =\mathbf M U_g\iff \big(P_g \otimes P_g\big)\mathbf M' =\mathbf M' U_g$
dónde$U_g$es la misma matriz de permutación que antes. Entonces, sumando el grupo y haciendo uso del hecho de que$\mathbf M'$es una matriz invertible tenemos
$(\mathbf M')^{-1}\big(\frac{1}{\vert S_n\vert}\sum_{g\in S_n}\big(P_g \otimes P_g\big)\Big)\mathbf M' = \big(\frac{1}{\vert S_n\vert}\sum_{g\in S_n}U_g\Big)=\begin{bmatrix}C_n & \mathbf 0 \\ \mathbf 0 & B_{n^2-n \times n^2-n} \end{bmatrix}$

Así la matriz$Z$es similar a (es decir, la RHS) tiene exactamente 2 valores propios iguales a$1$, por eso$Z$tiene dos valores propios iguales a$1$y todo lo demás es cero ya que es idempotente.
$\implies \text{trace}\big(Z\big)=2$
lo que completa la prueba de la segunda afirmación.

Nota: la prueba de la primera afirmación imita esto pero es mucho más fácil. solo considera
$Z':= \Big(\frac{1}{\vert S_n\vert}\sum_{g\in S_n}P_g\Big)$
y
(i) mostrar que es idempotente
(ii) mostrar$Z$es una matriz positiva, y siendo doblemente estocástica eso significa exactamente una raíz de Perron$= 1$. No es necesario, pero si lo desea, puede considerar la forma.$S_n$actúa sobre el conjunto de$n$vectores de base estándar y muestran una órbita.

Usando clases combinatorias tenemos la siguiente clase$\mathcal{P}$de permutaciones con puntos fijos marcados:

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{P} = \textsc{SET}( \mathcal{U} \times \textsc{CYC}_{=1}(\mathcal{Z}) + \textsc{CYC}_{=2}(\mathcal{Z}) + \textsc{CYC}_{=3}(\mathcal{Z}) + \cdots).$$

Esto le da al EGF

$$G(z, u) = \exp\left(uz+\frac{z^2}{2} + \frac{z^3}{3} + \frac{z^4}{4} + \cdots \right) \\ = \exp\left(\log\frac{1}{1-z} + (u-1)z\right) = \frac{1}{1-z} \exp\left((u-1)z\right) \\ = \frac{1}{1-z} \exp\left(-z\right) \exp\left(uz\right).$$

Se sigue que para$n\ge 1$la expectativa para el número de puntos fijos es

$$\mathrm{E}[X] = \left. [z^n] \frac{\partial}{\partial u} G(z,u) \right|_{u=1} \\ = [z^n] \frac{1}{1-z} \exp(-z) \exp(z) z = [z^n] \frac{z}{1-z} = 1.$$

también nos llevamos con$n\ge 2$

$$\mathrm{E}[X(X-1)] = \left. [z^n] \left(\frac{\partial}{\partial u}\right)^2 G(z,u) \right|_{u=1} \\ = [z^n] \frac{1}{1-z} \exp(-z) \exp(z) z^2 = [z^n] \frac{z^2}{1-z} = 1.$$

Concluimos así que con$n\ge 2$

$$\mathrm{E}[X^2] = 2.$$

Deja entonces$f(\sigma)$sea ​​el número de puntos fijos de cualquier permutación en$S_n$. Para cualquier$i \in\{1,2,\dots,n\}$escribir$\delta_{i,\sigma}=1$si$\sigma(i)=i$,$0$de lo contrario. Entonces

$$\sum_\sigma f(\sigma) = \sum_\sigma\sum_i \delta_{i,\sigma} = \sum_i\sum_\sigma \delta_{i,\sigma} = \sum_i (n-1)! =n(n-1)!=n!$$ para el número de permutaciones con$\sigma(i)=i$es simplemente el número de permutaciones de la$n-1$elementos restantes. Ahora $$\sum_\sigma (f(\sigma))^2 = \sum_\sigma\big(\sum_i \delta_{i,\sigma}\big)^2 = \sum_\sigma \big(\sum_i \delta_{i,\sigma}\big)\big(\sum_j \delta_{j,\sigma}\big)\,.$$ Tenga en cuenta que$\delta_{i,\sigma}\delta_{i,\sigma}=\delta_{i,\sigma}$, entonces $$\sum_\sigma (f(\sigma))^2 = \sum_\sigma\sum_i \delta_{i,\sigma} + \sum_\sigma \big(\sum_{i\ne j} \delta_{i,\sigma} \delta_{j,\sigma}\big) = n! + \sum_{i\ne j} \big(\sum_\sigma \delta_{i,\sigma} \delta_{j,\sigma}\big)\,.$$ Como antes, una permutación que corrige ambos$i$y$j$es solo una permutación del resto, contando$(n-2)!$. y el numero de parejas$(i,j)$con$i\ne j$Es claramente$n(n-1)$, entonces $$\sum_\sigma (f(\sigma))^2 = n! + \sum_{i\ne j}(n-2)! = n! + n(n-1)(n-2)! = 2\,n!\,.$$

Resumiendo, el promedio de$f(\sigma)$es 1, y el promedio de$(f(\sigma))^2$es 2