# On the Capacity of the $K$-User Cyclic Gaussian Interference Channel

Lei Zhou and Wei Yu
Department of Electrical and Computer Engineering,
University of Toronto, Toronto, Ontario M5S 3G4, Canada
emails: {zhoulei<EMAIL_ADDRESS>
###### Abstract

This paper studies the capacity region of a $K$-user cyclic Gaussian
interference channel, where the $k$th user interferes with only the $(k-1)$th
user (mod $K$) in the network. Inspired by the work of Etkin, Tse and Wang,
which derived a capacity region outer bound for the two-user Gaussian
interference channel and proved that a simple Han-Kobayashi power splitting
scheme can achieve to within one bit of the capacity region for all values of
channel parameters, this paper shows that a similar strategy also achieves the
capacity region for the $K$-user cyclic interference channel to within a
constant gap in the weak interference regime. Specifically, a compact
representation of the Han-Kobayashi achievable rate region using Fourier-
Motzkin elimination is first derived, a capacity region outer bound is then
established. It is shown that the Etkin-Tse-Wang power splitting strategy
gives a constant gap of at most two bits (or one bit per dimension) in the
weak interference regime. Finally, the capacity result of the $K$-user cyclic
Gaussian interference channel in the strong interference regime is also given.

##  I Introduction

The interference channel models a communication scenario where several
mutually interfering transmitter-receiver pairs share the same physical
medium. The interference channel is a useful model for practical wireless
network. The capacity region of the interference channel, however, has not
been completely characterized, even for the two-user Gaussian case.

The largest achievable rate region for the two-user interference channel is
due to a Han-Kobayashi strategy [1], where each transmitter splits its
transmit signal into a common and a private part. The achievable rate region
is the convex hull of the union of achievable rates where each receiver
decodes the common messages from both transmitters plus the private message
intended for itself. Recently, Chong et al. [2] obtained an equivalent
achievable rate region but in a simpler form by applying the Fourier-Motzkin
algorithm together with a time-sharing technique to the Han and Kobayashi’s
original rate region. The optimality of the Han-Kobayashi region for the two-
user Gaussian interference channel is still an open problem in general, except
in the strong interference regime where transmission with common information
only is shown to achieve the capacity region [1, 3, 4], and in a noisy
interference regime where transmission with private information only is shown
to be sum-capacity achieving [5, 6, 7].

In a recent breakthrough, Etkin, Tse and Wang [8] showed that the Han-
Kobayashi scheme can in fact achieve to within one bit of the capacity region
for the two-user Gaussian interference channel for all channel parameters.
Their key insight was that the interference-to-noise ratio (INR) of the
private message should be chosen to be as close to $1$ as possible in the Han-
Kobayashi scheme. They also found a new capacity region outer bound using a
genie-aided technique.

The Etkin-Tse-Wang result applies only to the two-user interference channel.
Practical communication systems often have more than two transmitter-receiver
pairs, yet extending the one-bit result of Etkin, Tse and Wang’s work to
beyond the two-user case is by no means trivial. This is because when more
than 2 users are involved, the Han-Kobayashi private-common superposition
coding strategy becomes exceedingly complicated. It is conceivable that
multiple common messages may be needed at each transmitter, each intended to
be decoded by an arbitrary subset of receivers, thus making the optimization
of the resulting rate region difficult. Further, superposition coding itself
may not be adequate. Interference alignment types of coding scheme [9] has
been shown to be able to enlarge the achievable rate region and to achieve to
within constant gap of many-to-one and one-to-many interference channels [10].

In the context of $K$-user Gaussian interference channels, sum-capacity
results are available in the noisy interference regime [5, 11]. Annapureddy et
al. [5] obtained the sum capacity for the symmetric three-user Gaussian
interference channel, the one-to-many and the many-to-one Gaussian
interference channels under the noisy interference criterion. Shang et al.
[11] studied the fully connected $K$-user Gaussian interference channel and
showed that treating interference as noise at the receiver is sum-capacity
achieving when the transmit power and the cross channel gains are sufficiently
weak to satisfy a certain criterion. In addition, much work has also been
carried out on the generalized degrees of freedom (as defined in [8]) of the
$K$-user interference channel and its variations [9, 12, 13].

Figure 1: The circular array handoff model

Instead of treating the general $K$-user interference channel, this paper
focuses on a cyclic Gaussian interference channel model, where the $k$th user
interferes with only the $(k-1)$th user. In this case, each transmitter
interferes with only one other receiver, and each receiver suffers
interference from only one other transmitter, thereby avoiding the
difficulties mentioned earlier. For the $K$-user cyclic interference channel,
the Etkin, Tse and Wang’s coding strategy remains a natural one. In our
previous work [14], we showed that such a strategy achieves the sum capacity
for a symmetric channel to within two bits. The main objective of this paper
is to show that this strategy also achieves to within two bits of the capacity
region for the general cyclic interference channel in the weak interference
regime. This paper contains an outline of the main results. Detailed proofs
can be found in [15].

The cyclic interference channel model is motivated by the so-called modified
Wyner model, which describes the soft handoff scenario of a cellular network
[16]. The original Wyner model [17] assumes that all cells are arranged in a
linear array with the base-stations located at the center of each cell, and
where intercell interference comes from only the two adjacent cells. In the
modified Wyner model [16] cells are arranged in a circular array as shown in
Fig. 1. The mobile terminals are located along the circular array. If one
assumes that the mobiles always communicate with the intended base-station to
its left (or right), while only suffering from interference due to the base-
station to its right (or left), one arrives at the $K$-user cyclic Gaussian
interference channel studied in this paper. The modified Wyner model has been
extensively studied in the literature [16, 18, 19], but often either with
interference treated as noise or with the assumption of full base station
cooperation. This paper studies the modified Wyner model without base station
cooperation, in which case the soft handoff problem becomes that of a cyclic
interference channel.

The main results of this paper are as follows. For the $K$-user cyclic
Gaussian interference channel in the weak interference regime, one can achieve
to within two bits of the capacity region using the Etkin, Tse and Wang’s
power splitting scheme. The capacity region in the strong interference regime
is also given. It is shown that transmission with common message only achieves
the capacity region.

A key part of the development involves a Fourier-Motzkin elimination procedure
on the achievable rate region of the $K$-user cyclic interference channel. To
deal with the large number of inequality constraints, an induction proof needs
to be used. It is shown that as compared to the two-user case, where the rate
region is defined by constraints on the individual rate $R_{i}$, the sum rate
$R_{1}+R_{2}$, and the sum rate plus an individual rate $2R_{i}+R_{j}$ ($i\neq
j$), the achievable rate region for the $K$-user cyclic interference channel
is defined by an additional set of constraints on the sum rate of any
arbitrary $l$ adjacent users, where $2\leq l<K$. These four types of rate
constraints completely characterize the Han-Kobayashi region for the $K$-user
cyclic interference channel. They give rise to a total of $K^{2}+1$
constraints.

##  II Channel Model

Figure 2: Cyclic Gaussian interference channel

The $K$-user cyclic Gaussian interference channel is first introduced in [14].
It consists of $K$ transmitter-receiver pairs as shown in Fig. 2. Each
transmitter communicates with its intended receiver while causing interference
to only one neighboring receiver. Each receiver receives a signal intended for
it and an interference signal from only one neighboring sender plus the
additive white Gaussian noise (AWGN). As shown in Fig. 2, $X_{1},X_{2},\cdots
X_{K}$ and $Y_{1},Y_{2},\cdots Y_{K}$ are complex-valued input and output
signals, respectively, and $Z_{i}\thicksim\mathcal{CN}(0,\sigma^{2})$ is the
independent and identically distributed (i.i.d) circularly symmetric Gaussian
noise at receiver $i$. The input-output model can be written as

$\displaystyle Y_{1}$ $\displaystyle=$ $\displaystyle
h_{1,1}X_{1}+h_{2,1}X_{2}+Z_{1},$ $\displaystyle Y_{2}$ $\displaystyle=$
$\displaystyle h_{2,2}X_{2}+h_{3,2}X_{3}+Z_{2},$ $\displaystyle\vdots$
$\displaystyle Y_{K}$ $\displaystyle=$ $\displaystyle
h_{K,K}X_{K}+h_{1,K}X_{1}+Z_{K},$ (1)

where each $X_{i}$ has a power constraint $P_{i}$ associated with it, i.e.,
$\mathbb{E}\left[|X_{i}|^{2}\right]\leq P_{i}$. Here, $h_{i,j}$ is the
complex-valued channel gain from transmitter $i$ to receiver $j$.

The encoding-decoding procedure is described as follows. Transmitter $i$ maps
a message $m_{i}\in\\{1,2,\cdots,2^{nR_{i}}\\}$ into a length $n$ codeword
$X_{i}^{n}$ that belongs to a codebook $\mathcal{C}_{i}^{n}$, i.e.
$X_{i}^{n}=f_{i}^{n}(m_{i})$, where $f_{i}^{n}(.)$ represents the encoding
function of user $i$, $i=1,2,\cdots,K$. Codeword $X_{i}^{n}$ is then sent over
a block of $n$ time instances. From the received sequence $Y_{i}^{n}$,
receiver $i$ obtains an estimate $\hat{m}_{i}$ of the transmit message $m_{i}$
using a decoding function $g_{i}^{n}(.)$, i.e.
$\hat{m}_{i}=g_{i}^{n}(Y_{i}^{n})$. The average probability of error is
defined as $P_{e}^{n}=\mathbb{E}\left[\textrm{Pr}(\cup(\hat{m}_{i}\neq
m_{i}))\right]$. A rate tuple $(R_{1},R_{2},\cdots,R_{K})$ is said to be
achievable if for an $\epsilon>0$, there exists a family of codebooks
$\mathcal{C}_{i}^{n}$, encoding functions $f_{i}^{n}(.)$, and decoding
functions $g_{i}^{n}(.)$, $i=1,2,\cdots,K$, such that $P_{e}^{n}<\epsilon$ for
a sufficiently large $n$. The capacity region is the collection of all
achievable rate tuples.

Define the signal-to-noise and interference-to-noise ratios for each user as
follows111Note that the definition of $\mathsf{INR}$ is slightly different
from that of Etkin, Tse and Wang [8].:

$\mathsf{SNR}_{i}=\frac{|h_{i,i}|^{2}P_{i}}{\sigma^{2}},\quad\mathsf{INR}_{i}=\frac{|h_{i,i-1}|^{2}P_{i}}{\sigma^{2}},\;i=1,2,\cdots,K.$
(2)

The $K$-user cyclic Gaussian interference channel is said to be in the weak
interference regime if

$\mathsf{INR}_{i}\leq\mathsf{SNR}_{i},\quad\forall i=1,2,\cdots,K.$ (3)

and the strong interference regime if

$\mathsf{INR}_{i}\geq\mathsf{SNR}_{i},\quad\forall i=1,2,\cdots,K.$ (4)

Otherwise, it is said to be in the mixed interference regime, which has
$2^{K}-2$ possible combinations.

Throughout this paper, modulo arithmetic is implicitly used on the user
indices, e.g., $K+1=1$ and $1-1=K$. Note that when $K=2$, the cyclic channel
reduces to the conventional two-user interference channel.

##  III Within Two Bits of the Capacity Region in the Weak Interference Regime

In the two-user case, the shape of the Han-Kobayashi achievable rate region is
the union of polyhedrons (each corresponding to a fixed input distribution)
with boundaries defined by rate constraints on $R_{1}$, $R_{2}$,
$R_{1}+R_{2}$, and on $2R_{1}+R_{2}$ and $2R_{2}+R_{1}$, respectively. To
extend Etkin, Tse and Wang’s result to the general case, one needs to find a
similar rate region characterization for the general $K$-user cyclic
interference channel first.

A key feature of the cyclic Gaussian interference channel model is that each
transmitter sends signal to its intended receiver while causing interference
to only one of its neighboring receivers; meanwhile, each receiver receives
the intended signal plus the interfering signal from only one of its
neighboring transmitters. Using this fact and with the help of Fourier-Motzkin
elimination algorithm, we show in this section that the achievable rate region
of the $K$-user cyclic Gaussian interference channel is the union of
polyhedrons with boundaries defined by rate constraints on the individual
rates $R_{i}$, the sum rate $R_{sum}$, the sum rate plus an individual rate
$R_{sum}+R_{i}$ ($i=1,2,\cdots,K$), and the sum rate for arbitrary $l$
adjacent users ($2\leq l<K$). This last rate constraint on arbitrary $l$
adjacent users’ rates is new as compared with the two-user case.

The preceding characterization together with outer bounds to be proved later
in the section allow us to show that the capacity region of the $K$-user
cyclic Gaussian interference channel can be achieved to within a constant gap
using the Etkin, Tse and Wang’s power-splitting strategy in the weak
interference regime. However, instead of the one-bit result as obtained for
the two-user interference channel [8], this section shows that without time-
sharing, one can achieve to within two bits of the capacity region for the
$K$-user cyclic Gaussian interference channel in the weak interference regime.
The strong interference regime is treated in the next section.

###  III-A Achievable Rate Region

######  Theorem 1.

Let $\mathcal{P}$ denote the set of probability distributions $P(\cdot)$ that
factor as

$\displaystyle P(q,w_{1},x_{1},w_{2},x_{2},\cdots,w_{K},x_{K})=$ (5)
$\displaystyle\quad\quad\quad p(q)p(x_{1},w_{1}|q)p(x_{2},w_{2}|q)\cdots
p(x_{K},w_{K}|q).$

For a fixed $P\in\mathcal{P}$, let $\mathcal{R}_{\mathrm{HK}}^{(K)}(P)$ be the
set of all rate tuples $(R_{1},R_{2},\cdots,R_{K})$ satisfying

$\displaystyle 0\leq R_{i}$ $\displaystyle\leq$
$\displaystyle\min\\{d_{i},a_{i}+e_{i-1}\\},$ (6)
$\displaystyle\sum_{j=m}^{m+l-1}R_{j}$ $\displaystyle\leq$
$\displaystyle\min\left\\{g_{m}+\sum_{j=m+1}^{m+l-2}e_{j}+a_{m+l-1},\right.$
(7)
$\displaystyle\left.\quad\quad\quad\sum_{j=m-1}^{m+l-2}e_{j}+a_{m+l-1}\right\\},$
$\displaystyle R_{sum}=\sum_{j=1}^{K}R_{j}$ $\displaystyle\leq$
$\displaystyle\min\left\\{\sum_{j=1}^{K}e_{j},r_{1},r_{2},\cdots,r_{K}\right\\},$
(8) $\displaystyle\sum_{j=1}^{K}R_{j}+R_{i}$ $\displaystyle\leq$
$\displaystyle a_{i}+g_{i}+\sum_{j=1,j\neq i}^{K}e_{j},$ (9)

where $a_{i},d_{i},e_{i},g_{i}$ and $r_{i}$ are defined as follows:

$\displaystyle a_{i}$ $\displaystyle=$ $\displaystyle
I(Y_{i};X_{i}|W_{i},W_{i+1},Q),$ (10) $\displaystyle d_{i}$ $\displaystyle=$
$\displaystyle I(Y_{i};X_{i}|W_{i+1},Q),$ (11) $\displaystyle e_{i}$
$\displaystyle=$ $\displaystyle I(Y_{i};W_{i+1},X_{i}|W_{i},Q),$ (12)
$\displaystyle g_{i}$ $\displaystyle=$ $\displaystyle
I(Y_{i};W_{i+1},X_{i}|Q),$ (13) $r_{i}=a_{i-1}+g_{i}+\sum_{j=1,j\neq
i,i-1}^{K}e_{j},$ (14)

and the range of indices are $i,m=1,2,\cdots,K$ in (6) and (9),
$l=2,3,\cdots,K-1$ in (7). Define

$\mathcal{R}_{\mathrm{HK}}^{(K)}=\bigcup_{P\in\mathcal{P}}\mathcal{R}_{\mathrm{HK}}^{(K)}(P).$
(15)

Then $\mathcal{R}_{\mathrm{HK}}^{(K)}$ is an achievable rate region for the
$K$-user cyclic interference channel.

###### Proof:

The achievable rate region can be proved by the Fourier-Motzkin algorithm
together with an induction step. The proof follows the Kobayashi and Han’s
strategy [20] of eliminating a common message at each step. Details are
available in [15]. ∎

In the above achievable rate region, (6) is the constraint on the achievable
rate of an individual user, (7) is the constraint on the achievable sum rate
for any $l$ adjacent users ($2\leq l<K$), (8) is the constraint on the
achievable sum rate of all $K$ users, and (9) is the constraint on the
achievable sum rate for all $K$ users plus a repeated user.

From (6) to (9), there are a total of $K+K(K-2)+1+K=K^{2}+1$ constraints.
Together they describe the shape of the achievable rate region under a fixed
input distribution. The quadratic growth in the number of constraints as a
function of $K$ makes the Fourier-Motzkin elimination of the Han-Kobayashi
region quite complex. An induction needs to be used to deal with the large
number of the constraints.

As an example, for the two-user Gaussian interference channel, there are
$2^{2}+1=5$ rate constraints, corresponding to that of $R_{1}$, $R_{2}$,
$R_{1}+R_{2}$, $2R_{1}+R_{2}$ and $2R_{2}+R_{1}$, as in [1, 20, 2, 8].
Specifically, substituting $K=2$ in Theorem 1 gives us the following
achievable rate region:

$\displaystyle 0\leq R_{1}$ $\displaystyle\leq$
$\displaystyle\min\\{d_{1},a_{1}+e_{2}\\},$ (16) $\displaystyle 0\leq R_{2}$
$\displaystyle\leq$ $\displaystyle\min\\{d_{2},a_{2}+e_{1}\\},$ (17)
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\min\\{e_{1}+e_{2},a_{1}+g_{2},a_{2}+g_{1}\\},$ (18)
$\displaystyle 2R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{1}+g_{1}+e_{2},$ (19) $\displaystyle 2R_{2}+R_{1}$ $\displaystyle\leq$
$\displaystyle a_{2}+g_{2}+e_{1},$ (20)

which is exactly the Theorem D of [20].

###  III-B Capacity Region Outer Bound

######  Theorem 2.

For the $K$-user cyclic Gaussian interference channel in the weak interference
regime, the capacity region is included in the following set of rate tuples
$(R_{1},R_{2},\cdots,R_{K})$:

$\displaystyle R_{i}$ $\displaystyle\leq$ $\displaystyle\lambda_{i},$ (21)
$\displaystyle\sum_{j=m}^{m+l-1}R_{j}$ $\displaystyle\leq$
$\displaystyle\min\left\\{\gamma_{m}+\sum_{j=m+1}^{m+l-2}\alpha_{j}+\beta_{m+l-1},\right.$
(22)
$\displaystyle\left.\quad\quad\mu_{m}+\sum_{j=m}^{m+l-2}\alpha_{j}+\beta_{m+l-1}\right\\},$
$\displaystyle\sum_{j=1}^{K}R_{j}$ $\displaystyle\leq$
$\displaystyle\min\left\\{\sum_{j=1}^{K}\alpha_{j},\rho_{1},\rho_{2},\cdots,\rho_{K}\right\\},$
(23) $\displaystyle\sum_{j=1}^{K}R_{j}+R_{i}$ $\displaystyle\leq$
$\displaystyle\beta_{i}+\gamma_{i}+\sum_{j=1,j\neq i}^{K}\alpha_{j},$ (24)

where the ranges of the indices $i$, $m$, $l$ are as defined in Theorem 1, and

$\displaystyle\alpha_{i}$ $\displaystyle=$
$\displaystyle\log\left(1+\mathsf{INR}_{i+1}+\frac{\mathsf{SNR}_{i}}{1+\mathsf{INR}_{i}}\right),$
(25) $\displaystyle\beta_{i}$ $\displaystyle=$
$\displaystyle\log\left(\frac{1+\mathsf{SNR}_{i}}{1+\mathsf{INR}_{i}}\right),$
(26) $\displaystyle\gamma_{i}$ $\displaystyle=$
$\displaystyle\log\left(1+\mathsf{INR}_{i+1}+\mathsf{SNR}_{i}\right),$ (27)
$\displaystyle\lambda_{i}$ $\displaystyle=$
$\displaystyle\log(1+\mathsf{SNR}_{i}),$ (28) $\displaystyle\mu_{i}$
$\displaystyle=$ $\displaystyle\log(1+\mathsf{INR}_{i}),$ (29)
$\displaystyle\rho_{i}$ $\displaystyle=$
$\displaystyle\beta_{i-1}+\gamma_{i}+\sum_{j=1,j\neq i,i-1}^{K}\alpha_{j}.$
(30)

###### Proof:

Genie-aided bounding techniques are used to prove the theorem. See [15] for
details. ∎

###  III-C Capacity Region to Within Two Bits

######  Theorem 3.

For the $K$-user cyclic Gaussian interference channel in the weak interference
regime, the fixed Etkin, Tse and Wang’s power-splitting strategy achieves to
within two bits of the capacity region222If a rate pair
$(R_{1},R_{2},\cdots,R_{K})$ is achievable and
$(R_{1}+k,R_{2}+k,\cdots,R_{K}+k)$ is outside the capacity region, then
$(R_{1},R_{2},\cdots,R_{K})$ is said to be within $k$ bits of the capacity
region..

###### Proof:

Applying the Etkin, Tse and Wang’s power-splitting strategy (i.e.,
$\mathsf{INR}_{ip}=\min(\mathsf{INR}_{i},1)$) to Theorem 1, parameters
$a_{i},d_{i},e_{i},g_{i}$ can be easily calculated as follows:

$\displaystyle a_{i}$ $\displaystyle=$
$\displaystyle\log\left(2+\mathsf{SNR}_{ip}\right)-1,$ (31) $\displaystyle
d_{i}$ $\displaystyle=$ $\displaystyle\log\left(2+\mathsf{SNR}_{i}\right)-1,$
(32) $\displaystyle e_{i}$ $\displaystyle=$
$\displaystyle\log\left(1+\mathsf{INR}_{i+1}+\mathsf{SNR}_{ip}\right)-1,$ (33)
$\displaystyle g_{i}$ $\displaystyle=$
$\displaystyle\log\left(1+\mathsf{INR}_{i+1}+\mathsf{SNR}_{i}\right)-1.$ (34)

To prove that the achievable rate region described by the above
$a_{i},d_{i},e_{i},g_{i}$ is within two bits of the outer bound in Theorem 2,
we need to show that each of the rate constraints in (6)-(9) is within two
bits of their corresponding outer bound in (21)-(24), i.e., the following
inequalities hold for all $i$, $m$, $l$ in the ranges defined in Theorem 1:

$\displaystyle\delta_{R_{i}}$ $\displaystyle<$ $\displaystyle 2,$ (35)
$\displaystyle\delta_{R_{m}+\cdots+R_{m+l-1}}$ $\displaystyle<$ $\displaystyle
2l,$ (36) $\displaystyle\delta_{R_{sum}}$ $\displaystyle<$ $\displaystyle 2K,$
(37) $\displaystyle\delta_{R_{sum}+R_{i}}$ $\displaystyle<$ $\displaystyle
2(K+1),$ (38)

where $\delta_{(\cdot)}$ is the difference between the achievable rate in
Theorem 1 and its corresponding outer bound in Theorem 2. A complete proof can
be found in [15] . ∎

##  IV Capacity Region in the Strong Interference Regime

The results so far in the paper pertain only to the weak interference regime,
where $\mathsf{SNR}_{i}\geq\mathsf{INR}_{i}$, $\forall i$. In the strong
interference regime, where $\mathsf{SNR}_{i}\leq\mathsf{INR}_{i}$, $\forall
i$, the capacity result in [1] [4] for the two-user Gaussian interference
channel can be easily extended to the $K$-user cyclic case.

######  Theorem 4.

For the $K$-user cyclic Gaussian interference channel in the strong
interference regime, the capacity region is given by the set of
$(R_{1},R_{2},\cdots,R_{K})$ such that

$\left\\{\begin{array}[]{l}R_{i}\leq\log(1+\mathsf{SNR}_{i})\\\
R_{i}+R_{i+1}\leq\log(1+\mathsf{SNR}_{i}+\mathsf{INR}_{i+1}),\end{array}\right.$
(39)

for $i=1,2,\cdots,K$. In the very strong interference regime where
$\mathsf{INR}_{i}\geq(1+\mathsf{SNR}_{i-1})\mathsf{SNR}_{i},\forall i$, the
capacity region is the set of $(R_{1},R_{2},\cdots,R_{K})$ with

$R_{i}\leq\log(1+\mathsf{SNR}_{i}),\;\;i=1,2,\cdots,K.$ (40)

###### Proof:

Achievability: It is easy to see that (39) is in fact the intersection of the
capacity regions of $K$ multiple-access channels:

$\bigcap_{i=1}^{K}\left\\{(R_{i},R_{i+1})\left|\begin{array}[]{l}R_{i}\leq\log(1+\mathsf{SNR}_{i})\\\
R_{i+1}\leq\log(1+\mathsf{INR}_{i+1})\\\
R_{i}+R_{i+1}\leq\log(1+\mathsf{SNR}_{i}+\mathsf{INR}_{i+1}).\end{array}\right.\right\\}.$
(41)

Each of these regions corresponds to that of a multiple-access channel with
$W_{i}^{n}$ and $W_{i+1}^{n}$ as inputs and $Y_{i}^{n}$ as output (with
$U_{i}^{n}=U_{i+1}^{n}=\emptyset$). Therefore, the rate region (39) can be
achieved by setting all the input signals to be common messages. This
completes the achievability part.

Converse: The converse proof follows the idea of [4]. The key ingredient is to
show that for a genie-aided Gaussian interference channel to be defined later,
in the strong interference regime, whenever a rate tuple
$(R_{1},R_{2},\cdots,R_{K})$ is achievable, i.e., $X_{i}^{n}$ is decodable at
receiver $i$, $X_{i}^{n}$ must also be decodable at $Y_{i-1}^{n}$,
$i=1,2,\cdots,K$.

The genie-aided Gaussian interference channel is defined by the Gaussian
interference channel (see Fig. 2) with genie $X_{i+2}^{n}$ given to receiver
$i$. The capacity region of the $K$-user cyclic Gaussian interference channel
must be resided inside the capacity region of the genie-aided one.

Assume that a rate tuple $(R_{1},R_{2},\cdots,R_{K})$ is achievable for the
$K$-user cyclic Gaussian interference channel. In this case, after $X_{i}^{n}$
is decoded, with the knowledge of the genie $X_{i+2}^{n}$, receiver $i$ can
construct the following signal:

$\displaystyle\widetilde{Y}_{i}^{n}$ $\displaystyle=$
$\displaystyle\frac{h_{i+1,i+1}}{h_{i+1,i}}(Y_{i}^{n}-h_{i,i}X_{i}^{n})+h_{i+2,i+1}X_{i+2}^{n}$
$\displaystyle=$ $\displaystyle
h_{i+1,i+1}X_{i+1}^{n}+h_{i+2,i+1}X_{i+2}^{n}+\frac{h_{i+1,i+1}}{h_{i+1,i}}Z_{i}^{n},$

which contains the signal component of $Y_{i+1}^{n}$ but with less noise since
$|h_{i+1,i}|\geq|h_{i+1,i+1}|$ in the strong interference regime. Now, since
$X_{i+1}^{n}$ is decodable at receiver $i+1$, it must also be decodable at
receiver $i$ using the constructed $\widetilde{Y}_{i}^{n}$. Therefore,
$X_{i}^{n}$ and $X_{i+1}^{n}$ are both decodable at receiver $i$. As a result,
the achievable rate region of $(R_{i},R_{i+1})$ is bounded by the capacity
region of the multiple-access channel $(X_{i}^{n},X_{i+1}^{n},Y_{i}^{n})$,
which is shown in (41). Since (41) reduces to (39) in the strong interference
regime, we have shown that (39) is an outer bound of the $K$-user cyclic
Gaussian interference channel in the strong interference regime. This
completes the converse proof.

In the very strong interference regime where
$\mathsf{INR}_{i}\geq(1+\mathsf{SNR}_{i-1})\mathsf{SNR}_{i},\forall i$, it is
easy to verify that the second constraint in (39) is no longer active. This
results in the capacity region (40). ∎

##  V Concluding Remarks

This paper studies the capacities and the coding strategies for the $K$-user
cyclic Gaussian interference channel in the weak and the strong interference
regimes. An achievable rate region based on the Han-Kobayashi power splitting
strategy is first derived; a corresponding capacity region outer bound is then
obtained using genie-aided bounding techniques. This paper shows that in the
weak interference regime, the Etkin, Tse and Wang’s power-splitting strategy
achieves to within two bits of the capacity region. The capacity result for
the $K$-user cyclic Gaussian interference channel in the strong interference
regime is a straightforward extension of the corresponding two-user case.
However, in the mixed interference regime, although the constant gap result
may well continue to hold, the proof becomes considerably more complicated, as
different mixed scenarios need to be enumerated and the corresponding outer
bounds derived.

## References

  * [1] T. S. Han and K. Kobayashi, “A new achievable rate region for the interference channel,” _IEEE Trans. Inf. Theory_ , vol. 27, no. 1, pp. 49–60, Jan. 1981.
  * [2] H. Chong, M. Motani, H. Garg, and H. El Gamal, “On the Han-Kobayashi region for the interference channel,” _IEEE Trans. Inf. Theory_ , vol. 54, no. 7, pp. 3188–3195, Jul. 2008.
  * [3] A. B. Carleial, “Interference channels,” _IEEE Trans. Inf. Theory_ , vol. 24, no. 1, pp. 60–70, Jan. 1978.
  * [4] H. Sato, “The capacity of the Gaussian interference channel under strong interference,” _IEEE Trans. Inf. Theory_ , vol. 27, no. 6, pp. 786–788, Nov. 1981.
  * [5] V. S. Annapureddy and V. Veeravalli, “Gaussian interference networks: Sum capacity in the low interference regime and new outer bounds on the capacity region,” _IEEE Trans. Inf. Theory_ , vol. 55, no. 7, pp. 3032–3035, Jul. 2009.
  * [6] A. S. Motahari and A. K. Khandani, “Capacity bounds for the Gaussian interference channel,” _IEEE Trans. Inf. Theory_ , vol. 55, no. 2, pp. 620–643, Feb. 2009.
  * [7] X. Shang, G. Kramer, and B. Chen, “A new outer bound and the noisy-interference sum-rate capacity for Gaussian interference channels,” _IEEE Trans. Inf. Theory_ , vol. 55, no. 2, pp. 689–699, Feb. 2009.
  * [8] R. Etkin, D. N. C. Tse, and H. Wang, “Gaussian interference channel capacity to within one bit,” _IEEE Trans. Inf. Theory_ , vol. 54, no. 12, pp. 5534–5562, Dec. 2008.
  * [9] V. R. Cadambe and S. A. Jafar, “Interference alignment and the degrees of freedom for the K user interference channel,” _IEEE Trans. Inf. Theory_ , vol. 54, no. 8, pp. 3425–3441, Aug. 2008.
  * [10] G. Bresler, A. Parekh, and D. N. C. Tse, “The approximate capacity of the many-to-one and one-to-many Gaussian interference channels,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 9, pp. 4566 –4592, Sep. 2010.
  * [11] X. Shang, G. Kramer, and B. Chen, “New outer bounds on the capacity region of Gaussian interference channels,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , Jul. 2008, pp. 245–249.
  * [12] S. A. Jafar and S. Vishwanath, “Generalized degrees of freedom of the symmetric Gaussian K user interference channel,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 7, pp. 3297–3303, July. 2010.
  * [13] V. R. Cadambe and S. A. Jafar, “Interference alignment and a noisy interference regime for many-to-one interference channels,” _Submitted to IEEE Trans. Inf. Theory_ , Dec. 2009. [Online]. Available: http://arxiv.org/pdf/0912.3029
  * [14] L. Zhou and W. Yu, “On the symmetric capacity of the k-user symmetric cyclic Gaussian interference channel,” in _Proc. IEEE Conf. Inf. Sciences and Systems (CISS)_ , Mar. 2010, pp. 1–6.
  * [15] ——, “On the capacity of the $K$-user cyclic Gaussian interference channel,” _Submitted to IEEE Trans. Inf. Theory_ , Oct. 2010. [Online]. Available: http://arxiv.org/abs/1010.1044
  * [16] O. Somekh, B. M. Zaidel, and S. Shamai, “Sum rate characterization of joint multiple cell-site processing,” _IEEE Trans. Inf. Theory_ , vol. 53, no. 12, pp. 4473–4497, Dec. 2007.
  * [17] A. D. Wyner, “Shannon-theoretic approach to a Gaussian cellular multiple-access channel,” _IEEE Trans. Inf. Theory_ , vol. 40, no. 6, pp. 1713–1727, Nov. 1994.
  * [18] Y. Liang and A. Goldsmith, “Symmetric rate capacity of cellular systems with cooperative base stations,” in _Proc. Global Telecommun. Conf. (Globecom)_ , Nov. 2006, pp. 1–5.
  * [19] J. Sheng, D. N. C. Tse, J. Hou, J. B. Soriaga, and R. Padovani, “Multi-cell downlink capacity with coordinated processing,” in _Proc. Inf. Theory and App. (ITA)_ , Jan. 2007, pp. 1–5.
  * [20] K. Kobayashi and T. S. Han, “A further consideration on the HK and the CMG regions for the interference channel,” in _Proc. Inf. Theory and App. (ITA)_ , Jan. 2007.


#  Structural accessibility and structural observability of nonlinear
networked systems

Marco Tulio Angulo∗, Andrea Aparicio and Claude H. Moog M.T. Angulo is with
CONACyT - Institute of Mathematics, Universidad Nacional Autonoma de Mexico,
Juriquilla Mexico. Correspondence should be addressed to<EMAIL_ADDRESS>Aparicio is with the Institute of Mathematics, Universidad Nacional Autonoma
de Mexico, Juriquilla Mexico.C. Moog is with the Laboratoire des Sciences du
Numérique de Nantes, UMR CNRS 6004, Nantes 44321, France.

###### Abstract

The classical notions of structural controllability and structural
observability are receiving increasing attention in Network Science, since
they provide a mathematical basis to answer how the network structure of a
dynamic system affects its controllability and observability properties.
However, these two notions are formulated assuming systems with linear
dynamics, which significantly limit their applicability. To overcome this
limitation, here we introduce and fully characterize the notions “structural
accessibility” and “structural observability” for systems with nonlinear
dynamics. We show how nonlinearities make easier the problem of controlling
and observing networked systems, reducing the number of variables that are
necessary to directly control and directly measure. Our results contribute to
understanding better the role that the network structure and nonlinearities
play in our ability to control and observe complex dynamic systems.

###### Index Terms:

networks; nonlinear systems; observability; accessibility; controllability.

##  I Introduction

In a world where complex networks underlie most biological, social and
technological systems that shape the human experience [1, 2], one central
challenge is finding principles that can help us control and observe complex
networked systems. When only the network structure of a dynamical system is
known (i.e., a graph of the interactions between its variables), a central
theoretical basis for this research program has been the classical notions of
“structural controllability” and “structural observability” of linear systems
[3]. These two notions characterize the conditions under which almost all
linear dynamical systems whose structure matches a given network are
controllable or observable, respectively [4]. Linear structural
controllability and structural observability thus provide a mathematical
formalism for predicting how changes in the network structure of a system
impact its controllability and observability properties. For example, linear
structural controllability was applied to build and then experimentally
validate predictions of how removing different neurons (i.e., removing nodes
in the network) affects the locomotion of the round worm _C. elegans_ [5].
Additionally, over the last few years, a central line of research has been
characterizing minimal sets of “driver nodes” and “sensor nodes” from which we
can efficiently render a complex networked system controllable and observable
[3].

The conditions of linear structural controllability and linear structural
observability can be stronger than necessary when applied to systems with
nonlinear dynamics, resulting in over-conservative predictions. This is
because the lack of linear controllability (resp. linear observability) of a
nonlinear system cannot be used to predict its lack of controllability (resp.
observability). An elementary example of this is a car, which is controllable
but not linearly controllable because it cannot move in the direction of the
axis defined by its rear wheels. Despite the ubiquity of nonlinear systems in
nature and technology, the effects of nonlinearities on our ability to
efficiently control and observe complex networked systems remain poorly
understood [6, 7, 8, 9, 10].

Given that most systems in nature are expected to contain nonlinearities, in
this Note we introduce and characterize the notions of nonlinear “structural
accessibility” and nonlinear “structural observability” as counterparts of
linear structural controllability and linear structural observability. These
two notions we introduce characterize the conditions under which almost all
nonlinear systems whose structure matches a given network are locally
accessible or locally observable almost everywhere, respectively.
Accessibility and observability are nonlinear generalizations of linear
controllability and linear observability, which have played a central role in
the development of nonlinear control theory [11]. Somewhat counter-
intuitively, we show that nonlinearities make significantly easier the problem
of controlling or observing a complex networked system. More precisely, our
main result proves that the conditions for nonlinear structural accessibility
and observability are weaker than the conditions for linear structural
controllability and observability. We show this implies that we need smaller
sets of driver and sensor nodes when compared to the those necessary for
linear structural controllability and linear structural observability.

This Note is organized as follows. Section II summarizes the network
characterization of structural controllability and structural observability of
linear systems, serving as a comparison point to our results. Section III
contains our problem statement and main results. Proofs are collected in
Sections IV and V. We end discussing some predictions that our structural
accessibility theory offers about the locomotion of _C. elegans_ , and some
limitations of our approach.

##  II Preliminaries

The network or _graph_ of a system with $N$ state variables, $M$ inputs, and
$P$ outputs is a directed graph $\mathcal{G}=({\sf X\cup\sf Y\cup\sf U},{\sf
A\cup B\cup C})$ containing state nodes ${\sf X}=\\{{\sf x}_{1},\cdots,{\sf
x}_{N}\\}$, output nodes ${\sf Y}=\\{{\sf y}_{1},\cdots,{\sf y}_{P}\\}$, and
input nodes ${\sf U}=\\{{\sf u}_{1},\cdots,{\sf u}_{M}\\}$, see Fig. 1a. Edges
take the form $({\sf x}_{j}\rightarrow{\sf x}_{i})\in{\sf A}$ to denote that
the $i$-th state variable directly depends on the $j$-th one, $({\sf
x}_{j}\rightarrow{\sf y}_{i})\in{\sf C}$ to denote that the $i$-th measured
output directly depends on the $j$-th state variable, and $({\sf
u}_{j}\rightarrow{\sf x}_{i})\in{\sf B}$ to denote that the $i$-th state
variable directly depends on the $j$-th control input. We allow graphs with
empty output or input node sets to represent systems without outputs or
inputs, respectively.

In the framework of linear structural controllability and linear structural
observability the system dynamics is of course assumed linear. Then the
controllability and observability of the set of all linear systems whose
structure matches the graph $\mathcal{G}$ is analyzed. More precisely, the
system dynamics is assumed to have the form

$\dot{x}(t)=Ax(t)+Bu(t),\quad y(t)=Cx(t),$ (1)

where $x(t)\in\mathbb{R}^{N}$, $u(t)\in\mathbb{R}^{M}$ and
$y(t)\in\mathbb{R}^{P}$ are the state, input, and output of the system at time
$t$, respectively. Here $A=(a_{ij})\in\mathbb{R}^{N\times N}$,
$B=(b_{ij})\in\mathbb{R}^{N\times M}$ and $C=(c_{ij})\in\mathbb{R}^{P\times
N}$ are matrices of parameters. The _structure_ of Eq. (1) is determined by
the zero/non-zero pattern of these three matrices. Thus, given a graph
$\mathcal{G}$, the class $\mathfrak{D}_{L}(\mathcal{G})$ of all linear systems
whose structure matches $\mathcal{G}$ is defined as all systems (1) such that:
$a_{ij}\neq 0$ iff $({\sf x}_{j}\rightarrow{\sf x}_{i})\in{\sf A}$,
$b_{ij}\neq 0$ iff $({\sf u}_{j}\rightarrow{\sf x}_{i})\in{\sf B}$, and
$c_{ij}\neq 0$ iff $({\sf x}_{j}\rightarrow{\sf y}_{i})\in{\sf C}$. Note that
the edges $({\sf x}_{j}\rightarrow{\sf x}_{i})$ and $({\sf
u}_{j}\rightarrow{\sf x}_{i})$ are encoded by differential equations. By
contrast, the edges $({\sf x}_{j}\rightarrow{\sf y}_{i})$ are encoded by
algebraic equations; these output edges have direction because the output map
$y=Cx$ is not necessarily one-to-one (e.g., the single output
$y=x_{1}+x_{2}$). Thus, the class $\mathfrak{D}_{L}(\mathcal{G})$ describes
the set of all linear dynamics that a system can take if its structure
coincides with $\mathcal{G}$.

The class $\mathfrak{D}_{L}(\mathcal{G})$ is said _structurally controllable_
(resp. _structurally observable_) if it contains at least one system that is
linearly controllable (resp. linearly observable) [4]. In that case we also
say that $\mathcal{G}$ is linearly structurally controllable (resp. linearly
structurally observable). It turns out that when one system in
$\mathfrak{D}_{L}(\mathcal{G})$ is linearly controllable (resp. linearly
observable), then almost all other systems in $\mathfrak{D}_{L}(\mathcal{G})$
are linearly controllable as well (resp. linearly observable) [4]. This means
that, if $\mathfrak{D}_{L}(\mathcal{G})$ is structurally controllable (resp.
structurally observable), any of its systems is either controllable (resp.
observable), or becomes controllable (resp. observable) by an infinitesimal
change in the nonzero entries of the matrices $A,B$ and $C$. A central result
in the theory of structural linear systems, which can be traced back to the
pioneer work of Lin in the 70’s [12], is the following:

######  Theorem 1.

(see, e.g., [4]) $\mathfrak{D}_{L}(\mathcal{G})$ is:

  * (i)

structurally controllable iff each state node is the end-node of a path that
starts in ${\sf U}$; and there is a disjoint union of cycles and paths
starting in $\sf U$ that covers ${\sf X}$.

  * (ii)

structurally observable iff each state node is the start-node of a path that
ends in ${\sf Y}$; and there is a disjoint union of cycles and paths ending in
$\sf Y$ that covers ${\sf X}$.

Recall that a _path_ is a sequence of nodes ${\sf v}_{1}\rightarrow{\sf
v}_{2}\rightarrow\cdots\rightarrow{\sf v}_{n}$ where ${\sf v}_{i}\in\sf X\cup
Y\cup U$. The _start-node_ of this path is ${\sf v}_{1}$ and its _end-node_ is
${\sf v}_{n}$. A _cycle_ is a path that starts and ends in the same node
(i.e., ${\sf v}_{n}={\sf v}_{1}$). Two paths are _disjoint_ if they have
disjoint sets of nodes.

Theorem 1 shows that except for a zero-measure set of “singularities,” the
graph $\mathcal{G}$ of a linear system determines its controllability and
observability properties. Note that for linear structural controllability it
is not sufficient that the control inputs propagate their influence through
$\mathcal{G}$ to all state nodes. Similarly, for linear structural
observability, it is not sufficient that each state node can propagate its
state to some output through $\mathcal{G}$. Both notions require that the
graph $\mathcal{G}$ contains enough “independent” paths to propagate these
effects, encoded by the existence of a disjoint union of cycles and paths that
covers all state nodes.

######  Example 1.

For the graph $\mathcal{G}$ of Fig. 1a, the class
$\mathfrak{D}_{L}(\mathcal{G})$ contains all linear systems of the form

$\left\\{\begin{split}\dot{x}_{1}(t)&=b_{11}u_{1}(t),\\\
\dot{x}_{2}(t)&=b_{21}u_{1}(t),\\\
y_{1}(t)&=c_{11}x_{1}(t)+c_{12}x_{2}(t),\end{split}\right.$ (2)

with nonzero constants $b_{11},b_{21},c_{11}$ and $c_{12}$. Recall that:

  * 1.

Together with isolated nodes in $\mathcal{G}$, the main obstacle for linear
structural controllability is the presence of so-called “dilations” [12]. In
essence, a dilation consist of two nodes with identical dynamics that are
controlled by the same input (top in Fig. 1a). A dilation makes $\mathcal{G}$
not structurally controllable because it is impossible to obtain a disjoint
union of paths that covers $\sf X$. For Fig. 1a, all systems in
$\mathfrak{D}_{L}(\mathcal{G})$ are uncontrollable because their state is
constrained to the plane
$b_{11}x_{2}(t)-b_{21}x_{1}(t)=b_{11}x_{2}(0)-b_{21}x_{1}(0)$ for all inputs
$u_{1}(t)$ and time $t$ (Fig. 1b).

  * 2.

Analogously, so-called “contractions” in $\mathcal{G}$ are the main obstacle
for linear structural observability. In essence, a contraction corresponds to
two state nodes that are measured using a single output (bottom in Fig. 1a).
Indeed, for Fig. 1a, all systems $\mathfrak{D}_{L}(\mathcal{G})$ are
unobservable because using $y_{1}=c_{11}x_{1}+c_{12}x_{2}$ and $k$ of its
derivatives $y_{1}^{(k)}=(c_{11}b_{11}+c_{12}b_{12})u_{1}^{(k)}$ it is
impossible to infer the value of $x_{1}$ and $x_{2}$ (Fig. 1c).

Theorem 1 provides a theoretical basis for a very active research line aiming
to identify and analyze the “driver” and “sensor” nodes that render a system
linearly structurally controllable and linearly structurally observable (see,
e.g., [2, 3]). More precisely, consider a graph $\mathcal{G}({\sf X},{\sf A})$
with only state nodes $\sf X$ and edges $({\sf x}_{i}\rightarrow{\sf
x}_{j})\in{\sf A}$. Then define:

######  Definition 1.

  * (i)

${\sf X}_{D}\subseteq\sf X$ is a set of _driver nodes_ if there exists a set
$\sf U$ of input nodes and a set $\sf B$ of edges of the form $({\sf
u}_{i}\rightarrow{\sf x}_{j})$ such that: (i) the graph $\mathcal{G}({\sf
X\cup\sf U},\sf A\cup B)$ is linearly structurally controllable; and (ii) all
and only the driver nodes have incoming edges from the input nodes (i.e.,
$({\sf u}_{i}\rightarrow{\sf x}_{j})\in{\sf B}$ iff ${\sf x}_{j}\in{\sf
X}_{D}$).

  * (ii)

${\sf X}_{S}\subseteq\sf X$ is a set of _sensor nodes_ if there exists a set
$\sf Y$ of output nodes and a set $\sf C$ of edges of the form $({\sf
x}_{i}\rightarrow{\sf y}_{j})$ such that: (i) the graph $\mathcal{G}({\sf
X\cup\sf Y},\sf A\cup C)$ is linearly structurally observable; and (ii) all
and only the sensor nodes have outgoing edges to the output nodes (i.e.,
$({\sf x}_{i}\rightarrow{\sf y}_{j})\in\sf C$ iff ${\sf x}_{i}\in{\sf
X}_{S}$).

A set of driver nodes or sensor nodes is called _minimal_ if it has the
minimal cardinality among all sets of driver nodes or sensor nodes,
respectively. The conditions in Theorem 1 allows finding a minimal set of
driver nodes (resp. a minimal set of sensor nodes) by mapping the satisfaction
of these conditions to solving maximum matching problem on the graph
$\mathcal{G}$ (resp. $\mathcal{G}^{\intercal}$ obtained from $\mathcal{G}$ by
reversing the direction of all its edges), see [3].

##  III Problem statement and Main results

Here we generalize the analysis of Section II by enlarging the class of
dynamics that the system can take to include arbitrary nonlinearities.
Specifically, we now consider general nonlinear systems of the form

$\dot{x}(t)=f\left(x(t),u(t)\right),\quad y(t)=h(x(t)),$ (3)

where $f:\mathbb{R}^{N}\times\mathbb{R}^{M}\rightarrow\mathbb{R}^{N}$ and
$h:\mathbb{R}^{N}\rightarrow\mathbb{R}^{P}$ are arbitrary _meromorphic_
functions of their arguments (i.e., each of their entries is the quotient of
analytic functions). The assumption of meromorphic functions is very weak in
the sense that it is satisfied by most models in biology, chemistry, ecology,
and engineering (see, e.g., Table 1 in Ref. [13]). Recall that meromorphic
functions are either identically zero (written as “$\equiv 0$”) or different
from zero in an open dense subset of their domain (written as “$\not\equiv
0$”), see [11, Chapter 1]. This property allow us to define:

######  Definition 2.

Given a meromorphic pair $\\{f,h\\}$, its graph $\mathcal{G}_{f,h}=({\sf
X\cup\sf Y\cup\sf U},{\sf A}_{f}\cup{\sf B}_{f}\cup{\sf C}_{h})$ has the edge-
set defined as: $({\sf x}_{j}\rightarrow{\sf x}_{i})\in{\sf
A}_{f}\Leftrightarrow\partial f_{i}/\partial x_{j}\not\equiv 0$; $({\sf
u}_{j}\rightarrow{\sf x}_{i})\in{\sf B}_{f}\Leftrightarrow\partial
f_{i}/\partial u_{j}\not\equiv 0$; and $({\sf x}_{j}\rightarrow{\sf
y}_{i})\in{\sf C}_{h}\Leftrightarrow\partial h_{i}/\partial x_{j}\not\equiv
0$.

We say that two pairs $\\{f,h\\}$ and $\\{\tilde{f},\tilde{h}\\}$ are graph-
equivalent if $\mathcal{G}_{f,h}=\mathcal{G}_{\tilde{f},\tilde{h}}$. Since any
$\\{f,h\\}$ is graph-equivalent to itself, graph-equivalence is an equivalence
relation. Thus, given a graph $\mathcal{G}$, we can define the equivalence
class

$\mathfrak{D}(\mathcal{G}):=\\{\mbox{all meromorphic }\\{f,h\\}\mbox{ such
that }\mathcal{G}_{f,h}=\mathcal{G}\\}.$

The class $\mathfrak{D}(\mathcal{G})$ represents the set of all nonlinear
dynamics that a system can have given that its graph is $\mathcal{G}$. Note
that $\mathfrak{D}_{L}(\mathcal{G})\subset\mathfrak{D}(\mathcal{G})$.

As the nonlinear counterparts of linear controllability and linear
observability, we consider the concepts of local _accessibility_ and local
_observability_. We will introduce these concepts using the algebraic
formalism of Ref. [11]. Consider the field of meromorphic functions
$\mathcal{K}$ in the variables
$\\{x,u,\dot{u},\ddot{u},\cdots,y,\dot{y},\ddot{y},\cdots\\}$, and the sets of
differential symbols
$\mathrm{d}x=(\mathrm{d}x_{1},\cdots,\mathrm{d}x_{N})^{\intercal}$,
$\mathrm{d}u=(\mathrm{d}u_{1},\cdots,\mathrm{d}u_{M})^{\intercal}$ and
$\mathrm{d}y^{(k)}=(\mathrm{d}y_{1}^{(k)},\cdots,\mathrm{d}y_{P}^{(k)})^{\intercal},k\geq
0$. For a function $\varphi\in\mathcal{K}$, its differential is
$\mathrm{d}\varphi=(\partial\varphi/\partial
x)^{\intercal}\mathrm{d}x+(\partial\varphi/\partial
u)^{\intercal}\mathrm{d}u$. More generally, functions in the vector space
spanned over $\mathcal{K}$ by the elements of
$\\{\mathrm{d}x,\mathrm{d}u,\mathrm{d}y,\cdots,\mathrm{d}y^{(k)}\\}$ are
called _one-forms_. We next recall the following notions:

######  Definition 3.

  * (i)

An _autonomous element_ of a system is a non-constant meromorphic function
$\xi(x)$ such that its $k$-th time derivative $\xi^{(k)}$ is independent of
$u$ for all $k\geq 0$, i.e.,

$\partial\xi^{(k)}/\partial u\equiv 0,\quad\forall k\geq 0.$

  * (ii)

A _hidden element_ of a system is a non-constant meromorphic function
$\zeta(x)$ that is independent of $\\{y,\cdots,y^{(k)}\\}$ for all $k\geq 0$,
i.e.,

$\mathrm{d}\zeta\notin\mbox{span}_{\mathcal{K}}\\{\mathrm{d}y,\mathrm{d}\dot{y},\cdots,\mathrm{d}y^{(k)}\\},\quad\forall
k\geq 0.$

Figure 1: a. Graph of a system. Here the input, state and output nodes are
${\sf U}=\\{{\sf u}_{1}\\}$, ${\sf X}=\\{{\sf x}_{1},{\sf x}_{2},{\sf
x}_{3}\\}$ and ${\sf Y}=\\{{\sf y}_{1}\\}$, respectively. b. The graph of
panel a is not linearly structurally controllable, meaning that no linear
system with this graph is controllable. We illustrate this with five
trajectories (colors) of the linear dynamics of Eq. (2) with initial condition
$x(0)=(1,1)^{\intercal}$ (black dot), parameters $b_{11}=0.5$ and $b_{12}=1$,
and random inputs $u_{1}(t)$. The lack of controllability constrains the
system to the plane
$\\{x\in\mathbb{R}^{2}|b_{21}x_{1}-b_{11}x_{2}=b_{21}x_{1}(0)-b_{11}x_{2}(0)\\}$
for all time and inputs, representing the autonomous element of this system.
Consequently, the system is not accessible and not controllable. c. The graph
of panel a is not linearly structurally observable, meaning that no linear
system with this graph is observable. We illustrate this using the linear
dynamics of Eq. (2), where five different trajectories (colors) with different
initial conditions (dots) give exactly the same projection in the output
$y_{1}$ because they are all vertically aligned. This is characterized by the
hidden element $\zeta=c_{12}x_{1}-c_{11}x_{2}$ which is orthogonal to the
output and its derivatives. Consequently, the system is not linearly
observable and not locally observable. d. The nonlinear dynamics of Eq. (4) is
accessible because it lacks autonomous elements, illustrated here by five
trajectories (colors) that are not constrained to any low-dimensional
manifold. Parameters are as in panel b and $\varepsilon=0.5$. This shows that
the graph in panel a is structurally accessible. e. The nonlinear dynamics of
Eq. (4) is locally observable since different trajectories (colors)
corresponding to different initial conditions (dots) give different
projections in the output $y_{1}$. Parameters are as in panel d and
$\varepsilon=0.5$. This shows that the graph in panel a is structurally
locally observable.

An autonomous element constrains the state of the system to a low-dimensional
manifold for all control inputs, just as in an uncontrollable linear system
its state is constrained to a hyperplane. A hidden element is an internal
variable of the system whose value cannot be inferred from the output, since
it cannot be rewritten as a function of the output and its derivatives. A non-
constant function that is not a hidden element is called observable.

With these notions a system is called locally _accessible_ (“accessible”, for
short) if it does not have autonomous elements, and locally _observable_
(“observable”, for short) if it does not have hidden elements [11]. For linear
systems, the lack of autonomous elements is equivalent to linear
controllability, and the lack of hidden elements is equivalent to linear
observability [11]. For example, all linear systems of Eq. (2) are not
controllable because $\xi(x)=b_{11}x_{1}-b_{21}x_{2}$ is an autonomous element
for all of them. Indeed $\xi^{(k)}\equiv 0$, which is independent of $u$ for
all $k\geq 1$. Similarly, $\zeta(x)=c_{12}x_{1}-c_{11}x_{2}$ is a hidden
element for all those linear systems, since $\zeta$ cannot be written as a
function of $y_{1}=c_{11}x_{1}+c_{12}x_{2}$ and its derivatives
$y_{1}^{(k)}=(c_{11}b_{11}+c_{12}b_{12})u_{1}^{(k-1)}$. Indeed, this happens
because no output derivative contains information of the state. In this sense,
the above definitions of accessibility and observability provide nonlinear
generalizations of linear controllability and linear observability.

In analogy to the definitions of linear structural controllability and
observability, we now define:

######  Definition 4.

$\mathfrak{D}(\mathcal{G})$ is:

  * (i)

_structurally accessible_ if $\mathfrak{D}(\mathcal{G})$ contains at least one
system that is accessible.

  * (ii)

_structurally observable_ if $\mathfrak{D}(\mathcal{G})$ contains at least one
system that is observable.

When $\mathfrak{D}(\mathcal{G})$ is structurally accessible (resp.
structurally observable), we also call the graph $\mathcal{G}$ structurally
accessible (resp. structurally observable). We also call a particular $f$
structurally accessible if there exists at least one graph-equivalent
$\bar{f}$ that is accessible. Similarly, a particular $\\{f,h\\}$ is
structurally observable if there exists at least one graph-equivalent
$\\{\bar{f},\bar{h}\\}$ that is observable.

As in the case of linear systems, in Lemma 1 of Section IV we prove that in a
structurally accessible class $\mathfrak{D}(\mathcal{G})$ the subset of
accessible systems is open and everywhere dense; furthermore the subset of
non-accessible systems is not dense. Similarly, in a structurally observable
class $\mathfrak{D}(\mathcal{G})$, we prove in Lemma 4 of Section V that the
subset of observable systems is open and everywhere dense; in addition, the
subset of non observable systems is not dense. This means that, if
$\mathfrak{D}(\mathcal{G})$ is structurally accessible (resp. structurally
observable), any of its systems is either accessible (resp. observable) or
becomes accessible (resp. observable) by an arbitrarily small change of its
dynamics (see example Example 2 below).

Our main result is the following:

######  Theorem 2.

$\mathfrak{D}(\mathcal{G})$ is:

  * (i)

structurally accessible iff each state node is the end-node of a path that
starts in ${\sf U}$.

  * (ii)

structurally observable iff each state node is the start-node of a path that
ends in ${\sf Y}$.

###### Proof.

See Proposition 2 in Section IV for point (i), and Proposition 3 in Section V
for point (ii). ∎

The above Theorem shows that despite the observability of a nonlinear system
may depend on which particular inputs are applied to it, its structural
observability is independent of the inputs. This happens because removing all
edges that connect the inputs to the state variables will not change if
condition (ii) of Theorem 2 is satisfied. Indeed, note that including more
edges in a graph cannot destroy its structural accessibility or structural
observability. Note also that a “duality” similar to the case of linear
systems remains: a network is structurally accessible if and only if its “dual
network” (with reversed edges and the labels of input and output nodes
interchanged) is structurally observable.

In addition and somewhat counterintuitively, Theorem 2 shows that
nonlinearities make it easier to “control” and “observe” networked systems
because the conditions of Theorem 2 are weaker than those of Theorem 1. We
illustrate this point by revisiting Example 1 now considering nonlinear
dynamics:

######  Example 2.

For the graph in Fig. 1a, the class $\mathfrak{D}(\mathcal{G})$ contains all
nonlinear systems of the form

$\left\\{\begin{split}\dot{x}_{1}(t)&=b_{11}u_{1}(t)+\varepsilon,\\\
\dot{x}_{2}(t)&=b_{21}u_{1}(t)+\varepsilon u_{1}^{3}(t),\\\
y_{1}(t)&=c_{11}x_{1}+c_{12}x_{2}+\varepsilon
x_{1}(t)x_{2}(t),\end{split}\right.$ (4)

with nonzero $b_{11},b_{21}$, and $\varepsilon$. Note that Eq. (4) is an
“$\varepsilon$-change” of Eq. (2) because making $\varepsilon=0$ renders Eq.
(4) equal to Eq. (2). Note also:

  * 1.

In the dilation of Fig. 1a, the nonlinearities in $\mathfrak{D}(\mathcal{G})$
eliminate the autonomous element that was present in
$\mathfrak{D}_{L}(\mathcal{D})$. That is, the function
$\xi(x)=b_{21}x_{1}-b_{11}x_{2}$ that was an autonomous element for all linear
dynamics of Eq. (2) is no longer an autonomous element for Eq. (4) because
$\dot{\xi}=-\varepsilon b_{11}u_{1}^{3}$ depends on $u_{1}$. This proves that
$\mathfrak{D}(\mathcal{G})$ is structurally accessible. Indeed, the
trajectories of Eq. (4) are no longer constrained to a low-dimensional
manifold (Fig. 1d).

  * 2.

In the contraction of Fig. 1a, the nonlinearities in
$\mathfrak{D}(\mathcal{G})$ also eliminate the hidden element. To see this,
compute
$\dot{y}_{1}=\alpha_{0}(u_{1})+\varepsilon\alpha_{1}(u_{1})x_{1}+\varepsilon\alpha_{2}(u_{1})x_{2},$
where $\alpha_{0}(u_{1})=c_{11}[b_{11}u_{1}+\varepsilon
p_{1}]+c_{12}[b_{21}u_{1}+\varepsilon u_{1}^{3}]$,
$\alpha_{1}(u_{1})=b_{21}u_{1}+\varepsilon u_{1}^{3}$ and
$\alpha_{2}(u_{1})=b_{11}u_{1}+\varepsilon p_{1}$. Note that
$\alpha_{1}\not\equiv 0$ and $\alpha_{2}\not\equiv 0$ for almost all $u_{1}$.
Therefore, the Jacobian

$\begin{pmatrix}\partial y_{1}/\partial x\\\ \partial\dot{y}_{1}/\partial
x\end{pmatrix}=\begin{pmatrix}c_{11}+\varepsilon x_{2}&c_{12}+\varepsilon
x_{1}\\\ \varepsilon\alpha_{1}&\varepsilon\alpha_{2}\end{pmatrix}$

is generically nonsingular. Consequently, from the Implicit Function Theorem,
it follows that we can locally infer $x_{1}$ and $x_{2}$ from $y_{1}$ and
$\dot{y}_{1}$. Indeed, the function $\zeta=c_{12}x_{1}-c_{11}x_{1}$ that was a
hidden element of the linear system of Eq. (2) is no longer a hidden element
of Eq. (4). This proves that Eq. (4) is observable (Fig. 1e), and that
$\mathfrak{D}(\mathcal{G})$ is structurally observable.

###  III-A Minimal sets of driver/sensor nodes and input/output nodes.

Consider graph $\mathcal{G}({\sf X},{\sf A})$ consisting of state nodes $\sf
X$ and edges $({\sf x}_{i}\rightarrow{\sf x}_{j})\in{\sf A}$. We can extend
Definition 1 to nonlinear systems by requiring that a set of driver nodes
${\sf X}_{D}\subseteq\sf X$ renders $\mathcal{G}(\sf X\cup\sf U,\sf A\cup B)$
structurally accessible. Similarly, a set of sensor nodes ${\sf
X}_{S}\subseteq\sf X$ must render $\mathcal{G}(\sf X\cup\sf U,\sf A\cup C)$
structurally observable. Then Theorem 2 has the following implication:

######  Proposition 1.

  * (i)

A minimal set of driver nodes is given by arbitrarily choosing one node in
each root strongly-connected-component of $\mathcal{G}({\sf X},\sf A)$.

  * (ii)

A minimal set of sensor nodes is given by arbitrarily choosing one node in
each top strongly-connected-component of $\mathcal{G}({\sf X},\sf A)$.

A strongly connected component (SCC) of a graph $\mathcal{G}$ is a maximal
subgraph such that there is a directed path in both directions between any two
of its nodes [14, pp. 552-557]. A root SCC is an SCC without incoming edges,
and a top SCC is an SCC without outgoing edges. Recall that any directed graph
can be decomposed into an acyclic graph between its SCCs, with root and top
SCCs at the start and end of this graph, respectively [14]. Let $m$ be the
number of root SCCs and $p$ the number of top SCCs of $\mathcal{G}({\sf X},\sf
A)$. Then a proof of Proposition 1-(i) is obtained from the fact that if a
single input node $\sf u$ is connected to one arbitrary node ${\sf x}_{j}$ of
each root SCC (i.e., ${\sf u}\rightarrow{\sf x}_{j}$, $j=1,\cdots,m$), the
decomposition into the acyclic graph of SCC implies that the graph satisfies
condition (i) of Theorem 2. Analogously, a proof of Proposition 1-(ii) is
obtained from the fact that if a single output node $\sf y$ is connected with
one arbitrary node ${\sf x}_{j}$ of each top SCC (i.e., ${\sf
x}_{j}\rightarrow{\sf y}$, $j=1,\cdots,p$), this will yield a graph that
satisfies condition (ii) of Theorem 2. An additional consequence of this
argument is the following:

######  Corollary 1.

  * (i)

The minimal number of driver nodes of any graph is its number of root SCCs,
and the minimal number of sensor nodes is its number of top SCCs.

  * (ii)

The minimal number of input nodes that renders any graph structurally
accessible is always one, and the minimal number of output nodes that renders
any graph structurally observable is also one.

The second statement in the above Corollary generalizes the result of Ref.
[15] to structural systems and to the case of analyzing observability.

All minimal sets of driver or sensor nodes of arbitrary graphs can be found in
linear time, since the SCCs of general graphs can be computed in linear time
[14, pp. 35]. For comparison, in the case of linear structural accessibility
(resp. linear structural observability), solving the maximum-matching problem
to find one set of driver nodes (resp. sensor nodes) takes polynomial time,
and identifying all sets of driver nodes (resp. sensor nodes) is intractable
for large graphs.

The following two Sections build the proofs for our main results.

##  IV Proof of the Structural Accessibility Theorem

Given a graph $\mathcal{G}=({\sf X\cup\sf U},\sf A\cup B)$, here we consider
the class $\mathfrak{D}(\mathcal{G})$ of all controlled systems

$\dot{x}(t)=f(x(t),u(t)),$ (5)

such that $\mathcal{G}_{f}=\mathcal{G}$.

Our first result shows that accessible systems are “generic” in a structurally
accessible class $\mathfrak{D}(\mathcal{G})$, while non-accessible are not
(i.e., they are “hard to find”). To establish this result, our argument relies
on the notions of the _$k$ -jet_ $f_{k}$ of the meromorphic function $f$
—informally defined as taking the first $k$-terms of its Taylor expansion— and
the resulting topology that can be constructed —the so-called “Whitney $C^{k}$
topologies”. We refer the reader to [16, Section 2.1] and [17, Chapter II.3]
for further details. Specifically, the topology we use is defined from the
notion of an open ball of radius $\varepsilon\geq 0$ centered at a meromorphic
$f_{0}$. This ball consists of all meromorphic $f$’s for which $\exists
k\in\mathbb{N}$ such that the Euclidean distance between the first $\ell$
Taylor coefficients of $f_{0}$ and $f$ is less than $\varepsilon$ for all
$\ell\geq k$.

Figure 2:  Figures for the proof of Lemma 1. a. Accessible systems are dense.
b. The subset of accessible systems is open. c. Contradiction obtained by
assuming that the subset of non-accessible systems is dense, proving that non-
accessible systems are not dense.

######  Lemma 1.

If $\mathfrak{D}(\mathcal{G})$ is structurally accessible then: (i) the subset
of accessible systems is dense everywhere in $\mathfrak{D}(\mathcal{G})$; (ii)
the subset of accessible systems is open; and (iii) the subset of non-
accessible systems is not dense.

###### Proof.

Although (iii) $\Rightarrow$ (i) because $\mathfrak{D}(\mathcal{G})$ is the
disjoint union of accessible and non-accessible systems, independent proofs of
each statement are provided:

  * (i)

We show that any $f\in\mathfrak{D}(\mathcal{G})$ has an arbitrarily close
neighbor $\tilde{f}\in\mathfrak{D}(\mathcal{G})$ that is accessible (Fig. 2a).
Let $f^{*}\in\mathfrak{D}(\mathcal{G})$ be an accessible system in
$\mathfrak{D}(\mathcal{G})$ (there is at least one because of the definition
of structural accessibility). Define the convex combination
$f_{\lambda}=\lambda f^{*}+(1-\lambda)f$. Note that
$f_{\lambda}\in\mathfrak{D}(\mathcal{G})$ for almost all $\lambda\in[0,1]$.
Note also that for $\lambda=1$ we have $f_{1}=f^{*}$, implying that $f_{1}$ is
accessible. Consequently, due to the generic properties of meromorphic
functions and the Accessibility rank condition [11], the family of systems
$\\{f_{\lambda}\\}$ are accessible for almost all $\lambda\in[0,1]$.
Therefore, for any $\varepsilon>0$, there exists $\lambda^{*}>0$ such that
$\lambda^{*}<\varepsilon$ and $f_{\lambda^{*}}$ is accessible. Thus,
$f_{\lambda^{*}}$ is an $\varepsilon$-neighbor of $f$ which is accessible,
completing the proof.

  * (ii)

We prove that any accessible $f\in\mathfrak{D}(\mathcal{G})$ has a
neighborhood consisting only of accessible systems. Since $f$ is meromorphic,
we can rewrite this function as the Taylor-expansion
$f(x,u)=\alpha_{0}(x)+\sum_{i=1}^{\infty}\alpha_{i}(x)u^{i}$ with
$\alpha_{i}\in\mathcal{K}$. Note that the accessibility of $f$ implies there
exists a $k\in\mathbb{\mathbb{missing}}N$ such that the $k$-jet
$f_{k}(x,u):=\alpha_{0}(x)+\sum_{i=1}^{k}\alpha_{i}(x)u^{i}$ is accessible.
Indeed, since $f$ is accessible there cannot be autonomous elements
$\xi\in\mathcal{K}$, implying that $\mathrm{d}\xi$ is not orthogonal to at
least some $\alpha_{k}$, $k\in\mathbb{N}$. This implies that no (non-constant)
$\xi\in\mathcal{K}$ can be an autonomous element for $f_{k}$, making the
$k$-jet $f_{k}$ accessible.

Recall that this $k$-jet represents the first $k$ terms of the Taylor
expansion of $f$, implying we can associate $f_{k}$ to a point in
$\mathbb{R}^{K}$ for some $K$ that depends on $k$ (right in Fig. 2b). Next we
regard $f_{k}$ as a polynomial function of its Taylor coefficients, so that
the generic properties of meromorphic functions imply that $f_{k}$ has a
neighborhood $N_{f_{k}}\subseteq\mathbb{R}^{K}$ of accessible systems. All
$\tilde{f}\in\mathfrak{D}(\mathcal{G})$ such that their $k$-jets
$\tilde{f}_{k}$ satisfy $\tilde{f}_{k}\in N_{f_{k}}$ will form the open
neighborhood of $f$ of accessible systems.

  * (iii)

We prove by contradiction, assuming that $\mathfrak{D}(\mathcal{G})$ is
structurally accessible but that it contains an open set $\mathfrak{N}$ such
that non-accessible systems are dense on it (pink in Fig. 2c). Since
$\mathfrak{D}(\mathcal{G})$ is structurally accessible and accessible systems
are dense due to Lemma 1-(i), then $\mathfrak{N}$ contains at least one
accessible system $f$ (blue in Fig. 2c). Now choose $k\geq 0$ large enough
such that the $k$-jet $f_{k}$ of the accessible system $f$ is accessible. The
$k$-jets $\tilde{f}_{k}$ of all non-accessible systems $\tilde{f}$’s remain
non-accessible. Since the $f_{k}$ and the $\tilde{f}_{k}$’s represent the
first $k$ terms of the Taylor expansion of $f$ and the $\tilde{f}$’s, we can
associate each of them to a point in $\mathbb{R}^{K}$ corresponding to the
value of the first $k$ coefficients of their Taylor expansion (here again $K$
is some constant that depends on $k$). Since $\mathfrak{N}$ is a neighborhood
of $f$, all its elements are mapped to a corresponding neighborhood of $f_{k}$
in $\mathbb{R}^{K}$ such that the points corresponding to non-accessible
systems are dense (Fig. 2c). Considering now that $f_{k}$ is accessible and
that it is a polynomial function of its Taylor coefficients, the generic
properties of meromorphic functions imply that there exists a neighborhood
$N_{f_{k}}\subseteq\mathbb{R}^{K}$ of $f_{k}$ such that all its corresponding
elements are accessible (blue neighborhood in Fig. 2c). This gives the desired
contradiction, since it contradicts the fact that the non-accessible systems
were dense.

∎

The next result allows us to analyze the structural accessibility of a graph
from its _spanning_ subgraphs, which will be instrumental for the proof of the
main result. Recall that a subgraph $\tilde{\mathcal{G}}$ of $\mathcal{G}$ is
spanning when $\tilde{\mathcal{G}}$ includes all nodes of $\mathcal{G}$.

######  Lemma 2.

Let $\tilde{\mathcal{G}}\subseteq\mathcal{G}$ be any spanning subgraph of
$\mathcal{G}$. If $\mathfrak{D}(\tilde{\mathcal{G}})$ is structurally
accessible then $\mathfrak{D}({\mathcal{G}})$ is also structurally accessible.

###### Proof.

Since $\mathfrak{D}(\tilde{\mathcal{G}})$ is structurally accessible, it
contains one system $\dot{x}=f(x,u)$ which is accessible. Notice that starting
from $\tilde{\mathcal{G}}$, we can recover $\mathcal{G}$ by adding some edges.
Suppose that the edge ${\sf x}_{j}\rightarrow{\sf x}_{i}$ is added to
$\tilde{\mathcal{G}}$ to obtain $\mathcal{G}$. Then
$\mathfrak{D}(\mathcal{G})$ contains the systems

$\dot{x}_{i}=f_{i}(x,u)+\alpha x_{j},$ (6)

for any constant $\alpha\neq 0$. Similarly, if the edge ${\sf
u}_{j}\rightarrow{\sf x}_{i}$ is added $\mathfrak{D}(\mathcal{G})$ contains
the systems

$\dot{x}_{i}=f_{i}(x,u)+\alpha u_{j}.$ (7)

For $\alpha=0$ the systems of Eqs. (6) or (7) are accessible. Additionally,
their right-hand side is a meromorphic function of $\alpha$. Thus, due to the
generic properties of meromorphic functions [11], both systems are accessible
for almost all $\alpha\in\mathbb{R}$. Therefore, the class
$\mathfrak{D}(\mathcal{G})$ is structurally accessible. Repeating the same
argument for all other edges completes the proof. ∎

Now consider a meromorphic function
$\varphi(x,u):\mathbb{R}^{N}\times\mathbb{R}^{M}\rightarrow\mathbb{R}^{N}$ and
a subset of nodes ${\sf V}\subseteq{\sf X\cup\sf U}$. We write $\varphi\in{\sf
S}$ if $\varphi(x)$ depends on _all_ variables $v_{i}$ for all ${\sf
v}_{i}\in{\sf V}$. With this notation, an autonomous element of Eq. (5) is a
non-constant meromorphic function $\varphi(x)$ such that
$\varphi^{(k)}\not\in{\sf U}$ for all $k\geq 0$.

######  Example 3.

For the graph of Fig. 1a with the linear dynamics of Eq. (2) we have that
$\xi=b_{11}x_{2}-b_{21}x_{1}$ satisfies $\xi^{(k)}=0$ for all $k\geq 1$. Thus
we have that $\xi^{(k)}\not\in\sf U$ for all $k$ and hence $\xi$ is an
autonomous element.

Next, for a set $\sf S$ of state nodes, define its “tail-set” $T(\sf
S)\subseteq{\sf V}\cup{\sf U}$ as all nodes which point to $\sf S$ (Fig. 3a).
We denote $T^{k}({\sf S}):=T(T^{k-1}(\sf S))$.

Figure 3:  a. A tree graph $\mathcal{G}$ where each state node has only one
incoming edge and its root is an input node. A set $\sf S$ and its tail-sets
$T(\sf S)$ and $T^{2}(\sf S)$ are marked in green, orange and purple,
respectively. b. From the graph $\mathcal{G}$ with $M=2$ input nodes (dark and
light edges), a spanning subgraph $\tilde{\mathcal{G}}$ (dark edges) is
obtained that has $M$ disjoint trees, one incoming edge per state node, and
roots at the input nodes.

######  Example 4.

Consider a graph $\mathcal{G}$ which is a (connected) directed tree with each
state node ${\sf x}_{i}$ having a single incoming edge, and rooted at a single
input node ${\sf u}_{1}$ (Fig. 3a). Note that the state nodes can be organized
into $L$ layers according to the distance they have to the input node, with
the first layer being all state nodes with distance one. Consider the
polynomial dynamics

$\dot{x}_{i}=(f_{T(i)})^{p_{i}}$ (8)

where $f_{T(i)}=x_{T(i)}$ if ${\sf x}_{i}$ is in layer $\geq 2$, and
$f_{T(i)}=u_{1}$ otherwise. The vector
$p=(p_{1},\cdots,p_{N})\in\mathbb{N}_{+}^{N}$ contains $N$ different integers
with $\min_{k}p_{k}$ large enough.

For this graph $\mathcal{G}$ and the dynamics of Eq. (8), any non-constant
meromorphic function $\varphi\in{\sf S}$ satisfies $\dot{\varphi}\in T({\sf
S})$ for any $\sf S\subseteq\sf X$. Namely, if $\varphi$ depends on
$\\{x_{i},\cdots,x_{k}\\}$, then $\dot{\varphi}$ depends on all variables
$\\{f_{T(i)},\cdots,f_{T(k)}\\}$. To show this, just note that

$\dot{\varphi}=\sum_{i\in\sf S}\frac{\partial\varphi}{\partial
x_{i}}\dot{x}_{i}=\sum_{i\in\sf S}\frac{\partial\varphi}{\partial
x_{i}}f_{T(i)}^{p_{i}}\in T({\sf S}),$

and that no term can cancel out in the sums because they have different
exponents.

This observation allow us to prove that this system is accessible. Indeed,
take any $\sf S\subseteq\sf X$ and any non-constant meromorphic function
$\varphi\in\sf S$. Since all state nodes are the end-node of a $\sf U$-rooted
path, there exists a finite $k$ such that ${\sf u}_{1}\in T^{k}(\sf S)$. Since
$\varphi^{(k)}\in T^{k}({\sf S})$, this implies that $\varphi$ cannot be an
autonomous element.

Combining Example 4 with Lemma 2, we have actually proved the following
result:

######  Lemma 3.

Assume that $\mathcal{G}$ is spanned by a disjoint union of directed trees
rooted at $\sf U$, with each state node having a single incoming edge. Then
$\mathfrak{D}(\mathcal{G})$ is structurally accessible.

We now have all the ingredients for proving our main result:

######  Proposition 2.

$\mathfrak{D}(\mathcal{G})$ is structurally accessible iff each state node is
the end-node of a path that starts in ${\sf U}$.

###### Proof.

  * ($\Leftarrow$)

By contradiction. If there is a state node ${\sf x}_{i}$ that is not the end-
node of any ${\sf U}$-rooted path, then $x_{i}$ itself is an autonomous
element.

  * ($\Rightarrow$)

Since each state node is the end-node of a $\sf U$-rooted path, note we can
always obtain a spanning subgraph $\tilde{\mathcal{G}}$ of $\mathcal{G}$ such
that: (i) it is a disjoint union of (connected) directed trees rooted at $\sf
U$; (ii) each state node has a single incoming edge (Fig. 2b). By Lemma 3, the
class $\mathfrak{D}({\mathcal{G}})$ is structurally accessible.

∎

######  Remark 1.

Note that in the trivial cases of an empty graph (i.e., a graph without nodes)
or a graph without state nodes (i.e., the underlying system has no dynamics),
applying Definition 4 yields that both graphs are structurally accessible
because the set of autonomous element is empty.

######  Remark 2.

Note that, even if $\mathcal{G}$ is linearly structurally controllable, this
does not imply that all nonlinear systems with graph $\mathcal{G}$ are
accessible. For example, the graph corresponding to the system
$\dot{x}_{1}=x_{2}+x_{3}u$, $\dot{x}_{2}=-x_{1}$, and $\dot{x}_{3}=-x_{1}u$ is
linearly structurally controllable. Yet, this nonlinear system is not
accessible because $\xi=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}$ is an autonomous
element.

######  Remark 3.

Note that restricting the system dynamics of Eq. (5) to be affine in the
control input changes the graph conditions for structural accessibility. In
such case, graphs that contains “pure dilations of the control input” as in
Fig.1a are not structurally accesible because those subgraphs only admit
linear dynamics

##  V Proof of the Structural Observability Theorem

We start with the following observation:

######  Lemma 4.

  * (i)

If $\mathfrak{D}(\mathcal{G})$ is structurally observable then the subset of
observable systems is open and dense everywhere in
$\mathfrak{D}(\mathcal{G})$; furthermore, the subset of non observable systems
is not dense.

  * (ii)

Let $\tilde{\mathcal{G}}\subseteq\mathcal{G}$ be any spanning subgraph of
$\mathcal{G}$. If $\mathfrak{D}(\tilde{\mathcal{G}})$ is structurally
observable then $\mathfrak{D}(\mathcal{G})$ is also structurally observable.

###### Proof.

A proof for item (i) follows using the exact same argument as in the proof of
Lemma 1. Similarly, item (ii) follows using the same argument as in the proof
of Lemma 2. ∎

We next prove the structural observability of a particular class of graphs:

######  Lemma 5.

Suppose that $\mathcal{G}(\sf X\cup Y,A\cup C)$ is a (connected) directed tree
topped at a single output node $\sf y$, with each state node having a single
outgoing edge. Then $\mathfrak{D}(\mathcal{G})$ is structurally observable.

###### Proof.

From the structure of the graph we can order its nodes by layers, where nodes
with distance $k$ to the output $\sf y$ belong to the $k$-th layer (Fig. 4a).
We will prove the claim by induction in the number of layers:

  * (i)

For one layer, denote its nodes by $\\{{\sf x}_{1},\cdots,{\sf x}_{d_{1}}\\}$
where $d_{1}$ is the number of nodes. One particular dynamics admissible for
this graph is

$\dot{x}_{i}=c_{i},\ i=1,\dots,d_{1};\quad y=x_{1}x_{2}\cdots x_{d_{1}},$ (9)

with $c_{i}$ some non-zero constants. In the following we show that Eq. (9) is
observable by proving that the span of $\mathrm{d}y$ and its derivatives
$\mathrm{d}y^{(k)}$ equals $\mathop{\sf span}_{\mathcal{K}}\mathrm{d}x$. If
$d_{1}=1$ the claim follows directly, because there is only one state variable
$x_{1}$ and $y=x_{1}$ renders it observable. Consider now that $d_{1}>1$. From
direct calculation we obtain the identity:

$\dot{y}=\frac{\mathrm{d}}{\mathrm{d}t}\left(\prod_{i=1}^{d_{1}}x_{i}\right)=\left(\prod_{i=1}^{d_{1}}x_{i}\right)\left(\sum_{i=1}^{d_{1}}\frac{c_{i}}{x_{i}}\right)=(y)\left(\sum_{i=1}^{d_{1}}\frac{c_{i}}{x_{i}}\right).$

The variable $z:=\dot{y}/y$ is observable from $y$. Therefore, the system of
Eq. (9) will be observable if the span of $\mathrm{d}z$ and its derivatives
$\mathrm{d}z^{(k)}$ equals $\mathop{\sf span}_{\mathcal{K}}\mathrm{d}x$. Note
that

$z^{(k)}=\sum_{i=1}^{d_{1}}(-1)^{k}k!\ \frac{c_{i}^{k+1}}{x_{i}^{k+1}},$

so its differential is

$\mathrm{d}z^{(k)}=\sum_{i=1}^{d_{1}}(-1)^{k+1}(k+1)!\
\frac{c_{i}^{k+1}}{x_{i}^{k+2}}\mathrm{d}x_{i}.$

Taking $k=d_{1}+1$, the set $\\{\mathrm{d}z,\cdots,\mathrm{d}z^{(d_{1}+1)}\\}$
will contain the functions $\\{1/x_{i}^{2},\cdots,1/x_{i}^{d_{i}+3}\\}$,
$i=1,\cdots,d_{1}$, whose span is $\mathop{\sf
span}_{\mathcal{K}}\mathrm{d}x$. This proves that the system of Eq. (9) is
observable, and thus that a graph $\mathcal{G}$ with one layer is locally
observable.

  * (ii)

For the induction step, we show that if a graph $\mathcal{G}$ with $L$ layers
is structurally observable, then a graph with $L+1$ layers is also
structurally observable. By definition, the nodes in the $(L+1)$-th layer are
only connected to nodes in the $L$-th layer. Furthermore, they are connected
in the same way as nodes in the first layer are connected to the output node
(Fig. 4a). Therefore, the argument in point (i) with $y$ replaced by the
corresponding node in the $L$-th layer implies that the nodes in the
$(L+1)$-th layer are observable. This completes the proof.

∎

Figure 4:  a. A tree graph $\mathcal{G}$ topped at ${\sf y}$ with a single
outgoing edge per state node. b. From any graph $\mathcal{G}$ such that each
node has a path to $\sf y$ (dark and light edges), a subgraph
$\tilde{\mathcal{G}}$ (dark edges) can be obtained such that it is a tree
topped at $\sf y$ and each state node has a single outgoing edge.

The final result follows by decomposing the graph into disjoint trees topped
at the output nodes:

######  Proposition 3.

$\mathfrak{D}(\mathcal{G})$ is structurally observable iff each state node is
the start-node of a path that ends in ${\sf Y}$.

###### Proof.

  * ($\Leftarrow$)

By contradiction. If there is a state node ${\sf x}_{i}$ that is not the
start-node of any ${\sf Y}$-topped path, then $x_{i}$ itself is a hidden
element.

  * ($\Rightarrow$)

Since each state node is the start-node of a $\sf Y$-topped path, note we can
always obtain a spanning subgraph $\tilde{\mathcal{G}}$ of $\mathcal{G}$ such
that: (i) it is a disjoint union of (connected) directed trees topped at $\sf
Y$; (ii) each state node has a single outgoing edge (Fig. 4b). By Lemma 5,
$\mathfrak{D}(\tilde{\mathcal{G}})$ is structurally observable. Since
$\tilde{\mathcal{G}}\subseteq\mathcal{G}$ is a spanning subgraph, Lemma 4-(ii)
implies that $\mathfrak{D}(\mathcal{G})$ is structurally observable.

∎

######  Remark 4.

In analogy to Remark 1, in the trivial cases of an empty graph (i.e., a graph
without nodes) or a graph without state nodes (i.e., the underlying system has
no dynamics), applying Definition 4 yields that both graphs are structurally
observable because the set of hidden elements is empty.

##  VI Discussion and Concluding Remarks

The notions of structural accessibility and structural observability that we
have introduced and characterized are nonlinear counterparts of the notions of
linear structural controllability and linear structural observability.

We next discuss some testable predictions offered by our theory. In a recent
study of the locomotion of the worm _C. elegans_ , the ablation of the neuron
PDB was found to generate a dilation in the nervous system connectome that
decreased its (output) structural linear controllability [5]. This loss of
linear controllability was suggested to imply that the worm lost some
“directions” in which it is was able to move, which were experimentally
confirmed by a decreased ability to produce some specific motion patterns
(quantified by a decrease in certain so-called “eigenworms”). Assuming that
the nervous system of the _C. elegans_ is an arbitrary nonlinear system
instead of a linear system, our theory implies that the dilation caused by
ablating PBD cannot decrease the structural accessibility of the _C. elegans_
connectome. Namely, the nervous system of an ablated worm can reach the same
set of states as those of normal worms using perhaps different “longer”
trajectories (e.g., by using different paths in the connectome that yield
different combinations of “eigenworms”). Thus, our structural accessibility
theory predicts that PDB ablated worms can still adopt each body pose that a
non-ablated worm can adopt. More generally, we predict that the ability of a
worm to adopt a body pose is preserved as long as the ablated interneurons do
not fully disconnect an input (i.e., a sensory neuron) or an output (i.e., a
motor neuron).

We emphasize that more detailed predictions for the impact of the network
structure on the controllability or observability properties can be obtained
when the class of dynamics that the system can take is better known —such as
neuronal, ecological, gene regulatory, or epidemic systems, see e.g., [13].
Such an analysis would provide graph conditions for structural accessibility
and structural local observability that are “between” those of Theorem 1
(i.e., linear systems), and those of Theorem 2 (i.e., arbitrary nonlinear
systems). Indeed, note that the conditions of Theorem 2 are always necessary,
but they may not be sufficient when we restrict the system dynamics to belong
to a particular class. For example, in [18] and [19], we analyzed the
structural accessibility and structural local observability properties for the
particular class of nonlinear dynamics found in ecosystems. In this analysis,
we found that the conditions for structural accessibility and structural local
observability for ecological dynamics are indeed stronger than those of
Theorem 2.

Finally, our results provide a broader perspective of what we can deduce about
the controllability or observability properties of a system from knowing only
its interconnection network. We have shown that if the control inputs can
reach all state nodes through a path in the network, then there exists some
admissible system dynamics that is accessible. Similarly, if all state nodes
can reach an output through a path in the network, then there exists some
admissible system dynamics that is locally observable. These two facts suggest
that the interconnection network only encodes the essential information of the
controllability and observability properties of complex systems.

Acknowledgements. M.T.A. gratefully acknowledges the financial support from
CONACyT, México, and LS2N, France. We also thank Yang-Yu Liu and Yu Kawano for
insightful comments about preliminary versions of this paper.

## References

  * [1] A.-L. Barabási, _Network Science_. Cambridge University Press, Cambridge, UK, 2016.
  * [2] A. E. Motter, “Networkcontrology,” _Chaos: An Interdisciplinary Journal of Nonlinear Science_ , vol. 25, no. 9, p. 097621, 2015.
  * [3] Y.-Y. Liu and A.-L. Barabási, “Control principles of complex systems,” _Reviews of Modern Physics_ , vol. 88, no. 3, p. 035006, 2016.
  * [4] J.-M. Dion, C. Commault, and J. Van Der Woude, “Generic properties and control of linear structured systems: a survey,” _Automatica_ , vol. 39, no. 7, pp. 1125–1144, 2003.
  * [5] G. Yan, P. E. Vértes, E. K. Towlson, Y. L. Chew, D. S. Walker, W. R. Schafer, and A.-L. Barabási, “Network control principles predict neuron function in the caenorhabditis elegans connectome,” _Nature_ , vol. 550, no. 7677, p. 519, 2017.
  * [6] Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Observability of complex systems,” _Proceedings of the National Academy of Sciences_ , vol. 110, no. 7, pp. 2460–2465, 2013.
  * [7] A. J. Whalen, S. N. Brennan, T. D. Sauer, and S. J. Schiff, “Observability and controllability of nonlinear networks: The role of symmetry,” _Physical Review X_ , vol. 5, no. 1, p. 011005, 2015.
  * [8] A. J. Gates and L. M. Rocha, “Control of complex networks requires both structure and dynamics,” _Scientific reports_ , vol. 6, p. 24456, 2016.
  * [9] J. G. T. Zañudo, G. Yang, and R. Albert, “Structure-based control of complex networks with nonlinear dynamics,” _Proceedings of the National Academy of Sciences_ , vol. 114, no. 28, pp. 7234–7239, 2017.
  * [10] A. Haber, F. Molnar, and A. E. Motter, “State observation and sensor selection for nonlinear networks,” _IEEE Transactions on Control of Network Systems_ , 2017.
  * [11] G. Conte, C. H. Moog, and A. M. Perdon, _Algebraic methods for nonlinear control systems_. Springer Science & Business Media, 2007.
  * [12] C.-T. Lin, “Structural controllability,” _IEEE Transactions on Automatic Control_ , vol. 19, no. 3, pp. 201–208, 1974.
  * [13] B. Barzel and A.-L. Barabási, “Universality in network dynamics,” _Nature physics_ , vol. 9, no. 10, p. 673, 2013.
  * [14] T. H. Cormen, _Introduction to algorithms_. MIT press, 2009.
  * [15] Y. Kawano, Ü. Kotta, and C. H. Moog, “Any dynamical system is fully accessible through one single actuator and related problems,” _International Journal of Robust and Nonlinear Control_ , vol. 26, no. 8, pp. 1748–1754, 2016.
  * [16] V. I. Arnold, “Lectures on bifurcations in versal families,” in _Vladimir I. Arnold-Collected Works_. Springer, 1972, pp. 271–340.
  * [17] M. Golubitsky and V. Guillemin, _Stable mappings and their singularities_. Springer Science & Business Media, 2012, vol. 14.
  * [18] M. T. Angulo, C. H. Moog, and Y.-Y. Liu, “Controlling microbial communities: a network-based approach,” _bioRxiv_ , p. 149765, 2017.
  * [19] A. Aparicio, J. X. Velasco, C. H. Moog, Y.-Y. Liu, and M. T. Angulo, “Identifying sensor species to predict critical transitions in complex ecosystems,” _bioRxiv_ , p. 472878, 2018.