A Faddeev sequence method for solving Lyapunov and Sylvester equations

Lyapunov and Sylvester equations play an important role in linear systems theory. This paper deals with a method of solving such equations of the form AP + PB = K and P − APB = K with A ∈ Rm × m, B ∈ Rn × n, and P, K ∈ Rm × n, by exploiting the matrix-algebra structure of the problem. No use is made of Kronecker products and the largest matrices occurring in the algorithms are of sizes m × m, n × n, and m × n. The Faddeev method for matrix inversion lies at the very heart of the algorithms presented. It occurs on several levels of the problem: for the matrices A and B and for the Lyapunov and Sylvester operators. The resulting algorithms are capable of solving the equations in a finite number of recursion steps. They are very much apt for symbolic calculation. It is shown how a solution can be quickly obtained for an equation with an arbitrary right-hand side K, provided a solution is known for a right-hand side xyT of rank 1, where (A, x) and (BT, y) are reachable pairs. The concept of a Faddeev reachability matrix introduced here turns out to be very useful. It establishes a close connection between the controller canonical (companion) form of a reachable pair (A, b) and the Faddeev sequence of A. If A is already on controller form, then its Faddeev sequence takes on an especially simple form. Also in the symmetric case where A = BT, many important simplifications arise. For this case alternative algorithms that require less iterations are developed. The paper concludes with some examples concerning the symbolic solution of the Lyapunov equation AP + PAT = bbT with (A, b) on controller form, showing the potential of the algorithms.