0
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$
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.

$\endgroup$
10
  • $\begingroup$ Thanks for your answer! Both methods are very elegant! $\endgroup$
    – Laplacian
    Apr 6, 2023 at 7:15
  • $\begingroup$ @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 $\endgroup$ Apr 6, 2023 at 8:25
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 6, 2023 at 8:36
  • $\begingroup$ @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. $\endgroup$ Apr 6, 2023 at 8:55
  • $\begingroup$ @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! $\endgroup$
    – Roman
    Apr 6, 2023 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.