Sylvester equation

In control theory, the Sylvester equation is the matrix equation of the form:$A\; X\; +\; X\; B\; =\; C,$where $A,B,X,C$ are $n\; imes\; n$ matrices.

Existence and uniqueness of the solution

Using the Kronecker product notation and the vectorization operator $operatorname\{vec\}$, we can rewrite the equation in the form:$(I\_n\; otimes\; A\; +\; B^T\; otimes\; I\_n)\; operatorname\{vec\}X\; =\; operatorname\{vec\}C,$where $I\_n$ is the $n\; imes\; n$ identity matrix. In this form, the Sylvester equation can be seen as a linear system of dimension $n^2\; imes\; n^2$. [Rewriting the equation in this form is not advised for the numerical solution, though, since the linear system version is costly to solve and can be ill-conditioned]

If $A=ULU^\{-1\}$ and $B^T=VMV^\{-1\}$ are the Jordan canonical forms of $A$ and $B^T$, and $lambda\_i$ and $mu\_j$ are their eigenvalues, one can write:$I\_n\; otimes\; A\; +\; B^T\; otimes\; I\_n\; =\; (Uotimes\; V)(I\_n\; otimes\; L\; +\; M\; otimes\; I\_n)(U\; otimes\; V)^\{-1\}.$Since $(I\_n\; otimes\; L\; +\; M\; otimes\; I\_n)$ is upper triangular with diagonal elements $lambda\_i+mu\_j$, the matrix on the left hand side is singular if and only if there exist $i$ and $j$ such that $lambda\_i=-mu\_j$.

Therefore, we have proved that the Sylvester equation has a unique solution if and only if $A$ and $-B$ have no common eigenvalues.

Numerical solutions

A classical algorithm for the numerical solution of the Sylvester equation is the "Bartels--Stewart algorithm", which consists in transforming $A$ and $B$ into Schur form by a QR algorithm, and then solving the resulting triangular system via back-substitution. This algorithm, whose computational cost is O$(n^3)$ arithmetical operations, is used, among others, by LAPACK, Matlab and GNU Octave (in the syl function).

ee also

* Lyapunov equation

References

R. H. Bartels and G. W. Stewart, Solution of the matrix equation $AX +XB = C$, "Comm. ACM", 15 (1972), pp. 820 – 826.

Notes