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.)

Improve this question
$\endgroup$

4 Answers 4

Reset to default
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)

Improve this answer
$\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$
    – Theo Johnson-Freyd
    Commented 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
    Commented 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$
    – Jiahao Chen
    Commented 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 ♦
    Commented 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).

Improve this answer
$\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$
    – Jiahao Chen
    Commented 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$
    – Greg Kuperberg
    Commented 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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .