Sylvester equation

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

${\displaystyle AX+XB=C.}$

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.[2]

Existence and uniqueness of the solutions

Using the Kronecker product notation and the vectorization operator ${\displaystyle \operatorname {vec} }$, we can rewrite Sylvester's equation in the form

${\displaystyle (I_{m}\otimes A+B^{T}\otimes I_{n})\operatorname {vec} X=\operatorname {vec} C,}$

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

Proposition. Given complex ${\displaystyle n\times n}$ matrices ${\displaystyle A}$ and ${\displaystyle B}$, Sylvester's equation has a unique solution ${\displaystyle X}$ for all ${\displaystyle C}$ if and only if ${\displaystyle A}$ and ${\displaystyle -B}$ have no common eigenvalues.

Proof. Consider the linear transformation ${\displaystyle S:M_{n}\rightarrow M_{n}}$ given by ${\displaystyle X\mapsto AX+XB}$.

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

(ii) Conversely, suppose that ${\displaystyle s}$ is a common eigenvalue of ${\displaystyle A}$ and ${\displaystyle -B}$. Note that ${\displaystyle s}$ is also an eigenvalue of the transpose ${\displaystyle A^{T}}$. Then there exist non-zero vectors ${\displaystyle v}$ and ${\displaystyle w}$ such that ${\displaystyle A^{T}w=sw}$ and ${\displaystyle Bv=-sv}$. Choose ${\displaystyle C}$ such that ${\displaystyle Cv={\overline {w}}}$, the vector whose entries are the complex conjugates of ${\displaystyle w}$. Then ${\displaystyle AX+XB=C}$ has no solution ${\displaystyle X}$, as is clear from the complex bilinear pairing ${\displaystyle \langle (AX+XB)v,w\rangle =\langle Cv,w\rangle =\langle {\overline {w}},w\rangle }$; 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: ${\displaystyle {\begin{bmatrix}A&C\\0&B\end{bmatrix}}}$ and ${\displaystyle {\begin{bmatrix}A&0\\0&B\end{bmatrix}}}$. 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.[4]

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

${\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}}.}$

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

Numerical solutions

A classical algorithm for the numerical solution of the Sylvester equation is the Bartels–Stewart algorithm, which consists of transforming ${\displaystyle A}$ and ${\displaystyle B}$ into Schur form by a QR algorithm, and then solving the resulting triangular system via back-substitution. This algorithm, whose computational cost is ${\displaystyle {\mathcal {O}}(n^{3})}$ arithmetical operations, is used, among others, by LAPACK and the lyap function in GNU Octave.[6] See also the sylvester function in that language.[7][8] In some specific image processing application, the derived Sylvester equation has a closed form solution.[9]

See also

• Lyapunov equation
• Algebraic Riccati equation

Notes

1. This equation is also commonly written in the equivalent form of AX − XB = C.
2. Bhatia and Rosenthal, 1997
3. 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.
4. Gerrish, F; Ward, A.G.B (Nov 1998). "Sylvester's matrix equation and Roth's removal rule". The Mathematical Gazette. 82 (495): 423–430. doi:10.2307/3619888. JSTOR 3619888.
5. Bhatia and Rosenthal, p.3
6. "Function Reference: Lyap".
7. "Functions of a Matrix (GNU Octave (version 4.4.1))".
8. The syl command is deprecated since GNU Octave Version 4.0
9. Wei, Q.; Dobigeon, N.; Tourneret, J.-Y. (2015). "Fast Fusion of Multi-Band Images Based on Solving a Sylvester Equation". IEEE. 24 (11): 4109–4121. arXiv:1502.03121. Bibcode:2015ITIP...24.4109W. doi:10.1109/TIP.2015.2458572. PMID 26208345.

References

• Sylvester, J. (1884). "Sur l'equations en matrices ${\displaystyle px=xq}$". C. R. Acad. Sci. Paris. 99 (2): 67–71, 115–116.
• Bartels, R. H.; Stewart, G. W. (1972). "Solution of the matrix equation ${\displaystyle AX+XB=C}$". Comm. ACM. 15 (9): 820–826. doi:10.1145/361573.361582.
• Bhatia, R.; Rosenthal, P. (1997). "How and why to solve the operator equation ${\displaystyle AX-XB=Y}$ ?". Bull. London Math. Soc. 29 (1): 1–21. doi:10.1112/S0024609396001828.
• 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. arXiv:1502.03121. Bibcode:2015ITIP...24.4109W. doi:10.1109/TIP.2015.2458572. PMID 26208345.
• 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