finding permutation matrices using eig()
in [Matlab]
|
From: Roger Stafford on 23 Apr 2010 17:38 "Leslie Watkins" <Theantipoke(a)gmail.com> wrote in message <hqrck0$pl8$1(a)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 |