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[[1]]], Transpose[{LinearSolve[ r + #2[[1]] IdentityMatrix[m], #2[[3]] - If[Times @@ Dimensions[#2] !== 0 && Times @@ Dimensions[#1] !== 0, Total[#2[[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[[3]]]] - 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}]]