7
$\begingroup$

I happen to be working on a problem that reduces to solving the following equation:

$$\mathbf{A X B} + \mathbf{B X A} + \mathbf{C X C} = \mathbf{D}$$

where A through D are known matrices ( A, B, D are real, symmetric matrices and C is real and antisymmetric), and X is an unknown square matrix to be solved for.

Is there a name for this equation, and is there any known algorithm for solving this equation? (Without the C X C term this reduces to the continuous Lyapunov equation given either A or B is an invertible matrix. I wonder if anyone working in control theory may have seen such equations before.)

$\endgroup$

4 Answers 4

5
$\begingroup$

Another suggestion is to reduce the equation to a linear one, but I'm not sure if it's a practical method.

One may use the Kronecker product of two matrices to rewrite the equation as $(B^T \otimes A + A^T \otimes B + C^T \otimes C)X = D$, which is a linear equation. So if the matrices aren't large, I guess one can just compute the Kronecker product directly and use Gaussian elimination to solve it.

More reference: V.V. Prasolov, Problems and Theorems in Linear algebra 27.5 (p.123)

$\endgroup$
4
  • $\begingroup$ The equation is a linear one, as you said. Your solution is what I was going to recommend, and it's feasible if the "known" matrices A,B,C,D are very well known. $\endgroup$ Nov 20, 2009 at 3:35
  • $\begingroup$ urghh I meant to say reduce it to the form AX = B in my first sentence. $\endgroup$
    – user709
    Nov 20, 2009 at 4:13
  • $\begingroup$ I agree that in principle this is a possible way to solve the equation. (I assume X and D in your equation are the vectorized equivalents where you rearrange the matrices into vectors.) However in practice the resulting equation becomes numerically unstable very quickly. $\endgroup$ Nov 20, 2009 at 13:24
  • $\begingroup$ Chetan Tonde (in a deleted answer) suggests that you change $X$ to $vec(X)$ and $D$ to $vec(D)$ in your formula. $\endgroup$
    – S. Carnahan
    May 15, 2013 at 2:18
4
$\begingroup$

I'm not sure about names for this equation. As for solving it, I can say this much: It is a linear system and there is a solution in which $X$ is also symmetric. Following basics of matrix differentiation, it is the critical point of the functional $$\mathrm{Tr}(AXBX) + \frac{\mathrm{Tr}(CXCX)}2 = \mathrm{Tr}(DX).$$ This is not generally positive definite. If $A$ and $B$ are positive definition and the $C$ term is absent or small, then it is positive definite and you can use convex minimization methods (such as conjugate gradient) to solve for $X$. But in the general case, no such luck, although it simplifies matters somewhat that it is a symmetric linear system (with respect to the inner product $\langle X,Y \rangle = \mathrm{Tr}(XY)$ for symmetric matrices).

$\endgroup$
2
  • $\begingroup$ The functional equation you have is basically where I started from. I think A and B are SPD - they are matrices built from inner products of vectors: A<sub>ij</sub> = <u<sub>i</sub>|u<sub>j</sub>, B<sub>ij</sub> = <v<sub>i</sub>|v<sub>j</sub>. I don't know anything (yet) about the size of the C term - in my problem C<sub>ij</sub> = <u<sub>i</sub>|j<sub>j</sub> and this turns out to be antisymmetric. Not sure if this gives any insight into bounds on the size. $\endgroup$ Nov 20, 2009 at 2:44
  • $\begingroup$ Well, you'll make things better if you diagonalize C (into 2x2 blocks if you're over R) or both A and B. That is a natural way to make the system more sparse and perhaps clarify what is going on. Does anything commute or anticommute with anything? $\endgroup$ Nov 20, 2009 at 3:11
2
$\begingroup$

Apart from very special cases (something commuting with something else), as far as I know there is no efficient algorithm for this kind of equations with more than two summands. (by "efficient" I mean "better than the Kronecker product approach").

May sound strange, but I would actually suggest solving the Kronecker product system with an iterative method like SYMMLQ, or CG if it's positive definite. Matrix-vector products cost "only" $O(n^3)$, and dropping a term provides a better-than-nothing preconditioner.

$\endgroup$
0
$\begingroup$

This is a linear equation. As such, it is not hard to solve numerically for specific values of $A, B, C,$ and $D$.

As for a "closed form" solution, using matrix exponentials and the like, as in the Lyapunov equations of control theory.... I don't think there will be one except in particular cases (if $A$ and $C$ commute for instance). The eigenvectors of the operator $AXB+BXA$ can be written in terms of the eigenvectors of $A$ and $B$. I don't think it is so when $C$ is present, in general.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.