Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: perms and determinant
Date: Fri, 18 Mar 2011 23:09:04 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 24
Message-ID: <im0omg$qg4$1@fred.mathworks.com>
References: <ilvbvs$rks$1@ginger.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: www-00-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1300489744 27140 172.30.248.45 (18 Mar 2011 23:09:04 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 18 Mar 2011 23:09:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:716749

"Greg von Winckel" wrote in message <ilvbvs$rks$1@ginger.mathworks.com>...
> I am using the function perms to generate all possible orderings of up to 7 elements, but I need to know the determinant (+1 or -1) for the permutation matrix which would generate the orderings. The determinant should be -1 for an odd number of element swaps and +1 for an even number of element swaps. 
> 
> Is there a quick way to obtain the signs corresponding to the output of perms?
- - - - - - - -
  The following is similar to Torsten's code but avoids the use of 'find' by working with the inverse of a permutation.  For large n that might be an advantage since it's O(n).

  Suppose that p is a row vector permutation.

 n = length(p);
 q = 1:n;
 q(p) = q; % Get the inverse of p
 s = 1;
 for k = 1:n-1
  if p(k) ~= k
   p(q(k)) = p(k); % Equivalent to a transposition between
   q(p(k)) = q(k); % the k-th and p(k)-th elements of p
   s = -s; % Change the sign for each transposition
  end
 end

  As with Torsten's code, the quantity s will be +1 or -1 according as the number of transpositions performed is even or odd, respectively, which is what you want.

Roger Stafford