# Beyond Diagonal Reconfigurable Intelligent Surfaces Utilizing Graph Theory:
Modeling, Architecture Design, and Optimization

Matteo Nerini, , Shanpu Shen, ,
Hongyu Li, , Bruno Clerckx Corresponding author: Shanpu Shen.M. Nerini and H.
Li are with the Department of Electrical and Electronic Engineering, Imperial
College London, London SW7 2AZ, U.K. (e-mail: {m.nerini20,
c.li21}@imperial.ac.uk).S. Shen is with the Department of Electronic and
Computer Engineering, The Hong Kong University of Science and Technology,
Clear Water Bay, Kowloon, Hong Kong (e-mail: sshenaa@connect.ust.hk).B.
Clerckx is with the Department of Electrical and Electronic Engineering,
Imperial College London, London SW7 2AZ, U.K., and with Silicon Austria Labs
(SAL), Graz A-8010, Austria (e-mail: b.clerckx@imperial.ac.uk).

###### Abstract

Recently, beyond diagonal reconfigurable intelligent surface (BD-RIS) has been
proposed to generalize conventional RIS. BD-RIS has a scattering matrix that
is not restricted to being diagonal and thus brings a performance improvement
over conventional RIS. While different BD-RIS architectures have been
proposed, it still remains an open problem to develop a systematic approach to
design BD-RIS architectures achieving the optimal trade-off between
performance and circuit complexity. In this work, we propose novel modeling,
architecture design, and optimization for BD-RIS based on graph theory. This
graph theoretical modeling allows us to develop two new efficient BD-RIS
architectures, denoted as tree-connected and forest-connected RIS. Tree-
connected RIS, whose corresponding graph is a tree, is proven to be the least
complex BD-RIS architecture able to achieve the performance upper bound in
multiple-input single-output (MISO) systems. Besides, forest-connected RIS
allows us to strike a balance between performance and complexity, further
decreasing the complexity over tree-connected RIS. To optimize tree-connected
RIS, we derive a closed-form global optimal solution, while forest-connected
RIS is optimized through a low-complexity iterative algorithm. Numerical
results confirm that tree-connected (resp. forest-connected) RIS achieves the
same performance as fully-connected (resp. group-connected) RIS, while
reducing the complexity by up to 16.4 times.

###### Index Terms:

Beyond diagonal reconfigurable intelligent surface (BD-RIS), forest-connected,
graph theoretical modeling, tree-connected.

##  I Introduction

Reconfigurable intelligent surface (RIS) is expected to be a key technology in
6G to enhance the performance of wireless systems in an efficient and cost-
effective manner [1, 2, 3]. An RIS consists of a large number of
reconfigurable scattering elements, each with the capability to manipulate the
phase of an incident electromagnetic wave, so that the phase shifts of these
elements can be coordinated to direct the scattered electromagnetic signal
toward the intended receiver. Owing to the benefits of low power consumption
and cost-effective architecture, RIS has gained widespread attention.

In a conventional RIS architecture, each element is independently controlled
by a tunable impedance connected to ground [4]. Such architecture, referred to
as the single-connected RIS, results in a diagonal scattering matrix, which is
also commonly known as the phase shift matrix. Conventional RIS with diagonal
scattering matrix has been widely used to enhance different wireless systems,
such as single-cell [5, 6], [7] and multi-cell communications [8], orthogonal
frequency division multiplexing (OFDM) [9], non-orthogonal multiple access
(NOMA) [10], rate splitting multiple access (RSMA) [11], radio frequency (RF)
sensing systems [12], wireless power transfer (WPT) systems [13], and
simultaneous wireless information and power transfer (SWIPT) systems [14]. In
addition, research has been conducted to optimize RIS based on imperfect
channel state information (CSI) [15, 16], in multi-RIS scenarios [17, 18], and
with discrete phase shifts to account for practical hardware impairments [19,
20]. Furthermore, RIS prototypes have been realized in [21, 22].

Figure 1: RIS classification tree.

Recently, the conventional RIS architecture considered in [5]-[22] has been
generalized with the introduction of beyond diagonal RIS (BD-RIS). BD-RIS has
a scattering matrix that is not restricted to being diagonal [23], with
various architectures and modes available as depicted in the classification
tree in Fig. 1. Specifically, group-connected and fully-connected
architectures, whereby some or all RIS elements are connected with each other
through tunable impedance components, are proposed in [4], generalizing the
single-connected architecture to enhance the RIS performance. Subsequently,
group- and fully-connected RIS with discrete values are efficiently optimized
in [24], while the closed-form global optimal solutions for group- and fully-
connected RIS with continuous values are derived in [25]. In addition, the
simultaneously transmitting and reflecting RIS (STAR-RIS) or intelligent omni-
surface (IOS) is presented in [26, 27], which differs from conventional RIS as
signals impinging on this RIS can be both reflected and transmitted through
the RIS for a full space coverage. STAR-RIS is generalized in [28] which
unifies different BD-RIS modes (reflective/transmissive/hybrid) and different
BD-RIS architectures (single-/group-/fully-connected). To further enhance RIS
performance while maintaining a full-space coverage, multi-sector BD-RIS is
proposed in [29], where the elements are split into multiple sectors with each
covering a sector of space. Further, the synergy of multi-sector BD-RIS and
RSMA is proved to enlarge the coverage, improve the performance, and save on
antennas in multi-user systems [30]. Departing from existing works on BD-RIS
with fixed architectures [4, 23]-[30], dynamically group-connected RIS has
been proposed in [31], outperforming fixed group-connected RIS by dynamically
dividing the RIS elements into groups depending on the channel realization.
Besides, a BD-RIS with a non-diagonal phase shift matrix has been proposed in
[32], which is able to achieve a higher rate than conventional RIS.

Among all the BD-RISs [4, 23]-[32], the fully-connected architecture provides
the highest flexibility and best performance, which is however at the expense
of high circuit complexity since it has a large number of tunable impedance
components. Although the group-connected architecture can simplify the circuit
complexity, it still remains an open problem to develop a systematic approach
to design BD-RIS architecture achieving the optimal trade-off between
performance and circuit complexity, that is achieving the best performance
with the least complexity. To address this issue, in this work, we propose
novel modeling, architecture design, and optimization for BD-RIS by utilizing
graph theory. The contributions of this paper are summarized as follows.

First, we propose a novel modeling of BD-RIS architectures utilizing graph
theory. To the authors’ best knowledge, it is the first time that BD-RIS (or
any other RIS) architectures are modeled through graph theory. Specifically,
we model each BD-RIS architecture by a graph, whose vertices characterize the
RIS ports and whose edges characterize the tunable impedance components
connecting the RIS ports. This graph theoretical modeling lays down the
foundations for developing new efficient BD-RIS architectures.

Second, we derive a necessary and sufficient condition for a BD-RIS
architecture to achieve the performance upper bound in multiple-input single-
output (MISO) systems. Consequently, we characterize the least complex BD-RISs
achieving such an upper bound. The resulting least-complexity BD-RIS
architectures are referred to as tree-connected RIS since their corresponding
graph is a tree. In addition, two specific examples of tree-connected RIS are
proposed, namely tridiagonal RIS and arrowhead RIS. Tree-connected RIS
achieves the same performance in MISO systems as fully-connected RIS with a
circuit complexity significantly reduced by $16.4$ times, when $64$ RIS
elements are considered.

Third, we prove that there always exists one and only one global optimal
solution to optimize tree-connected RIS. To find this solution, we derive a
closed-form algorithm valid for any tree-connected architecture. With this
algorithm, tree-connected RIS achieves a performance improvement of $51.7\%$
over single-connected RIS.

Fourth, we propose forest-connected RIS as an additional BD-RIS family to
reach a trade-off between performance and circuit complexity. Forest-connected
RIS serves as a bridge between single- and tree-connected RIS. We propose a
low-complexity iterative algorithm to optimize forest-connected RIS. Numerical
results show that forest-connected RIS achieves the same performance as group-
connected RIS, while reducing the circuit complexity by $2.4$ times.

Organization: In Section II, we introduce the graph theoretical modeling of
BD-RIS. In Section III, we derive tree- and forest-connected RIS architectures
and provide two examples of tree-connected RIS. In Section IV we provide a
global optimal closed-form solution to optimize tree-connected RIS and an
iterative approach to optimize forest-connected RIS. In Section V, we evaluate
the performance of the proposed BD-RISs. Finally, Section VI concludes this
work.

Notation: Vectors and matrices are denoted with bold lower and bold upper
letters, respectively. Scalars are represented with letters not in bold font.
$\Re\left\\{a\right\\}$, $\Im\left\\{a\right\\}$, $\left|a\right|$,
$\arg\left(a\right)$, and $a^{*}$ refer to the real part, imaginary part,
modulus, phase, and the complex conjugate of a complex scalar $a$,
respectively. $\left[\mathrm{\mathbf{a}}\right]_{i}$ and
$\left\|\mathbf{a}\right\|$ refer to the $i$th element and $l_{2}$-norm of a
vector $\mathrm{\mathbf{a}}$, respectively. $\mathrm{\mathbf{A}}^{T}$,
$\mathrm{\mathbf{A}}^{H}$, $\left[\mathrm{\mathbf{A}}\right]_{i,j}$, and
$\|\mathbf{A}\|$ refer to the transpose, conjugate transpose,
$\left(i,j\right)$th element, and $l_{2}$-norm of a matrix $\mathbf{A}$,
respectively. $\mathbf{A\sim B}$ means that the matrices $\mathbf{A}$ and
$\mathbf{B}$ are equivalent. $\mathbb{R}$ and $\mathbb{C}$ denote real and
complex number set, respectively. $j=\sqrt{-1}$ denotes imaginary unit.
$\mathbf{0}$ and $\mathbf{I}$ denote an all-zero matrix and an identity
matrix, respectively. $\mathcal{CN}\left(\mathbf{0},\mathbf{I}\right)$ denotes
the distribution of a circularly symmetric complex Gaussian random vector with
mean vector $\mathbf{0}$ and covariance matrix $\mathbf{I}$ and $\sim$ stands
for “distributed as”. diag$\left(\mathbf{a}\right)$ refers to a diagonal
matrix with diagonal elements being the vector $\mathbf{a}$.
diag$\left(\mathrm{\mathbf{A}}_{1},\ldots,\mathrm{\mathbf{A}}_{N}\right)$
refers to a block diagonal matrix with blocks being
$\mathrm{\mathbf{A}}_{1},\ldots,\mathrm{\mathbf{A}}_{N}$.

##  II BD-RIS Modeling Utilizing Graph Theory

Consider a MISO system with an $M$-antenna transmitter and a single-antenna
receiver, which is aided by an $N$-element RIS. The $N$-element RIS can be
modeled as $N$ antennas connected to an $N$-port reconfigurable impedance
network that is characterized by the scattering matrix
$\boldsymbol{\Theta}\in\mathbb{C}^{N\times N}$ [4]. We assume the direct
channel between the transmitter and receiver is blocked and thus is negligible
compared to the indirect channel provided by RIS. Therefore, the overall
channel $\mathbf{h}\in\mathbb{C}^{1\times M}$ between the transmitter and
receiver can be written as

$\mathbf{h}=\mathbf{h}_{RI}\boldsymbol{\Theta}\mathbf{H}_{IT},$ (1)

where $\mathbf{h}_{RI}\in\mathbb{C}^{1\times N}$ and
$\mathbf{H}_{IT}\in\mathbb{C}^{N\times M}$ are the channel matrices from the
RIS to the receiver, and from the transmitter to the RIS, respectively. We
denote the transmit signal as $\mathbf{x}=\mathbf{w}s$, where
$\mathbf{w}\in\mathbb{C}^{M\times 1}$ is the precoder satisfying
$\left\|\mathbf{w}\right\|=1$ and $s\in\mathbb{C}$ is the transmit symbol with
power $P_{T}=\mathrm{E}\text{[$\left|s\right|^{2}$]}$. Hence, the received
signal is given by $y=\mathbf{h}\mathbf{x}+n$, where $n$ is the additive white
Gaussian noise (AWGN).

The $N$-port reconfigurable impedance network consists of tunable passive
impedance components. In addition to S-parameters (the scattering matrix), the
$N$-port reconfigurable impedance network can be also characterized by
Y-parameters [33], that is the admittance matrix denoted as
$\mathbf{Y}\in\mathbb{C}^{N\times N}$. According to microwave network theory
[33], the scattering matrix $\boldsymbol{\Theta}$ and admittance matrix
$\mathbf{Y}$ are related by

$\boldsymbol{\Theta}=\left(\mathbf{I}+Z_{0}\mathbf{Y}\right)^{-1}\left(\mathbf{I}-Z_{0}\mathbf{Y}\right),$
(2)

where $Z_{0}$ denotes the reference impedance used for computing the
scattering parameter, and usually set as $Z_{0}=50\>\Omega$. Furthermore, we
have $\mathbf{Y}=\mathbf{Y}^{T}$ and
$\boldsymbol{\Theta}=\boldsymbol{\Theta}^{T}$ because of the reciprocity of
the reconfigurable impedance network. To maximize the power scattered by the
RIS, $\mathbf{Y}$ should be purely susceptive and thus writes as
$\mathbf{Y}=j\mathbf{B}$, where $\mathbf{B}\in\mathbb{R}^{N\times N}$ denotes
the susceptance matrix of the $N$-port reconfigurable impedance network.
Hence, $\boldsymbol{\Theta}$ is given by

$\boldsymbol{\Theta}=\left(\mathbf{I}+jZ_{0}\mathbf{B}\right)^{-1}\left(\mathbf{I}-jZ_{0}\mathbf{B}\right).$
(3)

Depending on the circuit topology of the $N$-port reconfigurable impedance
network, the scattering matrix $\boldsymbol{\Theta}$ and admittance matrix
$\mathbf{Y}$ satisfy different constraints, which results in diagonal RIS and
beyond diagonal RIS as follows.

###  II-A Diagonal RIS

In diagonal RIS, each RIS port is not connected to the other ports and is
connected to ground through a tunable admittance [4]. Accordingly, the
admittance matrix $\mathbf{Y}$ and the scattering matrix $\boldsymbol{\Theta}$
are diagonal, written as

$\mathbf{Y}=\mathrm{diag}\left(Y_{1},Y_{2},\ldots,Y_{N}\right),$ (4)
$\mathbf{\boldsymbol{\Theta}}=\mathrm{diag}\left(e^{j\theta_{1}},e^{j\theta_{2}},\ldots,e^{j\theta_{N}}\right),$
(5)

where $Y_{n}$ and $\theta_{n}$ are respectively the tunable admittance and
phase shift for the $n$th RIS port for $n=1,\ldots,N$. Such circuit topology
is also referred to as single-connected RIS [4] and has been widely adopted
[5]-[22].

###  II-B Beyond Diagonal RIS

In BD-RIS, the RIS ports can also be connected to each other through
additional tunable admittance components. We denote the tunable admittance
connecting the $n$th port to the $m$th port as $Y_{n,m}$. According to [34],
given the admittance components $Y_{n}$ and $Y_{n,m}$, the $(n,m)$th entry of
the admittance matrix $\mathbf{Y}$ is given by

$\left[\mathbf{Y}\right]_{n,m}=\begin{cases}-Y_{n,m}&n\neq m\\\
Y_{n}+\sum_{k\neq n}Y_{n,k}&n=m\end{cases}.$ (6)

Thus, by selecting $Y_{n,m}=-\left[\mathbf{Y}\right]_{n,m}$ and
$Y_{n}=\sum_{k}\left[\mathbf{Y}\right]_{n,k}$, we can implement an arbitrary
symmetric $\mathbf{Y}$ so that the admittance matrix $\mathbf{Y}$ and the
scattering matrix $\boldsymbol{\Theta}$ are beyond diagonal. Particularly,
there are two special categories of BD-RIS, namely fully-connected and group-
connected RIS [4]. Due to the enhanced flexibility in $\mathbf{Y}$ and
$\boldsymbol{\Theta}$, BD-RIS is proven to outperform single-connected RIS [4,
23]-[32].

###  II-C Graph Theoretical Modeling

To model the general circuit topology of BD-RIS, we resort for the first time
to graph theoretical tools [35]. Specifically, we represent the circuit
topology of BD-RIS through a graph

$\mathcal{G}=\left(\mathcal{V},\mathcal{E}\right),$ (7)

where $\mathcal{V}$ represents the vertex set of $\mathcal{G}$ and is given by
the set of indices of RIS ports, i.e.

$\mathcal{V}=\left\\{1,2,\ldots,N\right\\},$ (8)

and $\mathcal{E}$ represents the edge set of $\mathcal{G}$ and is given by

$\mathcal{E}=\left\\{\left(n_{\ell},m_{\ell}\right)|\>n_{\ell},m_{\ell}\in\mathcal{V},\>Y_{n_{\ell},m_{\ell}}\neq
0,\>n_{\ell}\neq m_{\ell}\right\\}.$ (9)

Thus, there exists an edge between vertex $n_{\ell}$ and vertex $m_{\ell}$ if
and only if there is a tunable admittance connecting port $n_{\ell}$ and port
$m_{\ell}$, namely the $\ell$th admittance. Accordingly, given a graph
$\mathcal{G}$ with edge set
$\mathcal{E}=\left\\{\left(n_{\ell},m_{\ell}\right)\right\\}_{\ell=1}^{L}$,
the corresponding BD-RIS admittance matrix has $2L$ non-zero off-diagonal
entries, i.e. $\left[\mathbf{Y}\right]{}_{n_{\ell},m_{\ell}}$ and
$\left[\mathbf{Y}\right]{}_{m_{\ell},n_{\ell}}$ for $\ell=1,\ldots,L$, while
the other off-diagonal entries are zero.

Figure 2: Examples of $4$-port BD-RIS architectures (left) and their
corresponding graphs $\mathcal{G}$ (right), where $\mathcal{G}$ is (a) empty,
(b) disconnected and acyclic, (c) connected and acyclic, i.e., a tree, (d)
connected and cyclic, (e) complete.

To better clarify our graph theoretical modeling of BD-RIS, we show a
$4$-element single-connected RIS with its associated graph in Fig. 2(a), and
four examples of $4$-element BD-RISs with their associated graphs in Fig.
2(b)-(e). We also use Fig. 2 to illustrate the graph theoretical definitions
[35] that are used in this work, as briefly summarized in the following.

  * •

A graph is empty when there is no edge.

  * •

A graph is connected when there is a path, i.e., a finite sequence of distinct
edges joining a sequence of distinct vertices, from any vertex to any other
vertex.

  * •

A graph that is not connected is called disconnected.

  * •

A cyclic graph is a graph containing at least one cycle, i.e., a finite
sequence of distinct edges joining a sequence of vertices, where only the
first and last vertices are equal.

  * •

A graph that is not cyclic is called acyclic, or a forest.

  * •

A tree is defined as a connected and acyclic graph.

  * •

A graph is complete when each pair of distinct vertices is joined by an edge.

  * •

A graph is simple when there is no edge with identical ends (called loops) and
no multiple edges joining the same pair of vertices.

Given these definitions, we recognize that the graph for the single-connected
RIS in Fig. 2(a) is empty, the graph in Fig. 2(b) is disconnected and acyclic,
the graph in Fig. 2(c) is connected and acyclic, i.e., a tree, the graph in
Fig. 2(d) is connected and cyclic as it presents the cycle $1-2-3$, and the
graph for the fully-connected RIS in Fig. 2(e) is complete. In addition,
graphs associated with BD-RIS are always simple111In this work, we consider
graphs where the edges are not oriented since we assume the RIS to have a
reciprocal reconfigurable impedance network. BD-RIS architectures with non-
reciprocal reconfigurable impedance networks could be modeled through directed
graphs, i.e., graphs with oriented edges, but are beyond the scope of this
work.. Therefore, graph theory is effective to characterize and model the
circuit topology of BD-RIS and the corresponding admittance matrix
$\mathbf{Y}$.

Utilizing graph theory, we propose two novel families of BD-RIS with
remarkable properties, which are referred to as tree-connected RIS and forest-
connected RIS, in the following section.

##  III BD-RIS Architecture Design Utilizing Graph Theory

###  III-A Tree-Connected RIS

As a starting point, we investigate how the graph of BD-RIS influences the
system performance. To that end, we formulate the BD-RIS optimization problem
for MISO systems utilizing graph theory. Specifically, we assume the BD-RIS is
lossless and purely susceptive and aim to maximize the received signal power
$P_{R}=P_{T}\left|\mathbf{h}_{RI}\boldsymbol{\Theta}\mathbf{H}_{IT}\mathbf{w}\right|^{2}$
by jointly optimize $\mathbf{w}$ and $\boldsymbol{\Theta}$. Thus, we can
formulate the problem as

$\displaystyle\underset{\boldsymbol{\Theta},\mathbf{w}}{\mathsf{\mathrm{max}}}\;\;$
$\displaystyle
P_{T}\left|\mathbf{h}_{RI}\boldsymbol{\Theta}\mathbf{H}_{IT}\mathbf{w}\right|^{2}$
(10) $\displaystyle\mathsf{\mathrm{s.t.}}\;\;\;$
$\displaystyle\boldsymbol{\Theta}=\left(\mathbf{I}+jZ_{0}\mathbf{B}\right)^{-1}\left(\mathbf{I}-jZ_{0}\mathbf{B}\right),$
(11) $\displaystyle\mathbf{B}=\mathbf{B}^{T},$ (12)
$\displaystyle\mathbf{B}\in\mathcal{B}_{\mathcal{G}},$ (13)

where $\mathcal{B}_{\mathcal{G}}$ represents the set of possible susceptance
matrices of BD-RISs characterized by the graph
$\mathcal{G}=\left(\mathcal{V},\mathcal{E}\right)$ and is written as

$\mathcal{B}_{\mathcal{G}}=\left\\{\mathbf{B}|\left[\mathbf{B}\right]{}_{n,m}=0,n\neq
m,n,m\in\mathcal{V},\left(n,m\right)\notin\mathcal{E}\right\\}$ (14)

which means that an off-diagonal entry is zero if there exists no
corresponding edge in the graph.

From (10)-(13), we can deduce that the maximum received signal power depends
on the graph of the BD-RIS. Specifically, when the graph $\mathcal{G}$ has
more edges, the susceptance matrix $\mathbf{B}$ is more flexible so that the
maximum received signal power is higher. However, the enhanced performance is
achieved at the expense of higher circuit complexity (more connections from
the increased edges). Thus, it is worth designing the graph of BD-RIS to
achieve the best performance with the least complexity.

To that end, we first consider the case that the graph $\mathcal{G}$ is
complete, that is the fully-connected RIS. As shown in [4] and [25], maximum
ratio transmission (MRT) gives the optimal $\mathbf{w}$ and subsequently the
fully-connected RIS can achieve the upper bound of the received signal power
given by

$\bar{P}_{R}=P_{T}\left\|\mathbf{h}_{RI}\right\|^{2}\left\|\mathbf{H}_{IT}\right\|^{2},$
(15)

following the sub-multiplicativity of the norm [25]. Leveraging this upper
bound, herein we define a BD-RIS that achieves the performance upper bound
$\bar{P}_{R}$ for any channel realization as MISO optimal. Thus, the fully-
connected RIS is MISO optimal. More generally, the following lemma provides a
sufficient and necessary condition for a BD-RIS to be MISO optimal.

######  Lemma 1.

A BD-RIS with associated graph $\mathcal{G}$ is MISO optimal if and only if
$\mathcal{G}$ is a connected graph.

###### Proof.

Please refer to Appendix A. ∎

Using Lemma 1, we have the following proposition providing the least
complexity for MISO optimal BD-RIS.

######  Proposition 1.

The minimum number of edges in the graph of a MISO optimal BD-RIS is $N-1$,
with $N$ denoting the number of RIS elements.

###### Proof.

Please refer to Appendix B. ∎

Remarkably, a connected graph $\mathcal{G}$ on $N$ vertices with $N-1$ edges
is a tree. To show this, we observe that removing any edge from $\mathcal{G}$
makes the graph disconnected because of Proposition 1. Thus, $\mathcal{G}$
cannot have a cycle and must be a tree (connected and acyclic). Therefore, to
minimize the BD-RIS circuit complexity while maintaining optimal performance,
we propose tree-connected RIS as BD-RIS whose corresponding graph is a tree.
According to this definition, tree-connected RIS includes $N$ admittance
components connecting each port to ground and $N-1$ admittance components
interconnecting the ports to each other, yielding a total of $2N-1$ admittance
components, which is much less than the $N(N+1)/2$ admittance components in
fully-connected RIS.

###  III-B Two Examples of Tree-Connected RIS

Tree-connected RIS refers to a family of BD-RISs, including multiple possible
architectures. To clarify the concept of tree-connected RIS, in this
subsection we provide two specific examples of tree-connected RIS, referred to
as tridiagonal and arrowhead RIS.

####  III-B1 Tridiagonal RIS

Figure 3: Tridiagonal RIS with $N=8$.

We define tridiagonal RIS as tree-connected RIS whose graph $\mathcal{G}$ is a
path graph. In graph theory, the degree of a vertex is defined as the number
of edges incident with it, and a path graph is defined as a graph where two
vertices have degree one and all the others (if any) have degree two [35]. The
vertex set of the graph associated with tridiagonal RIS is defined as

$\mathcal{V}^{\mathrm{Tri}}=\left\\{n_{1},n_{2},\ldots,n_{N}\right\\},$ (16)

and the edge set can be expressed accordingly as

$\mathcal{E}^{\mathrm{Tri}}=\left\\{\left(n_{\ell},n_{\ell+1}\right)|\>\ell=1,\ldots,N-1\right\\}.$
(17)

Interestingly, the tridiagonal architectures have also been proposed to
realize low-complexity impedance matching networks for multiple antenna
systems [34]. In Fig. 3, we provide an illustrative example of tridiagonal RIS
with $N=8$. As a consequence of such architecture, the susceptance matrix of
tridiagonal RIS is symmetric and tridiagonal ($[\mathbf{B}]_{i,j}=0$ if
$|i-j|>1$), written as

$\mathbf{B}=\left[\begin{matrix}\left[\mathbf{B}\right]_{1,1}&\left[\mathbf{B}\right]_{1,2}&\cdots&0\\\
\left[\mathbf{B}\right]_{1,2}&\left[\mathbf{B}\right]_{2,2}&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\left[\mathbf{B}\right]_{N-1,N}\\\
0&\cdots&\left[\mathbf{B}\right]_{N-1,N}&\left[\mathbf{B}\right]_{N,N}\end{matrix}\right].$
(18)

Note that if the port indexes in $\mathcal{V}^{\mathrm{Tri}}$ are permuted,
$\mathbf{B}$ is a permuted tridiagonal matrix.

####  III-B2 Arrowhead RIS

Figure 4: Arrowhead RIS with $N=5$ where port 1 is the central vertex.

We define arrowhead RIS as tree-connected RIS whose graph $\mathcal{G}$ is a
star graph. In graph theory, a star graph is defined as a graph where at most
one vertex, called central, has degree greater than one and all the others
have degree one [35]. Accordingly, the vertex set of the graph associated with
arrowhead RIS is defined as

$\mathcal{V}^{\mathrm{Arrow}}=\left\\{c,n_{1},n_{2},\ldots,n_{N-1}\right\\},$
(19)

where $c$ denotes the central vertex, while the edge set is consequently
expressed as

$\mathcal{E}^{\mathrm{Arrow}}=\left\\{\left(c,n_{\ell}\right)|\>\ell=1,\ldots,N-1\right\\}.$
(20)

In Fig. 4, we provide an illustrative example of arrowhead RIS with $N=5$
where port 1 is the central vertex. As a consequence, the susceptance matrix
of arrowhead RIS is symmetric and arrowhead ($[\mathbf{B}]_{i,j}=0$ if $i\neq
c$, $j\neq c$, and $i\neq j$) [36]. Assuming port 1 is the central vertex, the
susceptance matrix of arrowhead RIS can be written as

$\mathbf{B}=\left[\begin{matrix}\left[\mathbf{B}\right]_{1,1}&\left[\mathbf{B}\right]_{1,2}&\cdots&\left[\mathbf{B}\right]_{1,N}\\\
\left[\mathbf{B}\right]_{1,2}&\left[\mathbf{B}\right]_{2,2}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\
\left[\mathbf{B}\right]_{1,N}&0&\cdots&\left[\mathbf{B}\right]_{N,N}\end{matrix}\right].$
(21)

Note that if the central vertex is not port 1, $\mathbf{B}$ is a permuted
arrowhead matrix.

It should be noted that all tree-connected RISs satisfy the necessary
condition to be MISO optimal and contain the same number of tunable admittance
components. Thus, tridiagonal and arrowhead RIS have the same circuit
complexity and MISO optimality. In practice, we can select the suitable tree-
connected RIS architecture according to the use case. Tridiagonal RIS can be
easily implemented with cables or tapes, thanks to the path graph circuit
topology, so it enables the practical development of tree-connected RIS with
uniform linear arrays (ULAs) or radio stripes [37]. Conversely, arrowhead BD-
RIS is more suitable to develop tree-connected RIS with uniform planar arrays
(UPAs).

###  III-C Forest-Connected RIS

To further reduce the circuit complexity of tree-connected RIS, especially for
the large-scale case, we propose forest-connected RIS. A forest-connected RIS
is defined as a BD-RIS where the $N$ RIS elements are divided into $G=N/N_{G}$
groups with group size $N_{G}$ and each group utilizes the tree-connected
architecture (i.e. the graph for each group is a tree on $N_{G}$
vertices)222Note that the tree-connected RIS is a special case of the forest-
connected RIS, i.e., with $G=1$. This is consistent with the fact that in
graph theory a tree is a special case of forest.. Therefore, the graph
$\mathcal{G}$ associated with the forest-connected RIS is a forest, and the
corresponding vertex and edge sets can be represented as

$\mathcal{V}=\cup_{g=1}^{G}\mathcal{V}_{g},\>\mathcal{E}=\cup_{g=1}^{G}\mathcal{E}_{g},$
(22)

where $\mathcal{V}_{g}$ and $\mathcal{E}_{g}$ denote the vertex and edge sets
of the graph associated with the $g$th group for $g=1,\ldots,G$, with
$\mathcal{V}_{g_{1}}\cap\mathcal{V}_{g_{2}}=\emptyset$ for all $g_{1}\neq
g_{2}$.

More specifically, the tree-connected architecture for each group in the
forest-connected RIS can be either tridiagonal or arrowhead. When the
tridiagonal architecture is used, the vertex and edge sets of the graph
associated with forest-connected RIS are defined as

$\mathcal{V}_{\textrm{Forest}}^{\textrm{Tri}}=\cup_{g=1}^{G}\left\\{n_{g,1},n_{g,2},\ldots,n_{g,N_{G}}\right\\},$
(23)
$\mathcal{E}_{\textrm{Forest}}^{\textrm{Tri}}=\cup_{g=1}^{G}\left\\{\left(n_{g,\ell},n_{g,\ell+1}\right)|\>\ell=1,\ldots,N_{G}-1\right\\},$
(24)

similarly to (16) and (17). Accordingly, the susceptance matrix of forest-
connected RIS with tridiagonal architecture for each group is block diagonal
with each block being symmetric and tridiagonal. On the other hand, when the
arrowhead architecture is used, the vertex and edge sets of the graph
associated with forest-connected RIS are defined as

$\mathcal{V}_{\textrm{Forest}}^{\textrm{Arrow}}=\cup_{g=1}^{G}\left\\{c_{g},n_{g,1},n_{g,2},\ldots,n_{g,N_{G}-1}\right\\},$
(25)
$\mathcal{E}_{\textrm{Forest}}^{\textrm{Arrow}}=\cup_{g=1}^{G}\left\\{\left(c_{g},n_{g,\ell}\right)|\>\ell=1,\ldots,N_{G}-1\right\\},$
(26)

where $c_{g}$ is the index of the central vertex for the $g$th group,
similarly to (19) and (20). Accordingly, the susceptance matrix of forest-
connected RIS with arrowhead architecture for each group is block diagonal
with each block being symmetric and arrowhead.

The forest-connected RIS achieves a good performance-complexity trade-off
between the single-connected and the tree-connected RIS. Note that the single-
connected and tree-connected RIS can be viewed as two special cases of the
forest-connected RIS, with $N_{G}=1$ and $N_{G}=N$, respectively. In addition,
forest-connected RIS is equivalent to group-connected RIS when $N_{G}=2$ [4].
The number of tunable admittance components in forest-connected RIS with group
size $N_{G}$ is $N(2-1/N_{G})$.

##  IV Optimization of Tree- and Forest-Connected RIS for MISO Systems

In this section, we optimize tree-connected and forest-connected RIS to
maximize the received signal power in MISO systems. For tree-connected RIS, we
show that any tree-connected RIS is MISO optimal and provide a closed-form
global optimal solution. For forest-connected RIS, we provide a low-complexity
iterative solution.

###  IV-A Tree-Connected RIS Optimization

The tree-connected RIS optimization to maximize the received signal power in
MISO systems can be formulated as (10)-(13) plus a constraint that graph
$\mathcal{G}$ is a tree. Recall that the received signal power in BD-RIS-aided
MISO systems is upper bounded by
$\bar{P}_{R}=P_{T}\left\|\mathbf{h}_{RI}\right\|^{2}\left\|\mathbf{H}_{IT}\right\|^{2}$.
In the following, we prove that there is always one and only one solution for
the optimal susceptance matrix $\mathbf{B}$ of tree-connected RIS to achieve
the upper bound $\bar{P}_{R}$, and propose an algorithm to find such optimal
$\mathbf{B}$.

The key to achieve the upper bound $\bar{P}_{R}$ given by (15) is to find a
complex symmetric unitary matrix $\boldsymbol{\Theta}$ satisfying

$\hat{\mathbf{h}}_{RI}^{H}=\boldsymbol{\Theta}\mathbf{u}_{IT},$ (27)

where $\hat{\mathbf{h}}_{RI}=\mathbf{h}_{RI}/\left\|\mathbf{h}_{RI}\right\|$
and $\mathbf{u}_{IT}=\mathbf{u}_{\text{max}}(\mathbf{H}_{IT})$ is the dominant
left singular vector of $\mathbf{H}_{IT}$ [25]. Substituting (3) into (27), we
can equivalently rewrite (27) as

$\left(\mathbf{I}+jZ_{0}\mathbf{B}\right)\hat{\mathbf{h}}_{RI}^{H}=\left(\mathbf{I}-jZ_{0}\mathbf{B}\right)\mathbf{u}_{IT},$
(28)

which can be expressed in a compact form as

$\mathbf{B}\boldsymbol{\alpha}=\boldsymbol{\beta},$ (29)

where
$\boldsymbol{\alpha}=jZ_{0}\left(\mathbf{u}_{IT}+\hat{\mathbf{h}}_{RI}^{H}\right)\in\mathbb{C}^{N\times
1}$ and
$\boldsymbol{\beta}=\mathbf{u}_{IT}-\hat{\mathbf{h}}_{RI}^{H}\in\mathbb{C}^{N\times
1}$. The equation in (29) is composed of $N$ linear equations with $2N-1$
unknowns. The linear equation coefficients $\boldsymbol{\alpha}$ and
$\boldsymbol{\beta}$ are complex vectors, while the $2N-1$ unknowns are real
since they are the entries of the susceptance matrix $\mathbf{B}$ of the tree-
connected RIS, which are not constrained to be zero as shown in (18) and (21).
We aim to solve (29) as it is a sufficient and necessary condition to achieve
the performance upper bound $\bar{P}_{R}$. To that end, we rewrite (29) as
$2N$ linear equations with real coefficients and $2N-1$ real unknowns, namely

$\left[\begin{array}[]{c}\mathbf{B}\\\
\hdashline\mathbf{B}\end{array}\right]\mathbf{a}=\mathbf{b},$ (30)

where $\mathbf{a}\in\mathbb{R}^{2N\times 1}$ and
$\mathbf{b}\in\mathbb{R}^{2N\times 1}$ are defined as

$\mathbf{a}=\left[\begin{array}[]{c}\Re\left\\{\boldsymbol{\alpha}\right\\}\\\
\hdashline\Im\left\\{\boldsymbol{\alpha}\right\\}\end{array}\right],\>\mathbf{b}=\left[\begin{array}[]{c}\Re\left\\{\boldsymbol{\beta}\right\\}\\\
\hdashline\Im\left\\{\boldsymbol{\beta}\right\\}\end{array}\right].$ (31)

To solve (30), we further rewrite the equation such that the $2N-1$ real
unknowns are explicitly collected in a vector
$\mathbf{x}\in\mathbb{R}^{(2N-1)\times 1}$. Specifically, given a tree-
connected RIS whose graph has an edge set
$\mathcal{E}=\left\\{\left(n_{\ell},m_{\ell}\right)\right\\}_{\ell=1}^{N-1}$
such as (17) or (20), the $2N-1$ real unknowns are collected as

$\mathbf{x}=\left[\left[\mathbf{B}\right]_{1,1},\ldots,\left[\mathbf{B}\right]_{N,N},\left[\mathbf{B}\right]_{n_{1},m_{1}},\ldots,\left[\mathbf{B}\right]_{n_{N-1},m_{N-1}}\right]^{T},$
(32)

where $\text{[$\mathbf{B}$]}_{n,n}$ for $n=1,\ldots,N$ denote the $N$ diagonal
entries of $\mathbf{B}$ and $[\mathbf{B}]_{n_{\ell},m_{\ell}}$ for
$\ell=1,\ldots,N-1$ denote the $N-1$ off-diagonal entries of $\mathbf{B}$
specified by the edge set of graph. Accordingly, (30) can be equivalently
rewritten as

$\mathbf{A}\mathbf{x}=\mathbf{b},$ (33)

where $\mathbf{A}\in\mathbb{R}^{2N\times(2N-1)}$ is the coefficient matrix
given by

$\mathbf{A}=\left[\begin{array}[]{cc}\Re\left\\{\mathbf{A}_{1}\right\\}&\Re\left\\{\mathbf{A}_{2}\right\\}\\\
\hdashline\Im\left\\{\mathbf{A}_{1}\right\\}&\Im\left\\{\mathbf{A}_{2}\right\\}\end{array}\right],$
(34)

where $\mathbf{A}_{1}\in\mathbb{C}^{N\times N}$ and
$\mathbf{A}_{2}\in\mathbb{C}^{N\times(N-1)}$. Because the real and imaginary
parts of $\mathbf{A}_{1}$ are multiplied by the $N$ diagonal entries of
$\mathbf{B}$ in (33), to build the equivalence between (30) and (33),
$\mathbf{A}_{1}$ should be given by

$\mathbf{A}_{1}=\text{diag}\left(\boldsymbol{\alpha}\right).$ (35)

On the other hand, the real and imaginary parts of $\mathbf{A}_{2}$ are
multiplied by the $N-1$ off-diagonal entries of $\mathbf{B}$ including
$\left[\mathbf{B}\right]_{n_{1},m_{1}},\ldots,\left[\mathbf{B}\right]_{n_{N-1},m_{N-1}}$.
For this reason, the structure of $\mathbf{A}_{2}$ depends on how the RIS
ports are connected to each other, that is the specific graph associated with
the tree-connected RIS. Accordingly, the entry of the $\ell$th column of
$\mathbf{A}_{2}$ for $\ell=1,\ldots,N-1$ is given by

$\left[\mathbf{A}_{2}\right]{}_{k,\ell}=\begin{cases}[\boldsymbol{\alpha}]_{n_{\ell}}&\textrm{if}\>k=m_{\ell}\\\
{}[\boldsymbol{\alpha}]_{m_{\ell}}&\textrm{if}\>k=n_{\ell}\\\
0&\textrm{otherwise}\end{cases}.$ (36)

The following proposition provides a useful property of tree-connected RIS,
which we can leverage to solve the linear equations (33).

######  Proposition 2.

For any tree-connected RIS with $N$ elements, the coefficient matrix
$\mathbf{A}\in\mathbb{R}^{2N\times(2N-1)}$ has full column rank, i.e.,
$r\left(\mathbf{A}\right)=2N-1$.

###### Proof.

Please refer to Appendix C. ∎

According to Proposition 2, the linear equations (33) has one solution or no
solution [38]. Furthermore, we show that it has exactly one solution by using
the following proposition.

######  Proposition 3.

For any tree-connected RIS with $N$ elements, the augmented matrix
$\left[\mathbf{A}|\mathbf{b}\right]\in\mathbb{R}^{2N\times 2N}$ has rank
$r\left(\left[\mathbf{A}|\mathbf{b}\right]\right)=2N-1$.

###### Proof.

Please refer to Appendix D. ∎

According to the Rouche-Capelli theorem [38], a system of linear equations is
consistent if the rank of the coefficient matrix $\mathbf{A}$ is equal to the
rank of the augmented matrix $\left[\mathbf{A}|\mathbf{b}\right]$. Thus,
according to Proposition 3, the system of linear equations (33) is consistent
and has exactly one solution. As a result, we can find the solution of (33) as
$\mathbf{x}=\mathbf{A}^{\dagger}\mathbf{b}$, where
$\mathbf{A}^{\dagger}=\left(\mathbf{A}^{T}\mathbf{A}\right)^{-1}\mathbf{A}^{T}$
is the Moore-Penrose pseudo-inverse of $\mathbf{A}$, and subsequently the
optimal susceptance matrix $\mathbf{B}$ of the tree-connected RIS can be found
through (32).

To conclude, we prove that for any tree-connected RIS there is always one and
only one global optimal solution for the susceptance matrix $\mathbf{B}$ to
achieve the upper bound $\bar{P}_{R}$ for any channel realization. In Alg. 1,
we summarize the steps required to optimize tree-connected RIS for MISO
systems.

0: $\mathbf{h}_{RI}\in\mathbb{C}^{1\times N}$,
$\mathbf{H}_{IT}\in\mathbb{C}^{N\times M}$.

0: $\mathbf{B}$.

1: Obtain
$\hat{\mathbf{h}}_{RI}=\frac{\mathbf{h}_{RI}}{\left\|\mathbf{h}_{RI}\right\|}$,
$\mathbf{u}_{IT}=\mathbf{u}_{\text{max}}\left(\mathbf{H}_{IT}\right)$.

2: Obtain
$\boldsymbol{\alpha}=jZ_{0}\left(\mathbf{u}_{IT}+\hat{\mathbf{h}}_{RI}^{H}\right)$,
$\boldsymbol{\beta}=\mathbf{u}_{IT}-\hat{\mathbf{h}}_{RI}^{H}$.

3: Obtain $\mathbf{A}_{1}$ and $\mathbf{A}_{2}$ by (35) and (36),
respectively.

4: Obtain $\mathbf{A}$ and $\mathbf{b}$ by (34) and (31), respectively.

5: Obtain
$\mathbf{x}=\left(\mathbf{A}^{T}\mathbf{A}\right)^{-1}\mathbf{A}^{T}\mathbf{b}$.

6: Obtain $\mathbf{B}$ by (32).

7: Return $\mathbf{B}$.

Algorithm 1 Closed-form global optimization of tree-connected RIS for MISO
systems

###  IV-B Forest-Connected RIS Optimization

The forest-connected RIS optimization to maximize the received signal power in
MISO systems is formulated as

$\displaystyle\underset{\boldsymbol{\Theta},\mathbf{w}}{\mathsf{\mathrm{max}}}\;\;$
$\displaystyle
P_{T}\left|\mathbf{h}_{RI}\boldsymbol{\Theta}\mathbf{H}_{IT}\mathbf{w}\right|^{2}$
(37) $\displaystyle\mathsf{\mathrm{s.t.}}\;\;\;$
$\displaystyle\boldsymbol{\Theta}=\left(\mathbf{I}+jZ_{0}\mathbf{B}\right)^{-1}\left(\mathbf{I}-jZ_{0}\mathbf{B}\right),$
(38)
$\displaystyle\mathbf{B}=\mathrm{diag}\left(\mathbf{B}_{1},\ldots,\mathbf{B}_{G}\right),$
(39) $\displaystyle\mathbf{B}_{g}=\mathbf{B}_{g}^{T},\>\forall g,$ (40)
$\displaystyle\mathbf{B}_{g}\in\mathcal{B}_{\mathcal{G},g},\>\forall g,$ (41)

where the susceptance matrix $\mathbf{B}$ of the forest-connected RIS is a
block diagonal matrix with $\mathbf{B}_{g}$ being the $g$th block and
$\mathcal{B}_{\mathcal{G},g}$ represents the set of the $g$th block written as

$\mathcal{B}_{\mathcal{G},g}=\left\\{\mathbf{B}_{g}|\left[\mathbf{B}_{g}\right]{}_{n,m}=0,n\neq
m,n,m\in\mathcal{V}_{g},\left(n,m\right)\notin\mathcal{E}_{g}\right\\},$ (42)

where $\mathcal{V}_{g}$ and $\mathcal{E}_{g}$ are the vertex and edge sets of
the graph for the $g$th group for $g=1,\ldots,G$. Specifically,
$\mathcal{V}_{g}$ and $\mathcal{E}_{g}$ can be found by (23) and (24) when the
tridiagonal architecture is used for the $g$th group, or by (25) and (26) when
the arrowhead architecture is used.

Different from optimizing the tree-connected RIS, it is hard to find a tight
upper bound on the received signal power in forest-connected RIS-aided MISO
systems due to block diagonal characteristics of the susceptance matrix, which
makes it hard to derive a closed-form global optimal solution. To solve the
challenging forest-connected RIS optimization problem, we propose an iterative
optimization approach, where the precoder $\mathbf{w}$ and the RIS susceptance
matrix $\mathbf{B}$ are alternatively optimized.

####  IV-B1 Optimizing $\mathbf{B}$ with Fixed $\mathbf{w}$

When the precoder $\mathbf{w}$ is fixed, we introduce
$\mathbf{h}_{IT}^{\mathrm{eff}}=\mathbf{H}_{IT}\mathbf{w}$ as the effective
channel between the transmitter and RIS so that the forest-connected RIS-aided
MISO system is equivalently converted to a forest-connected RIS-aided SISO
system. Thus, we can equivalently rewrite the problem (37)-(41) as

$\displaystyle\underset{\boldsymbol{\Theta}_{g}}{\mathsf{\mathrm{max}}}\;\;$
$\displaystyle
P_{T}\left|\sum_{g=1}^{G}\mathbf{h}_{RI,g}\boldsymbol{\Theta}_{g}\mathbf{h}_{IT,g}^{\mathrm{eff}}\right|^{2}$
(43) $\displaystyle\mathsf{\mathrm{s.t.}}\;\;\;$
$\displaystyle\boldsymbol{\Theta}_{g}=\left(\mathbf{I}+jZ_{0}\mathbf{B}_{g}\right)^{-1}\left(\mathbf{I}-jZ_{0}\mathbf{B}_{g}\right),$
(44) $\displaystyle\mathbf{B}_{g}=\mathbf{B}_{g}^{T},\>\forall g,$ (45)
$\displaystyle\mathbf{B}_{g}\in\mathcal{B}_{\mathcal{G},g},\>\forall g,$ (46)

where $\mathbf{h}_{RI,g}\in\mathbb{C}^{1\times N_{G}}$ and
$\mathbf{h}_{IT,g}^{\mathrm{eff}}\in\mathbb{C}^{N_{G}\times 1}$ consist of the
$N_{G}$ entries of $\mathbf{h}_{RI}$ and $\mathbf{h}_{IT}^{\mathrm{eff}}$
corresponding to the RIS elements of the $g$th group, respectively [4]. To
solve the problem (43)-(46), we first consider the case that the graph for
each group is complete, that is the group-connected RIS where $\mathbf{B}_{g}$
can be arbitrary symmetric matrix. As shown in [4] and [25], the received
signal power in the group-connected RIS aided SISO system, i.e.
$P_{T}\left|\sum_{g=1}^{G}\mathbf{h}_{RI,g}\boldsymbol{\Theta}_{g}\mathbf{h}_{IT,g}^{\mathrm{eff}}\right|^{2}$,
is upper bounded by

$\bar{P}_{R}^{\mathrm{eff}}=P_{T}\left(\sum_{g=1}^{G}\left\|\mathbf{h}_{RI,g}\right\|\left\|\mathbf{h}_{IT,g}^{\mathrm{eff}}\right\|\right)^{2}.$
(47)

The key to achieve such upper bound (47) is to find complex symmetric unitary
matrices $\boldsymbol{\Theta}_{g}$ for $g=1,\ldots,G$ satisfying

$\hat{\mathbf{h}}_{RI,g}^{H}=\boldsymbol{\Theta}_{g}\hat{\mathbf{h}}_{IT,g}^{\mathrm{eff}},\>\forall
g,$ (48)

where $\hat{\mathbf{h}}_{RI,g}=\mathbf{h}_{RI,g}/\|\mathbf{h}_{RI,g}\|$ and
$\hat{\mathbf{h}}_{IT,g}^{\mathrm{eff}}=\mathbf{h}_{IT,g}^{\mathrm{eff}}/\|\mathbf{h}_{IT,g}^{\mathrm{eff}}\|$.
Recall that each group in the forest-connected RIS utilizes the tree-connected
architecture. Thus, referring to the tree-connected RIS optimization shown in
Section IV.A, it is straightforward to show that for each group of the forest-
connected RIS there is always one and only one solution for $\mathbf{B}_{g}$
whose corresponding $\boldsymbol{\Theta}_{g}$ satisfying (48), so that the
upper bound (47) can be achieved. Moreover, the optimal $\mathbf{B}_{g}$ for
each group can be found by Alg. 1 with the input of the channels
$\mathbf{h}_{RI,g}$ and $\mathbf{h}_{IT,g}^{\mathrm{eff}}$. Therefore, the
susceptance matrix $\mathbf{B}$ of the forest-connected RIS can be globally
optimized to achieve the upper bound (47) when $\mathbf{w}$ is fixed.

0: $\mathbf{h}_{RI}\in\mathbb{C}^{1\times N}$,
$\mathbf{H}_{IT}\in\mathbb{C}^{N\times M}$.

0: $\mathbf{B}$ and $\mathbf{w}$.

1: Initialize $\mathbf{w}$.

2: while no convergence of objective (37) do

3: Update $\mathbf{B}_{g}$ by Alg. 1 with input $\mathbf{h}_{RI,g}$,
$\mathbf{h}_{IT,g}^{\mathrm{eff}}$, $\forall g$.

4: Obtain $\boldsymbol{\Theta}$ from
$\mathbf{B}=\mathrm{diag}\left(\mathbf{B}_{1},\ldots,\mathbf{B}_{G}\right)$ by
(3).

5: Update
$\mathbf{w}=\left(\mathbf{h}_{RI}\boldsymbol{\Theta}\mathbf{H}_{IT}\right)^{H}/\|\mathbf{h}_{RI}\boldsymbol{\Theta}\mathbf{H}_{IT}\|$.

6: end while

7: Return $\mathbf{B}$ and $\mathbf{w}$.

Algorithm 2 Optimization of forest-connected RIS for MISO systems

####  IV-B2 Optimizing $\mathbf{w}$ with Fixed $\mathbf{B}$

When the RIS susceptance matrix $\mathbf{B}$ is fixed, it is obvious that the
optimal $\mathbf{w}$ is the MRT given by
$\mathbf{w}=(\mathbf{h}_{RI}\boldsymbol{\Theta}\mathbf{H}_{IT})^{H}/\left\|\mathbf{h}_{RI}\boldsymbol{\Theta}\mathbf{H}_{IT}\right\|$,
where $\boldsymbol{\Theta}$ can be computed by (3) as a function of
$\mathbf{B}$.

The precoder $\mathbf{w}$ and the RIS susceptance matrix $\mathbf{B}$ are
alternatively optimized until convergence of the objective (37). We summarize
the steps to optimize forest-connected RIS in MISO systems in Alg. 2. The
iterative algorithm is initialized by randomly setting $\mathbf{w}$ to a
feasible value. In addition, the convergence of Alg. 2 is guaranteed by the
following two facts. First, at each iteration, the objective given by the
received signal power $P_{R}$ is non-decreasing. Second, the objective
function is upper bounded by
$P_{T}\left\|\mathbf{h}_{RI}\right\|^{2}\left\|\mathbf{H}_{IT}\right\|^{2}$
because of the sub-multiplicativity of the spectral norm.

##  V Performance Evaluation

In this section, we provide the performance evaluation for the proposed tree-
and forest-connected RIS. We consider a two-dimensional coordinate system, as
shown in Fig. 5. The transmitter and receiver are located at $(0,0)$ and
$(52,0)$ in meters (m), respectively. The RIS is located at $(50,2)$ and it is
equipped with $N$ elements. For the large-scale path loss, we use the
distance-dependent path loss modeled as
$L_{ij}(d_{ij})=L_{0}(d_{ij}/D_{0})^{-\alpha_{ij}}$, where $L_{0}$ is the
reference path loss at distance $D_{0}=1$ m, $d_{ij}$ is the distance, and
$\alpha_{ij}$ is the path loss exponent for $ij\in\\{RI,IT\\}$. We set
$L_{0}=-30$ dB, $\alpha_{RI}=2.8$, $\alpha_{IT}=2$, and $P_{T}=10$ mW. For the
small-scale fading, we assume that the channel from the RIS to the receiver is
Rayleigh fading. The channel from the transmitter to the RIS is modeled with
Rician fading, given by

$\mathbf{H}_{IT}=\sqrt{L_{IT}}\left(\sqrt{\frac{K}{1+K}}\mathbf{H}_{IT}^{\mathrm{LoS}}+\sqrt{\frac{1}{1+K}}\mathbf{H}_{IT}^{\mathrm{NLoS}}\right),$
(49)

where $K$ refers to the Rician factor, while $\mathbf{H}_{IT}^{\mathrm{LoS}}$
and
$\mathrm{vec}(\mathbf{H}_{IT}^{\mathrm{NLoS}})\sim\mathcal{CN}\left(\boldsymbol{0},\mathbf{I}\right)$
represent the small-scale line-of-sight (LoS) and non-line-of-sight (NLoS)
(Rayleigh fading) components, respectively. We consider two scenarios, with
Rician factor $K=0$ dB and $K=10$ dB.

Figure 5: Two-dimensional coordinate system for the RIS-aided MISO system.

Figure 6: Received signal power in MISO systems aided by fully- and tree-
connected RIS.

Figure 7: Received signal power in MISO systems aided by tree-, group-,
forest-, and single-connected RIS, with $M=2$.

###  V-A Tree-Connected RIS-Aided MISO Systems

We first evaluate the performance of the tree-connected RIS to verify that it
is MISO optimal. Specifically, the tree-connected RIS is optimized through
Alg. 1 and compared with the performance upper bound (15) achieved by the
fully-connected RIS. We recall that in the fully-connected RIS, all the RIS
ports are connected with each other, so that $\mathbf{B}$ is an arbitrary
symmetric matrix and $\boldsymbol{\Theta}$ satisfies that

$\boldsymbol{\Theta}^{H}\boldsymbol{\Theta}=\boldsymbol{\mathrm{I}},\boldsymbol{\Theta}=\boldsymbol{\Theta}^{T},$
(50)

as shown in [4]. In Fig. 6, we provide the received signal power achieved in
MISO systems aided by fully- and tree-connected RIS. We can make the following
observations. _First_ , as expected, the tree-connected RIS can always achieve
the performance upper bound. However, it has much lower circuit complexity
than the fully-connected RIS, which will be quantitatively shown in Section
V-C. _Second_ , higher received signal power can be obtained by increasing the
number of transmit antennas $M$ for both fully- and tree-connected RIS. _Last_
, Rician fading channels with a lower Rician factor offer richer scattering,
allowing to reach a slightly higher performance.

Figure 8: Received signal power in MISO systems aided by tree-, group-,
forest-, and single-connected RIS, with $M=8$.

###  V-B Forest-Connected RIS-Aided MISO Systems

We next evaluate the performance of the forest-connected RIS. Specifically,
the forest-connected RIS is optimized through Alg. 2 and it is compared with
tree-, group-, and single-connected RIS. For the group-connected RIS, we
recall that the $N$ element are divided into $G$ groups and all the RIS ports
within the same group are connected with each other, so that $\mathbf{B}$ is
arbitrary symmetric block diagonal matrix and $\boldsymbol{\Theta}$ satisfies

$\boldsymbol{\Theta}=\mathrm{diag}\left(\boldsymbol{\Theta}_{1},\boldsymbol{\Theta}_{2},\ldots,\boldsymbol{\Theta}_{G}\right),$
(51)
$\boldsymbol{\Theta}_{g}=\boldsymbol{\Theta}_{g}^{T},\>\boldsymbol{\Theta}_{g}^{H}\boldsymbol{\Theta}_{g}=\boldsymbol{\mathrm{I}},\>\forall
g,$ (52)

as shown in [4]. In Figs. 7 and 8, we provide the received signal power in
MISO systems aided by tree-, group-, forest-, and single-connected RIS, with
$M=2$ and $M=8$, respectively. Group-connected and single-connected RIS are
optimized as proposed in [25, Alg. 2]. We can make the following observations.

_First_ , the forest-connected RIS can always achieve the same received signal
power as the group-connected RIS with the same group size. However, it has
much lower circuit complexity than the group-connected RIS with the same group
size, as quantitatively shown in Section V-C.

_Second_ , the forest-connected RIS achieves a higher received signal power
than the single-connected RIS. For example, forest-connected RIS with group
size $8$ brings an improvement in the received signal power of $44.6\%$, when
$M=2$, $N=64$, and $K=0$ dB. On the other hand, it achieves a lower received
signal power than the tree-connected RIS due to the simplified circuit
complexity. Therefore, it is shown that the forest-connected RIS achieves a
good performance-complexity trade-off between the single-connected and the
tree-connected RIS.

_Third_ , the received signal power increases with the group size in the
forest-connected RIS, which is because increasing the group size can provide
more flexibility for RIS optimization.

Fourth, higher received signal power can be obtained by increasing the number
of transmit antennas $M$ for all the BD-RIS architectures.

_Last_ , BD-RIS is particularly beneficial over single-connected RIS in the
presence of fading channels with lower Rician factors, in agreement with [4].

###  V-C Circuit Topology Complexity

We finally evaluate the circuit topology complexity of the proposed tree- and
forest-connected RIS. As analyzed in Section III, the circuit topology
complexity in terms of the number of the tunable admittance components of the
tree- and forest-connected RIS is $2N-1$ and $N(2-1/N_{G})$, respectively. For
comparison, we also consider the circuit topology complexity of fully-,
group-, and single-connected RIS, given by $N(N+1)/2$, $N(N_{G}+1)/2$, and
$N$, respectively [4]. In Fig. 9, we provide the number of tunable admittance
components in the fully-, group, tree-, forest-, and single-connected RIS. We
can make the following observations.

First, compared with the fully-connected RIS, the tree-connected RIS has much
lower circuit topology complexity. For example, the number of tunable
admittance components is decreased by $16.4$ times when $N=64$ in the tree-
connected RIS compared to the fully-connected RIS, but they achieve the same
performance.

Second, compared with the group-connected RIS with same group size, the
forest-connected RIS has much lower circuit topology complexity. For example,
the number of tunable admittance components is reduced by $2.4$ times when
$N=64$ in the forest-connected RIS with group size $8$ compared to the group-
connected RIS with group size $8$, but they achieve the same performance.

Third, increasing the group size in the forest-connected RIS will increase the
number of tunable admittance components while also enhancing the performance.

Fourth, compared with the single-connected RIS, the tree- and forest-connected
RIS introduce appropriate complexity but achieves an improvement in the
received power.

To conclude, we demonstrate that the benefit of the tree-connected (resp.
forest-connected) RIS over the fully-connected (resp. group-connected) RIS
lies in their highly simplified circuit complexity while maintaining optimal
performance. Therefore, the proposed tree- and forest-connected architectures
significantly improve the performance-complexity trade-off over existing BD-
RIS architectures.

##  VI Conclusion

We propose novel modeling, architecture design, and optimization for BD-RIS by
utilizing graph theory. In particular, we model BD-RIS architectures as
graphs, capturing the presence of interconnections between the RIS elements.
Through this modeling, we prove that a BD-RIS achieves the performance upper
bound in MISO systems if and only if its associated graph is connected. This
remarkable result allows us to characterize the least complex BD-RIS
architectures able to achieve the performance upper bound in MISO systems,
denoted as tree-connected RIS. We also propose forest-connected RIS to bridge
between the single-connected and the tree-connected architectures. To optimize
these novel BD-RIS architectures, we derive a closed-form global optimal
solution for tree-connected RIS, and an iterative algorithm for forest-
connected RIS. Numerical results confirm that tree-connected (resp. forest-
connected) RIS achieve the same performance as fully-connected (resp. group-
connected) RIS, with a significantly reduced circuit complexity by up to 16.4
times.

The proposed graph theoretical modeling of BD-RIS is expected to promote
significant advancements in the growth of BD-RIS. This modeling can be used to
explore the vast design space of possible architectures and evaluate them in
terms of achievable performance and circuit complexity. This will enable the
systematic development of new BD-RIS architectures with a more favorable
balance between performance and complexity.

Figure 9: Circuit topology complexity given by the number of tunable
admittance components in fully-, group-, tree-, forest-, and single-connected
RIS.

## Appendix

###  VI-A Proof of Lemma 1

We prove the necessary condition by showing that if $\mathcal{G}$ is not a
connected graph, the corresponding BD-RIS is not MISO optimal. If
$\mathcal{G}$ is disconnected, it has $C\geq 2$ connected components, where
the $c$th component includes $N^{(c)}$ ports, for $c=1,\ldots,C$, with
$\sum_{c=1}^{C}N^{(c)}=N$. With no loss of generality, we assume that each
component includes adjacent ports. Thus, the admittance matrix $\mathbf{Y}$
given by (6) is block diagonal, with the $c$th block having dimensions
$N^{(c)}\times N^{(c)}$, for $c=1,\ldots,C$. As a consequence of (2), also the
scattering matrix $\boldsymbol{\Theta}$ is block diagonal, and writes as
$\boldsymbol{\Theta}=\mathrm{diag}\left(\boldsymbol{\Theta}_{1},\ldots,\boldsymbol{\Theta}_{C}\right)$,
where $\boldsymbol{\Theta}_{c}\in\mathbb{C}^{N^{(c)}\times N^{(c)}}$, for
$c=1,\ldots,C$. Thus, the received signal power (10) in the case of a
disconnected graph $\mathcal{G}$ is

$P_{R}^{\textrm{$\mathrm{DisC}$}}=P_{T}\left|\sum_{c=1}^{C}\mathbf{h}_{RI,c}\boldsymbol{\Theta}_{c}\mathbf{H}_{IT,c}\mathbf{w}\right|^{2},$
(53)

where $\mathbf{h}_{RI,c}\in\mathbb{C}^{1\times N^{(c)}}$ and
$\mathbf{H}_{IT,c}\in\mathbb{C}^{N^{(c)}\times M}$ contain the $N^{(c)}$
elements of $\mathbf{h}_{RI}$ and rows of $\mathbf{H}_{IT}$ corresponding to
the $N^{(c)}$ RIS elements grouped into the $c$th component, respectively. The
received signal power $P_{R}^{\textrm{$\mathrm{DisC}$}}$ is upper bounded by

$\bar{P}_{R}^{\textrm{DisC}}=P_{T}\left(\sum_{c=1}^{C}\left\|\mathbf{h}_{RI,c}\right\|\left\|\mathbf{H}_{IT,c}\mathbf{w}\right\|\right)^{2},$
(54)

following the Cauchy-Schwarz inequality and that
$\boldsymbol{\Theta}_{c}^{H}\boldsymbol{\Theta}_{c}=\boldsymbol{\mathrm{I}}$,
for $c=1,\ldots,C$. Furthermore, it holds that

$\bar{P}_{R}^{\textrm{DisC}}\overset{(a)}{\leq}P_{T}\left\|\mathbf{h}_{RI}\right\|^{2}\left\|\mathbf{H}_{IT}\mathbf{w}\right\|^{2}\overset{(b)}{\leq}\bar{P}_{R},$
(55)

where $(a)$ follows by the Cauchy-Schwarz inequality and $(b)$ follows by the
definition of the spectral norm. Note that $(b)$ is an equality if and only if
$\mathbf{w}$ is the dominant right singular vector of $\mathbf{H}_{IT}$.
However, $(a)$ is in general a strict inequality if $\mathbf{w}$ is the
dominant right singular vector of $\mathbf{H}_{IT}$, which thus proves the
necessary condition of the lemma.

On the other hand, we prove the sufficient condition by showing that if
$\mathcal{G}$ is a connected graph, the corresponding BD-RIS is MISO optimal.
This is straightforward to prove because 1) for a connected graph, we can
always remove some edges to make it a tree, i.e. setting the corresponding
off-diagonal entries of $\mathbf{B}$ zero, 2) there exist one and only one
solution for any RIS whose associated graph is a tree to achieve the
performance upper bound (i.e., to be MISO optimal) as shown in Section IV. A.

###  VI-B Proof of Proposition 1

Applying Lemma 1, we need to prove that a connected graph with $N$ vertices
has at least $N-1$ edges. This is achieved by induction. The base case is
easily verified: a connected graph with a single vertex has at least zero
edges. As the induction step, we consider a connected graph with $N$ vertices.
From this graph, we remove edges (at least one) until we obtain a disconnected
graph with two connected components. Assuming the two components have $K$ and
$N-K$ vertices, they have at least $K-1$ and $N-K-1$ edges by the induction
hypothesis, respectively. Since we removed at least one edge to disconnect the
graph, it had originally at least $(K-1)+(N-K-1)+1=N-1$ edges.

###  VI-C Proof of Proposition 2

This proof is conducted by induction. As the base case, we consider the only
tree-connected RIS that can be realized with $N=2$ ports. This RIS includes
two tunable admittance components connecting the two ports to ground and a
further tunable admittance connecting the two ports to each other.

Based on the susceptance matrix $\mathbf{B}\in\mathbb{R}^{2\times 2}$, the
left-hand side of the system (33) is built by setting
$\mathbf{x}=[[\mathbf{B}]_{1,1},[\mathbf{B}]_{2,2},[\mathbf{B}]_{1,2}]^{T}$.
Accordingly, $\mathbf{A}\in\mathbb{R}^{4\times 3}$ is given by (34) with
$\mathbf{A}_{1}\in\mathbb{C}^{2\times 2}$ as in (35) and
$\mathbf{A}_{2}\in\mathbb{C}^{2\times 1}$ given by
$\mathbf{A}_{2}=[[\boldsymbol{\alpha}]_{2},[\boldsymbol{\alpha}]_{1}]^{T}$.
Thus, it is easy to recognize that $\mathbf{A}$ has in general full column
rank, i.e., $r\left(\mathbf{A}\right)=3$. The proposition is hence verified
for the case $N=2$.

As the induction step, we prove that if the proposition is valid for RISs with
$N-1$ ports, it also holds for RISs with $N$ ports. We consider a tree-
connected RIS with $N-1$ elements, whose coefficient matrix is given by

$\mathbf{A}^{(N-1)}=\left[\begin{array}[]{cc}\Re\left\\{\mathbf{A}_{1}^{(N-1)}\right\\}&\Re\left\\{\mathbf{A}_{2}^{(N-1)}\right\\}\\\
\hdashline\Im\left\\{\mathbf{A}_{1}^{(N-1)}\right\\}&\Im\left\\{\mathbf{A}_{2}^{(N-1)}\right\\}\end{array}\right].$
(56)

To this $(N-1)$-port tree-connected RIS, we connect an additional port
creating an $N$-port tree-connected RIS. With no loss of generality, we assume
that the additional port is connected to the $(N-1)$th port through a tunable
admittance. In this way, the resulting $N$-port BD-RIS has the coefficient
matrix

$\mathbf{A}^{(N)}=\left[\begin{array}[]{cc}\Re\left\\{\mathbf{A}_{1}^{(N)}\right\\}&\Re\left\\{\mathbf{A}_{2}^{(N)}\right\\}\\\
\hdashline\Im\left\\{\mathbf{A}_{1}^{(N)}\right\\}&\Im\left\\{\mathbf{A}_{2}^{(N)}\right\\}\end{array}\right],$
(57)

where $\mathbf{A}_{1}^{(N)}\in\mathbb{C}^{N\times N}$ and
$\mathbf{A}_{2}^{(N)}\in\mathbb{C}^{N\times(N-1)}$ are given by

$\mathbf{A}_{1}^{(N)}=\left[\begin{array}[]{cc}\mathbf{A}_{1}^{(N-1)}&\mathbf{0}_{(N-1)\times
1}\\\
\hdashline\mathbf{0}_{1\times(N-1)}&\left[\boldsymbol{\alpha}\right]_{N}\end{array}\right],$
(58)
$\mathbf{A}_{2}^{(N)}=\left[\begin{array}[]{cc}\mathbf{A}_{2}^{(N-1)}&\begin{matrix}\mathbf{0}_{(N-2)\times
1}\\\ \left[\boldsymbol{\alpha}\right]_{N}\end{matrix}\\\
\hdashline\mathbf{0}_{1\times(N-2)}&\left[\boldsymbol{\alpha}\right]_{N-1}\end{array}\right],$
(59)

with $\mathbf{0}_{R\times C}$ denoting an $R\times C$ all-zero matrix. To
prove the induction step, we need to show that
$r(\mathbf{A}^{(N-1)})=2(N-1)-1$ implies $r(\mathbf{A}^{(N)})=2N-1$. To this
end, $\mathbf{A}^{(N)}$ is rewritten as

$\mathbf{A}^{(N)}\sim\left[\begin{array}[]{ccc}\mathbf{A}^{(N-1)}&\mathbf{0}_{(2N-2)\times
1}&\begin{matrix}\mathbf{0}_{(N-2)\times 1}\\\
\Re\left\\{\left[\boldsymbol{\alpha}\right]_{N}\right\\}\\\
\mathbf{0}_{(N-2)\times 1}\\\
\Im\left\\{\left[\boldsymbol{\alpha}\right]_{N}\right\\}\end{matrix}\\\
\hdashline\mathbf{0}_{2\times(2N-3)}&\begin{matrix}\Re\left\\{\left[\boldsymbol{\alpha}\right]_{N}\right\\}\\\
\Im\left\\{\left[\boldsymbol{\alpha}\right]_{N}\right\\}\end{matrix}&\begin{matrix}\Re\left\\{\left[\boldsymbol{\alpha}\right]_{N-1}\right\\}\\\
\Im\left\\{\left[\boldsymbol{\alpha}\right]_{N-1}\right\\}\end{matrix}\end{array}\right],$
(60)

by applying appropriate row and column swapping operations. From (60), we
notice that if $\mathbf{A}^{(N-1)}$ has full column rank and the vectors
$\left[\Re\left\\{\left[\boldsymbol{\alpha}\right]_{N}\right\\},\Im\left\\{\left[\boldsymbol{\alpha}\right]_{N}\right\\}\right]$
and
$\left[\Re\left\\{\left[\boldsymbol{\alpha}\right]_{N-1}\right\\},\Im\left\\{\left[\boldsymbol{\alpha}\right]_{N-1}\right\\}\right]$
are linearly independent, then $\mathbf{A}^{(N)}$ has full column rank. Since
$\left[\Re\left\\{\left[\boldsymbol{\alpha}\right]_{N}\right\\},\Im\left\\{\left[\boldsymbol{\alpha}\right]_{N}\right\\}\right]$
and
$\left[\Re\left\\{\left[\boldsymbol{\alpha}\right]_{N-1}\right\\},\Im\left\\{\left[\boldsymbol{\alpha}\right]_{N-1}\right\\}\right]$
are in practice linearly independent with probability 1, the induction step is
proven and the proof is concluded.

###  VI-D Proof of Proposition 3

To prove that $r\left(\left[\mathbf{A}|\mathbf{b}\right]\right)=2N-1$, we show
that it is always possible to obtain a zero row in
$\left[\mathbf{A}|\mathbf{b}\right]$ by applying appropriate row operations.
Firstly, we execute on $\left[\mathbf{A}|\mathbf{b}\right]$ the $N$ row
operations

$\mathbf{r}_{N+n}=\mathbf{r}_{N+n}-\frac{\Im\left\\{\left[\boldsymbol{\alpha}\right]_{n}\right\\}}{\Re\left\\{\left[\boldsymbol{\alpha}\right]_{n}\right\\}}\mathbf{r}_{n},$
(61)

for $n=1,\ldots,N$, where $\mathbf{r}_{n}$ denotes the $n$th row of
$\left[\mathbf{A}|\mathbf{b}\right]$. The resulting matrix is given by

$\left[\mathbf{A}|\mathbf{b}\right]\sim\left[\begin{array}[]{ccc}\Re\left\\{\mathbf{A}_{1}\right\\}&\Re\left\\{\mathbf{A}_{2}\right\\}&\Re\left\\{\boldsymbol{\beta}\right\\}\\\
\hdashline\mathbf{0}_{N\times
N}&\mathbf{A}^{\prime}&\mathbf{b}^{\prime}\end{array}\right],$ (62)

where we introduced $\mathbf{A}^{\prime}\in\mathbb{R}^{N\times(N-1)}$ and
$\mathbf{b}^{\prime}\in\mathbb{R}^{N\times 1}$. The matrix
$\mathbf{A}^{\prime}$ has exactly two non-zero elements in each column, in the
same positions as the non-zero elements in $\mathbf{A}_{2}$. Specifically,

$\begin{cases}\left[\mathbf{A}^{\prime}\right]_{n_{\ell},\ell}&=\Im\left\\{\left[\boldsymbol{\alpha}\right]_{m_{\ell}}\right\\}-\frac{\Im\left\\{\left[\boldsymbol{\alpha}\right]_{n_{\ell}}\right\\}}{\Re\left\\{\left[\boldsymbol{\alpha}\right]_{n_{\ell}}\right\\}}\Re\left\\{\left[\boldsymbol{\alpha}\right]_{m_{\ell}}\right\\},\\\
\left[\mathbf{A}^{\prime}\right]_{m_{\ell},\ell}&=\Im\left\\{\left[\boldsymbol{\alpha}\right]_{n_{\ell}}\right\\}-\frac{\Im\left\\{\left[\boldsymbol{\alpha}\right]_{m_{\ell}}\right\\}}{\Re\left\\{\left[\boldsymbol{\alpha}\right]_{m_{\ell}}\right\\}}\Re\left\\{\left[\boldsymbol{\alpha}\right]_{n_{\ell}}\right\\},\\\
\left[\mathbf{A}^{\prime}\right]_{p,\ell}&=0,\forall p\neq
m_{\ell},n_{\ell},\end{cases}$ (63)

for $\ell=1,\ldots,N-1$, with $n_{\ell}$ and $m_{\ell}$ being the row indexes
of the two non-zero elements in the $\ell$th column of $\mathbf{A}_{2}$. The
vector $\mathbf{b}^{\prime}$ writes as

$\left[\mathbf{b}^{\prime}\right]_{n}=\Im\left\\{\left[\boldsymbol{\beta}\right]_{n}\right\\}-\frac{\Im\left\\{\left[\boldsymbol{\alpha}\right]_{n}\right\\}}{\Re\left\\{\left[\boldsymbol{\alpha}\right]_{n}\right\\}}\Re\left\\{\left[\boldsymbol{\beta}\right]_{n}\right\\},$
(64)

for $n=1,\ldots,N$. Secondly, we execute on the resulting
$\left[\mathbf{A}|\mathbf{b}\right]$ the $N$ row operations

$\mathbf{r}_{N+n}=\Re\left\\{\left[\boldsymbol{\alpha}\right]_{n}\right\\}\mathbf{r}_{N+n},$
(65)

for $n=1,\ldots,N$, followed by the $N-1$ row operations

$\mathbf{r}_{2N}=\mathbf{r}_{2N}+\mathbf{r}_{N+n},$ (66)

for $n=1,\ldots,N-1$. The resulting matrix is given by

$\left[\mathbf{A}|\mathbf{b}\right]\sim\left[\begin{array}[]{ccc}\Re\left\\{\mathbf{A}_{1}\right\\}&\Re\left\\{\mathbf{A}_{2}\right\\}&\Re\left\\{\boldsymbol{\beta}\right\\}\\\
\hdashline\mathbf{0}_{N\times
N}&\mathbf{A}^{\prime\prime}&\mathbf{b}^{\prime\prime}\end{array}\right],$
(67)

where we introduced $\mathbf{A}^{\prime\prime}\in\mathbb{R}^{N\times N-1}$ and
$\mathbf{b}^{\prime\prime}\in\mathbb{R}^{N\times 1}$.

We now show that (67) has rank $2N-1$ since its $2N$th row is all-zero.
Indeed, we have

$\left[\mathbf{A}^{\prime\prime}\right]_{N,\ell}=\Re\left\\{\left[\boldsymbol{\alpha}\right]_{n_{\ell}}\right\\}\left[\mathbf{A}^{\prime}\right]_{n_{\ell},\ell}+\Re\left\\{\left[\boldsymbol{\alpha}\right]_{m_{\ell}}\right\\}\left[\mathbf{A}^{\prime}\right]_{m_{\ell},\ell}=0$
(68)

for $\ell=1,\ldots,N-1$, with $n_{\ell}$ and $m_{\ell}$ being the row indexes
of the two non-zero elements in the $\ell$th column of $\mathbf{A}_{2}$.
Furthermore, the $N$th entry of vector $\mathbf{b}^{\prime\prime}$ is given by

$\displaystyle\left[\mathbf{b}^{\prime\prime}\right]_{N}$
$\displaystyle=\sum_{n=1}^{N}\Re\left\\{\left[\boldsymbol{\alpha}\right]_{n}\right\\}\left[\mathbf{b}^{\prime}\right]_{n}$
(69)
$\displaystyle=\sum_{n=1}^{N}\Re\left\\{\left[\boldsymbol{\alpha}\right]_{n}\right\\}\Im\left\\{\left[\boldsymbol{\beta}\right]_{n}\right\\}-\Im\left\\{\left[\boldsymbol{\alpha}\right]_{n}\right\\}\Re\left\\{\left[\boldsymbol{\beta}\right]_{n}\right\\},$
(70)

where

$\displaystyle\Re\left\\{\left[\boldsymbol{\alpha}\right]_{n}\right\\}\Im\left\\{\left[\boldsymbol{\beta}\right]_{n}\right\\}-\Im\left\\{\left[\boldsymbol{\alpha}\right]_{n}\right\\}\Re\left\\{\left[\boldsymbol{\beta}\right]_{n}\right\\}$
(71) $\displaystyle=$ $\displaystyle
jZ_{0}\left(\Im\left\\{\left[\hat{\mathbf{h}}_{RI}^{H}\right]_{n}\right\\}^{2}-\Im\left\\{\left[\mathbf{u}_{IT}\right]_{n}\right\\}^{2}\right.$
(72)
$\displaystyle\left.+\Re\left\\{\left[\hat{\mathbf{h}}_{RI}^{H}\right]_{n}\right\\}^{2}-\Re\left\\{\left[\mathbf{u}_{IT}\right]_{n}\right\\}^{2}\right)$
(73) $\displaystyle=$ $\displaystyle
jZ_{0}\left(\left|\left[\hat{\mathbf{h}}_{RI}^{H}\right]_{n}\right|^{2}-\left|\left[\mathbf{u}_{IT}\right]_{n}\right|^{2}\right).$
(74)

Thus, recalling that $\|\hat{\mathbf{h}}_{RI}^{H}\|^{2}=1$ and
$\|\mathbf{u}_{IT}\|^{2}=1$, we have

$\left[\mathbf{b}^{\prime\prime}\right]_{N}=jZ_{0}\left(\left\|\hat{\mathbf{h}}_{RI}^{H}\right\|^{2}-\left\|\mathbf{u}_{IT}\right\|^{2}\right)=0.$
(75)

## References

  * [1] E. Basar, M. Di Renzo, J. De Rosny, M. Debbah, M.-S. Alouini, and R. Zhang, “Wireless Communications Through Reconfigurable Intelligent Surfaces,” _IEEE Access_ , vol. 7, pp. 116 753–116 773, 2019.
  * [2] Q. Wu and R. Zhang, “Towards Smart and Reconfigurable Environment: Intelligent Reflecting Surface Aided Wireless Network,” _IEEE Commun. Mag._ , vol. 58, no. 1, pp. 106–112, 2020.
  * [3] Q. Wu, S. Zhang, B. Zheng, C. You, and R. Zhang, “Intelligent Reflecting Surface-Aided Wireless Communications: A Tutorial,” _IEEE Trans. Commun._ , vol. 69, no. 5, pp. 3313–3351, 2021.
  * [4] S. Shen, B. Clerckx, and R. Murch, “Modeling and Architecture Design of Reconfigurable Intelligent Surfaces Using Scattering Parameter Network Analysis,” _IEEE Trans. Wireless Commun._ , pp. 1–1, 2021.
  * [5] Q. Wu and R. Zhang, “Intelligent reflecting surface enhanced wireless network via joint active and passive beamforming,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 11, pp. 5394–5409, 2019.
  * [6] H. Guo, Y.-C. Liang, J. Chen, and E. G. Larsson, “Weighted sum-rate maximization for reconfigurable intelligent surface aided wireless networks,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 5, pp. 3064–3076, 2020.
  * [7] Y. Liu, J. Zhao, M. Li, and Q. Wu, “Intelligent reflecting surface aided MISO uplink communication network: Feasibility and power minimization for perfect and imperfect CSI,” _IEEE Trans. Commun._ , vol. 69, no. 3, pp. 1975–1989, 2021.
  * [8] C. Pan, H. Ren, K. Wang, W. Xu, M. Elkashlan, A. Nallanathan, and L. Hanzo, “Multicell MIMO communications relying on intelligent reflecting surfaces,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 8, pp. 5218–5233, 2020.
  * [9] H. Li, W. Cai, Y. Liu, M. Li, Q. Liu, and Q. Wu, “Intelligent reflecting surface enhanced wideband MIMO-OFDM communications: From practical model to reflection optimization,” _IEEE Trans. Commun._ , vol. 69, no. 7, pp. 4807–4820, 2021.
  * [10] Y. Xiu, J. Zhao, W. Sun, M. D. Renzo, G. Gui, Z. Zhang, and N. Wei, “Reconfigurable intelligent surfaces aided mmwave NOMA: Joint power allocation, phase shifts, and hybrid beamforming optimization,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 12, pp. 8393–8409, 2021.
  * [11] A. Bansal, K. Singh, B. Clerckx, C.-P. Li, and M.-S. Alouini, “Rate-splitting multiple access for intelligent reflecting surface aided multi-user communications,” _IEEE Trans. Veh. Technol._ , vol. 70, no. 9, pp. 9217–9229, 2021.
  * [12] J. Hu, H. Zhang, B. Di, L. Li, K. Bian, L. Song, Y. Li, Z. Han, and H. V. Poor, “Reconfigurable intelligent surface based RF sensing: Design, optimization, and implementation,” _IEEE J. Sel. Areas Commun._ , vol. 38, no. 11, pp. 2700–2716, 2020.
  * [13] Z. Feng, B. Clerckx, and Y. Zhao, “Waveform and beamforming design for intelligent reflecting surface aided wireless power transfer: Single-user and multi-user solutions,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 7, pp. 5346–5361, 2022.
  * [14] Y. Zhao, B. Clerckx, and Z. Feng, “IRS-aided SWIPT: Joint waveform, active and passive beamforming design under nonlinear harvester model,” _IEEE Trans. Commun._ , vol. 70, no. 2, pp. 1345–1359, 2022.
  * [15] Z. Peng, Z. Chen, C. Pan, G. Zhou, and H. Ren, “Robust transmission design for RIS-aided communications with both transceiver hardware impairments and imperfect CSI,” _IEEE Wireless Commun. Lett._ , vol. 11, no. 3, pp. 528–532, 2022.
  * [16] Y. Chen, Y. Wang, and L. Jiao, “Robust transmission for reconfigurable intelligent surface aided millimeter wave vehicular communications with statistical CSI,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 2, pp. 928–944, 2022.
  * [17] B. Zheng, C. You, and R. Zhang, “Double-IRS assisted multi-user MIMO: Cooperative passive beamforming design,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 7, pp. 4513–4526, 2021.
  * [18] W. Mei and R. Zhang, “Intelligent reflecting surface for multi-path beam routing with active/passive beam splitting and combining,” _IEEE Commun. Lett._ , vol. 26, no. 5, pp. 1165–1169, 2022.
  * [19] Q. Wu and R. Zhang, “Beamforming optimization for intelligent reflecting surface with discrete phase shifts,” in _ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2019, pp. 7830–7833.
  * [20] B. Di, H. Zhang, L. Song, Y. Li, Z. Han, and H. V. Poor, “Hybrid beamforming for reconfigurable intelligent surface based multi-user communications: Achievable rates with limited discrete phase shifts,” _IEEE J. Sel. Areas Commun._ , vol. 38, no. 8, pp. 1809–1822, 2020.
  * [21] L. Dai, B. Wang, M. Wang, X. Yang, J. Tan, S. Bi, S. Xu, F. Yang, Z. Chen, M. D. Renzo, C.-B. Chae, and L. Hanzo, “Reconfigurable intelligent surface-based wireless communications: Antenna design, prototyping, and experimental results,” _IEEE Access_ , vol. 8, pp. 45 913–45 923, 2020\.
  * [22] J. Rao, Y. Zhang, S. Tang, Z. Li, S. Shen, C.-Y. Chiu, and R. Murch, “A novel reconfigurable intelligent surface for wide-angle passive beamforming,” _IEEE Trans. Microw. Theory Tech._ , vol. 70, no. 12, pp. 5427–5439, 2022\.
  * [23] H. Li, S. Shen, M. Nerini, and B. Clerckx, “Reconfigurable intelligent surfaces 2.0: Beyond diagonal phase shift matrices,” _arXiv preprint arXiv:2301.03288_ , 2023.
  * [24] M. Nerini, S. Shen, and B. Clerckx, “Discrete-value group and fully connected architectures for beyond diagonal reconfigurable intelligent surfaces,” _arXiv preprint arXiv:2110.00077_ , 2021.
  * [25] ——, “Optimal group and fully connected design for beyond diagonal reconfigurable intelligent surfaces,” _arXiv preprint arXiv:2211.06117_ , 2022.
  * [26] J. Xu, Y. Liu, X. Mu, and O. A. Dobre, “STAR-RISs: Simultaneous transmitting and reflecting reconfigurable intelligent surfaces,” _IEEE Commun. Lett._ , vol. 25, no. 9, pp. 3134–3138, 2021.
  * [27] H. Zhang, S. Zeng, B. Di, Y. Tan, M. Di Renzo, M. Debbah, Z. Han, H. V. Poor, and L. Song, “Intelligent omni-surfaces for full-dimensional wireless communications: Principles, technology, and implementation,” _IEEE Commun. Mag._ , vol. 60, no. 2, pp. 39–45, 2022.
  * [28] H. Li, S. Shen, and B. Clerckx, “Beyond diagonal reconfigurable intelligent surfaces: From transmitting and reflecting modes to single-, group-, and fully-connected architectures,” _IEEE Trans. Wireless Commun._ , vol. 22, no. 4, pp. 2311–2324, 2023.
  * [29] ——, “Beyond diagonal reconfigurable intelligent surfaces: A multi-sector mode enabling highly directional full-space wireless coverage,” _arXiv preprint arXiv:2209.00301_ , 2022.
  * [30] ——, “Synergizing beyond diagonal reconfigurable intelligent surface and rate-splitting multiple access,” _arXiv preprint arXiv:2303.06912_ , 2023\.
  * [31] ——, “A dynamic grouping strategy for beyond diagonal reconfigurable intelligent surfaces with hybrid transmitting and reflecting mode,” _arXiv preprint arXiv:2210.02499_ , 2022.
  * [32] Q. Li, M. El-Hajjar, I. Hemadeh, A. Shojaeifard, A. A. M. Mourad, B. Clerckx, and L. Hanzo, “Reconfigurable intelligent surfaces relying on non-diagonal phase shift matrices,” _IEEE Trans. Veh. Technol._ , vol. 71, no. 6, pp. 6367–6383, 2022.
  * [33] D. M. Pozar, _Microwave engineering_. John wiley & sons, 2011.
  * [34] S. Shen and R. D. Murch, “Impedance Matching for Compact Multiple Antenna Systems in Random RF Fields,” _IEEE Trans. Antennas Propag._ , vol. 64, no. 2, pp. 820–825, 2016.
  * [35] J. A. Bondy and U. S. R. Murty, _Graph theory with applications_. Macmillan London, 1976, vol. 290.
  * [36] D. O’Leary and G. Stewart, “Computing the eigenvalues and eigenvectors of symmetric arrowhead matrices,” _J. Comput. Phys._ , vol. 90, no. 2, pp. 497–505, 1990.
  * [37] Z. H. Shaik, E. Björnson, and E. G. Larsson, “MMSE-optimal sequential processing for cell-free massive MIMO with radio stripes,” _IEEE Trans. Commun._ , vol. 69, no. 11, pp. 7775–7789, 2021.
  * [38] G. Strang, _Introduction to linear algebra_. Wellesley-Cambridge Press Wellesley, MA, 1993, vol. 3.