Suma de las trazas de todas las permutaciones de una matriz

Question

Tengo un problema que se reduce a encontrar la suma de las trazas de todas las posibles permutaciones de filas de una matriz grande. Por ejemplo, si tuviéramos una matriz de 3x3, las posibles ordenaciones de filas serían (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1), donde los números representan los números originales de las filas. Quiero encontrar la suma de las filas sobre todos los posibles ordenamientos.

Podría calcularlos todos pero eso escalaría a N!, lo que es demasiado caro computacionalmente. ¿Hay alguna forma de simplificar el problema? ¿O de aproximar la respuesta sin realizar cada cálculo?

Algunas informaciones adicionales

La matriz representa las probabilidades de manera que todas las filas y columnas suman 1. Y sé que la traza de la matriz original es el término más grande de la suma. (Si algo de eso ayuda). Además, lo que en realidad estoy tratando de hacer es maximizar la suma con respecto a un parámetro, lambda, que se utiliza en una función para calcular los elementos de la matriz. Así que si quieres transformar la suma utilizando una función creciente y maximizar/calcular eso en su lugar, entonces eso también funcionaría.

Answer 1

En primer lugar, afirmo que la suma de todo el orden $n$ matrices de permutaciones es igual a la matriz cuyas entradas son todas iguales a $(n-1)!$ . Esto se debe a que para cada $1\le i \le n$ y $1\le j\le n$ el número de permutaciones para las que $\pi(i)=j$ es $(n-1)!$ .

Otra forma de escribir esta matriz constante es $(n-1)!\def\1{{\bf1}}\1\1^T$ , donde $\1$ es un vector columna de todos los unos.

Por lo tanto, dejar que $B$ sea cualquier $n\times n$ matriz, y $A_\pi$ sea la matriz de permutaciones correspondiente a $\pi$ entonces \begin{align} \sum_{\pi\in S_n}\mathrm{tr}(A_\pi B) &=\mathrm{tr}\left(\left(\sum_{\pi}A_\pi\right)B\right) \\&=\mathrm{tr}\big((n-1)!\1\1^TB\big) \\&=(n-1)!\mathrm{tr}(\1^TB\1) \end{align} La última igualdad es la propiedad cíclica de la traza. Finalmente, $\mathrm{tr}(\1^TB\1)$ es la suma de las entradas de $B$ . Por tanto, la suma de las trazas de las permutaciones de una matriz es igual a $(n-1)!$ veces la suma de las entradas de esa matriz.