Source-linked AI summary
On the reachability and observability of path and cycle graphs
Gianfranco Parlangeli, Giuseppe Notarstefano
TL;DR
The paper asks whether all node configurations can be reached by controlling limited nodes and whether the entire network state can be reconstructed from partial observations. It characterizes reachability and observability for path and cycle graphs using algebraic rules from number theory, showing that a path has these properties from any single node exactly when its size is a power of two.
Problem
The paper investigates whether all node configurations can be reached by controlling a limited number of nodes and whether the entire network state can be reconstructed from partial observations.
Method
The paper provides necessary and sufficient reachability and observability conditions using simple algebraic rules from number theory, combined with the PBH lemma and state-matrix symmetry.
Results
A path graph is reachable and observable from any single node if and only if its number of nodes is a power of two, n = 2^i.
Takeaways & Limitations
The paper characterizes all unreachable and unobservable node sets and provides routines for selecting control or observation nodes that guarantee reachability or observability.
Abstract
from arXiv · showhide
In this paper we investigate the reachability and observability properties of a network system, running a Laplacian based average consensus algorithm, when the communication graph is a path or a cycle. More in detail, we provide necessary and sufficient conditions, based on simple algebraic rules from number theory, to characterize all and only the nodes from which the network system is reachable (respectively observable). Interesting immediate corollaries of our results are: (i) a path graph is reachable (observable) from any single node if and only if the number of nodes of the graph is a power of two, $n=2^i, i\in \natural$, and (ii) a cycle is reachable (observable) from any pair of nodes if and only if $n$ is a prime number. For any set of control (observation) nodes, we provide a closed form expression for the (unreachable) unobservable eigenvalues and for the eigenvectors of the (unreachable) unobservable subsystem.
I. INTRODUCTION
The paper studies reachability and observability in Laplacian-based average-consensus networks with path or cycle communication graphs. It derives number-theoretic characterizations of reachable and observable nodes, together with spectral descriptions of unreachable and unobservable subsystems.
- Motivation and problem: The study considers whether limited control or observation nodes can reach every network configuration or reconstruct the entire network state.The system is first-order, uses a Laplacian-based average-consensus algorithm, and has fixed path or cycle topology.
- Main contribution: Reachability and observability are characterized completely using necessary and sufficient conditions based on simple algebraic relations from number theory.The rules use node labels and the total number of graph nodes to identify reachable or observable nodes and construct suitable control or observation sets.
- Path-graph results: A path graph is reachable and observable from any single node if and only if its size is a power of two, n = 2^i.The paper also gives a further single-node criterion involving the absence of a specified odd-prime factor relation.
- Cycle-graph results: A cycle graph is reachable and observable from any pair of nodes if and only if n is prime.For specified nodes i1 and i2, the condition is that i2 − i1 and n + i1 − i2 are coprime.
- Spectral characterization: For any unreachable or unobservable node set, the paper gives closed-form eigenvalues and eigenvectors and characterizes the corresponding orthogonal complement.These results rely on complete spectral characterizations of suitable path and cycle Laplacian submatrices and also yield a closed form for path-graph Laplacian eigenvalues.
II. PRELIMINARIES AND PROBLEM SET-UP
This section introduces graph-theoretic terminology, the network model, and the reachability and observability problems used to establish the paper’s main results.
- The section presents preliminary graph theory and standard linear-systems results needed for the analysis.
A. Preliminaries on graph theory
The paper defines undirected graphs through nodes, edges, neighborhoods, degrees, adjacency matrices, and Laplacians, then specializes to paths and cycles.
- An undirected graph G=(I,E) consists of nodes I and edges E, with N_i denoting the neighbors of node i.
- The maximum degree is Δ=max_i∈I d_i, and the degree matrix D is diagonal with entries [D]_ii=d_i.
- The adjacency matrix A represents graph connections, while the Laplacian is defined as L=D−A.
- The Laplacian is symmetric positive semidefinite and has as many zero eigenvalues as the graph has connected components.
- For a connected graph, the eigenvector associated with eigenvalue 0 is the all-ones vector.
- A path has two degree-one external nodes and internal degree-two nodes, whereas every cycle node has degree two.
B. Network of agents running average consensus
The network consists of agents communicating over a time-invariant undirected graph and applying Laplacian-based average consensus in continuous or discrete time.
- The agents communicate over a time-invariant undirected graph, so communication between any two agents is bidirectional.
- Each agent runs a consensus algorithm based on a Laplacian control law, with continuous-time dynamics represented compactly using the state vector and graph Laplacian.
- For ε∈(0,1/Δ), P=I−εL is a nonnegative, doubly stochastic, stable matrix for the discrete-time system.
- The continuous- and discrete-time systems have the same reachability and observability properties, including unreachable and unobservable eigenvalues and eigenvectors.
C. Network reachability and observability
The section formulates reachability through externally controlled nodes and observability through nodes whose states are measured, exploiting Laplacian symmetry to establish duality.
- Reachability concerns whether external inputs applied at selected control nodes can affect the network system.
- Control nodes, also called leader or pinned nodes, are modeled by an input vector u(t) and matrix B formed from their corresponding basis vectors.
- Observability concerns reconstructing the entire network state from measurements collected at selected observation nodes.
- For observation nodes I_o, the output consists of their states, with output matrix C=[e_i1|...|e_im]^T.
- Because the Laplacian is symmetric, reachability from a node subset is equivalent to observability from that same subset.
- This duality supports regulator designs that estimate the entire network state and control it toward a desired configuration.
D. Standard results on reachability and observability of linear systems
Reachability and observability are formulated through reachable and unobservable subspaces, rank conditions, and the PBH lemma. For symmetric state matrices, these properties can be characterized using eigenvectors orthogonal to the input or output nodes.
- Definitions: Reachability concerns states reachable in finite time from the origin, while observability concerns initial states producing identically zero output.The reachable subspace is the image of the reachability matrix, and the unobservable subspace is the kernel of the observability matrix.
- Matrix criteria: The two problems are equivalent to studying the ranks of the reachability and observability matrices.
- PBH criterion: The PBH lemma characterizes reachability and observability through rank conditions involving the system matrices for every eigenvalue λ.
- Symmetric systems: For symmetric state matrices, the orthogonal complement of the reachable subspace is spanned by eigenvectors annihilated by the transpose of the input matrix.
- Symmetric systems: The unobservable subspace is similarly spanned by eigenvectors annihilated by the output matrix, defining the paper’s unreachable and unobservable eigenvalues and eigenvectors.
III. SPECTRAL PROPERTIES OF THE LAPLACIAN OF A PATH AND RELATED SUBMATRICES
The section derives spectral properties of path Laplacians and related submatrices, then uses their structure to obtain closed-form eigenvalues and eigenvectors. These results support later reachability and observability characterizations.
- Spectral characterization: The section provides closed-form expressions for eigenvalues and eigenvectors of path-Laplacian-related matrices.
- Matrix structure: A path Laplacian can be partitioned into suitable submatrices, with cycle Laplacians yielding submatrices of type M_μ under the stated node labeling.
- Boundary components: Every eigenvector of N_μ, M_μ, and L_μ has nonzero first and last components.
- Related submatrices: The eigenvalues of N_ν are eigenvalues of M_2ν, with corresponding eigenvectors obtained through the stated symmetry relation.
- Path spectrum: The eigenvalues of M_μ are obtained from the path adjacency spectrum by adding 2, while the eigenvectors remain unchanged.
- Characteristic polynomials: The characteristic polynomials of N_μ and M_μ are derived by Laplace expansion, providing the tools for computing path-Laplacian eigenvalues.
IV. REACHABILITY AND OBSERVABILITY OF PATH AND CYCLE GRAPHS
The paper completely characterizes reachability and observability for path and cycle graphs.
- Reachability and observability of path and cycle graphs are completely characterized.
A. Reachability and observability of path graphs
Path-graph reachability and observability are characterized through common eigenvalues of Laplacian submatrices and algebraic rules based on the prime factors of the graph size. The results also identify unreachable eigenvalues and eigenvectors for node sets.
- Single-node characterization: A path is reachable and observable from either external node.
- Single-node characterization: For a single interior node, path reachability and observability fail exactly when the corresponding left and right submatrices share an eigenvalue.
- Odd-sized paths: If n is odd, the path is not reachable or observable from its central node, which has (n −1)/2 unreachable and unobservable eigenvalues.
- Multiple nodes: For a control or observation set, reachability and observability hold if and only if the intervening N and M submatrices have no common eigenvalues.
- Number-theoretic characterization: A path is not completely reachable or observable from an interior node when an odd prime dividing n satisfies the theorem’s node congruence condition.
- Number-theoretic characterization: For each odd prime factor, the theorem identifies node sets with shared unreachable or unobservable eigenvalues and gives corresponding eigenvector forms.
B. Reachability and observability of cycle graphs
The paper gives number-theoretic conditions characterizing reachability and observability of cycle graphs from selected nodes. It also identifies unreachable eigenvalues and corresponding eigenvectors, with simple node-selection consequences.
- Single-node control and observation: A cycle graph is not completely reachable or observable from any single node.This follows from the cycle Laplacian's repeated eigenvalues and the PBH lemma.
- Characterization by node spacing: A node set is reachable or observable exactly when the associated distance matrices satisfy the theorem's common-eigenvalue condition.For nodes {i1, ..., im}, the relevant matrices are formed from successive cyclic distances.
- Characterization by node spacing: Reachability and observability depend on the relative distances between consecutive control or observation nodes.The cycle's symmetry makes these properties functions of node spacing rather than absolute labels.
- Prime-factor structure: For each prime factor p of n, specific p-node sets are unreachable or unobservable, with the corresponding eigenvalues and eigenvectors determined by M_(p−1).For larger node sets, products of distinct prime factors determine the unreachable eigenvalues and the spanning eigenvectors of the unreachable or unobservable subspace.
- Node-selection corollaries: Two adjacent nodes always provide reachability and observability for any cycle length, whereas every pair does so if and only if n is prime.The graphical procedure encodes these conditions through node symbols: selecting nodes with no symbols in common yields a reachable and observable set.
V. CONCLUSIONS
The paper characterizes reachability and observability of path and cycle graphs using simple algebraic rules from number theory. It identifies unreachable and unobservable node sets and supplies routines for selecting nodes that guarantee these properties, while proposing extensions to more complex graphs.
- Conclusions: The paper characterizes reachability and observability of path and cycle graphs through simple algebraic rules from number theory.The characterization identifies the relevant reachable and observable structures rather than treating node selection empirically.
- Conclusions: The results identify all and only the unreachable or unobservable sets of nodes.This provides an exact description of which control or observation-node selections fail to provide the desired property.
- Conclusions: The paper provides simple routines for selecting control or observation nodes that guarantee reachability or observability.These routines turn the characterization into a node-selection procedure.
- Conclusions: Future research includes extending the proposed methodologies to more complex graphs built from paths and cycles, such as grids and tori.The paper presents this extension as a promising avenue rather than a completed result.
B. Circulant matrices and eigenstructure of the Laplacian of a cycle graph
The cycle Laplacian is treated as a circulant matrix, whose eigenstructure follows from its first column and cyclic symmetry. Its eigenvalues have a zero mode and paired values except for the simple exceptional cases.
- Circulant matrices: A circulant matrix is fully specified by its first column, with remaining columns obtained by cyclic permutation.Its eigenvalues can be expressed in terms of the first-column coefficients.
- Cycle Laplacian: The cycle-graph Laplacian is the circulant matrix with c0 = 2, c1 = c_(n−1) = −1, and all other coefficients zero.This coefficient pattern represents the cycle's self-degree and two neighboring connections.
- Cycle Laplacian: The cycle Laplacian has eigenvalues λ0 = 0 and paired eigenvalues satisfying λj = λ_(n−j).The zero eigenvalue and the opposite-index pairing summarize the cycle's spectral symmetry.