Sylvester equation

Existence and uniqueness of the solutions

Using the Kronecker product notation and the vectorization operator vec , we can rewrite Sylvester's equation in the form

where I k is the k × k identity matrix. In this form, the equation can be seen as a linear system of dimension m n × m n .

Proposition. Given complex n × n matrices A and B , Sylvester's equation has a unique solution X for all C if and only if A and − B have no common eigenvalues.

Proof. Consider the linear transformation S : M n → M n given by X ↦ A X + X B .

(i) Suppose that A and − B have no common eigenvalues. Then their characteristic polynomials f ( z ) and g ( z ) have highest common factor 1 . Hence there exist complex polynomials p ( z ) and q ( z ) such that p ( z ) f ( z ) + q ( z ) g ( z ) = 1 . By the Cayley–Hamilton theorem, f ( A ) = 0 = g ( − B ) ; hence g ( A ) q ( A ) = I . Let X be any solution of S ( X ) = 0 ; so A X = − X B and repeating this one sees that X = q ( A ) g ( A ) X = q ( A ) X g ( − B ) = 0 . Hence by the rank plus nullity theorem S is invertible, so for all C there exists a unique solution X .

(ii) Conversely, suppose that s is a common eigenvalue of A and − B . Note that s is also an eigenvalue of the transpose A T . Then there exist non-zero vectors v and w such that A T w = s w and B v = − s v . Choose C such that C v = w ¯ , the vector whose entries are the complex conjugates of w . Then A X + X B = C has no solution X , as is clear from the complex bilinear pairing < ( A X + X B ) v , w >=< C v , w >=< w ¯ , w > ; the right-hand side is positive whereas the left is zero.

Roth's removal rule

Given two square complex matrices A and B, of size n and m, and a matrix C of size n by m, then one can ask when the following two square matrices of size n+m are similar to each other: [ A C 0 B ] and [ A 0 0 B ] . The answer is that these two matrices are similar exactly when there exists a matrix X such that AX-XB=C. In other words, X is a solution to a Sylvester equation. This is known as Roth's removal rule.

One easily checks one direction: If AX-XB=C then

Roth's removal rule does not generalize to infinite-dimensional bounded operators on a Banach space.

Numerical solutions

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 sylvester function in that language. In some specific image processing application, the derived Sylvester equation has a closed form solution.