section[0pt]Supplementary Note :

# Supplementary Materials

Efficient Communication over Complex Dynamical Networks

Giacomo Baggio  Department of Information Engineering, University of Padova,
via Gradenigo, 6/B I-35131 Padova, Italy Virginia Rutten  Gatsby Computational
Neuroscience Unit, University College London, London W1T 4JG, UK Janelia
Research Campus, Howard Hughes Medical Institute, Ashburn, VA, USA Guillaume
Hennequin  Sandro Zampieri

††$\ast$Corresponding author<EMAIL_ADDRESS>contributions.

###### Contents

  1. 1 Controllability and observability Gramians
  2. 2 Derivation of the information capacity formula
  3. 3 Properties of the information capacity and rate
  4. 4 Information rate in the low and high noise regime
  5. 5 Information rate of normal networks
  6. 6 Measures of matrix non-normality and network indicators of non-normality
  7. 7 Information rate of a class of non-normal networks
  8. 8 Optimal communication architectures

##  1 Controllability and observability Gramians

Consider the continuous-time linear time-invariant system

$\displaystyle\begin{split}\frac{\mathrm{d}x(t)}{\mathrm{d}t}&=Ax(t)+Bu(t),\\\
y(t)&=Cx(t),\end{split}$ (S1)

where $t\geq 0$ and $x(0)=x_{0}\in\mathbb{R}^{n}$. Here,
$x(t)\in\mathbb{R}^{n}$, $u(t)\in\mathbb{R}^{m}$, and $y(t)\in\mathbb{R}^{p}$
denote the state, input, and output of the system at time $t$, respectively,
and $A$, $B$, and $C$ are matrices of suitable dimensions. The controllability
Gramian of the system over the interval $[0,T]$, $T>0$, is defined as

$\displaystyle\mathcal{W}=\int_{0}^{T}e^{At}BB^{\top}e^{A^{\top}t}\,\text{d}t,$
(S2)

whereas the observability Gramian of the system over the interval $[0,T]$,
$T>0$, as

$\displaystyle\mathcal{O}=\int_{0}^{T}e^{A^{\top}t}C^{\top}Ce^{At}\,\text{d}t.$
(S3)

The above-defined Gramians matrices $\mathcal{W}$ and $\mathcal{O}$ are always
positive semidefinite, and they are related to the controllability and
observability properties of the linear system in Equation S1. In particular,
the system is controllable if and only if $\mathcal{W}$ is positive definite,
and observable if and only if $\mathcal{O}$ is positive definite (see e.g. (?)
for further details). Furthermore, if $A$ is Hurwitz stable (that is, all the
eigenvalues of $A$ have negative real part), then $\mathcal{W}$ and
$\mathcal{O}$ are well-defined for $T\to\infty$, and they correspond to the
(unique) positive semidefinite solution of the continuous-time Lyapunov
equations $AX+XA^{\top}=-BB^{\top}$ (controllability Gramian) and
$A^{\top}X+XA=-C^{\top}C$ (observability Gramian). From an intuitive
viewpoint, $\mathcal{W}$ is related to the energy needed to steer the system
from an initial state $x_{0}$ to a desired target state $x_{f}$ at time $T$,
i.e. $x(T)=x_{f}$, whereas $\mathcal{O}$ to the energy of the system’s free
response evoked by a certain initial state $x_{0}$ in the interval $[0,T]$,
see e.g. (?, ?, ?).

Similar definitions/interpretations hold for systems governed by discrete-time
dynamics

$\displaystyle\begin{split}x(k+1)&=Ax(k)+Bu(k),\\\ y(k)&=Cx(k),\end{split}$
(S4)

where $k\in\mathbb{N}_{>0}$ and $x(0)=x_{0}\in\mathbb{R}^{n}$. In this case,
the controllability and observability Gramians over the interval $[0,T]$,
$T\in\mathbb{N}$, are given, respectively, by

$\displaystyle\mathcal{W}=\sum_{k=0}^{T-1}A^{k}BB^{\top}(A^{\top})^{k}\ \ \
\text{ and }\ \ \ \mathcal{O}=\sum_{k=0}^{T-1}(A^{\top})^{k}C^{\top}CA^{k}.$
(S5)

If $A$ is Schur stable (all the eigenvalues of $A$ have modulus strictly less
than one), then the infinite-horizon ($T\to\infty$) controllability and
observability Gramians coincide with the positive semidefinite solution of the
discrete-time Lyapunov equation $AXA^{\top}-X=-BB^{\top}$ and
$A^{\top}XA-X=-C^{\top}C$, respectively.

##  2 Derivation of the information capacity formula

Here and throughout the paper, we indicate with $\det(X)$ and
$\operatorname{tr}(X)$ the determinant and trace of matrix $X$, respectively,
and $X\succcurlyeq 0$ ($X\succ 0$) means that $X$ is positive semidefinite
(positive definite, respectively). Further, given two continuous random
variables $x$ and $y$, we let $h(x)$ and $h(x|y)$ denote, respectively, the
differential entropy of $x$ and the conditional differential entropy of $x$
given $y$. The mutual information between two continuous random variable $x$
and $y$ is given by $\mathcal{I}(x;y)=h(x)-h(x|y)$ (?).

We remark that the mutual information between the input and output messages of
a communication channel, further optimized over all power-limited input
distributions, coincides with the maximum achievable rate of reliable
information transmission (Shannon’s channel capacity) when the channel is
_memoryless_ , i.e., when past inputs do not affect the currently transmitted
message (?). This is not, however, the case in our scenario because of inter-
symbol interference. Moreover, even in the memoryless case, to achieve
Shannon’s capacity the encoder and the decoder must keep memory of previous
transmissions. In most applications of network transmission (as those
mentioned in the main text), instead, memory is not available, and so
reconstruction has to be performed on a packet-by-packet basis.

To derive the capacity formula in Equation 5 of the main text, we first
address the case $B=I$, and then we show how to extend the argument to the
general case of rectangular $B$’s. With reference to the communication channel
described in the main text, we focus, without any loss of generality, on the
transmission delivered at time $t=0$. The total information signal in the time
window $[0,T]$ will be the superposition of the signals $y_{k}(t)$’s in the
same window, namely $\sum_{k\in\mathbb{Z}}y_{k}(t)$, $0\leq t\leq T$. In the
latter summation, the signal that contains the “useful” information is given
by $y_{0}(t)$, $0\leq t\leq T$. Let $\mathcal{L}_{2}^{p}[0,T]$ be the Hilbert
space of square integrable functions over the interval $[0,T]$ equipped with
the inner product $\langle
f,g\rangle_{\mathcal{L}_{2}}=\int_{0}^{T}f(t)g(t)\,\mathrm{d}t$, and note that
$y_{0}(t)$, $0\leq t\leq T$, belongs to the finite-dimensional subspace
$\mathcal{Q}$ of $\mathcal{L}_{2}^{p}[0,T]$ generated by the functions
$\\{Ce^{At}e_{i},\ t\in[0,T]\\}_{i=1}^{n}$, where $\\{e_{i}\\}_{i=1}^{n}$
denotes the canonical basis vectors of $\mathbb{R}^{n}$. Thus, $y_{0}(t)$ can
be written as

$\displaystyle y_{0}(t)=\sum_{i=1}^{M}y_{i}f_{i}(t),$ (S6)

where $\\{f_{i}(t)\\}_{i=1}^{M}$ is any orthonormal basis in $\mathcal{Q}$ and

$\displaystyle y_{i}$ $\displaystyle:=\langle
f_{i}(t),y_{0}(t)\rangle_{\mathcal{L}_{2}}=\int_{0}^{T}f_{i}^{\top}(t)y_{0}(t)\,\mathrm{d}t=\underbrace{\int_{0}^{T}f_{i}^{\top}(t)Ce^{At}\,\mathrm{d}t}_{\displaystyle=:F_{i}^{\top}}u_{0}.$
(S7)

Let us define $F:=[F_{1},\dots,F_{M}]^{\top}$ and
$Y_{0}:=[y_{1},\dots,y_{M}]^{\top}$. For all $u_{0}\in\mathbb{R}^{n}$, it
holds

$\displaystyle\langle y_{0}(t),y_{0}(t)\rangle_{\mathcal{L}_{2}}$
$\displaystyle=u_{0}^{\top}\int_{0}^{T}e^{A^{\top}t}C^{\top}Ce^{At}\,\mathrm{d}t\,u_{0}=Y_{0}^{\top}Y_{0}=u_{0}^{\top}F^{\top}Fu_{0}.$
(S8)

The latter equation implies that $F^{\top}F=\mathcal{O}$ where
$\mathcal{O}=\int_{0}^{T}e^{A^{\top}t}C^{\top}Ce^{At}\,\mathrm{d}t$ is the
observability Gramian of the pair $(A,C)$ over the interval $[0,T]$. The
covariance between two components $y_{h}$ and $y_{\ell}$,
$h,\ell=1,2,\dots,M$, is given by
$\mathbb{E}[y_{h}y_{\ell}]=\mathbb{E}\left[F^{\top}_{h}u_{0}u_{0}^{\top}F_{\ell}\right]=F^{\top}_{h}\Sigma
F_{\ell},$ where $\Sigma:=\mathbb{E}[u_{0}u_{0}^{\top}]$. From this fact, it
follows that the covariance of the useful signal $y_{0}(t)$ is

$\displaystyle\Sigma_{y_{0}}:=\mathbb{E}\left[Y_{0}Y_{0}^{\top}\right]=F\Sigma
F^{\top}.$ (S9)

The overall channel noise, here denoted by $r(t)$, is modelled as the sum of
two contributions, namely:

  1. (i)

the additive Gaussian white noise $n(t)$, and

  2. (ii)

the interference term $i(t)$ due to inter-symbol interference.

The noise term $r(t)=n(t)+i(t)$ can be written as, w.r.t. the previously
introduced orthonormal basis $\\{f_{i}(t)\\}_{i=1}^{M}$ of $\mathcal{Q}$,

$\displaystyle r(t)=\sum_{i=1}^{M}r_{i}f_{i}(t)+r_{\perp}(t),$ (S10)

where $r_{\perp}(t)$ belongs to the orthogonal complement of $\mathcal{Q}$ and

$\displaystyle r_{i}$ $\displaystyle:=\langle f_{i}(t),r(t)\rangle_{{\cal
L}_{2}}=\int_{0}^{T}f_{i}^{\top}(t)\left(Ce^{At}\sum_{k=1}^{\infty}e^{AkT}u_{-k}+n(t)\right)\mathrm{d}t=F_{i}^{\top}\sum_{k=1}^{\infty}e^{AkT}u_{-k}+n_{i},$
(S11)

with $n_{i}:=\int_{0}^{T}f_{i}(t)^{\top}n(t)\,\mathrm{d}t$. The covariance
between two noise components $r_{h}$, $r_{\ell}$, $h,\ell=1,2,\dots,M$, is
given by

$\displaystyle\mathbb{E}[r_{h}r_{\ell}]$
$\displaystyle=F_{h}^{\top}\sum_{k=1}^{\infty}e^{AkT}\mathbb{E}[u_{-k}u^{\top}_{-k}]e^{A^{\top}kT}F_{\ell}+\sigma^{2}\int_{0}^{T}\int_{0}^{T}f_{h}^{\top}(t)f_{\ell}(\tau)\delta(t-\tau)\,\mathrm{d}t\,\mathrm{d}\tau=F_{h}^{\top}\sum_{k=1}^{\infty}e^{AkT}\Sigma
e^{A^{\top}kT}F_{\ell}+\sigma^{2}\delta_{h,\ell},$ (S12)

where $\delta_{h,\ell}$ denotes the Kronecker delta function and we implicitly
used the fact that $\\{u_{k}\\}$ are i.i.d. random variables, and $u_{k}$ and
$n_{i}$ are independent for all $k$ and $i$. Therefore, by defining
$R:=[r_{1},\dots,r_{M}]^{\top}$, we have that the covariance of the noise
component in $\mathcal{Q}$ is given by

$\displaystyle\Sigma_{r}:=\mathbb{E}\left[RR^{\top}\right]$
$\displaystyle=F\sum_{k=1}^{\infty}e^{AkT}\Sigma
e^{A^{\top}kT}F^{\top}+\sigma^{2}I=F(\mathcal{W}-\Sigma)F^{\top}+\sigma^{2}I,$
(S13)

where $\mathcal{W}:=\sum_{k=0}^{\infty}e^{AkT}\Sigma e^{A^{\top}kT}$ is the
infinite-horizon controllability Gramian of the discretized pair
$(e^{AT},\Sigma^{1/2})$.

By exploiting the above finite-dimensional representation of the output signal
and noise term and the covariance expressions in Equations S9 and S13, we can
now compute the mutual information (as measured in bits) between the channel
input $u_{0}$ and the corrupted output trajectory over the window $[0,T]$,
$\tilde{Y}_{0}$,

$\displaystyle\mathcal{I}_{T}(u_{0},\tilde{Y}_{0})$
$\displaystyle=h(\tilde{Y}_{0})-h(\tilde{Y}_{0}|u_{0})=h(Y_{0}+R)-h(Y_{0}+R|u_{0})=h(Y_{0}+R)-h(R)$
$\displaystyle=\frac{1}{2}\log_{2}\frac{\det(\Sigma_{y_{0}}+\Sigma_{r})}{\det\Sigma_{r}}=\frac{1}{2}\log_{2}\frac{\det(\sigma^{2}I+\mathcal{O}\mathcal{W})}{\det(\sigma^{2}I+\mathcal{O}(\mathcal{W}-\Sigma))},$
(S14)

where we used the properties of the differential entropy, the fact that
$Y_{0}$ and $R$ are independent Gaussian random variables (?, Ch. 8), and, in
the last step, the similarity invariance of the determinant and the fact that
$F^{\top}F=\mathcal{O}$. Finally, the previous expression yields the
expression of the information capacity with power constraint $P$,

$\displaystyle\mathcal{C}_{T}$
$\displaystyle=\frac{1}{2}\,\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma\leq
P}\mathcal{I}_{T}(u_{0},\tilde{Y}_{0})=\frac{1}{2}\,\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma\leq
P}\log_{2}\frac{\det(\sigma^{2}I+\mathcal{O}\mathcal{W})}{\det(\sigma^{2}I+\mathcal{O}(\mathcal{W}-\Sigma))}.$
(S15)

This concludes the proof for the case $B=I$.

For general input matrices $B\in\mathbb{R}^{n\times m}$, the search space
$\\{\Sigma\in\mathbb{R}^{n\times n},\,\Sigma\succcurlyeq
0,\,\operatorname{tr}\,\Sigma\leq P\\}$ in the maximization of the previously
derived formula should be replaced by $\\{B\Sigma
B^{\top}\,:\,\Sigma\in\mathbb{R}^{m\times m},\ \Sigma\succcurlyeq 0,\
\operatorname{tr}\,\Sigma\leq P\\}.$ Hence, it holds

$\displaystyle\mathcal{C}_{T}=\frac{1}{2}\,\max_{\begin{subarray}{c}\Sigma\succcurlyeq
0,\operatorname{tr}\,\Sigma\leq
P\end{subarray}}\log_{2}\frac{\det(\sigma^{2}I+\mathcal{O}\mathcal{W})}{\det(\sigma^{2}I+\mathcal{O}(\mathcal{W}-B\Sigma
B^{\top}))},$ (S16)

where $\mathcal{W}:=\sum_{k=0}^{\infty}e^{AkT}B\Sigma B^{\top}e^{A^{\top}kT}$
is the infinite-horizon controllability Gramian of the discretized pair
$(e^{AT},B\Sigma^{1/2})$.

To conclude, we show that the constraint $\operatorname{tr}\,\Sigma\leq P$ in
Equation S16 can be replaced by $\operatorname{tr}\,\Sigma=P$. To this end,
Let us define

$\displaystyle
f_{T}(\Sigma):=\log_{2}\frac{\det(\sigma^{2}I+\mathcal{O}\mathcal{W})}{\det(\sigma^{2}I+\mathcal{O}(\mathcal{W}-B\Sigma
B^{\top}))}.$ (S17)

We will show that $f_{T}(\alpha\Sigma)$ is a monotonically increasing function
of $\alpha\geq 0$, that is, for any $\alpha_{1},\,\alpha_{2}\geq 0$ such that
$\alpha_{1}\leq\alpha_{2}$, it holds $f_{T}(\alpha_{1}\Sigma)\leq
f_{T}(\alpha_{2}\Sigma)$. The latter fact clearly implies that the optimal
$\Sigma$ maximizing $f_{T}(\Sigma)$ under the constraint
$\operatorname{tr}\,\Sigma\leq P$, must satisfy the latter constraint with
equality. We have

$\displaystyle f_{T}(\alpha\Sigma)$
$\displaystyle=\log_{2}\frac{\det(\sigma^{2}I+\alpha\mathcal{O}\mathcal{W})}{\det(\sigma^{2}I\alpha\mathcal{O}(\mathcal{W}-B\Sigma
B^{\top}))}$
$\displaystyle=\log_{2}\frac{\det(\alpha\mathcal{O}^{1/2}\mathcal{W}\mathcal{O}^{1/2}+\sigma^{2}I)}{\det(\alpha\mathcal{O}^{1/2}(\mathcal{W}-B\Sigma
B^{\top})\mathcal{O}^{1/2}+\sigma^{2}I)}$
$\displaystyle=\sum_{i=1}^{N}\log_{2}(\alpha\lambda_{i}+\sigma^{2})-\sum_{i=1}^{N}\log_{2}(\alpha\mu_{i}+\sigma_{r}^{2}),$
(S18)

where $\\{\lambda_{i}\\}_{i=1}^{n}$ and $\\{\mu_{i}\\}_{i=1}^{n}$ denotes the
ordered eigenvalues of $\mathcal{O}^{1/2}\mathcal{W}\mathcal{O}^{1/2}$ and
$\mathcal{O}^{1/2}(\mathcal{W}-B\Sigma B^{\top})\mathcal{O}^{1/2}$,
respectively. Taking the derivative w.r.t. $\alpha$ of the previous
expression, we get

$\displaystyle\frac{\mathrm{d}f_{T}(\alpha\Sigma)}{\mathrm{d}\alpha}=\frac{1}{\ln
2}\sum_{i=1}^{N}\frac{\lambda_{i}}{\alpha\lambda_{i}+\sigma^{2}}-\frac{1}{\ln
2}\sum_{i=1}^{N}\frac{\mu_{i}}{\alpha\mu_{i}+\sigma^{2}}.$ (S19)

Since
$\mathcal{O}^{1/2}\mathcal{W}\mathcal{O}^{1/2}\succcurlyeq\mathcal{O}^{1/2}(\mathcal{W}-B\Sigma
B^{\top})\mathcal{O}^{1/2}$, then $\lambda_{i}\geq\mu_{i}$, $i=1,2,\dots,n$.
This yields

$\displaystyle\frac{\mathrm{d}f_{T}(\alpha\Sigma)}{\mathrm{d}\alpha}=\frac{1}{\ln
2}\sum_{i=1}^{N}\frac{\lambda_{i}-\mu_{i}}{(\lambda_{i}\alpha+\sigma^{2})(\mu_{i}\alpha+\sigma^{2})}\geq
0,$ (S20)

which, in turn, implies that $f_{T}(\alpha\Sigma)$ is a monotonically
increasing function of $\alpha\geq 0$, as required.

##  3 Properties of the information capacity and rate

In this Supplementary Note, we collect and discuss some key properties of the
information capacity $\mathcal{C}_{T}$ and information rate $\mathcal{R}_{T}$.
The first result asserts that $\mathcal{C}_{T}$ (and, therefore,
$\mathcal{R}_{T}$) does not independently depend on the available power $P$
and readout noise variance $\sigma^{2}$, but on the “signal-to-noise” ratio
$P/\sigma^{2}$ only.

######  Proposition 1 (Scaling invariance of $\mathcal{C}_{T}$ w.r.t. $P$ and
$\sigma^{2}$).

For all $\alpha>0$, it holds

$\displaystyle\mathcal{C}_{T}(P,\sigma^{2})=\mathcal{C}_{T}(\alpha
P,\alpha\sigma^{2}),$ (S21)

where we made explicit the dependence of $\mathcal{C}_{T}$ on $P$ and
$\sigma^{2}$.

###### Proof.

First observe that if we replace $\Sigma$ and $\sigma^{2}$ with $\alpha\Sigma$
and $\alpha\sigma^{2}$, respectively, then $\mathcal{W}$ is replaced with
$\alpha\mathcal{W}$. This in turn implies that the value of

$\displaystyle
f_{T}(\Sigma,\sigma^{2}):=\log_{2}\frac{\det(\sigma^{2}I+\mathcal{O}\mathcal{W})}{\det(\sigma^{2}I+\mathcal{O}(\mathcal{W}-B\Sigma
B^{\top}))}$ (S22)

is not affected by this change of variables. If $\Sigma^{\star}$ is the input
covariance maximizing $f_{T}(\Sigma,\sigma^{2})$ under the constraint
$\operatorname{tr}\,\Sigma=P$, it holds

$\displaystyle\mathcal{C}_{T}(\alpha P,\alpha\sigma^{2})\geq
f_{T}(\alpha\Sigma^{\star},\alpha\sigma^{2})=f_{T}(\Sigma^{\star},\sigma^{2})=\mathcal{C}_{T}(P,\sigma^{2}).$
(S23)

On the other hand, let $\Sigma^{\star}\succcurlyeq 0$ now denote the input
covariance maximizing $f_{T}(\Sigma,\alpha\sigma^{2})$ under the constraint
$\operatorname{tr}\,\Sigma=\alpha P$. It holds

$\displaystyle\mathcal{C}_{T}(P,\sigma^{2})\geq
f_{T}\left(\frac{1}{\alpha}\Sigma^{\star},\sigma^{2}\right)=f_{T}(\Sigma^{\star},\alpha\sigma^{2})=\mathcal{C}_{T}(\alpha
P,\alpha\sigma^{2}).$ (S24)

Therefore, it must be $\mathcal{C}_{T}(\alpha
P,\alpha\sigma^{2})=\mathcal{C}_{T}(P,\sigma^{2})$. ∎

We now investigate the convexity properties of the maximizing function in
Equation S16, namely

$\displaystyle
f_{T,\sigma^{2}}(\Sigma):=\frac{1}{2}\log_{2}\frac{\det\left(\sigma^{2}I+\mathcal{O}\mathcal{W}\right)}{\det\left(\sigma^{2}I+\mathcal{O}(\mathcal{W}-B\Sigma
B^{\top})\right)},$ (S25)

where we used the subscripts $T$ and $\sigma^{2}$ to make explicit the
dependence of $f$ on the transmission time window and output noise variance,
respectively. The following result provides a sufficient condition under which
the $f_{T,\sigma^{2}}(\Sigma)$ is a concave function of $\Sigma\succcurlyeq
0$.

######  Proposition 2 (Concavity of $f_{T,\sigma^{2}}(\Sigma)$).

Assume that the pair $(A,C)$ is observable. If the following condition is
satisfied

$\displaystyle C^{\top}C\succcurlyeq e^{A^{\top}T}C^{\top}Ce^{AT},$ (S26)

then $f_{T,\sigma^{2}}(\Sigma)$ is a concave function of $\Sigma\succcurlyeq
0$.

###### Proof.

Since $(A,C)$ is observable, $\mathcal{O}$ is positive definite, and hence
invertible. This implies that $\mathcal{W}+\sigma^{2}\mathcal{O}^{-1}$ is
positive definite for every $\Sigma\succcurlyeq 0$. After some algebraic
manipulations, we can rewrite $f_{T,\sigma^{2}}(\Sigma)$ as

$\displaystyle f_{T,\sigma^{2}}(\Sigma)$
$\displaystyle=\frac{1}{2}\log_{2}\frac{\det(\sigma^{2}\mathcal{O}^{-1}+\mathcal{W})}{\det(\sigma^{2}\mathcal{O}^{-1}+e^{AT}\mathcal{W}e^{A^{\top}T})}$
$\displaystyle=\frac{1}{2}\log_{2}\frac{\det(\sigma^{2}\mathcal{O}^{-1}+\mathcal{W})}{\det
e^{2AT}\det(\sigma^{2}e^{-AT}\mathcal{O}^{-1}e^{-A^{\top}T}+\mathcal{W})}$
$\displaystyle=\frac{1}{2}\log_{2}\det\Big{[}(\sigma^{2}\mathcal{O}^{-1}+\mathcal{W})(\sigma^{2}e^{-AT}\mathcal{O}^{-1}e^{-A^{\top}T}+\mathcal{W})^{-1}\Big{]}+\frac{1}{2}\log_{2}\det
e^{-2AT}$
$\displaystyle=-\frac{1}{2}\log_{2}\det\Big{[}(\sigma^{2}\mathcal{O}^{-1}+\mathcal{W})^{-1}(\sigma^{2}e^{-AT}\mathcal{O}^{-1}e^{-A^{\top}T}+\mathcal{W})\Big{]}+\frac{1}{2}\log_{2}\det
e^{-2AT}$ $\displaystyle=-\frac{1}{2\ln
2}\ln\det\left(I+X^{-1}K\right)-\frac{T}{\ln 2}\operatorname{tr}(A),$ (S27)

where we have defined $X:=\sigma^{2}\mathcal{O}^{-1}+\mathcal{W}$ and
$K:=\sigma^{2}e^{-AT}\mathcal{O}^{-1}e^{-A^{\top}T}-\sigma^{2}\mathcal{O}^{-1}$.
Next, since

  1. (i)

$X\succ 0$ is a linear function of $\Sigma$, and

  2. (ii)

from (?), $\ln\det\left(I+X^{-1}K\right)$ is a convex function of $X$ if
$K\succcurlyeq 0$,

it follows that $f_{T,\sigma^{2}}(\Sigma)$ is concave if $K\succcurlyeq 0$. To
conclude we notice that the latter condition is satisfied if

$\displaystyle K\succcurlyeq 0$ $\displaystyle\ \ \Leftrightarrow\ \
\sigma^{2}e^{-AT}\mathcal{O}^{-1}e^{-A^{\top}T}-\sigma^{2}\mathcal{O}^{-1}\succcurlyeq
0$ $\displaystyle\ \ \Leftrightarrow\ \
e^{-AT}\mathcal{O}^{-1}e^{-A^{\top}T}-\mathcal{O}^{-1}\succcurlyeq 0$
$\displaystyle\ \ \Leftrightarrow\ \
-e^{A^{\top}T}\mathcal{O}e^{AT}+\mathcal{O}\succcurlyeq 0$ $\displaystyle\ \
\Leftrightarrow\ \
\int_{0}^{T}e^{A^{\top}t}(-e^{A^{\top}T}C^{\top}Ce^{AT}+C^{\top}C)e^{AT}\text{d}t\succcurlyeq
0$ $\displaystyle\ \ \Leftrightarrow\ \
-e^{A^{\top}T}C^{\top}Ce^{AT}+C^{\top}C\succcurlyeq 0.$ (S28)

This completes the proof. ∎

As a side remark, it is worth pointing out that the condition in Proposition 2
always holds if $A$ is stable and normal and $C=I$, since
$\|e^{X}\|=\lambda_{\max}(e^{X}(e^{X})^{\top})<1$ for normal and stable $X$’s,
where $\lambda_{\max}(\cdot)$ denotes the largest eigenvalue of a symmetric
matrix.

Next, we focus on the monotonicity properties of $f_{T,\sigma^{2}}(\Sigma)$
with respect to $\sigma^{2}$.

######  Proposition 3 (Monotonicity of $f_{T,\sigma^{2}}(\Sigma)$ w.r.t.
$\sigma^{2}$).

For all $\sigma^{2}_{2}\geq\sigma^{2}_{1}>0$ and $\Sigma\succcurlyeq 0$, it
holds

$\displaystyle f_{T,\sigma^{2}_{1}}(\Sigma)$ $\displaystyle\geq
f_{T,\sigma^{2}_{2}}(\Sigma),$ (S29)
$\displaystyle{\sigma^{2}_{1}}{f_{T,\sigma^{2}_{1}}(\Sigma)}$
$\displaystyle\leq{\sigma^{2}_{2}}{f_{T,\sigma^{2}_{2}}(\Sigma)}.$ (S30)

###### Proof.

Given $\sigma^{2}>0$, by using the properties of logarithms,
$f_{T,\sigma^{2}}(\Sigma)$ can be rewritten as

$\displaystyle
f_{T,\sigma^{2}}(\Sigma)=\sum_{i=1}^{n}\log_{2}\left(\frac{1+\lambda_{i}/\sigma^{2}}{1+\mu_{i}/\sigma^{2}}\right),$
(S31)

where $\\{\lambda_{i}\\}_{i=1}^{n}$, $\lambda_{1}\geq\dots\geq\lambda_{n}$,
and $\\{\mu_{i}\\}_{i=1}^{n}$, $\mu_{1}\geq\dots\geq\mu_{n}$, are the
eigenvalues of the positive (semi)definite matrices
$\mathcal{O}^{1/2}\mathcal{W}\mathcal{O}^{1/2}$ and
$\mathcal{O}^{1/2}(\mathcal{W}-B\Sigma B^{\top})\mathcal{O}^{1/2}$,
respectively. By virtue of Weyl’s Monotonicity Theorem (?, Corollary III.2.3),
it holds $\lambda_{i}\geq\mu_{i}$ for all $i=1,2,\dots,n$. It is now a matter
of direct computation to show that if $\lambda>\mu>0$,

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}x}\,\log_{2}\left(\frac{1+\lambda/x}{1+\mu/x}\right)>0,\quad
x>0,$ (S32)
$\displaystyle\frac{\mathrm{d}}{\mathrm{d}x}\,x\log_{2}\left(\frac{1+\lambda/x}{1+\mu/x}\right)<0,\quad
x>0.$ (S33)

In view of the latter inequalities, it follows that each term in the sum
defining $f_{T,\sigma^{2}}(\Sigma)$ is a monotonically decreasing function of
$\sigma^{2}>0$, whereas each term in the sum defining
$\sigma^{2}f_{T,\sigma^{2}}(\Sigma)$ is monotonically increasing function of
$\sigma^{2}>0$. ∎

######  Proposition 4 (Monotonicity of $f_{T,\sigma^{2}}(\Sigma)$ w.r.t. $T$).

Suppose that the pair $(A,C)$ is observable and $\sigma^{2}>0$. For all
$T_{1}>0$, $T_{2}=hT_{1}$, $h\in\mathbb{N}_{>0}$, and $\Sigma\succcurlyeq 0$,
it holds

$\displaystyle f_{T_{2},\sigma^{2}}(\Sigma)\geq f_{T_{1},\sigma^{2}}(\Sigma).$
(S34)

###### Proof.

Since $T_{2}\geq T_{1}$, we have

$\displaystyle\mathcal{O}_{T_{2}}:=\int_{0}^{T_{2}}e^{A^{\top}t}C^{\top}Ce^{At}\mathrm{d}t\succcurlyeq\int_{0}^{T_{1}}e^{A^{\top}t}C^{\top}Ce^{At}\mathrm{d}t=:\mathcal{O}_{T_{1}}\succ
0,$ (S35)

where positive definiteness follows from observability of the pair $(A,C)$.
Furthermore, since $T_{2}=hT_{1}$, $h\in\mathbb{N}_{>0}$,

$\displaystyle\mathcal{W}_{T_{1}}:=\sum_{k=0}^{\infty}e^{AkT_{1}}B\Sigma
B^{\top}e^{A^{\top}kT_{1}}\succcurlyeq\sum_{k=0}^{\infty}e^{AkhT_{1}}B\Sigma
B^{\top}e^{A^{\top}khT_{1}}=:\mathcal{W}_{T_{2}}.$ (S36)

Next, we can rewrite $f_{T,\sigma^{2}}(\Sigma)$ as

$\displaystyle f_{T,\sigma^{2}}(\Sigma)$
$\displaystyle=\frac{1}{2}\log_{2}\det\Big{[}\left(\sigma^{2}I+\mathcal{O}\mathcal{W}\right)\left(\sigma^{2}I+\mathcal{O}(\mathcal{W}-B\Sigma
B^{\top})\right)^{-1}\Big{]}$
$\displaystyle=\frac{1}{2}\log_{2}\det\Big{[}I+\mathcal{O}B\Sigma
B^{\top}\left(\sigma^{2}I+\mathcal{O}(\mathcal{W}-B\Sigma
B^{\top})\right)^{-1}\Big{]}$
$\displaystyle=\frac{1}{2}\log_{2}\det\Big{[}I+B\Sigma
B^{\top}\left(\sigma^{2}I+\mathcal{O}(\mathcal{W}-B\Sigma
B^{\top})\right)^{-1}\mathcal{O}\Big{]}$
$\displaystyle=\frac{1}{2}\log_{2}\det\Big{[}I+B\Sigma
B^{\top}((\mathcal{W}-B\Sigma
B^{\top})+{\sigma^{2}\mathcal{O}^{-1}})^{-1}\Big{]}$
$\displaystyle=\frac{1}{2}\log_{2}\det\Big{[}I+(B\Sigma
B^{\top})^{1/2}(e^{AT}\mathcal{W}e^{A^{\top}T}+{\sigma^{2}\mathcal{O}^{-1}})^{-1}(B\Sigma
B^{\top})^{1/2}\Big{]},$ (S37)

In view of Equations S35 and S36, we have
$\mathcal{O}_{T_{2}}^{-1}\preccurlyeq\mathcal{O}_{T_{1}}^{-1}$, and

$\displaystyle\mathcal{W}_{T_{1}}+\sigma^{2}\mathcal{O}_{T_{1}}^{-1}\succcurlyeq\mathcal{W}_{T_{2}}+\sigma^{2}\mathcal{O}_{T_{2}}^{-1}$
$\displaystyle\Rightarrow\ \ \ $
$\displaystyle\left(\mathcal{W}_{T_{1}}+\sigma^{2}\mathcal{O}_{T_{1}}^{-1}\right)^{-1}\preccurlyeq\left(\mathcal{W}_{T_{2}}+\sigma^{2}\mathcal{O}_{T_{2}}^{-1}\right)^{-1}$
$\displaystyle\Rightarrow\ \ \ $ $\displaystyle(B\Sigma
B^{\top})^{1/2}\left(\mathcal{W}_{T_{1}}+\sigma^{2}\mathcal{O}_{T_{1}}^{-1}\right)^{-1}(B\Sigma
B^{\top})^{1/2}\preccurlyeq(B\Sigma
B^{\top})^{1/2}\left(\mathcal{W}_{T_{2}}+\sigma^{2}\mathcal{O}_{T_{2}}^{-1}\right)^{-1}(B\Sigma
B^{\top})^{1/2}$ $\displaystyle\Rightarrow\ \ \ $ $\displaystyle I+(B\Sigma
B^{\top})^{1/2}\left(\mathcal{W}_{T_{1}}+\sigma^{2}\mathcal{O}_{T_{1}}^{-1}\right)^{-1}(B\Sigma
B^{\top})^{1/2}\preccurlyeq I+(B\Sigma
B^{\top})^{1/2}\left(\mathcal{W}_{T_{2}}+\sigma^{2}\mathcal{O}_{T_{2}}^{-1}\right)^{-1}(B\Sigma
B^{\top})^{1/2}.$ (S38)

Finally, from Section 3, the latter inequality implies
$f_{T_{2},\sigma^{2}}(\Sigma)\geq f_{T_{1},\sigma^{2}}(\Sigma)$. ∎

We note that, in the limit $T\to\infty$, $\mathcal{W}\to B\Sigma B^{\top}$ and
$\mathcal{O}\to\int_{0}^{T}e^{A^{\top}t}C^{\top}Ce^{At}\,\text{d}t=\mathcal{O}_{\infty}$,
which are both finite matrices since $A$ is stable. Hence, it follows that

$\displaystyle\lim_{T\to\infty}f_{T,\sigma^{2}}(\Sigma)=\log_{2}\det\left(I+\frac{1}{\sigma^{2}}\mathcal{O}_{\infty}B\Sigma
B^{\top}\right),$ (S39)

which is finite. From Proposition 4, this in turn implies that
$f_{T,\sigma^{2}}(\Sigma)$ attains its maximum for $T\to\infty$.

To conclude, we establish a monotonicity property of the capacity with respect
to a particular choice of the input and output matrices $B$ and $C$.

######  Proposition 5 (Monotonicity of $\mathcal{C}_{T}$ w.r.t. $B$ and $C$).

Assume that the pair $(A,C)$ is observable, and let

$\displaystyle B_{1}$ $\displaystyle=\begin{bmatrix}I_{m_{1}}\\\
0\end{bmatrix},\quad C_{1}=\begin{bmatrix}0&I_{p_{1}}\end{bmatrix},$ (S40)
$\displaystyle B_{2}$ $\displaystyle=\begin{bmatrix}I_{m_{2}}\\\
0\end{bmatrix},\quad C_{2}=\begin{bmatrix}0&I_{p_{2}}\end{bmatrix},$ (S41)

be two pairs of input and output matrices. If $m_{2}\geq m_{1}$ and $p_{2}\geq
p_{1}$, then

$\displaystyle\mathcal{C}_{T}(B_{1},C_{1})\leq\mathcal{C}_{T}(B_{2},C_{2}),$
(S42)

where we made explicit the dependence of $\mathcal{C}_{T}$ on the input matrix
$B$ and output matrix $C$.

###### Proof.

First, as in the proof of Proposition 4, we have that Equation S25 can be
rewritten as

$\displaystyle
f_{T,\sigma^{2}}(\Sigma)=\frac{1}{2}\log_{2}\det\Big{[}I+(B\Sigma
B^{\top})^{1/2}(e^{AT}\mathcal{W}e^{A^{\top}T}+{\sigma^{2}\mathcal{O}^{-1}})^{-1}(B\Sigma
B^{\top})^{1/2}\Big{]},$ (S43)

Next, since $p_{2}\geq p_{1}$, we have

$\displaystyle\mathcal{O}_{1}:=\int_{0}^{T}e^{A^{\top}t}C_{1}^{\top}C_{1}e^{At}\,\mathrm{d}t\preccurlyeq\int_{0}^{T}e^{A^{\top}t}C_{2}^{\top}C_{2}e^{At}\,\mathrm{d}t=:\mathcal{O}_{{2}}.$
(S44)

From the previous inequality and the observability of $(A,C)$, we have
$\mathcal{O}_{1}^{-1}\succcurlyeq\mathcal{O}_{2}^{-1}$. This in turn implies
that

$\displaystyle\mathcal{W}+\sigma^{2}\mathcal{O}_{1}^{-1}\succcurlyeq\mathcal{W}+\sigma^{2}\mathcal{O}_{2}^{-1}$
$\displaystyle\Rightarrow\ \ \ $
$\displaystyle\left(\mathcal{W}+\sigma^{2}\mathcal{O}_{1}^{-1}\right)^{-1}\preccurlyeq\left(\mathcal{W}+\sigma^{2}\mathcal{O}_{2}^{-1}\right)^{-1}$
$\displaystyle\Rightarrow\ \ \ $ $\displaystyle(B\Sigma
B^{\top})^{1/2}\left(\mathcal{W}+\sigma^{2}\mathcal{O}_{1}^{-1}\right)^{-1}(B\Sigma
B^{\top})^{1/2}\preccurlyeq(B\Sigma
B^{\top})^{1/2}\left(\mathcal{W}+\sigma^{2}\mathcal{O}_{2}^{-1}\right)^{-1}(B\Sigma
B^{\top})^{1/2}$ $\displaystyle\Rightarrow\ \ \ $ $\displaystyle I-(B\Sigma
B^{\top})^{1/2}\left(\mathcal{W}+\sigma^{2}\mathcal{O}_{1}^{-1}\right)^{-1}(B\Sigma
B^{\top})^{1/2}\preccurlyeq I-(B\Sigma
B^{\top})^{1/2}\left(\mathcal{W}+\sigma^{2}\mathcal{O}_{2}^{-1}\right)^{-1}(B\Sigma
B^{\top})^{1/2}$ (S45)

which in view of Section 3 yields

$\displaystyle f_{T,\sigma^{2}}(\Sigma,B,C_{2})\geq
f_{T,\sigma^{2}}(\Sigma,B,C_{1}),$ (S46)

for any $B\in\mathbb{R}^{n\times m}$ and $\Sigma\succcurlyeq 0$, where we made
explicit the dependence of $f_{T,\sigma^{2}}(\cdot)$ on the input matrix $B$
and output matrix $C$. From the previous inequality, it follows that

$\displaystyle\mathcal{C}_{T}(B,C_{1})=\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=P}f_{T,\sigma^{2}}(\Sigma,B,C_{1})\leq\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=P}f_{T,\sigma^{2}}(\Sigma,B,C_{2})=\mathcal{C}_{T}(B,C_{2}).$
(S47)

Now, let us define

$\displaystyle\mathcal{S}_{1}:=\\{B_{1}\Sigma_{1}B_{1}\,:\,\Sigma_{1}\succcurlyeq
0,\
\operatorname{tr}\,\Sigma_{1}=P\\},\quad\mathcal{S}_{2}:=\\{B_{2}\Sigma_{2}B_{2}\,:\,\Sigma_{2}\succcurlyeq
0,\ \operatorname{tr}\,\Sigma_{2}=P\\}.$ (S48)

Since $m_{2}\geq m_{1}$, we have $\mathcal{S}_{1}\subseteq\mathcal{S}_{2}$.
This in turn implies that

$\displaystyle\mathcal{C}_{T}(B_{1},C)=\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=P}f_{T,\sigma^{2}}(\Sigma,B_{1},C)=\max_{\Sigma\in\mathcal{S}_{1}}f_{T,\sigma^{2}}(\Sigma,I,C)\leq\max_{\Sigma\in\mathcal{S}_{2}}f_{T,\sigma^{2}}(\Sigma,I,C)=\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=P}f_{T,\sigma^{2}}(\Sigma,B_{2},C)=\mathcal{C}_{T}(B_{2},C).$
(S49)

Finally, a combination of Equations S47 and S49 yields the thesis. ∎

Proposition 5 in particular implies that the maximum capacity is always
attained by picking $B=C=I$, that is, by selecting all nodes in the network as
input/output nodes.

##  4 Information rate in the low and high noise regime

Here, we analyze the behavior of the information rate $\mathcal{R}_{T}$ in the
limit cases where $\sigma^{2}$ tends to either zero or infinity.

######  Theorem 1 (Behavior of $\mathcal{R}_{T}$ in the low noise regime).

Let $A\in\mathbb{R}^{n\times n}$ be a stable matrix and assume that the pair
$(A,C)$ is observable. For all $T>0$, it holds

$\displaystyle\lim_{\sigma^{2}\to 0}\mathcal{R}_{T}$
$\displaystyle=-\frac{1}{\ln 2}\operatorname{tr}(A).$ (S50)

Further, as $\sigma^{2}\to 0$, the optimal $\Sigma$ in Equation S16 is any
positive semidefinite unit-trace matrix such that $(A,B\Sigma^{1/2})$ is
controllable.

###### Proof.

Consider $f_{T,\sigma^{2}}(\Sigma)$ as defined in Equation S25. Since
$f_{T,\sigma^{2}}(\Sigma)$ and $\smash{\displaystyle\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=1}f_{T,\sigma^{2}}(\Sigma)}$ are monotonically
decreasing functions of $\sigma^{2}$ (Proposition 3, Equation S29), we have
that

$\displaystyle\lim_{\sigma^{2}\to 0}\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=1}f_{T,\sigma^{2}}(\Sigma)=\sup_{\sigma^{2}\geq
0}\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=1}f_{T,\sigma^{2}}(\Sigma)=\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=1}\sup_{\sigma^{2}\geq
0}f_{T,\sigma^{2}}(\Sigma)=\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=1}\lim_{\sigma^{2}\to 0}f_{T,\sigma^{2}}(\Sigma).$
(S51)

If $\Sigma$ maximizing $\displaystyle\lim_{\sigma^{2}\to
0}f_{T,\sigma^{2}}(\Sigma)$ is such that $(e^{AT},B\Sigma^{1/2})$ is a
controllable pair, then $\mathcal{W}>0$, and we have

$\displaystyle\frac{1}{T}\lim_{\sigma^{2}\to 0}f_{T,\sigma^{2}}(\Sigma)$
$\displaystyle=\frac{1}{2T}\log_{2}\frac{\det(\mathcal{O}\mathcal{W})}{\det(\mathcal{O}e^{AT}\mathcal{W}e^{A^{\top}T})}$
$\displaystyle=-\frac{1}{2T}\log_{2}\det(e^{AT})^{2}=-\frac{1}{T\ln
2}\ln\det(e^{AT})$ $\displaystyle=-\frac{1}{T\ln
2}\operatorname{tr}(AT)=-\frac{1}{\ln 2}\operatorname{tr}(A),$ (S52)

where in the second equation we used the fact that $\mathcal{O}$ is
invertible, in view of the observability of $(A,C)$. If the maximizing
$\Sigma$ is such that $(e^{AT},B\Sigma^{1/2})$ is _not_ controllable, then,
via a suitable similarity transformation $Q$, we can bring $e^{AT}$ and
$B\Sigma^{1/2}$ in Kalman canonical form (?, Chapter 16), namely

$\displaystyle\overline{A}:=Q^{-1}e^{AT}Q=\begin{bmatrix}A_{11}&A_{12}\\\
0&A_{22}\end{bmatrix},\quad\overline{B}:=Q^{-1}B\Sigma^{1/2}=\begin{bmatrix}B_{1}\\\
0\end{bmatrix},$ (S53)

where $(A_{11},B_{1})$ forms a controllable pair. By partitioning
$\mathcal{O}$ conformably to the block partition of $\overline{A}$, namely,

$\displaystyle\overline{\mathcal{O}}:=Q^{-\top}\mathcal{O}Q^{-1}=\begin{bmatrix}\mathcal{O}_{11}&\mathcal{O}_{12}\\\
\mathcal{O}_{21}&\mathcal{O}_{22}\end{bmatrix},\quad\mathcal{O}_{11}>0,$ (S54)

it follows that,

$\displaystyle\frac{1}{T}\lim_{\sigma^{2}\to 0}f_{T,\sigma^{2}}(\Sigma)$
$\displaystyle=-\frac{1}{T}\log_{2}\det(A_{11})<-\frac{1}{T}\log_{2}\det(e^{AT}),$
(S55)

since the eigenvalues of $A_{11}$ are a subset of eigenvalues of $e^{AT}$.
This in turn implies that the maximum of $\lim_{\sigma^{2}\to
0}f_{T,\sigma^{2}}(\Sigma)$ cannot be achieved by any $\Sigma$ that renders
$(e^{AT},B\Sigma^{1/2})$ not controllable and, therefore, its value is given
by Equation S52. ∎

######  Theorem 2 (Behavior of $\mathcal{R}_{T}$ in the high noise regime).

Let $A\in\mathbb{R}^{n\times n}$ be a stable matrix. For all $T>0$, it holds

$\displaystyle\lim_{\sigma^{2}\to\infty}\sigma^{2}\mathcal{R}_{T}$
$\displaystyle=\frac{1}{2\ln 2T}\|B\mathcal{O}B^{\top}\|.$ (S56)

Further, as $\sigma^{2}\to\infty$, the optimal $\Sigma$ in Equation S16 is
given by $\Sigma^{\star}=vv^{\top}/(v^{\top}v)$, where $v\in\mathbb{R}^{m}$ is
the eigenvector corresponding to the maximum eigenvalue of
$B\mathcal{O}B^{\top}$.

###### Proof.

Since $\sigma^{2}f_{T,\sigma^{2}}(\Sigma)$ and
$\smash{\displaystyle\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=1}\sigma^{2}f_{T,\sigma^{2}}(\Sigma)}$ are
monotonically increasing functions of $\sigma^{2}$ (Proposition 3, Equation
S30),

$\displaystyle\lim_{\sigma^{2}\to\infty}\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=1}\sigma^{2}f_{T,\sigma^{2}}(\Sigma)=\sup_{\sigma^{2}\geq
0}\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=1}\sigma^{2}f_{T,\sigma^{2}}(\Sigma)=\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=1}\sup_{\sigma^{2}\geq
0}\sigma^{2}f_{T,\sigma^{2}}(\Sigma)=\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=1}\lim_{\sigma^{2}\to\infty}\sigma^{2}f_{T,\sigma^{2}}(\Sigma).$
(S57)

Using the Taylor expansion of the natural logarithm $\ln(1+x)=x+\text{h.o.t.}$
as $x\to 0$, it holds

$\displaystyle\ln\det(I+\mathcal{O}\mathcal{W}/\sigma^{2})$
$\displaystyle=\operatorname{tr}(\mathcal{O}\mathcal{W})/\sigma^{2}+\text{h.o.t.}\quad\text{
as }\ \ \sigma^{2}\to\infty,$ (S58)
$\displaystyle\ln\det(I+\mathcal{O}(\mathcal{W}-B^{\top}\Sigma B)/\sigma^{2})$
$\displaystyle=\operatorname{tr}(\mathcal{O}(\mathcal{W}-B^{\top}\Sigma
B))/\sigma^{2}+\text{h.o.t.}\quad\text{ as }\ \ \sigma^{2}\to\infty,$ (S59)

so that

$\displaystyle\lim_{\sigma^{2}\to\infty}\sigma^{2}f_{T,\sigma^{2}}(\Sigma)$
$\displaystyle=\frac{1}{2\ln
2}\lim_{\sigma^{2}\to\infty}\sigma^{2}\ln\frac{\det(I+\mathcal{O}\mathcal{W}/\sigma^{2})}{\det(I+\mathcal{O}(\mathcal{W}-B^{\top}\Sigma
B)/\sigma^{2})}$ $\displaystyle=\frac{1}{2\ln
2}\lim_{\sigma^{2}\to\infty}\sigma^{2}\left(\ln\det(I+\mathcal{O}\mathcal{W}/\sigma^{2})-\ln\det(I+\mathcal{O}(\mathcal{W}-B^{\top}\Sigma
B)/\sigma^{2})\right)$ $\displaystyle=\frac{1}{2\ln
2}\operatorname{tr}(\mathcal{O}B^{\top}\Sigma B).$ (S60)

Next, we note that the following inequality holds (?)

$\displaystyle\operatorname{tr}(\mathcal{O}B^{\top}\Sigma
B)=\operatorname{tr}(B\mathcal{O}B^{\top}\Sigma)\leq\|B\mathcal{O}B^{\top}\|\operatorname{tr}(\Sigma).$
(S61)

On the other hand, by picking $\Sigma^{\star}=vv^{\top}/(v^{\top}v)$, with
$v\in\mathbb{R}^{n}$ being the eigenvector corresponding to the maximum
eigenvalue of $B\mathcal{O}B^{\top}$, we have
$\operatorname{tr}(B\mathcal{O}B^{\top}\Sigma^{\star})=\|B\mathcal{O}B^{\top}\|\operatorname{tr}(\Sigma^{\star})=\|B\mathcal{O}B^{\top}\|$.
Hence,

$\displaystyle\max_{\Sigma\succcurlyeq
0,\operatorname{tr}\Sigma=1}\operatorname{tr}(B\mathcal{O}B^{\top}\Sigma)=\|B\mathcal{O}B^{\top}\|,$
(S62)

from which Equation S56 follows using Equation S57. ∎

##  5 Information rate of normal networks

We derive here an explicit expression for the information information rate of
networks described by a normal adjacency matrix with $B=C=I$. To this end, we
first establish an instrumental lemma. In what follows,
$\operatorname{diag}(X)$ will denote the diagonal matrix with the diagonal
entries of $X$, if $X$ is a matrix, or the entries of $X$ along the diagonal,
if $X$ is a vector.

######  Lemma 1.

Let $P\in\mathbb{C}^{n\times n}$ be a positive definite Hermitian matrix. It
holds $\operatorname{diag}(P^{-1})\succcurlyeq(\operatorname{diag}\,P)^{-1}.$

###### Proof.

Let $\\{e_{i}\\}_{i=1}^{n}$ be the canonical basis in $\mathbb{R}^{n}$, by
Cauchy–Schwarz inequality
$(e_{i}^{\top}Pe_{i})(e_{i}^{\top}P^{-1}e_{i})=\|P^{1/2}e_{i}\|^{2}\|P^{-1/2}e_{i}\|^{2}\geq(e_{i}^{\top}P^{1/2}P^{-1/2}e_{i})^{2}=1,$
so that $e_{i}^{\top}P^{-1}e_{i}\geq(e_{i}^{\top}Pe_{i})^{-1}$ for all
$i=1,\dots,n$. ∎

######  Theorem 3 (information rate of normal networks).

If $B=C=I$ and $A\in\mathbb{R}^{n\times n}$ is a normal and stable matrix with
eigenvalues $\\{\lambda_{i}\\}_{i=1}^{n}$, then

$\displaystyle\mathcal{R}_{T}=\max_{\begin{subarray}{c}\\{P_{i}\\}_{i=1}^{n},P_{i}\geq
0\\\ \text{\ s.t.\
}\sum_{i=1}^{n}P_{i}=P\end{subarray}}\sum_{i=1}^{n}\mathcal{R}_{T}(P_{i},\lambda_{i}),$
(S63)

with

$\displaystyle\mathcal{R}_{T}(P,\lambda):=\frac{1}{2T}\log_{2}\frac{\frac{P}{\sigma^{2}}-2\mathrm{Re}\,\lambda}{\frac{P}{\sigma^{2}}\,e^{2T\mathrm{Re}\,\lambda}-2\mathrm{Re}\,\lambda}.$
(S64)

###### Proof.

Consider the function $f_{T,\sigma^{2}}$ as previously defined in Equation
S25. We will show that the matrix $\Sigma\succcurlyeq 0$,
$\operatorname{tr}(\Sigma)=1$, maximizing $f_{T,\sigma^{2}}(\Sigma)$ is
diagonal w.r.t. the same basis diagonalizing $A$. Along the lines of the proof
of Proposition 2, we first note that $f_{T,\sigma^{2}}$ can be equivalently
rewritten as

$\displaystyle f_{T,\sigma^{2}}(\Sigma)=\frac{1}{2\ln
2}\ln\det\left(I-\sigma^{2}KX^{-1}\right)-\frac{T}{\ln
2}\operatorname{tr}(A),$ (S65)

where $X:=\mathcal{W}+\sigma^{2}e^{-AT}\mathcal{O}^{-1}e^{-A^{\top}T}$ and
$K:=e^{-AT}\mathcal{O}^{-1}e^{-A^{\top}T}-\mathcal{O}^{-1}$. Next, if $A$ is
stable and normal, it can be unitarily diagonalized in the form
$A=-U^{\dagger}\Lambda U$, where $U$ is a unitary matrix and $\Lambda$ is
diagonal with diagonal entries $\\{\lambda_{i}\\}_{i=1}^{n}$ having positive
real part. Since $C=I$, we can rewrite $\mathcal{O}$ as

$\displaystyle\mathcal{O}=U^{\dagger}\left[\frac{1}{2}\mathrm{Re}(\Lambda)^{-1}\left(I-e^{-2\mathrm{Re}(\Lambda)T}\right)\right]U,$
(S66)

where $\mathrm{Re}(\cdot)$ denotes element-wise real part when applied to
matrices, so that Equation S65 can be rewritten as

$\displaystyle f_{T,\sigma^{2}}(\Sigma)=\frac{1}{2\ln
2}\ln\det\left(I-\sigma^{2}\overline{K}^{1/2}\overline{X}^{-1}\overline{K}^{1/2}\right)-\frac{T}{\ln
2}\operatorname{tr}(A),$ (S67)

where
$\overline{X}:=U\mathcal{W}U^{\dagger}+\frac{\sigma^{2}}{2}\mathrm{Re}(\Lambda)\left(e^{2\mathrm{Re}(\Lambda)T}-I\right)^{-1}$
and
$\overline{K}:=\frac{1}{2}\mathrm{Re}(\Lambda)e^{2\mathrm{Re}(\Lambda)T}\succ
0$. Now assume, by contradiction, that the optimal $\Sigma^{\star}$,
$\operatorname{tr}(\Sigma^{\star})=1$, maximizing $f_{T,\sigma^{2}}(\Sigma)$
yields a matrix $\bar{\Sigma}^{\star}:=U\Sigma^{\star}U^{\dagger}$ which is
not diagonal. This implies that
$Z^{\star}:=\overline{K}^{1/2}\overline{X}^{-1}\overline{K}^{1/2}$ is not
diagonal, since

  1. (i)

$U\mathcal{W}U^{\dagger}=\sum_{k=0}^{\infty}e^{-\Lambda
kT}\bar{\Sigma}e^{-\Lambda^{\dagger}kT}$ is not diagonal,

  2. (ii)

$\frac{\sigma^{2}}{2}\mathrm{Re}(\Lambda)\left(e^{2\mathrm{Re}(\Lambda)T}-I\right)^{-1}$
and $\overline{K}$ are diagonal matrices, and

  3. (iii)

the inverse of a non-singular, non-diagonal matrix cannot be diagonal.

Let $\bar{\Sigma}_{d}:=\operatorname{diag}(\bar{\Sigma}^{\star})$ and consider
the corresponding diagonal matrix
$Z_{d}:=K^{1/2}\overline{X}_{d}^{-1}K^{1/2}$, where

$\displaystyle\overline{X}_{d}:=U\mathcal{W}_{d}U^{\dagger}+\frac{\sigma^{2}}{2}\mathrm{Re}(\Lambda)\left(e^{2\mathrm{Re}(\Lambda)T}-I\right)^{-1},$
(S68)

and $\mathcal{W}_{d}:=\sum_{k=0}^{\infty}e^{-\Lambda
kT}\bar{\Sigma}_{d}e^{-\Lambda^{\dagger}kT}$. Since for every positive
definite matrix $P\succ 0$ it holds
$\operatorname{diag}(P^{-1})\succcurlyeq(\operatorname{diag}\,P)^{-1}$ (Lemma
1), we have that

$\displaystyle\operatorname{diag}(Z^{\star})=\overline{K}^{1/2}\operatorname{diag}(\overline{X}^{-1})\overline{K}^{1/2}\succcurlyeq\overline{K}^{1/2}\bar{X_{d}}^{-1}\overline{K}^{1/2}=Z_{d}.$
(S69)

Eventually, we argue that

$\displaystyle\det(I-Z^{\star})$
$\displaystyle<\det(I-\operatorname{diag}(Z^{\star}))\overset{\lx@cref{creftype~refnum}{eq:proof-
normal-2}}{\leq}\det(I-Z_{d}),$ (S70)

where the first inequality follows from the fact that $I-Z^{\star}\succ 0$ and
from Hadamard’s inequality $\det P\leq\det\operatorname{diag}(P)$, for a
positive definite $P\succ 0$ (with equality attained if and only if $P$ is
diagonal, cf. (?, p. 505)). The inequality in Equation S70 contradicts the
optimality of $\Sigma^{\star}$ and therefore the matrix
$U\Sigma^{\star}U^{\dagger}$ must be diagonal. In view of this fact, the
desired expression in Equation S63 follows by direct computation. ∎

From the above result we have the following interesting corollary.

######  Corollary 1 (Optimal power allocation for normal networks).

If $B=C=I$ and $A$ is normal, then $\mathcal{R}_{\max}:=\max_{T\geq
0}\mathcal{R}_{T}$ is achieved for $T\to 0$ and the optimal power allocation
is

$\displaystyle P_{i}=\frac{\mathrm{Re}\,\lambda_{i}}{\operatorname{tr}A}P,$
(S71)

which yields

$\displaystyle\mathcal{R}_{\max}=\frac{1}{\ln
2}\frac{P\operatorname{tr}A}{2\sigma^{2}\operatorname{tr}A-P}.$ (S72)

###### Proof.

Since $\mathcal{R}_{T}$ is the sum of $n$ terms of the form in Equation S64
and each of these terms is a monotonically decreasing function of $T$, it
follows that the maximum of $\mathcal{R}_{T}$ is achieved for $T\to 0$. For
$T\to 0$, the expression of $\mathcal{R}_{T}$ becomes

$\displaystyle\mathcal{R}_{T}=\frac{1}{\ln
2}\max_{\begin{subarray}{c}\\{P_{i}\\}_{i=1}^{n},P_{i}\geq 0\\\ \text{\ s.t.\
}\sum_{i=1}^{n}P_{i}=P\end{subarray}}\sum_{i=1}^{n}\frac{\frac{P_{i}}{\sigma^{2}}\mathrm{Re}\,\lambda_{i}}{2\mathrm{Re}\,\lambda_{i}-\frac{P_{i}}{\sigma^{2}}}.$
(S73)

Consider the Lagrangian of the above constrained optimization problem

$\displaystyle\mathcal{L}(P_{1},\dots,P_{n},\mu)=\sum_{i=1}^{n}\frac{\frac{P_{i}}{\sigma^{2}}\mathrm{Re}\,\lambda_{i}}{2\mathrm{Re}\,\lambda_{i}-\frac{P_{i}}{\sigma^{2}}}+\mu\left(P-\sum_{i=1}^{n}P_{i}\right),$
(S74)

where $\mu\in\mathbb{R}$ is the Lagrangian multiplier. By equating
$\partial\mathcal{L}/\partial P_{i}$ to zero, we have

$\displaystyle\frac{\partial\mathcal{L}}{\partial
P_{i}}=\frac{2(\mathrm{Re}\,\lambda_{i})^{2}}{\left(-2\mathrm{Re}\,\lambda_{i}+\frac{P_{i}}{\sigma^{2}}\right)^{2}}-\mu=0\Rightarrow\frac{P_{i}}{\sigma^{2}}=\left(2\pm\sqrt{\frac{2}{\mu}}\right)\mathrm{Re}\,\lambda_{i},\quad
i=1,2,\dots,n.$ (S75)

In view of the latter equation,

$\displaystyle\frac{P}{\sigma^{2}}=\sum_{i=1}^{n}\frac{P_{i}}{\sigma^{2}}=\left(2\pm\sqrt{\frac{2}{\mu}}\right)\sum_{i=1}^{n}\mathrm{Re}\,\lambda_{i}=\left(2\pm\sqrt{\frac{2}{\mu}}\right)\operatorname{tr}A\Rightarrow\frac{P_{i}}{\sigma^{2}}=\frac{P}{\operatorname{tr}A}\mathrm{Re}\,\lambda_{i}.$
(S76)

Eventually, by substituting the above optimal signal-to-noise ratios
$P_{i}/\sigma^{2}$ into Equation S73, we obtain

$\displaystyle\mathcal{R}_{\max}=\frac{1}{\ln
2}\frac{P\operatorname{tr}A}{2\sigma^{2}\operatorname{tr}A-P}.$ (S77)

which ends the proof. ∎

It is worth pointing out that, from Proposition 5, Equation S63 provides an
upper bound to the achievable rate of any normal network for _any_ choice of
input and output node subsets. Furthermore, the expression of
$\mathcal{R}_{\max}$ in Equation S72 corresponds to the maximum information
rate that can be attained by a network described by a normal matrix $A$ for a
fixed noise level.

##  6 Measures of matrix non-normality and network indicators of non-normality

Mathematically speaking, matrix non-normality is not easy to measure and there
does not exist a unique scalar parameter that quantifies it. However, several
scalar estimates of matrix non-normality have been proposed and studied in the
literature, see (?), or Chapter 48 of (?) for a complete survey. There are two
general approaches for quantifying the “degree” of non-normality of a matrix
$A\in\mathbb{R}^{n\times n}$. The first and classic approach is to measure
non-normality in terms of departure from some algebraic properties
characterizing the set of normal matrices. In particular, metrics that fall
into this category are zero when evaluated at normal matrices. Examples
include:

  * •

the distance from commutativity, $c(A)=\|AA^{\top}-A^{\top}A\|_{F}$, where
$\|\cdot\|_{F}$ is the Frobenius norm;

  * •

the Henrici’s departure from normality,
$h(A)=(\|A\|_{F}^{2}-\sum_{z\in\lambda(A)}|z|^{2})^{1/2}$, where
$\lambda(\cdot)$ denotes the set of eigenvalues (or spectrum) of a matrix.

Alternatively, one can consider the linear dynamical system governed by $A$,
and quantify non-normality in terms of the ability of this system to
transiently amplify its trajectories. This ability is, in turn, related to the
sensitivity of the spectrum of $A$ to perturbations of the entries of $A$ (?).
Some standard measures of non-normality that carry such a “dynamical”
interpretation are:

  * •

the numerical abscissa, $\omega(A)=\max_{z\in\lambda((A+A^{\top})/2)}\ z$;

  * •

the condition number of the eigenvector matrix of $A$,
$\kappa(A)=\|V\|\|V^{-1}\|$, where the columns of $V$ are the eigenvectors of
$A$.111 Here, we assume that $A$ is diagonalizable. Note that, if $A$ is
normal, then $\kappa(A)=1$.

In the network considered in our paper, the above-listed non-normality metrics
correlate with some scalar network parameters. These parameters can thus be
thought of as knobs regulating the “degree” of non-normality of the network.
Specifically, for the chain network in Equation (9) of the main text, as
$\alpha$ (directionality strength) grows, then all of the above-listed
measures of non-normality increase as well (Supplementary Figure S1, left
plot). For $\alpha\neq 1$, $h(A)$, $\kappa(A)$, and $\omega(A)$ are positively
correlated with the chain length $\ell$, whereas $c(A)$ is independent of
$\ell$ (Supplementary Figure S1, right plot). A similar correlation behavior
is found when considering the more general layered topologies described in
Supplementary Note 6 (not shown). Finally, for heterogeneous topologies
generated via Equation (11) of the main text, the parameter $\sigma_{S}$ (st.
dev. of the entries of the skew-symmetric matrix $S$) and the network
dimension $n$ are highly correlated with the non-normality metrics $h(A)$ and
$\omega(A)$, whereas they do not exhibit a clear correlation w.r.t. $c(A)$ and
$\kappa(A)$ (Supplementary Figure S2).

Supplementary Figure S1: Non-normality metrics and parameters of chain
network. Correlation between standard non-normality metrics and parameters
$\alpha$ and $\ell$ of the chain network described in Equation (9) of the main
text with $\gamma=-3$ and $\beta=1$. For better visualization, $\kappa(A)$ is
plotted in logarithmic scale. Left plot: $\ell=n=8$. Right plot: $\ell=n$,
$\alpha=2$. Supplementary Figure S2: Non-normality metrics and parameters of
heterogeneous network. Correlation between standard non-normality metrics and
parameter $\sigma_{S}$ and dimension $n$ of heterogenous topologies. The
curves are the average over $500$ realizations of the random model in Equation
(11) of the main text with scale parameter $\omega^{-2}=\nu-n-1$ and
$\nu=24+n$ degrees of freedom. Left plot: $n=10$. Right plot: $\sigma_{S}=2$.

If matrix $A$ represents the adjacency matrix of a network, then it can be
shown that non-normality is related to (i) absence of cycles in the network,
(ii) low reciprocity of directed edges, and (iii) presence of hierarchical
organization (see (?) for further details). With reference to our examples of
chain and layered topologies, these networks are clearly acyclic, with
reciprocity inversely proportional to $\alpha$, and number of “hierarchical
levels” equal to $\ell$.

Finally, we mention that, although for general networks the presence of long
directed paths does not necessarily imply (strong) non-normality222 An example
is a directed ring topology, which is always normal regardless of the
directionality strength., if the network is stable (a standing assumption in
our paper) the connection between strong non-normality (here interpreted in a
dynamical sense) and presence of strongly directional network paths can be
made more precise. We next provide a simple example of this fact by
illustrating what happens to a directed chain in which we add one edge to form
a directed ring, while we refer to (?) for a more rigorous characterization of
the aforementioned connection for general networks with non-negative weights
(self-loops excluded). In the example, we consider as non-normality measure
the numerical abscissa.

Consider the directed chain described by the following adjacency matrix

$\displaystyle A=\begin{bmatrix}\gamma&0&0&&\\\ \alpha&\gamma&0&\ddots&\\\
&\ddots&\ddots&\ddots&0\\\ &&\ddots&\gamma&0\\\
&&&\alpha&\gamma\end{bmatrix}\in\mathbb{R}^{n\times n},$ (S78)

with $\gamma\in\mathbb{R}$ and $\alpha>0$. It can be shown that the numerical
abscissa is

$\omega(A)=\gamma+\alpha\cos\left(\frac{\pi}{n+1}\right)$

which, for large $n$, is approximately equal to

$\omega(A)\approx\gamma+\alpha.$

The system described by $A$ exhibits transient amplification if and only if
$\omega(A)>0$ (?). If $A$ is stable, then $\gamma<0$ and the previous
condition implies that $\alpha$ should be sufficiently large (strong
directionality) for the network to feature a high “degree” of non-normality.
If we add an edge so that the directed chain becomes a directed ring, matrix
$A$ becomes

$\displaystyle A^{\prime}=\begin{bmatrix}\gamma&0&0&&\alpha\\\
\alpha&\gamma&0&\ddots&\\\ &\ddots&\ddots&\ddots&0\\\ &&\ddots&\gamma&0\\\
&&&\alpha&\gamma\end{bmatrix},$ (S79)

which is indeed a normal matrix with the same trace of $A$. However, when
$\alpha+\gamma>0$ the largest eigenvalue of $A^{\prime}$ (which equals its
numerical abscissa) is unstable. Thus in the case of strong directionality,
the matrix $A^{\prime}$ becomes unstable, so that the stability assumption is
violated.

##  7 Information rate of a class of non-normal networks

Let $S\in\mathbb{R}^{n\times n}$ be the adjacency matrix of a weighted graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ and $\mathcal{E}$
denote the set of nodes and edges of $\mathcal{G}$, respectively, and consider
the following matrix

$\displaystyle A:=DSD^{-1},$ (S80)

where $D:=\operatorname{diag}(d_{1},d_{2},\dots,d_{n})$, $d_{i}>0$,
$i=1,2,\dots,n$. Note that the graph with adjacency matrix $A$ has the same
connectivity of $\mathcal{G}$ but, in general, different weights.
Additionally, $A$ has the same eigenvalues of $S$, but, typically, a different
“degree” of non-normality. The following result characterizes the information
rate of the network with adjacency matrix $A$ as in Equation S80.

######  Theorem 4 (information rate of networks with adjacency matrix
$A=DSD^{-1}$).

Let $S\in\mathbb{R}^{n\times n}$ be the stable adjacency matrix of a weighted
graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, and consider $A:=DSD^{-1}$,
where $D_{1}:=\operatorname{diag}(d_{1},d_{2},\dots,d_{n})$, $d_{i}>0$,
$i=1,2,\dots,n$, is a positive diagonal matrix. Let
$B=[e_{k_{1}},\dots,e_{k_{m}}]$ and $C=[e_{t_{1}},\dots,e_{t_{p}}]^{\top}$ be
the input matrix and the output matrix respectively and let
$d_{\min}:=\min\\{d_{k_{1}},\dots,d_{k_{m}}\\}$ and
$d_{\max}=\max\\{d_{t_{1}},\dots,d_{t_{p}}\\}$. Then,

$\displaystyle\mathcal{R}_{T}(A,\sigma^{2})\geq\mathcal{R}_{T}\bigg{(}S,\bigg{(}\frac{d_{\min}}{d_{\max}}\sigma\bigg{)}^{2}\bigg{)},$
(S81)

where we made explicit the dependence of $\mathcal{R}_{T}$ on the network
adjacency matrix and noise variance.

###### Proof.

Let $r:=\arg\min\\{d_{k_{1}},\dots,d_{k_{m}}\\}$ and
$q:=\arg\max\\{d_{t_{1}},\dots,d_{t_{p}}\\}$. Consider first the special case
where $C=e_{q}$ and $B=e_{r}$. In view of the definition of $A$, we have
$De_{q}^{\top}e_{q}D=d_{\max}^{2}e_{q}^{\top}e_{q}$. This in turn implies that

$\displaystyle\mathcal{O}=\int_{0}^{T}e^{A^{\top}t}C^{\top}Ce^{At}\mathrm{d}t=\int_{0}^{T}D^{-1}e^{S^{\top}t}De_{q}^{\top}e_{q}De^{St}D^{-1}\mathrm{d}t=d_{\max}^{2}D^{-1}\underbrace{\int_{0}^{T}e^{S^{\top}t}e_{q}^{\top}e_{q}e^{St}\mathrm{d}t}_{=:\widehat{\mathcal{O}}}D^{-1}.$
(S82)

Similarly, we have
$D^{-1}e_{r}e_{r}^{\top}D^{-1}=\frac{1}{d_{\min}^{2}}e_{r}e_{r}^{\top}$, so
that we can rewrite $\mathcal{W}$ as

$\displaystyle\mathcal{W}=\sum_{k=0}^{\infty}e^{AkT}B\Sigma
B^{\top}e^{A^{\top}kT}=\sum_{k=0}^{\infty}De^{SkT}D^{-1}e_{r}e_{r}^{\top}D^{-1}e^{S^{\top}kT}D=\frac{1}{d_{\min}^{2}}D\underbrace{\sum_{k=0}^{\infty}e^{SkT}e_{r}e_{r}^{\top}e^{S^{\top}kT}}_{=:\widehat{\mathcal{W}}}D.$
(S83)

By substituting Equations S82 and S83 in the expression of $\mathcal{R}_{T}$,
we have

$\displaystyle\mathcal{R}_{T}(A,\sigma^{2})$
$\displaystyle=\frac{1}{2T}\,\max_{\begin{subarray}{c}\Sigma\succcurlyeq
0,\,\operatorname{tr}\Sigma=P\end{subarray}}\log_{2}\frac{\det(\sigma^{2}I+\mathcal{O}\mathcal{W})}{\det(\sigma^{2}I+\mathcal{O}(\mathcal{W}-B\Sigma
B^{\top}))}=\frac{1}{2T}\,\max_{\begin{subarray}{c}\Sigma\succcurlyeq
0,\,\operatorname{tr}\Sigma=P\end{subarray}}\log_{2}\frac{\det(\sigma^{2}I+\mathcal{O}\mathcal{W})}{\det(\sigma^{2}I+\mathcal{O}e^{AT}\mathcal{W}e^{A^{\top}T})}$
$\displaystyle=\frac{1}{2T}\,\max_{\begin{subarray}{c}\Sigma\succcurlyeq
0,\,\operatorname{tr}\Sigma=P\end{subarray}}\log_{2}\frac{\det(\sigma^{2}I+\left(\frac{d_{\max}}{d_{\min}}\right)^{2}D^{-1}\widehat{\mathcal{O}}D^{-1}D\widehat{\mathcal{W}}D)}{\det(\sigma^{2}I+\left(\frac{d_{\max}}{d_{\min}}\right)^{2}D^{-1}\widehat{\mathcal{O}}D^{-1}De^{ST}D^{-1}D\widehat{\mathcal{W}}DD^{-1}e^{S^{\top}T}D)}$
$\displaystyle=\frac{1}{2T}\,\max_{\begin{subarray}{c}\Sigma\succcurlyeq
0,\,\operatorname{tr}\Sigma=P\end{subarray}}\log_{2}\frac{\det\bigg{(}\left(\frac{d_{\min}}{d_{\max}}\sigma\right)^{2}I+\widehat{\mathcal{O}}\widehat{\mathcal{W}}\bigg{)}}{\det\bigg{(}\left(\frac{d_{\min}}{d_{\max}}\sigma\right)^{2}I+\widehat{\mathcal{O}}e^{ST}\widehat{\mathcal{W}}e^{S^{\top}T}\bigg{)}}=\mathcal{R}_{T}\bigg{(}S,\bigg{(}\frac{d_{\min}}{d_{\max}}\sigma\bigg{)}^{2}\bigg{)}.$
(S84)

Finally, for the general case where $B=[e_{k_{1}},\dots,e_{k_{m}}]$ is such
that $r\in\\{k_{1},\dots,k_{m}\\}$, and $C=[e_{t_{1}},\dots,e_{t_{p}}]^{\top}$
is such that $q\in\\{t_{1},\dots,t_{p}\\}$, the inequality in Equation S85
directly follows from Proposition 5. ∎

Theorem 4 in particular implies that, as the heterogeneity of the elements of
$D$ grows unbounded, we recover the same value of information rate of the
_noiseless_ case.

######  Corollary 2 (Limiting behavior of information rate for strongly non-
normal networks).

Let $B$, $C$ and $A$ be as in Theorem 4, and assume that the pair $(S,e_{q})$,
with $q:=\arg\max\\{d_{t_{1}},\dots,d_{t_{p}}\\}$, is observable. Then,

$\displaystyle\lim_{\frac{d_{\min}}{d_{\max}}\to 0}\mathcal{R}_{T}$
$\displaystyle=-\frac{1}{\ln 2}\operatorname{tr}(A).\vskip 3.0pt plus 1.0pt
minus 1.0pt$ (S85)

###### Proof.

From Theorem 4, decreasing the ratio ${d_{\min}}/{d_{\max}}$ is equivalent to
decreasing the noise variance $\sigma^{2}$ for a network with adjacency matrix
$S$. Then, Equation S85 directly follows from Theorem 1, noting that
$\operatorname{tr}(A)=\operatorname{tr}(S)$. ∎

From the above analysis, it follows that increasing the non-normality of the
network by diminishing the ratio ${d_{\min}}/{d_{\max}}$ is always beneficial
to the information rate $\mathcal{R}_{T}$, in that it reduces the detrimental
effect of output noise. Indeed, for the class of networks in Equation S80, the
ratio $d_{\min}/d_{\max}$, can be thought of regulating the “degree” of non-
normality of the network. To clarify this claim, assume that $S_{ij}\neq 0$
and consider two diagonal entries $d_{i},d_{j}$ with $d_{i}\neq d_{j}$, in
this case the $(i,j)$-th entry and $(j,i)$-th entry of $A$ take the form
$\smash{A_{ij}=\frac{d_{i}}{d_{j}}S_{ij}}$ and
$\smash{A_{ji}=\frac{d_{j}}{d_{i}}S_{ij}}$, respectively. As the ratio
$d_{i}/d_{j}$ tends either to zero or to infinity, matrix $A$ departs from
symmetry because the entries $A_{ij}$ and $A_{ji}$ becomes very heterogenous
in magnitude. As a concrete example of this, consider the chain network
described in our paper (Equation 9 of the main text). The adjacency matrix of
this network (here reported for convenience) reads as

$\displaystyle A=\begin{bmatrix}\gamma&\beta/\alpha&0&\cdots&0\\\
\alpha\beta&\gamma&\beta/\alpha&\ddots&\vdots\\\
0&\alpha\beta&\ddots&\ddots&0\\\ \vdots&\ddots&\ddots&\ddots&\beta/\alpha\\\
0&\cdots&0&\alpha\beta&\gamma\\\ \end{bmatrix}\in\mathbb{R}^{n\times n},$
(S86)

with $\beta,\alpha>0$ and $\gamma<-2\beta$. As described in our paper and in
Supplementary Note 6, the parameter $\alpha$ (directionality strength)
regulates the “degree” of non-normality of the network. Notice that the matrix
in Equation S86 can be rewritten as in Equation S80 with
$D=\mathrm{diag}(1,\alpha,\dots,\alpha^{n-1})$ and

$\displaystyle S=\begin{bmatrix}\gamma&\beta&0&\cdots&0\\\
\beta&\gamma&\beta&\ddots&\vdots\\\ 0&\beta&\ddots&\ddots&0\\\
\vdots&\ddots&\ddots&\ddots&\beta\\\ 0&\cdots&0&\beta&\gamma\\\
\end{bmatrix}.$ (S87)

Assume that $\alpha>1$. Then, 2 yields that, as
$d_{\min}/d_{\max}=1/\alpha^{n-1}$ tends to zero, the information rate
$\mathcal{R}_{T}$ tends to $-\frac{1}{\ln 2}\text{tr}(A)=-\frac{\gamma n}{\ln
2}$, which corresponds to the information rate of the network in the noiseless
case. In other words, as $\alpha$ as grows unbounded (large directionality
strength, and, therefore, strong non-normality), the information rate
approaches the one achieved in the noiseless case.

Finally, we stress that a small value of ${d_{\min}}/{d_{\max}}$ would
typically correspond to a large magnitude of some entries of $A$, which is not
desirable in many scenarios. However, we also observe that, in the above
example of the chain network, $d_{\min}/d_{\max}$ depends on the chain length
$n$, and for large $n$ the ratio $d_{\min}/d_{\max}$ can be made small
regardless of the value of $\alpha$ (provided that $\alpha>1$). Inspired by
this example, we therefore propose an alternative procedure that leads to a
decrease of the ratio ${d_{\min}}/{d_{\max}}$, while keeping the entries $A$
bounded in magnitude. We term this procedure “directed stratification” as it
partitions the network in different “directed” layers, according to the length
of the paths from a given subset of nodes to all the other network’s nodes.

Supplementary Figure S3: Construction of “layered” non-normal networks.
Example of construction of a “layered” non-normal network with $n=12$ nodes.
(A) A subset $\mathcal{S}_{0}$ of nodes in a weights graph $\mathcal{G}$ with
homogeneous weights is selected. (B) Each node of the network is assigned to a
different layers according to its distance from $\mathcal{S}_{0}$. (C) The
parameter $\alpha>0$ is used to generate a directional structure between
adjacent layers. The thickness of each edge in the network is proportional to
their weight.

To this end, given any two nodes $k,t\in\mathcal{V}$, we denote by $d(k,t)$
the length of a shortest path from the node $k$ to the node $t$. Given
$\mathcal{K}\subseteq\mathcal{V}$ and $t\in\mathcal{V}$, we denote by
$d(\mathcal{K},t)$ the minimum length of a shortest path from the nodes in
$\mathcal{K}$ to the node $t$, namely

$\displaystyle d(\mathcal{K},t)=\min\left\\{\,d(k,t)\ :\
k\in\mathcal{K}\,\right\\}.$ (S88)

Further, let $s_{\min}$ and $s_{\max}$ denote the smallest and largest (in
magnitude) non-zero entries of $S$, respectively, and consider the matrix
$A:=DSD^{-1}$ as in Equation S80. We select any subset of nodes in the
network, say $\mathcal{S}_{0}$ , and define the following sets

$\displaystyle\mathcal{S}_{\ell}=\left\\{v\in\mathcal{V}\,:\,d(\mathcal{K},v)=\ell\right\\},\
\ell=1,2,\dots,\ell_{\max},$ (S89)

where $\ell_{\max}$ is the maximum length of a shortest path from subset
$\mathcal{S}_{0}$ to any other node in $\mathcal{V}$. Next, we set
$d_{i}=\alpha^{\ell}$, $\alpha>0$, for each node $i\in\mathcal{S}_{\ell}$.
Then, for every edge $(i,j)\in\mathcal{E}$, we distinguish three cases:

  1. (i)

if $i,j\in\mathcal{S}_{\ell}$, then
$A_{ij}=\frac{d_{j}}{d_{i}}S_{ij}=\frac{\alpha^{\ell}}{\alpha^{\ell}}S_{ij}=S_{ij}$;

  2. (ii)

if $i\in\mathcal{S}_{\ell-1}$ and $j\in\mathcal{S}_{\ell}$, then
$A_{ij}=\frac{\alpha^{\ell-1}}{\alpha^{\ell}}S_{ij}=\frac{1}{\alpha}S_{ij}$;

  3. (iii)

if $i\in\mathcal{S}_{\ell}$ and $j\in\mathcal{S}_{\ell-1}$, then
$A_{ij}=\frac{\alpha^{\ell}}{\alpha^{\ell-1}}S_{ij}=\alpha S_{ij}$.

From the above equations, we observe the magnitude of the entries of $A$ in
Equation S80 is bounded in the interval $[s_{\min}/\alpha,\alpha s_{\max}]$.
In graphical terms, the above-described procedure corresponds to a “directed
stratification” of $\mathcal{G}$, as illustrated in Supplementary Figure S3.

Finally, if we consider a matrix $A$ generated as above, an input matrix
$B=[e_{k_{1}},\dots,e_{k_{m}}]$, such that there exists
$r\in\\{k_{1},\dots,k_{m}\\}$ with $r\in\mathcal{S}_{0}$, and an output matrix
$C=[e_{t_{1}},\dots,e_{t_{p}}]^{\top}$, such that there exists
$q\in\\{k_{1},\dots,k_{m}\\}$ with $q\in\mathcal{S}_{\ell_{\max}}$, in view of
Theorem 4,

$\displaystyle\mathcal{R}_{T}(A,\sigma^{2})\geq\mathcal{R}_{T}\left(S,\left(\alpha^{\ell_{\max}-1}\sigma\right)^{2}\right).$
(S90)

The latter equation shows that it is possible to reduce the effect of noise in
the rate either by increasing $\alpha$ or, for a fixed $\alpha>1$, by
increasing $\ell_{\max}$. In particular, via a proper tuning of these two
parameters, it is possible to increase the rate while keeping the entries of
$A$ bounded in magnitude in a desired interval. Remarkably, this offers a
viable way to enhance the communication performance of real-world networks.

##  8 Optimal communication architectures

Optimal communication networks can be computed by solving the following
optimization problem:333Here, we considered optimality w.r.t. the information
rate $\mathcal{R}_{T}$. Similar considerations and results apply when
considering the information capacity $\mathcal{C}_{T}$.

$\displaystyle\max_{A\in\mathcal{S}}\mathcal{R}_{T}(A),$ (S91)

where $\mathcal{S}$ denotes the set of real stable matrices, and we made
explicit the dependence of $\mathcal{R}_{T}$ on $A$. This problem is non-
convex and computationally expensive. In fact, it requires solving two
(typically non-convex) optimization problems: one for computing the
information rate, and one for finding the optimal $A$. However this problem
can be made more tractable by introducing some mild assumptions and using the
properties of the information rate, as we describe next.

In what follows, we restrict the attention to the subset
$\mathcal{S}_{r}\subset\mathcal{S}$ consisting of stable matrices with real
eigenvalues and we consider $B=C=I$. For $C=I$, it is not difficult to see
that $\mathcal{R}_{T}$ is invariant under unitary similarity transformation of
$A$. In view of this fact, we can consider the Schur form of the matrices in
$\mathcal{S}_{r}$ and reduce the original problem to an optimization problem
over the set of lower triangular matrices with negative diagonal entries. We
denote the latter set with $\mathcal{S}_{\Delta,r}$. The new “simplified”
optimization problem reads as

$\displaystyle\max_{A\in\mathcal{S}_{\Delta,r}}\mathcal{R}_{T}(A)-\varepsilon\|A\|_{F},$
(S92)

where we added a regularization term $\varepsilon\|A\|_{F}$, $\varepsilon>0$,
to the objective function $\mathcal{R}_{T}(A)$ to bound the magnitude of the
entries of $A$. Recall that the computation of the information rate
$\mathcal{R}_{T}$ requires solving a constrained optimization problem over
input covariances $\Sigma$. Consequently, in order to numerically solve the
problem in Equation S92, we exploited a coordinate gradient ascent strategy
(?, Ch. 9) over unit-trace covariance matrices $\Sigma$, and connectivity
matrices $A\in\mathcal{S}_{\Delta,r}$. Numerical solutions of the optimization
problem in Equation S92 are shown in Supplementary Figure S4, for a network of
$10$ nodes, $\sigma^{2}=1$, and different values of $T>0$.

Supplementary Figure S4: Optimal networks and input covariances as a function
of the transmission window $T$. Optimal network architecture $A^{\star}$ and
input covariance $\Sigma^{\star}$ obtained by solving the optimization problem
in Equation S93 for $n=10$, $\sigma^{2}=1$, $\varepsilon=2.5\times 10^{-3}$.
The solution of the optimization problem has been computed via unconstrained
coordinate gradient ascent over unit-trace positive definite $\Sigma$ and
lower triangular $A\in\mathcal{S}_{\Delta,r}$. The simulations have been
carried out in Python using Autograd (?).

From these plots, we observe that:

  1. 1.

for small values of $T$, the optimal structure $A^{\star}$ is diagonal and,
therefore, normal. In this case, the corresponding optimal input covariance
$\Sigma^{\star}$ is also diagonal.

  2. 2.

as $T$ increases, the strictly lower triangular entries of $A^{\star}$ becomes
different from zero, yielding a non-normal optimal network structure. In
particular, for $T$ large enough, the entries of the subdiagonal of
$A^{\star}$ are greater than the other lower triangular entries, resulting in
an optimal structure similar to a purely feedforward chain. In this case, the
non-zero entries of the corresponding optimal input covariances are localized
around the upper diagonal entries (source nodes).

To investigate the effect of noise on the optimal matrix, we further optimized
the cost function in Equation S92 over the transmission window $T\geq 0$.
Namely, we considered the following regularized optimization problem:

$\displaystyle\max_{A\in\mathcal{S}_{\Delta,r},T\geq
0}\mathcal{R}_{T}(A)-\varepsilon\|A\|_{F},$ (S93)

As before, we exploited a coordinate gradient ascent method to solve the
latter problem. In this case, gradient ascent need to be jointly performed
w.r.t. unit-trace covariances $\Sigma$, lower triangular connectivity matrices
$A\in\mathcal{S}_{\Delta,r}$, and non-negative transmission windows $T\geq 0$.
Supplementary Figure S5 shows the numerical results obtained via this
optimization strategy, for different values of $\sigma^{2}$. We notice that,
for small values of $\sigma^{2}$, the optimal transmission window equals zero,
and the optimal connectivity matrix and covariance are both diagonal. For
larger values of $\sigma^{2}$ the optimal transmission window becomes strictly
positive, and grows as $\sigma^{2}$ increases. Further, the resulting
$A^{\star}$ is non-normal and resembles a feedforward chain, while
$\Sigma^{\star}$ has non-zero diagonal entries concentrated around the upper
diagonal entries.

Supplementary Figure S5: Optimal networks and input covariances as a function
of the noise covariance $\sigma^{2}$. Optimal network architecture
$A^{\star}$, input covariance $\Sigma^{\star}$, and transmission window
$T^{\star}$ obtained by solving the problem in Equation S93 for $n=10$ nodes,
$\varepsilon=2.5\times 10^{-3}$, and different values of $\sigma^{2}$. The
solution of the problem in Equation S93 has been computed via unconstrained
coordinate gradient ascent over unit-trace positive definite $\Sigma$’s, lower
triangular $A\in\mathcal{S}_{\Delta,r}$, and non-negative $T$.