Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: finding permutation matrices using eig()
Date: Fri, 23 Apr 2010 12:21:04 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 57
Message-ID: <hqs3bg$3l0$1@fred.mathworks.com>
References: <hqrck0$pl8$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1272025264 3744 172.30.248.38 (23 Apr 2010 12:21:04 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 23 Apr 2010 12:21:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:629166

"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