# Summation over permutation: $\sum_{\sigma \in S_N} \mathrm{sgn}(\sigma) \prod_{i=1}^N x_{i+\sigma(i)}$

Let $$N$$ be a natural number, and $$S_N$$ be the symmetric group over $$\{1, \ldots, N\}$$. I want to compute $$\sum_{\sigma \in S_N} \mathrm{sgn}(\sigma) \prod_{i=1}^N x_{i+\sigma(i)}$$ for small $$N$$ using Mathematica. Here, $$x_2, \ldots, x_{2N}$$ are variables, which one may implement in the form x[i], and $$\mathrm{sgn}(\sigma) = \pm 1$$ if $$\sigma$$ is an odd (resp. even) permutation.

How to implement the sum? After searching other posts in this site, I found Permutations[Range[3]] useful, but I cannot implement $$\prod_{i=1}^N x_{i+\sigma(i)}$$ and summation over the permutation.

f[n_] := Total[Signature[#] Apply[Times, MapIndexed[x[#2[[1]] + #1] &, #]] & /@
Permutations[Range[n]]]

f[1]
(*    x[2]    *)

f[2]
(*    -x[3]^2 + x[2] x[4]    *)

f[3]
(*    -x[4]^3 + 2 x[3] x[4] x[5] - x[2] x[5]^2 - x[3]^2 x[6] + x[2] x[4] x[6]    *)


A much easier calculation would be through the matrix determinant:

g[n_] := Det[Table[x[i + j], {i, n}, {j, n}]]

Table[f[n] == g[n], {n, 9}] // Expand
(*    {True, True, True, True, True, True, True, True, True}    *)


For fun we can write this determinant as

G = Det[x@+##&~Array~{#,#}]&


to save some bits and confuse the reader.

• Thanks for your answer! Both methods are very elegant! Apr 6, 2023 at 7:15
• @eigenvalue The x[i+j] reminded me of Toeplitz matrices (or circulant matrices it was vague in my head) and indeed after some searching, it's connected as it's a Hankel matrix: en.wikipedia.org/wiki/Hankel_matrix. Thus I suppose one could calculate the determinant in O(n^2) time using the Levinson algorithm given here en.wikipedia.org/wiki/Toeplitz_matrix Apr 6, 2023 at 8:25
• I wanted to see if ChatGPT could identify the matrix. It first incorrectly stated it was a Toeplitz matrix. I told it why it was incorrect, and it then said it was a Cauchy matrix and I told it why it's incorrect in general and then it finally said it was a Hankel matrix. I feel that's somewhat telling of how it operates. I assume it did not read a lot about Hankel matrices and so It picked out a more common element in a semantic cluster of similar-looking concepts. That feels similar to how people remember by association and tend to remember the stuff we saw more often. Apr 6, 2023 at 8:36
• @eigenvalue just to clarify, when I said one could use the Levinson algorithm, I meant on the Toepliz factor after using the decomposition in the Hankel Wikipedia page. Perhaps there is a modification of the Levinson algorithm that would allow implementing it directly on the Hankel matrix. Apr 6, 2023 at 8:55
• @userrandrand yes I was looking up all the Toeplitz- and Hankel-matrix pages but could not find a match for this problem, and so I left it as an explicit Table. Getting the Levinson algorithm set up for this determinant could be an interesting problem for the math stackexchange! Apr 6, 2023 at 9:53