3
$\begingroup$

I'm looking to solve a matrix equation and not sure where to start looking for resources. The equation is $$AX + XB = C\,,$$ where $A\in\mathbb{R}^{n\times n}$, $B\in\mathbb{R}^{m\times m}$, $C\in\mathbb{R}^{n\times m}$ and $X\in\mathbb{R}^{n\times m}$. (Alternatively $AX + XA = C$ with $n=m$ would be useful.)

I can see that I could change it into a system $$A'\mathbf{x}' = \mathbf{b}'\,,$$ with $A' \in \mathbb{R}^{nm\times nm}$, ${\mathbf{x}\in \mathbb{R}^{nm}}$, ${\mathbf{b}\in \mathbb{R}^{nm}}$, but was wondering if there were any shortcuts I could take.

$\endgroup$
  • $\begingroup$ Whilst we're here, is there a name for problems which include $EXD$ terms? $\endgroup$ – Steve Feb 17 '16 at 11:03
4
$\begingroup$

This is a Sylvester equation, although normally the matrices would all be square. Even for rectangular matrices, the Bartels-Stewart method applies (also A Hessenberg-Schur Method for the Problem $AX+XB=C$, Golub, Nash, Van Loan).

The idea is to use the Schur decompositions $$ A = URU^\top, \qquad B^\top = VSV^\top, $$ so that $AX+XB=C$ is transformed into $$ RY+YS^\top = F, \qquad Y = U^\top XV, F = U^\top CV. $$

Since $R$ is upper-triangular and $S^\top$ lower-triangular, this can be used to solve the system directly. If $Y = [y_1, \ldots, y_m]$ are the columns of $Y$, and $f_k$ are the columns of $F$, then the equation for $y_k$ depends only on $y_{k+1},\ldots,y_m$, and can be solved with back-substitution: $$ (R+s_{kk}I)y_k = f_k - \sum_{j>k} s_{kj}y_j. $$ When using the real Schur decomposition, this would sometimes be a coupled linear equation in $y_k, y_{k+1}$ instead.

This also shows it doesn't matter if $m\neq n$. To convert to the usual Sylvester equation with $m=n$ one could also just pad the matrices with zeros to obtain an equivalent problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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