CODEWITHSUNDEEP
algorithmmatlabmatrixpermutationcombinatorics
Kinin
Kinin

Reputation: 55

Matlab: Finding the permutation matrices that produce another matrix

I'm trying to write MATLAB code that will allow me to find the permutation matrices of a matrix.

Let's consider the example below. I'm given the matrices A and B:

A = [1 2 3;4 5 6; 7 8 9]   % is a given matrix
B = [9 7 8;3 1 2; 6 4 5]   % is a permuted version of A.

My goal is to find the matrices L (that pre-multiply A) and R (that post-multiply A) such that L*A*R = B:

% L is an n by n (3 by 3) that re-order the rows a matrix when it pre-multiply that matrix
L = [0 0 1;1 0 0;0 1 0] 

% R is an n by n that re-order the columns of a matrix
R = [0 1 0;0 0 1;1 0 0] 

B = L*A*R

How to find L and R when I know A and B?

Upvotes: 4

Views: 569

Answers (1)

Amro
Amro

Reputation: 124563

To give a baseline solution, here is the brute-force method:

function [L,R] = find_perms(A,B)
    [n,n] = size(A);
    p = perms(1:n);
    I = eye(n);
    for i=1:size(p,1)
        for j=1:size(p,1)
            L = I(p(i,:),:);
            R = I(:,p(j,:));
            if isequal(L*A*R, B)
                return;
            end
        end
    end
    % none found
    L = [];
    R = [];
end

Let's test it:

A = [1 2 3; 4 5 6; 7 8 9];
B = [9 7 8; 3 1 2; 6 4 5];
[L,R] = find_perms(A,B);
assert(isequal(L*A*R, B));

The left/right permutation matrices are as expected:

>> L
L =
     0     0     1
     1     0     0
     0     1     0
>> R
R =
     0     1     0
     0     0     1
     1     0     0

Upvotes: 4

Related Questions