# Laplacian Controllability and Observability of Multi-Agent Systems: Recent Advances in Tree Graphs
## 4 Zero-Nonzero Pattern of Eigenvectors Associated to \(\lambda=1\)
As for Figure 5b, it matches Condition \((R1)\) with \(r=3\), so that \(m_{g}(1)=2\). The two branches with white nodes satisfy the eigenvalue equation for zero node values only. _Node Selection for Reachability and Observability of \(\lambda=1\)_  
Considering all the above analysis and results, and specifically the eigenspace dimension and zero/nonzero structure, it is now easy to deduce the node selection rule to achieve reachability and observability in the case of \(\lambda=1\). For the above reason, the following procedure is more suited in the case of complex graphs, with hundreds or more nodes. In the following procedure, we denote the eigenvector of \(\lambda=1\) by the symbol \(\mathbf{v}_{1}\) (in general, \(\mathbf{v}_{\lambda}\) denotes the eigenvector associated to \(\lambda\)). Figure 5: Example of starlike graphs whose reduction leads to a core that falls into, respectively, Cases R1 (**a**) and R2 (**b**). In the next Section, stemming from the experience on \(\lambda=1\), we easily develop an algorithm for a general \(\lambda\) and we derive an overall algorithm with Algorithm 1 as one of its blocks. ```
1:Input: \(\mathcal{S}(a_{1},a_{2},\ldots,a_{s})\). 2:Output: \(\mathcal{V}_{c}^{1}\), set of control/observation nodes to achieve controllability of \(\lambda=1\). BEGIN: First stage (reduction to the core graph):
3:for\(i=1,\ldots,s\)do:
4: Reduce branch \(i\) to its core, as depicted in Figure 3.
5: 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_{1}}^{i}\) those with nonzero values. 6:endfor
7: Let \(\mathcal{S}_{0}^{\lambda}\) be the remaining reduced graph, equivalently called the _core_ graph. 8:Second stage (analysis of the core graph):
9:If\(\mathcal{S}_{0}\) falls in the case (R1), then:
10: order the branches so that the first \(r\) reductions satisfy \(\left(\mathbf{v}\right)_{c}=0\)
11:if\(r=1\), then:
12: the eigenvalue \(\lambda\in\Lambda_{N_{1}}\) is NOT a Laplacian eigenvalue
13:elseif\(r\geq 2\), then:
14:\(\lambda\in\Lambda_{N_{1}}\) is a Laplacian eigenvalue of \(\mathcal{S}(a_{1},a_{2},\ldots,a_{s})\) of multiplicity \(r-1\). 15: Build set \(\mathcal{V}_{c}^{N_{1}}\) adding one node for each \(\mathcal{V}_{N_{1}}^{i}\) but one, arbitrarily;
16:endif
17:elseif\(\mathcal{S}_{0}\) satisfies case (R2) then:
18:\(\mathcal{V}_{c}^{N_{1}}\) is made of only one node, to be chosen among \(\mathcal{V}_{N_{1}}^{i}\),
19:else
20:\(\lambda=1\) is not an eigenvalue of the Laplacian of \(\mathcal{S}(a_{1},a_{2},\ldots,a_{s})\)
21:endif
```  
**Algorithm 1** Node selection for controllability and observability. Case \(\lambda=1\). 5 Zero-Nonzero Pattern of Eigenvectors Associated to Any \(\boldsymbol{\lambda}\) of \(N_{k}\)  
Interestingly, the above conditions on \(\lambda=1\) can be extended in the general case of any \(\lambda\in\Lambda_{N_{k}}\). We start this generalization by an example regarding \(N_{2}\); then, we describe the general procedure that extends conditions (R1)-(R2) to the general case of \(\lambda\) of \(N_{k}\). Consider the two graphs depicted in Figure 6. They represent the generalization to \(N_{2}\) of the two graphs discussed in Figure 5, and they are related, respectively, to Conditions (R1) and (R2) for \(\lambda\in\Lambda_{N_{2}}\), namely \(\lambda_{N_{2}}=\frac{3\pm\sqrt{5}}{2}\). They are obtained by replacing the branches characterizing \(N_{1}\) (see Figure 3) with those of \(N_{2}\) (Figure 7) and by adding one neighbor node to each branch around the central node \(v_{c}\). Starting from the above consideration, we are now ready to generalize rules (R1)-(R2) as follows. We let \(\lambda\in\Lambda_{N_{k}},k\leq a_{i}\). As a first step, we reduce the graph to the core based on the basic elements depicted in Figure 8. Then, \(\lambda\in\Lambda_{N_{k}}\) is an eigenvalue of the considered starlike graph if one of the following two conditions hold:  
1. The reduction related to \(N_{k}\) of at least two branches provides \((\mathbf{v})_{c}=0\).