# Algorithms for Solving Nonhomogeneous Generalized Sylvester Matrix Equations

Authors: Ehab A. El-Sayed; Eid E. El Behady
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This paper considers a new method to solve the first-order and second-order nonhomogeneous generalized Sylvester matrix equationsAV+BW=EVF+R and MVF2+DVF+KV=BW+R, respectively, where A,E,M,D,K,B, and F are the arbitrary real known matrices and V and W are the matrices to be determined. An explicit solution for these equations is proposed, based on the orthogonal reduction of the matrix F to an upper Hessenberg form H. The technique is very simple and does not require the eigenvalues of matrix F to be known. The proposed method is illustrated by numerical examples.


---

## Body

## 1. Introduction

Consider the following two homogeneous generalized Sylvester matrix equations:(1)AV+BW=EVF,(2)MVF2+DVF+KV=BW.Matrix equation (1) is called a first-order homogeneous generalized Sylvester matrix equation that is closely related to many problems in linear systems theory, such as eigenstructure assignment [1–5] and control of systems with input constraints [6]. Second-order homogeneous generalized Sylvester matrix equation (2) has found applications in many control problems, for example, pole assignment [7–9] and eigenstructure assignment [10, 11].As a generalization of the above matrix equations, we have considered the following nonhomogeneous generalized Sylvester matrix equation:(3)AV+BW=EVF+R,(4)MVF2+DVF+KV=BW+R.where A,E,M,D,K,B∈ℝn×n, R∈ℝn×p, and F∈ℝp×p are the known matrices, while V∈ℝn×p and W∈ℝn×p need to be determined. Several authors have studied different methods for matrix equation (3) (see for example, Song and Chen, [12], Ramadan et al. [13], Duan [14], and Wu et al. [15]). The second-order nonhomogeneous Sylvester matrix equation was introduced by Duan [16]. Recently, Ramadan et al. [17] developed the Hessenberg method to solve the Sylvester matrix equation XA+BX=C by reducing only one coefficient matrix to a block upper Hessenberg form. The main goal of this paper is to present algorithms for solving well-known nonhomogeneous generalized Sylvester matrix equations (3) and (4). The proposed algorithm differs from the preceding standard methods; in our algorithms, F is only reduced to an unreduced upper Hessenberg matrix H, and eigenvalues of matrix F must be distinct, because if any eigenvalue of H repeats, then it is defective. An unreduced Hessenberg matrix is always nonsingular, so F must be nonsingular. Throughout this paper, the notation (GSME) is used for generalized Sylvester matrix equation and we assume that detE≠0, detF≠0, detB≠0, and detM≠0.


## 2. The Proposed Method forAV+BW=EVF+R

Consider the following nonhomogeneous generalized first-order Sylvester matrix equation:(5)AV+BW=EVF+R,where A,E,B∈ℝn×n,R∈ℝn×p, and F∈ℝp×p are the known matrices, while V,W∈ℝn×p are to be determined. The following lemma plays a vital role in this paper.Lemma 1.
(see [18, 19]). Let H=hij∈ℝp×p be an unreduced upper Hessenberg matrix and let x1,x2,…,xp be the p successive columns of a matrix X that commutes with H; then,(i)
x1 can be chosen arbitrarily.(ii)
The columnsx2 through xp can be computed recursively by the following formula:(6)xi+1=1hi+1,iHxi−∑j=1ihj,ixj,i=1,2,…,p−1.
Algorithm1 constructs an unknown matrix L=lkk=1p∈ℝn×p and compute matrix G=0¯0¯⋯g∈ℝn×p for the following matrix equation:(7)AL+BG=ELH+S,or(8)Al1,l2,…,lp+0¯,0¯,…,Bg=El1,El2,…,Elph11h12h13⋯h1ph21h22h23⋯h2p0h32h33⋯h3p⋮⋮⋮⋱⋮000hp,p−1hpp+s1,s2,…,sp,where l1,l2,…,lp are the columns of L, 0¯ is the zero vector, g is the unknown vector, and S=s1,s2,…,sp is the known real n×p matrix.Algorithm 1: The proposed algorithm for AL + BG = ELH + S.
Step 1
Choosel1 arbitrarily
For
i
=
1,2
,
…
,
p
−
1 do
l
i
+
1
=
E
−
1
/
h
i
+
1
,
i
A
l
i
−
s
i
−
∑
j
=
1
i
h
j
,
i
E
l
j;
Step 2
Computeg; for Bg=sp+∑j=1phj,pElj−Alp.Theorem 1.
The solution of matrix equation (5) is V=LXQT and W=GXQT, where A,E,B∈ℝn×n,R∈ℝn×p, and F∈ℝp×p are the known matrices and the matrix X is generated as in Lemma 1.Proof.
Matrix equation (5) can be rewritten in the following form:(9)AVQ+BWQ=EVQQTFQ+RQ.
That is,(10)AV^+BW^=EV^H+R˜,where H=QTFQ∈ℝp×p is an unreduced upper Hessenberg matrix, R˜=RQ, and Q∈ℝp×p is an orthogonal similarity transformation. The matrix X∈ℝp×p is generated by (6), and matrix equation (7) is multiplied by X to get(11)ALX+BGX=ELHX+SX.
By using Lemma1HX=XH, assume that SX=R˜,V^=LX, and W^=GX, where L and G are computed from Algorithm 1. Then, we recover the original problem via the relations V=V^QT, W=W^QT, R=R˜QT, and F=QHQT, and then, the solution of (5) is V=LXQT and W=GXQT (see Algorithm  2).Algorithm 2: The proposed algorithm for AV+BW=EVF+R.
Input: Matrices A,E,B∈ℝn×n,R∈ℝn×p and F∈ℝp×p.
Output: Matrices V and W.
Assumptions: detE≠0detF≠0, detB≠0, and X are nonsingular matrix as shown in [19] and eigenvalues of matrix F must be distinct.
Step 1: Reduce F to an unreduced upper Hessenberg H=QTFQ∈ℝp×p. Let Q be an orthogonal matrix.
Step 2: Construct the matrix X∈ℝp×p generated by (6).
Step 3: Compute the matrix S∈ℝn×p by solving SX=RQ.
Step 4: Construct the matrices L and G as shown in Algorithm 1.
Step 5: Compute V=LXQT and W=GXQT.


## 3. The Proposed Method ofMVF2+DVF+KV=BW+R

Consider the following second-order nonhomogeneous generalized Sylvester matrix equation:(12)MVF2+DVF+KV=BW+R,where M,D,K,B∈ℝn×n,R∈ℝn×p, and F∈ℝp×p are the known matrices, while V∈ℝn×p and W∈ℝn×p are to be determined.The following algorithm constructs an unknown matrixL∈ℝn×p and computes matrix G∈ℝn×p for the following matrix equation:(13)MLH2+DLH+KL=BG+S.PuttingU=LH in (13), we get(14)MUH+DU+KL=BG+S,or(15)Mu1,Mu2,…,Muph11h12h13⋯h1ph21h22h23⋯h2p0h32h33⋯h3p⋮⋮⋮⋱⋮000hp,p−1hpp+Du1,Du2,…,Dup+Kl1,Kl2,…,Klp=0¯,0¯,…,0¯,Bg1,Bg2+s1,s2,…,sp.SinceU=LH, then(16)ui=∑j=1i+1hj,ilj,fori=1,2,…,p−1.Bothl1,l2,…,lp, u1,u2,…,up, and s1,s2,…,sp are columns of L, U, and S, respectively. G=0¯,0¯,…,0¯,g1,g2 is a n×p real matrix, where 0¯ is the zero vector and g1 and g2 are the unknown vectors. From (15) and (16), we design Algorithm 3.Algorithm 3: The proposed algorithm for MLH2 + DLH + KL = BG + S.
Step1
Choosel1 and u1 arbitrarily.
For
i
=
1,2
,
…
,
p
−
2 do
l
i
+
1
=
1
/
h
i
+
1
,
i
u
i
−
∑
j
=
1
i
h
j
i
l
j
u
i
+
1
=
−
M
−
1
/
h
i
+
1
,
i
D
u
i
+
∑
j
=
1
i
h
j
i
M
u
j
+
K
l
i
−
s
i
Step 2
Last column ofU=LH is up=∑j=1phj,plj and
l
p
=
1
/
h
p
,
p
−
1
u
p
−
1
−
∑
j
=
1
p
−
1
h
j
p
−
1
l
j
,
Step 3
Computeg1 and g2 for
B
g
1
=
∑
j
=
1
p
h
j
,
p
−
1
M
u
j
+
D
u
p
−
1
+
K
l
p
−
1
−
s
p
−
1
,
B
g
2
=
∑
j
=
1
p
h
j
,
p
M
u
j
+
D
u
p
+
K
l
p
−
s
p
.Theorem 2.
The solution of matrix equation (12) is V=LXQT and W=GXQT, where M,D,K,B∈ℝn×n,R∈ℝn×p, and F∈ℝp×p are the known matrices, and the matrix X is generated as in Lemma 1.Proof.
Matrix equation (12) can be rewritten in the Hessenberg form as follows:(17)MVQQTFQQTFQ+DVQQTFQ+KVQ=BWQ+RQ.
That is(18)MV^H2+DV^H+KV^=BW^+R˜,where W^=WQ and V^=VQ are to be determined, while H=QTFQ∈ℝp×p is an unreduced upper Hessenberg matrix, R˜=RQ, and Q∈ℝp×p is an orthogonal similarity transformation. The main idea is to find a matrix L and matrix G for a new matrix equation (13) as shown in Algorithm 3, where S=R˜X−1 is known as n×p real matrix while the matrix X∈ℝp×p is generated by (6). Multiply matrix equation (13) by X; then,(19)MLH2X+DLHX+KLX=BGX+SX.
By using Lemma1 and assuming that V^=LX, W^=GX, and S=R˜X−1 we have(20)MV^H2+DV^H+KV^=BW^+R.˜
We then recover the original problem via the relationsV=V^QT, W=W^QT, and F=QHQT; then, the solution of (12) is V=LXQT and W=GXQT (see Algorithm 4).Algorithm 4: The proposed algorithm for MVF2+DVF+KV=BW+R.
Input: Matrices M,D,K,B∈ℝn×n,R∈ℝn×p and F∈ℝp×p.
Output: Matrices V and W.
Assumptions: detM≠0, detF≠0, detB≠0 and X is nonsingular matrix as shown in [19] and eigenvalues of matrix F must be distinct.
Step 1: Reduce F to an unreduced upper Hessenberg H=QTFQ∈ℝp×p. Let Q be an orthogonal matrix.
Step 2: Construct the matrix X∈ℝp×p generated by (6).
Step 3: Compute the matrix S∈ℝn×p by solving SX=RQ.
Step 4: Construct the matrices L and G as shown in Algorithm 3.
Step 5: Compute V=LXQT and W=GXQT.


## 4. Numerical Examples

In this section, we present two numerical examples to illustrate the application of our proposed method.Example 1.
We solve first-order GSME (3) where A,E,B∈Rn×n and F∈Rp×p are random matrices. The accuracy of the proposed method is reported for different values of n, when p=2, and for different values of p, when n=10, as in Table 1.Table 1
The accuracy error for Algorithm2.
n
‖
A
V
+
B
W
−
E
V
F
−
R
‖
2
p
‖
A
V
+
B
W
−
E
V
F
−
R
‖
2
6
1.2437
×
10
−
14
2
8.0572
×
10
−
15
10
8.0572
×
10
−
15
4
3.7550
×
10
−
12
100
2.2609
×
10
−
12
6
1.5518
×
10
−
9
1000
2.8632
×
10
−
9
8
1.5072
×
10
−
5Example 2.
We solve the second-order GSME (4) where M,D,K,B∈Rn×n and F∈Rp×p are random matrices. The accuracy of the proposed method is reported for different values of n, when p=2, and for different values of p, when n=10, as in Table 2.Table 2
The accuracy error for Algorithm4.
n
‖
M
V
F
2
+
D
V
F
+
K
V
−
B
W
−
R
‖
2
p
‖
M
V
F
2
+
D
V
F
+
K
V
−
B
W
−
R
‖
2
6
4.8449
×
10
−
15
2
9.9654
×
10
−
15
10
9.9654
×
10
−
15
4
8.6627
×
10
−
13
100
1.0817
×
10
−
12
6
4.1397
×
10
−
11
1000
1.0817
×
10
−
12
8
4.0780
×
10
−
8


## 5. Discussion

The accuracy of the proposed methods is remarkably dependent onp. If p is too large, one of the entries hi+1,i of H may have a tendency to be zero, which affects singularity of the X matrix. Thus, the smaller the value of p, the greater the precision. In previous studies of GSME AV+BW=EVF+R [12–15] and MVF2+DVF+KV=BW+R [16], the working hypotheses that size n of known matrices are very small. However, in our method, n is very large.


## 6. Conclusion

In this study, the solution of GSMEAV+BW=EVF+R and MVF2+DVF+KV=BW+R, where A,B,E,M,D,K,R, and F are arbitrary real known matrices and V and W are the matrices to be determined, is investigated. With the help of orthogonal similarity transformation and reduction to Hessenberg form, some good results are obtained. The proposed techniques are tested by solving two test problems where the accuracy is seen to be highly remarkable.


## 7. Open Problem

Extend the Hessenberg method to solve Sylvester quaternion matrix equation [20] and coupled matrix equation [21].



---

*Source: 1549520-2020-03-31.xml*