# Structural Controllability of Discrete-Time Linear Control Systems with Time-Delay: A Delay Node Inserting Approach

Authors: Ailing Qi; Xuewei Ju; Qing Zhang; Zengqiang Chen
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

This paper is concerned with the structural controllability analysis for discrete-time linear control systems with time-delay. By adding virtual delay nodes, the linear systems with time-delay are transformed into corresponding linear systems without time-delay, and the structural controllability of them is equivalent. That is to say, the time-delay does not affect or change the controllability of the systems. Several examples are also presented to illustrate the theoretical results.


---

## Body

## 1. Introduction

Controllability has been one of the fundamental concepts in modern control theory and has played an essential role in its development because of the broad applications. Controllability in the classical sense refers to the complete controllability which means that it is possible to steer control systems from an arbitrary initial state to an arbitrary final state using the set of unconstrained admissible controls. In practice, admissible controls are always required to satisfy certain additional constraints. The controllability for linear dynamical systems with constrained controls has also been studied; see [1–3]. The problem of controllability with unconstrained controls for both linear and nonlinear systems has been considered in various ways; see [4–8] and the references therein.In this paper, we will consider the problem of structural controllability on unconstrained values of admissible controls. The concept of structural controllability was introduced by Lin in 1974 to study the controllability of linear systems, and it was extended to other systems, such as complex networks and multiagent systems. Roughly speaking, structural controllability generally means that, by adjusting the free parameters of the structured matrix, the control system is completely controllable. Controllability is important in the solution of many control problems, yet the determination of controllability indices, for example, is a particularly ill-posed computational problem as is the problem of checking the controllability of an uncontrollable system. Structural controllability, on the other hand, is a property that is as useful as traditional controllability and can be determined precisely by a computer. The structural controllability is a generalization of traditional controllability concept for linear systems and is purely based on the graphic topologies among state and input vertices. It is now a fundamental tool to study the controllability and enables us to understand the control systems.The necessary and sufficient conditions of structural controllability were constructed by Lin in [9] from the graphical point of view. Since then, much work has been done on the structural controllability of linear systems. For example, Shields and Pearson extended Lin’s results on structural controllability of single-input linear systems to multi-input linear systems [10]. For linear time-varying systems, the structural properties were defined as the strong structural controllability; for the related research, see [11, 12]. Recently, in view of switched linear systems, the structural controllability was investigated by Liu et al. [13].It is well recognized that time-delay is often encountered in physical and biological systems. Time-delay phenomenon may occur naturally because of the physical characteristics of information transmitting and diversity of signals, as well as the bandwidth of communication channels. Systems with time-delay are more difficult to handle in engineering since the controllability matrices are usually complex.Studying the linear delayed systems has become an important topic in control theory and many researchers have devoted themselves to the controllability analysis for the delayed systems. For example, a data-based method is used to analyze the controllability of discrete-time linear delayed system by Liu et al. [14]. The controllability and observability of linear time-delay differential equations have been studied in [15, 16]. Two sufficient conditions were recently reported in Ji et al. [17] with respect to the controllability of multiagent systems with single time-delay. The results were then extended to multiagent systems with time-delay in state and control [18] and switching topology [19].In spite of this progress, there is less work concerned with the structural controllability of linear systems with time-delay. This paper is devoted to the structural controllability analysis for discrete-time linear delayed systems. By adding virtual delay nodes, the linear systems with time-delay are transformed into corresponding linear systems without time-delay; the necessary and sufficient conditions with respect to the structural controllability of linear delayed systems are obtained.This paper is organized as follows. In Section2, some basic definitions and preliminary results are presented. We introduce the discrete-time linear delayed systems in Section 3 and, by adding delay nodes, the linear systems with time-delay are transformed into corresponding linear systems without time-delay and the main result of this paper is obtained. Several examples are also presented to illustrate the theoretical results in Section 4. The paper concludes in Section 5 with a summary and the possible future research directions.


## 2. Preliminaries

This section gives some basic definitions and preliminary results.


### 2.1. The Representation Graph of the Linear Systems

Consider the following discrete-time linear control system:(1)
x
k
+
1
=
A
x
k
+
B
u
k
,where state x and input u take their values in R
n and R
r, respectively. Matrixes A
=
(
a
i
j
)
n
×
n and B
=
(
b
i
j
)
n
×
r are assumed to be structured matrices, which means that their elements are either fixed zeros or free parameters. For convenience in this paper, the structured system (1) is represented as matrix pair (
A
,
B
).The matrix pair(
A
¯
,
B
¯
) has the same structure as the pair (
A
,
B
) of the same dimensions if for every fixed (zero) entry of matrix (
A
¯
,
B
¯
) the corresponding entry of matrix (
A
,
B
) is also fixed (zero) and for every fixed (zero) entry of matrix (
A
,
B
) the corresponding entry of matrix (
A
¯
,
B
¯
) is also fixed (zero).The structured system(
A
,
B
) can be described by a directed graph (Lin [9]).The representation graph of structured system (1) is a directed graph G, with vertex set V
=
X
∪
U, where X
=
{
x
1
,
x
2
,
…
,
x
n
} is called state vertex set and U
=
{
u
1
,
u
2
,
…
,
u
r
} is called input vertex set, and edge set I
=
I
U
X
∪
I
X
X, where (2)
I
U
X
=
u
i
,
x
j
∥
b
j
i
≠
0
,
1
≤
i
≤
r
,
1
≤
j
≤
nis the oriented edges between inputs and states, and (3)
I
X
X
=
x
i
,
x
j
∥
a
j
i
≠
0
,
1
≤
i
≤
n
,
1
≤
j
≤
nis the oriented edges between states defined by the interconnection matrices A and B above. This directed graph G is also called the graph of matrix pair (
A
,
B
) and denoted by G
(
A
,
B
).Definition 1 ([9] (stem)).
An alternating sequence of distinct vertices and oriented edges is called a directed path, in which the terminal node of any edge never coincides with its initial node or the initial or the terminal nodes of the former edges. A stem is a directed path in the state vertex setX, which begins in the input vertex set U.Definition 2 ([9] (accessibility)).
A vertex (other than the input vertices) is called nonaccessible if and only if there is no possibility of reaching this vertex through any stem of graphG.Definition 3 ([9] (dilation)).
Consider one vertex setS formed by the vertices from the state vertices set X and determine another vertex set T
(
S
), which contains all vertices v with the property that there exists an oriented edge from v to one vertex in S. Then, graph G contains a “dilation” if and only if there exist at least a set S of k vertices in the vertex set of the graph such that there are no more than k
-
1 vertices in T
(
S
).


### 2.2. Controllability and Structural Controllability

It is well known that for delayed control systems generally two types of controllability are considered: absolute controllability and relative controllability; see paper [3]. In this paper, we will consider the relative controllability under general assumption on unconstrained values of admissible controls. The definitions are as follows.Definition 4 (see [5]).
The linear control system (1) is said to be (completely) controllable if for any initial state x
(
0
) and any terminal state x
f there exist a positive integer k and a sequence of controls u
(
0
)
,
…
,
u
(
k
-
1
) such that x
(
k
)
=
x
f.For the linear system (1), let W
=
[
B
,
A
B
,
…
,
A
n
-
1
B
], and we have the following complete controllability criterion (Kalman [6]).Lemma 5.
The linear control system (1) is controllable if and only if r
a
n
k
[
W
]
=
n.Definition 6 (see [9]).
The linear control system (1) given by its structured matrices (
A
,
B
) is said to be structurally controllable if and only if there exists a matrix pair (
A
¯
,
B
¯
) having the same structure as the pair (
A
,
B
) such that the corresponding structured system (
A
¯
,
B
¯
) is completely controllable.The following lemma characterizes the structural controllability for the linear structured system (1) (Liu et al. [13]).Lemma 7.
The linear structured system(
A
,
B
) is structurally controllable if and only if its representation graph satisfies that(i)
there is no nonaccessible vertex inG
(
A
,
B
),
(ii)
there is no “dilation” inG
(
A
,
B
).


## 2.1. The Representation Graph of the Linear Systems

Consider the following discrete-time linear control system:(1)
x
k
+
1
=
A
x
k
+
B
u
k
,where state x and input u take their values in R
n and R
r, respectively. Matrixes A
=
(
a
i
j
)
n
×
n and B
=
(
b
i
j
)
n
×
r are assumed to be structured matrices, which means that their elements are either fixed zeros or free parameters. For convenience in this paper, the structured system (1) is represented as matrix pair (
A
,
B
).The matrix pair(
A
¯
,
B
¯
) has the same structure as the pair (
A
,
B
) of the same dimensions if for every fixed (zero) entry of matrix (
A
¯
,
B
¯
) the corresponding entry of matrix (
A
,
B
) is also fixed (zero) and for every fixed (zero) entry of matrix (
A
,
B
) the corresponding entry of matrix (
A
¯
,
B
¯
) is also fixed (zero).The structured system(
A
,
B
) can be described by a directed graph (Lin [9]).The representation graph of structured system (1) is a directed graph G, with vertex set V
=
X
∪
U, where X
=
{
x
1
,
x
2
,
…
,
x
n
} is called state vertex set and U
=
{
u
1
,
u
2
,
…
,
u
r
} is called input vertex set, and edge set I
=
I
U
X
∪
I
X
X, where (2)
I
U
X
=
u
i
,
x
j
∥
b
j
i
≠
0
,
1
≤
i
≤
r
,
1
≤
j
≤
nis the oriented edges between inputs and states, and (3)
I
X
X
=
x
i
,
x
j
∥
a
j
i
≠
0
,
1
≤
i
≤
n
,
1
≤
j
≤
nis the oriented edges between states defined by the interconnection matrices A and B above. This directed graph G is also called the graph of matrix pair (
A
,
B
) and denoted by G
(
A
,
B
).Definition 1 ([9] (stem)).
An alternating sequence of distinct vertices and oriented edges is called a directed path, in which the terminal node of any edge never coincides with its initial node or the initial or the terminal nodes of the former edges. A stem is a directed path in the state vertex setX, which begins in the input vertex set U.Definition 2 ([9] (accessibility)).
A vertex (other than the input vertices) is called nonaccessible if and only if there is no possibility of reaching this vertex through any stem of graphG.Definition 3 ([9] (dilation)).
Consider one vertex setS formed by the vertices from the state vertices set X and determine another vertex set T
(
S
), which contains all vertices v with the property that there exists an oriented edge from v to one vertex in S. Then, graph G contains a “dilation” if and only if there exist at least a set S of k vertices in the vertex set of the graph such that there are no more than k
-
1 vertices in T
(
S
).


## 2.2. Controllability and Structural Controllability

It is well known that for delayed control systems generally two types of controllability are considered: absolute controllability and relative controllability; see paper [3]. In this paper, we will consider the relative controllability under general assumption on unconstrained values of admissible controls. The definitions are as follows.Definition 4 (see [5]).
The linear control system (1) is said to be (completely) controllable if for any initial state x
(
0
) and any terminal state x
f there exist a positive integer k and a sequence of controls u
(
0
)
,
…
,
u
(
k
-
1
) such that x
(
k
)
=
x
f.For the linear system (1), let W
=
[
B
,
A
B
,
…
,
A
n
-
1
B
], and we have the following complete controllability criterion (Kalman [6]).Lemma 5.
The linear control system (1) is controllable if and only if r
a
n
k
[
W
]
=
n.Definition 6 (see [9]).
The linear control system (1) given by its structured matrices (
A
,
B
) is said to be structurally controllable if and only if there exists a matrix pair (
A
¯
,
B
¯
) having the same structure as the pair (
A
,
B
) such that the corresponding structured system (
A
¯
,
B
¯
) is completely controllable.The following lemma characterizes the structural controllability for the linear structured system (1) (Liu et al. [13]).Lemma 7.
The linear structured system(
A
,
B
) is structurally controllable if and only if its representation graph satisfies that(i)
there is no nonaccessible vertex inG
(
A
,
B
),
(ii)
there is no “dilation” inG
(
A
,
B
).


## 3. Main Results

### 3.1. Discrete-Time Linear Systems with Time-Delay

Consider the following linear control systems with time-delay in state:(4)
x
i
k
+
1
=
∑
j
=
1
n
a
i
j
x
j
k
-
τ
i
j
+
∑
j
=
1
r
b
i
j
u
j
k
,
i
=
1,2
,
…
,
n
,where x
=
[
x
1
,
x
2
,
…
,
x
n
]
T
∈
R
n is the state vector and u
=
[
u
1
,
u
2
,
…
,
u
r
]
T
∈
R
r is the control input vector. Matrices A
=
(
a
i
j
)
n
×
n and B
=
(
b
i
j
)
n
×
r are assumed to be structured matrices. 0
≤
τ
i
j
≤
b with bounded maximum delay b and each directed edge (
x
i
,
x
j
) experiences a fixed delay τ
i
j in the sense that each message leaving state node x
i takes τ
i
j iterations to reach x
j.Definition 8.
The linear delayed system (4) given by its structured matrices (
A
,
B
) is said to be structurally controllable if and only if there exists a matrix pair (
A
¯
,
B
¯
) has the same structure as the pair (
A
,
B
) such that the corresponding delayed system (4) given by its structured matrices (
A
¯
,
B
¯
) is completely controllable.By inserting delays on edges, the linear delayed system is transformed into a corresponding linear system without time-delay.For every directed edge(
x
i
,
x
j
) with time-delay τ
i
j, we want to add τ
i
j nodes d
1
i
j
,
d
2
i
j
,
…
,
d
τ
i
j
i
j on the edge, replace (
x
i
,
x
j
) by a delay chain d
1
i
j
,
d
2
i
j
,
…
,
d
τ
i
j
i
j, and reroute all messages from x
i to x
j through that chain. Instead, x
i sends its message to delay node x
1
i
j with the weight of the message being the same as the one that would be used to send a message from x
i to x
j directly without delay; after that, all delay nodes just forward information until the destination node x
j is reached (see Figure 1).Figure 1
(a) A directed graph with 3 state nodes. (b) The directed graph when we add a delay of 4 on the edge(
x
1
,
x
2
).
(a)
(b)Noteτ
=
τ
11
+
⋯
+
τ
1
n
+
τ
21
+
⋯
+
τ
21
+
⋯
+
τ
n
1
+
⋯
+
τ
n
n, all the numbers of time-delays. Let (5)
x
~
=
x
1
,
…
,
x
n
,
d
1
11
,
…
,
d
τ
11
11
,
…
,
d
1
1
n
,
…
,
d
τ
1
n
1
n
,
…
,
d
1
n
1
,
…
,
d
τ
n
1
n
1
,
…
,
d
1
n
n
,
…
,
d
τ
n
n
n
n
T
;then, x
~
∈
R
n
+
τ.Thus, the linear delayed system (4) is equivalent to the following linear system without time-delay:(6)
x
~
k
+
1
=
A
x
~
k
+
B
u
k
,where A
∈
R
(
n
+
τ
)
×
(
n
+
τ
) and B
∈
R
(
n
+
τ
)
×
r are corresponding to A and B, respectively.Example 9.
Consider a very simple example. Without delays we define(7)
A
=
2
3
1
3
0
1
3
1
3
1
3
0
1
3
2
3
,
B
=
1
0
0
.Assume that the directed edge (
x
1
,
x
2
) experiences a fixed delay 4 in the sense that the message leaving state node x
1 takes 4 iterations to reach state node x
2. Then, by inserting 4 delay nodes on the edge (
x
1
,
x
2
), replace (
x
1
,
x
2
) by a delay chain d
1, d
2, d
3, d
4 and reroute all messages from x
1 to x
2 through that chain; that is, x
1 sends its message to delay node d
1 with the weight being 2
/
3, and then d
1 sends its message to delay node d
2, d
2 sends its message to delay node d
3, d
3 sends its message to delay node d
4, and d
4 sends its message to state node x
2 all with the weight being 1. Then, the linear control system with delays is transformed into a linear system without time-delay with the corresponding structured matrices given by (8)
A
=
2
3
1
3
0
0
0
0
0
0
1
3
1
3
0
0
0
1
0
1
3
2
3
0
0
0
0
1
3
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
,
B
=
1
0
0
0
0
0
0
.The directed graphs G
(
A
,
B
) and G
(
A
,
B
) can be seen in Figure 1.


### 3.2. Structural Controllability Analysis

As mentioned above, the structural controllability of the linear delayed system (4) is in consensus with that of the linear system (6) without time-delay. However, some parameters of the structured matrix A are not adjusted; the weight of the edge from one delay node to another node is fixed number 1 (see Figure 1). Therefore, it has failed to apply Lemma 7 to characterize the structural controllability of the linear system (6). Thus, we construct the following linear structured system:(9)
x
^
k
+
1
=
A
x
^
k
+
B
u
k
,where x
^
=
[
x
1
,
…
,
x
n
,
x
n
+
1
,
…
,
x
n
+
τ
]
T
∈
R
n
+
τ and matrices A and B are structured matrices such that (
A
,
B
) have the same structure as (
A
,
B
).For example, we construct a linear structured system corresponding to the linear control system described by a directed graph in Figure1 with the structured matrices A and B given by (10)
A
=
α
11
α
12
0
0
0
0
0
0
α
22
α
23
0
0
0
α
27
0
α
32
α
33
0
0
0
0
α
41
0
0
0
0
0
0
0
0
0
α
54
0
0
0
0
0
0
0
α
65
0
0
0
0
0
0
0
α
76
0
,
B
=
β
1
0
0
0
0
0
0with α
i
j
(
1
≤
i
,
j
≤
7
) and β
1 being nonzero free parameters.In fact, the structure of the representation graphG
(
A
,
B
) is the same as graph G
(
A
,
B
), only denoting the delay nodes of G
(
A
,
B
) as ordinary nodes is graph G
(
A
,
B
). On the other hand, graph G
(
A
,
B
) can also be seen as the expansion of G
(
A
,
B
).The following theorems build the equivalence of the structural controllability of the three systems: system (1), system (4), and system (9).Theorem 10.
The linear system (6) is structurally controllable if and only if the linear system (9) is structurally controllable.Proof.
The necessity is obvious; we then prove the sufficiency. Assume that the linear system (9) is structurally controllable; that is, there exists a matrix pair (
A
¯
,
B
¯
) having the same structure as (
A
,
B
) and satisfying (11)
rank
⁡
B
¯
,
A
¯
B
¯
,
…
,
A
¯
n
-
1
B
¯
T
=
n
+
τ
.
In the following, we will adjust some parameters ofA
¯, wihch is the corresponding parameters to fixed numbers 1 of A.
Firstly, we analyze the characteristics of columns ofA. It is easy to conclude from graph G
(
A
,
B
) that the weight of edge from each delay node is number 1. Then, there is one element 1 in every column from the n
+
1 column to the n
+
τ column, and there is only one non-zero parameter 1 in every column from the n
+
1 column to the n
+
τ column since there is only one edge from each delay node. These elements 1 are either below the diagonal or above the diagonal. If they are below the diagonal, they will be in the form of inclined diagonal; else, if they are above the diagonal, they are in the first n rows (see Figure 1).
Then, from then
+
τ column (the last column), we carry the elementary transformation on the matrix A
¯. In the n
+
τ column of the matrix A, there is only one element that is not zero, and the nonzero element is fixed number 1. Since A
¯ have the same structure as A, the corresponding element in the n
+
τ column of A
¯ is also nonzero, assuming that he value of this element is σ
n
+
τ. Our goal is to put this number σ
n
+
τ into number 1. We can do it as we just need to multiply the n
+
τ column of A
¯ by 1
/
σ
n
+
τ. For the sake of calculating the rank of the controllability matrix, we then multiply the n
+
τ row of A
¯ by σ
n
+
τ.
Next, assume that the single nonzero element in then
+
τ
-
1 column of A
¯ is σ
n
+
τ
-
1. We then multiply the n
+
τ
-
1 column of A
¯ by 1
/
σ
n
+
τ
-
1 and multiply the n
+
τ
-
1 row of A
¯ by σ
n
+
τ
-
1.
Continue to do elementary transformation according to the rules, multiply then
+
τ
-
j column by 1
/
σ
n
+
τ
-
j, and multiply the n
+
τ
-
j row by σ
n
+
τ
-
j, until the n
+
1 column of A
¯. Due to the features of matrix A, The column number of the nonzero element in the n
+
k
(
1
≤
k
≤
τ
) row of A
¯ is less than n
+
k, so multiply the n
+
k row by σ
n
+
k which changes the elements in the first n
+
k columns; the elements after n
+
k columns having been transferred to 1 are not subject to change.
In this way, matrixA
¯ is transformed to a matrix A
¯ with the invertible matrix P, the product of a series of elementary matrix, such that A
¯
=
P
-
1
A
¯
P.
LetB
~
=
P
-
1
B
~
P. Here the matrix B
~
=
(
B
¯
,
0
)
∈
R
(
n
+
τ
)
×
(
n
+
τ
) is constituted by B
¯ as sub-block matrix. Then B
~ can be expressed in the form of a partitioned matrix, that is B
~
=
(
B
¯
,
0
) with the first r columns denoted by B
¯. We thus obtained a pair of matrix (
A
¯
,
B
¯
) having the same structure as the matrix pair (
A
,
B
), such that(12)
rank
⁡
B
¯
,
A
¯
B
¯
,
…
,
A
¯
n
-
1
B
¯
T
=
rank
⁡
B
~
,
A
¯
B
~
,
…
,
A
¯
n
-
1
B
~
T
=
rank
⁡
P
-
1
B
~
P
,
P
-
1
A
¯
B
~
P
,
…
,
P
-
1
A
¯
n
-
1
B
~
P
T
=
rank
⁡
B
~
,
A
¯
B
~
,
…
,
A
¯
n
-
1
B
~
T
=
rank
⁡
B
¯
,
A
¯
B
¯
,
…
,
A
¯
n
-
1
B
¯
T
=
n
+
τ
,which implies the structural controllability of system (6). This completes the proof.The theorem above reveals that the structural controllability of the time-delayed system (4) is consistent with the expansion system (9) without time-delay. Next, we will show the equivalence of the structural controllability between system (1) and the expansion system (9).Theorem 11.
The linear system (1) is structurally controllable if and only if the linear system (9) is structurally controllable.Proof.
The proof of the theorem mainly used the results of Lemma7. Prove the necessity first. Suppose that the linear system (9) is not structurally controllable; it means that there is nonaccessible vertex or there is “dilation” in G
(
A
,
B
). Since there is no difference between graph G
(
A
,
B
) and graph G
(
A
,
B
) from the view of graph theory, therefore there is nonaccessible vertex or there is “dilation” in G
(
A
,
B
).
In the first case, there is nonaccessible vertex inG
(
A
,
B
). If the nonaccessible vertex is the adding delayed vertex d
k
τ
i
j, the k delayed vertex adding on the edge (
x
i
,
x
j
), then the state vertex x
i is a nonaccessible vertex. If the nonaccessible vertex is state vertex, then there exists the corresponding nonaccessible state vertex in G
(
A
,
B
). This is because if the state vertex x
i and the state vertex x
j experience a delay τ
i
j, we add τ
i
j delay vertex on the edge (
x
i
,
x
j
) in the graph G
(
A
,
B
) and replace (
x
i
,
x
j
) by a delay chain; the resulting graph is G
(
A
,
B
). The state vertex in G
(
A
,
B
) is the corresponding state vertex in G
(
A
,
B
).
In the second case, there is “dilation” inG
(
A
,
B
). That is, there exist at least a set S of k vertices in the vertex set of graph G
(
A
,
B
) such that there are no more than k
-
1 vertices in T
(
S
). If there are σ
(
0
≤
σ
≤
k
) delayed vertices in set S, then the σ delayed vertices are in set T
(
S
), and there are no more than k
-
σ
-
1 state vertices in T
(
S
). This implies there exist a corresponding set S
~ of k
-
σ vertices in the vertex set of the graph G
(
A
,
B
) such that there are no more than k
-
σ
-
1 state vertices in T
(
S
~
). Therefore, there is “dilation” in G
(
A
,
B
). By Lemma 7, the linear system (1) is not structurally controllable.
It is easy to prove the sufficiency as in the discussion above. Thus, the proof of the theorem is complete.


## 3.1. Discrete-Time Linear Systems with Time-Delay

Consider the following linear control systems with time-delay in state:(4)
x
i
k
+
1
=
∑
j
=
1
n
a
i
j
x
j
k
-
τ
i
j
+
∑
j
=
1
r
b
i
j
u
j
k
,
i
=
1,2
,
…
,
n
,where x
=
[
x
1
,
x
2
,
…
,
x
n
]
T
∈
R
n is the state vector and u
=
[
u
1
,
u
2
,
…
,
u
r
]
T
∈
R
r is the control input vector. Matrices A
=
(
a
i
j
)
n
×
n and B
=
(
b
i
j
)
n
×
r are assumed to be structured matrices. 0
≤
τ
i
j
≤
b with bounded maximum delay b and each directed edge (
x
i
,
x
j
) experiences a fixed delay τ
i
j in the sense that each message leaving state node x
i takes τ
i
j iterations to reach x
j.Definition 8.
The linear delayed system (4) given by its structured matrices (
A
,
B
) is said to be structurally controllable if and only if there exists a matrix pair (
A
¯
,
B
¯
) has the same structure as the pair (
A
,
B
) such that the corresponding delayed system (4) given by its structured matrices (
A
¯
,
B
¯
) is completely controllable.By inserting delays on edges, the linear delayed system is transformed into a corresponding linear system without time-delay.For every directed edge(
x
i
,
x
j
) with time-delay τ
i
j, we want to add τ
i
j nodes d
1
i
j
,
d
2
i
j
,
…
,
d
τ
i
j
i
j on the edge, replace (
x
i
,
x
j
) by a delay chain d
1
i
j
,
d
2
i
j
,
…
,
d
τ
i
j
i
j, and reroute all messages from x
i to x
j through that chain. Instead, x
i sends its message to delay node x
1
i
j with the weight of the message being the same as the one that would be used to send a message from x
i to x
j directly without delay; after that, all delay nodes just forward information until the destination node x
j is reached (see Figure 1).Figure 1
(a) A directed graph with 3 state nodes. (b) The directed graph when we add a delay of 4 on the edge(
x
1
,
x
2
).
(a)
(b)Noteτ
=
τ
11
+
⋯
+
τ
1
n
+
τ
21
+
⋯
+
τ
21
+
⋯
+
τ
n
1
+
⋯
+
τ
n
n, all the numbers of time-delays. Let (5)
x
~
=
x
1
,
…
,
x
n
,
d
1
11
,
…
,
d
τ
11
11
,
…
,
d
1
1
n
,
…
,
d
τ
1
n
1
n
,
…
,
d
1
n
1
,
…
,
d
τ
n
1
n
1
,
…
,
d
1
n
n
,
…
,
d
τ
n
n
n
n
T
;then, x
~
∈
R
n
+
τ.Thus, the linear delayed system (4) is equivalent to the following linear system without time-delay:(6)
x
~
k
+
1
=
A
x
~
k
+
B
u
k
,where A
∈
R
(
n
+
τ
)
×
(
n
+
τ
) and B
∈
R
(
n
+
τ
)
×
r are corresponding to A and B, respectively.Example 9.
Consider a very simple example. Without delays we define(7)
A
=
2
3
1
3
0
1
3
1
3
1
3
0
1
3
2
3
,
B
=
1
0
0
.Assume that the directed edge (
x
1
,
x
2
) experiences a fixed delay 4 in the sense that the message leaving state node x
1 takes 4 iterations to reach state node x
2. Then, by inserting 4 delay nodes on the edge (
x
1
,
x
2
), replace (
x
1
,
x
2
) by a delay chain d
1, d
2, d
3, d
4 and reroute all messages from x
1 to x
2 through that chain; that is, x
1 sends its message to delay node d
1 with the weight being 2
/
3, and then d
1 sends its message to delay node d
2, d
2 sends its message to delay node d
3, d
3 sends its message to delay node d
4, and d
4 sends its message to state node x
2 all with the weight being 1. Then, the linear control system with delays is transformed into a linear system without time-delay with the corresponding structured matrices given by (8)
A
=
2
3
1
3
0
0
0
0
0
0
1
3
1
3
0
0
0
1
0
1
3
2
3
0
0
0
0
1
3
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
,
B
=
1
0
0
0
0
0
0
.The directed graphs G
(
A
,
B
) and G
(
A
,
B
) can be seen in Figure 1.


## 3.2. Structural Controllability Analysis

As mentioned above, the structural controllability of the linear delayed system (4) is in consensus with that of the linear system (6) without time-delay. However, some parameters of the structured matrix A are not adjusted; the weight of the edge from one delay node to another node is fixed number 1 (see Figure 1). Therefore, it has failed to apply Lemma 7 to characterize the structural controllability of the linear system (6). Thus, we construct the following linear structured system:(9)
x
^
k
+
1
=
A
x
^
k
+
B
u
k
,where x
^
=
[
x
1
,
…
,
x
n
,
x
n
+
1
,
…
,
x
n
+
τ
]
T
∈
R
n
+
τ and matrices A and B are structured matrices such that (
A
,
B
) have the same structure as (
A
,
B
).For example, we construct a linear structured system corresponding to the linear control system described by a directed graph in Figure1 with the structured matrices A and B given by (10)
A
=
α
11
α
12
0
0
0
0
0
0
α
22
α
23
0
0
0
α
27
0
α
32
α
33
0
0
0
0
α
41
0
0
0
0
0
0
0
0
0
α
54
0
0
0
0
0
0
0
α
65
0
0
0
0
0
0
0
α
76
0
,
B
=
β
1
0
0
0
0
0
0with α
i
j
(
1
≤
i
,
j
≤
7
) and β
1 being nonzero free parameters.In fact, the structure of the representation graphG
(
A
,
B
) is the same as graph G
(
A
,
B
), only denoting the delay nodes of G
(
A
,
B
) as ordinary nodes is graph G
(
A
,
B
). On the other hand, graph G
(
A
,
B
) can also be seen as the expansion of G
(
A
,
B
).The following theorems build the equivalence of the structural controllability of the three systems: system (1), system (4), and system (9).Theorem 10.
The linear system (6) is structurally controllable if and only if the linear system (9) is structurally controllable.Proof.
The necessity is obvious; we then prove the sufficiency. Assume that the linear system (9) is structurally controllable; that is, there exists a matrix pair (
A
¯
,
B
¯
) having the same structure as (
A
,
B
) and satisfying (11)
rank
⁡
B
¯
,
A
¯
B
¯
,
…
,
A
¯
n
-
1
B
¯
T
=
n
+
τ
.
In the following, we will adjust some parameters ofA
¯, wihch is the corresponding parameters to fixed numbers 1 of A.
Firstly, we analyze the characteristics of columns ofA. It is easy to conclude from graph G
(
A
,
B
) that the weight of edge from each delay node is number 1. Then, there is one element 1 in every column from the n
+
1 column to the n
+
τ column, and there is only one non-zero parameter 1 in every column from the n
+
1 column to the n
+
τ column since there is only one edge from each delay node. These elements 1 are either below the diagonal or above the diagonal. If they are below the diagonal, they will be in the form of inclined diagonal; else, if they are above the diagonal, they are in the first n rows (see Figure 1).
Then, from then
+
τ column (the last column), we carry the elementary transformation on the matrix A
¯. In the n
+
τ column of the matrix A, there is only one element that is not zero, and the nonzero element is fixed number 1. Since A
¯ have the same structure as A, the corresponding element in the n
+
τ column of A
¯ is also nonzero, assuming that he value of this element is σ
n
+
τ. Our goal is to put this number σ
n
+
τ into number 1. We can do it as we just need to multiply the n
+
τ column of A
¯ by 1
/
σ
n
+
τ. For the sake of calculating the rank of the controllability matrix, we then multiply the n
+
τ row of A
¯ by σ
n
+
τ.
Next, assume that the single nonzero element in then
+
τ
-
1 column of A
¯ is σ
n
+
τ
-
1. We then multiply the n
+
τ
-
1 column of A
¯ by 1
/
σ
n
+
τ
-
1 and multiply the n
+
τ
-
1 row of A
¯ by σ
n
+
τ
-
1.
Continue to do elementary transformation according to the rules, multiply then
+
τ
-
j column by 1
/
σ
n
+
τ
-
j, and multiply the n
+
τ
-
j row by σ
n
+
τ
-
j, until the n
+
1 column of A
¯. Due to the features of matrix A, The column number of the nonzero element in the n
+
k
(
1
≤
k
≤
τ
) row of A
¯ is less than n
+
k, so multiply the n
+
k row by σ
n
+
k which changes the elements in the first n
+
k columns; the elements after n
+
k columns having been transferred to 1 are not subject to change.
In this way, matrixA
¯ is transformed to a matrix A
¯ with the invertible matrix P, the product of a series of elementary matrix, such that A
¯
=
P
-
1
A
¯
P.
LetB
~
=
P
-
1
B
~
P. Here the matrix B
~
=
(
B
¯
,
0
)
∈
R
(
n
+
τ
)
×
(
n
+
τ
) is constituted by B
¯ as sub-block matrix. Then B
~ can be expressed in the form of a partitioned matrix, that is B
~
=
(
B
¯
,
0
) with the first r columns denoted by B
¯. We thus obtained a pair of matrix (
A
¯
,
B
¯
) having the same structure as the matrix pair (
A
,
B
), such that(12)
rank
⁡
B
¯
,
A
¯
B
¯
,
…
,
A
¯
n
-
1
B
¯
T
=
rank
⁡
B
~
,
A
¯
B
~
,
…
,
A
¯
n
-
1
B
~
T
=
rank
⁡
P
-
1
B
~
P
,
P
-
1
A
¯
B
~
P
,
…
,
P
-
1
A
¯
n
-
1
B
~
P
T
=
rank
⁡
B
~
,
A
¯
B
~
,
…
,
A
¯
n
-
1
B
~
T
=
rank
⁡
B
¯
,
A
¯
B
¯
,
…
,
A
¯
n
-
1
B
¯
T
=
n
+
τ
,which implies the structural controllability of system (6). This completes the proof.The theorem above reveals that the structural controllability of the time-delayed system (4) is consistent with the expansion system (9) without time-delay. Next, we will show the equivalence of the structural controllability between system (1) and the expansion system (9).Theorem 11.
The linear system (1) is structurally controllable if and only if the linear system (9) is structurally controllable.Proof.
The proof of the theorem mainly used the results of Lemma7. Prove the necessity first. Suppose that the linear system (9) is not structurally controllable; it means that there is nonaccessible vertex or there is “dilation” in G
(
A
,
B
). Since there is no difference between graph G
(
A
,
B
) and graph G
(
A
,
B
) from the view of graph theory, therefore there is nonaccessible vertex or there is “dilation” in G
(
A
,
B
).
In the first case, there is nonaccessible vertex inG
(
A
,
B
). If the nonaccessible vertex is the adding delayed vertex d
k
τ
i
j, the k delayed vertex adding on the edge (
x
i
,
x
j
), then the state vertex x
i is a nonaccessible vertex. If the nonaccessible vertex is state vertex, then there exists the corresponding nonaccessible state vertex in G
(
A
,
B
). This is because if the state vertex x
i and the state vertex x
j experience a delay τ
i
j, we add τ
i
j delay vertex on the edge (
x
i
,
x
j
) in the graph G
(
A
,
B
) and replace (
x
i
,
x
j
) by a delay chain; the resulting graph is G
(
A
,
B
). The state vertex in G
(
A
,
B
) is the corresponding state vertex in G
(
A
,
B
).
In the second case, there is “dilation” inG
(
A
,
B
). That is, there exist at least a set S of k vertices in the vertex set of graph G
(
A
,
B
) such that there are no more than k
-
1 vertices in T
(
S
). If there are σ
(
0
≤
σ
≤
k
) delayed vertices in set S, then the σ delayed vertices are in set T
(
S
), and there are no more than k
-
σ
-
1 state vertices in T
(
S
). This implies there exist a corresponding set S
~ of k
-
σ vertices in the vertex set of the graph G
(
A
,
B
) such that there are no more than k
-
σ
-
1 state vertices in T
(
S
~
). Therefore, there is “dilation” in G
(
A
,
B
). By Lemma 7, the linear system (1) is not structurally controllable.
It is easy to prove the sufficiency as in the discussion above. Thus, the proof of the theorem is complete.


## 4. Some Examples

There are two examples being presented in this section to illustrate the theoretical results.Example 1.
Consider a linear control system without time-delays with the structured matrices given by(13)
A
=
1
3
1
3
0
2
3
1
3
2
3
0
1
3
1
3
,
B
=
1
0
0
.
We first consider the case that the message leaving state nodex
1 takes 3 iterations to reach state node x
2 and the message leaving state node x
3 takes also 3 iterations to reach state node x
2. Then, the linear control system with delays by inserting delay nodes is transformed into a corresponding linear system without time-delay with the corresponding structured matrices given by (14)
A
=
1
3
1
3
0
0
0
0
0
0
0
0
1
3
0
0
0
1
0
0
1
0
1
3
1
3
0
0
0
0
0
0
2
3
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
2
3
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
,
B
=
1
0
0
0
0
0
0
0
0
.The directed graphs G
(
A
,
B
) and G
(
A
,
B
) can be seen in Figure 2.
We then construct a linear structured system(
A
,
B
) with the same structure as (
A
,
B
); its controllable matrices are assumed to be (
A
¯
,
B
¯
) with A
¯ given by (15)
A
¯
=
α
11
α
12
0
0
0
0
0
0
0
0
α
22
0
0
0
α
26
0
0
α
29
0
α
32
α
33
0
0
0
0
0
0
α
41
0
0
0
0
0
0
0
0
0
0
0
α
54
0
0
0
0
0
0
0
0
0
α
65
0
0
0
0
0
0
α
73
0
0
0
0
0
0
0
0
0
0
0
0
α
87
0
0
0
0
0
0
0
0
0
α
98
0
.
Selecting(16)
P
=
1
1
1
1
α
26
α
65
α
54
1
α
26
α
65
1
α
26
1
α
29
α
98
α
87
1
α
29
α
98
1
α
29
,
by simple calculation we obtain(17)
A
¯
=
P
-
1
A
¯
P
=
∗
∗
0
0
0
0
0
0
0
0
∗
0
0
0
1
0
0
1
0
∗
∗
0
0
0
0
0
0
∗
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
∗
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
,where ∗ are non-zero elements and A
¯ is the controllability matrix of A.Figure 2
(a) A directed graph with 3 state nodes. (b) The directed graph when we add a delay of 3 on the edge(
x
1
,
x
2
) and add a delay of 3 on the edge (
x
3
,
x
2
).
(a)
(b)Example 2.
Consider another linear control system without time-delay with the structured matrices given by(18)
A
=
1
3
2
3
0
1
3
1
3
1
3
0
2
3
1
3
,
B
=
1
0
0
.We then consider the case that the message leaving state node x
2 takes 3 iterations to reach state node x
1 and the message leaving state node x
2 also takes 3 iterations to reach state node x
3. Then, the linear control system with delays by inserting delay nodes is transformed into a corresponding linear system without time-delay with the corresponding structured matrices given by (19)
A
=
1
3
0
0
0
0
1
0
0
0
1
3
1
3
1
3
0
0
0
0
0
0
0
0
1
3
0
0
0
0
0
1
0
2
3
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
2
3
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
,
B
=
1
0
0
0
0
0
0
0
0
.The directed graphs G
(
A
,
B
) and G
(
A
,
B
) can be seen in Figure 3.
We then construct a linear structured system(
A
,
B
) with the same structure as (
A
,
B
); its controllable matrices are assumed to be (
A
¯
,
B
¯
) with A
¯ given by (20)
A
¯
=
α
11
0
0
0
0
α
16
0
0
0
α
21
α
22
α
23
0
0
0
0
0
0
0
0
α
33
0
0
0
0
0
α
39
0
α
42
0
0
0
0
0
0
0
0
0
0
α
54
0
0
0
0
0
0
0
0
0
α
65
0
0
0
0
0
α
72
0
0
0
0
0
0
0
0
0
0
0
0
0
α
87
0
0
0
0
0
0
0
0
0
α
98
0
.
Selecting(21)
P
=
1
1
1
1
α
16
α
65
α
54
1
α
16
α
65
1
α
16
1
α
39
α
98
α
87
1
α
39
α
98
1
α
39
,
by simple calculation we obtain(22)
A
¯
=
P
-
1
A
¯
P
=
∗
0
0
0
0
1
0
0
0
∗
∗
∗
0
0
0
0
0
0
0
0
∗
0
0
0
0
0
1
0
∗
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
∗
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
,where ∗ are nonzero elements, which is the controllability matrix of A.Figure 3
(a) A directed graph with 3 state nodes. (b) The directed graph when we add a delay of 3 on the edge(
x
2
,
x
1
) and add a delay of 3 on the edge (
x
2
,
x
3
).
(a)
(b)


## 5. Summary and Future Work

The structural controllability analysis for discrete-time linear control systems with time-delay is discussed in the paper. We derive necessary and sufficient conditions for the linear delayed systems to be structurally controllable by transforming the delayed systems into a corresponding linear system without time-delay. This method is suitable for the discrete-time linear delayed systems; the structural controllability for the continuous-time linear delayed systems is also an issue we are concern with. We look forward to making some results on continuous-time systems.



---

*Source: 1429164-2016-02-04.xml*