Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

4 Answers

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)

share|improve this answer
    
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. –  Theo Johnson-Freyd Nov 20 '09 at 3:35
    
urghh I meant to say reduce it to the form AX = B in my first sentence. –  Ho Chung Siu Nov 20 '09 at 4:13
    
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. –  Jiahao Chen Nov 20 '09 at 13:24
    
Chetan Tonde (in a deleted answer) suggests that you change $X$ to $vec(X)$ and $D$ to $vec(D)$ in your formula. –  S. Carnahan May 15 '13 at 2:18
add comment

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

share|improve this answer
    
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. –  Jiahao Chen Nov 20 '09 at 2:44
    
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? –  Greg Kuperberg Nov 20 '09 at 3:11
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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