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:
Solve Matrix Equation AX=XB

Subject: Solve Matrix Equation AX=XB

From: Laoji Zhou

Date: 15 Jun, 2009 21:32:01

Message: 1 of 18

Do you know how to solve matrix equation AX=XB?

I was thinking of using Sylvester equation with C=0, but it would give the trivial solution X=0.

Thanks.

Subject: Solve Matrix Equation AX=XB

From: Matt

Date: 15 Jun, 2009 21:52:01

Message: 2 of 18

"Laoji Zhou" <laoji@yahoo.com> wrote in message <h16ekh$26u$1@fred.mathworks.com>...
> Do you know how to solve matrix equation AX=XB?

You could re-organize it into the form

G*x=0

and solve for x=X(:) as with typical linear equations.

But what kind of solution could you be looking for? Clearly, the trivial solution is the only solution if G is non-singular. If G is singular, you have a space of solutions, so what form would the solution take in that case?

Subject: Solve Matrix Equation AX=XB

From: John D'Errico

Date: 15 Jun, 2009 22:50:20

Message: 3 of 18

"Laoji Zhou" <laoji@yahoo.com> wrote in message <h16ekh$26u$1@fred.mathworks.com>...
> Do you know how to solve matrix equation AX=XB?
>
> I was thinking of using Sylvester equation with C=0, but it would give the trivial solution X=0.
>
> Thanks.

We went through this some months ago. Code was
posted to solve it then, based on the kron trick I
used in this submission.

http://www.mathworks.com/matlabcentral/fileexchange/19614

John

Subject: Solve Matrix Equation AX=XB

From: Bruno Luong

Date: 15 Jun, 2009 23:00:21

Message: 4 of 18

n = length(A);
G = kron(eye(n),A)-kron(B.',eye(n));
x = null(G)

% reshaping each column of x to (n x n) matrix X will provide a basis-element of the space of solutions.

Bruno

Subject: Solve Matrix Equation AX=XB

From: Bruno Luong

Date: 15 Jun, 2009 23:12:02

Message: 5 of 18

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <h16j7c$354$1@fred.mathworks.com>...
> "Laoji Zhou" <laoji@yahoo.com> wrote in message <h16ekh$26u$1@fred.mathworks.com>...
> > Do you know how to solve matrix equation AX=XB?
> >
> > I was thinking of using Sylvester equation with C=0, but it would give the trivial solution X=0.
> >
> > Thanks.
>
> We went through this some months ago. Code was
> posted to solve it then, based on the kron trick I
> used in this submission.
>
> http://www.mathworks.com/matlabcentral/fileexchange/19614
>

I just submitted a Bug report to the author. ;-)

Bruno

Subject: Solve Matrix Equation AX=XB

From: John D'Errico

Date: 16 Jun, 2009 00:26:02

Message: 6 of 18

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <h16kg2$ocu$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <h16j7c$354$1@fred.mathworks.com>...
> > "Laoji Zhou" <laoji@yahoo.com> wrote in message <h16ekh$26u$1@fred.mathworks.com>...
> > > Do you know how to solve matrix equation AX=XB?
> > >
> > > I was thinking of using Sylvester equation with C=0, but it would give the trivial solution X=0.
> > >
> > > Thanks.
> >
> > We went through this some months ago. Code was
> > posted to solve it then, based on the kron trick I
> > used in this submission.
> >
> > http://www.mathworks.com/matlabcentral/fileexchange/19614
> >
>
> I just submitted a Bug report to the author. ;-)
>
> Bruno

;-)

Yes, I guess I never worried about complex arrays
when I wrote it. I'll need to fix that and resubmit.

John

Subject: Solve Matrix Equation AX=XB

From: Laoji Zhou

Date: 17 Jun, 2009 15:27:02

Message: 7 of 18

John and Bruno:

Thank you very much. I will look at the scripts you posted.

John, did you fix the bug Bruno mentioned? I saw Transpose now on line 68, instead of complex conjugate transpose.

Thanks again

Laoji

Subject: Solve Matrix Equation AX=XB

From: Laoji Zhou

Date: 17 Jun, 2009 15:38:01

Message: 8 of 18

John:

It seems that your scripts solve equations AX+XA =0 or AX-XA=0 while I need to solve AX + XB =0.

AX+XB=0 is a case with K being a matrix in the form you used.

Did you see any discussion on AX+XB=0?

Thanks,

Laoji

Subject: Solve Matrix Equation AX=XB

From: John D'Errico

Date: 17 Jun, 2009 17:01:02

Message: 9 of 18

"Laoji Zhou" <laoji@yahoo.com> wrote in message <h1b206$iab$1@fred.mathworks.com>...
> John and Bruno:
>
> Thank you very much. I will look at the scripts you posted.
>
> John, did you fix the bug Bruno mentioned? I saw Transpose now on line 68, instead of complex conjugate transpose.
>
> Thanks again
>
> Laoji

I sent it in this morning. It appears to be up now.
I also just checked to see that the proper version
was uploaded, and it is.

John

Subject: Solve Matrix Equation AX=XB

From: Bruno Luong

Date: 19 Jun, 2009 11:04:01

Message: 10 of 18

"Laoji Zhou" <laoji@yahoo.com> wrote in message <h1b2kp$16n$1@fred.mathworks.com>...
> John:
>
> It seems that your scripts solve equations AX+XA =0 or AX-XA=0 while I need to solve AX + XB =0.
>
> AX+XB=0 is a case with K being a matrix in the form you used.
>
> Did you see any discussion on AX+XB=0?

This discussion starts with AX = XB. The formula is provided in post #4.

Bruno

Subject: Solve Matrix Equation AX=XB

From: John D'Errico

Date: 19 Jun, 2009 11:38:01

Message: 11 of 18

"Laoji Zhou" <laoji@yahoo.com> wrote in message <h1b2kp$16n$1@fred.mathworks.com>...
> John:
>
> It seems that your scripts solve equations AX+XA =0 or AX-XA=0 while I need to solve AX + XB =0.
>
> AX+XB=0 is a case with K being a matrix in the form you used.
>
> Did you see any discussion on AX+XB=0?

Bruno gave you the solution in this thread.

n = length(A);
G = kron(eye(n),A)-kron(B.',eye(n));
X = reshape(null(G),n,n);

My FEX submission uses the same trick to solve
that similar problem.

John

Subject: Solve Matrix Equation AX=XB

From: Itzhak Barkana

Date: 11 Jul, 2011 14:30:26

Message: 12 of 18

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <h1ftap$ips$1@fred.mathworks.com>...
> "Laoji Zhou" <laoji@yahoo.com> wrote in message <h1b2kp$16n$1@fred.mathworks.com>...
> > John:
> >
> > It seems that your scripts solve equations AX+XA =0 or AX-XA=0 while I need to solve AX + XB =0.
> >
> > AX+XB=0 is a case with K being a matrix in the form you used.
> >
> > Did you see any discussion on AX+XB=0?
>
> Bruno gave you the solution in this thread.
>
> n = length(A);
> G = kron(eye(n),A)-kron(B.',eye(n));
> X = reshape(null(G),n,n);
>
> My FEX submission uses the same trick to solve
> that similar problem.
>
> John

Careful: the equation may have more than 1 solution, so X could have matrical form, so the last line abover may end in error.
I suggest checking:

Y=null(G);
sG=size(G);
Y1=Y(:,1);
Y2=Y(:,2);
......
Then
X1= reshape(Y1,n,n);
X2= reshape(Y2,n,n);
.....

Besides, X1 and X2 could be solutions, but so are -X1 and -X2 and many other combinations.
For example, I was looking for a PDS solution for A'X=XA. The solutions that I got using the above were not PDS, yet after palying a little bit, I got the PDS one that I needed.

Itzhak

Subject: Solve Matrix Equation AX=XB

From: Matt J

Date: 26 Apr, 2012 18:53:07

Message: 13 of 18

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <h16jq4$a79$1@fred.mathworks.com>...
> n = length(A);
> G = kron(eye(n),A)-kron(B.',eye(n));
> x = null(G)
>
> % reshaping each column of x to (n x n) matrix X will provide a basis-element of the space of solutions.
===============

When B is non-singular (you could do something similar if A is as well), the approach below using generalized eigendecomposition gives much faster results. However, it seems to be because the NULL command is really inefficient. Maybe because NULL is M-coded?


%fake data
N=40;
[Q,R]=qr(rand(N));
A=Q'*diag(0:N-1)*Q;
[Q,R]=qr(rand(N));
B=Q'*diag(1:N)*Q;

tic;
 n = length(A);
 G = kron(eye(n),A)-kron(B.',eye(n));
 x1 = null(G);
toc
%Elapsed time is 5.129806 seconds.


tic;
 n=length(A);
[Va,Da]=eig(A,eye(n));
[Vb,Db]=eig(eye(n),B.');

    V=kron(Vb,Va);
    D=kron(diag(Db),diag(Da));

    idx=find( abs(D-1)<=1e-6*max(D));

    x2=V(:,idx);

toc;
%Elapsed time is 0.050615 seconds.

Subject: Solve Matrix Equation AX=XB

From: Bruno Luong

Date: 28 Apr, 2012 08:24:18

Message: 14 of 18

"Matt J" wrote in message <jnc5ij$blf$1@newscl01ah.mathworks.com>...

> tic;
> n=length(A);
> [Va,Da]=eig(A,eye(n));
> [Vb,Db]=eig(eye(n),B.');
>
> V=kron(Vb,Va);
> D=kron(diag(Db),diag(Da));
>
> idx=find( abs(D-1)<=1e-6*max(D));
>
> x2=V(:,idx);
>
> toc;

Very good idea.

Bruno

Subject: Solve Matrix Equation AX=XB

From: SMK

Date: 6 Mar, 2013 14:23:06

Message: 15 of 18

"Matt J" wrote in message <jnc5ij$blf$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <h16jq4$a79$1@fred.mathworks.com>...
> > n = length(A);
> > G = kron(eye(n),A)-kron(B.',eye(n));
> > x = null(G)
> >
> > % reshaping each column of x to (n x n) matrix X will provide a basis-element of the space of solutions.
> ===============
>
> When B is non-singular (you could do something similar if A is as well), the approach below using generalized eigendecomposition gives much faster results. However, it seems to be because the NULL command is really inefficient. Maybe because NULL is M-coded?
>
>
> %fake data
> N=40;
> [Q,R]=qr(rand(N));
> A=Q'*diag(0:N-1)*Q;
> [Q,R]=qr(rand(N));
> B=Q'*diag(1:N)*Q;
>
> tic;
> n = length(A);
> G = kron(eye(n),A)-kron(B.',eye(n));
> x1 = null(G);
> toc
> %Elapsed time is 5.129806 seconds.
>
>
> tic;
> n=length(A);
> [Va,Da]=eig(A,eye(n));
> [Vb,Db]=eig(eye(n),B.');
>
> V=kron(Vb,Va);
> D=kron(diag(Db),diag(Da));
>
> idx=find( abs(D-1)<=1e-6*max(D));
>
> x2=V(:,idx);
>
> toc;
> %Elapsed time is 0.050615 seconds.

But this method results empty matrix x1 and x2 ana matlab states
 Empty matrix: 4-by-0

Subject: Solve Matrix Equation AX=XB

From: Matt J

Date: 6 Mar, 2013 15:39:09

Message: 16 of 18

"SMK" wrote in message <kh7jga$hr9$1@newscl01ah.mathworks.com>...
>
> But this method results empty matrix x1 and x2 ana matlab states
> Empty matrix: 4-by-0

Probably because there is no solution for your particular input data A,B. If you run with my example data, then you will easily see that it returns a non-empty result.

Subject: Solve Matrix Equation AX=XB

From: Wey Fun

Date: 1 Jul, 2014 01:33:12

Message: 17 of 18

Hi;

Seems that the link http://www.mathworks.com/matlabcentral/fileexchange/19614
has been removed. Is it somewhere else now?

Fun Wey

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <h16j7c$354$1@fred.mathworks.com>...
> "Laoji Zhou" <laoji@yahoo.com> wrote in message <h16ekh$26u$1@fred.mathworks.com>...
> > Do you know how to solve matrix equation AX=XB?
> >
> > I was thinking of using Sylvester equation with C=0, but it would give the trivial solution X=0.
> >
> > Thanks.
>
> We went through this some months ago. Code was
> posted to solve it then, based on the kron trick I
> used in this submission.
>
> http://www.mathworks.com/matlabcentral/fileexchange/19614
>
> John

Subject: Solve Matrix Equation AX=XB

From: Mirosaw Kwaniak

Date: 1 Jul, 2014 14:13:09

Message: 18 of 18

Wey Fun <funwey@singnet.com.sg> wrote:
> Hi;
>
> Seems that the link http://www.mathworks.com/matlabcentral/fileexchange/19614
> has been removed. Is it somewhere else now?
>
> Fun Wey

https://www.mathworks.com/matlabcentral/newsreader/view_thread/167740
;)

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