Prev: HoldFirst, Unevaluated
Next: labels in GraphicsGrid[]
From: Conlon, Paul on 7 May 2010 06:22
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. But
sometimes I get elements that are the trivial solution (zeroes). Also,
this is for a real world app, so the elements are real. I looked at
Solve, SolveAlways, FindInstance and the other recommended fns. If it is
parametric, interesting, but since I get some correct values from
real-world (vs real - ha) matrices I am dealing with that seems less
likely.



Thanks.



Paul

From: Sseziwa Mukasa on 8 May 2010 07:05
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}]]


 | 
Pages: 1
Prev: HoldFirst, Unevaluated
Next: labels in GraphicsGrid[]