is there a name for this function (parity of a finite sequence)?

Question

Variants of this question have been crossposted to Stack Overflow and Computational Science Stack Exchange. Additional answers may be found at these other sites.

Math people:

In an attempt to solve a larger problem, I defined a function $\sigma$ as follows: if $(x_1, x_2, \ldots, x_n)$ is a finite sequence of distinct real numbers, then $\sigma(x_1, x_2, \ldots, x_n) = 1$ if $(x_1, x_2, \ldots, x_n)$ is an even permutation of an increasing sequence, and $\sigma(x_1, x_2, \ldots, x_n) = -1$ if $(x_1, x_2, \ldots, x_n)$ is an odd permutation of an increasing sequence. Does this function have a name? I Googled "parity of a finite sequence" and found nothing. I found plenty on the parity of a permutation, but $(x_1, x_2, \ldots, x_n)$ is not a permutation. Note that $n$ can be any positive integer. The function is defined, and I need to define it, only for finite sequences of distinct real numbers.

An example of an increasing sequence is $(1, 2, 4, 7, 10)$. The numbers $x_1, \ldots, x_n$ are distinct, so there is exactly one increasing sequence you can form using all of them exactly once.

Here is an example: $(2.3, 4.7, 9.9, 10, 13)$ is an increasing sequence of real numbers. $(4.7, 2.3, 10, 9.9, 13)$ is an even permutation of that sequence. So $\sigma(4.7, 2.3, 10, 9.9, 13) = 1$. Got it?

Regardless of whether this function has a standard name, does anyone know if there is a function built-in to Matlab or Maple to compute it?

UPDATE: I got some help at Stack Overflow. If I enter

A = [2 7 4 10]

then

[i a] =sort(A)

then

a

at the Matlab command prompt, the value of $a$ is $[1\ 3\ 2\ 4]$.

The sign of the permutation vector $a$ can be computed in Matlab in two lines using only two additional commands:

J=eye(length(a));

sign =det(J(:,a)))

Stefan (STack Exchange FAN)

Answer 1

Assume your numbers are in order: $x_1<x_2<\ldots<x_n$. Shuffling the t-uple $(x_1,x_2,\ldots,x_n)$ amounts to permuting the indices by a uniquely determined $\sigma\in S_n$: $(x_{\sigma(1)},x_{\sigma(2)},\ldots,x_{\sigma(n)})$.

We call inversion of $(x_{\sigma(1)},x_{\sigma(2)},\ldots,x_{\sigma(n)})$ the number of pairs $(i,j)$ such that $i<j$ and $x_{\sigma(i)}>x_{\sigma(j)}$. Note that the latter is equivalent to $\sigma(i)>\sigma(j)$. The number of inversions in such a t-uple is called its inversion number. And we have $$ \mbox{inversion number}(x_{\sigma(1)},x_{\sigma(2)},\ldots,x_{\sigma(n)})=\mbox{inversion number}(\sigma(1),\sigma(2),\ldots,\sigma(n)). $$

Fact: for every permutation $\sigma$, the inversion number of $(\sigma(1),\sigma(2),\ldots,\sigma(n))$ has the same parity has every set of transpositions $S$ such that $\sigma=\prod_{\tau\in S}\tau$. The signature of $\sigma$ is defined to be $-1$ if the latter is odd, $+1$ if it is even.

Conclusion: your function $\sigma(x_{\sigma(1)},x_{\sigma(2)},\ldots,x_{\sigma(n)})$ corresponds to the signature $\epsilon (\sigma)$ of the permutation $\sigma$. Therefore $$ \sigma(x_{\sigma(1)},x_{\sigma(2)},\ldots,x_{\sigma(n)})=\epsilon(\sigma)=(-1)^{\mbox{inversion number}(x_{\sigma(1)},x_{\sigma(2)},\ldots,x_{\sigma(n)})}. $$

Proof of the fact: you can find it here. See in particular proof 2.

Matlab/Maple: I don't know if this is already implemented. But if your sequences are not insanely long, I think both will compute easily $$ \sigma(x_{\sigma(1)},x_{\sigma(2)},\ldots,x_{\sigma(n)})=\frac{\prod_{i<j}x_{\sigma(i)}-x_{\sigma(j)}}{\prod_{i<j} x_i-x_j}. $$ Note that it is not even necessary to compute the denominator. The sign of the numerator suffices.

Answer 2

If you have a function or notation for the $N$th largest element of a list $L$, this is the parity of the permutation that takes $N$th[$L$] to $L[N]$ for all $N$.

Answer 3

The map that sends a sequence $(x_1,\ldots,x_n)$ to the permutation $(\pi_1,\ldots,\pi_n)$ such that $$ \pi_i<\pi_j \iff x_i<x_j \text{ or } (x_i=x_j \text{ and } i<j) \qquad\text{ for all $i,j$} $$ is often called standardisation (since your sequences have no repetition, you don't need the second part of the specification). What you compute would then be the sign(ature) of the standardisation of your sequence.

I should add the this use of "standardisation" is neither very old nor widespread, and is mainly used in relation to the combinatorics of tableaux, where it corresponds to the relation between semi-standard and standard tableaux.