8
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ What do you mean by an increasing sequence? I don't know that your two options exhaust all possibilities, nor do I know if you wanted them to do so. $\endgroup$ – Ian Coley May 3 '13 at 0:44
  • $\begingroup$ An example of an increasing sequence is $(1, 2, 4, 7, 10)$. $\endgroup$ – Stefan Smith May 3 '13 at 1:41
  • $\begingroup$ Isn't it just the sign of a permutation? (No idea about matlab). Also, the talk about increasing seems to be unnecessary. Replace each $x_i$ with the rank in the increasing order, and talk about the sign of that... $\endgroup$ – Aryabhata May 3 '13 at 1:49
  • 1
    $\begingroup$ The closest I can think of is the [inversion number](en.wikipedia.org/wiki/Inversion_(discrete_mathematics). $\endgroup$ – Julien May 3 '13 at 1:52
  • 1
    $\begingroup$ But now that I think about it, $(-1)^\mbox{inversion number}$ is your $\sigma$. So I doubt it has a more specfic name than that. That's even how the signature of a permutation is defined in the first place here. $\endgroup$ – Julien May 3 '13 at 1:58
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much. That was very quick. It is getting late, but I will read it tomorrow. If there is a built-in Matlab function for it, it is very hard to find. The Matlab files I saw posted on the Web looked a lot more complicated than your simple formula. $\endgroup$ – Stefan Smith May 3 '13 at 3:09
  • $\begingroup$ Though the product formula you gave is very simple, the inversion number can be computed in 3 lines of code using Matlab. I edited the question to explain how. $\endgroup$ – Stefan Smith May 3 '13 at 13:27
  • 1
    $\begingroup$ @StefanSmith Great. I'm glad you found what you were looking for. $\endgroup$ – Julien May 3 '13 at 13:53
  • $\begingroup$ @StefanSmith If you desire better performance, the sign of a permutation can be computed in $O(n)$ time and storage by simply decomposing into cycles. $\endgroup$ – Erick Wong May 3 '13 at 18:11
  • 1
    $\begingroup$ @StefanSmith The signature of a cycle of legnth $k$ is $(-1)^{k+1}$. To find the disjoint cycles that compose a given permutation, follow the orbit of the first element. Then the orbit of the first element left out. Etc. $\endgroup$ – Julien May 3 '13 at 21:19
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, that is exactly what I asked for. Unfortunately, I already accepted another answer with a lot of helpful information, and that poster (julien) also had many helpful comments. I can only accept one answer, and I think it would be rude to unaccept his. $\endgroup$ – Stefan Smith May 3 '13 at 20:42
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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