# Composition Rules for Strong Structural Controllability and Minimum Input
Problem in Diffusively-Coupled Networks

Nam-Jin Park<EMAIL_ADDRESS>Seong-Ho Kwon<EMAIL_ADDRESS>Yoo-Bin
Bae<EMAIL_ADDRESS>Byeong-Yeon Kim<EMAIL_ADDRESS>Kevin L. Moore
<EMAIL_ADDRESS>Hyo-Sung Ahncor<EMAIL_ADDRESS>School of Mechanical
Engineering, Gwangju Institute of Science and Technology (GIST), Gwangju,
Korea  Korea Railroad Research Institute (KRRI), Gyeonggi-do, Korea  Korea
Aerospace Research Institute (KARI), Daejeon, Korea  Korea Atomic Energy
Research Institute (KAERI), Daejeon, Korea  Department of Electrical
Engineering, Colorado School of Mines, Golden, CO, USA

###### Abstract

This paper presents new results and reinterpretation of existing conditions
for strong structural controllability in a structured network determined by
the zero/non-zero patterns of edges. For diffusively-coupled networks with
self-loops, we first establish a necessary and sufficient condition for strong
structural controllability, based on the concepts of dedicated and sharing
nodes. Subsequently, we define several conditions for strong structural
controllability across various graph types by decomposing them into disjoint
path graphs. We further extend our findings by introducing a composition rule,
facilitating the analysis of strong structural controllability in larger
networks. This rule allows us to determine the strong structural
controllability of connected graphs called pactus graphs (a generalization of
the well-known cactus graph) by consideration of the strong structural
controllability of its disjoint component graphs. In this process, we
introduce the notion of a component input node, which is a state node that
functions identically to an external input node. Based on this concept, we
present an algorithm with approximate polynomial complexity to determine the
minimum number of external input nodes required to maintain strong structural
controllability in a diffusively-coupled network with self-loops.

###### keywords:

Diffusively-coupled networks, strong structural controllability, composition
rule, minimum input problem

, , , , , and

[cor]Corresponding author at: School of Mechanical Engineering, Gwangju
Institute of Science and Technology (GIST), Gwangju, Korea

##  1 Introduction

Network controllability is a topic of active research, with many works in the
literature that investigate it from different points of view. From the
viewpoint of the structure of a network, it is common to use only some
information about the edges in a network. The problem of network
controllability for structured networks, which are characterized by the non-
zero/zero patterns of edges, was first introduced as structural
controllability in [1]. A structured network is considered structurally
controllable if it can be controlled for almost all choices of non-zero edge
weights, though it can still be uncontrollable for specific edge weight
combinations. This is known as the generic property [2, 3] of structural
controllability. To address this limitation, the concept of strong structural
controllability was introduced in [4] to guarantee full controllability by
considering all choices of edge weights. Specifically, a graph is strongly
structurally controllable (SSC) if its controllability can be determined based
only on the zero/non-zero patterns of edges, independent of the values of the
edge weights. In the literature, several methods have been proposed to
determine the strong structural controllability of structured networks, such
as PMI sequences [5, 6], zero forcing sets [7, 8], graph distance [9], and
maximum matching [10]. These methods from different perspectives are crucial
for a more comprehensive analysis of structured networks, which have diverse
applications in areas such as targeted networks [11], social networks [12],
and brain networks [13].

Related to strong structural controllability, the problems of input addition
and Minimum Input Problem (MIP) for control efficiency are important issues.
These problems have been studied in various approaches, such as the loopy zero
forcing set [14], structural balance [15], zero forcing number [16], and
constrained matching [17, 18]. In particular, the authors in [7, 18] proved
that the problem of finding minimum inputs for general networks is NP-hard.
However, it is known that for some special types of small networks, the MIP
can be solved in approximate polynomial time using heuristic algorithms, such
as greedy algorithm [19, 20] and independent strongly connected component
(iSSC) [21].

In this paper we provide a detailed graph-theoretical interpretation of strong
structural controllability, presenting new results as well as reinterpretation
of existing conditions. Based on these ideas, we offer several methods for
designing SSC networks as well as an algorithm with approximate polynomial
complexity to solve the MIP problem. We conclude this introduction with a
guide to the flow of ideas in the paper as well as a summary of our distinct
contributions.

###  1.1 Research Flow

This paper introduces several conditions for strong structural controllability
based on the new concept of dedicated & sharing nodes, which is a more
detailed concept of dilation [1] for structural controllability. For
diffusively-coupled networks with self-loops, we provide a reinterpretation of
Theorem 1 in [4], which provides the necessary and sufficient condition for
strong structural controllability, from the perspective of the dedicated node.
Based on [22], we provide conditions for strong structural controllability of
basic graph components, i.e., paths, cycles, and tree structures. In
particular, we provide an intuitive interpretation by decomposing these basic
graph components into paths and employing a composition rule for proof. The
composition rule refers to the principle that disjoint controllable components
can merge in a manner to ensure that the overall graph meets the
controllability conditions. From this perspective we develop a composition
process for pactus type graphs, which we will define in subsequent sections of
this paper. These graphs consist of basic graph components and represent a
more generalized concept than cactus, as defined in [23]. Finally, by
interpreting the properties of external input nodes from the perspective of
dedicated nodes, we define the concept of a component input node, which is a
state node that has the same property as an external input node. Based on
these two types of input nodes, we then propose an algorithm of approximate
polynomial complexity to solve MIP.

###  1.2 Contributions

Note that this paper is an advanced version of [22]. Although Section 3 in
this paper follows a similar logical flow to [22], there are some significant
differences. First, there is an error in [22, Corollary 1]. This paper
corrects this error and makes the results flawless. Furthermore, while [22] is
based on the sufficient condition for controllability, here we provide
necessary and sufficient conditions for strong structural controllability. The
contributions of this paper are as follows:

  * •

Different from the condition of strong structural controllability introduced
in [4], we provide a simplified condition for strong structural
controllability of undirected graphs of diffusively-coupled networks with
self-loops based on the notions of dedicated & sharing nodes.

  * •

The paper provides intuitive insights into network controllability by
decomposing basic components such as cycles and trees into path graphs and
analyzing them based on composition rules. Furthermore, we expand these
findings to more complex graph types, such as pactus, which consist of these
basic elements. This approach highlights the topological control paths within
these networks, providing clarity and enhanced understanding.

  * •

From the perspective of the dedicated & sharing nodes, we present the new
notion of a component input node, which is a state node that has the same
property as an external input node. Based on this notion, we devise an
algorithm for pactus type graphs that efficiently identifies the minimum
external input nodes necessary for strong structural controllability, offering
a deeper insight into such structured networks.

The paper is organized as follows. In Section 2, the preliminaries and the
problems of strong structural controllability are formulated. In Section 3,
the conditions for strong structural controllability of basic components and
pactus are presented. Section 4 develops an algorithm for solving MIP for
pactus graphs. Conclusions are presented in Section 5.

##  2 Preliminaries and Problem Formulations

We will consider undirected networks of diffusively-coupled states $x_{i}$ and
external inputs $u_{i}$ with self-loops:

$\displaystyle\dot{x}_{i}=-\sum_{j\in\mathcal{N}_{i}}a_{ij}(x_{i}-x_{j})+a_{ii}x_{i}+b_{i}u_{i},$
(1)

where $a_{ij}$ represents the diffusive couplings between states $x_{i}$ and
$x_{j}$, satisfying $a_{ij}=a_{ji}$, $\mathcal{N}_{i}$ denotes the set of
indices of the states $x_{j}$ for which $a_{ji}\neq 0$, and $b_{i}$ represents
the external input coupling of $x_{i}$. This paper assumes that for non-zero
values of $a_{ij}$, $a_{ij}$ is positive when $i\neq j$, and is nonzero and
negative when $i=j$ as per [8, 24]. The Laplacian matrix is defined as
$\mathcal{L}=\mathcal{A}-\mathcal{D}$, where
$\mathcal{A}\in\mathbb{R}^{n\times n}$ is the adjacency matrix consisting of
diffusive couplings $a_{ij}$ for $i\neq j$, and
$\mathcal{D}=diag(\mathcal{A}\mathds{1}_{n})\in\mathbb{R}^{n\times n}$. Let us
now define a self-loop matrix $\mathcal{S}\in\mathbb{R}^{n\times n}$, which is
the diagonal matrix consisting of $a_{ii}$ for $i\in\\{1,...,n\\}$. Then, the
diffusively-coupled network in (1) can be represented as:

$\displaystyle\dot{x}=\tilde{\mathcal{L}}x+Bu,$ (2)

where $x=(x_{1},\ldots,x_{n})^{T}\in\mathbb{R}^{n\times 1}$,
$u=(u_{1},\ldots,u_{m})^{T}\in\mathbb{R}^{m\times 1}$,
$\tilde{\mathcal{L}}=\mathcal{L}-\mathcal{S}\in\mathbb{R}^{n\times n}$ is the
modified Laplacian matrix, and
$B=[e_{1},e_{2},...,e_{m}]\in\mathbb{R}^{n\times m}$ is the input matrix
consisting of linearly independent standard column bases with appropriate
dimensions. Let the diffusively-coupled network matrix corresponding to (2) be
symbolically written as
$T=[\tilde{\mathcal{L}},B]\in\mathbb{R}^{n\times(n+m)}$. From the network
perspective, the modified Laplacian matrix $\tilde{\mathcal{L}}$ includes the
interactions of $n$ state nodes including each node’s own interaction. The
input matrix $B$ includes interactions between $m$ external input nodes and
state nodes. Hence, there are $n+m$ nodes in the network.

######  Remark 1.

The negative weight of the self-loops, $a_{ii}<0$ in (1), represents a
stabilizing force that prevents uncontrolled growth in the node’s state due to
self-influence. This assumption is commonly used to ensure the stability of
the network dynamics [25, 26], as a positive self-loop term can lead to
instability in the system.

For structured networks, we define a family set of modified Laplacian matrices
as $Q(\tilde{\mathcal{L}})$, which is determined by the same non-zero/zero
patterns as $\mathcal{A}$ and $\mathcal{S}$ in an element-wise fashion. Note
that since the structured network of (2) is determined only by the non-
zero/zero patterns of $\mathcal{A}$ and $\mathcal{S}$, all
$\mathcal{L}^{\prime}\in Q(\tilde{\mathcal{L}})$ have off-diagonal elements
with the same non-zero/zero pattern, but the diagonal elements of
$\mathcal{L}^{\prime}$ do not necessarily have the same non-zero/zero pattern.
From the viewpoint of control system design, we assume that the input matrix
$B$ is fixed since the variations of non-zero elements in $B$ do not affect
the controllability. Thus, the family set of network matrix $T$ is defined as
$Q(T):=[Q(\tilde{\mathcal{L}}),B]$. The network given by (2) is said to be
controllable if its controllability matrix has full row rank [27]. The
controllability matrix corresponding to $T=[\tilde{\mathcal{L}},B]$ is given
by
$\mathcal{C}_{\tilde{\mathcal{L}}}=[B,\tilde{\mathcal{L}}B,\tilde{\mathcal{L}}^{2}B,...,\tilde{\mathcal{L}}^{n-1}B]$.

From a graph point of view, the network given by (2) can be represented as a
graph:

$\displaystyle\mathcal{G}(T)=(\mathcal{V},\mathcal{E}),$ (3)

where $T=[t_{ij}]=[\tilde{\mathcal{L}},B]$, the node set $\mathcal{V}$ is the
union of the set of state nodes and the set of input nodes, i.e.,
$\mathcal{V}=\mathcal{V}^{S}\cup\mathcal{V}^{I}$ satisfying
$\mathcal{V}^{S}\cap\mathcal{V}^{I}=\emptyset$, and the edge set $\mathcal{E}$
is defined by the interactions between nodes $\mathcal{V}$. The graph
$\mathcal{G}(T)=(\mathcal{V},\mathcal{E})$ consists of a state graph
$\mathcal{G}^{S}$ and an interaction graph $\mathcal{G}^{I}$ as
$\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$, where $\mathcal{G}^{S}$
is the subgraph induced by $\mathcal{V}^{S}$, and $\mathcal{G}^{I}$ is the
graph representing the interactions between $\mathcal{V}^{S}$ and
$\mathcal{V}^{I}$. That is,
$\mathcal{G}^{S}=(\mathcal{V}^{S},\mathcal{E}^{S})$ and
$\mathcal{G}^{I}=(\mathcal{V},\mathcal{E}^{I})$, the direction of edges in
$\mathcal{E}^{S}$ is undirected, while the direction of edges in
$\mathcal{E}^{I}$ is directed such that $(i,j)\in\mathcal{E}^{I}$ with
$i\in\mathcal{V}^{I}$ and $j\in\mathcal{V}^{S}$. Also, since the input matrix
in (2) consists of the standard column bases, each external input node is
connected to only one state node. Then, the strong structural controllability
of a graph corresponding to the diffusively-coupled network given by (2) is
defined as:

######  Definition 2.

(Strong structural controllability) A graph $\mathcal{G}(T)$ of (2) is said to
be strongly structurally controllable (SSC) if all network matrices
$T^{{}^{\prime}}\in Q(T)$ are controllable.

We say that the graph $\mathcal{G}(T)$ is accessible if there exists a path
from $j\in\mathcal{V}^{I}$ to $i$ for any $i\in\mathcal{V}^{S}$. Note that if
there is no path from an external input node $i\in\mathcal{V}^{I}$ to a state
node $j\in\mathcal{V}^{S}$, then $j$ is not controllable. Without loss of
generality, this paper assumes that a graph $\mathcal{G}(T)$ is accessible, as
these are necessary for ensuring network controllability.

######  Lemma 3.

For a diffusively-coupled network given by (2), the matrix
$\tilde{\mathcal{L}}^{{}^{\prime}}$ of a graph $\mathcal{G}(T)$ has full rank
for all $\tilde{\mathcal{L}}^{{}^{\prime}}\in Q(\tilde{\mathcal{L}})$.

Let us consider the matrix $\tilde{\mathcal{L}}=\mathcal{L}-\mathcal{S}$ in
(2), where $\mathcal{L}\in\mathbb{R}^{n\times n}$ is a Laplacian matrix and
$\mathcal{S}\in\mathbb{R}^{n\times n}$ is a diagonal self-loop matrix. We
assume that the edges between two different state nodes have a positive sign,
so every $\mathcal{L}^{\prime}\in Q(\mathcal{L})$ must be positive semi-
definite, i.e., $x^{T}\mathcal{L}^{\prime}x\geq 0$ for all
$x\in\mathbb{R}^{n}$. Now, consider the matrix
$\mathcal{S}=diag[a_{11},...,a_{nn}]$. Since we assume that every state node
in $\mathcal{G}(T)$ has a self-loop with a negative sign, i.e., $a_{ii}<0$ for
all $i\in{1,...,n}$, every $\mathcal{S}$ must be negative definite, implying
that $x^{T}(-\mathcal{S})x>0$ for all $x\in\mathbb{R}^{n}\setminus\\{0\\}$.
Therefore, we obtain
$x^{T}\tilde{\mathcal{L}}^{\prime}x=x^{T}(\mathcal{L}^{\prime}-\mathcal{S})x>0$
for all $x\in\mathbb{R}^{n}\setminus\\{0\\}$, which means that
$\tilde{\mathcal{L}}^{\prime}$ is positive definite. Hence, every
$\tilde{\mathcal{L}}^{\prime}\in Q(\tilde{\mathcal{L}})$ has full rank.
$\square$

From the above lemma, it follows that every network matrix $T^{\prime}\in
Q(T)$ for the diffusively-coupled network with self-loops given by (2) also
has a full row rank.

Next, let the neighboring set of the set $\alpha\subseteq\mathcal{V}^{S}$ be
denoted as $\mathcal{N}(\alpha)=\bigcup_{j\in\alpha}\mathcal{N}_{j}$, which is
the union set of neighboring set of $j$ satisfying $j\in\alpha$. From [4,
Lemma 3], the conditions provided in [4, Theorem 1] provided can be simplified
for diffusively-coupled networks with self-loops as:

######  Theorem 4.

[4] The graph $\mathcal{G}(T)$ is SSC if and only if for all
$\alpha\subseteq\mathcal{V}^{S}$, there exists
$i\in\mathcal{N}(\alpha)$$\setminus$$\alpha$ having exactly one edge
$(i,j)\in\mathcal{E}$ with $j\in\alpha$ in $\mathcal{G}(T)$.111Note that in
this theorem and in our results below, it is necessary to consider all
$\alpha\subseteq\mathcal{V}^{S}$. The number of possible sets of $\alpha$ is
$2^{|V^{S}|}-1$.

For a more detailed analysis, we classify the node
$i\in\mathcal{N}(\alpha)$$\setminus$$\alpha$ as dedicated nodes and sharing
nodes for $\alpha\subseteq\mathcal{V}^{S}$.

######  Definition 5.

(Dedicated and Sharing nodes) A node
$i\in\mathcal{N}(\alpha)$$\setminus$$\alpha$ is a dedicated node of $\alpha$
if it satisfies $|\mathcal{N}_{i}\cap\alpha|=1$, or is a sharing node of
$\alpha$ if it satisfies $|\mathcal{N}_{i}\cap\alpha|>1$.

For an arbitrary $\alpha$ satisfying $\alpha\subseteq\mathcal{V}^{S}$, if a
node $i\in\mathcal{N}(\alpha)$$\setminus$$\alpha$ has exactly one edge
connected to $\alpha$, then the node $i$ is called a dedicated node of
$\alpha$. This statement is equivalent to the cardinality condition of
$|\mathcal{N}_{i}\cap\alpha|=1$. On the other hand, a node
$i\in\mathcal{N}(\alpha)$$\setminus$$\alpha$ is called a sharing node if the
node $i$ has more than one edge connected to $\alpha$. Using the concepts of
dedicated and sharing nodes, a reinterpretation of Theorem 1 is that a a graph
$\mathcal{G}(T)$ is SSC if and only if the set
$\mathcal{N}(\alpha)$$\setminus$$\alpha$ has at least one dedicated node for
all $\alpha\subseteq\mathcal{V}^{S}$. This is stated formally below in
Corollary 7.

For example, consider the graph $\mathcal{G}(T)$ depicted in Fig. 2(a). It is
shown that $\mathcal{V}^{S}=\\{1,2,3,4,5\\}$ and
$\mathcal{V}^{I}=\\{u_{1},u_{2}\\}$. Let $\alpha\subseteq\mathcal{V}^{S}$ be
$\alpha=\\{1,3\\}$. Then, we obtain
$\mathcal{N}(\alpha)$$\setminus$$\alpha=\\{2,u_{1}\\}$. Now, we need to check
whether the set $\mathcal{N}(\alpha)$$\setminus$$\alpha$ has a dedicated node
or not. For the node $2\in$ $\mathcal{N}(\alpha)$$\setminus$$\alpha$, we
obtain $\mathcal{N}_{2}=\\{1,3,4\\}$. Then, it follows that
$|\mathcal{N}_{2}\cap\alpha|=2$, which means that the node $2$ is a sharing
node since those have two edges $(2,1),(2,3)\in\mathcal{E}$ connected to
$1,3\in\alpha$, respectively. For the external input node $u_{1}\in$
$\mathcal{N}(\alpha)$$\setminus$$\alpha$, we obtain
$\mathcal{N}_{u_{1}}=\\{3\\}$. Then, we obtain
$|\mathcal{N}_{u_{1}}\cap\alpha|=1$, which means that $u_{1}$ is a dedicated
node of $\alpha$ because the node $u_{1}$ has exactly one edge
$(u_{1},3)\in\mathcal{E}$ connected to $3\in\alpha$. Hence, in case of
$\alpha=\\{1,3\\}$, there exists a dedicated node $u_{1}$. In the same way, if
the set $\mathcal{N}(\alpha)$$\setminus$$\alpha$ has at least one dedicated
node for all $\alpha\subseteq\mathcal{V}^{S}$, the graph $\mathcal{G}(T)$ is
determined to be a SSC graph.

######  Remark 6.

Note that the concept of dedicated & sharing node is an extended concept of
dilation [1] for structural controllability. More precisely, the authors in
[1] show that the condition of structural controllability is the absence of
dilation in a graph, but this condition is not sufficient for strong
structural controllability. Dedicated & sharing nodes are a more detailed
concept for determining the strong structural controllability.

##  3 Strongly Structurally Controllable Graphs

In this section, we provide several necessary and sufficient conditions for
strong structural controllability of basic graph components such as paths,
cycles, and tree structures. While there is a wealth of research on
determining controllability conditions for these graph types using concepts,
such as the zero forcing set [28] and structural balance [15], this paper
offers a reinterpretation of these existing conditions. This is driven by the
belief that alternative approaches to the same results can provide deeper
insights and different perspectives on the problem at hand. We specifically
analyze the controllability of basic components based on the notions of
dedicated and sharing nodes, employing composition rules to deepen the
analysis. With the notion of a dedicated node, Theorem 1 can be simplified as:

######  Corollary 7.

The graph $\mathcal{G}(T)$ is SSC if and only if there exists at least one
dedicated node in $\mathcal{N}(\alpha)$$\setminus$$\alpha$ for all
$\alpha\subseteq\mathcal{V}^{S}$.

The above Corollary 7 provides the necessary and sufficient condition for
strong structural controllability from the perspective of dedicated nodes. For
further analysis, the following proposition provides the condition for strong
structural controllability of the path graph, a basic component, as presented
in [4].

######  Proposition 8.

[4] Let us consider a path state graph
$\mathcal{G}^{S}=(\mathcal{V}^{S},\mathcal{E}^{S})$ with
$\mathcal{G}^{I}=(\mathcal{V}^{I},\mathcal{E}^{I})$. The graph
$\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$ is SSC if and only if
there exists an external input node connected to a terminal state node222In a
graph $\mathcal{G}(T)=(\mathcal{V},\mathcal{E})$, we say that a state node
$k\in\mathcal{V}^{S}$ is a terminal state node if it satisfies
$|\mathcal{N}_{k}|=1$ in $\mathcal{G}^{S}$..

$1$$2$$3$$4$$5$$u_{1}$$u_{2}$

$1$$2$$3$$4$$5$$u_{1}$$u_{2}$

Figure 1: Tree state graphs with two external input nodes.

$1$$2$$3$$4$$u_{1}$$u_{2}$

$1$$2$$3$$4$$u_{1}$$u_{2}$

Figure 2: Cycle state graphs with two external input nodes.

For further analysis of a larger graph, we define a bridge graph
$\mathcal{G}_{ij}^{S}$, which connects two disjoint graphs $\mathcal{G}_{i}$
and $\mathcal{G}_{j}$.

######  Definition 9.

(Bridge graph) A bridge graph is a state graph defined as
$\mathcal{G}_{ij}^{S}=(\mathcal{V}_{ij}^{S},\mathcal{E}_{ij}^{S}$), which
connects two disjoint state graphs $\mathcal{G}^{S}_{i}$ and
$\mathcal{G}^{S}_{j}$. If nodes $k\in\mathcal{V}^{S}_{i}$ and
$l\in\mathcal{V}^{S}_{j}$ are connected by an edge $(k,l)$, then
$(k,l)\in\mathcal{E}_{ij}^{S}$ and $k,l\in\mathcal{V}_{ij}^{S}$. We assume
that a state node $k\in\mathcal{V}^{S}_{i}$ is connected to a state node
$l\in\mathcal{V}^{S}_{j}$ by a one-to-one. Hence, $|\mathcal{E}_{ij}^{S}|$
satisfies the following boundary condition.

$\displaystyle 1\leq|\mathcal{E}_{ij}^{S}|\leq
min(|\mathcal{V}_{i}^{S}|,|\mathcal{V}_{j}^{S}|).$ (4)

For convenience, we first define the concept of neighbor components for a
given component $\mathcal{G}_{i}^{S}$ in a graph. The set of neighbor
components, denoted as $\mathcal{N}_{\mathcal{G}_{i}^{S}}$, includes the
indices $j$ for which there exists a non-empty bridge graph
$\mathcal{G}_{ij}^{S}$ connecting $\mathcal{G}_{i}^{S}$ to
$\mathcal{G}_{j}^{S}$. This is formally expressed as
$\mathcal{N}_{\mathcal{G}_{i}^{S}}=\\{j\mid\mathcal{G}_{ij}^{S}\neq\emptyset\\}$,
where each index $j$ in this set represents a component directly connected to
$\mathcal{G}_{i}^{S}$ by at least bridge edge. With the above notation, we say
that the graph $\mathcal{G}(T)=(\mathcal{V},\mathcal{E})$ is induced by
$m$-disjoint components $\mathcal{G}_{i}=(\mathcal{V}_{i},\mathcal{E}_{i})$
with bridge graph edges $\mathcal{E}_{ij}^{S}$ if
$\mathcal{V}={\bigcup}^{m}_{i=1}\mathcal{V}_{i}$ and
$\mathcal{E}={\bigcup}^{m}_{i=1}{\bigcup}_{j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}}(\mathcal{E}_{i}\cup\mathcal{E}_{ij}^{S})$.
Based on the concept above of induction, we now proceed to decompose larger
graphs into the basic components, i.e., path graphs, and explore their strong
structural controllability conditions.

######  Theorem 10.

Consider a tree state graph
$\mathcal{G}^{S}=(\mathcal{V}^{S},\mathcal{E}^{S})$ with
$\mathcal{G}^{I}=(\mathcal{V}^{I},\mathcal{E}^{I})$ satisfying
$|\mathcal{V}^{I}|=m\geq 2$. Then, the graph
$\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$ can be induced by
$m$-disjoint components $\mathcal{G}_{i}$ with $\mathcal{E}_{ij}^{S}$
satisfying $|\mathcal{E}_{ij}^{S}|=1$ and $|\mathcal{V}^{I}_{i}|=1$ for
$i\in\\{1,...,m\\}$ and $j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}$. The graph
$\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$ is SSC if and only if each
disjoint component $\mathcal{G}_{i},i\in\\{1,...,m\\}$ is SSC path graph
satisfying Proposition 8.

For if condition, let us assume that each disjoint component
$\mathcal{G}_{i},i\in\\{1,...,m\\}$ satisfies Proposition 8. Then, since each
$\mathcal{G}_{i}$ is SSC, the set
$\mathcal{N}(\alpha_{i})$$\setminus$$\alpha_{i}$ contains at least one
dedicated node for all $\alpha_{i}\subseteq\mathcal{V}_{i}^{S}$. Now, consider
the merged graph $\mathcal{G}(T)$ with the bridge edge
$(k,l)\in\mathcal{E}_{ij}^{S}$, where $k\in\mathcal{V}_{i}^{S}$ and
$l\in\mathcal{V}_{j}^{S}$ for $i\in\\{1,...,m\\}$ and
$j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}$. For the merged graph $\mathcal{G}(T)$
to be SSC, we only need to consider the existence of dedicated nodes in
$\mathcal{N}(\alpha)$$\setminus$$\alpha$ when $\alpha\subseteq\mathcal{V}^{S}$
contains at least one bridge node. Because after adding the bridge edge, each
set of in-neighboring nodes of a node in $\mathcal{V}^{S}$ remains unchanged
except for $\mathcal{N}_{k}$ and $\mathcal{N}_{l}$ in $\mathcal{G}(T)$.
However, since each disjoint component $\mathcal{G}_{i},i\in\\{1,...,m\\}$ is
SSC, even if the bridge node $k\in\mathcal{V}_{i}^{S}$ or
$l\in\mathcal{V}_{j}^{S}$ belongs to $\alpha\subseteq\mathcal{V}^{S}$, the set
$\mathcal{N}(\alpha)$$\setminus$$\alpha$ still has at least one dedicated node
in $\mathcal{V}_{i}$ or in $\mathcal{V}_{j}$. It follows that the existence of
at least one dedicated node in $\mathcal{N}(\alpha)$$\setminus$$\alpha$ is
independent of the bridge edge $(k,l)\in\mathcal{E}_{ij}^{S}$ satisfying
$|\mathcal{E}_{ij}^{S}|=1$ for all $\alpha\subseteq\mathcal{V}^{S}$.

For only if condition, in the merged graph $\mathcal{G}(T)$, let us suppose
that a disjoint component
$\mathcal{G}_{q}=\mathcal{G}_{q}^{S}\cup\mathcal{G}_{q}^{I},q\in\\{1,...,m\\}$
does not satisfy Proposition 8. Since the graph $\mathcal{G}(T)$ is a tree
graph, there always exists a state node $i\in\mathcal{V}^{S}$, which has out-
degree 3. Then, there always exists a case without a dedicated node in
$\mathcal{N}(\alpha)$$\setminus$$\alpha$ when
$\alpha=\mathcal{V}^{S}$$\setminus$$\\{i\\}$. $\square$ As an example of
Theorem 10, the graph $\mathcal{G}(T)$ depicted in Fig. 2(a) shows a tree
state graph $\mathcal{G}^{S}$ with two external input nodes
$u_{1},u_{2}\in\mathcal{V}^{I}$. In this case, the graph $\mathcal{G}(T)$ can
be induced by $2$-disjoint path graphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$
with a bridge edge $(2,4)\in\mathcal{E}_{12}$, i.e.,
$\mathcal{G}_{1}:u_{1}\rightarrow 3\leftrightarrow 2\leftrightarrow 1$ and
$\mathcal{G}_{2}:u_{2}\rightarrow 5\leftrightarrow 4$, where the symbols
$\rightarrow$ and $\leftrightarrow$ are used to denote directions of the
connection between nodes. It follows from Theorem 10 that the merged graph
$\mathcal{G}(T)$ is SSC since each disjoint component $\mathcal{G}_{1}$ and
$\mathcal{G}_{2}$ satisfies Proposition 8. However, the graph $\mathcal{G}(T)$
depicted in Fig. 2(b) can not be induced by 2-disjoint path graphs. In this
case, when $\alpha=\\{1,3\\}$, we obtain
$\mathcal{N}(\alpha)$$\setminus$$\alpha=\\{2\\}$. But the node $2$ is a
sharing node satisfying $|\mathcal{N}_{2}\cap\alpha|>1$, which is connected to
the nodes $1,3\in\alpha$, thus, the graph $\mathcal{G}(T)$ in Fig. 2(b) is not
SSC. With the result of Theorem 10, the following Corollary 11 can be
obtained:

######  Corollary 11.

Let two components $\mathcal{G}_{i}$ and $\mathcal{G}_{j}$ be SSC,
respectively. If there exists a bridge graph $\mathcal{G}_{ij}^{S}$ satisfying
$|\mathcal{E}_{ij}^{S}|=1$, then the merged graph
$\mathcal{G}(T)=\mathcal{G}_{i}\cup\mathcal{G}_{ij}^{S}\cup\mathcal{G}_{j}$ is
SSC, regardless of the location of the bridge edge.

The above corollary means that the existence of one bridge edge connecting two
disjoint SSC graphs is independent of the strong structural controllability of
the merged graph.

######  Theorem 12.

Consider a cycle state graph
$\mathcal{G}^{S}=(\mathcal{V}^{S},\mathcal{E}^{S})$ with
$\mathcal{G}^{I}=(\mathcal{V}^{I},\mathcal{E}^{I})$ satisfying
$|\mathcal{V}^{I}|=2$. The graph
$\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$ is SSC if and only if
there exists an edge $(k,l)\in\mathcal{E}$ with
$k,l\in\mathcal{N}(\mathcal{V}^{I})$.

Let us consider that a graph
$\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$ consists of a cycle state
graph $\mathcal{G}^{S}=(\mathcal{V}^{S},\mathcal{E}^{S})$ with
$\mathcal{G}^{I}=(\mathcal{V}^{I},\mathcal{E}^{I})$ satisfying
$|\mathcal{V}^{I}|=2$. Then, the graph $\mathcal{G}(T)$ can be induced by
$2$-disjoint components $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ with
$\mathcal{E}_{12}^{S}$ satisfying $|\mathcal{E}_{12}^{S}|=2$. Also, each
disjoint component $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ satisfies
Proposition 8. Thus, the sets $\mathcal{N}(\alpha_{1})$$\setminus$$\alpha_{1}$
and $\mathcal{N}(\alpha_{2})$$\setminus$$\alpha_{2}$ have at least one
dedicated node for all $\alpha_{1}\subseteq\mathcal{V}_{1}^{S}$ and
$\alpha_{2}\subseteq\mathcal{V}_{2}^{S}$, respectively. For the merged graph
$\mathcal{G}(T)$ to be SSC, we only need to consider the existence of
dedicated nodes in $\mathcal{N}(\alpha)$$\setminus$$\alpha$ when
$\alpha\subseteq\mathcal{V}^{S}$ contains at least one bridge node. Because
each set of in-neighboring nodes of a node in $\mathcal{V}^{S}$ remains
unchanged except for the nodes in $\mathcal{V}_{12}^{S}$. Now, start from
$\mathcal{G}_{1}\cup\mathcal{G}_{2}$, we gradually add two bridge edges step-
by-step for check the condition of Corollary 7. Let the bridge edges be
$\\{(k_{1},l_{1}),(k_{2},l_{2})\\}\in\mathcal{E}^{S}_{12}$, where
$k_{1},k_{2}\in\mathcal{V}_{1}^{S}$ and $l_{1},l_{2}\in\mathcal{V}_{2}^{S}$
satisfying $k_{1},l_{1}\notin\mathcal{N}(\mathcal{V}^{I})$.

For if condition, consider a merged graph $\mathcal{G}_{1}\cup\mathcal{G}_{2}$
with the bridge edge $(k_{1},l_{1})\in\mathcal{E}^{S}_{12}$. It follows from
Corollary 11 that if each $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ is SSC, the
merged graph $\mathcal{G}_{1}\cup\mathcal{G}_{2}$ with a bridge edge
$(k_{1},l_{1})\in\mathcal{E}_{12}^{S}$ is SSC. For the other bridge edge
$(k_{2},l_{2})\in\mathcal{E}^{S}_{12}$, suppose that the bridge nodes
$k_{2},l_{2}$ satisfy $k_{2},l_{2}\in\mathcal{N}(\mathcal{V}^{I})$. Then, each
set of in-neighboring nodes of nodes $k_{2}$ and $l_{2}$ always includes each
other, i.e., $k_{2}\in\mathcal{N}_{l_{2}}$ and $l_{2}\in\mathcal{N}_{k_{2}}$.
Hence, if $\alpha\subseteq\mathcal{V}^{S}$ contains $k_{2}$ or $l_{2}$, the
set $\mathcal{N}(\alpha)$$\setminus$$\alpha$ always contains at least one of
the nodes $k_{2}$ and $l_{2}$ with
$k_{2},l_{2}\in\mathcal{N}(\mathcal{V}^{I})$. However, if $\alpha$ contains a
node in $\mathcal{N}(\mathcal{V}^{I})$, there always exists at least one
dedicated node in $\mathcal{N}(\alpha)$$\setminus$$\alpha$, and this dedicated
node is always an external input node in $\mathcal{V}^{I}$. Therefore, the
graph $\mathcal{G}(T)$ is SSC. For only if condition, let us suppose that
$(k_{2},l_{2})\notin\mathcal{E}$ with
$k_{2},l_{2}\in\mathcal{N}(\mathcal{V}^{I})$. In this case, when choosing
$\alpha=\mathcal{V}^{S}$, we obtain
$\mathcal{N}(\alpha)$$\setminus$$\alpha=\\{k_{2},l_{2}\\}$. However, both
nodes $k_{2}$ and $l_{2}$ are sharing nodes satisfying
$|\mathcal{N}_{k_{2}}\cap\alpha|=|\mathcal{N}_{l_{2}}\cap\alpha|=2$. Hence,
from Corollary 7, the graph $\mathcal{G}(T)$ is not SSC. $\square$

For example, Fig. 2(a) shows a cycle state graph $\mathcal{G}^{S}$ with
$\mathcal{N}(\mathcal{V}^{I})=\\{2,3\\}$ and there exists an edge
$(2,3)\in\mathcal{E}$. According to Theorem 12, the graph
$\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$ is SSC. However, the graph
$\mathcal{G}(T)$ depicted in Fig. 2(b) shows
$\mathcal{N}(\mathcal{V}^{I})=\\{1,3\\}$ and there is no edge between the
nodes $1,3\in\mathcal{N}(\mathcal{V}^{I})$, i.e., $(1,3)\notin\mathcal{E}$. In
this case, when choosing
$\alpha=\mathcal{V}^{S}$$\setminus$$\mathcal{N}(\mathcal{V}^{I})=\\{2,4\\}$,
we obtain $\mathcal{N}(\alpha)$$\setminus$$\alpha=\\{1,3\\}$. It is clear that
nodes $1,3\in\mathcal{N}(\alpha)$$\setminus$$\alpha$, are sharing nodes
satisfying $|\mathcal{N}_{1}\cap\alpha|=|\mathcal{N}_{3}\cap\alpha|=2$. Hence,
according to Corollary 7, the graph $\mathcal{G}(T)$ in Fig. 2(b) is not SSC.
Note that if $\mathcal{G}^{S}$ is a cycle, two properly located external input
nodes are sufficient for the graph $\mathcal{G}(T)$ to be SSC, i.e., the
minimum number of external input nodes for the strong structural
controllability of $\mathcal{G}(T)$ is $2$.

With the above proof, Theorem 12 can be generalized as:

######  Theorem 13.

Let two disjoint components $\mathcal{G}_{i}$ and $\mathcal{G}_{j}$ be SSC
with path state graphs $\mathcal{G}^{S}_{i}$ and $\mathcal{G}^{S}_{j}$,
respectively. If there exists a bridge edge $(k,l)\in\mathcal{E}_{ij}^{S}$
satisfying $k,l\in\mathcal{N}(\mathcal{V}^{I})$, the merged graph
$\mathcal{G}_{i}\cup\mathcal{G}_{ij}^{S}\cup\mathcal{G}_{j}$ is SSC,
regardless of the existence of an additional bridge edge in
$\mathcal{E}_{ij}^{S}$.

The above Theorem 13 contains the condition of strong structural
controllability for a graph
$\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$ when $\mathcal{G}^{S}$ is
a cycle. Thus, Theorem 12 is a special case of Theorem 13. To extend our
results to larger graphs, we define a pactus as a structure consisting of
disjoint components interconnected by bridge graphs.

######  Definition 14.

(Pactus) A pactus is a connected graph defined as
$\mathcal{G}^{S}={\bigcup}^{m}_{i=1}{\bigcup}_{j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}}(\mathcal{G}_{i}^{S}\cup\mathcal{G}_{ij}^{S})$.
A pactus satisfies the following properties.

  1. 1.

$\mathcal{G}^{S}$ is induced by $m$-disjoint components $\mathcal{G}_{i}^{S}$
with $\mathcal{E}_{ij}^{S}$.

  2. 2.

Each $\mathcal{G}_{i}^{S},i\in\\{1,...,m\\}$, is either a path or a cycle.

  3. 3.

If $j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}$, $\mathcal{G}_{i}^{S}$ and
$\mathcal{G}_{j}^{S}$ are connected by at least one bridge edge
$(k,l)\in\mathcal{E}_{ij}^{S}$, where $k\in\mathcal{V}^{S}_{i}$,
$l\in\mathcal{V}^{S}_{j}$.

Note that the pactus is a more generalized concept than the cactus defined in
[23]. It means that the cactus is a special case of the pactus. For example,
the bridge edges between two disjoint components in pactus may be several
under the boundary condition given by (4), while the cactus has only one.
Based on the aforementioned lemmas, the following theorem can be established.

$\mathcal{G}_{1}$$\mathcal{G}_{2}$$\mathcal{G}_{3}$$\mathcal{G}_{4}$$\mathcal{G}_{12}^{S}$$\mathcal{G}_{23}^{S}$$\mathcal{G}_{34}^{S}$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$u_{7}$
Figure 3: A SSC graph $\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$ with
a pactus
$\mathcal{G}^{S}={\bigcup}^{4}_{i=1}{\bigcup}_{j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}}(\mathcal{G}_{i}^{S}\cup\mathcal{G}_{ij}^{S})$
satisfying $|\mathcal{E}_{ij}^{S}|=1$.

######  Theorem 15.

Let us consider a pactus $\mathcal{G}^{S}$ and suppose that each bridge graph
has only one bridge edge, i.e., $|\mathcal{E}_{ij}^{S}|=1$. The graph
$\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$ is SSC if each disjoint
component $\mathcal{G}_{i},i\in\\{1,...,m\\}$, is SSC.

The if condition can be proved by an induction of Corollary 11. Let a state
graph $\mathcal{G}^{S}$ be a pactus. Then, the pactus $\mathcal{G}^{S}$ can be
induced by $m$-disjoint components $\mathcal{G}_{i}^{S}$ with
$\mathcal{E}^{S}_{ij}$. Also, each $\mathcal{G}_{i}^{S}$ is either a path or a
cycle. Suppose that each disjoint component
$\mathcal{G}_{i}=\mathcal{G}_{i}^{S}\cup\mathcal{G}_{i}^{I},i\in\\{1,...,m\\}$
satisfies Proposition 8 (path) or Theorem 12 (cycle). From each disjoint
component point of view, it is clear that the set
$\mathcal{N}(\alpha_{i})$$\setminus$$\alpha_{i}$ has at least one dedicated
node for all $\alpha_{i}\subseteq\mathcal{V}_{i}^{S},i\in\\{1,...,m\\}$. Thus,
since each SSC component $\mathcal{G}_{i}^{S}$ and $\mathcal{G}_{j}^{S}$ is
connected by exactly one bridge edge $(k,l)\in\mathcal{E}_{ij}^{S}$ with
$k\in\mathcal{V}^{S}_{i}$ and $l\in\mathcal{V}^{S}_{j}$ for
$i\in\\{1,...,m\\}$ and $j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}$. By an
induction of Corollary 11, the merged graph $\mathcal{G}(T)$ is SSC, i.e., the
set $\mathcal{N}(\alpha)$$\setminus$$\alpha$ has at least one dedicated node
for all $\alpha\subseteq{\bigcup}^{m}_{i=1}\mathcal{V}_{i}^{S}$, which is
equivalent to $\alpha\subseteq\mathcal{V}^{S}$. $\square$

The above Theorem 15 shows a sufficient condition for the strong structural
controllability of pactus satisfying $|\mathcal{E}_{ij}^{S}|=1$, which is
interpreted from the perspective of each component. For example, let us
consider the pactus depicted in Fig. 3. According to Proposition 8,
$\mathcal{G}_{1}$ needs an external input node connected to node $1$ to be
SSC, i.e., $\mathcal{V}_{1}^{I}=\\{u_{1}\\}$. Since
$\mathcal{G}_{2},\mathcal{G}_{3}$, and $\mathcal{G}_{4}$ are cycles, each
component requires at least two properly located external input nodes to
satisfy Theorem 12, i.e., $\mathcal{V}^{I}_{2}=\\{u_{2},u_{3}\\}$,
$\mathcal{V}^{I}_{3}=\\{u_{4},u_{5}\\}$,
$\mathcal{V}^{I}_{4}=\\{u_{6},u_{7}\\}$. These results are shown in Fig. 3.
Hence, the graph $\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$ requires
seven external input nodes to satisfy Theorem 15, i.e.,
$\mathcal{V}^{I}={\bigcup}^{4}_{i=1}\mathcal{V}_{i}^{I}=\\{u_{1},u_{2},u_{3},u_{4},u_{5},u_{6},u_{7}\\}$.
Note that the locations of the external input nodes are not unique.

##  4 Strongly Structurally Controllable Graphs with Minimum External Input
Nodes

In this section, we first present the condition for achieving strong
structural controllability from the perspective of a single node.
Subsequently, a composition process of approximate polynomial complexity for
MIP is provided. For further analysis from a single node point of view, it is
necessary to examine whether a state node is guaranteed at least one dedicated
node. For this reason, we introduce the notion of SSC node, defined as a state
node that satisfies the condition of strong structural controllability, a
notion initially established in [29].

######  Definition 16.

[29] (SSC node) A state node $k\in\mathcal{V}_{i}^{S}$ is called a SSC node if
the set $\mathcal{N}(\alpha)$$\setminus$$\alpha$ has at least one dedicated
node for all $\alpha\subseteq\mathcal{V}_{i}^{S}$ satisfying $k\in\alpha$. The
set of SSC nodes in $\mathcal{G}^{S}_{i}$ be symbolically written as
$\mathcal{V}_{i}^{\text{\tiny SSC}}$.

For convenience, we say that a state node $k\in\mathcal{V}^{S}$ has a
dedicated node if the set $\mathcal{N}(\alpha)$$\setminus$$\alpha$ has at
least one dedicated node for all $\alpha\subseteq\mathcal{V}^{S}$ satisfying
$k\in\alpha$. For example, consider the graph depicted in Fig. 4(a). In this
case, the nodes $1,3\in\mathcal{V}^{S}$ are SSC nodes, which are guaranteed a
dedicated node from the external input nodes $u_{1}$ and $u_{2}$, i.e.,
$1,3\in\mathcal{V}^{\text{\tiny SSC}}$. In other words, if $\alpha$ contains
at least one SSC node, the set $\mathcal{N}(\alpha)$$\setminus$$\alpha$ always
has at least one dedicated node. Based on the concept of an SSC node, the
following corollary, which provides an interpretation of strong structural
controllability from the perspective of each component, is directly derived
from [29]:

######  Corollary 17.

Let us consider a pactus $\mathcal{G}^{S}=(\mathcal{V}^{S},\mathcal{E}^{S})$
induced by $m$-disjoint components
$\mathcal{G}_{i}^{S}=({\mathcal{V}}_{i}^{S},{\mathcal{E}}_{i}^{S})$ with
$\mathcal{E}_{ij}^{S}$ for $i\in\\{1,...,m\\}$ and
$j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}$. Then, the graph
$\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$ is SSC if and only if all
state nodes in each component are SSC nodes, i.e.,
${\bigcup}^{m}_{i=1}\mathcal{V}_{i}^{\text{\tiny SSC}}=\mathcal{V}^{S}$.

In the context of MIP, a precise understanding of the role of input nodes is
essential. The following remark provides the significance of external input
nodes, particularly from the perspective of dedicated nodes.

######  Remark 18.

For a graph $\mathcal{G}(T)=(\mathcal{V},\mathcal{E})$, consider a state node
$k\in\mathcal{V}^{S}$ that is connected to an external input node
$u\in\mathcal{V}^{I}$ with an edge $(u,k)\in\mathcal{E}$. Suppose a set
$\alpha\subseteq\mathcal{V}^{S}$ includes the state node $k$, i.e.,
$k\in\alpha$. Given the assumption that an external input node is connected to
exactly one state node, the node $u$ always meets the cardinality condition
$|\mathcal{N}_{u}\cap\alpha|=1$. Therefore, the external input node
$u\in\mathcal{V}^{I}$ ensures the existence of a dedicated node for its
connected state node $k\in\mathcal{V}^{S}$

As shown in Remark 18, the property of an external input node is to guarantee
the existence of a dedicated node for any state node to which it is connected.
Surprisingly, this role of an external input node can also be fulfilled by a
state node. More specifically, if a specific structural condition is satisfied
in a pactus, there exists a case that a state node $k\in\mathcal{V}_{i}^{S}$
in $\mathcal{G}_{i}$ guarantees the existence of a dedicated node of a state
node $l\in\mathcal{V}_{j}^{S}$ in another component $\mathcal{G}_{j}$, which
is adjacent to the node of $k$, i.e., $l\in\mathcal{N}_{k}$, we call such
state nodes component input nodes. With the above observation, the input nodes
can be classified as the external input nodes and the component input nodes.

######  Definition 19.

(External input node) A set of external input nodes in $\mathcal{G}_{i}$ is
symbolically written as $\mathcal{V}_{i}^{IE}$. If a node
$k\in\mathcal{V}_{i}^{I}$ guarantees a dedicated node of
$l\in\mathcal{V}^{S}_{i}$ with a directed edge $(k,l)\in\mathcal{E}$, the node
$k$ is called an external input node of $\mathcal{G}_{i}$, i.e.,
$k\in\mathcal{V}^{IE}_{i}$.

######  Definition 20.

(Component input node) A set of component input nodes in $\mathcal{G}_{i}$ is
symbolically written as $\mathcal{V}_{i}^{IC}$. Consider a graph
$\mathcal{G}(T)=\mathcal{G}_{i}\cup\mathcal{G}_{ij}^{S}\cup\mathcal{G}_{j}$.
If a node $k\in\mathcal{V}_{i}^{S}$ guarantees a dedicated node of
$l\in\mathcal{V}^{S}_{j}$ with an edge $(k,l)\in\mathcal{E}_{ij}^{S}$, the
node $k$ is called a component input node of $\mathcal{G}_{j}$, i.e.,
$k\in\mathcal{V}^{IC}_{j}$.

$\mathcal{G}_{1}$$\mathcal{G}_{2}$$\mathcal{G}_{12}^{S}$$1$$2$$3$$4$$5$$6$$7$$8$$9$$u_{1}$$u_{2}$

$\mathcal{G}_{2}$$4$$5$$6$$7$$8$$9$$3$$2$

Figure 4: Example of the SSC nodes and the component input nodes: (a) A graph
$\mathcal{G}(T)=\mathcal{G}_{1}\cup\mathcal{G}_{12}\cup\mathcal{G}_{2}$ with
$|\mathcal{V}^{IE}|=2$. (b) $\mathcal{G}_{2}$ with
$\mathcal{V}^{IC}_{2}=\\{2,3\\}$.

From the above definitions, the set of input nodes $\mathcal{V}^{I}$ is re-
defined as a union of the set of component input nodes and the set of external
input nodes, i.e., $\mathcal{V}^{I}=\mathcal{V}^{IE}\cup\mathcal{V}^{IC}$
satisfying $\mathcal{V}^{IE}\cap\mathcal{V}^{IC}=\emptyset$. For a pactus
given by
$\mathcal{G}^{S}={\bigcup}^{m}_{i=1}{\bigcup}_{j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}}(\mathcal{G}_{i}^{S}\cup\mathcal{G}_{ij}^{S})$,
The following theorem provides the necessary and sufficient condition for the
component input nodes in a graph
$\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$.

######  Theorem 21.

Consider a graph $\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$ with a
pactus $\mathcal{G}^{S}$. Then, the state nodes in
$\mathcal{V}_{i}^{S}\cap\mathcal{V}_{ij}^{S}$, are the component input nodes
of $\mathcal{G}_{j}$, i.e.,
$\mathcal{V}_{j}^{IC}=\mathcal{V}_{i}^{S}\cap\mathcal{V}_{ij}^{S}$, if and
only if
${\bigcup}_{j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}}(\mathcal{G}_{i}\cup\mathcal{G}_{ij}^{S})$
is SSC for $i\in\\{1,...,m\\}$.

Let the subgraph
${\bigcup}_{j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}}(\mathcal{G}_{i}\cup\mathcal{G}_{ij}^{S})$
be denoted as
$\bar{\mathcal{G}}_{i}=(\bar{\mathcal{V}}_{i},\bar{\mathcal{E}}_{i})$ for
$i\in\\{1,...,m\\}$. For if condition, suppose that $\bar{\mathcal{G}}_{i}$ is
SSC for each $i\in\\{1,...,m\\}$. According to Definition 16 and Corollary 17,
it follows that all state nodes in $\bar{\mathcal{V}}_{i}$ are SSC nodes.
Obviously, any bridge nodes $k,l\in\mathcal{V}_{ij}^{S}$ satisfying
$k\in\mathcal{N}_{l}$ are also SSC nodes. This ensures that the node
$k\in\mathcal{V}^{S}_{i}$ guarantees the existence of a dedicated node of the
node $l\in\mathcal{V}^{S}_{j}$. Hence, by Definition 20, the bridge nodes in
$\mathcal{V}_{i}^{S}\cap\mathcal{V}_{ij}^{S}$ are the component input nodes of
$\mathcal{G}_{j}$, i.e.,
$\mathcal{V}_{j}^{IC}=\mathcal{V}_{i}^{S}\cap\mathcal{V}_{ij}^{S}$.

For the only if condition, suppose $\bar{\mathcal{G}}_{i}$ is not SSC for some
$i\in\\{1,...,m\\}$. Note that if $\bar{\mathcal{G}}_{i}$ is SSC, then
$\mathcal{G}_{i}$ must also be SSC, but the converse is not necessarily true.
Let us consider the case where $\mathcal{G}_{i}$ is SSC. Under this
assumption, the bridge nodes in $\mathcal{V}_{i}^{S}\cap\mathcal{V}_{ij}^{S}$
are SSC nodes. However, the assumption that $\bar{\mathcal{G}}_{i}$ is not SSC
implies that there exists at least one bridge node in
$\mathcal{V}_{j}^{S}\cap\mathcal{V}_{ij}^{S}$ that is not an SSC node. This
results in a case where there is no dedicated node for some subsets
$\alpha\subseteq\mathcal{V}^{S}$ including a node in
$\mathcal{V}_{j}^{S}\cap\mathcal{V}_{ij}^{S}$. $\square$

Note that if Theorem 21 is satisfied, the set of component input nodes is
defined as $\mathcal{V}^{IC}_{j}=\mathcal{V}^{S}_{i}\cap\mathcal{V}^{S}_{ij}$
for $i\in\\{1,...,m\\}$ and $j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}$. This
implies that the component input nodes of $\mathcal{G}_{j}$ can be determined
only by its adjacent component
$\mathcal{G}_{i},i\in\mathcal{N}_{\mathcal{G}_{j}^{S}}$. For example, in the
graph $\mathcal{G}(T)$ depicted in Fig. 4(a), consider the SSC subgraph
$\mathcal{G}_{1}\cup\mathcal{G}_{12}^{S}$ satisfying Theorem 10. Then,
according to Theorem 21, the nodes
$2,3\in\mathcal{V}_{1}^{S}\cap\mathcal{V}_{12}^{S}$ are the component input
nodes of $\mathcal{G}_{2}$, i.e., $\mathcal{V}_{2}^{IC}=\\{2,3\\}$. From the
viewpoint of $\mathcal{G}_{2}$, the graph depicted in Fig. 4(a) can be
expressed as shown in Fig. 4(b). Note that the property of an external input
node and component input node is equivalent to the existence of a dedicated
node. Now, let us suppose that the graph $\mathcal{G}_{2}$ in Fig. 4(b)
satisfies Theorem 12 by an additional properly located external input node
connected to one of the nodes $5,7$, and $9$. Then, all state nodes in
$\mathcal{G}(T)$ become SSC nodes, it follows from Corollary 17 that
$\mathcal{G}(T)$ is SSC. In this manner, based on the concept of component
input node, SSC graphs with the minimum number of external input nodes can be
designed by adding additional proper external input nodes.

######  Remark 22.

While most existing literature on the MIP for structured networks primarily
focuses on external input nodes, our paper introduces a novel concept of
component input nodes. Despite being state nodes, these component input nodes
function identically to external input nodes. Based on the notions of
dedicated and sharing nodes, we demonstrate that these nodes indeed assure the
presence of dedicated nodes, thereby playing a role equivalent to external
input nodes. It is important to note that this finding does not invalidate
previous studies concentrated on external input nodes for the MIP. Instead, it
implies that in certain graph structures, control paths emanating from
external input nodes may inherently incorporate the component input nodes we
define. This insight provides a fresh perspective on the topological formation
of control paths, offering significant contributions and broadening existing
methodologies in the field.

For a graph $\mathcal{G}(T)=\mathcal{G}^{S}\cup\mathcal{G}^{I}$, the minimum
number of external input nodes in $\mathcal{V}^{I}$ for the strong structural
controllability is symbolically written as $\min{|\mathcal{V}^{IE}|}$. Note
that it follows from Proposition 8, Theorem 10, and Theorem 12 that
$\min{|\mathcal{V}^{I}|}$ of path, tree, and cycle are $1$, $m$, and $2$,
respectively. For a general type of pactus, here we propose a composition
algorithm of polynomial complexity that can uniquely determine the minimum
number of external input nodes while maintaining strong structural
controllability.

The algorithm starts with a decomposition process, which involves breaking
down a pactus into its basic components. This process sequentially classifies
the structure of the given pactus, represented as
$\mathcal{G}^{S}={\bigcup}^{m}_{i=1}{\bigcup}_{j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}}(\mathcal{G}_{i}^{S}\cup\mathcal{G}_{ij}^{S})$,
into specific types in the decomposition process. In this decomposition
process, the graph $\bar{\mathcal{G}}_{i}^{S}$ denotes a union of state graphs
of the $i$-th component and its bridge graph, i.e.,
$\bar{\mathcal{G}}_{i}^{S}:=\mathcal{G}_{i}^{S}\cup\mathcal{G}_{i(i+1)}^{S}$,
where $i+1\in\mathcal{N}_{\mathcal{G}_{i}^{S}}$. We classify graph types of
$\bar{\mathcal{G}}_{i}^{S}$ as path-type, tree-type, and cycle-type. The graph
$\bar{\mathcal{G}}_{i}^{S}$ is path-type and tree-type if
$\bar{\mathcal{G}}_{i}^{S}$ is a path and a tree graph, respectively.
Furthermore, $\bar{\mathcal{G}}_{i}^{S}$ is cycle-type if
$\bar{\mathcal{G}}_{i}^{S}$ contains a cycle graph. The algorithm continues
with a composition process, which involves methodically adding the minimum
number of external input nodes to each component. This process is conducted
step-by-step, following the guidelines established in Proposition 8, Theorem
10, and Theorem 12. Accordingly, based on Theorem 21, the set of component
input nodes for each stage is determined as
$\mathcal{V}_{i+1}^{IC}:=\mathcal{V}_{i}^{S}\cap\mathcal{V}^{S}_{i(i+1)}$,
where $i+1\in\mathcal{N}_{\mathcal{G}_{i}^{S}}$. Utilizing the above
principles, the graph composition algorithm for the general type of a pactus
is outlined in Algorithm 1.

Algorithm 1

1:Decomposition:

2:a pactus
$\mathcal{G}^{S}:={\bigcup}^{m}_{i=1}{\bigcup}_{j\in\mathcal{N}_{\mathcal{G}_{i}^{S}}}(\mathcal{G}_{i}^{S}\cup\mathcal{G}_{ij}^{S})$,
$\mathcal{V}^{IE}=\emptyset$

3:$i=0$

4:for $i=i+1$ do

5: if $i<m$ then

6:
$\bar{\mathcal{G}}_{i}^{S}:=\mathcal{G}_{i}^{S}\cup\mathcal{G}_{i(i+1)}^{S}$
where $i+1\in\mathcal{N}_{\mathcal{G}_{i}^{S}}$

7: else if $i=m$ then

8: $\bar{\mathcal{G}}_{i}:=\mathcal{G}_{i}^{S}$

9: else

10: goto composition

11: end if

12:end for$\triangleright$ End for $i$

13:composition:

14:$i=0$

15:for $i=i+1$ do

16: if $\bar{\mathcal{G}}_{i}^{S}$ is not SSC then

17: switch graph type of $\bar{\mathcal{G}}_{i}^{S}$

18: case path-type

19: add $\min{|\mathcal{V}^{IE}_{i}|}$ to satisfy Proposition 8

20: case tree-type

21: add $\min{|\mathcal{V}^{IE}_{i}|}$ to satisfy Theorem 10

22: case cycle-type

23: add $\min{|\mathcal{V}^{IE}_{i}|}$ to satisfy Theorem 12

24: end if

25: if $i<m$ then

26: update
$\mathcal{V}_{i+1}^{IC}:=\mathcal{V}_{i}^{S}\cap\mathcal{V}^{S}_{i(i+1)}$

27:
$\bar{\mathcal{G}}_{i}:=\bar{\mathcal{G}}_{i}^{S}\cup\bar{\mathcal{G}}_{i}^{I}$

28: else

29: goto end

30: end if

31:end for$\triangleright$ End for $i$

32:_end_ :

33:output $\mathcal{G}(T)^{out}=\bigcup^{m}_{i=1}\bar{\mathcal{G}}_{i}$ with
$min|\mathcal{V}^{IE}|$

As a topological example of Algorithm 1, let us consider the pactus
$\mathcal{G}^{S}=(\mathcal{V}^{S},\mathcal{E}^{S})$ depicted in Fig. 5(a)
consisting of four disjoint components with bridge edges. In decomposition
process, the pactus $\mathcal{G}^{S}$ is decomposed into disjoint components
and bridge graphs. In composition process, for each
$\bar{\mathcal{G}}_{i}=\bar{\mathcal{G}}_{i}^{S}\cup\bar{\mathcal{G}}_{i}^{I},i\in\\{1,2,3,4\\}$,
additional external input nodes are added at proper locations to guarantee the
existence of dedicated nodes for all
$\alpha\subseteq\bar{\mathcal{V}}_{i}^{S}$, i.e, the SSC nodes in
$\mathcal{G}$ will expand sequentially. As a result, the output graph
$\mathcal{G}^{out}$ in Algorithm 1 satisfies Corollary 17, which is equivalent
to satisfying Theorem 1. For intuition, the blue marked state nodes in Fig. 5
are the SSC nodes.

  * •

Step 1: Since
$\bar{\mathcal{G}}_{1}^{S}=\mathcal{G}_{1}^{S}\cup\mathcal{G}_{12}^{S}$ is a
tree-type, two additional external input nodes
$u_{1},u_{2}\in\mathcal{V}_{1}^{IE}$ need to be connected at node $1$ and $3$
to satisfy Theorem 10. After that, all state nodes of $\bar{\mathcal{G}}_{1}$
are SSC nodes as shown in Fig. 5(b), i.e., $\bar{\mathcal{V}}_{1}^{\text{\tiny
SSC}}=\\{1,2,3,4,6\\}$.

  * •

Step 2:
$\bar{\mathcal{G}}_{2}^{S}=\mathcal{G}_{2}^{S}\cup\mathcal{G}_{23}^{S}$ is a
cycle-type. It follows from Theorem 21 that the component input nodes of
$\bar{\mathcal{G}}_{2}$ are $2,3\in\bar{\mathcal{V}}_{2}^{IC}$. Hence, one
external input node $u_{3}\in\mathcal{V}_{2}^{IE}$ needs to be connected to
node $5$, $7$ or $9$ to satisfy Theorem 12 (we choose node $7$). After that,
all state nodes of $\bar{\mathcal{G}}_{2}$ are SSC nodes as shown in Fig.
5(c), i.e., $\bar{\mathcal{V}}_{2}^{\text{\tiny
SSC}}=\\{4,5,6,7,8,9,10,12\\}$.

  * •

Step 3: Since
$\bar{\mathcal{G}}_{3}^{S}=\mathcal{G}_{3}^{S}\cup\mathcal{G}_{34}^{S}$ is a
cycle-type, two input nodes are needed to satisfy Theorem 12. According to
Theorem 21, the component input nodes of $\bar{\mathcal{G}}_{3}$ are
$4,9\in\bar{\mathcal{V}}_{3}^{IC}$. Hence, $\bar{\mathcal{G}}_{3}$ already
satisfies Theorem 12 without additional external input nodes since there
exists an edge $(10,12)\in\bar{\mathcal{E}}_{3}$ between the nodes
$10,12\in\mathcal{N}(\bar{\mathcal{V}}_{3}^{IC})$. Therefore, all state nodes
of $\bar{\mathcal{G}}_{3}$ are SSC nodes as shown in Fig. 5(d), i.e.,
$\bar{\mathcal{V}}_{3}^{\text{\tiny SSC}}=\\{10,11,12,13\\}$.

  * •

Step 4: $\bar{\mathcal{G}}_{4}^{S}=\mathcal{G}_{4}^{S}$ is a cycle-type, two
input nodes are needed to satisfy Theorem 12. According to Theorem 21, the
component input node of $\bar{\mathcal{G}}_{4}$ is
$12\in\bar{\mathcal{V}}_{4}^{IC}$. Thus, one external input node
$u_{4}\in\mathcal{V}_{4}^{IE}$ needs to be added at node $14$ or $16$ to
satisfy Theorem 12 (we choose node $14$). After that, all state nodes of
$\bar{\mathcal{G}}_{4}$ are SSC nodes as shown in Fig. 5(e), i.e.,
$\bar{\mathcal{V}}_{4}^{\text{\tiny SSC}}=\\{13,14,15,16\\}$.

Finally, all the state nodes in $\mathcal{V}^{S}$ are the SSC nodes, i.e.,
$\bar{\mathcal{V}}^{\text{\tiny SSC}}=\mathcal{V}^{S}$, where
$\bar{\mathcal{V}}^{\text{\tiny
SSC}}={\bigcup}^{4}_{i=1}\bar{\mathcal{V}}_{i}^{\text{\tiny SSC}}$, From
Corollary 17, it follows that the output graph shown in Fig. 5(f) is SSC with
minimum number of external input nodes.

$\mathcal{G}_{1}$$\mathcal{G}_{2}$$\mathcal{G}_{3}$$\mathcal{G}_{4}$$\mathcal{G}_{12}$$\mathcal{G}_{23}$$\mathcal{G}_{34}$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$
(a) Initial : A pactus $\mathcal{G}^{S}$

$\mathcal{G}_{1}$$\mathcal{G}_{2}$$\mathcal{G}_{3}$$\mathcal{G}_{4}$$\mathcal{G}_{12}$$\mathcal{G}_{23}$$\mathcal{G}_{34}$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$u_{1}$$u_{2}$
(b) Step 1 : $\bar{\mathcal{G}}_{1}=\mathcal{G}_{1}\cup\mathcal{G}_{12}$

$\mathcal{G}_{2}$$\mathcal{G}_{3}$$\mathcal{G}_{4}$$\mathcal{G}_{12}$$\mathcal{G}_{23}$$\mathcal{G}_{34}$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$u_{3}$
(c) Step 2 : $\bar{\mathcal{G}}_{2}=\mathcal{G}_{2}\cup\mathcal{G}_{23}$

$\mathcal{G}_{3}$$\mathcal{G}_{4}$$\mathcal{G}_{23}$$\mathcal{G}_{34}$$4$$9$$10$$11$$12$$13$$14$$15$$16$
(d) Step 3 : $\bar{\mathcal{G}}_{3}=\mathcal{G}_{3}\cup\mathcal{G}_{34}$

$\mathcal{G}_{4}$$\mathcal{G}_{34}$$12$$13$$14$$15$$16$$u_{4}$ (e) Step 4 :
$\bar{\mathcal{G}}_{4}=\mathcal{G}_{4}$

$\mathcal{G}_{1}$$\mathcal{G}_{2}$$\mathcal{G}_{3}$$\mathcal{G}_{4}$$\mathcal{G}_{12}$$\mathcal{G}_{23}$$\mathcal{G}_{34}$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$u_{1}$$u_{2}$$u_{3}$$u_{4}$
(f) Final :
$\mathcal{G}(T)^{out}=\bar{\mathcal{G}}_{1}\cup\bar{\mathcal{G}}_{2}\cup\bar{\mathcal{G}}_{3}\cup\bar{\mathcal{G}}_{4}$

Figure 5: Topological example of Algorithm 1, where the blue-marked nodes
represent the SSC nodes.

######  Remark 23.

The Algorithm 1 provides the graph-theoretic method to ensure the strong
structural controllability of $\mathcal{G}(T)=(\mathcal{V},\mathcal{E})$ with
the minimum number of external input nodes. Similarly, for structural
controllability, a method of finding the minimum number of leaders (inputs)
has been developed in [21], and the complexity of Theorem 2 in [21] is
$\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$. However, the complexity of
Algorithm 1 is $\mathcal{O}(m)$, where $m$ is the number of disjoint
components constituting a pactus. Note that $m$ is equal to or less than
$|\mathcal{V}|$ because the simplest structure of a pactus is a path, e.g.,
each disjoint component in pactus has only one state node, see Definition 14.

##  5 Conclusion

This paper delves into the strong structural controllability of undirected
graphs in diffusively-coupled networks with self-loops. Initially, we
establish necessary and sufficient conditions for strong structural
controllability, using the concepts of dedicated and sharing nodes. Following
this, we reinterpret existing results on the controllability of basic
components through composition rules applied to disjoint path graphs. This
approach provides insights into how control paths are topologically
configured. Using the composition rule, our findings are then extended to
pactus graphs, which comprise basic components. Finally, we present an
algorithm for addressing the MIP for pactus graphs, based on the concept of a
component input node, which has the same properties as an external input node.
As our future work, the research presented here can be expanded to include
observability, considering its duality with controllability. Observability in
structured networks is critical, especially in the context of determining the
minimal number of measurements necessary for state estimation in diffusively-
coupled networks. These extensions are earmarked for future exploration.

## Acknowledgment

This work was supported by both the Institute of Planning and Evaluation for
Technology (IPET) of Korea under grant 1545026393 and the National Research
Foundation of Korea (NRF) grant funded by the Korea government (MSIT)
(2022R1A2B5B03001459).

## References

  * [1] Ching-Tai Lin.  Structural controllability.  IEEE Transactions on Automatic Control, 19(3):201–208, 1974.
  * [2] Jean-Michel Dion, Christian Commault, and Jacob Van der Woude.  Generic properties and control of linear structured systems: a survey.  Automatica, 39(7):1125–1144, 2003.
  * [3] Nam-Jin Park, Yeong-Ung Kim, and Hyo-Sung Ahn.  Fixed node determination and analysis in directed acyclic graphs of structured networks.  Submitted to Journal of the Franklin Institute, 2023.
  * [4] Hirokazu Mayeda and Takashi Yamada.  Strong structural controllability.  SIAM Journal on Control and Optimization, 17(1):123–138, 1979.
  * [5] A Yasin Yazicioglu, Waseem Abbas, and Magnus Egerstedt.  A tight lower bound on the controllability of networks with multiple leaders.  In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pages 1978–1983. IEEE, 2012.
  * [6] AY Yazıcıoğlu, Waseem Abbas, and Magnus Egerstedt.  Graph distances and controllability of networks.  IEEE Transactions on Automatic Control, 61(12):4125–4130, 2016\.
  * [7] Shima Sadat Mousavi, Mohammad Haeri, and Mehran Mesbahi.  On the structural and strong structural controllability of undirected networks.  IEEE Transactions on Automatic Control, 63(7):2234–2241, 2017.
  * [8] Yasin Yazıcıoğlu, Mudassir Shabbir, Waseem Abbas, and Xenofon Koutsoukos.  Strong structural controllability of diffusively coupled networks: Comparison of bounds based on distances and zero forcing.  In 2020 59th IEEE Conference on Decision and Control (CDC), pages 566–571. IEEE, 2020.
  * [9] Shuo Zhang, Ming Cao, and M Kanat Camlibel.  Upper and lower bounds for controllable subspaces of networks of diffusively coupled agents.  IEEE Transactions on Automatic control, 59(3):745–750, 2013.
  * [10] Mudassir Shabbir, Waseem Abbas, and Yasin Yazıcıoğlu.  On the computation of the distance-based lower bound on strong structural controllability in networks.  In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 5468–5473. IEEE, 2019.
  * [11] Nima Monshizadeh, Kanat Camlibel, and Harry Trentelman.  Strong targeted controllability of dynamical networks.  In 2015 54th IEEE Conference on Decision and Control (CDC), pages 4782–4787. IEEE, 2015.
  * [12] Bruno Requião da Cunha and Sebastián Gonçalves.  Topology, robustness, and structural controllability of the brazilian federal police criminal intelligence network.  Applied network science, 3(1):1–20, 2018.
  * [13] Shi Gu, Fabio Pasqualetti, Matthew Cieslak, Qawi K Telesford, Alfred B Yu, Ari E Kahn, John D Medaglia, Jean M Vettel, Michael B Miller, Scott T Grafton, et al.  Controllability of structural brain networks.  Nature communications, 6(1):1–10, 2015.
  * [14] Jiajia Jia, Henk J van Waarde, Harry L Trentelman, and M Kanat Camlibel.  A unifying framework for strong structural controllability.  IEEE Transactions on Automatic Control, 66(1):391–398, 2020.
  * [15] Baike She, Siddhartha Mehta, Chau Ton, and Zhen Kan.  Controllability ensured leader group selection on signed multiagent networks.  IEEE Transactions on Cybernetics, 50(1):222–232, 2018.
  * [16] Nima Monshizadeh, Shuo Zhang, and M Kanat Camlibel.  Zero forcing sets and controllability of dynamical systems defined on graphs.  IEEE Transactions on Automatic Control, 59(9):2562–2567, 2014.
  * [17] Airlie Chapman and Mehran Mesbahi.  On strong structural controllability of networked systems: A constrained matching approach.  In 2013 American Control Conference, pages 6126–6131. IEEE, 2013\.
  * [18] Maguy Trefois and Jean-Charles Delvenne.  Zero forcing number, constrained matchings and strong structural controllability.  Linear Algebra and its Applications, 484:199–218, 2015.
  * [19] Alex Olshevsky.  Minimal controllability problems.  IEEE Transactions on Control of Network Systems, 1(3):249–258, 2014\.
  * [20] Shana Moothedath, Prasanna Chaporkar, and Madhu N Belur.  A flow-network-based polynomial-time approximation algorithm for the minimum constrained input structural controllability problem.  IEEE Transactions on Automatic Control, 63(9):3151–3158, 2018.
  * [21] Yongqiang Guan, Aming Li, and Long Wang.  Structural controllability of directed signed networks.  IEEE Transactions on Control of Network Systems, 8(3):1189–1200, 2021.
  * [22] Hyo-Sung Ahn, Kevin L Moore, Seong-Ho Kwon, Quoc Van Tran, Byeong-Yeon Kim, and Kwang-Kyo Oh.  Topological controllability of undirected networks of diffusively-coupled agents.  In 2019 58th Annual Conference of the Society of Instrument and Control Engineers of Japan (SICE), pages 673–678. IEEE, 2019.
  * [23] Tommaso Menara, Danielle S Bassett, and Fabio Pasqualetti.  Structural controllability of symmetric networks.  IEEE Transactions on Automatic Control, 64(9):3740–3747, 2018.
  * [24] Mudassir Shabbir, Waseem Abbas, Yasin Yazicioglu, and Xenofon Koutsoukos.  Computation of the distance-based bound on strong structural controllability in networks.  IEEE Transactions on Automatic Control, 2022.
  * [25] Murat Arcak.  Diagonal stability on cactus graphs and application to network stability analysis.  IEEE Transactions on Automatic Control, 56(12):2766–2777, 2011\.
  * [26] Eugenius Kaszkurewicz and Amit Bhaya.  Matrix diagonal stability in systems and computation.  Springer Science & Business Media, 2012.
  * [27] Wilson J Rugh.  Linear system theory.  Prentice-Hall, Inc., 1996.
  * [28] Shima Sadat Mousavi, Mohammad Haeri, and Mehran Mesbahi.  Strong structural controllability of signed networks.  In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 4557–4562. IEEE, 2019.
  * [29] Nam-Jin Park, Yeong-Ung Kim, Hyo-Sung Ahn, and Kevin L. Moore.  Strong Structural Controllability and Observability of Individual Nodes: A Graph-Theoretical Approach.  IEEE Transactions on Automatic Control, 2023.


# A semi-finite proof of Jacobi’s triple product identity

Jun-Ming Zhu  Department of Mathematics, Luoyang Normal University, Luoyang
City, Henan Province 471022, China<EMAIL_ADDRESS>
###### Abstract.

Jacobi’s triple product identity is proved from one of Euler’s $q$-exponential
functions in an elementary way.

Keywords: Jacobi’s triple product identity; Euler’s $q$-exponential function;
semi-finite.
MSC (2010): 33D15, 11F27.

##  1\. Introduction

We suppose $|q|<1$ and, as usual, the $q$-Pochhammer symbols are defined
respectively by

$(a;q)_{\infty}=\prod_{n=0}^{\infty}(1-aq^{n})\qquad\mbox{and}\qquad(a;q)_{n}=\frac{(a;q)_{\infty}}{(aq^{n};q)_{\infty}}$

for any integer $n$. Jacobi’s triple product identity is one of the most
important series-product identities. We state it in the following theorem.

######  Theorem 1.1.

For any complex number $z\neq 0$, we have

(1.1)
$(q;q)_{\infty}(-q/z;q)_{\infty}(-z;q)_{\infty}=\sum_{n=-\infty}^{\infty}q^{n(n-1)/2}z^{n}.$

Bellman said in [3, p. 42] that there are no simple proofs known of the
complete result. After that, Andrews [1] proved Theorem 1.1 using both of
Euler’s $q$-exponential functions, which are, respectively,

(1.2)
$(-z;q)_{\infty}=\sum_{n=0}^{\infty}\frac{q^{n(n-1)/2}z^{n}}{(q;q)_{n}},~{}~{}z\in\mathbf{C},$

and

$\frac{1}{(-z;q)_{\infty}}=\sum_{n=0}^{\infty}\frac{(-1)^{n}z^{n}}{(q;q)_{n}},~{}~{}|z|<1.$

In this short note, we will prove Jacobi’s triple product identity only using
(1.2). This seems also a proof of the complete triple product identity
required by Bellman. We use a method which is often called semi-finite method
(see [3]).

##  2\. The proof

###### Proof.

For a nonnegative integer $m$ and $z\neq 0$,

$\displaystyle\sum_{n=-m}^{\infty}\frac{q^{n(n-1)/2}z^{n}}{(q^{m+1};q)_{n}}$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\frac{q^{(n-m)(n-m-1)/2}z^{n-m}}{(q^{m+1};q)_{n-m}}$
$\displaystyle=$
$\displaystyle\frac{q^{m(m+1)/2}z^{-m}}{(q^{m+1};q)_{-m}}\sum_{n=0}^{\infty}\frac{q^{n(n-1)/2}{(zq^{-m})}^{n}}{(q;q)_{n}}$
$\displaystyle=$ $\displaystyle
q^{m(m+1)/2}z^{-m}(q;q)_{m}(-zq^{-m};q)_{\infty}\qquad\mbox{(by \eqref{E1})}$
$\displaystyle=$ $\displaystyle
q^{m(m+1)/2}z^{-m}(q;q)_{m}(-zq^{-m};q)_{m}(-z;q)_{\infty}$ $\displaystyle=$
$\displaystyle(q;q)_{m}(-q/z;q)_{m}(-z;q)_{\infty}.$

Note that $\frac{1}{(q^{m+1};q)_{-n}}=(q^{m+1-n};q)_{n}=0$ when $n>m$. The
left hand side of (2) can be rewritten as

$\displaystyle\sum_{n=0}^{\infty}\frac{q^{n(n-1)/2}z^{n}}{(q^{m+1};q)_{n}}+\sum_{n=1}^{\infty}(q^{m+1-n};q)_{n}q^{n(n+1)/2}z^{-n}.$

Restricting $z$ in any compact subset of $0<|z|<\infty$ and letting
$m\rightarrow\infty$ in (2), we get (1.1). By analytic continuation, the
restriction on $z$ may be relaxed.

Acknowledgment. The author wishes to thank the editor and the referee for
their valuable comments and advices. The author is partially supported by the
National Science Foundation of China (Grant No. 11371184).

## References

  * [1] G. E. Andrews, A simple proof of Jacobi’s triple product identity, Proc. Amer. Math. Soc. 16 no. 2 (1965) 333–334.
  * [2] R. Bellman, A brief introduction to theta functions, Holt, Rinehart and Winston, New York, 1961.
  * [3] W. Y. C. Chen, A. M. Fu, Semi-finite forms of bilateral basic hypergeometric series, Proc. Amer. Math. Soc. 134 (2006) 1719–1725.