Thread Subject:

perms and determinant

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?

"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?

Greg, I post a code here that decomposes a permutation in term of swaps
http://www.mathworks.com/matlabcentral/newsreader/view_thread/239871

Hope it helps

Bruno

Thanks, Bruno. I'm a bit confused about what your code is computing.

This is what I'm currently generating:

P=perms(1:n);
d=arrayfun(@(j)det(sparse(P(j,:)',(1:n),ones(n,1),n,n)), 1:factorial(n))';

Obviously, this scales really badly with n, but as I mentioned before n<8 is sufficient for my purposes. It's actually not terribly slow, if wasteful, but I was wondering if I could avoid computing all of those determinants.

cheers,

Greg

> Greg, I post a code here that decomposes a permutation in term of swaps
> http://www.mathworks.com/matlabcentral/newsreader/view_thread/239871
>
> Hope it helps
>
> Bruno

On 18 Mrz., 12:35, "Greg von Winckel" <gre...@gmail.com> wrote:
> Thanks, Bruno. I'm a bit confused about what your code is computing.
>
> This is what I'm currently generating:
>
> P=perms(1:n);
> d=arrayfun(@(j)det(sparse(P(j,:)',(1:n),ones(n,1),n,n)), 1:factorial(n))';
>
> Obviously, this scales really badly with n, but as I mentioned before n<8 is sufficient for my purposes. It's actually not terribly slow, if wasteful, but I was wondering if I could avoid computing all of those determinants.
>
> cheers,
>
> Greg
>
>
>
> > Greg, I post a code here that decomposes a permutation in term of swaps
> >http://www.mathworks.com/matlabcentral/newsreader/view_thread/239871
>
> > Hope it helps
>
> > Bruno- Zitierten Text ausblenden -
>
> - Zitierten Text anzeigen -

http://kom.aau.dk/~borre/matlab/strang/signperm.m

Best wishes
Torsten.

"Greg von Winckel" wrote in message <ilvg1a$7sn$1@ginger.mathworks.com>...
> Thanks, Bruno. I'm a bit confused about what your code is computing.
>
> This is what I'm currently generating:
>
> P=perms(1:n);
> d=arrayfun(@(j)det(sparse(P(j,:)',(1:n),ones(n,1),n,n)), 1:factorial(n))';

It decompose the permutation is swaps;

n = 10;
P = randperm(n)
swapidx = swapfactor(P)

% Check
I=1:n; % identity permutation
for k=1:nswaps
    s = swapidx(k,:);
    I(s([1 2])) = I(s([2 1])); % swap I
end
disp(I)

% Here is the determinant
nswaps = size(swapidx ,1) % number of swaps
detP = (-1).^nswaps

% Bruno

Sorry, I reversed incorrectly some commands:

n = 10;
P = randperm(n)
swapidx = swapfactor(P)
nswaps = size(swapidx ,1)
detP = (-1).^nswaps

I = 1:n; % Identity
% Recosntruction P from I
for k=1:nswaps
    s = swapidx(k,:);
    I(s([1 2])) = I(s([2 1]));
end
disp(I)

% Bruno

"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

The function below also avoids the find() function, which is expensive, especially as n becomes large. For the output of perms it really doesn't matter what you use because n is small.

------------------------------------------------------
function s = SignCycs(p);
% p(1,n) is a permutation of {1,2,...,n}
% One of many definitions: Sign(p) = (-1)^(No. of even-length cycles)
% Complexity : O(n + ncycles) ~ O(n + Hn) ~~ O(n+log(n)) steps.
%
% USE :>> n = 10^8; p = GRPfys(n); s = SignCycs(p);
%
% Derek O'Connor 20 March 2011. derekroconnor@eircom.net
%
n = length(p);
visited = p<0;
           
% Logical array visited(1:n) = false which marks all p(k) not visited.
% Not needed if sign bit of p(k) is used. Messy.

s = 1;
for k = 1:n
     if ~visited(k) % k not visited, start of new cycle
          next = k;
          L = 0;
          while ~visited(next) % Traverse the current cycle k
                L = L+1; % and find its length L
                visited(next) = true;
                next = p(next);
          end
          if rem(L,2) == 0 % If L is even, change sign.
               s = -s;
          end
     end % if ~visited
end % for k
return % SignCycs
-----------------------------------------------------

The only extra memory used is the logical array visited(1,n). This may be eliminated if the sign-bit of p(k) is used to mark each 'node' of p, but the code is messier and error-prone.

With n = 10^6, time to generate p = 0.22 secs, time sign p = 0.13 secs

With n = 10^8, time to generate p = 31 secs, time sign p = 26 secs

Dell Precision 690, Intel 2xQuad-Core E5345 @ 2.33GHz 16GB RAM,
Windows7 64-bit Professional. MATLAB Version 7.6.0.324 (R2008a)


Derek O'Connor