## Abstract

In this paper, the state controllability of networked higher-dimensional linear time-invariant dynamical systems is considered, where communications are performed through one-dimensional connections. The influences on the controllability of such a networked system are investigated, which come from a combination of network topology, node-system dynamics, external control inputs and inner interactions. Particularly, necessary and sufficient conditions are presented for the controllability of the network with a general topology, as well as for some special settings such as cycles and chains, which show that the observability of the node system is necessary in general and the controllability of the node system is necessary for chains but not necessary for cycles. Moreover, two examples are constructed to illustrate that uncontrollable node systems can be assembled to a controllable networked system, while controllable node systems may lead to uncontrollable systems even for the cycle topology.

This article is part of the themed issue ‘Horizons of cybernetical physics’.

## 1. Introduction

Complex networks of dynamical systems are ubiquitous in nature and society, as well as in science and technology [1]. When a network is subject to control, the controllability of the network is essential, which is a classical concept [2] applicable to multi-variable control systems [3,4], composite systems [5], decentralized control systems [6], etc.

The notion of system controllability has been extensively studied over the last half a century. Although various criteria have been well developed, including different kinds of matrix-rank conditions and fundamental graphic properties [2–7], the controllability issue becomes more complicated and challenging when applied to large-scale complex networks due to their structural complexity.

To date, some controllability conditions for large-scale networks have been developed. Notably, the maximum matching technique in graph theory was applied in [8] to find driver nodes to guarantee the structural controllability, and it was found from many real networks that the number of driver nodes is determined mainly by the network’s degree distribution. Moreover, it was shown in [9] that for a class of networks, structural controllability can always be ensured with a single control input, irrespective of the degree distribution; it was then discovered in [10] that the structural controllability of a network depends strongly on the fraction of nodes with in- and out-degree equal to 1 and 2, respectively. Besides, it was investigated in [11] how to optimize the controllability of a network regarding certain performances by perturbing the network structure; the subject of target control was explored in [12] by controlling only a preselected subset of nodes; and the control profile problem was discussed in [13] by quantifying the proportions of source nodes, external dilation points and internal dilation points. It is noted that all the above-mentioned results [8–13] are applicable only to the structural controllability regardless of specific edge weights, and that the dimension of the state of each node is one. However, the state controllability concept was intended to mean the ability to drive the node state vector from any initial state to any desired final state within a finite time, which is more important and useful for practical systems. More noticeably, most real-world networked systems have higher-dimensional node states.

In this paper, we consider the state controllability problem of a networked system with higher-dimensional node systems. One closely related subject is the controllability of multi-agent systems [14–21], where some results [16,18–20] indicated that the controllability usually can be decoupled into two independent parts: one is about the controllability of each individual node and the other is solely determined by the network topology. In [21], the connection between the network topology and the controllability properties of a consensus network is revealed. Moreover, it was investigated in [22] the controllability and observability of some Cartesian product networks, and in [23], the controllability and observability of a general networked system with every subsystem subject to external control input. In recent work [24], we addressed networks with higher-dimensional node systems in a directed and weighted topology, and proved that the controllability of the overall network is an integrated result of the network topology, node-system dynamics, external control inputs and inner interactions, which cannot be decoupled.

In [24], the communications between two connected node systems were performed through higher-dimensional input and output of the node systems. Considering the situation where less transmitted information is more economical, in this paper the controllability of networked systems with one-dimensional communication is investigated, where the higher-dimensional states of the node systems are integrated into one-dimensional input and output so as to save storage and bandwidth. Besides, in many practical situations, only one-dimensional input–output signals can be extracted and transmitted; therefore, this special setting is important to study. Different from the necessary and sufficient condition in [24], which is represented by two algebraic equations in a general form, here in the case of one-dimensional communication, precise and easily verified necessary and sufficient conditions on the controllability will be derived, which show that the observability of the node system is necessary for the controllability of the networked system; the controllability of the node system is necessary for chain networks, but not necessary for cycle networks; and the inner interactions among connected nodes are much more crucial. Moreover, two examples are constructed, which illustrate the efficiency of the results, and further show that uncontrollable node systems can be assembled to form a controllable networked system, while controllable node systems may lead to an uncontrollable networked system even for the cycle topology.

The rest of the paper is organized as follows. In §2, some preliminaries and the general model of networked LTI systems are presented. Controllability conditions on various networked systems are derived in §3. Finally, conclusions are drawn in §4.

## 2. Preliminaries and the networked system

### (a) Preliminaries

Let and denote the real and complex numbers, respectively, () the vector space of real (complex) *n*-vectors, () the set of *n*×*m* real (complex) matrices, *I*_{N} the *N*×*N* identity matrix and *diag*(*a*_{1},…,*a*_{N}) the *N*×*N* diagonal matrix with diagonal elements *a*_{1},…,*a*_{N}. Denote by *σ*(*A*) the set of all the eigenvalues of matrix *A* and by ⊗ the Kronecker product of two matrices.

In a directed graph, an edge (*i*,*j*) is directed from *i* to *j*, where *i* is the tail and *j* is the head of the edge. A graph formed by a sequence of edges {(*v*_{i},*v*_{i+1}) | *i*=1,…,ℓ−1} with no repeated node is called a path, denoted as *v*_{1},…,*v*_{ℓ}, where *v*_{1} is the beginning and *v*_{ℓ} is the end of the path, and *v*_{ℓ} is said to be reachable from *v*_{1}. If *v*_{1},…,*v*_{ℓ} is a path, then the graph formed by adding the edge (*v*_{ℓ},*v*_{1}) is a cycle. A graph without cycles is called a tree. The node in a tree which can reach every other node is called the root of the tree. A leaf in a rooted tree is a node of degree 1 that is not the root.

An *n*-dimensional system is said to be *state controllable*, if it can be driven from any initial state to the origin in finite time by a piecewise continuous control input. (*A*,*B*) is state controllable if and only if the controllability matrix (*B*,*AB*,*A*^{2}*B*,…,*A*^{n−1}*B*) has a full row rank [2,4].

In this paper, for brevity, *controllability* always means state controllability unless otherwise specified, e.g. structural controllability [7].

### (b) The networked system model

In this paper, the node system is *n*-dimensional, and the output and input of each node system are one dimensional. In order to communicate, the signals of *n*-dimensional state of the node system are integrated into one dimension for transmission. Specifically, the dynamical system of node *i* is described by
2.1in which is the state vector, , denotes the inner interaction manner from the output of one node to the state of another node, represents the communication bandwidth between two nodes with *β*_{ii}=0 and *β*_{ij}≠0 if there is communication from node *j* to node *i*, is the output vector, , is the external control input to node *i*, , and *δ*_{i}=1 if node *i* is under control, but otherwise *δ*_{i}=0. To avoid trivial situations, always assume that *N*≥2. Here and throughout, for statement simplicity the network with the node system described by (2.1) will be called a *networked system*.

Denote 2.2which represent the network topology and the external input connections of the networked system (2.1), respectively. Let be the whole state of the networked system, and the total external control input. Then, this networked system can be rewritten in a compact form as 2.3with 2.4

First, recall the Popov–Belevitch–Hautus (PBH) rank condition [4]: the networked system (2.3) and (2.4) is controllable if and only if rank(*sI*_{N⋅n}−*Φ*,*Ψ*)=*N*⋅*n* is satisfied for any . In [24], a necessary and sufficient condition on the controllability of a more general networked system has been given through two algebraic equations, namely, Δ^{T}*FB*=0 and *L*^{T}*FHC*=*F*(*sI*−*A*) has a unique matrix solution *F*=0. These are not easy to verify and are clearly not in the best form of the condition for systems with one-dimensional communication.

In the following, for the networked system (2.1) with one-dimensional communication, some easy-to-check necessary and sufficient conditions will be established, which illustrate in detail how the network topology (described by the matrix *L*), the node system (*A*,*B*,*C*), the external control input (determined by the matrix Δ) and the inner interactions specified by *H* altogether affect the controllability of the whole networked system.

## 3. Main results

### (a) A general network topology

To state the theorem, some more notations are needed. Denote the set of nodes with external control inputs by
3.1For any *s*∈*σ*(*A*), define a matrix set
3.2where

### Theorem 3.1

*Suppose that* *. Then, the networked system (2.1) is controllable if and only if the following hold*:

(i)

*(A,H) is controllable;*(ii)

*(A,C) is observable;*(iii)

*for any s∈σ(A) and κ∈Γ(s), κL≠0 if κ≠0;*(iv)

*for any s∉σ(A), rank(I−Lγ,Δη)=N, where γ=C(sI−A)*^{−1}*H and η=C(sI−A)*^{−1}*B.*

It should be noticed that both formulation and proof cannot directly follow from that of the MIMO setting in [24]. Besides, the conditions are much easier to verify, e.g. condition (iii) is automatically satisfied for cycles and condition (iv) holds automatically for chains, both of which will be discussed in detail in §3b. In order to prove the theorem, two results from [24] and one new result are presented first.

### Lemma 3.2 [24]

*If there exists one node without external control inputs, then for networked system* (*2.3*) *and* (*2.4*) *to be controllable, it is necessary that* (*A*,*HC*) *is controllable*.

### Lemma 3.3 [24]

*If the number of nodes with external control inputs is m, and* *N*>*m*⋅*rank*(*B*), *then for the networked system* (*2.3*) *and* (*2.4*) *to be controllable, it is necessary that* (*A*,*C*) *is observable*.

### Lemma 3.4

*Assume that* *is non-zero. Then*, (*A*,*HC*) *is controllable if and only if* (*A*,*H*) *is controllable*.

### Proof.

Since and , one has rank(*HC*)=1. Therefore, rank(*sI*−*A*,*HC*)=rank(*sI*− *A*,*H*), leading to the conclusion. ▪

### Proof of theorem 3.1: Necessity.

The assumption indicates that there exists at least one node without external control input; therefore, it follows from lemmas 3.2 and 3.4 that condition (i) is necessary. Furthermore, for , it follows from lemma 3.3 that condition (ii) is also necessary.

Now, suppose that condition (iii) is not necessary. Then, there exist an *s*_{0}∈*σ*(*A*) and a non-zero matrix *κ*∈*Γ*(*s*_{0}) such that
For matrix , denote by the vectorization of matrix *M* formed by stacking the columns of *M* into a single column vector. Furthermore, let *α*=*vec*(*κ*)^{T}. Since *κ*∈*Γ*(*s*_{0}), it is easy to verify that *αΨ*=0 and
which contradicts the network controllability.

Finally, suppose that condition (iv) is not necessary. Then, there exists an *s*_{0}∉*σ*(*A*) satisfying
with *γ*_{0}=*C*(*s*_{0}*I*−*A*)^{−1}*H* and *η*_{0}=*C*(*s*_{0}*I*−*A*)^{−1}*B*. Thus, there exists a non-zero vector , such that
Let *α*=[*α*_{1},…,*α*_{N}] with *α*_{i}=*ζ*_{i}*C*(*s*_{o}*I*−*A*)^{−1}. Then, since *ζ*≠0, one has *α*≠0. Moreover,
and
3.3This is also in conflict with the controllability of the networked system.

*Sufficiency*. For , suppose that there exists a vector *α*=[*α*_{1},…,*α*_{N}], with , such that *α*(*sI*−*Φ*)=0 and *αΨ*=0. That is,
3.4and
3.5

If *s*∈*σ*(*A*), then rank(*sI*−*A*)<*n*. From (3.4), it follows that, for all *i*=1,…,*N*,
3.6If not, then
which contradicts with the observability of (*A*,*C*). Moreover, based on (3.4), one has
3.7Therefore, for all *i*=1,…,*N*, one has
3.8Combining it with (3.6) and the controllability of (*A*,*H*), one obtains
3.9

Next, let . In view of (3.5), (3.7) and (3.9), it is easy to verify that *κL*=0 with *α*_{i}(*sI*−*A*)=0 for *i*=1,…,*N*, and *α*_{i}*B*=0 for . Therefore, by condition (iii), one has *α*=0.

If *s*∉*σ*(*A*), then *sI*−*A* is invertible. From (3.4), one has
3.10Let . Then, for *i*=1,…,*N*,
3.11and
3.12Let *ζ*=[*ζ*_{1},…,*ζ*_{N}], and rewrite (3.12) as
3.13Then, from (3.5) and (3.11), it follows that *ζ*_{i}*C*(*sI*−*A*)^{−1}*B*=0 for , which is equivalent to
3.14Consequently, by combining it with (3.13) and condition (iv), one has *ζ*=0, which together with (3.11) imply that *α*=0.

It follows from the above analysis that, for any , the row vectors of matrix [*sI*−*Φ*,*Ψ*] are linearly independent, hence rank(*sI*−*Φ*,*Ψ*)=*N*⋅*n*. Thus, the networked system (2.3) and (2.4) is controllable. ▪

### (b) Some typical network topologies

In this subsection, as applications of theorem 3.1, specific and precise results are derived for some typical network topologies such as cycles and trees (including chains).

#### (i) Cycles

Without loss of generality, assume that node 1 is under external control, as shown in figure 1. The cycle networked system has
3.15where *β*_{1N}≠0, *β*_{i,i−1}≠0 for *i*=2,…,*N* and *β*_{ij}=0 otherwise.

### Corollary 3.5

*Under the assumption that* *and* *the cycle networked system* (*2.3*)–(*3.15*) *is controllable if and only if*

(i) (

*A*,*H*)*is controllable*,(ii) (

*A*,*C*)*is observable*,(iii)

*for any**s*∉*σ*(*A*), 3.16*where**with**γ*=*C*(*sI*−*A*)^{−1}*H*.

### Proof.

For the cycle networked system, 3.17which is invertible; therefore, condition (iii) in theorem 3.1 is automatically satisfied.

In the following, it will be proved that condition (iv) in theorem 3.1 is equivalent to the above rank condition. Note that the two conditions are both given in terms of matrix ranks, yet one is about the network topology which is *N*-dimensional while the other is about a node system which is only *n*-dimensional.

If *γ*=0, then the two matrices both have full ranks. In the following, assume that *γ*≠0.

If rank(*I*−*Lγ*,*Δη*)<*N*, then there exists a non-zero vector such that
that is,
3.18From the recursion formula (3.18), it follows that *k*_{1}≠0 since **k**≠0. Moreover,
which implies that *bγ*=1.

Choose *ξ*=*k*_{1}*C*(*sI*−*A*)^{−1}. Then, *ξ*≠0,
which implies that rank(*I*−*bHC*(*sI*−*A*)^{−1},*B*)<*n*.

If rank(*I*−*bHC*(*sI*−*A*)^{−1},*B*)<*n*, then there exists a non-zero vector , satisfying
Since *ξ*≠0, one has *b*≠0 and *ξH*≠0. Moreover, *ξH*=*bξHγ*, which implies that *bγ*=1.

Now, define
3.19One can easily verify that
Therefore,
which implies that rank(*I*−*Lγ*,*Δη*)<*N*. ▪

### Example 3.6

Consider the networked system (2.1) with three identical nodes as shown in figure 2*a*, where *β*_{13}=*β*_{21}=*β*_{32}=1 and
It is easy to check that (*A*,*B*) is uncontrollable; however, the networked system (2.1) has rank(*Ψ*,*ΦΨ*,*Φ*^{2}*Ψ*,…,*Φ*^{5}*Ψ*)=6, indicating that the networked system is controllable. Next, by using corollary 3.5, it can be seen that *σ*(*A*)={0,0}. And, for any *s*≠0, one has *b*=*s*^{−4} and
3.20Moreover, (*A*,*H*) is controllable and (*A*,*C*) is observable. Therefore, from corollary 3.5, it follows that the networked system is controllable.

### Example 3.7

Consider the networked system (2.1) with three identical nodes as shown in figure 2*b*, where *β*_{13}=−1, *β*_{21}=*β*_{32}=1 and
It is easy to check that (*A*,*B*) and (*A*,*H*) are both controllable and (*A*,*C*) is observable. However, the networked system (2.1) has rank(*Ψ*,*ΦΨ*,*Φ*^{2}*Ψ*,…,*Φ*^{8}*Ψ*)=8<9, showing that the networked system is uncontrollable. Next, by using corollary 3.5, it can be seen that for *s*=2∉*σ*(*A*), one has *C*(2*I*−*A*)^{−1}*H*=−1, *b*=−1 and
3.21Therefore, it follows from corollary 3.5 that the networked system is uncontrollable.

#### (ii) Trees

In [24], it was shown that for a tree with more than one leaf, if only the root has an external control input, then the networked system is uncontrollable, as a consequence of the result that if (*L*,Δ) is uncontrollable then the networked system is uncontrollable. In the following, this result is reproved by verifying the conditions of theorem 3.1.

### Corollary 3.8 [24]

*Consider a tree, in which every node is reachable from the root, and only the root has an external control input. If there is more than one leaf node in the tree, then the tree networked system is uncontrollable irrespective of the node dynamics. Consequently, a star networked system with* *N*>2 *is uncontrollable*.

### Proof.

It will be shown that the condition (iii) of theorem 3.1 is violated. Since there is no cycle in the tree, for convenience renumber the nodes so that for each edge the index of the tail is smaller than that of the head. Thus, the root is labelled as node 1, and the topology matrix *L* of the tree has a lower-triangular form.

If there is more than one leaf node in the tree, there must exist a node, denoted as *k*, which has at least two outgoing edges, (*k*,ℓ) and (*k*,*v*), with ℓ≠*v* and ℓ>*k*, *v*>*k*. Accordingly, *β*_{ℓk}≠0, *β*_{vk}≠0 and the topology can be represented by
3.22where * represents some *β*_{ij} with *i*>*j*. Since each node except the root has one and only one incoming edge, for any *i*=2,…,*N*, there is one and only one index *j* with *j*<*i* satisfying *β*_{ij}≠0. Consequently, all the elements in the ℓth row and *v*th row except *β*_{ℓk} and *β*_{vk} are zeros.

For *s*_{0}∈*σ*(*A*), there exists a non-zero vector *ξ*∈*R*^{1×n} such that
Choose
with *k*_{ℓ},*k*_{v}≠0, satisfying
3.23

Let . Then, *κ*≠0 but *κL*=0, which violates the condition (iii) of theorem 3.1. Therefore, the tree networked system is uncontrollable. ▪

For a tree with only one leaf, it becomes a chain as shown in figure 3, which has
3.24where *β*_{i,i−1}≠0 for *i*=2,…,*N* and *β*_{ij}=0 for *j*≠*i*−1, *i*=1,…,*N*.

### Corollary 3.9

*Under the assumption that* *and* *the chain networked system* (*2.3*)–(*3.24*) *is controllable if and only if* (*A*,*B*) *and* (*A*,*H*) *are both controllable and* (*A*,*C*) *is observable*.

### Proof.

Construct according to condition (iii) of theorem 3.1, such that *α*_{1}∈*Γ*^{2} satisfies *α*_{1}(*sI*−*A*)=0 and *α*_{1}*B*=0, and moreover, *α*_{i}∈*Γ*^{1} satisfies *α*_{i}(*sI*−*A*)=0 for *i*=2,…,*N*. In view of , the condition *κL*≠0 for *κ*≠0 is equivalent to *α*_{1}=0, which implies the equivalence with the controllability of (*A*,*B*). Therefore, condition (iii) in theorem 3.1 is equivalent to the controllability of (*A*,*B*).

Condition (iv) in theorem 3.1 is automatically satisfied for the chain network, since
3.25and correspondingly for *s*∉*σ*(*A*), rank(*I*−*Lγ*)=*N* with *γ*=*C*(*sI*−*A*)^{−1}*H*. □

## 4. Conclusion

We have presented necessary and sufficient conditions for the controllability of a networked system with one-dimensional communication, which explain in detail the integrated effects of the network topology *L*, node system (*A*,*B*,*C*), inner interactions *H* and external control input Δ on the controllability. Specifically, the observability of the node system is necessary for the controllability of the networked system; the controllability of the node system is necessary for the controllability of chain networked system, but not necessary for the cycle networked system; and a tree networked system with more than one leaf is always uncontrollable. These results not only provide precise and efficient criteria for determining the controllability of many large-scale networked systems, by means of verifying some properties of a few matrices of lower dimensions, but also provide some general guidelines on how to assemble uncontrollable node systems to form a controllable networked system, which is deemed useful in engineering practice.

If each node system (described by higher-dimensional matrices (*A*,*B*,*H*,*C*)) is viewed as a subnetwork, then the networked system studied in this paper can also be considered as an interdependent network (or interconnected network, multi-layer network, network of networks, multiplex network, etc. [25]); therefore, the results obtained in this paper should shed light onto studying the controllability of such complex networks.

In this paper, state controllability of networked system with identical node dynamics is considered. For future research, output controllability, stabilization and network with non-identical nodes of large-scale networked systems will be further investigated.

## Authors' contributions

L.W. proved the results and drafted the manuscript. X.W. and G.C. discussed, revised and approved the manuscript.

## Competing interests

The authors declare that there are no competing interests.

## Funding

This work was supported by the National Natural Science Foundation of China under grant nos. 61374176 and 61473189, and the Science Fund for Creative Research Groups of the National Natural Science Foundation of China (no. 61221003), as well as the Huawei Technologies Co. Ltd.

## Footnotes

One contribution of 15 to a theme issue ‘Horizons of cybernetical physics’.

- Accepted November 20, 2016.

- © 2017 The Author(s)

Published by the Royal Society. All rights reserved.