# Laplacian Controllability and Observability of Multi-Agent Systems: Recent Advances in Tree Graphs
## 4 Zero-Nonzero Pattern of Eigenvectors Associated to \(\lambda=1\)
If \(r\) denotes the number of branches whose reduction satisfies \((\mathbf{v})_{c}=0\), (\(2\leq r\leq s\)), then \(\lambda\) has multiplicity \(m_{g}(\lambda)=r-1\). 2. After reducing the graph, the core is made of branches all of length \(k\) but only one of length \(k-1\). In this case, \(v_{c}\
eq 0\) and \(m_{g}(\lambda)=1\). However, eigenvectors related to Condition (R2) can be found only if \(k\leq\min\left\{a_{1},a_{2},\ldots,a_{s}\right\}\), so that its search is limited to the length of the smallest branch; conversely,eigenvectors as in (R2) can be found until there are two possible branches, and its search must be performed up to the largest-but-one branch. In this latter case, ordering the branches such that \(a_{i}\leq a_{i+1}\) for \(i=1,\ldots,s\), when \(a_{i}\leq k\leq a_{i+1}\), then the eigenvector components relative to the branches \(a_{1},\ldots,a_{s}\) are necessarily zero. This allows us to state a generalization of Algorithm 1 to any \(k\). In the following, we state Algorithm 2 that allows us to get the \(\mathcal{V}^{N_{k}}\) for \(k\leq a_{1}\), \(a_{1}\) being the shortest branch, and then we provide Algorithm 3, which is the adaption of Algorithm 1 for the remaining branches for \(a_{1}\leq k\leq a_{s-1}\). Figure 8: External and internal branches associated to \(N_{k}\). They are the basic elements of the proposed graph reduction technique in case of \(\lambda\in\Lambda(N_{k})\). Grey nodes are related to nonzero eigenvector components, double-circled white nodes are associated to zero eigenvector components. Figure 6: Example of extension of Cases R1 (**a**) and R2 (**b**) for eigenvalues of \(N_{2}\), with\(\lambda_{N_{2}}=\frac{3\pm\sqrt{5}}{2}\). Figure 4:0 External and internal branches associated to \(N_{2}\). They constitute the basic elements of the proposed graph reduction technique in case of \(\lambda\in\Lambda(N_{2})\). Grey nodes are related to nonzero eigenvector components, double-circled white nodes are associated to zero eigenvector components. When \(a_{1}\leq k\leq a_{s-1}\), only one case is possible, and the algorithm is simplified as follows. ```
1:Input: \(\mathcal{S}(a_{1},a_{2},\ldots,a_{s})\). 2:Output: \(\mathcal{V}_{c}^{N_{k}}\), set of control/observation nodes to achieve controllability of \(\lambda\in\Lambda_{N_{k}}\), \(a_{1}<k\leq a_{s-1}\). 3:Input: \(\mathcal{S}(a_{1},a_{2},\ldots,a_{s})\). 4:Output: \(\mathcal{V}_{c}^{N_{k}}\), set of control/observation nodes to achieve controllability of any \(\lambda\in\Lambda_{N_{k}}\) (\(a_{1}\leq k\leq a_{s-1}\)). 5:BEGIN: First stage (reduction to the core graph):
6:for\(i=1,\ldots,s\)do:
7: Reduce branch \(i\) to its core, as depicted in Figure 4:1
8: Record the associated zero-nonzero pattern of each branch \(i\) (as in the bottom of Figure 3), and store in the set \(\mathcal{V}_{N_{k}}^{i}\) those with nonzero values. 9:endfor
10:Let \(\mathcal{S}_{0}^{i}\) be the remaining reduced graph, equivalently called the _core_ graph. 11:Second stage (analysis of the core graph):
12:If\(\mathcal{S}_{0}\) falls in the case (R1), then:
13:order the branches so that the first \(r\) reductions satisfy \(\left(\mathbf{v}\right)_{c}=0\)
14:if\(r=1\), then:
15:the eigenvalue \(\lambda\in\Lambda_{N_{k}}\) is NOT a Laplacian eigenvalue
16:elseif\(r\geq 2\), then:
17:\(\lambda\in\Lambda_{N_{k}}\) is a Laplacian eigenvalue of \(\mathcal{S}(a_{1},a_{2},\ldots,a_{s})\) of multiplicity \(r-1\). 18:Build set \(\mathcal{V}_{c}^{N_{k}}\) adding one node for each \(\mathcal{V}_{N_{k}}^{i}\) but one, arbitrarily;
19:endif
20:elseif\(\mathcal{S}_{0}\) satisfies case (R2) then:
21:\(\mathcal{V}_{c}^{N_{k}}\) is made of only one node, to be chosen among \(\mathcal{V}_{N_{k}}^{i}\),
22:else
23:\(\lambda\in\Lambda_{N_{k}}\) is not an eigenvalue of the Laplacian of \(\mathcal{S}(a_{1},a_{2},\ldots,a_{s})\). 24:endif
```  
**Algorithm 2** Node selection for controllability and observability.