Resources for solving mixed left and right matrix equations

Question

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.

Answer 1

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.