MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

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}]]



  • 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