Find variance of quadratic assignment cost over all permutations Given $A=(a_{ij})_{n\times n}$ and $D=(d_{ij})_{n\times n}$ and a permutation $\pi:\{1,\ldots,n\}\rightarrow \{1,\ldots,n\}$, the quadratic assignment cost is
$$\sum_{1\le i,j\le n}a_{ij}d_{\pi(i)\pi(j)} $$
I want to know the expectation and variance of this cost over all permutations (with the same probability $1/n!$).
The expectation is relatively easy:
$$\frac{1}{n!}\sum_{\pi\in \Pi}\sum_{1\le i,j\le n}a_{ij}d_{\pi(i)\pi(j)}=\frac{1}{n!}\sum_{1\le i,j\le n} a_{ij}\sum_{\pi\in \Pi}d_{\pi(i)\pi(j)}=\frac{1}{n}\sum_{1\le i\le n} a_{ii}\sum_{1\le i\le n} d_{ii}+\frac{1}{n(n-1)}\sum_{i\neq j} a_{ij}\sum_{i\neq j} d_{ij}$$
However, I cannot calculate the variance.
I have tried to calculate $\sum_{\pi\in \Pi}(\sum_{1\le i,j\le n}a_{ij}d_{\pi(i)\pi(j)})^2$, which will gives the cross term $a_{ij}d_{\pi(i)\pi(j)}a_{i'j'}d_{\pi(i')\pi(j')}$, and I cannot handle it.
 A: This is not a complete answer. However, I wanted to point out that I find a different result for the expectation.
You can write the cost as: $$\sum_{1\le i,j\le n}\sum_{1\le k,l\le n} a_{i,j}d_{k,l}X_{i,k}X_{j,l}.$$
Where $X_{i,k} = \begin{cases}1 & \text{if $k=\pi (i)$}\\ 0 & \text{otherwise}\end{cases}$
It is clear that
\begin{align}
E\left[X_{i,k}X_{j,l}\right] &= P\left[X_{i,k} = 1 \cap X_{j,l} = 1\right]\\
&=P\left[X_{j,l}=1\mid X_{i,k}=1\right]P\left[X_{i,k}=1\right]\\
&=\begin{cases}
0 & \text{if ($i\neq j$ and $k=l$) or ($i=j$ and $k\neq l$)}\\
\frac1n & \text{if $i=j$ and $k=l$}\\
\frac1{n(n-1)} & \text{if $i\neq j$ and $k\neq l$}
\end{cases}
\end{align}
So the expected cost is \begin{align}
\frac1n\left(\sum_{i=1}^{n}a_{i,i}\right)\left(\sum_{k=1}^{n}d_{k,k}\right) + \frac1{n(n-1)}\left(\sum_{i\neq j}a_{i,j}\right)\left(\sum_{k\neq l}d_{k,l}\right)
\end{align}
Now to compute the variance you need to compute:
$$E\left[X_{i,k}X_{j,l}X_{i',k'}X_{j',l'}\right] = P\left[X_{i,k}=1\cap X_{j,l}=1\cap X_{i', k'}=1\cap X_{j',l'} = 1\right]$$
Try to do the same idea as I did for the expectation.
A: According to Youem's method, $\mathbb{E}_{\pi\in\Pi}(\sum_{ij}a_{ij}d_{\pi(i)\pi(j)})^2$ becomes
$$\sum_{ij}\sum_{kl}\sum_{i'j'}\sum_{k'l'}a_{ij}a_{i'j'}d_{kl}d_{k'l'}\mathbb{E}[X_{ik}X_{jl}X_{i'k'}X_{j'l'}] \\
=\frac{1}{n}\sum_{i=1}^n\sum_{k=1}^n\sum_{i'=1}^n\sum_{k'=1}^n a_{ii}^2d_{kk}^2\\+\frac{1}{n(n-1)}\sum_{i=1}^n\sum_{k=1}^n\sum_{i\neq j'}\sum_{k\neq l'} a_{ii}a_{ij'}d_{kk}d_{kl'}\\
+\frac{1}{n(n-1)}\sum_{i=1}^n\sum_{k=1}^n\sum_{i'\neq i}\sum_{k'\neq k} a_{ii}a_{i'i}d_{kk}d_{k'k}\\
+\frac{1}{n(n-1)}\sum_{i\neq j}\sum_{k\neq l}\sum_{i'=1}^n\sum_{k'=1}^n a_{i'j}a_{i'i'}d_{k'l}d_{k'k'}\\
+\frac{1}{n(n-1)}\sum_{i\neq j}\sum_{k\neq l}\sum_{i'=1}^n\sum_{k'=1}^n a_{ii'}a_{i'i'}d_{kk'}d_{k'k'}\\
+\frac{1}{n(n-1)}\sum_{i=1}^n\sum_{k=1}^n\sum_{i'=1}^n\sum_{k'=1}^n a_{ii}a_{i'i'}d_{kk}d_{k'k'}\\
+\frac{1}{n(n-1)}\sum_{i\neq j}\sum_{k\neq l} a_{ii}a_{jj}d_{kk}d_{ll}\\
+\frac{1}{n(n-1)}\sum_{i\neq j}\sum_{k\neq l} a_{ij}a_{ji}d_{kl}d_{lk}\\
+\frac{1}{n(n-1)(n-2)}\sum_{i=1}^n\sum_{k=1}^n\sum_{i'\neq j'}\sum_{k'\neq l'} a_{ii}d_{kk}a_{i'j'}d_{k'l'}1[i\neq i']1[i\neq j'][k\neq k'][k\neq l']\\
+\frac{1}{n(n-1)(n-2)}\sum_{i\neq j}\sum_{k\neq l}\sum_{i'=1}^n\sum_{k'=1}^n a_{ij}d_{kl}a_{i'i'}d_{k'k'}1[i\neq i']1[j\neq i'][k\neq k'][l\neq k']\\
+\frac{1}{n(n-1)(n-2)}\sum_{i\neq j}\sum_{k\neq l}\sum_{i'\neq j'}\sum_{k'\neq l'}a_{ij}a_{i'j'}d_{kl}d_{k'l'}1[i=i']1[j\neq j']1[k=k']1[l\neq l']\\
+\frac{1}{n(n-1)(n-2)}\sum_{i\neq j}\sum_{k\neq l}\sum_{i'\neq j'}\sum_{k'\neq l'}a_{ij}a_{i'j'}d_{kl}d_{k'l'}1[i=j']1[i'\neq j]1[k=l']1[l'\neq k]\\
+\frac{1}{n(n-1)(n-2)}\sum_{i\neq j}\sum_{k\neq l}\sum_{i'\neq j'}\sum_{k'\neq l'}a_{ij}a_{i'j'}d_{kl}d_{k'l'}1[j=i']1[j'\neq i]1[l=k']1[k'\neq l]\\
+\frac{1}{n(n-1)(n-2)}\sum_{i\neq j}\sum_{k\neq l}\sum_{i'\neq j'}\sum_{k'\neq l'}a_{ij}a_{i'j'}d_{kl}d_{k'l'}1[j=j']1[i\neq i']1[l=l']1[k\neq k']\\
+\frac{1}{n(n-1)(n-2)(n-3)}\sum_{i\neq j}\sum_{k\neq l}\sum_{i'\neq j'}\sum_{k'\neq l'}a_{ij}a_{i'j'}d_{kl}d_{k'l'} 1[i\neq j]1[i\neq i']1[i\neq j']1[j\neq i']1[j\neq j']1[i'\neq j']1[k\neq l]1[k\neq k']1[k\neq l']1[l\neq k']1[l\neq l']1[k'\neq l']\\
$$
At least, it could be computed using a program.
