# Laplacian Controllability and Observability of Multi-Agent Systems: Recent Advances in Tree Graphs
## 2 Problem Setting and Preliminary Results
\begin{table}
\begin{tabular}{c} \hline \hline
**Basic Notation** \\ \hline \(\mathbb{N}\), \(\mathbb{R}\), \(\mathbb{R}_{\geq 0}\), \(\mathbb{R}_{+}\) denote the natural, real, non-negative real numbers, and positive real numbers, respectively. \\ Vectors are denoted in bold letters. \(\mathbf{0}_{d}\) and \(\mathbf{1}_{d}\), \(d\in\mathbb{N}\), denote, respectively, the vector of dimension \(d\) with components, respectively, all equal to \(0\) or to \(1\), and \(0_{d_{1}\times d_{2}}\), \(d_{1},d_{2}\in\mathbb{N}\), the matrix with \(d_{1}\) rows and \(d_{2}\) columns with zero entries. \\ \end{tabular} For \(i\in\mathbb{N}\), \(\mathbf{e}_{i}\) is the \(i\)th element of the canonical basis, e.g., \(\mathbf{e}_{1}=\begin{bmatrix}1&0&\ldots&0\end{bmatrix}^{\top}\). For vector \(\mathbf{v}\in\mathbb{R}^{d}\), we denote \((\mathbf{v})_{i}\) the \(i\)th component of \(\mathbf{v}\) so that \(\mathbf{v}=[(\mathbf{v})_{1}\,\ldots\,(\mathbf{v})_{d}]^{\top}\). \\ \hline \hline
**Spectral Theory** \\ \hline We let \(A\in\mathbb{R}^{n\times n}\), be the polynomial \(p_{A}(s):=\det(sI_{n}-A)\) is the characteristic polynomial. \\ \(\Lambda(A)\) denotes the **spectrum** of \(A\), namely the set of eigenvalues of \(A\). \\ For an eigenvalue \(\lambda\), the **algebraic multiplicity**\(m_{a}(\lambda)\) of \(\lambda\) is its multiplicity as zero of \(p_{A}(s)\), the **geometric multiplicity**\(m_{g}(\lambda)\) is defined as \(m_{g}(\lambda)=\dim[\ker(A-\lambda I_{n})]\). \\ The linear subspace of \(\mathbb{R}^{n}\) given by \(\ker(A-\lambda I_{n})\) is called **eigenspace** associated to \(\lambda\) and it is denoted by \(\mathcal{V}_{\lambda}=\ker(A-\lambda I_{n})\). \\ In general, it holds that \(1\leq m_{g}(\lambda)\leq m_{a}(\lambda)\); if \(m_{a}(\lambda)=1\); then, \(\lambda\) is called **simple** \\ **eigenvalue** of \(A\), while if \(m_{g}(\lambda)=m_{a}(\lambda)\) for a \(\lambda\in\mathbb{C}\) such that \(m_{a}(\lambda)>1\), then \(\lambda\) is called **semi-simple**[30]. \\ \hline \hline
**Basic Graph Theory** \\ \hline A **graph**\(\mathcal{G}\) is a pair \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) with \(\mathcal{V}=\{1,2,\ldots,n\}\) and \(\mathcal{E}\subset\mathcal{V}\times\mathcal{V}\). \\ The **neighbors set** of a node \(i\in\mathcal{V}\) is \(\mathcal{N}_{i}=\{j\in\mathcal{V}|(i,j)\in\mathcal{E}\}\). \\ The **degree** of a node \(i\in\mathcal{V}\)\(d(i)\) is the number of incident edges, so that \(d(i)=\sum_{j\in\mathcal{N}_{i}}1\). \\ A node \(i\in\mathcal{V}\) is called a **pendant node** or a **leaf node** if it holds \(d(i)=1\). \\ A graph \(\mathcal{T}\) with no cycles is a **tree** if it is connected, otherwise it is called **forest**. A **path**\(\mathcal{P}_{n}\) is a graph with \(\mathcal{V}=\{1,\ldots,n\}\) nodes and \(\mathcal{E}=\{(i,i+1),i=1,\ldots,n-1\}\). \\ A **star graph**\(\mathcal{S}\) is a graph with one node connected to all the others, and all the others are pendant nodes. A **starlike tree graph**, denoted by \(\mathcal{S}(a_{1},\ldots,a_{s})\), is a tree graph having \(|\mathcal{V}|=\sum_{i=1}^{s}a_{i}+1\) nodes with only one node, say node 1, with \(d(1)>2\), and \(\mathcal{S}(a_{1},\ldots,a_{s})-\{1\}=\mathcal{P}_{a_{1}}\cup\mathcal{P}_{a_{2}} \cup\cdots\cup\mathcal{P}_{a_{s}}\). \\ Parameters \(a_{1}\),..., \(a_{s}\) determine the starlike tree graph up to isomorphism. We say that the starlike tree \(\mathcal{S}(a_{1},\ldots,a_{s})\) has \(s\)**branches**, the lengths of which are \(a_{1}\),..., \(a_{s}\). \\ \hline \hline \end{tabular}  
* We let \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) be a graph; the associated **adjacency matrix**\(A_{\mathcal{G}}\in\mathbb{R}^{n\times n}\) is \([A]_{ij}=1\) if \((i,j)\in\mathcal{E}\) and \([A]_{ij}=0\) if \((i,j)\
otin\mathcal{E}\), and the corresponding **Laplacian matrix** is \([L_{\mathcal{G}}]_{ij}=-[A_{\mathcal{G}}]_{ij}\) if \(i\
eq j\) and \([L_{\mathcal{G}}]_{ii}=\sum_{j=1,i\
eq j}^{n}[A_{\mathcal{G}}]_{ji}\). If the graph \(\mathcal{G}\) is clear from the context, then the subindex \(\mathcal{G}\) is omitted.
* By construction, the Laplacian is a symmetric positive semidefinite matrix and it has zero row sum, so that it holds that \(L_{\mathcal{G}}\mathbf{1}=\mathbf{0}\) for any \(\mathcal{G}\), and hence the polynomial \(p_{L}(s)=\det[sI-L_{\mathcal{G}}]\) can be written as \(p_{L}(s)=s(s-\lambda_{2})(s-\lambda_{3})\ldots(s-\lambda_{n})\) where \(\lambda_{i}\in\mathbb{R}_{\geq 0}\); we choose the numbering such that \(\lambda_{i}\geq\lambda_{i-1}\) and, if \(\mathcal{G}\) is connected, \(\lambda_{i}\
eq 0\) for any \(i=2,\ldots,n\).  
\end{table}