Show that two ways to sum the entries of an $n\times n$ array yield the same

Question

Let $A = (a_{ij})$ be a matrix. I am looking for an algebraic proof that $$ \sum_{\sigma, \tau \in S_k} \mbox{sgn}(\sigma\circ\tau) a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{n\sigma(n)}a_{1\tau(1)}a_{2\tau(2)}\cdots a_{n\tau(n)} $$ equals $$ \sum_{\sigma \in S_n} \mbox{sgn}(\sigma) \sum_{k_1,k_2,\ldots,k_n=1}^n a_{1k_1}a_{2k_2}\cdots a_{nk_n}a_{\sigma(1)k_1} a_{\sigma(2)k_2} \cdots a_{\sigma(n)k_n} $$ Do you know how to prove this? For $n = 2$ we have $$ a_{11}a_{22}a_{11}a_{22} - a_{11}a_{22}a_{12}a_{21} - a_{12}a_{21}a_{11}a_{22} + a_{12}a_{21}a_{12}a_{21} $$ and $$ a_{11}a_{21}a_{11}a_{21} + a_{11}a_{22}a_{11}a_{22} + a_{12}a_{21}a_{12}a_{21} + a_{12}a_{22}a_{12}a_{22} -(a_{11}a_{21}a_{21}a_{11} + a_{11}a_{22}a_{21}a_{12} + a_{12}a_{21}a_{22}a_{11} + a_{12}a_{22}a_{22}a_{12}) $$ for both sides, which is equal.

Answer 1

In your second sum, you can restrict yourself to the case that all the $k_i$ have pairwise different values. If e.g. $k_1 = k_2$, this summand cancels out with the corresponding summand where $\sigma$ is replaced with the permutation $(12) \sigma$.

But this means that your second sum simplifies to the following: $$\sum \limits_{\sigma \in S_n} \sum \limits_{k \in S_n} \operatorname{sgn}(\sigma)a_{1, k(1)}\cdots a_{n, k(n)} \cdot a_{\sigma(1), k(1)}\ldots a_{\sigma(n), k(n)} \\ = \sum \limits_{k \in S_n} \sum \limits_{\sigma \in S_n} \operatorname{sgn}(\sigma)a_{1, k(1)}\cdots a_{n, k(n)} \cdot a_{1, k(\sigma^{-1}(1))}\ldots a_{n, k(\sigma^{-1}(n))}$$

Now observe that for any fixed permutation $k \in S_n$ the map $\sigma \mapsto \sigma^{-1} \circ k$ is a bijection from $S_n$ onto itself, i.e. you can replace $\sigma$ with $\sigma^{-1} \circ k$. Together with $\operatorname{sgn}(\sigma) = \operatorname{sgn}(\sigma^{-1})$ this yields the result.