Controllability of Kronecker Product Networks
Yuqing Hao Qingyun Wang Zhisheng Duan Guanrong Chen




                                              
                                              
                                              


                                                

[footnoteinfo]This work is supported by the National Natural Science Foundation (NNSF) of China under Grants 11802006, 11572015, U1713223, 61673026, the Beijing Natural Science Foundation under Grant 1194024, the Fundamental Research Funds for the Central Universities under Grant YWF-19-BJ-J-275, and the Hong Kong Research Grants Council under the GRF Grant CityU 11200317. The material in this paper was not presented at any conference.

YUQING]Yuqing Haohaoyq@buaa.edu.cn,    
YUQING]Qingyun Wangnmqingyun@163.com,
Duan]Zhisheng Duanduanzs@pku.edu.cn,             
CHEN]Guanrong Cheneegchen@cityu.edu.hk  

[YUQING]Department of Dynamics and Control, Beihang University, Beijing, 100191, China  
[Duan]State Key Laboratory for Turbulence and Complex Systems, Department of Mechanics and Engineering Science, College of Engineering, Peking University, Beijing 100871, China             
[CHEN]Department of Electronic Engineering, City University of Hong Kong, Hong Kong, China        


                           
Network controllability, network observability, Kronecker product graph, multi-agent systems.               
                             
                                          
                                          


                          
A necessary and sufficient condition is derived for the controllability of Kronecker product networks, where the factor networks are general directed graphs. The condition explicitly illustrates how the controllability of the factor networks affects the controllability of the composite network. For the special case where at least one factor network is diagonalizable, an easily-verifiable condition is explicitly expressed. Furthermore, the controllability of higher-dimensional multi-agent systems is revisited, revealing that some controllability criterion reported in the literature does not hold. Consequently, a modified necessary and sufficient condition is established. The effectiveness of the new conditions is demonstrated through several examples.






§ INTRODUCTION

Controllability is a fundamental issue to be addressed before considering how to control a dynamical system in applications <cit.>. This subject has been extensively studied over more than half a century with various criteria developed, such as the PBH test, Kalman and other kinds of rank conditions, substantial graphic properties, and so on <cit.>.



For most large-scale networked systems, these criteria cannot be applied practically because of their complex structures and heavy computational burdens. Therefore, in recent years, the notion of network controllability has received compelling attention with some efficient criteria established <cit.>. In <cit.>, an exact controllability framework was introduced to identify the minimum set of input nodes for a general network with an arbitrary link-weight distribution. The controllability of networks with specific topologies, such as path graphs, cycle graphs, circulant graphs, multi-chain graphs and grid graphs, was explored in <cit.>. Network controllability was investigated from a graph-theoretic perspective in <cit.>. It is noted that most of the above results are derived for the networks with one-dimensional nodes. Recently, the controllability of networks with
 higher-dimensional nodes has attracted a great deal of interest <cit.>. Some controllability conditions for networked LTI systems were presented in <cit.>, which depend on the transmission zeros of every subsystem and the connection matrix. The controllability of diffusively coupled LTI systems was studied in <cit.> and <cit.>. In <cit.>, the controllability condition for networked MIMO systems was established in terms of two algebraic matrix equations. Moreover, some easily-verifiable conditions were proposed in <cit.> for the controllability of networked LTI systems with a diagonalizable topology matrix.

Besides isolated networks, composite networks have come into play due to their broad applications in different areas of engineering <cit.>. There are many kinds of composite networks, such as Cartesian product networks, Kronecker product networks, strong product networks, lexicographic product networks and so on. In addition to their importance of constructing `larger' networks out of `small' ones, they are useful in the sense that one can get insights about the properties of composite networks from the factor networks. Intuitively, the controllability of a composite network might be verified by checking some properties of the factor networks. The controllability and observability of Cartesian product networks were investigated in <cit.>. In <cit.>, the controllability and observability of linear dynamical systems whose dynamics are induced by the Laplacian of a grid graph were studied. Note that many real-world networks are similar to stochastic Kronecker product graphs. For example, the Kronecker power of a simple generating matrix can yield a Kronecker product graph that fits the Internet (at the autonomous systems level) fairly well <cit.>. Large online social networks, web and blog graphs, peer-to-peer networks, etc., can also be modeled by Kronecker product networks. Moreover, every non-trivial graph has a prime factorization over the Kronecker product <cit.>. It has lower computational complexity to check the controllability of a large-scale network by examining some properties of the smaller factor networks. Therefore, the controllability analysis for Kronecker product networks has brought about renewed interest recently <cit.>. The eigenanalysis for the Kronecker product of two matrices was presented in <cit.>, which shows that the Kronecker products of the factor matrices' eigenvectors are the eigenvectors of the composite matrix. However, not all the eigenvectors of the composite matrix are formulated therein. In <cit.>, the Kronecker product of defective matrices was revisited, characterizing the number of the eigenvectors. Nevertheless, the explicit expressions of the eigenvectors, which are the cornerstone of controllability analysis, are not presented. Recently, a sufficient condition was established in <cit.> for the controllability of Kronecker product networks, where the topology matrices are required to be diagonalizable.


In this paper, the controllability of Kronecker product networks is revisited. The contribution of the paper is four-fold. First, the factor networks considered here are general, directed and weighted. Differing from the condition given in <cit.>, which requires the topology matrix of the composite network to be diagonalizable, this paper removes the diagonalizability requirement. Second, a new necessary and sufficient condition on the controllability of Kronecker product networks is provided in terms of eigenvectors. Compared with the classical PBH test, the new condition typically has a much lower computational cost. Third, for the special case where at least one factor network is diagonalizable, a specified condition is explicitly expressed, which is easier to verify. Finally, this paper shows that the sufficiency of the controllability criterion given in <cit.> does not hold, thereby a modified necessary and sufficient condition is derived.

The remainder of this paper is organized as follows.
Some notations and preliminaries are given
in Section <ref>. The model is formulated in Section <ref>. Some conditions on the controllability of Kronecker product networks are developed in Section <ref>. The controllability of higher-dimensional multi-agent systems is reinvestigated in Section <ref>. Finally, conclusions are drawn in Section <ref>.







§ NOTATIONS AND PRELIMINARIES


In this section, notations and useful preliminaries are introduced.



 §.§ Notations


The notations mostly follow <cit.>. Let e_i be the row vector with all zero entries except for [e_i]_i=1. The linear span of row vectors v_1, ⋯, v_k is a set of all the linear combinations of these vectors, i.e., span{v_1,v_2, ⋯ ,v_k}  = {∑_i = 1^k c_iv_i|c_i∈ℝ}. Let U_1⊕U_2 be the direct sum of two spaces U_1 and U_2.
Matrices, if their dimensions are not explicitly indicated, are assumed to be compatible for algebraic operations.


A weighted digraph 𝒢=(V,E,W) is characterized by a node set V with cardinality n, an edge set E comprised of ordered pairs of nodes with cardinality m, and a weight set W
with cardinality m, where an edge exists from nodes i to j if
(i,j)∈ E with edge weight w_ji∈ W.
𝒜=[a_ij] ∈ℝ^n× n is called the adjacency matrix of 𝒢 with a_ij=w_ij if (j,i) ∈ E and a_ij=0 otherwise. The ith diagonal term of the adjacency matrix denotes the weight of the self-loop on node i. 










 §.§ Kronecker Product Network

The Kronecker product network is a kind of composite network
that can be obtained by applying Kronecker product operation(s) to several smaller networks, called factor networks. Let 𝒢_1=(V_1,E_1,W_1) and 𝒢_2=(V_2,E_2,W_2) be two factor networks. The Kronecker product of 𝒢_1 and 𝒢_2, denoted by 𝒢=𝒢_1 ×𝒢_2, has the node set V_1 × V_2. There is an edge from
node (i,p) to node (j,q) if and only if (i,j) is an
edge of E_1 and (p,q) is an edge of E_2. If an edge exists, the corresponding
weight is w_((i,p),(j,q)) = w_ijw_pq. An example of the Kronecker product of two graphs
𝒢_1 and 𝒢_2 is displayed in Fig. <ref>.










 §.§ Useful Lemmas and Definitions









<cit.>

If u_1, u_2, ⋯, u_n are linearly independent vectors and v_1, v_2, ⋯, v_n are arbitrary vectors, then
∑_k = 1^n u_k⊗v_k = 0
implies that v_k =0 for all k=1,2,⋯,n. Moreover, the roles of u_k and v_k in the above statement can be exchanged.





<cit.>
A row vector x_m is called the mth-order generalized left eigenvector of matrix A corresponding to its eigenvalue λ if
x_m(A - λ I)^m = 0,
and
x_m(A - λ I)^m - 1 0.
Moreover, x_1, ⋯, x_g form a left Jordan chain of A on top of x_1, where the maximum value of g is called the length of this Jordan chain.



























§ MODEL FORMULATION


























Consider a network consisting of Nn nodes with a directed and weighted topology 𝒢 in the following form <cit.>:

    [ ẋ_i(t) =  ∑_j = 1^Nnc _ijx_j(t) + δ_iu_i(t),  i = 1,2, ⋯ ,Nn,;                                                               ]

 where x_i∈ℝ is the state of node i, c _ij∈ℝ represents the coupling strength between nodes i and j, u_i∈ℝ is the control input to node i, and δ_i = 1 if node i is under control, but otherwise δ_i=0, for all i = 1,2, ⋯ ,Nn. Assume that c _ij 0 if there is an edge from node j to node i, otherwise c _ij = 0, for all i,j = 1,2, ⋯ ,Nn.
Denote
A(𝒢) = 𝒜(𝒢)= [c_ij] ∈ℝ^Nn×Nn and B = diag{δ_1,δ_2, ⋯, δ_Nn},
which represent the topology and the external input channels of the network (<ref>), respectively.
Let X = [ x_1, x_2, ⋯ , x_Nn ]^T be the whole state of the network, and U = [ u_1, u_2, ⋯ , u_Nn ]^T be the total external control input. Then, the network (<ref>) can be rewritten in a compact form as

    Ẋ(t) = A(𝒢) X(t) + B U(t).

In the following, consider the controllability of the network with topology graph 𝒢 being the Kronecker product of two factor graphs 𝒢_1 and 𝒢_2. The dynamics of the factor networks are described by
Ẏ_1(t) = A(𝒢_1)Y_1(t) + B_1U_1(t) and
Ẏ_2(t) = A(𝒢_2)Y_2(t) + B_2U_2(t),
where Y_1 ∈ℝ^N and U_1 ∈ℝ^D are the state vector and the control input of the first factor network, respectively; Y_2 ∈ℝ^n and U_2 ∈ℝ^d are the state vector and the control input of the second factor network, respectively. According to the definition of Kronecker product graph, it is easy to prove A(𝒢) = A(𝒢_1×𝒢_2)= A(𝒢_1) ⊗ A(𝒢_2). Therefore,
for this Kronecker product network, its compact form can be formulated as (<ref>) with

    [ A(𝒢) = A(𝒢_1×𝒢_2)= A(𝒢_1) ⊗ A(𝒢_2),;                        B = B_1⊗B_2. ]

The analysis here is presented in terms of two factor networks, which can be extended to larger numbers of factor networks by sequential compositions.
In the following,
it will be shown that the controllability of the composite network can be revealed by
examining some features of the smaller factor networks, which makes the computational complexity much lower.

A graph 𝒢 is prime if it is nontrivial and cannot be decomposed into the Kronecker product of two nontrivial graphs. An expression 𝒢=𝒢_1 ×𝒢_2 ×⋯×𝒢_k, with each 𝒢_i being prime, is called a prime factorization of 𝒢. Note that every nontrivial graph has a prime factorization over the Kronecker product <cit.>. It has lower computational complexity to check the controllability of a large-scale network by examining some properties of the smaller factor networks. Therefore, exploring low-dimensional controllability conditions for Kronecker product networks is of great significance in engineering applications, which gives insight into the controllability of large-scale networks.






§ MAIN RESULTS


In this section, controllability conditions for the composite network (<ref>)-(<ref>) are considered. Firstly, the general case that both A(𝒢_1) and A(𝒢_2) are non-diagonalizable is investigated. Then, a special case where at least one factor network is diagonalizable is further analyzed, with a direct and easily-verifiable condition derived.





 §.§ Both A(𝒢_1) and A(𝒢_2) are non-diagonalizable

In this subsection, the general case that both A(𝒢_1) and A(𝒢_2) are non-diagonalizable is investigated. The connection between the eigenspaces of the factor networks and that of the composite network provides a mechanism to establish efficient controllability conditions.
Firstly, all left eigenvectors of the Kronecker product of two defective matrices are characterized.




Let P=λ I_p+N_p∈ℂ^p × p and Q=μ I_q+N_q∈ℂ^q × q be two defective matrices, where N_p and N_q are nilpotent matrices. The eigenvalues of P⊗ Q are λμ. Moreover,



  
  * if λμ 0, the corresponding left eigenvectors are η^1=e_p⊗ξ_1, η^2=e_p-1⊗ξ_1+e_p⊗ξ_2, ⋯, η^θ=e_p-θ+1⊗ξ_1+e_p-θ+2⊗ξ_2+⋯+e_p⊗ξ_θ, where ξ_1=e_q, ξ _k = ( - 1)^k + 1/λ^k - 1∑_l = 0^k - 2C_k - 2^lμ^k - l - 1e_q - k + l + 1, k=2,⋯,θ, θ  = min{p,q};
  
  * if λ=0 and μ 0, the corresponding left eigenvectors are η^k=e_p⊗ e_k, k=1,⋯,q;
  
  * if λ 0 and μ = 0, the corresponding left eigenvectors are η^k=e_k⊗ e_q, k=1,⋯,p;
  
  * if λ = μ = 0, the corresponding left eigenvectors are η^1=e_p⊗ e_1, η^2=e_p⊗ e_2, ⋯, η^q=e_p⊗ e_q, η^q+1=e_p-1⊗ e_q, ⋯, η^q+p-1=e_1⊗ e_q.






Proof:
According to the structure of matrix P ⊗ Q,
it is easy to verify that the eigenvalues of P ⊗ Q are λμ. In the following, the aforementioned four cases are proved respectively.

Case 1: λμ 0. Since η^1(P⊗Q) = (e_p⊗ e_q)(P⊗Q) = (λe_p) ⊗ (μe_q) = λμη^1, it follows that η^1 is the left eigenvector of P ⊗ Q.
Note that η^2 is the left eigenvector of P ⊗ Q if and only if

    η^2(P⊗Q) = λμη^2.

This implies that λξ _2(μI - Q) = ξ _1Q. Since λξ _2(μI - Q) = μe_q and ξ _1Q = μe_q, equation (<ref>) holds, indicating that η^2 is the left eigenvector of P ⊗ Q.

Assume that η^1, ⋯, η^k-1 are the left eigenvectors of P⊗ Q. Then, η^k is the left eigenvector of P⊗ Q if and only if

    λξ _k(μI - Q) = ξ _k-1Q.

Since λξ _k(μI - Q) = ( - 1)^k + 2/λ^k - 2∑_l = 0^k - 2C_k - 2^lμ^k - l - 1e_q - k + l + 2 and
ξ _k - 1Q = ( - 1)^k/λ^k - 2∑_l = 0^k - 3 C_k - 3^lμ^k - l - 2(μe_q- k + l + 2+  e_q- k + l + 3)
= ( - 1)^k/λ^k - 2∑_l = 0^k - 2 C_k - 2^lμ^k - l - 1e_q - k + l + 2,
one can verify that (<ref>) holds. Therefore, η^k is the left eigenvector of P⊗ Q.
It has been shown in <cit.> that the number of the left eigenvectors for this case is min{p,q}, thus all the left eigenvectors of P⊗ Q are η^1, ⋯, η^θ.


Case 2: λ=0 and μ 0. Since η^k(P⊗Q) = (e_p⊗ e_k)(P⊗Q) = (e_pP) ⊗ (e_kQ) = 0_p^T ⊗ (e_kQ) = 0_pq^T = λμη^k, it follows that η^k=e_p⊗ e_k is the left eigenvector of P ⊗ Q, k=1,⋯,q.
It has been shown in <cit.> that the number of the left eigenvectors for this case is q, thus all the left eigenvectors of P⊗ Q are η^1, ⋯, η^q.

One can prove the results in Cases 3 and 4 similarly, thus the detail is omitted.
This completes the proof.

▪






The number of the eigenvectors of P ⊗ Q associated with the sole eigenvalue λμ was given in <cit.>. However, it does not present explicit expressions of the eigenvectors, which are characterized in the above theorem. Theorem <ref> is the cornerstone of the following controllability analysis for Kronecker product networks.





In what follows, the left eigenvectors of A(𝒢) are expressed through the generalized eigenspaces of the factor networks.



Let λ_1,λ_2,⋯,λ_s be the eigenvalues of A(𝒢_1), and μ_1,⋯,μ_t be the eigenvalues of A(𝒢_2). Then, the eigenvalues of A(𝒢) are λ_1μ_1, ⋯, λ_1μ_t, ⋯, λ_sμ_1, ⋯, λ_sμ_t. Moreover, for the eigenvalue λ_i μ_j with geometric multiplicity θ_ij,

  
  * if λ_iμ_j 0, then θ_ij=min{p_i,q_j}, and the corresponding left eigenvectors are η _ij^k = v_i^k ⊗ w_j^1 -μ _j/λ _iv_i^k - 1⊗ w_j^2 
+ v_i^k - 2⊗[ μ _j^2/λ _i^2w_j^3 +μ _j/λ _i^2w_j^2]+⋯+ v_i^1 ⊗[ ( - 1)^k + 1/λ _i^k + 1∑_l = 0^k - 2C_k-2^lμ _j^k-l- 1.
.w_j^k - l], k=1,⋯,θ_ij;
  
  * if λ_i=0 and μ_j  0, then θ_ij=q_j, and the corresponding left eigenvectors are η_ij^k=v_i^1 ⊗ w_j^k, k=1,⋯,θ_ij;
  
  * if λ_i0 and μ_j = 0, then θ_ij=p_i, and the corresponding left eigenvectors are η_ij^k=v_i^k ⊗ w_j^1, k=1,⋯,θ_ij;
  
  * if λ_i=0 and μ_j = 0, then θ_ij=q_j+p_i-1, and the corresponding left eigenvectors are η_ij^1=v_i^1 ⊗ w_j^1, ⋯, η_ij^q_j=v_i^1⊗ w_j^q_j, η_ij^q_j+1=v_i^2⊗ w_j^1, ⋯, η_ij^θ_ij=v_i^p_i⊗ w_j^1,

where v_i^1, ⋯, v_i^p_i is the left Jordan chain of A(𝒢_1) associated with the eigenvalue λ_i, and w_j^1, ⋯, w_j^q_j is the left Jordan chain of A(𝒢_2) associated with the eigenvalue μ_j, i=1,⋯,s, j=1,⋯,t.





Proof:
Let V ∈ℂ^N × N be a nonsingular matrix such that VA(𝒢_1)V^-1=P=blockdiag{P_1, P_2,⋯,P_s}, where P is the Jordan form of A(𝒢_1) and the ith Jordan block P_i=λ_i I_p_i+N_p_i∈ℂ^p_i × p_i with N_p_i being a nilpotent matrix, i=1,⋯,s. The left Jordan chain of A(𝒢_1) associated with the eigenvalue λ_i is denoted as v_i^1, v_i^2, ⋯, v_i^p_i, where v_i^1 is the top vector and p_i is the length of the Jordan chain.


Let W ∈ℂ^n × n be a nonsingular matrix such that WA(𝒢_2)W^-1=Q=blockdiag{Q_1, Q_2,⋯,Q_t}, where Q is the Jordan form of A(𝒢_2) and the jth Jordan block Q_j=μ_j I_q_j+N_q_j∈ℂ^q_j × q_j, j=1,⋯,t. The left Jordan chain of A(𝒢_2) associated with the eigenvalue μ_j is denoted as w_j^1, w_j^2, ⋯, w_j^q_j, where w_j^1 is the top vector and q_j is the length of the Jordan chain.


Since (V ⊗ W)[A(𝒢_1) ⊗ A(𝒢_2)](V ⊗ W)^ - 1 = P ⊗ Q = blockdiag{P_1⊗Q_1, ⋯ ,P_1⊗Q_t, ⋯ ,P_s⊗Q_1, ⋯ ,P_s⊗Q_t}, the eigenvalues of A(𝒢) are λ_1μ_1, ⋯, λ_1μ_t, ⋯, λ_sμ_1, ⋯, λ_sμ_t.
Let V_i = [ [ v_i^p_iT        ⋯   v_i^1T ] ]^T and W_j = [ [ w_j^q_jT        ⋯   w_j^1T ] ]^T. It is easy to derive that (V_i⊗W_j)A(𝒢) = (P_i⊗Q_j)(V_i⊗W_j). If ζ∈ℂ^1 ×p_iq_j is a left eigenvector of P_i ⊗ Q_j, then ζ (V_i⊗W_j) is the left eigenvector of A(𝒢), i=1,⋯,s, j=1,⋯,t. Thus, the results follow from Theorem <ref> directly.
▪




The explicit expressions of the left eigenvectors given in Theorem <ref> are the core of the following controllability criteria for Kronecker product networks.
Let U_ij=span{η_ij^1,⋯,η_ij^θ_ij} be the left eigenspace of A(𝒢) corresponding to the eigenvalue λ_i μ_j.
In what follows, a theorem is established for the controllability of the Kronecker product network (<ref>)-(<ref>).



Let Λ={λ_1, λ_2, ⋯, λ_s} be the set of the eigenvalues of A(𝒢_1), and Σ={μ_1,⋯,μ_t} be the set of the eigenvalues of A(𝒢_2). The composite network (<ref>)-(<ref>) is controllable if and only if the following two conditions hold simultaneously:

  
  * ∀η∈U_ij and η 0, η (B_1  ⊗ B_2)  0, for i =1,⋯,s, j =1,⋯,t;
  
  * if λ_i_1μ_j_1=λ_i_2μ_j_2=⋯=λ_i_rμ_j_r, where λ_i_k∈Λ, μ_j_k∈Σ, k=1,⋯,r, r >1, then ∀η∈⊕_k = 1^r U_i_kj_k and η 0, η(B_1  ⊗ B_2)  0.








Proof:
Using Theorem <ref> and the PBH test, one can prove this theorem easily. Thus, the detail is omitted.
▪


Theorem <ref> provides a precise and efficient criterion for determining the controllability of a general Kronecker product network, using the generalized eigenvectors of the factor networks with low dimensions. Compared with the classical PBH test, the new condition typically has a much lower computational cost. Due to linear systems duality, the results in Theorem <ref> are equally applicable to the observability of Kronecker product networks.


The effectiveness of the above condition can be illustrated by the following example.


Consider graph 𝒢_1 depicted in Fig. <ref>.

It is easy to verify that
A(𝒢_1) = [ [  8.5    4 -0.5;  3.5    8  0.5;  3.5    3  5.5;      ]].
The eigenvalues of A(𝒢_1) are λ_1=12, λ_2=5. The left eigenvector associated with λ_1 is v_1=-e_1-e_2 and the left Jordan chain corresponding to λ_2 is v_2^1=e_2-e_3, v_2^2=-e_1+e_2.
It is easy to obtain that A(𝒢_1) is non-diagonalizable.
Assume that the second node of 𝒢_1 is under control.
Thus, one has
B_1 = e_2^T.
Let A(𝒢)=A(𝒢_1) ⊗ A(𝒢_1), B=B_1 ⊗ B_1.
Then η _22^1 = [ [   0   0   0   0   1 - 1   0 - 1   1 ]] and η _22^2 = [ [   0 - 1   1   1   0 - 1 - 1   1   0 ]]. If c_1=0, one has (c_1 η_22^1+c_2 η_22^2)(B_1 ⊗ B_1)=c_1=0.
It then follows from Theorem <ref> that (A(𝒢),B) is uncontrollable. This example fully demonstrates the effectiveness of the condition.



















Theorem 6 in <cit.> has established a controllability condition for Kronecker product networks, which requires A(𝒢) to be diagonalizable. This assumption is conservative and the condition can only be applied to a very restricted type of networks. The new condition here removes this restriction, thus is more general and flexible. This nontrivial extension is of great significance in engineering applications.





In the following, some more intuitive and easily-verifiable conditions are presented, which reveal how the controllability of the factor networks affects the controllability of the whole composite network.



If the composite network (<ref>)-(<ref>) is controllable, then the factor networks (A(𝒢_1),B_1) and (A(𝒢_2),B_2) are controllable.





If A(𝒢_1) has an eigenvalue 0, to ensure the controllability of the composite network (<ref>)-(<ref>), it is necessary that B_2=I_n. Moreover, if A(𝒢_2) has an eigenvalue 0, to ensure the controllability of the composite network, it is necessary that B_1=I_N.



Proof:

If A(𝒢_1) has an eigenvalue 0, without loss of generality, let λ_i=0, then the left eigenvectors of A(𝒢) corresponding to 0 are v_i^1⊗ w_1^1, ⋯, v_i^1 ⊗ w_1^q_1, ⋯, v_i^1⊗ w_t^1, ⋯, v_i^1 ⊗ w_t^q_t, where v_i^1 is the left eigenvector of A(𝒢_1) associated with the eigenvalue 0; w_1^1, ⋯, w_1^q_1, ⋯, w_t^1, ⋯, w_t^q_t are all the left root vectors of A(𝒢_2). If the composite network (<ref>)-(<ref>) is controllable, then [ ∑_j = 1^t ∑_k = 1^q_k (c_j^kv_i^1 ⊗ w_j^k)](B_1  ⊗ B_2)  0, for any scalars c_1^1, ⋯, c_1^q_1, ⋯, c_t^1, ⋯, c_t^q_t, which are not all zero. That is, (v_i^1 B_1 ) ⊗[ ∑_j = 1^t ∑_k = 1^q_k(c_j^kw_j^kB_2)]  0, which implies [ ∑_j = 1^t ∑_k = 1^q_kc_j^kw_j^k]B_2  0, for any nonzero [c_1^1,⋯, c_1^q_1, ⋯, c_t^1, ⋯, c_t^q_t]. Since w_1^1, ⋯, w_1^q_1, ⋯, w_t^1, ⋯, w_t^q_t are all the left root vectors of A(𝒢_2), which span ℂ^n, one has B_2=I_n.

The second part can be proved similarly.
▪



Hereinafter, the special case where A(𝒢_1) or A(𝒢_2) is diagonalizable is analyzed in detail, for which a simple and effective condition is obtained. Compared with the conditions for the general case, this easy-to-verify condition allows to check the network controllability more efficiently.




 §.§ A(𝒢_1) or A(𝒢_2) is diagonalizable
































In this subsection, a controllability criterion is established for the Kronecker product network (<ref>)-(<ref>) with one diagonalizable factor network.



Assume that A(𝒢_1) or A(𝒢_2) is diagonalizable. Let Λ={λ_1,⋯, λ_s} be the set of the eigenvalues of A(𝒢_1), and Σ={μ_1,⋯,μ_t} be the set of the eigenvalues of A(𝒢_2). The composite network (<ref>)-(<ref>) is controllable if and only if the following four conditions hold simultaneously:

  
  * (A(𝒢_1),B_1) and (A(𝒢_2),B_2) are controllable;
  
  * if A(𝒢_1) has an eigenvalue 0, then B_2=I_n;
  
  * if A(𝒢_2) has an eigenvalue 0, then B_1=I_N;
  
  * if λ_i_1μ_j_1=λ_i_2μ_j_2=⋯=λ_i_rμ_j_r 0, where λ_i_k∈Λ, μ_j_k∈Σ, for k=1,⋯,r, r >1, then (v_i_1B_1 ) ⊗ (w_j_1B_2), ⋯, (v_i_rB_1 ) ⊗ (w_j_rB_2) are linearly independent, where v_i_k is the left eigenvector of A(𝒢_1) corresponding to the eigenvalue λ_i_k; w_j_k is the left eigenvector of A(𝒢_2) corresponding to the eigenvalue μ_i_k, k=1,⋯,r.







Proof:
The case that A(𝒢_1) is diagonalizable is firstly proved. In this case, s=N. Then with a similar method, one can prove the other case easily.





















Necessity: First of all, from Corollaries <ref> and <ref>, it follows that conditions (1)-(3) are necessary for the controllability of the composite network (<ref>)-(<ref>).




Assume that λ_i_1μ_j_1=λ_i_2μ_j_2=⋯=λ_i_rμ_j_r=σ 0, where λ_i_k∈Λ, μ_j_k∈Σ, k=1,⋯,r, r >1. Then, any left eigenvector of A(𝒢) corresponding to σ can be expressed in the form of ∑_k = 1^r α _k(v_i_k⊗w_j_k), where v_i_k is the left eigenvector of A(𝒢_1) corresponding to the eigenvalue λ_i_k; w_j_k is the left eigenvector of A(𝒢_2) corresponding to the eigenvalue μ_i_k; α_k∈ℝ (k=1,⋯,r) are some scalars which are not all zero. If the composite network (<ref>)-(<ref>) is controllable, then [ ∑_k = 1^r α _k(v_i_k⊗w_j_k)](B_1  ⊗ B_2)  0. Consequently,
∑_k = 1^rα _k(v_i_kB_1) ⊗ (w_j_kB_2) 0,
for any scalars α _1, ⋯, α_r, which are not all zero.
Therefore, (v_i_1B_1 ) ⊗ (w_j_1B_2), ⋯, (v_i_rB_1 ) ⊗ (w_j_rB_2) are linearly independent.



Sufficiency: One needs to prove that, if the composite network (<ref>)-(<ref>) is uncontrollable, then at least one condition in Corollary <ref> does not hold. Based on the PBH test, if the composite network (<ref>)-(<ref>) is uncontrollable, then there exists a left-eigenpair of A(𝒢), denoted as (σ, ξ ), such that

    ξ B=0.

This will be discussed in the following 3 cases.

  
  * If σ 0 is an eigenvalue with the geometric multiplicity being 1, assume that σ=λ_iμ_j, it then follows from Theorem <ref> that ξ=v_i⊗ w_j^1, where λ_i ∈Λ 0 with the corresponding left eigenvector v_i; μ_j  ∈Σ 0 with the corresponding left eigenvector w_j^1. From equality (<ref>), it can be easily deduced that (v_i⊗ w_j^1)(B_1 ⊗ B_2)=(v_i B_1)⊗ (w_j^1 B_2) =0, which yields
v_i B_1=0
or
w_j^1 B_2=0.
It can be then derived that (A(𝒢_1),B_1) is uncontrollable or (A(𝒢_2),B_2) is uncontrollable.
  
  * If σ 0 is an eigenvalue with the geometric multiplicity more than 1, assume that λ_i_1μ_j_1=⋯=λ_i_rμ_j_r=σ, where λ_i_k∈Λ 0, μ_j_k∈Σ 0, k=1,⋯,r, r >1. It follows from Theorem <ref> that ξ can be expressed in the form of ∑_k = 1^r α̂_k(v_i_k⊗w_j_k), where v_i_k is the left eigenvector of A(𝒢_1) associated with the eigenvalue λ_i_k; w_j_k is the left eigenvector of A(𝒢_2) associated with the eigenvalue μ_j_k; α̂_k∈ℝ (k=1,⋯,r) are some scalars, which are not all zero. From equality (<ref>), it follows that there exists a nonzero vector [α̂_1,⋯,α̂_r], such that
      [ ∑_k = 1^r α̂_k(v_i_k⊗w_j_k)](B_1  ⊗ B_2) = ∑_k = 1^r α̂_k(v_i_kB_1 ) ⊗ (w_j_k
B_2)  = 0.
      It indicates that (v_i_1B_1 ) ⊗ (w_j_1B_2), ⋯, (v_i_rB_1 ) ⊗ (w_j_rB_2) are linearly dependent.

  




























  
  * If σ = 0, assume that λ_1=⋯=λ_p=0 and μ_1=⋯=μ_l=0. It follows from Theorem <ref> that ξ can be expressed in the form of ∑_i = 1^p ∑_j = 1^t ∑_k = 1^q_j (α̂_ij^kv_i⊗ w_j^k)   + ∑_j = 1^l ∑_i = p + 1^N (β̂_ijv_i⊗ w_j^1), where v_i is the left eigenvector of A(𝒢_1) associated with the eigenvalue λ_i, i=1,⋯,N; q_j, w_j^k (k=1,⋯,q_j) are defined as in Theorem <ref>; α̂_ij^k (k=1,⋯,q_j, j=1,⋯,t, i=1,⋯,p) and β̂_ij (j=1,⋯,l, i=p+1,⋯,N) are some scalars, which are not all zero. From equality (<ref>), it follows that there exist scalars α̂_ij^k (k=1,⋯,q_j, j=1,⋯,t, i=1,⋯,p) and β̂_ij (j=1,⋯,l, i=p+1,⋯,N), which are not all zero, such that
      [ ∑_i = 1^p ∑_j = 1^t ∑_k = 1^q_j(α̂_ij^kv_i⊗ w_j^k)  + ∑_j = 1^l ∑_i = p + 1^N (β̂_ijv_i⊗ w_j^1)](B_1
⊗B_2) = 0,
      which implies that
 
    [ ∑_j = 1^l [ (∑_i = 1^p α̂_ij^1v_iB_1  + ∑_i = p + 1^N β̂_ijv_iB_1 ) ⊗ (w_j^1B_2)]  +;                      ∑_j = 1^l ∑_k = 2^q_j[ (∑_i = 1^p α̂_ij^kv_iB_1)⊗ (w_j^kB_2)] +;             ∑_j = l + 1^t ∑_k = 1^q_j[ (∑_i = 1^p α̂_ij^kv_iB_1) ⊗ (w_j^kB_2)]  = 0. ]

      From Lemma <ref>, it can be derived that equality (<ref>) holds if and only if at least one of the following conditions holds:
      
        
  * w_1^1B_2, ⋯, w_1^q_1B_2, ⋯, w_t^1B_2, ⋯, w_t^q_tB_2 are linearly dependent.
        
  * v_1B_1, ⋯, v_NB_1 are linearly dependent.
      
      Since w_1^1, ⋯, w_1^q_1, ⋯, w_t^1, ⋯, w_t^q_t are all the left root vectors of A(𝒢_2), which span ℂ^n, the first condition implies that B_2  I_n. Moreover, since v_1, ⋯, v_N are all the left eigenvectors of A(𝒢_1), which span ℂ^N, the second condition indicates that B_1  I_N. Thus, in this case, if the composite network (<ref>)-(<ref>) is uncontrollable, then B_1  I_N or B_2  I_n.


Therefore, if the composite network (<ref>)-(<ref>) is uncontrollable, then at least one condition in Corollary <ref> does not hold.
This completes the proof.
▪














The effectiveness of this criterion can be illustrated by the following example.



Consider two graphs 𝒢_1 and 𝒢_2, which are depicted in Fig.<ref>.

It is easy to verify that
A(𝒢_1) = [ [  8.5    6 -2.5;  3.5    6  2.5;  3.5    6  2.5;      ]] and A(𝒢_2) = [ [  8.5    4 -0.5;  3.5    8  0.5;  3.5    3  5.5;      ]].
Note that A(𝒢_1) is diagonalizable. The eigenvalues of A(𝒢_1) are λ_1=12, λ_2=5 and λ_3=0 with the corresponding left eigenvectors v_1=e_1+e_2, v_2=-e_1+e_3 and v_3=-e_2+e_3, respectively. Moreover, the eigenvalues of A(𝒢_2) are μ_1=12, μ_2=5. The left eigenvector associated with μ_1 is w_1=-e_1-e_2 and the left Jordan chain corresponding to μ_2 is w_2^1=e_2-e_3, w_2^2=-e_1+e_2.
Assume that the first two nodes of 𝒢_1 have control inputs and all the nodes of 𝒢_2 are under control.
Thus, one has
B_1 = [e_1^T, e_2^T] and B_2 = [e_1^T, e_2^T, e_3^T]. Firstly, it is easy to verify that (A(𝒢_1),B_1) and (A(𝒢_2),B_2) are controllable. Since A(𝒢_1) has an eigenvalue 0 and B_2=I_3, the second condition holds. Further, noting that λ_1μ_2=λ_2μ_1=60, one needs to check whether (v_1B_1)⊗ (w_2^1B_2) and (v_2B_1)⊗ (w_1B_2) are linearly dependent. Since B_2=I_3, w_2^1B_2 and w_1B_2 are linearly independent. Moreover, v_1B_1  0 and v_2B_1  0. Thus, one can verify that (v_1B_1)⊗ (w_2^1B_2) and (v_2B_1)⊗ (w_1B_2) are linearly independent. It then follows from Corollary <ref> that (A(𝒢),B) is controllable. This result coincides with the conclusion derived by the Kalman rank condition.





































If A(𝒢) is diagonalizable, then both A(𝒢_1) and A(𝒢_2) are diagonalizable. The conditions in Corollary <ref> are also effective for diagonalizable Kronecker product networks, as demonstrated by the following example.












Consider two graphs 𝒢_1 and 𝒢_2, which are depicted in Fig. <ref>.

It is easy to verify that
A(𝒢_1) = [ [ 1 1 2; 0 2 0; 0 1 3;   ]] and A(𝒢_2) = [ [ 6 1 2; 0 2 0; 0 5 3;   ]].
The eigenvalues of A(𝒢_1) are λ_1=2, λ_2=1 and λ_3=3 with the corresponding left eigenvectors
v_1=e_2, v_2=e_1-e_3 and v_3=e_2+e_3, respectively.
The eigenvalues of A(𝒢_2) are μ_1=2, μ_2=3 and μ_3=6 with the corresponding left eigenvectors w_1=e_2, w_2=5e_2+e_3, w_3=3/2e_1+13/8e_2+e_3, respectively. It is easy to verify that A(𝒢) is diagonalizable.
Assume that the first two nodes of 𝒢_1 have control inputs. Node 2 and node 3 of 𝒢_2 are under control.
Thus, one has
B_1 = [e_1^T, e_2^T] and B_2 = [e_2^T, e_3^T].
Both pairs (A(𝒢_1),B_1) and (A(𝒢_2),B_2) are controllable. Since λ_1μ_2=λ_2μ_3=λ_3μ_1=6,
the value of [c_1(v_1 ⊗ w_2)+c_2(v_2⊗ w_3)+c_3(v_3 ⊗ w_1)](B_1 ⊗ B_2) is required to be checked, which gives [c_1(v_1⊗w_2) + c_2(v_2⊗w_3) + c_3(v_3⊗w_1)](B_1⊗B_2) = [ [    13/8c_2,        c_2, 5c_1 + c_3,         c_1 ] ]  0, for any nonzero [c_1, c_2, c_3].
It then follows from Corollary <ref> that (A(𝒢),B) is controllable, which coincides with the conclusion derived by the Kalman rank condition. This example fully demonstrates the effectiveness of the condition.













A controllability criterion for diagonalizable Kronecker product networks was established in <cit.>,
which was claimed to be necessary and sufficient. However, Example <ref> shows that the necessity of that criterion does not hold. Corollary <ref>
provides a new controllability condition, which is not only sufficient but also necessary.



























§ CONTROLLABILITY OF HIGHER-DIMENSIONAL MULTI-AGENT SYSTEMS REVISITED





 §.§ Problem Statement

Consider a multi-agent system consisting of N agents labeled by the set V = {1,2, ⋯ ,N}. Assign the roles of leaders and followers to the agents by denoting V_L = {v_1,v_2, ⋯ ,v_m} and V_F = V\V_L as the sets of indices of the leaders and followers, respectively, where m ≤ N.

To each follower i ∈ V_F, associate a dynamical system
ẋ_i = z_i,
and to each leader i ∈ V_L, we associate a dynamical system
ẋ_i = z_i + Bu_i,
where x_i∈ℝ^n is the state of agent i; u_i∈ℝ^p is the external input to agent i ∈ V_L; z_i ∈ℝ^n is the coupling input from other agents.

Agent i is said to be a neighbor of agent j if its state is known by agent j. Here, assume that the neighboring relationships are fixed, which can be described by a directed and weighted graph 𝒢=(V,E,W). The coupling input z_i to each agent i ∈ V is determined by the diffusive coupling rule based on the neighboring relations as follows:
z_i = H∑_(j,i) ∈ Ew_ij(x_j - x_i),
where H ∈ℝ^n × n is the matrix describing inner-coupling between different components, and w_ij∈ℝ is the strength of the information link.





















The Laplacian matrix of 𝒢 and the external input channels of the multi-agent system are denoted by
L  ∈ℝ^N × N and Δ = diag{d_1,d_2, ⋯, d_N},
respectively, where d_i = 1 for i ∈ V_L, but otherwise d_i=0, for all i = 1,2, ⋯ ,N.
Let X = [ x_1^T, x_2^T, ⋯ , x_N^T ]^T be the whole state of the multi-agent system, and U = [ u_1^T, u_2^T, ⋯ , u_N^T ]^T be the total external control input. Then, the above multi-agent system can be rewritten in a compact form as

    [ Ẋ = F X + G U, ]

with

    F  =  -L ⊗ H,  G  = Δ⊗ B.

Note that matrix F has the form of the Kronecker product of two matrices and so does G. This higher-dimensional multi-agent system can be seen as a special case with A(𝒢_1) being a Laplacian matrix. In the following,
conditions for ensuring the controllability of the multi-agent system (<ref>)-(<ref>) are specified.

The controllability of networked LTI systems or multi-agent systems with linear dynamics has been investigated in <cit.>. The state matrices for those systems have the form of I ⊗ A+ L ⊗ H rather than a pure Kronecker product. The higher-dimensional multi-agent systems investigated here can be seen as a special case with nodes having no internal dynamics.



 §.§ A Counterexample

Recall the controllability condition for the multi-agent system (<ref>)-(<ref>) given in <cit.>, where it was assumed that the first N_l agents are leaders. Then, Δ  = [ [   e_1^T,       ⋯, e_N_l^T,     0_N,       ⋯,      0_N ] ] ∈ℝ^N × N and L can be partitioned as
L = [ [ L_ll L_lf; L_fl L_ff ]],
where L_ll∈ℝ^N_l × N_l and L_ff∈ℝ^(N-N_l) × (N-N_l) with subscripts `l' and `f' denoting `leader' and `follower', respectively.







(Theorem 1 of <cit.>)
For an LTI swarm system described by (<ref>)-(<ref>), suppose the first N_l agents are leaders. Then, the system is completely controllable if and only if

  
  * (H,B) is a controllable matrix pair;
  
  * L represents a controllable graph, i,e, [ [ L_ff L_fl ] ] is a controllable matrix pair.








However, while this condition is necessary for the controllability of the network, it may not be sufficient, as shown in the following example.







Consider the undirected path network with three nodes depicted in Fig. <ref>.
Node 1 is selected to be the leader. One has
L  = [ [   1 - 1   0; - 1   2 - 1;   0 - 1   1 ]] and Δ  = [ [ 1 0 0; 0 0 0; 0 0 0 ]]. Let H = [ [ 1.5 0.5; 0.5 1.5 ]] and B = [ [ 1; 2 ]]. It is easy to verify that (H,B) and (L_ff, L_fl) are controllable. From Theorem 1 in <cit.>, it follows that this undirected path network is controllable.

However, if one checks the controllability of this system by using the classical Kalman rank condition, one can find that (-L ⊗ H, Δ⊗ B) is actually uncontrollable. Therefore, its sufficiency does not hold.


This example is a modification of the example presented in <cit.>, which was used to demonstrate that the controllability condition for diffusive networks proposed in <cit.> is not always sufficient. The incomplete eigenanalysis of networks presented in <cit.> and <cit.> leads to errors in controllability analysis. In the following, a modified controllability condition is proposed, which is both necessary and sufficient.









 §.§ New Controllability Criteria

Note that the conditions proposed in Section <ref> are not restricted to checking the controllability of Kronecker product networks. They can tackle the controllability problem for any system represented by the Kronecker product of two matrices. Based on the results in Section <ref>, a modified controllability condition for the multi-agent system (<ref>)-(<ref>) is established as follows.



The multi-agent system (<ref>)-(<ref>) is controllable if and only if the following three conditions hold simultaneously:

  
  * (L,Δ) is controllable;
  
  * rank(B)=n;
  
  * if H has an eigenvalue 0, then Δ=I_N.



Proof:
Note that L has an eigenvalue 0. If the multi-agent system (<ref>)-(<ref>) is controllable, then rank(B)=n.
From Corollaries <ref> and <ref>, it follows that the conditions (1) and (3) are necessary for the controllability of the multi-agent system (<ref>)-(<ref>).

For sufficiency, one needs to prove that, if the conditions (1)-(3) hold, then no left eigenvectors of F are orthogonal to G, thus the multi-agent system (<ref>)-(<ref>) is controllable. It is easy to verify that if the conditions (1)-(3) hold, then no left eigenvectors of F associated with eigenvalue 0 are orthogonal to G. For a nonzero eigenvalue σ=-λμ, if it is not a common eigenvalue, it follows from Theorem <ref> that any corresponding left eigenvector can be expressed as ξ=(∑_i = 1^θc_iv^i)  ⊗ w^1 + ∑_k = 2^θ[ ( ∑_i = k^θ∑_j = 1^i - k + 1c_il_ijv^j) ⊗ w^k], where v^1, ⋯, v^p is the left Jordan chain of L associated with the eigenvalue λ, and w^1, ⋯, w^q is the left Jordan chain of H associated with the eigenvalue μ, θ=min{p,q}, l_ij is a nonzero scalar about λ and μ, c_1, ⋯, c_θ are scalars, which are not all zero. Next, the value of ξ(Δ⊗ B) will be checked.
It is easy to verify that
ξ (Δ⊗ B) = (∑_i = 1^θc_iv^iΔ) ⊗ (w^1B) + ∑_k = 2^θ[ ( ∑_i = k^θ∑_j = 1^i - k + 1c_il_ijv^jΔ) ⊗ (w^kB)].
Since rank(B)=n, w^1B, ⋯, w^θB are linearly independent. Since (L,Δ) is controllable, it follows that ∑_i = 1^θc_iv^iΔ and ∑_i = k^θ∑_j = 1^i - k + 1c_il_ijv^jΔ (k=2,⋯,θ) are not all zero. From Lemma <ref>, it can be easily deduced that ξ (Δ⊗ B) 0. Thus, for any nonzero eigenvalue of F, if it is not a common eigenvalue, no corresponding left eigenvectors are orthogonal to G.
Similarly, one can prove that, for each nonzero common eigenvalue of F, no corresponding left eigenvectors are orthogonal to G.
Consequently, no left eigenvectors of F are orthogonal to G.
Therefore, the multi-agent system (<ref>)-(<ref>) is controllable. This completes the proof.
▪




According to Corollary <ref>, one can easily verify that the undirected path network in the above counterexample is uncontrollable. This example fully demonstrates the effectiveness of the condition.



















































§ CONCLUSIONS


The controllability of Kronecker product networks has been investigated, in which the factor networks have general directed topologies. A necessary and sufficient condition for the controllability of the composite network has been derived, which is effective and has a much lower computational cost as compared to existing criteria. For the special case where at least one factor network is diagonalizable, a specified condition has also been established, which is simple and easier to verify. Moreover, the controllability of higher-dimensional multi-agent systems has been reinvestigated. It is found that the sufficiency of the controllability criterion given in <cit.> does not hold. Consequently, a modified condition is derived, which is necessary and sufficient. In future studies, the controllability and observability of other types of network-of-networks will be further considered.


















                                 
10

partition_controllability_2017
Aguilar, C. O., & Gharesifard, B. (2017).
Almost equitable partitions and new necessary
conditions for network controllability.
Automatica, 80, 25–31.
Asavathiratham_2001
Asavathiratham, C., Roy, S., Lesieutre, B., & Verghese, G. (2001). The
influence model. IEEE Control Systems Magazine, 21(6), 52–64.






caining
Cai, N., Zhang, Y. S. (2010). Formation controllability of high-order linear
time-invariant swarm systems. IET Control Theory and Applications, 4(4), 646–654.

chapmanconference
Chapman, A., Mesbahi, M. (2014). Kronecker product of networked systems and their approximates. In 21st International Symposium on the Mathematical Theory
of Networks and Systems. Groningen, the Netherlands (pp. 1426–1431).

chapman_controllability_2014
Chapman, A., Nabi-Abdolyousefi, M., & Mesbahi, M. (2014). Controllability and observability of network-of-networks via
  Cartesian products. IEEE Transactions on Automatic Control, 59(10), 2668–2679.
chen_pinning_2016
Chen, G. R. (2017). Pinning control and controllability of complex dynamical networks. International Journal of Automation and Computing, 14(1), 1–9.
chen_book
Chen, G. R., Wang, X. F., & Li, X. (2014). Fundamentals of Complex Networks: Models, Structures and Dynamics.
Wiley Press.
book
Hammack, R., Imrich, W., & Klavzar, S. (2011).
Handbook of Product Graphs.
CRC Press.
hao_controllability_2017
Hao, Y. Q., Duan, Z. S., & Chen, G. R. (2018).
Further on the controllability of networked MIMO LTI systems.
International Journal of Robust and Nonlinear Control, 28(5), 1778–1788.

hautus_controllability_1969
Hautus. M. L. J. (1969).
Controllability and observability conditions of linear autonomous systems.
Nederlandse Akademie van
  Wetenschappen Proceedings Series A-Mathematical Sciences, 72(5), 443–448.
horn_matrix_1987
Horn, R. A., & Johnson, C. R. (1991).
Topics in matrix analysis.
Cambridge, U.K.: Cambridge Univ. Press.
controllability_multichain_2017
Hsu, S.-P. (2017).
A necessary and sufficient condition for the controllability
of single-leader multi-chain systems.
Int. J. Robust Nonlinear Control, 27(1), 156–168.
kalman_canonical_1962
Kalman, R. E. (1962).
Canonical structure of linear dynamical systems.
Proceedings of the National Academy of Sciences of the United States of America, 48(4), 596–600.
leskovec_2010
Leskovec, J. (2010). Kronecker graphs: an approach to modeling networks.
Journal of Machine Learning Research, 11, 985–1042.
liu_controllability_2011
Liu, Y. Y., Slotine, J. J., & Barabasi, A. L. (2011).
Controllability of complex networks.
Nature, 473(7346), 167–173.
Loan_2000
Loan, C. F. Van (2000). The ubiquitous Kronecker product. Journal of
Computational and Applied Mathematics, 123, 85–100.
controllability_circulant_2013
Nabi-Abdolyousefi, M., & Mesbahi, M. (2013).
On the controllability properties
of circulant networks.
IEEE Transactions on Automatic Control, 58(12), 3179–3184.
Notarstefano
Notarstefano, G., & Parlangeli, G. (2013). Controllability and observability of
grid graphs via reduction and symmetries. IEEE Transactions on Automatic Control,
58(7), 1719–1731.
controllability_path_2012
Parlangeli, G., & Notarstefano, G. (2012).
On the reachability and observability
of path and cycle graphs.
IEEE Transactions on Automatic Control, 57(3), 743–748.
controllability_metrics_2014
Pasqualetti, F., Zampieri, S., & Bullo, F. (2014).
Controllability metrics, limitations and algorithems for complex networks.
IEEE Transactions on Network Systems, 1(1), 40–52.
Rahmani_2009
Rahmani, A., Ji, M., Mesbahi, M. & Egerstedt, M. (2009).
Controllability of multi-agent systems from a graph-theoretic perspective.
SIAM Journal on Control and Optimization, 48(1), 162–186.




roman_advanced_2005
Roman, M. (2005).
Advanced Linear Algebra. New York: Springer.
antagonistic_controllability_2017
Sun, C., Hu, G. Q., & Xie, L. H. (2017).
Controllability of multi-agent networks with
antagonistic interactions.
IEEE Transactions on Automatic Control, 62(10), 5457–5462.
Trentelman_2012
Trentelman, H., Stoorvogel, A. A., & Hautus, M. (2012).
Control Theory for Linear Systems.
New York: Springer.
wang_controllability_2016
Wang, L., Chen, G. R., Wang, X. F., & Tang, W. K. S. (2016)
Controllability of networked MIMO systems.
Automatica, 69, 405–409.
Weichsel
Weichsel, P. M (1962).
The Kroneker product of graphs. Proceedings of the American Mathematical Society, 13(1), 47–52.
xuemengran_comment_2018
Xue, M. R., & Roy, S. (2018).
Comments on “Upper and lower bounds for controllable subspaces of networks of diffusively coupled agents”.
IEEE Transactions on Automatic Control, 63(7), 2306.
xuemengran_input_2017
Xue, M. R., & Roy, S. (2017).
Input-output properties of linearly-coupled dynamical systems: Interplay between local dynamics and network interactions.
In 56th IEEE conference on decision and control. Melbourne, Australia (pp. 487–492).
xuemengran
Xue, M. R., & Roy, S. (2012). Kronecker products of defective matrices: some
spectral properties and their implications on observability. In 2012 American Control Conference. Montreal, Canada (pp. 5202–5207).
xuemengran_model_2018
Xue, M. R., & Roy, S. (2018).
Modal barriers to controllability in networks with linearly-coupled homogeneous subsystems.
arXiv preprint arXiv:1805.01995.
yuan_controllability_2013
Yuan, Z. Z., Zhao, C., Di, Z. R., Wang, W. X., & Lai, Y. C. (2013).
Exact controllability of complex networks.
Nature Communication, 4, 2447.

caoming_2014
Zhang, S., Cao, M, & Camlibel, M. K. (2014).
Upper and lower bounds for controllable
subspaces of networks of diffusively coupled agents.
IEEE Transactions on Automatic Control, 59(3), 745–750.
zhangyuan_2017
Zhang, Y., & Zhou, T. (2017).
Controllability analysis for a networked dynamic system with
autonomous subsystems.
IEEE Transactions on Automatic Control, 62(7), 3408–3415.
zhoutong_2015
Zhou, T. (2015).
On the controllability and observability of networked dynamic systems.
Automatica, 52, 63–75.
















                               
                                 


                                 
                                 
                                 
                                 




























                                        
