# The Algebraic Riccati Matrix Equation for Eigendecomposition of Canonical Forms

Authors: M. Nouri; S. Talatahari
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The algebraic Riccati matrix equation is used for eigendecomposition of special structured matrices. This is achieved by similarity transformation and then using the algebraic Riccati matrix equation to the triangulation of matrices. The process is the decomposition of matrices into small and specially structured submatrices with low dimensions for easy finding of eigenpairs. Here, we show that previous canonical forms I, II, III, and so on are special cases of the presented method. Numerical and structural examples are included to show the efficiency of the present method.


---

## Body

## 1. Introduction

Eigenvalue problem is a special category for studying of engineering problems. As an example, the eigenvalues correspond to natural frequencies in vibration of systems and buckling loads in the stability analysis of structures [1–4]. General methods are available in the literature for eigenvalue problems [5–7]. Well established techniques exist for the eigensolution of bilateral symmetry in the work of Kaveh and Sayarinejad [8, 9] and Kaveh and Salimbahrami [10]. Other eigensolution methods are also available for cyclically symmetric structures in Thomas [11], Williams [12, 13], Aghayere [14], Kaveh and Rahami [15–17], and Kaveh and Nemati [18]. The history of the developments in symmetry and the application of different mathematical tools can be found in the excellent review paper of Kangwai et al. [19]. Canonical forms are also studied in the past decade for eigensolution of symmetric structural mathematical modeling, [8–10, 18].The algebraic Riccati equation has been widely used in control system syntheses [20, 21], especially in optimal control [22–24]. As a solution of this equation, it may not be unique [25]. The existence conditions of solutions have been considerably investigated by [26]. A review of application and solution of the algebraic Riccati matrix equation can be found in [27, 28].In this paper, we introduce a general solution form of canonical and symmetry forms I, II, III, and so on which presented in [8–10, 29–34]. This is achieved via using similarity transformations and the solutions of the algebraic Riccati matrix equation.


## 2. Basic Definitions of Graph Theory

### 2.1. Definitions from Graph Theory

A graphS(N,E) consists of a set of elements, N(S), called nodes and a set of elements, E(S), called members (edges), together with a relation of incidence which associates two distinct nodes with each member, known as its ends. Two nodes of a graph are called adjacent if these nodes are the end nodes of a member. A member is called incident with a node if it is an end node of the member [17]. The degree of a node is the number of edges incident with the node.


### 2.2. Matrices Associated with a Graph

LetS be a graph with N nodes. The adjacency matrix A is an N×N matrix in which the entry in row i and column j is 1 if node ni is adjacent to nj and is zero otherwise. This matrix is symmetric, and the row sums of A are the degrees of nodes of S. The Laplacian matrix L of graph S is defined as
(1)L=D-A,
where D is a diagonal matrix in which the ith diagonal entry is equal to the degree of node i. The adjacency and Laplacian matrices are important matrices in the theory of graphs, and their eigenvalues and eigenvectors form the foundation of a branch of mathematics known as the algebraic graph theory [18–20].


## 2.1. Definitions from Graph Theory

A graphS(N,E) consists of a set of elements, N(S), called nodes and a set of elements, E(S), called members (edges), together with a relation of incidence which associates two distinct nodes with each member, known as its ends. Two nodes of a graph are called adjacent if these nodes are the end nodes of a member. A member is called incident with a node if it is an end node of the member [17]. The degree of a node is the number of edges incident with the node.


## 2.2. Matrices Associated with a Graph

LetS be a graph with N nodes. The adjacency matrix A is an N×N matrix in which the entry in row i and column j is 1 if node ni is adjacent to nj and is zero otherwise. This matrix is symmetric, and the row sums of A are the degrees of nodes of S. The Laplacian matrix L of graph S is defined as
(1)L=D-A,
where D is a diagonal matrix in which the ith diagonal entry is equal to the degree of node i. The adjacency and Laplacian matrices are important matrices in the theory of graphs, and their eigenvalues and eigenvectors form the foundation of a branch of mathematics known as the algebraic graph theory [18–20].


## 3. Bisymmetric and Persymmetric Matrices

### 3.1. Bisymmetric Matrix

In mathematics, a bisymmetric matrix is a square matrix that is, symmetric about both of its main diagonals. More precisely, ann×n matrix M is bisymmetric if and only if it satisfies M=MT and M×S=S×M, where S is the n×n exchange matrix:
(2)S=[11⋰1].


### 3.2. Persymmetric Matrix

In mathematics, a persymmetric matrix may refer to a square matrix which is symmetric in the northeast-to-southwest diagonal or a square matrix such that the values on each line perpendicular to the main diagonal are the same for a given line. IfB is a persymmetric matrix:
(3)BT=SBS,
where S is the exchange matrix.


## 3.1. Bisymmetric Matrix

In mathematics, a bisymmetric matrix is a square matrix that is, symmetric about both of its main diagonals. More precisely, ann×n matrix M is bisymmetric if and only if it satisfies M=MT and M×S=S×M, where S is the n×n exchange matrix:
(2)S=[11⋰1].


## 3.2. Persymmetric Matrix

In mathematics, a persymmetric matrix may refer to a square matrix which is symmetric in the northeast-to-southwest diagonal or a square matrix such that the values on each line perpendicular to the main diagonal are the same for a given line. IfB is a persymmetric matrix:
(3)BT=SBS,
where S is the exchange matrix.


## 4. Similarity Transformation of Matrices

A complex scalarλi is called an eigenvalue of the square matrix An×n if a nonzero vector vi exists such that Avi=λivi. The vector vi is called an eigenvector of A associated with λi. The set of eigenvalues of A is called the spectrum of A. A scalar λi is an eigenvalue of A if and only if det(A-λiI)=0. That is true if and only if λi is a root of the characteristic polynomial. Two matrices A and B are said to be similar if there is a nonsingular matrix U such that
(4)B=U-1AU.
The mapping A→B is called a similarity transformation. Using (3)–(5), it can be shown that similarity transformations preserve the eigenvalues of matrices:
(5)Avi=λvi,(6)U-1AUU-1vi=U-1λvi.
By substituting B=U-1AU and yi=U-1vi, we will have
(7)Byi=λyi.
Equation (9) which is a standard representation of eigenproblems means that λi are also the eigenvalues of the matrix B. This transformation is used in the next sections for block diagonalization of adjacency and the Laplacian matrices with a special pattern.


## 5. The Algebraic Riccati Matrix Equation

The matrix equation(8)XBX+XA-DX-C=0
is called algebraic Riccati matrix equation. In this equation, A,B,C, and D, with appropriate dimensions, are known matrices, and X should be determined. Solutions of the algebraic Riccati matrix equation (6) are important in many applications. Potter [20] has solved a special case of the equation, but the closed form of the problem has not been solved. Additional particular solutions are obtained by the decomposition of C into a sum of three matrices. Unfortunately, there is no procedure for determining every permissible decomposition of C. This solution of the Riccati equation by the decomposition of C is as follows:
(9)XBX=M,XA=N,-DX=P,M+N+P=C.


## 6. Decomposition of Specially Structured Matrix

Consider the following blocked matrix:(10)L=[ABCD],
where A,D∈Rn×n. It is desired to find a similarity transformation form of L. We use matrix U as
(11)U=[I0XI].
It is obvious that
(12)U-1=[I0-XI].
Eigenvalues of L can be determined as
(13)Lvi=λvi.
Similarity transformation of L can be written as
(14)K=U-1LU,(15)K=[I0-XI][ABCD][I0XI],
expanding and then the simplification of (15) yields
(16)K=[A+BXB-XBX-XA+DX+CD-XB].If the algebraic Riccati equation,-XBX-XA+DX+C=0, can be solved, then we can decompose (10) as
(17)[A+BXB0D-XB].So, the eigenvalues ofLcan be found as
(18)eig(L)=eig(A+BX)∪eig(D-XB).


## 7. The Algebraic Riccati Matrix Equation and Canonical Forms

If in (16), we assume X=I and
(19)B+A-D-C=0
or
(20)B+A=D+C,
then the decomposed form of (10) can be written as
(21)eig(L)=eig(A+B)∪eig(D-B).
Equation (19) is the fundamental idea behind all of the canonical and symmetry forms I, II, and so on and the augmented form of them. This means that all of the canonical and symmetry forms are a special form of (10) when A=D and C=B. The solution can be obtained by solving the algebraic Riccati equation when X=I.


## 8. Augmented Forms

The solution of the algebraic matrix equation isX=I, when the submatrices of L are satisfied by the following condition:
(22)B+A=D+C.
We can add matrices in the both sides of (20) while the decomposed form is stable
(23)B±m+A±n=D±m+C±n.
So, eigenvalues of L and K are the same:
(24)L=[ABCD],K=[A±nB±mC±nD±m].


## 9. Decomposition of Bisymmetric Matrices

Consider bisymmetric matrixL(25)L=[ABBTA].
So, we have
(26)SBS=BT,AS=SA.
Similarity transformation of L can be written as
(27)K=[A+BXB-XBX-XA+AX+BTA-XB].
If the matrix equation -XBX-XA+AX+BT=0 can be solved, we can write the decomposed form of L. For this case, the relationship X=S satisfies in the algebraic Riccati matrix equation (27), so
(28)eig(L)=eig(A+BS)∪eig(A-SB).


## 10. Numerical Examples

Example 1.
Consider the following submatrices:(29)A=[4-12-16-12-14],B=[163856081],M=[ABBTA].
In this example, A is a symmetric, and B is a persymmetric, so we can calculate the eigenvalues of M using present method by eigenvalues of the following submatrices:
(30)eig(M)=eig(A+BS)∪eig(A-BS)=(-0.32744.000018.3274)∪(-9.13281.159813.9731).Example 2.
In this example,M is the Laplacian matrix of the following graph:
(31)
M
=
[
3
1
1
1
1
3
1
1
1
2
1
1
2
1
1
1
3
1
1
1
1
3
]
,
A
=
[
3
1
0
1
3
1
0
1
2
]
,
B
=
[
1
1
1
1
]
,
eig
(
M
)
=
eig
(
A
+
B
S
)
∪
eig
(
S
A
S
-
B
S
)
=
(
1.0968
3.1939
5.7093
)
∪
(
0.5858
2.0000
3.4142
)
.Example 3.
In this example,M is the adjacency, and the Laplacian matrix of the following graph model of a truss:
(32)
Adj
(
s
)
=
[
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
]
,
Lap
(
S
)
=
[
3
-
1
-
1
-
1
-
1
4
-
1
-
1
-
1
-
1
4
-
1
-
1
-
1
-
1
4
-
1
-
1
-
1
-
1
2
-
1
-
1
2
-
1
-
1
-
1
-
1
4
-
1
-
1
-
1
-
1
4
-
1
-
1
-
1
-
1
4
-
1
-
1
-
1
-
1
3
]
.Example 4.
In this example,M is the adjacency, and the Laplacian matrix of the following graph model of a truss:
(33)
Adj
(
s
)
=
[
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
]
,
Lap
(
s
)
=
[
3
-
1
-
1
-
1
-
1
3
-
1
-
1
-
1
4
-
1
-
1
-
1
-
1
5
-
1
-
1
-
1
-
1
-
1
2
-
1
-
1
2
-
1
-
1
-
1
-
1
-
1
5
-
1
-
1
-
1
-
1
4
-
1
-
1
-
1
3
-
1
-
1
-
1
-
1
3
]
.Example 5.
In this example,M is the adjacency, and the Laplacian, matrix of the following graph model of a truss:
(34)
Adj
(
s
)
=
[
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
]
,
LaP
(
s
)
=
[
4
-
1
-
1
-
1
-
1
-
1
3
-
1
-
1
-
1
5
-
1
-
1
-
1
-
1
-
1
-
1
3
-
1
-
1
3
-
1
-
1
-
1
-
1
-
1
-
1
5
-
1
-
1
-
1
3
-
1
-
1
-
1
-
1
-
1
4
]
.Example 6.
In this example,M is the adjacency, and the Laplacian matrix of the following graph model of a truss:(35)
Adj
(
s
)
=
[
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
]
,
Adj
(
s
)
=
[
2
-
1
-
1
-
1
5
-
1
-
1
-
1
-
1
-
1
2
-
1
-
1
-
1
5
-
1
-
1
-
1
-
1
-
1
5
-
1
-
1
-
1
-
1
-
1
-
1
4
-
1
-
1
4
-
1
-
1
-
1
-
1
-
1
-
1
5
-
1
-
1
-
1
-
1
-
1
5
-
1
-
1
-
1
2
-
1
-
1
-
1
-
1
-
1
5
-
1
-
1
-
1
2
]
.Example 7.
Consider matrixM as follows:
(36)M=[0145467982-44103112]=[ABCD]=[ABCA+B-C].
This matrix can be decomposed as
(37)eig(M)=eig(A+B)∪eig(D-B)=eig(A+B)∪eig(A-C),eig(A+B)∪eig(A-C)=eig([461115])∪eig([-8-1-63]),(-0.3107,19.3107)∪(-8.5208,3.5208).
Eigenvalues of M calculated by the decomposition method were proposed in this paper. Matrix M has a complex pattern than all of the canonical forms. So, it is obvious that canonical forms are a special form of proposed method:
(38)eig(M)=(19.3107,-8.5208,-0.3107,3.5208).Example 8.
Consider the directed graph(S) and its adjacency matrix in Figure 1.
Adjacency matrix of the graph(S) is written as
(39)Adj(S)=[010000001110100010000010010101000110]=[ABCD].
This matrix can be decomposed as
(40)eig(Adj(S))=eig(A+B)∪eig(D-B)=eig(A+B)∪eig(A-C),eig(A+B)∪eig(A-C)=eig([010111110])∪eig([010111110]),[2.1479-0.5739+0.3690i-0.5739-0.3690i]∪[0.7549-0.8774+0.7449i-0.8774-0.7449i]→eig(Adj(S))=[2.14790.7549-0.8774+0.7449i-0.8774-0.7449i-0.5739+0.3690i-0.5739-0.3690i].
The decomposed and healed form of graph (S) is presented in Figure 1(b). It is noted that the graph (S) has more complex pattern than those decomposable by known canonical forms. It is obvious that previous canonical forms I, II, and so forth are unable to decompose graph (S).(a) Graph (S) and (b) decomposed form of graph (S).
(a)
(b)


## 11. Concluding Remarks

The main contribution of this paper is to generalize some previously developed canonical and symmetry forms and to provide a powerful means for decomposing matrices. This aim is achieved by the similarity transformation and by using the algebraic Riccati matrix equation. In this paper, we showed that the canonical forms defined in the previously works are special cases of the proposed method. The present method simplifies the numerical operations required for calculating the eigenvalues and eigenvectors of the corresponding matrices. Here, some useful methods are developed for the application of canonical and symmetry forms. Applications of the present methods can be used to solve different problems such as calculating the natural frequencies of vibrating systems and finding buckling loads of structures. It can also be employed in other fields of engineering where eigenvalues and eigenvectors of matrices are required.



---

*Source: 176389-2013-03-19.xml*