Perm sign

perm_sign
Computes the sign of a permutation
Other toolboxes required	none
Related functions	perm_inv
Function category	Helper functions

perm_sign is a function that computes the sign of a permutation. The output of the function is either 1, indicating the permutation is even, or -1, indicating the permutation is odd.

Syntax

• SGN = perm_sign(PERM)

Argument descriptions

• PERM: A vector containing a permutation of the integers 1, 2, ..., n.

Examples

Small examples

The identity permutation is even:

>> perm_sign(1:4)
 
ans =
 
     1

The permutation that transposes 3 and 4 is odd:

>> perm_sign([1,2,4,3,5])
 
ans =
 
    -1

A large example

This function has no trouble with large permutations. The following code determines the sign of a random permutation of 1:1000000 in under 1/2 of a second on a standard desktop computer:

>> perm_sign(randperm(1000000))
 
ans =
 
     1

Source code

Click on "expand" to the right to view the MATLAB source code for this function.

1. %%  PERM_SIGN    Computes the sign of a permutation

2. %   This function has one required argument:

3. %     PERM: a permutation vector

4. %

5. %   SGN = perm_sign(PERM) is the sign (either -1 or 1) of the permutation

6. %   PERM. In other words, SGN = (-1)^INV, where INV is the number of

7. %   inversions contained in PERM.

8. %

9. %   URL: http://www.qetlab.com/perm_sign

11. %   requires: nothing

12. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)

13. %   package: QETLAB

14. %   last updated: November 21, 2012

16. function sgn = perm_sign(perm)

18. Id = speye(length(perm));

20. % At first glance, the following looks like it should be slow (something

21. % like O(n^3)). However, MATLAB is able to exploit the extreme sparsity of

22. % Id(:,perm) to make this computation more like O(n).

23. sgn = det(Id(:,perm));