Sylvester equation
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, in the field of control theory, a Sylvester equation is a
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
equation In mathematics, an equation is a formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for example, in ...
of the form: :A X + X B = 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 mathematics, more specifically in functional analysis, a Banach space (pronounced ) is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the computation of vector length and distance between vector ...
. 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 In mathematics, the Kronecker product, sometimes denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a generalization of the outer product (which is denoted by the same symbol) from vectors to ...
notation and the vectorization operator \operatorname, we can rewrite Sylvester's equation in the form : (I_m \otimes A + B^T \otimes I_n) \operatornameX = \operatornameC, where A is of dimension n\! \times\! n, B is of dimension m\!\times\!m, X of dimension n\!\times\!m and I_k is the k \times k
identity matrix In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere. Terminology and notation The identity matrix is often denoted by I_n, or simply by I if the size is immaterial o ...
. In this form, the equation can be seen as a linear system of dimension mn \times mn. Theorem. Given matrices A\in \mathbb^ and B\in \mathbb^, the Sylvester equation AX+XB=C has a unique solution X\in \mathbb^ for any C\in\mathbb^ if and only if A and -B do not share any eigenvalue. Proof. The equation AX+XB=C is a linear system with mn unknowns and the same amount of equations. Hence it is uniquely solvable for any given C if and only if the homogeneous equation AX+XB=0 admits only the trivial solution 0. (i) Assume that A and -B do not share any eigenvalue. Let X be a solution to the abovementioned homogeneous equation. Then AX=X(-B), which can be lifted to A^kX = X(-B)^k for each k \ge 0 by mathematical induction. Consequently, p(A) X = X p(-B) for any polynomial p. In particular, let p be the characteristic polynomial of A. Then p(A)=0 due to the Cayley-Hamilton theorem; meanwhile, the
spectral mapping theorem In mathematics, especially functional analysis, a Banach algebra, named after Stefan Banach, is an associative algebra A over the real or complex numbers (or over a non-Archimedean complete normed field) that at the same time is also a Banach spa ...
tells us \sigma(p(-B)) = p(\sigma(-B)), where \sigma(\cdot) denotes the spectrum of a matrix. Since A and -B do not share any eigenvalue, p(\sigma(-B)) does not contain zero, and hence p(-B) is nonsingular. Thus X= 0 as desired. This proves the "if" part of the theorem. (ii) Now assume that A and -B share an eigenvalue \lambda. Let u be a corresponding right eigenvector for A, v be a corresponding left eigenvector for -B, and X=u^*. Then X\neq 0, and AX+XB = A(uv^*)-(uv^*)(-B) = \lambda uv^*-\lambda uv^* = 0. Hence X 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 In mathematics, especially functional analysis, a Banach algebra, named after Stefan Banach, is an associative algebra A over the real or complex numbers (or over a non-Archimedean complete normed field) that at the same time is also a Banach spa ...
, the nonsingularity of p(-B) in part (i) of the proof can also be demonstrated by the
Bézout's identity In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem: Here the greatest common divisor of and is taken to be . The integers and are called Bézout coefficients for ; they a ...
for coprime polynomials. Let q be the characteristic polynomial of -B. Since A and -B do not share any eigenvalue, p and q are coprime. Hence there exist polynomials f and g such that p(z)f(z)+q(z)g(z)\equiv 1. By the Cayley–Hamilton theorem, q(-B)=0. Thus p(-B)f(-B)=I, implying that p(-B) 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 \mathrm(uv^*) and \mathrm(uv^*) satisfy the homogenous equation AX+XB=0, 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: \begin A & C \\ 0 & B \end and \begin A & 0 \\0&B \end. 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 :\beginI_n & X \\ 0 & I_m \end \begin A&C\\0&B \end \begin I_n & -X \\ 0& I_m \end = \begin A&0\\0&B \end. 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 In numerical linear algebra, the Bartels–Stewart algorithm is used to numerically solve the Sylvester matrix equation AX - XB = C. Developed by R.H. Bartels and G.W. Stewart in 1971, it was the first numerically stable method that could be syst ...
, which consists of transforming A and B into
Schur form In the mathematical discipline of linear algebra, the Schur decomposition or Schur triangulation, named after Issai Schur, is a matrix decomposition. It allows one to write an arbitrary complex square matrix as unitarily equivalent to an upper tria ...
by a QR algorithm, and then solving the resulting triangular system via back-substitution. This algorithm, whose computational cost is \mathcal(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.


See also

*
Lyapunov equation In control theory, the discrete Lyapunov equation is of the form :A X A^ - X + Q = 0 where Q is a Hermitian matrix and A^H is the conjugate transpose of A. The continuous Lyapunov equation is of the form :AX + XA^H + Q = 0. The Lyapunov equation o ...
* Algebraic Riccati equation


Notes


References

* * * * * *


External links


Online solver for arbitrary sized matrices.




{{Authority control Matrices Control theory