Sylvester equation

From Wikipedia, the free encyclopedia

In control theory, the Sylvester equation is the matrix equation of the form

AX + XB = C,

where A,B,X,C are n \times n matrices.

Contents

[edit] 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 In is the n \times n identity matrix. In this form, the Sylvester equation can be seen as a linear system of dimension n^2 \times n^2.[1]

If A = ULU − 1 and BT = VMV − 1 are the Jordan canonical forms of A and BT, and λi and μj are their eigenvalues, one can write

I_n \otimes A + B^T \otimes I_n = (U\otimes 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 λi + μj, the matrix on the left hand side is singular if and only if there exist i and j such that λi = − μj.

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

[edit] 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(n3) arithmetical operations, is used, among others, by LAPACK, Matlab and GNU Octave (in the syl function).

[edit] See also

[edit] References

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

[edit] Notes

  1. ^ 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