MATLAB Answers

How to calculate permutation powers

13 views (last 30 days)
lilly lord
lilly lord on 31 Jul 2021
Commented: lilly lord on 2 Aug 2021
I have to find higher powers of a permutation. For example if M is a given permutation , then to calculate M^11
M= [ 1 2 3 4 5 6 7 8 9 10; 3 6 8 1 2 4 5 7 10 9]
M^11 the answer should be [1:10;7 1 5 8 4 3 62 10 9];
The code below works well for small permutation but for large permutation and higher power gives error. If any one can help . Thanks in advance
inMat: The input permutation matrix
% n: The number of permutations
% M=[1 2 3 4 5 6; 3 4 1 5 6 2];
Temp=inMat;
Temp1=inMat;
rc=size(Temp);
outMat(1,:)=Temp(1,:);
for j=1:n
for i=1:rc(2)
r=Temp(:,i);
outMat(2,i)=Temp1(2,r(2));
end
Temp1=outMat;
end
  2 Comments
Image Analyst
Image Analyst on 1 Aug 2021
I agree with dpb (above). No idea how you came up with that answer, or what a "power" of a permutation is. All I know is that M is a matrix, not a permutation.
% M is a matrix, not a permutation of anything that we know of so far.
M = [1 2 3 4 5 6 7 8 9 10; 3 6 8 1 2 4 5 7 10 9]
% With the above M, the bottom row is a permutation of the top row.
% So actually each row is a permutation of the other row.
% Make a new matrix that is a permutation of M:
randomIndexes = randperm(numel(M))
M2 = reshape(M(randomIndexes), size(M))
You can see in the last line I made a permutation of your matrix M using randperm(). But I still have no idea what you mean by the "power" of it. Do you just want to raise it to the 11th power, like
M2 = M2 .^ 11;
????

Sign in to comment.

Accepted Answer

Bruno Luong
Bruno Luong on 1 Aug 2021
M= [ 1 2 3 4 5 6 7 8 9 10; 3 6 8 1 2 4 5 7 10 9]
M = 2×10
1 2 3 4 5 6 7 8 9 10 3 6 8 1 2 4 5 7 10 9
S=sparse(M(2,:),M(1,:),1);
[p11,~]=find(S^11);
M11= [M(1,:);p11']
M11 = 2×10
1 2 3 4 5 6 7 8 9 10 7 1 5 8 4 3 6 2 10 9
  3 Comments
lilly lord
lilly lord on 2 Aug 2021
Your answer solved my problem . Thank u . for powers of disjoint cycles i will ask as another question

Sign in to comment.

More Answers (1)

David Goodmanson
David Goodmanson on 2 Aug 2021
Edited: David Goodmanson on 2 Aug 2021
Hi lilly,
Since the 1:n in the first row is just along for the ride, you don't have to carry it along in the calculation; you can just append it at the end. For the 11th power you have to use n=10 multplciations so it might be less confusing to redifine nnew = n+1 and use nnew-1 multiplications. Anyway, the inner do loop is equivalent to the following iterative mapping process:
n = 10;
inMat = [1:10;
3 6 8 1 2 4 5 7 10 9]
Temp=inMat;
Temp1=inMat;
rc=size(Temp);
outMat(1,:)=Temp(1,:);
for j=1:n
for i=1:rc(2)
r=Temp(:,i)
outMat(2,i)=Temp1(2,r(2));
end
Temp1=outMat;
end
outMat
% alterative
p0 = inMat(2,:);
p = p0;
for j = 1:n
p = p0(p);
end
outMat2 = [1:10; p]

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!