1
$\begingroup$

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

Computational Science People:

I originally posed this as part of a question at https://math.stackexchange.com/questions/379809/is-there-a-name-for-this-function-parity-of-a-finite-sequence . The title pretty much says it all. Given a finite sequence of real numbers which I know are distinct, I want an easy way to compute whether it is an even permutation of an increasing sequence or an odd permutation of an increasing sequence. For example, $(5, 1.3, 8, 6, 10.5)$ is an even permutation of the increasing sequence $(1.3, 5, 6, 8, 10)$, so the answer is "even". $(2, 3, 5, 1)$ is an odd permutation of the increasing sequence $(1, 2, 3, 5)$, so the answer is "odd". I can get Matlab to give me a permutation vector, which for my first example would be $[2\ 1\ 4\ 3\ 5]$, but I cannot find a built-in function in Matlab to compute the sign of that permutation vector. If I could get Matlab to give me the permutation matrix, I could take the determinant of that matrix. People have posted quite long Matlab files on the Web to accomplish this, but I'm hoping I can avoid that. I would also be willing to use Maple.

Please no nitpicking or unconstructive comments, which are very common at Math Stack Exchange. I have less experience here, but I'm hoping people are more polite here.

Stefan (STack Exchange FAN)

Improve this question
$\endgroup$
3
$\begingroup$

Suppose you have a permutation vector permVec. Then a permutation matrix should be calculated as follows (modulo some MATLAB syntax bugs, since it's been a while):

permMat = function permVecToMat(permVec)
    n = length(permVec);
    permMat = zeros(n,n);
    for i = 1:n
        permMat(i, permVec(i)) = 1
    end
end

Then you just take the determinant, and you're done. Consider the code BSD-licensed, even though the Stack Exchange license is CC-BY-SA 3.0 (and I loathe it).

An alternate way of calculating the sign of a permutation would be to convert it into a product of transpositions. If the number of transpositions in such a decomposition is even, the permutation is even; otherwise, the permutation is odd. However, I don't know an algorithm for decomposing a permutation into a product of transpositions.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Thank you. Someone at Math Stack Exchange posted the product of transpositions formula. Whether I use that formula or your code, the Matlab code will be much shorter than the files I saw posted on the Web for this purpose. I'm not familiar with BSD-licensed code or the Stack Exchange license, and I don't understand how someone would be able to license such a tiny block of code. $\endgroup$ – Stefan Smith May 3 '13 at 12:54
  • $\begingroup$ People at StackOverflow found two shorter solutions: I = speye(length(a)); sign = det(I(:,a)); and y = eye(numel(x)); evenodd = det( y(:,x) ); $\endgroup$ – Stefan Smith May 3 '13 at 13:16
  • $\begingroup$ @Stefan: Cross-posting is highly frowned upon on the Stack Exchange sites; as a result, this question will be closed. Please don't do this. $\endgroup$ – Geoff Oxberry May 3 '13 at 15:44
  • 1
    $\begingroup$ @Stefan: Posting a question you've asked somewhere else, and for which you have an answer, is considered bad forum etiquette (see the site FAQ). The justification as to why it's bad etiquette is that people feel they've wasted their time if you've posted the question somewhere else and gotten answers. Had I known you already knew how to calculate the sign of a permutation vector efficiently, I wouldn't have bothered to take the time to write my answer. $\endgroup$ – Geoff Oxberry May 3 '13 at 18:25
  • 2
    $\begingroup$ @Stefan: The system does not allow me to use "duplicate" as a reason for closing cross-posted questions (because it assumes the duplicate is on the same site). If you didn't post the same question on Stack Overflow, then I misunderstood your comment, and I will reopen the question. $\endgroup$ – Geoff Oxberry May 3 '13 at 20:58

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