# A Note on the Inversion of Sylvester Matrices in Control Systems

Authors: Hongkui Li; Ranran Li
Journal: Mathematical Problems in Engineering
 (2011)

---

## Abstract

We give a sufficient condition (the solvability of two standard equations) of Sylvester matrix by using the displacement structure of the Sylvester matrix, and, according to the sufficient condition, we derive a new fast algorithm for the inversion of a Sylvester matrix, which can be denoted as a sum of products of two triangular Toeplitz matrices. The stability of the inversion formula for a Sylvester matrix is also considered. The Sylvester matrix is numerically forward stable if it is nonsingular and well conditioned.


---

## Body

## 1. Introduction

LetR[x] be the space of polynomials over the real numbers. Given univariate polynomials f(x),g(x)∈R[x], a1≠0, where(1.1)f(x)=a1xn+a2xn-1+⋯+an+1,a1≠0,g(x)=b1xm+b2xm-1+⋯+bm+1,b1≠0.LetS denote the Sylvester matrix of f(x) and g(x):(1.2)S=(a1a2⋯⋯an+1a1a2⋯⋯an+1⋱⋱⋱a1a2⋯⋯an+1b1b2⋯bmbm+1b1b2⋯bmbm+1⋱⋱⋱⋱b1b2⋯bmbm+1)}mrow<}nrowSylvester matrix is applied in many science and technology fields. The solutions of Sylvester matrix equations and matrix inequations play an important role in the analysis and design of control systems. In determining the greatest common divisor of two polynomials, the Sylvester matrix plays a vital role, and the magnitude of the inverse of the Sylvester matrix is important in determining the distance to the closest polynomials which have a common root. Assuming that all principal submatrices of the matrix are nonsingular, in [1], Jing Yang et al. have given a fast algorithm for the inverse of Sylvester matrix by using the displacement structure of m+n-order Sylvester matrix.By using the displacement structure of the Sylvester matrix, in this paper, we give a sufficient condition (the solvability of two standard equations) of Toeplitz matrix, and, according to the sufficient condition, we derive a new fast algorithm for the inversion of a Sylvester matrix, which can be denoted as a sum of products of two triangular Toeplitz matrices. At last, the stability of the inversion formula for a Sylvester matrix is also considered. The Sylvester matrix is numerically forward stable if it is nonsingular and well conditioned.In this paper,∥·∥2 always denotes the Euclidean or spectral norm and ∥·∥F the Frobenius norm.


## 2. Preliminary Notes

In this section, we present a lemma that is important to our main results.Lemma 2.1 (see [2, Section 2.4.8]).
LetA,B∈ℂn,n and α∈ℂ. Then for any floating-point arithmetic with machine precision ε, one has that
(2.1)fl(αA)=αA+E,‖E‖F≤ε|α|‖A‖F≤εn|α|‖A‖2,fl(A+B)=A+B+E,‖E‖F≤ε‖A+B‖F≤εn‖A+B‖2,fl(AB)=AB+E,‖E‖F≤εn‖A‖F‖B‖F.
As usual, one neglects the errors of  O(ε2), O(ε̃2), and O(εε̃).


## 3. Sylvester Inversion Formula

In this section, we present our main results.Theorem 3.1.
Let matrixS be a Sylvester matrix; then it satisfies the formula
(3.1)KS-SK=emfT-em+ngT,
where K=(0e1e2⋯em+n-1) is a (m+n)×(m+n) shift matrix,
(3.2)f=(b1⋯bmbm+1-a1⋯-an)T,g=(0⋯0b1⋯bm)T.Proof.
We have that(3.3)KS-SK=(0a1⋯an+10⋯0a1⋯an+1⋯0⋮b1⋯bm+10⋯0b1⋯bm+10⋯0⋮0⋯0)-(0a1⋯an+10⋯0⋮0⋯a1⋯anb1⋯bm+1⋮0⋯0b1⋯bm)=(0⋯00⋯0⋮b1⋯bmbm+1-a1-a2⋯-an0⋯00⋮00⋯-b1⋯-bm)emfT-em+ngT=(0⋯00⋯0⋮b1⋯bmbm+1-a1-a2⋯-an0⋯00⋮00⋯-b1⋯-bm).
So KS-SK=emfT-em+ngT.Theorem 3.2.
Let  matrixS be a Sylvester matrix and x=(x1x2⋯xm+n)T, y=(y1y2⋯ym+n)T, μ=(μ1μ2⋯μm+n)T, and V=(V1V2⋯Vm+n)T  the solutions  of the systems of equations  Sx=em, Sy=em+n, STμ=f, and STV=g, respectively, where em and em+n are both (m+n)×1 vectors; then(a)
S is invertible, and the column vector wj(j=1,2,…,m+n) of  S-1 satisfies the recurrence relation(3.4)wm+n=y,wi-1=Kwi+μix-Viy,i=m+n,…,3,2,(b)(3.5)S-1=S1U1+S2U2=(ym+nym+n-1⋯y2y1ym+n⋱y3y2⋱⋱⋮ym+nym+n-1ym+n)(1-Vm+n1⋮⋮⋱-V3-V4⋯1-V2-V3⋯-Vm+n1)+(xm+nxm+n-1⋯x2x1xm+n⋱x3x2⋱⋱⋮xm+nxm+n-1xm+n)(0μm+n0⋮⋮⋱μ3μ4⋯0μ2μ3⋯μm+n0).Proof.
By Theorem3.1  Sx=em and Sy=em+n, we have that
(3.6)KS=SK+emfT-em+ngT=SK+SxfT-SygT=S[K+xfT-ygT],
so
(3.7)KiS=Ki-1S[K+xfT-ygT]=Ki-2KS[K+xfT-ygT]=Ki-2S[K+xfT-ygT]2⋮=S[K+xfT-ygT]i.
Hence, we have that
(3.8)Kiem+n=KiSy=S[K+xfT-ygT]iy,i=0,1,…,m+n-1.
Let
(3.9)wm+n-i=[K+xfT-ygT]iy,i=0,1,…,m+n-1.
It is easy to see that Kiem+n=em+n-i, and by (3.8)
(3.10)Swm+n-i=Kiem+n=em+n-i,i=0,1,…,m+n-1.
From Sy=em+n, we have that wm+n=y. Let X=(w1w2⋯wm+n); then
(3.11)[SX=S(w1w2⋯wm+n)=(Sw1Sw2⋯Swm+n)=Im+n],
so the matrix S is invertible and the inverse of S is the matrix X.
From (3.1), we have that(3.12)S-1(KS-SK)S-1=S-1(emfT-em+ngT)S-1,
and thus
(3.13)S-1K-KS-1=xμT-yVT.
So(3.14)(S-1K-KS-1)ei=(xμT-yVT)ei.
SinceKei=ei-1, we have that(3.15)wi-1=Ksi+μix-Viy,i=m+n,…,3,2,
and hence
(3.16)wm+n=y,wi-1=Kwi+μix-Viy,i=m+n,…,3,2.
For (b), by  (3.4)(3.17)wm+n=y,wm+n-1=Ky+μm+nx-Vm+ny,wm+n-2=K2y+Kμm+nx-KVm+ny+μm+n-1x-Vm+n-1y,⋯w1=Km+n-1y+Km+n-2μm+nx-Km+n-2Vm+ny+⋯+μ2x-V2y.
So
(3.18)S-1=(w1w2⋯wm+n)=(Km+n-1yKm+n-2y⋯Kyy)(1-Vm+n1⋮⋮⋱-V3-V4⋯1-V2-V3⋯-Vm+n1)+(Km+n-1xKm+n-2x⋯Kxx)(0μm+n0⋮⋮⋱μ3μ4⋯0μ2μ3⋯μm+n0)=(ym+nym+n-1⋯y2y1ym+n⋱y3y2⋱⋱⋮ym+nym+n-1ym+n)(1-Vm+n1⋮⋮⋱-V3-V4⋯1-V2-V3⋯-Vm+n1)+(xm+nxm+n-1⋯x2x1xm+n⋱x3x2⋱⋱⋮xm+nxm+n-1xm+n)(0μm+n0⋮⋮⋱μ3μ4⋯0μ2μ3⋯μm+n0).
This completes the proof.


## 4. Stability Analysis

In this section, we will show that the Sylvester inversion formula presented in this paper is evaluation forward stable.If, for all well conditioned problems, the computed solutionx̃ is close to the true solution  x, in the sense that the relative error  ∥x-x̃∥2/∥x∥2 is small, then we call the algorithm forward stable (the author called this weakly in [3]).  Round-off errors will occur in the matrix computation.Theorem 4.1.
Let matrixS be a nonsingular Sylvester matrix and well conditioned; then the formula in Theorem 3.2 is forward stable.Proof.
Assume that we have computed the solutionsx̃,ỹ,μ̃, and Ṽ of Sx=em, Sy=em+n, STμ=f, and STV=g in Theorem 3.2 which are perturbed by the normwise relative errors bounded by ε̃,
(4.1)‖x̃‖2≤‖x‖2(1+ε̃),‖ỹ‖2≤‖y‖2(1+ε̃),‖μ̃‖2≤‖μ‖2(1+ε̃),‖Ṽ‖2≤‖V‖2(1+ε̃).
Thus, we have that(4.2)‖S1‖F≤m+n‖y‖2,‖S2‖F≤m+n‖x‖2,‖U1‖F≤m+n1+‖V‖22,‖U2‖F≤m+n‖μ‖2.
The inversion formula in Theorem3.2, using the perturbed solutions x̃, ỹ, μ̃, and Ṽ, can be expressed as(4.3)S̃-1=fl(S̃1Ũ1+S̃2Ũ2)=fl((S1+ΔS1)(U1+ΔU1)+(S2+ΔS2)(U2+ΔU2))=S-1+ΔS1U1+S1ΔU1+ΔS2U2+S2ΔU2+E+F.
Here, and in the sequel, E is the matrix containing the error which results from computing the matrix products and  F contains the error from subtracting the matrices. For the error matrices  ΔS1, ΔU1, ΔS2, and ΔU2, we have that
(4.4)‖ΔS1‖F≤ε̃‖S1‖F≤ε̃m+n‖y‖2,‖ΔS2‖F≤ε̃‖S2‖F≤ε̃m+n‖x‖2,‖ΔU1‖F≤ε̃‖U1‖F≤ε̃m+n1+‖V‖22,‖ΔU2‖F≤ε̃‖U2‖F≤ε̃m+n‖μ‖2.
By Lemma2.1, we have the following bounds on E and F:(4.5)‖E‖2≤‖E‖F≤ε(m+n)(‖S1‖F‖U1‖F+‖S2‖F‖U2‖F)≤ε(m+n)2(‖y‖21+‖V‖22+‖x‖2‖μ‖2)≤ε(m+n)2(‖y‖2(1+‖V‖22)+‖x‖2‖μ‖2)‖F‖2≤m+nε‖S-1‖2.
Consequently, adding all these error bounds, by (4.3), we have that(4.6)‖S̃-1-S-1‖2≤(m+n)(2ε̃+(m+n)ε)(‖y‖2(1+‖V‖22)+‖x‖2‖μ‖2)+m+nε‖S-1‖2.
From the equationsSx=em, Sy=em+nSTμ=f, and STV=g in Theorem 3.2, we have that(4.7)‖y‖2≤‖S-1‖2,‖V‖2≤‖S-1‖2‖g‖2,‖x‖2≤‖S-1‖2,‖μ‖2≤‖S-1‖2‖f‖2.
Thus, the relative error is(4.8)‖S̃-1-S-1‖2‖S-1‖2≤(m+n)(2ε̃+(m+n)ε)(‖y‖2(1+‖V‖22)+‖x‖2‖μ‖2)2‖S-1‖2+εm+n≤(m+n)(2ε̃+(m+n)ε)(1+‖S-1‖2(‖g‖2+‖f‖2))+εm+n.
SinceS is well conditioned, ∥S-1∥2 is finite. It is easy to see that ∥g∥2,∥f∥2 are finite. Therefore, the formula presented in Theorem 3.2 is forward stable.
This completes the proof.


## 5. Numerical Example

This section gives an example to illustrate our results. All the following tests are performed by MATLAB 7.0.Example 5.1.
Givenf(x)=x+1,g(x)=x2+x+1, that is, a1=1,a2=1,b1=1,b2=1,b3=1,n=1,m=2,f=(1,1,0)T,g=(0,1,1)T, and  S=(110011111).
So(5.1)KS-SK=(010001000)(110011111)-(110011111)(010001000)=(011111000)-(011001011)=(0001100-1-1),(5.2)emfT-em+ngT=(010)(110)-(001)(011)=(0001100-1-1).
Therefore, KS-SK=emfT-em+ngT.
By the condition of Theorem3.2, we can get(5.3)x=(-1,1,0)T,y=(1,-1,1)T,μ=(1,0,0)T,V=(0,1,0)T.
Obviously, S is invertible and  S-1=(0-1111-1-101). And it is easy to see that  w3=y,
(5.4)w1=(01-1)=(010001000)(-110)+0(-110)-(1-11)=Sw2+μ2x-V2y,w2=(-110)=(010001000)(1-11)+0(-110)-0(1-11)=Sw3+μ3x-V3y,S-1=(0-1111-1-101)=(1-111-11)(101-101)+(01-1010)(000000)=S1U1+S2U2.



---

*Source: 609863-2011-05-26.xml*