Sylvester equation

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

[math]\displaystyle{ A X + X B = C. }[/math]

It is named after English mathematician James Joseph Sylvester. 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 [math]\displaystyle{ \operatorname{vec} }[/math], we can rewrite Sylvester's equation in the form

[math]\displaystyle{ (I_m \otimes A + B^T \otimes I_n) \operatorname{vec}X = \operatorname{vec}C, }[/math]

where [math]\displaystyle{ A }[/math] is of dimension [math]\displaystyle{ n\! \times\! n }[/math], [math]\displaystyle{ B }[/math] is of dimension [math]\displaystyle{ m\!\times\!m }[/math], [math]\displaystyle{ X }[/math] of dimension [math]\displaystyle{ n\!\times\!m }[/math] and [math]\displaystyle{ I_k }[/math] is the [math]\displaystyle{ k \times k }[/math] identity matrix. In this form, the equation can be seen as a linear system of dimension [math]\displaystyle{ mn \times mn }[/math].

Theorem. Given matrices [math]\displaystyle{ A\in \mathbb{C}^{n\times n} }[/math] and [math]\displaystyle{ B\in \mathbb{C}^{m\times m} }[/math], the Sylvester equation [math]\displaystyle{ AX+XB=C }[/math] has a unique solution [math]\displaystyle{ X\in \mathbb{C}^{n\times m} }[/math] for any [math]\displaystyle{ C\in\mathbb{C}^{n\times m} }[/math] if and only if [math]\displaystyle{ A }[/math] and [math]\displaystyle{ -B }[/math] do not share any eigenvalue.

Proof. The equation [math]\displaystyle{ AX+XB=C }[/math] is a linear system with [math]\displaystyle{ mn }[/math] unknowns and the same number of equations. Hence it is uniquely solvable for any given [math]\displaystyle{ C }[/math] if and only if the homogeneous equation [math]\displaystyle{ AX+XB=0 }[/math] admits only the trivial solution [math]\displaystyle{ 0 }[/math].

(i) Assume that [math]\displaystyle{ A }[/math] and [math]\displaystyle{ -B }[/math] do not share any eigenvalue. Let [math]\displaystyle{ X }[/math] be a solution to the abovementioned homogeneous equation. Then [math]\displaystyle{ AX=X(-B) }[/math], which can be lifted to [math]\displaystyle{ A^kX = X(-B)^k }[/math] for each [math]\displaystyle{ k \ge 0 }[/math] by mathematical induction. Consequently, [math]\displaystyle{ p(A) X = X p(-B) }[/math] for any polynomial [math]\displaystyle{ p }[/math]. In particular, let [math]\displaystyle{ p }[/math] be the characteristic polynomial of [math]\displaystyle{ A }[/math]. Then [math]\displaystyle{ p(A)=0 }[/math] due to the Cayley-Hamilton theorem; meanwhile, the spectral mapping theorem tells us [math]\displaystyle{ \sigma(p(-B)) = p(\sigma(-B)), }[/math] where [math]\displaystyle{ \sigma(\cdot) }[/math] denotes the spectrum of a matrix. Since [math]\displaystyle{ A }[/math] and [math]\displaystyle{ -B }[/math] do not share any eigenvalue, [math]\displaystyle{ p(\sigma(-B)) }[/math] does not contain zero, and hence [math]\displaystyle{ p(-B) }[/math] is nonsingular. Thus [math]\displaystyle{ X= 0 }[/math] as desired. This proves the "if" part of the theorem.

(ii) Now assume that [math]\displaystyle{ A }[/math] and [math]\displaystyle{ -B }[/math] share an eigenvalue [math]\displaystyle{ \lambda }[/math]. Let [math]\displaystyle{ u }[/math] be a corresponding right eigenvector for [math]\displaystyle{ A }[/math], [math]\displaystyle{ v }[/math] be a corresponding left eigenvector for [math]\displaystyle{ -B }[/math], and [math]\displaystyle{ X=u{v}^* }[/math]. Then [math]\displaystyle{ X\neq 0 }[/math], and [math]\displaystyle{ AX+XB = A(uv^*)-(uv^*)(-B) = \lambda uv^*-\lambda uv^* = 0. }[/math] Hence [math]\displaystyle{ X }[/math] 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 nonsingularity of [math]\displaystyle{ p(-B) }[/math] in part (i) of the proof can also be demonstrated by the Bézout's identity for coprime polynomials. Let [math]\displaystyle{ q }[/math] be the characteristic polynomial of [math]\displaystyle{ -B }[/math]. Since [math]\displaystyle{ A }[/math] and [math]\displaystyle{ -B }[/math] do not share any eigenvalue, [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] are coprime. Hence there exist polynomials [math]\displaystyle{ f }[/math] and [math]\displaystyle{ g }[/math] such that [math]\displaystyle{ p(z)f(z)+q(z)g(z)\equiv 1 }[/math]. By the Cayley–Hamilton theorem, [math]\displaystyle{ q(-B)=0 }[/math]. Thus [math]\displaystyle{ p(-B)f(-B)=I }[/math], implying that [math]\displaystyle{ p(-B) }[/math] is nonsingular.

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 [math]\displaystyle{ \mathrm{Re}(uv^*) }[/math] and [math]\displaystyle{ \mathrm{Im}(uv^*) }[/math] satisfy the homogenous equation [math]\displaystyle{ AX+XB=0 }[/math], 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: [math]\displaystyle{ \begin{bmatrix} A & C \\ 0 & B \end{bmatrix} }[/math] and [math]\displaystyle{ \begin{bmatrix} A & 0 \\0&B \end{bmatrix} }[/math]. 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

[math]\displaystyle{ \begin{bmatrix}I_n & X \\ 0 & I_m \end{bmatrix} \begin{bmatrix} A&C\\0&B \end{bmatrix} \begin{bmatrix} I_n & -X \\ 0& I_m \end{bmatrix} = \begin{bmatrix} A&0\\0&B \end{bmatrix}. }[/math]

Roth's removal rule does not generalize to infinite-dimensional bounded operators on a Banach space. Nevertheless, Roth's removal rule generalizes to the systems of Sylvester equations.

Numerical solutions

A classical algorithm for the numerical solution of the Sylvester equation is the Bartels–Stewart algorithm, which consists of transforming [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] into Schur form by a QR algorithm, and then solving the resulting triangular system via back-substitution. This algorithm, whose computational cost is [math]\displaystyle{ \mathcal{O}(n^3) }[/math] 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 applications, the derived Sylvester equation has a closed form solution.

See also

• Lyapunov equation, a special case of the Sylvester equation
• Algebraic Riccati equation

References

• Sylvester, J. (1884). "Sur l'equations en matrices [math]\displaystyle{ px = xq }[/math]". C. R. Acad. Sci. Paris 99 (2): 67–71, 115–116. 
• Bartels, R. H.; Stewart, G. W. (1972). "Solution of the matrix equation [math]\displaystyle{ AX +XB = C }[/math]". Comm. ACM 15 (9): 820–826. doi:10.1145/361573.361582. 
• Bhatia, R.; Rosenthal, P. (1997). "How and why to solve the operator equation [math]\displaystyle{ AX -XB = Y }[/math] ?". Bull. London Math. Soc. 29 (1): 1–21. doi:10.1112/S0024609396001828. 
• Dmytryshyn, Andrii; Kågström, Bo (2015). "Coupled Sylvester-type Matrix Equations and Block Diagonalization". SIAM Journal on Matrix Analysis and Applications 36 (2): 580–593. doi:10.1137/151005907. 
• Lee, S.-G.; Vu, Q.-P. (2011). "Simultaneous solutions of Sylvester equations and idempotent matrices separating the joint spectrum". Linear Algebra Appl. 435 (9): 2097–2109. doi:10.1016/j.laa.2010.09.034. 
• Wei, Q.; Dobigeon, N.; Tourneret, J.-Y. (2015). "Fast Fusion of Multi-Band Images Based on Solving a Sylvester Equation". IEEE Transactions on Image Processing 24 (11): 4109–4121. doi:10.1109/TIP.2015.2458572. PMID 26208345. Bibcode: 2015ITIP...24.4109W. 
• Birkhoff and MacLane. A survey of Modern Algebra. Macmillan. pp. 213, 299. 

External links

• Online solver for arbitrary sized matrices.
• Mathematica function to solve the Sylvester equation
• MATLAB function to solve the Sylvester equation