PaperlayerView exact revision on arXiv

Source-linked AI summary

Controllability and observability of grid graphs via reduction and symmetries

Giuseppe Notarstefano, Gianfranco Parlangeli

arXiv:1203.0129v1math.OC

TL;DR

The paper asks how controllability and observability can be characterized for linear systems induced by grid-graph Laplacians, a problem arising in network control, quantum computation, and PDE discretization. It analyzes grid eigenvectors through graph decompositions and symmetries, then derives necessary and sufficient node-level criteria and routines for selecting control or observation nodes.

  • Problem

    The paper addresses controllability and observability of Laplacian-induced linear systems on grid graphs, including the broader problem of choosing control nodes beyond special cases.

  • Method

    The authors characterize grid Laplacian eigenvectors using brick decompositions, symmetries, and polynomial evaluations, then analyze zero components for selected nodes.

  • Results

    The paper provides necessary and sufficient criteria identifying all and only uncontrollable or unobservable node sets for grid-induced systems.

  • Takeaways & Limitations

    The resulting routines identify suitable control or observation nodes and reduce the complexity of grid controllability and observability analysis.

Abstract

from arXiv · show

In this paper we investigate the controllability and observability properties of a family of linear dynamical systems, whose structure is induced by the Laplacian of a grid graph. This analysis is motivated by several applications in network control and estimation, quantum computation and discretization of partial differential equations. Specifically, we characterize the structure of the grid eigenvectors by means of suitable decompositions of the graph. For each eigenvalue, based on its multiplicity and on suitable symmetries of the corresponding eigenvectors, we provide necessary and sufficient conditions to characterize all and only the nodes from which the induced dynamical system is controllable (observable). We discuss the proposed criteria and show, through suitable examples, how such criteria reduce the complexity of the controllability (respectively observability) analysis of the grid.

I. INTRODUCTION

The paper studies Laplacian-induced linear systems on grid graphs, motivated by network control, quantum computation, and discretized partial differential equations. It characterizes eigenvector structure and derives graph-based criteria for controllability and observability.

  • I. INTRODUCTION: The paper studies linear time-invariant systems whose state matrix is induced by the Laplacian of a d-dimensional grid graph.Grid topologies arise in several application scenarios.
  • I. INTRODUCTION: The framework is motivated by applications in distributed control, quantum computation, and discretized partial differential equations.The paper connects the same graph-induced dynamics to multiple application areas.
  • I. INTRODUCTION: The authors characterize grid Laplacian eigenvectors using prime factorizations, brick decompositions, and symmetry operations across grid axes.Eigenvalues of elementary bricks also appear in the main grid, with corresponding eigenvectors composed through suitable flips.
  • I. INTRODUCTION: Necessary and sufficient conditions identify all and only the uncontrollable and unobservable nodes through zero eigenvector components, symmetries, and polynomial evaluations.The criteria support analysis of eigenvalue multiplicity and eigenvector structure.
  • I. INTRODUCTION: The resulting routines identify controllable or observable nodes, test a given node set, and construct control or observation sets.These procedures use node labels, eigenvector symmetries, and polynomial evaluations.

II. PROBLEM SET-UP AND MOTIVATIONS

The paper models grid-induced dynamics using Cartesian products of paths and the Laplacian of an undirected graph. This setup defines the graph structure, node labeling, and Laplacian properties used later in controllability and observability analysis.

  • II. PROBLEM SET-UP AND MOTIVATIONS: The graph Laplacian is L = D−A, where D is the degree matrix and A is the adjacency matrix.For a connected graph, the zero eigenvalue has eigenvector 1 = [1 ... 1]^T.
  • II. PROBLEM SET-UP AND MOTIVATIONS: The Cartesian product combines vertex pairs and connects them when one coordinate is adjacent while the other is equal.The product operation is commutative and associative.
  • II. PROBLEM SET-UP AND MOTIVATIONS: Paths consist of two degree-one external nodes and internal nodes connected by consecutive edges.The external nodes are labeled 1 and n.
  • II. PROBLEM SET-UP AND MOTIVATIONS: A d-dimensional grid graph is the Cartesian product of d paths, possibly with different lengths.Grid node degrees range from d to 2d, with corner nodes obtained from products of external path nodes.
  • II. PROBLEM SET-UP AND MOTIVATIONS: The setup introduces node coordinates and identifies individual components of a grid Laplacian eigenvector by their grid positions.A node is represented by one position per path dimension.

B. Controllability and observability of graph induced systems: problem set-up and analysis tools

The paper formulates controllability and observability for systems induced by a grid Laplacian and uses symmetry of the state matrix to reduce both analyses to eigenvector components that vanish at selected nodes.

  • B. Controllability and observability of graph induced systems: problem set-up and analysis tools: The system uses the grid Laplacian as its state matrix, with inputs applied directly to selected control nodes and outputs taken from selected observation nodes.The input and output matrices are formed from corresponding standard basis vectors.
  • B. Controllability and observability of graph induced systems: problem set-up and analysis tools: For symmetric state matrices, observability is dual to controllability, so both properties can be analyzed with the same tools.The relevant dual pairs are (L, C) and (L^T, B^T).
  • B. Controllability and observability of graph induced systems: problem set-up and analysis tools: The PBH-based characterization reduces uncontrollability or unobservability to Laplacian eigenvectors having zero components at all selected control or observation nodes.Such eigenvalues and eigenvectors are designated uncontrollable or unobservable.
  • B. Controllability and observability of graph induced systems: problem set-up and analysis tools: The same first-order analysis applies to higher-order integrator systems of the form x^(k)(t) = αLx(t) + Bu(t).The equivalence follows from the block structure of the higher-order system.

C. Motivating applications

The paper connects grid-Laplacian systems to consensus networks, quantum walks, and discretized partial differential equations. In each setting, the resulting dynamics can be studied using the paper’s controllability and observability tools.

  • C. Motivating applications: Grid-Laplacian dynamics model systems arising in network consensus, continuous-time quantum walks, and discretized partial differential equations.These are presented as three main application areas.
  • C. Motivating applications: In consensus networks, selected nodes can receive additional inputs that fully control their dynamics, forming a leader-follower model.Observation nodes read selected node states or reconstruct the network state from their own states.
  • C. Motivating applications: For quantum walks on grids, the Hamiltonian can use the grid Laplacian, linking the resulting dynamics to the paper’s linear-system analysis.Prior work relates controllability of the quantum system to controllability of the corresponding linear system.
  • C. Motivating applications: The Laplace operator appears in diffusion, wave propagation, fluid dynamics, acoustics, electromagnetism, and quantum mechanics.The paper uses these physical examples to motivate the discretized systems.
  • C. Motivating applications: Regular discretization of Laplacian-based heat and wave equations produces ordinary differential equations with the same structure as the modeled grid system.The discretized Laplacian becomes the Laplacian of an n1 × n2 grid graph.

III. CONTROLLABILITY AND OBSERVABILITY OF SIMPLE EIGENVALUES IN GRID GRAPHS

This section characterizes controllability and observability for grid eigenvalues of multiplicity one.

  • The analysis targets simple grid eigenvalues, namely eigenvalues with multiplicity one.

A. Laplacian eigenstructure of cartesian-product graphs

Cartesian-product structure induces corresponding structure in grid Laplacian eigenvalues and eigenvectors, enabling their characterization from constituent graphs.

  • The Laplacian of a Cartesian product is constructed from the Laplacians of its constituent graphs through Kronecker sums.
  • Cartesian-product eigenvalues and eigenvectors are formed from constituent eigenvalues and eigenvectors.
  • The simple Cartesian-product definition requires the relevant sums of distinct constituent eigenvalues to remain distinct.
  • The Cartesian-product construction generalizes associatively from two graphs to products of more than two graphs.

B. Controllability and observability of the simple eigenvalues

For simple grids, controllability and observability reduce to corresponding properties of constituent paths, yielding node-wise criteria and an intersection-based test for node sets.

  • A simple grid is controllable or observable from a node if and only if every constituent path is controllable or observable from its corresponding coordinate.
  • Any simple grid eigenvalue is controllable or observable from every node.
  • For a simple grid, failure at a node occurs exactly when at least one direction has a path eigenvalue that is not controllable or observable there.
  • For each odd prime factor of a path length, the theorem identifies node sets producing uncontrollable or unobservable grid eigenvalues and eigenvectors.
  • The partition procedure extends from the presented two-dimensional case to higher dimensions.
  • A node set controls or observes a two-dimensional simple grid exactly when its controllability or observability partition has empty total intersection.

IV. EIGENSTRUCTURE OF GENERAL GRID GRAPHS

For general grids, the paper analyzes eigenvector symmetries and zero components to obtain necessary and sufficient controllability and observability conditions.

  • General-grid analysis characterizes eigenvector symmetries through suitable grid partitions and identifies components that must be equal or zero.
  • For non-simple grids, eigenvectors need not be Kronecker products of path eigenvectors, so zero propagation alone cannot characterize controllability or observability.
  • Zero propagation provides only necessary conditions for controllability and observability in the general-grid setting.
  • These structural results support necessary and sufficient conditions for controllability and observability.
  • The analysis is presented for two-dimensional grids, with higher-dimensional results based on the same arguments.

A. Symmetries of the path Laplacian eigenvectors

Path Laplacian eigenvectors are constrained by reversal symmetry: each is either preserved or sign-flipped by the path-reversal permutation. These symmetry classes support the analysis of larger paths built from repeated segments.

  • Path-reversal symmetry: Each path Laplacian eigenvector satisfies either v = Πv or v = −Πv, where Π reverses the path coordinates.The result follows because reversal commutes with the path Laplacian, simple eigenvalues force proportionality, and norm preservation restricts the factor to ±1.
  • Symmetry classes: The reversal-symmetric and reversal-antisymmetric vector sets are denoted S+ and S−, and they are orthogonal complements.These classes organize whether eigenvector components mirror or change sign under reversal.
  • Repeated-path structure: For a path whose length is a multiple of a shorter path, eigenvectors associated with the shorter path’s eigenvalues inherit a repeated, symmetry-related structure.The construction is established by expressing the larger path Laplacian through the shorter path Laplacian and extending the argument from k = 3 to general k.
  • Repeated-path structure: The repeated-path eigenvector construction is verified by decomposing the larger eigenvector into shorter-path blocks and selecting blocks related by reversal.For example, the proof uses blocks vi, Πvi, and vi in the k = 3 case.

B. Symmetries of the grid eigenvectors

Grid eigenvector symmetries are exposed by partitioning larger grids into bricks and relating each brick to a reference brick through coordinate reflections. Path reversal symmetries then yield four basis-vector classes and identify component-zero patterns, while linear combinations require separate treatment.

  • Brick partitions: Every eigenvalue of the reference grid G0 = P_n1□P_n2 remains an eigenvalue of any grid formed by repeating its dimensions by integer factors.The result follows from the additive path-spectrum structure and the corresponding repeated-path eigenvalues.
  • Brick partitions: A grid G = P_{l·n1}□P_{m·n2} is partitioned into n1 × n2 bricks whose eigenvector subvectors are related by horizontal and vertical reflections.The reference brick G11 determines the component pattern in other bricks through successive reflections.
  • Brickwise eigenvector structure: For each eigenvalue of the reference grid, an eigenvector in the larger grid decomposes into brick subvectors obtained from a reference eigenvector through coordinate reversals.Odd and even brick indices determine whether each reversal operator contributes a change, producing the stated brickwise decomposition.
  • Four grid symmetry classes: Each Kronecker-product basis eigenvector belongs to one of four symmetry classes determined by the two constituent path eigenvectors’ reversal parities.The classes are denoted S++, S+−, S−+, and S−−.
  • Four grid symmetry classes: For odd grid dimensions, S−+ and S−− vanish on the central coordinate of the first path, while S+− and S−− vanish on the central coordinate of the second.These zero-component patterns provide direct information for identifying nodes relevant to controllability and observability tests.
  • Multiplicity and general eigenvectors: Simple-eigenvalue eigenvectors retain a single Kronecker-product symmetry, whereas non-simple eigenvalues permit linear combinations whose symmetry need not remain in one class.The limitation arises because vectors expressed as Kronecker products are not closed under linear combination.

V. CONTROLLABILITY AND OBSERVABILITY ANALYSIS OF GENERAL GRID GRAPHS

The paper derives necessary and sufficient controllability and observability criteria for grid-Laplacian systems by analyzing eigenvalue multiplicities, eigenvector zeros, and symmetries. Graph decompositions and component-value patterns then provide a simpler way to select valid control or observation nodes.

  • Necessary and sufficient conditions characterize all and only the grid nodes from which the induced system is controllable or observable.
  • For simple eigenvalues, zeros of grid eigenvectors can be found from the path-eigenvector zeros and propagated through the Kronecker-product structure.
  • For repeated eigenvalues, controllability and observability depend on both path-eigenvector zeros and symmetries among grid eigenvector components.
  • For multiplicity-two eigenvalues, simultaneous zeroing of two grid components is possible exactly when the polynomial-product equality in equation (8) holds.
  • The criterion extends to higher-dimensional grids and higher eigenvalue multiplicities through products of component polynomials and larger determinant conditions.
  • The resulting graph-based tools expose eigenvector symmetries and offer an alternative to standard tests whose repeated eigenvalue-by-eigenvalue computations become prohibitive as grid dimensions grow.

VI. CONCLUSIONS

The paper characterizes controllability and observability for linear time-invariant systems induced by grid Laplacians. It uses graph decompositions, eigenvector symmetries, and number-theoretic rules to identify problematic nodes and construct sufficient control or observation sets.

  • The work characterizes controllability and, by duality, observability for linear time-invariant systems whose dynamics are induced by grid-graph Laplacians.
  • Grid-Laplacian eigenstructure is described through graph decompositions, eigenvector symmetries, and simple number-theoretic rules.
  • The analysis identifies all and only uncontrollable or unobservable node sets and supplies simple routines for choosing nodes that guarantee controllability or observability.

APPENDIX

The appendix recalls number-theoretic controllability and observability results for path graphs, including prime-factor conditions for problematic nodes, eigenvalues, and eigenvectors. These path results form a basis for the grid analysis.

  • The appendix recalls path-graph controllability and observability results expressed through the prime factorization of the path length.
  • For an interior node, path controllability or observability can fail when an odd prime divides the path length and the node belongs to the corresponding node set.
  • Each odd prime factor yields node sets associated with uncontrollable or unobservable eigenvalues and eigenvectors.
  • The uncontrollable or unobservable subspaces are spanned by the corresponding path eigenvectors.
  • The appendix extends the statements to repeated prime factors by replacing a prime with the appropriate power determined by its multiplicity.
Loading 1203.0129v1…