Eigenstructure Analysis from Symmetrical Graph Motives with
Application to Aggregated Controller Design
Takayuki Ishizaki1 , Risong Ku1 , and Jun-ichi Imura1
Abstract— In this paper, we analyze the eigenstructure of
network systems having symmetrical graph motives and apply
it to reduced order controller design based on their aggregated models. In the eigenstructure analysis, formulating thesymmetry of graph motives as the graph automorphism, weshow that particular eigenspace decomposition of network
systems can be found by analyzing the common eigenspacesof all possible permutation matrices, with regard to the graphautomorphism. This eigenspace decomposition explains the appearance of uncontrollable and unobservable subspaces that canbe removed by aggregating, i.e., averaging, symmetrical graphmotives. Furthermore, it turns out that the resultant aggregatedmodel, whose state behavior tracks a kind of centroids of thatof the original network system, has good compatibility withobserver-based state feedback controller design. The efficiencyof the aggregated controller design method is numericallydemonstrated by output regulation of second-order oscillator
networks.

I. I NTRODUCTION
Many of network systems found in the real world havebeen shown to share several common characteristics, e.g.,
the small-world property, the scale-free property, high cluster
coefficients, and so forth [1], [2]. Besides them, some particular patterns of interconnections, called network motives
or graph motives, can often be found [3], [4]. Graph motives
correspond to recurring subnetworks, which can naturally
appear as network growth with duplication [5]. This kindof duplication endows resultant networks with geometricalsymmetry in the sense that the permutation of graph motives
leave the entire network invariant.
In this paper, formulating the symmetry of graph motives as the graph automorphism [6], we first analyze theeigenstructure of network systems having symmetrical graphmotives. On the basis of the fact that the simultaneous
diagonalizability of square matrices is equivalent to thecommutativity of multiplication [7], we show that particulareigenspace decomposition of network systems can be foundby analyzing the common eigenspaces of all possible permutation matrices that leave networks invariant. Our result
is deduced purely from the symmetry of graph motives;
The analysis based on the simultaneous diagonalizability
makes no distinction among directed and undirected graphs,
adjacency and graph Laplacian matrices, and others [8].
From this viewpoint, our analysis can be seen to be more
universal than those in [9], [10], each of which focuses on
adjacency and graph Laplacian matrices.
1 Department of Mechanical and Environmental Informatics, Graduate
School of Information Science and Engineering, Tokyo Institute of Technology; 2-12-1, Meguro, Tokyo, Japan.
{ishizaki,ku,imura}@cyb.mei.titech.ac.jp

Furthermore, as an application of the eigenstructure analysis, we develop a reduced order controller design method thatmakes use of a reduced order model obtained by aggregating
symmetrical graph motives. This method is based on the factthat the existence of symmetrical graph motives makes alocal state space associated with the motives both uncontrollable and unobservable, when the input and output ports are
assigned to nodes other than the motives. It will turn out thatan aggregated model given by removing the redundant state
spaces has good compatibility with state feedback controller
design based on average state observation, which tracks
a kind of centroids of the system states. The efficiencyof this aggregated controller design method is numericallydemonstrated by output regulation of second-order oscillator
networks, which are often used as a primary model of rotary
appliances in power systems control [11].
To clarify our contribution, we provide some referenceson the controllability analyses of network systems. In theline of works [12], [13], a controllability analysis based on
the equitable partition is performed for single-leader leaderfollower networks with a consensus protocol. In particular, acondition to make network systems completely controllable
is derived in view of graph symmetry from the equitablepartition. Most of network controllability analyses, e.g., [14],focus on the discussion of complete controllability, i.e., theability to steer the states to an arbitrary place. It should
be noted that this complete controllability is not necessarily
realistic for the control of large-scale network systems. For
example, in power systems control, it is not necessarily reasonable to individually handle a large number of generatorsfrom the viewpoint of operation and implementation costs.
In this sense, the complete controllability is generally strict
and excessive for the control of large-scale network systems.
On the other hand, for large-scale network systems, we are
not always interested in the exact steering of individual statevariables towards individual target values, but we are onlyinterested in the control of a kind of macroscopic behavior,e.g., the centroids (averages) of node groups classified withrespect to synchronism among nodes [15]–[17]. As being
compatible with this viewpoint, our aggregated controller
design is performed on the premise that the network systems
of interest involve a number of symmetrical graph motives
whose states are to be synchronized with each other. This canbe viewed as the case where they involve a number of stableuncontrollable and unobservable modes corresponding to thedisagreement with the average of the state space associatedwith the motives. As long as the input and output ports are
assigned to make their aggregated model controllable andobservable, we can design the aforementioned aggregatedcontroller in a systematic manner. Through the arguments inthis paper, we aim at showing that making explicit use of
the redundancy from graph symmetry, i.e., the existence ofparticular stable modes that are both uncontrollable and unobservable, can be a key insight into performing reasonable
control system design that is scalable to large-scale network
systems.
The rest of this paper is organized as follows. In Section II, we first provide the system description of dynamical
networks having symmetrical graph motives. In Section III,
we analyze the eigenstructure of the network systems fromthe viewpoint of the graph automorphism and then apply the
analysis to reduced order controller design based on theiraggregated models. Section IV demonstrates the efficiency of
our aggregated controller design method numerically. Finally,
Section V provides concluding remarks of this paper.
Notation: We denote the identity matrix by I, the all-ones
vector by 1 , the image of a matrix A by im A, the kernel by
ker A, the block diagonal matrix whose diagonal blocks are
A and B by diag(A, B), the Kronecker product of A and
B by A ⊗ B, the set of eigenvalues of A by spec(A), theorthogonal complement of a subspace V by V ⊥ , the column
vector stacking a set of vectors xi by col(x1 , . . . , xn ), andthe subspace spanned by xi by span{x1 , . . . , xn }. A pair(λ, v) is said to be an eigenpair of A if Av = λv holds. A
subspace V is said to be an eigenspace of A associated withan eigenvalue λ if V ⊆ ker λI − A.
Let V1 and V2 be subspaces of a vector space. The sumof V1 and V2 is denoted by
V1 + V2 := {x1 + x2 : x1 ∈ V1 , x2 ∈ V2 },∑which may be rewritten as i∈{1,2} Vi . The union is denotedby
V1 ∪ V2 := {x : x ∈ V1 or x ∈ V2 },∪which may be rewritten as i∈{1,2} Vi , and the intersection
is denoted byV1 ∩ V2 := {x : x ∈ V1 and x ∈ V2 },∩which may be rewritten as i∈{1,2} Vi .
II. S YSTEM D ESCRIPTIONIn this paper, we consider a linear network system evolving
over graphs described by{ẋ = Ax + Bu, x(0) = x0
Σ:(1)
y = Cxwhere the system matrices are supposed to be structured as[]
A0
H0 (1 T ⊗ F )A =,(1 ⊗ H)F0 I ⊗ A + Γ ⊗ BC
[
]
(2)
[
]
B0
B =
, C = C0 0 .
0In this formulation, the second half dynamics corresponds
to the network of a set of graph motives having the same
dynamics, whose interconnection structure is represented(A)
Chain part

Motives(B)
Chain part

MotivesFig. 1.

Examples of chain graph with three motives.

by Γ , whereas the first half dynamics corresponds to theremaining part other than the graph motives. The details are
explained through the following example.
Example: Let us consider the dynamics based on theadjacency matrices of the two graphs in Figs. 1-(A) and(B). Both are composed of a chain graph with three graphmotives, depicted by the dashed-dotted line and dashed lines,
respectively. The system matrices of the chain part are given
as follows. The state transition matrix A0 is the tridiagonal
matrix whose superdiagonal and subdiagonal elements are
all one. The input and output matrices are given as
B0 = C0T = col(1, 0, . . . , 0),

H0 = F0T = col(0, . . . , 0, 1),

which correspond to the input and output nodes with theexternal signals u and y and the interconnection with the
motives, respectively. On the other hand, the dynamics ofthe motives is described by




0 1 1
1
A =  1 0 0  , B = H = CT = F T =  0  ,1 0 0
0
where B and C are relevant to the interconnection amongmotives, and H and F are relevant to the interconnection
with the chain part. The difference between the graphs in
Figs. 1-(A) and (B) appears in the interconnection matrices,which are given as


0 1 1
Γ = 0, Γ =  1 0 1  ,
(3)
1 1 0
respectively. The cases of e.g., directed graphs, edgeweighted networks, and graph Laplacian matrices can beconsidered in a similar manner.
□
In this paper, we first analyze the eigenstructure of A in (2)deduced from the existence of symmetrical graph motives,
and then apply the analysis to aggregated controller designfor the network system Σ in (1).

Theorem 1: Let Γ be symmetrical. If∩
ker I − Π = span{1 },III. E IGENSTRUCTURE A NALYSIS
A. Eigenstructure from Symmetrical Graph Motives
In this subsection, we investigate a general principle of thestructure of eigenspaces of A in (2) that is deduced fromsymmetrical graph motives. This eigenstructure analysis isdependent on the symmetry of Γ , but not reliant on thespecific choices of system matrices in (2).
An interconnection matrix Γ is said to be symmetricalwith respect to a permutation matrix Π ifΠΓ = ΓΠ .

(4)

We denote the set of all permutation matrices that satisfy(4) by P[Γ ], in which we do not include the identity
matrix without loss of generality. This is called the graphautomorphism [6]. From (4), we have ΠΓΠ T = Γ , implyingthat interchanging a set of indices, compatible with a node
set having symmetry, makes no change in the matrix Γ .
For example, both interconnection matrices Γ in (3) aresymmetrical with respect to any permutation matrix. Notethat this definition of symmetry makes no distinction between
directed and undirected graphs as well as adjacency andgraph Laplacian matrices. Furthermore, ΠΓ T = Γ T Π is also
led by (4).
From Π 1 = 1 , we can verify that
Π A = AΠ ,

Π := diag(I, Π ⊗ I),(5)which implies that A is symmetrical with respect to the
permutation matrix Π . It is known that square matrices are
simultaneously diagonalizable if and only if they commute[7]. From this fact, we see that Π and Γ in (4) share the same
eigenvectors, as well as Π and A in (5) do so. Therefore,
the eigenspaces of A can be deduced from the analysis ofΠ . In the following, we assume that the square matrices,e.g., A and Γ , are all diagonalizable.
Because Π is unitary for any Π ∈ P[Γ ], the eigenvaluesof Π locate on the unit circle in the complex plane and theireigenvectors can form an orthogonal basis. From the block
diagonal structure of Π in (5), we see that the eigenvector
v of Π associated with the multiple eigenvalues of π = 1
lies in the space of
[
]
[
]
I
0
v ∈ im
+ im
(6)
0
w⊗I
where w is an eigenvector of Π associated with the multiple
eigenvalues of π = 1. On the other hand, the eigenvector vof Π associated with π ∈ spec(Π ) \ {1} lies in the spaceof[]0v ∈ im(7)w⊗I
where w is an eigenvector associated with π ∈ spec(Π )\{1}.
Thus we see that the eigenspace analyses of Π can be divided
into the cases of π = 1 and π ̸= 1.
First we show the following result deduced by analyzing
the eigenspaces of Π ∈ P[Γ ] associated with π = 1.

(8)

Π ∈P[Γ ]then, for any eigenvalue of Γ , there exists an associatedeigenvector w such thatw ∈ span{1 } ∪ span{1 }⊥ .

(9)

Proof: Let q be the number of permutation matrices thatbelong to P[Γ ]. Denote Vi := ker I − Πi for i = 1, . . . , q.
Note thatVi⊥ ⊆ span{1 }⊥(10)because the eigenvectors associated with π ∈ spec(Πi ) \ {1}are orthogonal to the eigenspace span{1 } associated with
π = 1, namely∑Vi⊥ = π∈spec(Πi )\{1} ker πI − Πi .
Furthermore, it follows that each of eigenvectors of Γ liesin either Vi or Vi⊥ , because Πi and Γ are simultaneously
diagonalizable. Consider an eigenvector w ∈ Vi of Γ . Then
we see that()
w ∈ (Vi ∩ Vj ) ∪ Vi ∩ Vj⊥ , ∀j = 1, . . . , q.
If w ∈ Vi ∩ Vj⊥ for some j, then w ∈ span{1 }⊥ because of(10). On the other hand, if w ̸∈ Vi ∩ Vj⊥ for all j, then∩w ∈ j∈{1,...,q} Vj = span{1 }owing to (8). This proves the claim.
Theorem 1 shows that the eigenspaces of an interconnection matrix Γ satisfying (8) is decomposed as in (9). In
the rest of this paper, an interconnection matrix Γ is said
to be strictly symmetrical if (8) holds. One may think thatthe eigenvectors of a graph Laplacian matrix always admit
the decomposition of (9). However, note that Theorem 1 isdeduced from only the symmetry in the sense of (4), whose
definition makes no distinction among adjacency and graphLaplacian matrices and other details.
Example: Both interconnection matrices of Γ in (3) arestrictly symmetrical. This can be easily verified because they
are symmetrical with respect to any permutation matrices,
including the circulant permutation matrix given asTTΠ = e1 eT
2 + e2 e3 + · · · + eν e1 ,(11)

where ei denotes the ith unit vector and ν denotes the sizeof Π . Since the eigenvectors of this permutation matrix
coincides with the discrete Fourier transform vectors [18],it satisfies ker I − Π = span{1 }, which is sufficient for (8).
Furthermore, we see that any interconnection matrix Γ being
circulant, e.g., in the left of Fig. 2, is strictly symmetrical,
because all circulant matrices commute.
Next let us consider an interconnection matrix of
γ1 β βΓ =  β γ2 0  ,(12)
β 0 γ2Mof eigenspaces of A can be deduced from the strict symmetryof Γ as follows.
Theorem 2: Consider A in (2) with Γ being strictly
symmetrical. Then, for any eigenvalue of A, there exists anassociated eigenvector v such that
( [
])
]
]
[
[
I
0
0
v ∈ im
+ im
∪ im
(17)
0
1 ⊗I
w⊗I

M

M

M

M

M

M
M

M

M
M

Fig. 2.
Examples of symmetrical interconnection structure, where themotives are denoted by “M”.

which is depicted in the center of Fig. 2. We can easily
verify that this Γ is symmetrical with respect to the single
permutation matrix[]
0 1
Π = diag(1, I), I :=
.
(13)
1 0
Thus we obtainker I − Π = span {col(1, 0, 0), col(0, 1, 1)} .

(14)

This shows that Γ in (12) is not classified into strictly
symmetrical matrices, even though a particular case, e.g.,
the symmetric graph Laplacian matrix given as γ1 = −2β
and γ2 = −β, admits the property of (9).
Finally, let us consider the case of
γ1 β1 0 β2′
 β1′ γ2 β2 0 

Γ =
(15)
 0 β2 γ1 β1′  ,′β2 0 β1 γ2which is depicted in the right of Fig. 2; a similar example
can be found in [10]. If γ1 = γ2 , β1 = β1′ , and β2 = β2′ ,we have
{[
] [
] [
]}
0 I
I 0
0 I
P[Γ ] =
,
,
,
(16)
I 0
0 I
I 0
{[

otherwiseP[Γ ] =

0
I

I
0

]}
.

Then the term in the left-hand side of (8) is given as
[ ]
[ ]
[ ]
∩
I
I
1
ker I − Π = im
∩ im I ⊗∩ im
I
1IΠ ∈P[Γ ]for the former case, which is equal to span{1 }, while it isgiven as[ ]∩I
ker I − Π = imIΠ ∈P[Γ ]for the latter case. Thus Γ in (15) is strictly symmetrical onlyin the former case. Note that this strict symmetry is inherentin Γ with arbitrary choice of the parameters γi and βi . □On the basis of Theorem 1, which shows the eigenspacedecomposition of Γ led by analyzing the eigenspaces of Π
associated with π = 1, we next analyze the eigenspaces of A
in (2). Owing to the commutativity of (5), the decomposition

where w is an eigenvector of Γ such that w ∈ span{1 }⊥ .
Proof: From (5), we see that the eigenvectors of A canbe classified into (6) and (7). Because Γ is assumed to bestrictly symmetrical, its eigenvector can also be classified asshown in Theorem 1. Thus w in (6) satisfies w ∈ span{1 }whereas w in (7) satisfies w ∈ span{1 }⊥ .
Let (λγ , vγ ) be an eigenpair of A+γBC for γ ∈ spec(Γ )associated with an eigenvector w ∈ span{1 }⊥ . Then we
have
A col(0, w ⊗ vγ ) = λγ col(0, w ⊗ vγ ),which shows that col(0, w ⊗ vγ ) is an eigenvector of A
associated with λγ ∈ spec(A + γBC). Thus this proves theclaim.
Theorem 2 shows that the eigenvectors of A in (2)with a strictly symmetrical interconnection matrix Γ canbe classified into two types as in (17), which stem fromthe strict symmetry. Note that the eigenmodes of Σ in (1)classified into the latter of (17) are necessarily unobservablebecause the corresponding eigenvectors lie in ker C. These
unobservable modes originate from the existence of symmetrical graph motives; Thus they appear regardless of thespecific choices of system matrices. By the arguments of thedual space, we can say that uncontrollable modes appear also
from the symmetry.
The eigenvectors of Γ lying in span{1 }⊥ can also be
deduced by analyzing the eigenspaces of Π associated withπ ∈ spec(Π ) \ {1}. This can be seen though the following
example.
Example: Let Γ be a symmetrical interconnection matrix.
Because Π ∈ P[Γ ] is simultaneously diagonalizable with Γ ,the number of linearly independent eigenvectors of Γ lying
in an eigenspace of Π coincides with the dimension of theeigenspace of Π . Therefore, if
dim ker πI − Π = 1,

π ∈ spec(Π ) \ {1}for some Π ∈ P[Γ ], then w ∈ ker πI − Π is an eigenvectorof Γ lying in span{1 }⊥ . For example, the discrete Fouriertransform vectors spanning span{1 }⊥ are the eigenvectorsof both interconnection matrices Γ in (3), because they
are symmetrical with respect to the circulant permutation
matrix Π in (11), whose eigenvalues are distinct. The same
argument is valid for all circulant interconnection matrices.
Next let us consider Γ in (12), which is symmetrical withrespect to Π in (13). In this case, we haveker πI − Π = span{col(0, −1, 1)}for π = −1. Thus col(0, −1, 1) is an eigenvector of Γ
lying in span{1 }⊥ , which is not dependent on the parameterchoice of Γ . From (14), we see that other two eigenvectors
are given ascol(αi , 1, 1) ∈ span {col(1, 0, 0), col(0, 1, 1)}
where α1 and α2 are the solutions of
αi2 + β −1 (γ2 − γ1 )αi − 2 = 0.
These eigenvectors are dependent on the parameter choiceof γi and β.
Finally, let us consider Γ in (15) with γ1 = γ2 , β1 =
β1′ , and β2 = β2′ , which satisfies (9). For each permutation
matrix in (16), the eigenspace ker πI − Π for π = −1 isobtained as
V1⊥ := span {col(1, 0, −1, 0), col(0, 1, 0, −1)} ,V2⊥ := span {col(1, −1, 0, 0), col(0, 0, 1, −1)} ,V3⊥ := span {col(1, 0, 0, −1), col(0, 1, −1, 0)} ,respectively. Let us find three eigenvectors of Γ such thatany two of them are the elements of V1⊥ , V2⊥ , or V3⊥ . To thisend, we calculate the intersections of two of them, leadingtospan {col(1, −1, −1, 1)} ,span {col(1, −1, 1, −1)} .

span {col(1, 1, −1, −1)} ,It turns out that these one-dimensional subspaces correspondto the eigenvectors of Γ lying in span{1 }⊥ . They are notdependent on the specific choice of γi and βi .
□B. Aggregation of Symmetrical Graph Motives
Let ν denote the number of symmetrical graph motives,
which corresponds to the size of Γ . As shown in Theorem 2,
a set of eigenvectors of A with a strictly symmetricalinterconnection matrix Γ can be classified into the two
types. According to this classification of eigenvectors, theeigenvalues of A can also be classified as follows.
Lemma 3: For A in (2) with Γ being strictly symmetrical,
it follows that∪spec(A) = spec(Â) ∪spec(A + γBC) (18)γ∈spec(Γ )\{γ0 }where the eigenspace span{1 } of Γ is associated with γ0 ∈spec(Γ ) and
[
]
√
νH0 F
A
Â := √ 0.
(19)
νHF0 A + γ0 BC
Furthermore, col(u, v) is an eigenvector of Â associated withλ ∈ spec(Â) if and only if col(u, √1ν 1 ⊗v) is an eigenvectorof A associated with λ.
Proof: From the proof of Theorem 2, we can see thatλγ ∈ spec(A + γBC)is an eigenvalue of A for the eigenvalue γ ∈ spec(Γ )\{γ0 }.
Furthermore, we can verify that the equality of
A col(u, √1ν 1 ⊗ v) = λ col(u, √1ν 1 ⊗ v)

is equivalently rewritten asÂ col(u, v) = λ col(u, v).
This proves the claim.
The classification of the eigenvalues of A in (18) corresponds to that of its eigenvectors in (17). From Lemma 3,
we see that the multiplicity of∪λ ∈ γ∈spec(Γ )\{γ0 } spec(A + γBC)(20)
coincides with that of γ ∈ spec(Γ ) \ {γ0 }. For example, themultiplicity of λ in (20) is found as ν − 1 for both interconnection matrices Γ in (3). As seen here, the existence ofsymmetrical graph motives is also relevant to the multiplicity
of eigenvalues of A.
Note that Â in (19) satisfies
P T A = ÂP T

AP = P Â,

(21)

T

where the projector P such that P P = I is given by()
P := diag I, √1ν 1 ⊗ I .
(22)Furthermore, we see that
B = P B̂,C = ĈP T ,(23)

where B̂ := P T B and Ĉ := CP . On the basis of thisorthogonal projection, let us consider an aggregated modelof Σ in (1) given as{x̂˙ = Âx̂ + B̂u, x̂(0) = P T x0
(24)
Σ̂ :
ŷ = Ĉ x̂.
This aggregated model is almost equivalent to the original
system in the following sense.
Theorem 4: For Σ in (1) with Γ being strictly symmetrical, let Σ̂ be defined as in (24). Theny(t) ≡ ŷ(t),

t≥0

(25)

for any x0 and u. In particular, if x0 ∈ im P , thenx(t) ≡ P x̂(t),t ≥ 0.

(26)

Furthermore, Σ is detectable (stabilizable) if and only if Σ̂is detectable (stabilizable) and A + γBC is stable for allγ ∈ spec(Γ ) \ {γ0 }.
Proof: For any x0 and u, we have∫ tx(t) = exp(At)x0 +exp(A(t − τ ))Bu(τ )dτ.
0

From the second relations in (21) and (23), we see thatk

CAk = Ĉ Â P T
for any natural number k. Thus (25) is proven by
C exp(At) = Ĉ exp(Ât)P T .
Furthermore, from the first relations in (21) and (23), it
follows thatk
Ak B = P Â B̂,which leads toOriginal system

exp(At)B = P exp(Ât)B̂.
From x0 = P P T x0 for x0 ∈ im P , we have (26).
Next we show the relation of detectability. From Theorem 2 and Lemma 3, we see that the unobservable modes ofΣ eliminated by the aggregation of P are associated withthe eigenvalues of λ in (20). Thus the unobservable modes
are stable by the assumption that A + γBC is stable forall γ ∈ spec(Γ ) \ {γ0 }. The claim of stabilizability can beshown by the same arguments of the dual space.
As shown in (25), the aggregated model Σ̂ has the same
initial value response as well as input-to-output characteristics as those of the original system Σ. This stems fromthe unobservability of symmetrical graph motives. On theother hand, the property of state trajectories in (26) stems
from their uncontrollability. Both properties of (25) and(26) are, in principle, essential for designing an observerbased state feedback controller when utilizing the aggregatedmodel. This is because, unless (25) holds, there can bediscrepancy in the measurement output that is injected toan observer; on the other hand, unless (26) holds, there canbe discrepancy in an observed state that is fedback to theplant as a control input signal. As a relaxation of this, somesmall approximation errors can be taken into account in arobust control framework.
IV. N UMERICAL D EMONSTRATION
A. Second-Order Oscillator Network
Let us consider a network system depicted as the uppergraph in Fig. 3, which is composed of three large nodes
forming a chain and 30 small nodes forming a circle. In thissection, regarding each node as a second-order oscillator,i.e., a mass-spring-damper system, we consider an output
regulation problem of the oscillator network. This kind of
second-order networks is called a (linearized) swing equationin power systems control [11]. A similar loop-topology
model can be found in [19], [20], for which a stability
analysis is performed from a viewpoint of node coherence.
The system dynamics is given as follows. Let L denote theunweighted symmetric graph Laplacian matrix compatible
with the upper graph in Fig. 3. In particular, the (1, 1)-blockof L is given as
1 −1 0
L11 =  −1 2 −1  ,0 −1 31
which corresponds to the chain of large nodes. Using thismatrix, we obtain the (1, 1)-block of A in (2) as
[
]
[
]
]
0
1
0 [
k 0
A0 = I ⊗− L11 ⊗
1d
0 −M
Mwhere M > 0 denotes a mass constant, d > 0 denotes adamper constant, and k > 0 denotes a spring constant. In asimilar way, the (1, 2)-block of A is given as
]
[
]
0 [
T
k 0 ,
H0 (1 ⊗ F ) = L12 ⊗1
M

Aggregated modelFig. 3.

Network structures of original system and aggregated model.

where L12 = col(0, 0, 1)1 T . This leads to[][0
H0 = col(0, 0, 1) ⊗, F = k
1

0

]

.

M

The (2, 2)-block of L is given as the symmetric circulant
matrixT,
L22 = C30 + C30

T
C30 := I − (e1 eT
2 + · · · + e30 e1 ),which corresponds to the circle of small nodes. In thisnotation, the (2, 2)-block of A corresponding to the networkof symmetrical graph motives can be represented as
[
]
[
]
0
1
0
A=
, B =
1
d
0 −m
(27)
m
[
]
C = δ k ,
Γ = −L22 ,where m > 0 denotes a mass constant for small nodes andδ ≥ 0 denotes a coefficient of coupling among small nodes.
Then, in a way similar to the (1, 2)-block of A, the (2, 1)block can be represented by
[
]
[
]
0
F0 = colT (0, 0, 1) ⊗ k 0 , H =.
1mFinally, B and C in (2) are given with
[
]
[
]
0
B0 = I ⊗, C0 = I ⊗ 1 0 ,1which imply that the input signals are injected to all large
nodes and the output signals are measured as their positions.
These system matrices lead to a 66-dimensional network
system Σ in (1). This system is semistable and has one zero
eigenvalue for any choice of constants. Furthermore, for any
constant input signal, it follows thatx∗3 = x∗4 = · · · = x∗33 ,where x∗i denotes the steady state of the ith node. Thisimplies that all states of small nodes are to be synchronizedwith that of the third large node. The values of x∗1 , x∗2 , andx∗3 can vary with the value of input signals.
B. Output Regulator Design Based on Aggregated Model
To design an output regulator for the network systemΣ, let us utilize the aggregated model Σ̂ in (24), whose
network structure is depicted as the lower graph in Fig. 3.
In particular, regarding Σ̂ as a plant to be controlled, we
consider designing an observer-based integrator in the formof{ξ̂˙ = Âξ̂ + B̂u + Ĥ(ŷ − Ĉ ξ̂)Ξ:(28)
λ̇ = y ∗ − Ĉ ξ̂,2

C. Numerical Experiments

Position

1.5
1

In the following, we set the system parameters as

0.5
0

M = 10,Zoopm up

-0.5
-1
3

Velocity

2

0
-1
-2
-3
5

10

15

20

25

30

35

40

45

50

5

5.5

6

6.5

7

Time

7.5

8

8.5

9

9.5 102

1
0.5
0Zoopm up

Position

1.5

-0.5
2
1.5

Velocity

1
0.5
0
-0.5
-1
-1.5
-2
0

5

10

15

20

25

30

35

40

45

50

5

5.5

Time

6

6.5

7

7.5

8

8.5

9

9.5 10Time

Output regulation of network system with δ = 1.

Fig. 5.

where the first dynamics corresponds to the observer of Σ̂,which is eight-dimensional, and the second is the threedimensional integrator for output regulation, steering thesystem output to a reference signal denoted by y ∗ . Note thatthe measurement signal ŷ in the observer can be equivalently
replaced with the system output y owing to the property of(25). On the premise of the feedback control ofu = K̂ ξ̂ + Kλ,the output regulation
lim y = y ∗t→∞is achieved if the feedback gains are designed such that
[

Â
−Ĉ

0
0

]

[
+

d = 0.1.

y ∗ = col(0, 0.5, 1),

Time

Output regulation of network system with δ = 0.

Fig. 4.

k = 5,In this setting, we investigate two cases of δ = 0 and δ =1 in (27). A set of stabilizing gains in (29) is found by
the standard LQR design technique. Furthermore, the output
reference signal is given as

1

0m = 1,

B̂
0

]

[

K̂

K

]

,

Â − Ĥ Ĉ

(29)

are stable. Note that the four-dimensional observer works as
an average state observer of Σ, which attainsξ̂1 − x1
ξ̂2 − x2


lim 
(30)
 = 0.
t→∞ ξ̂3 − x3
1
ξ̂ 4 − √30 (x4 + · · · + x33 )This is owing to the property of (26).

which implies that the positions of three large nodes are to
be steered to 0, 0.5, and 1, respectively. The initial value ofΣ is given randomly.
For δ = 0, the trajectories of the network system Σ and its
average state observer in Ξ in (28) are shown in Fig. 4, where
the black thick lines correspond to the states of large nodes,
the red thin lines correspond to those of small nodes, and thedotted lines correspond to those of the observer. The observerstate variable ξ̂ 4 is scaled by √130 as being compatible with(30). From this figure, we can see that the states of three large
nodes are steered to the target positions while the states of
the average state observer track the centroids of the system
states in the sense of (30).
For δ = 1, the resultant trajectories are shown in Fig. 5,
where the same notation as Fig. 4 is used. In this case, thesynchronization of small nodes becomes stronger than theprevious case because the value of δ works as a damper
coefficient for the reduction of discrepancy among small
nodes. These results demonstrate that the observer-basedstate feedback controller design based on aggregated models
works well and it is reasonable for network systems having
a number of symmetrical graph motives, whose states are tobe synchronized with each other.
V. C ONCLUDING R EMARKSIn this paper, from a viewpoint of the symmetry of graphmotives, we have analyzed a sparse structure appearing
in eigenvectors, i.e., eigenmodes of network systems. Furthermore, this eigenstructure analysis has been applied toreduced order controller design based on aggregated models,
derived by aggregating symmetrical graph motives. It has
been found that the existence of symmetry, formulated as
the graph automorphism, makes a local state space associatedwith the motives both uncontrollable and unobservable. An
aggregated model given by removing the redundant modes isuseful in designing a state feedback controller composed ofan average state observer, which tracks a kind of centroidsof the system states.
As a numerical demonstration of the aggregated controller
design, we have performed output regulation of a secondorder oscillator network. Our aggregated controller designis based on the premise that the aggregated model is bothcontrollable and observable, whereas the original oscillator
network is supposed to be only stabilizable and detectable.
In particular, the original is supposed to involve a numberof particular uncontrollable and unobservable modes that

correspond to the disagreement with the average of thestate space associated with symmetrical graph motives. The
degree of stability of disagreement modes is relevant tothe coherence of symmetrical graph motives. From thisviewpoint, we see that making explicit use of the redundancy
from graph symmetry, e.g., sensor and actuator allocation
with explicit consideration of coherent states (cluster states),
can be a key insight into reasonably controlling large-scale
network systems. Introducing a notion of approximation in
the construction of aggregated models, in a way of [16], [17],would be worth pursuing to make the aggregated controller
design method more practical.
ACKNOWLEDGMENTS
This research was supported in part by CREST, JST,and by JSPS Grant-in-Aid for Young Scientists (B) Grant
Number 26820165.
R EFERENCES[1] M. Newman, Networks: an introduction. Oxford University Press,
2009.
[2] S. H. Strogatz, “Exploring complex networks,” Nature, vol. 410, no.
6825, pp. 268–276, 2001.
[3] U. Alon, “Network motifs: theory and experimental approaches,”
Nature Reviews Genetics, vol. 8, no. 6, pp. 450–461, 2007.
[4] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, andU. Alon, “Network motifs: simple building blocks of complex networks,” Science, vol. 298, no. 5594, pp. 824–827, 2002.
[5] F. Chung, L. Lu, T. G. Dewey, and D. J. Galas, “Duplication models
for biological networks,” Journal of computational biology, vol. 10,
no. 5, pp. 677–687, 2003.
[6] B. D. MacArthur, R. J. Sánchez-Garcı́a, and J. W. Anderson, “Symmetry in complex networks,” Discrete Applied Mathematics, vol. 156,
no. 18, pp. 3525–3531, 2008.
[7] B. Noble and J. W. Daniel, Applied linear algebra. Prentice-Hall
New Jersey, 1988, vol. 3.
[8] M. Mesbahi and M. Egerstedt, Graph theoretic methods in multiagent
networks. Princeton University Press, 2010.
[9] B. D. MacArthur and R. J. Sánchez-Garcı́a, “Spectral characteristicsof network redundancy,” Physical Review E, vol. 80, no. 2, p. 026117,
2009.
[10] A. Pogromsky, G. Santoboni, and H. Nijmeijer, “Partial synchronization: from symmetry towards stability,” Physica D: Nonlinear
Phenomena, vol. 172, no. 1, pp. 65–87, 2002.
[11] J. Zhou and Y. Ohsawa, “Improved swing equation and its properties
in synchronous generators,” Circuits and Systems, IEEE Transactions
on, vol. 56, no. 1, pp. 200–209, 2009.
[12] A. Rahmani, M. Ji, M. Mesbahi, and M. Egerstedt, “Controllability ofmulti-agent systems from a graph-theoretic perspective,” SIAM Journal
on Control and Optimization, vol. 48, no. 1, pp. 162–186, 2009.
[13] M. Egerstedt, “Controllability of networked systems,” in Mathematical
Theory of Networks and Systems, 2010.
[14] Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Controllability of complex
networks,” Nature, vol. 473, no. 7346, pp. 167–173, 2011.
[15] M. Bürger, D. Zelazo, and F. Allgöwer, “Hierarchical clustering ofdynamical networks using a saddle-point analysis,” Automatic Control,
IEEE Transactions on, vol. 58, no. 1, pp. 113–124, 2013.
[16] T. Ishizaki, K. Kashima, J.-i. Imura, and K. Aihara, “Model reduction
and clusterization of large-scale bidirectional networks,” AutomaticControl, IEEE Transactions on, vol. 59, no. 1, pp. 48–63, 2014.
[17] T. Ishizaki, K. Kashima, A. Girard, J.-i. Imura, L. Chen, and K. Aihara,“Clustered model reduction of positive directed networks,” Automatica, vol. 59, pp. 238–247, 2015.
[18] D. S. Bernstein, Matrix mathematics: theory, facts, and formulas.
Princeton University Press, 2009.
[19] Y. Susuki, I. Mezić, and T. Hikihara, “Coherent swing instability of
power grids,” Journal of nonlinear science, vol. 21, no. 3, pp. 403–
439, 2011.

[20] ——, “Coherent swing instability of power systems and cascading
failures,” in Power and Energy Society General Meeting, 2010 IEEE.
IEEE, 2010, pp. 1–8.