Sylvester equation

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, in the field of control theory, the Sylvester equation is a matrix equation of the form

A X + X B = C,

where A,B,X,C are n \times n matrices: A,B,C are given and the problem is to find X.

Existence and uniqueness of the solutions[edit]

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 \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 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 = (V\otimes U)(I_n \otimes L +  M \otimes I_n)(V \otimes U)^{-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[edit]

A classical algorithm for the numerical solution of the Sylvester equation is the Bartels–Stewart algorithm, which consists of 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 and the lyap function in GNU Octave. See also the syl function in that language.

See also[edit]

References[edit]

  • J. Sylvester, Sur l’equations en matrices px = xq, C. R. Acad. Sc. Paris, 99 (1884), pp. 67 – 71, pp. 115 – 116.
  • R. H. Bartels and G. W. Stewart, Solution of the matrix equation AX +XB = C, Comm. ACM, 15 (1972), pp. 820 – 826.
  • R. Bhatia and P. Rosenthal, How and why to solve the operator equation AX -XB = Y  ?, Bull. London Math. Soc., 29 (1997), pp. 1 – 21.
  • S.-G. Lee and Q.-P. Vu, Simultaneous solutions of Sylvester equations and idempotent matrices separating the joint spectrum, Linear Algebra and its Applications, 435 (2011), pp. 2097 – 2109.

Notes[edit]

  1. ^ However, rewriting the equation in this form is not advised for the numerical solution since this version is costly to solve and can be ill-conditioned.

External links[edit]