Sylvester equation

In mathematics, in the field of control theory, a Sylvester equation is a matrix equation of the form:
Then given matrices "A", "B", and "C", the problem is to find the possible matrices "X" that obey this equation. All matrices are assumed to have coefficients in the complex numbers. For the equation to make sense, the matrices must have appropriate sizes, for example they could all be square matrices of the same size. But more generally, "A" and "B" must be square matrices of sizes "n" and "m" respectively, and then "X" and "C" both have "n" rows and "m" columns.
A Sylvester equation has a unique solution for "X" exactly when there are no common eigenvalues of "A" and −"B".
More generally, the equation "AX" + "XB" = "C" has been considered as an equation of bounded operators on a (possibly infinite-dimensional) Banach space. In this case, the condition for the uniqueness of a solution "X" is almost the same: There exists a unique solution "X" exactly when the spectra of "A" and −"B" are disjoint.
Existence and uniqueness of the solutions.
Using the Kronecker product notation and the vectorization operator formula_2, we can rewrite Sylvester's equation in the form
where formula_4 is of dimension formula_5, formula_6 is of dimension formula_7, formula_8 of dimension formula_9 and formula_10 is the formula_11 identity matrix. In this form, the equation can be seen as a linear system of dimension formula_12.
Theorem. 
Given matrices formula_13 and formula_14, the Sylvester equation formula_15 has a unique solution formula_16 for any formula_17 if and only if formula_4 and formula_19 do not share any eigenvalue.
Proof. 
The equation formula_15 is a linear system with formula_21 unknowns and the same amount of equations. Hence it is uniquely solvable for any given formula_22 if and only if the homogeneous equation 
formula_23
admits only the trivial solution formula_24.
(i) Assume that formula_4 and formula_19 do not share any eigenvalue. Let formula_8 be a solution to the abovementioned homogeneous equation. Then formula_28, which can be lifted to 
formula_29
for each formula_30
by mathematical induction. Consequently,
formula_31
for any polynomial formula_32. In particular, let formula_32 be the characteristic polynomial of formula_4. Then 
formula_35 
due to the Cayley-Hamilton theorem; meanwhile, the spectral mapping theorem tells us
formula_36
where formula_37 denotes the spectrum of a matrix. Since formula_4 and formula_19 do not share any eigenvalue, formula_40 does not contain zero, and hence formula_41 is nonsingular. Thus formula_42 as desired. This proves the "if" part of the theorem.
(ii) Now assume that formula_4 and formula_19 share an eigenvalue formula_45. Let formula_46 be a corresponding right eigenvector for formula_4, formula_48 be a corresponding left eigenvector for formula_19, and formula_50. Then formula_51, and 
formula_52
Hence formula_8 is a nontrivial solution to the aforesaid homogeneous equation, justifying the "only if" part of the theorem. Q.E.D.
As an alternative to the spectral mapping theorem, the nonsigularity of formula_41 in part (i) of the proof can also be demonstrated by the Bézout's identity for coprime polynomials. 
Let formula_55 be the characteristic polynomial of formula_19. Since formula_4 and formula_19 do not share any eigenvalue, formula_32 and formula_55 are coprime. Hence there exist polynomials formula_61 and formula_62 such that formula_63. By the Cayley–Hamilton theorem, formula_64. Thus formula_65, implying that formula_41 is nonsigular.
The theorem remains true for real matrices with the caveat that one considers their complex eigenvalues. The proof for the "if" part is still applicable; for the "only if" part, note that both formula_67 and formula_68 satisfy the homogenous equation formula_69, and they cannot be zero simultaneously.
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: formula_70 and formula_71. 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 formula_4 and formula_6 into Schur form by a QR algorithm, and then solving the resulting triangular system via back-substitution. This algorithm, whose computational cost is formula_75 arithmetical operations, is used, among others, by LAPACK and the codice_1 function in GNU Octave. See also the codice_2 function in that language. In some specific image processing application, the derived Sylvester equation has a closed form solution.