Got Questions? Get Answers.
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:
finding permutation matrices using eig()

Subject: finding permutation matrices using eig()

From: Leslie Watkins

Date: 23 Apr, 2010 05:53:05

Message: 1 of 14

I have two matrices A and B:
A = [0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 1; 1 0 1 0 0; 0 0 1 0 0]
B = [0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 1; 1 0 1 0 1; 0 0 1 1 0]
There exists a permutation matrix P such that P*A*P' = B.
(P = [0 0 1 0 0; 0 0 0 1 0; 1 0 0 0 0; 0 0 0 0 1; 0 1 0 0 0])
I know P because this is a contrived data set, but I want to find P independently using MATLAB. Here's what I tried:

[VA DA] = eig(A);
[VB DB] = eig(B);
"P" = VB*VA'

In theory,
P should be VB*VA'

But it doesn't work!

Here's what I get:

QA =
   -0.0000 -0.7702 0.3069 -0.0000 0.5590
   -0.3717 0.4294 0.4390 0.6015 0.3505
   -0.6015 0.1378 -0.5100 -0.3717 0.4700
    0.3717 0.4294 0.4390 -0.6015 0.3505
    0.6015 0.1378 -0.5100 0.3717 0.4700

QB =
    0.6015 0.1378 0.5100 -0.3717 0.4700
   -0.3717 0.4294 -0.4390 -0.6015 0.3505
   -0.0000 -0.7702 -0.3069 0.0000 0.5590
   -0.6015 0.1378 0.5100 0.3717 0.4700
    0.3717 0.4294 -0.4390 0.6015 0.3505

"P" =
    0.3131 0.0006 -0.2439 0.8951 0.2033
   -0.2695 -0.1091 0.8951 0.3381 0.0006
    0.8116 -0.2695 0.3131 -0.2695 0.3131
    0.3131 0.8951 0.2033 0.0006 -0.2439
   -0.2695 0.3381 0.0006 -0.1091 0.8951

The weird thing is, P*QA should be QB, but when I use the correct value for P, I get:
P*QA=
   -0.6015 0.1378 -0.5100 -0.3717 0.4700
    0.3717 0.4294 0.4390 -0.6015 0.3505
   -0.0000 -0.7702 0.3069 -0.0000 0.5590
    0.6015 0.1378 -0.5100 0.3717 0.4700
   -0.3717 0.4294 0.4390 0.6015 0.3505

The values are the same as QB, but the signs are different, and they're not consistent across the columns. So why am I getting different eigenvectors for A and B? They should be the same, just arranged in a different order. Thank you in advance for any help.

Subject: finding permutation matrices using eig()

From: Bruno Luong

Date: 23 Apr, 2010 06:14:07

Message: 2 of 14

"Leslie Watkins" <Theantipoke@gmail.com> wrote in message <hqrck0$pl8$1@fred.mathworks.com>...
> I have two matrices A and B:
> A = [0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 1; 1 0 1 0 0; 0 0 1 0 0]
> B = [0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 1; 1 0 1 0 1; 0 0 1 1 0]
> There exists a permutation matrix P such that P*A*P' = B.
> (P = [0 0 1 0 0; 0 0 0 1 0; 1 0 0 0 0; 0 0 0 0 1; 0 1 0 0 0])
 

Stop right there, it's not correct.

When we multiply (left or right) by a permutation matrix, the elements only change places. In particular the number "1s" should remain identical.

But B has 2 more 1s than A (14 vs 12), so B can not be permutation of A as you have stated.

The statement is wrong not only for the P you provide but any permutation matrix P.

Bruno

Subject: finding permutation matrices using eig()

From: Leslie Watkins

Date: 23 Apr, 2010 06:48:05

Message: 3 of 14

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hqrdrf$feq$1@fred.mathworks.com>...
> "Leslie Watkins" <Theantipoke@gmail.com> wrote in message <hqrck0$pl8$1@fred.mathworks.com>...
> > I have two matrices A and B:
> > A = [0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 1; 1 0 1 0 0; 0 0 1 0 0]
> > B = [0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 1; 1 0 1 0 1; 0 0 1 1 0]
> > There exists a permutation matrix P such that P*A*P' = B.
> > (P = [0 0 1 0 0; 0 0 0 1 0; 1 0 0 0 0; 0 0 0 0 1; 0 1 0 0 0])
>
>
> Stop right there, it's not correct.
>
> When we multiply (left or right) by a permutation matrix, the elements only change places. In particular the number "1s" should remain identical.
>
> But B has 2 more 1s than A (14 vs 12), so B can not be permutation of A as you have stated.
>
> The statement is wrong not only for the P you provide but any permutation matrix P.
>
> Bruno

Thanks for catching that! Unfortunately it doesn't solve my problem. The A I used in my calculations is:
A = [0 1 1 1 1; 1 0 0 0 1; 1 0 0 1 1; 1 0 1 0 0; 1 1 1 0 0]
The one I gave in my first post was just a typo. Sorry for the confusion!

Subject: finding permutation matrices using eig()

From: Yi Cao

Date: 23 Apr, 2010 07:49:05

Message: 4 of 14

"Leslie Watkins" <Theantipoke@gmail.com> wrote in message <hqrfr5$gc5$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hqrdrf$feq$1@fred.mathworks.com>...
> > "Leslie Watkins" <Theantipoke@gmail.com> wrote in message <hqrck0$pl8$1@fred.mathworks.com>...
> > > I have two matrices A and B:
> > > A = [0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 1; 1 0 1 0 0; 0 0 1 0 0]
> > > B = [0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 1; 1 0 1 0 1; 0 0 1 1 0]
> > > There exists a permutation matrix P such that P*A*P' = B.
> > > (P = [0 0 1 0 0; 0 0 0 1 0; 1 0 0 0 0; 0 0 0 0 1; 0 1 0 0 0])
> >
> >
> > Stop right there, it's not correct.
> >
> > When we multiply (left or right) by a permutation matrix, the elements only change places. In particular the number "1s" should remain identical.
> >
> > But B has 2 more 1s than A (14 vs 12), so B can not be permutation of A as you have stated.
> >
> > The statement is wrong not only for the P you provide but any permutation matrix P.
> >
> > Bruno
>
> Thanks for catching that! Unfortunately it doesn't solve my problem. The A I used in my calculations is:
> A = [0 1 1 1 1; 1 0 0 0 1; 1 0 0 1 1; 1 0 1 0 0; 1 1 1 0 0]
> The one I gave in my first post was just a typo. Sorry for the confusion!

This is a special case of the Sylvester equation, XA-BX=C. In your case, X = P and C=0. The condition for a Sylvester equation to have a unique solution is that A and B have no common eigenvalues. Clearly, this condition is not satisfied here because A nad B have exactly the same eigenvalues. Therefore, the solution is non-unique!

To get the permutation matrix, you need another equation, PP' = I.

HTH
Yi

Subject: finding permutation matrices using eig()

From: Bruno Luong

Date: 23 Apr, 2010 08:24:05

Message: 5 of 14

"Yi Cao" <y.cao@cranfield.ac.uk> wrote in message
>
> To get the permutation matrix, you need another equation, PP' = I.

Is it sufficient? (P*P' = I) merely ensure P is orthogonal (unitary for complex). A matrix being a permutation is even more restrictive.

Bruno

Subject: finding permutation matrices using eig()

From: Yi Cao

Date: 23 Apr, 2010 08:47:05

Message: 6 of 14

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hqrlf5$hao$1@fred.mathworks.com>...
> "Yi Cao" <y.cao@cranfield.ac.uk> wrote in message
> >
> > To get the permutation matrix, you need another equation, PP' = I.
>
> Is it sufficient? (P*P' = I) merely ensure P is orthogonal (unitary for complex). A matrix being a permutation is even more restrictive.
>
> Bruno

It is true. The extra equtions can be sum(P) = n, sum(P,2)=n and 0<=p_ij<=1.

Yi

Subject: finding permutation matrices using eig()

From: Bruno Luong

Date: 23 Apr, 2010 09:41:22

Message: 7 of 14

Are A and B contain only 0/1? If it's the case, I think the problem can be more easily solved in GF(2) rather than in real or complex.

Bruno

Subject: finding permutation matrices using eig()

From: Roger Stafford

Date: 23 Apr, 2010 12:21:04

Message: 8 of 14

"Leslie Watkins" <Theantipoke@gmail.com> wrote in message <hqrck0$pl8$1@fred.mathworks.com>...
> I have two matrices A and B:
> A = [0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 1; 1 0 1 0 0; 0 0 1 0 0]
> B = [0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 1; 1 0 1 0 1; 0 0 1 1 0]
> There exists a permutation matrix P such that P*A*P' = B.
> (P = [0 0 1 0 0; 0 0 0 1 0; 1 0 0 0 0; 0 0 0 0 1; 0 1 0 0 0])
> I know P because this is a contrived data set, but I want to find P independently using MATLAB. Here's what I tried:
>
> [VA DA] = eig(A);
> [VB DB] = eig(B);
> "P" = VB*VA'
>
> In theory,
> P should be VB*VA'
>
> But it doesn't work!
>
> Here's what I get:
>
> QA =
> -0.0000 -0.7702 0.3069 -0.0000 0.5590
> -0.3717 0.4294 0.4390 0.6015 0.3505
> -0.6015 0.1378 -0.5100 -0.3717 0.4700
> 0.3717 0.4294 0.4390 -0.6015 0.3505
> 0.6015 0.1378 -0.5100 0.3717 0.4700
>
> QB =
> 0.6015 0.1378 0.5100 -0.3717 0.4700
> -0.3717 0.4294 -0.4390 -0.6015 0.3505
> -0.0000 -0.7702 -0.3069 0.0000 0.5590
> -0.6015 0.1378 0.5100 0.3717 0.4700
> 0.3717 0.4294 -0.4390 0.6015 0.3505
>
> "P" =
> 0.3131 0.0006 -0.2439 0.8951 0.2033
> -0.2695 -0.1091 0.8951 0.3381 0.0006
> 0.8116 -0.2695 0.3131 -0.2695 0.3131
> 0.3131 0.8951 0.2033 0.0006 -0.2439
> -0.2695 0.3381 0.0006 -0.1091 0.8951
>
> The weird thing is, P*QA should be QB, but when I use the correct value for P, I get:
> P*QA=
> -0.6015 0.1378 -0.5100 -0.3717 0.4700
> 0.3717 0.4294 0.4390 -0.6015 0.3505
> -0.0000 -0.7702 0.3069 -0.0000 0.5590
> 0.6015 0.1378 -0.5100 0.3717 0.4700
> -0.3717 0.4294 0.4390 0.6015 0.3505
>
> The values are the same as QB, but the signs are different, and they're not consistent across the columns. So why am I getting different eigenvectors for A and B? They should be the same, just arranged in a different order. Thank you in advance for any help.
---------
  First of all, you have no assurance that your eigenvalues from 'eig' for the two matrices are in the same order, particularly if they are complex-valued. You probably should be using 'svd' instead of 'eig'.

  Next, even when you have matching eigenvalues, the corresponding eigenvectors may be reversed in direction from what you need. Each one should be examined in turn to see if such a reversal needs to be done.

  Finally, if it happens that two or more singular values/eigenvalues are the same in each matrix, then you have a more difficult task facing you. The needed permutation may match up eigenvectors by way of some rotation which you will have to somehow determine.

Roger Stafford

Subject: finding permutation matrices using eig()

From: Bruno Luong

Date: 23 Apr, 2010 12:38:04

Message: 9 of 14

This works on the example, but I have no idea (yet) if it's reliable or how to generalize the method:

[UA S VA] = svd(A)
[UB S VB] = svd(B)

P=round(UB*UA')

Bruno

Subject: finding permutation matrices using eig()

From: Roger Stafford

Date: 23 Apr, 2010 12:48:05

Message: 10 of 14

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hqs3bg$3l0$1@fred.mathworks.com>...
> .........
> Finally, if it happens that two or more singular values/eigenvalues are the same in each matrix, then you have a more difficult task facing you. The needed permutation may match up eigenvectors by way of some rotation which you will have to somehow determine.
> .........
------
  I would add the following to that last point: In an extreme case with all eigenvalues equal, an eigenvector analysis tells you absolutely nothing.

Roger Stafford

Subject: finding permutation matrices using eig()

From: Roger Stafford

Date: 23 Apr, 2010 21:38:04

Message: 11 of 14

"Leslie Watkins" <Theantipoke@gmail.com> wrote in message <hqrck0$pl8$1@fred.mathworks.com>...
> I have two matrices A and B:
> A = [0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 1; 1 0 1 0 0; 0 0 1 0 0]
> B = [0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 1; 1 0 1 0 1; 0 0 1 1 0]
> There exists a permutation matrix P such that P*A*P' = B.
> (P = [0 0 1 0 0; 0 0 0 1 0; 1 0 0 0 0; 0 0 0 0 1; 0 1 0 0 0])
> I know P because this is a contrived data set, but I want to find P independently using MATLAB. Here's what I tried:
> .........
-----------
  After looking at your problem a little more, Leslie, I found it surprisingly messy to solve. The need is, wherever necessary, to reverse the signs of the appropriate columns of B so that its eigenvectors will match those in A, but doing so is faced with the problem that its rows have been permuted relative to A. Unfortunately it is that permutation we are seeking, so we don't know what it is yet. The following solves that problem by sorting and matching the eigenvectors and their negatives, except in those cases where both A and B have some equal eigenvalues. That is a harder problem to solve and I didn't attempt it at this time.

  I assume here that the eigenvalues in A and B are already in ascending, and therefore in matching, order, and are all distinct. VA and VB denote their respective eigenvector arrays.

 SA = sort(VA); % Sort eigenvectors of A
 SB = sort(VB); % Sort eigenvectors of B
 MB = -flipud(SB); % Get sorted negatives of B eigenvectors
 [t,ix] = min([sum(abs(SA-SB),1);sum(abs(SA-MB),1)],[],1); % Compare
 VB = VB.*repmat(2*(ix==1)-1,n,1); % Reverse signs accordingly
 P = VB*VA'; % Generate presumed permutation matrix
 P = +(P>1-1e-12); % Turn all elements into 1's and 0's

If this has succeeded, then at this point we would have P*A*P' = B.

Roger Stafford

Subject: finding permutation matrices using eig()

From: Brian Butler

Date: 20 Apr, 2011 03:50:04

Message: 12 of 14

I have found Roger's code very useful for my application. Thanks!
I'll just post a thing I had to fix. Sometimes the permutation matrix has
values near 0.5 before thresholding as the comparisons done with min() come
out nearly a tie for me. In the following code, I take all the close comparisons
are try flipping them...

SA = sort(VA); % Sort eigenvectors of A
SB = sort(VB); % Sort eigenvectors of B
MB = -flipud(SB); % Get sorted negatives of B eigenvectors
[t,ix] = min([sum(abs(SA-SB),1);sum(abs(SA-MB),1)],[],1); % Compare
[u,jx] = max([sum(abs(SA-SB),1);sum(abs(SA-MB),1)],[],1); % Compare
x=2*(ix==1)-1;
nVB = VB.*repmat(x,n,1); % Reverse signs accordingly
P = nVB*VA'; % Generate presumed permutation matrix
P = +(P>1-1e-12); % Turn all elements into 1's and 0's
uncert=find(u<1e-10);
if ~isempty(uncert) && (abs(det(P))~=1),
    e=[1;-1]; xm=x;
    for i=2:length(uncert),
        e=[ones(length(e),1) e; -1*ones(length(e),1) e];
    end
    for i=2:length(e), % already tried first one above
        xm(uncert)=x(uncert).*e(i,:);
        nVB = VB.*repmat(xm,n,1); % Reverse signs accordingly
        P = nVB*VA'; % Generate presumed permutation matrix
        P = +(P>1-1e-12); % Turn all elements into 1's and 0's
        if abs(det(P))==1,
            break;
        end
    end
end

Subject: finding permutation matrices using eig()

From: Brian Butler

Date: 20 Apr, 2011 03:54:04

Message: 13 of 14

I have found Roger's code very useful for my application. Thanks!
I'll just post a thing I had to fix. Sometimes the permutation matrix has
values near 0.5 before thresholding as the comparisons done with min() come
out nearly a tie for me. In the following code, I take all the close comparisons
are try flipping them...

SA = sort(VA); % Sort eigenvectors of A
SB = sort(VB); % Sort eigenvectors of B
MB = -flipud(SB); % Get sorted negatives of B eigenvectors
[t,ix] = min([sum(abs(SA-SB),1);sum(abs(SA-MB),1)],[],1); % Compare
[u,jx] = max([sum(abs(SA-SB),1);sum(abs(SA-MB),1)],[],1); % Compare
x=2*(ix==1)-1;
nVB = VB.*repmat(x,n,1); % Reverse signs accordingly
P = nVB*VA'; % Generate presumed permutation matrix
P = +(P>1-1e-12); % Turn all elements into 1's and 0's
uncert=find(u<1e-10);
if ~isempty(uncert) && (abs(det(P))~=1),
    e=[1;-1]; xm=x;
    for i=2:length(uncert),
        e=[ones(length(e),1) e; -1*ones(length(e),1) e];
    end
    for i=2:length(e), % already tried first one above
        xm(uncert)=x(uncert).*e(i,:);
        nVB = VB.*repmat(xm,n,1); % Reverse signs accordingly
        P = nVB*VA'; % Generate presumed permutation matrix
        P = +(P>1-1e-12); % Turn all elements into 1's and 0's
        if abs(det(P))==1,
            break;
        end
    end
end

Subject: finding permutation matrices using eig()

From: Brian Butler

Date: 20 Apr, 2011 18:57:07

Message: 14 of 14

Sorry for duplicate post above. I've noticed more issues as my test set of matrices has continued to expand. I've written a new version based on the homogeneous solution to Sylvester's equation: B*P - P*A = 0. I've been lucky so far with the rational option to MATLAB's null() command hitting vectored permutation matrices. Also note, just because its binary doesn't make it a permutation matrix. Use at your own risk.

% Find the nullspace of this. vec(P) will be a basis of nullspace.
N=null(kron(eye(n),B)-kron(A',eye(n)), 'r');
% Challenge is to find binary valued columns of N
grp=floor(((find(N==0)|(N==1))-1)/(n*n))+1;
a=find(hist(grp,1:size(N,2))==(n*n));
if (~isempty(a))
    st=(a(1)-1)*n*n+1;
    P=reshape( N(st:(st+n*n-1)),n,n);
else
    fprintf('couldnt find a binary column\n');
end

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