Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
perms and determinant

Subject: perms and determinant

From: Greg von Winckel

Date: 18 Mar, 2011 10:26:04

Message: 1 of 8

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?

Subject: perms and determinant

From: Bruno Luong

Date: 18 Mar, 2011 10:47:04

Message: 2 of 8

"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

Subject: perms and determinant

From: Greg von Winckel

Date: 18 Mar, 2011 11:35:06

Message: 3 of 8

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

Subject: perms and determinant

From: Torsten

Date: 18 Mar, 2011 11:39:03

Message: 4 of 8

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.

Subject: perms and determinant

From: Bruno Luong

Date: 18 Mar, 2011 11:54:05

Message: 5 of 8

"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

Subject: perms and determinant

From: Bruno Luong

Date: 18 Mar, 2011 12:13:05

Message: 6 of 8

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

Subject: perms and determinant

From: Roger Stafford

Date: 18 Mar, 2011 23:09:04

Message: 7 of 8

"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

Subject: perms and determinant

From: Derek O'Connor

Date: 20 Mar, 2011 14:13:04

Message: 8 of 8

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

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us