New Year's equation

The Sylvester equation is a matrix equation of form in mathematics and control theory

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

there are three predefined matrices. The matrix is the desired solution to the equation. ${\displaystyle A,B,C}$ ${\displaystyle n\times n}$ ${\displaystyle n\times n}$ ${\displaystyle X}$

A matrix can even be more general ; then is a matrix, a matrix and like a matrix. ${\displaystyle C}$ ${\displaystyle m\times n}$ ${\displaystyle A}$ ${\displaystyle m\times m}$ ${\displaystyle B}$ ${\displaystyle n\times n}$ ${\displaystyle X}$ ${\displaystyle C}$ ${\displaystyle m\times n}$

It is named after James Joseph Sylvester , who published about it in 1884.

The special case, which is important for applications, in which the matrix to be adjoint is, is also called the Lyapunov equation (after Alexander Michailowitsch Lyapunow ). ${\displaystyle B=A^{*}}$ ${\displaystyle A}$

Existence and uniqueness of the solution

Because of the non-commutativity of the matrix product , the equation cannot be solved directly. Nevertheless, it is simply a linear equation with the unknown, written in vectorized form matrix elements of a linear system of equations is formed. ${\displaystyle n^{2}}$ ${\displaystyle X_{ij}}$

In compact form it can be written using the Kronecker product and the vectorization operator as follows: ${\displaystyle \operatorname {vec} }$

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

Where is the identity matrix . ${\displaystyle I_{n}}$ ${\displaystyle n\times n}$

The direct solution of this system of equations is complex ( elements in a sparse matrix , unknowns and FLOPs ) and, moreover, numerically unstable . ${\displaystyle n^{4}}$ ${\displaystyle n^{2}}$ ${\displaystyle {\mathcal {O}}(n^{6})}$

There is a unique solution for all if and only if and have no common eigenvalues . ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle -B}$

Numerical resolution

Classically, the solution is calculated in a stable and robust manner using the Bartels-Stewart algorithm. In doing so, and through similarity transformations are brought into Schur's normal form and the New Year's equation is transformed into a simpler triangular shape that can be solved by inserting backwards. The similarity transformations are carried out with the Francis algorithm derived from the QR algorithm. ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle A=P^{-1}RP}$; ; and are suitable triangular matrices (in real terms they may contain isolated subdiagonal elements). ${\displaystyle B=Q^{-1}SQ}$ ${\displaystyle R}$ ${\displaystyle S}$

${\displaystyle AX+XB=P^{-1}RPX+XQ^{-1}SQ=C}$

${\displaystyle RPXQ^{-1}+PXQ^{-1}S=PCQ^{-1}}$

${\displaystyle RY+YS=D}$

There are and . ${\displaystyle Y=PXQ^{-1}}$ ${\displaystyle D=PCQ^{-1}}$

In the simpler triangular shape, you can now determine directly and from . The computing time is in the order of magnitude of the Schursch normal form ( FLOPs). ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X=P^{-1}YQ}$ ${\displaystyle {\mathcal {O}}(n^{3})}$

Newer algorithms manage with a Schur transformation (e.g. for ) and together with the other matrix (e.g. ) only form a Hessenberg matrix. ${\displaystyle B}$ ${\displaystyle A}$

The solution can also be calculated with the iterative solvers for linear systems.

credentials

• J. Sylvester: Sur l'equations en matrices ${\displaystyle px=xq}$ . In: CR Acad. Sc. Paris . tape 99 , 1884, pp. 67-71, 115-116 .
• RH Bartels, GW Stewart: Solution of the matrix equation ${\displaystyle AX+XB=C}$ . In: Communications of the ACM . tape 15 , no. 9 , 1972, p. 820-826 , doi : 10.1145 / 361573.361582 .
• R. Bhatia, P. Rosenthal: How and Why to Solve the Operator Equation ${\displaystyle AX-XB=Y}$ . In: Bulletin of the London Mathematical Society . tape 29 , no. 1 , 1997, p. 1–21 , doi : 10.1112 / S0024609396001828 .
• Sang-Gu Lee, Quoc-Phong Vu: Simultaneous solutions of Sylvester equations and idempotent matrices separating the joint spectrum . In: Linear Algebra and its Applications . tape 435 , no. 9 , November 2011, p. 2097–2109 , doi : 10.1016 / j.laa.2010.09.034 .
• Jituan Zhou Ruirui Wang and Qiang Niu: A Preconditioned Iteration Method for Solving Sylvester Equations . 2012 ( hindawi.com ).

Web links

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