       Re: matrix equation

• To: mathgroup at smc.vnet.net
• Subject: [mg109606] Re: matrix equation
• From: Sseziwa Mukasa <mukasa at jeol.com>
• Date: Sat, 8 May 2010 07:05:27 -0400 (EDT)

```On May 7, 2010, at 6:28 AM, Conlon, Paul wrote:

> Hi & thanks.
>
>
>
> Here is my problem:
>
>
>
> Similarity matrix equation:    A . B   ==== ====   B . C
>
>
>
> If I have A and C, how do I determine B? I've looked at Solve and
> eigenvalues, etc. and have limited success with Solve (can accurately
> get a several of the matrix element, but not all. Eg  seems I can get
> sort of  parametric response when I put in B where I have the elements
> ....{{m11, m12, ...}, {m21, m22,....},  ...} ).
>
>
>
> Surely there is a solution because I can create A,B,C that work.

If A and B are square you are attempting to solve a Sylvester Equation, it is not true that a solution necessarily exists, there are restrictions on A and C, namely they can't have common eigenvalues.

If A and C don't have common eigenvalues you can solve problem using Schur Decomposition and backsubstitution, see section II of http://www.cs.cornell.edu/cv/ResearchPDF/Hessenberg.Schur.Method.pdf for example.  The paper also describes a solution based on a Hessenberg and Schur decomposition, and Mathematica can also do HessenbergDecomposition, but I'll sketch out the Bartels-Stewart algorithm:

bartelsStewart[a_, b_, c_] :==
Module[{r, s, u, v, f, m == First[Dimensions[a]], n == First[Dimensions[b]],
y}, {u, r} == SchurDecomposition[a]; {v, s} ==
SchurDecomposition[Transpose[b]]; f == Transpose[u].c.v;
y == bartelsStewartBacksubstitution[r, m, n, s, f]; u.y.Transpose[v]] /;
Equal @@ Dimensions[a] && Equal @@ Dimensions[b] &&
Intersection[Eigenvalues[a], Eigenvalues[b]] ==== {}

my implementation of the backsubstitution step is a little complicated, I've put it at the end of the message, but

bartelsStewart[A,-C,ConstantArray[0,{First[Dimensions[A]],Last[Dimensions[C]]}]]

will solve for B should it exist.  I'm not familiar with any solutions when A and C are not square.

Regards,
Ssezi

bartelsStewartBacksubstitution[r_, m_, n_, s_, f_] :==
Fold[ArrayFlatten[{{If[! MatrixQ[#2[]],
Transpose[{LinearSolve[
r + #2[] IdentityMatrix[m], #2[] -
If[Times @@ Dimensions[#2] !== 0 && Times @@ Dimensions[#1] !== 0,
Total[#2[] Transpose[#1]], 0]]}],
Transpose[
Partition[
LinearSolve[
ArrayFlatten[{{r + #2[[1, 1, 1]] IdentityMatrix[m], #2[[1, 1,
2]] IdentityMatrix[m]}, {#2[[1, 2, 1]] IdentityMatrix[m],
r + #2[[1, 2, 2]] IdentityMatrix[m]}}],
Flatten[Transpose[#2[]]] -
If[Times @@ Dimensions[#2] !== 0 && Times @@ Dimensions[#1] !== 0,
Join[Total[#2[[2, 1]] Transpose[#1]],
Total[#2[[2, 2]] Transpose[#1]]], 0]], m]]], #1}}] &,
ConstantArray[{}, m],
Table[If[i < n && s[[i + 1, i]] !== 0, Sequence @@ {},
If[i > 1 && s[[i, i - 1]] !== 0, {s[[i - 1 ;; i, i - 1 ;; i]],
s[[i - 1 ;; i, i + 1 ;;]], f[[All, {i - 1, i}]]}, {s[[i, i]],
s[[i, i + 1 ;;]], f[[All, i]]}]], {i, n, 1, -1}]]

```

• Prev by Date: Re: Optimization problem for dice game (repost)
• Next by Date: Re: Optimization problem for dice game (repost)
• Previous by thread: matrix equation
• Next by thread: HoldFirst, Unevaluated