finding permutation matrices using eig()
in [Matlab]
|
From: Leslie Watkins on 23 Apr 2010 01:53 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.
From: Bruno Luong on 23 Apr 2010 02:14 "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]) 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
From: Leslie Watkins on 23 Apr 2010 02:48 "Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <hqrdrf$feq$1(a)fred.mathworks.com>... > "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]) > > > 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!
From: Yi Cao on 23 Apr 2010 03:49 "Leslie Watkins" <Theantipoke(a)gmail.com> wrote in message <hqrfr5$gc5$1(a)fred.mathworks.com>... > "Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <hqrdrf$feq$1(a)fred.mathworks.com>... > > "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]) > > > > > > 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
From: Bruno Luong on 23 Apr 2010 04:24
"Yi Cao" <y.cao(a)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 |