Source-linked AI summary
Quiver Semistability and Structured Kalman Decompositions for Networked Linear Dynamical Systems
Kazuo Murota, Tasuku Soma
TL;DR
Networked LTI systems need control-theoretic notions that preserve subsystem and interconnection structure rather than treating the whole network as one large system. The paper uses quiver representations and σ-semistability to define network-respecting controllability, observability, and Kalman-type decompositions, with efficient algorithms for these tasks and for selected quivers with self-loops. These notions provide structured certificates and decompositions, but they do not replace ordinary controllability and observability because the converse implication fails in general.
Problem
Classical controllability and observability analyses can ignore network structure and mix substates across subsystems, motivating structure-respecting notions for networked LTI systems.
Method
The paper models networked LTI systems as quiver representations and applies σ-semistability and generalized King criteria to define network-respecting control notions and a Kalman-type decomposition.
Results
The paper provides efficient algorithms for deciding the proposed controllability and observability, finding the Kalman-type decomposition, and deciding σ-semistability with maximally violating subrepresentations for specified acyclic quivers with self-loops.
Takeaways & Limitations
The framework yields subsystem-level invariant-subspace certificates and decompositions that respect local and interconnection dynamics, and extends to target control settings.
Takeaways & Limitations
Network-respecting controllability and observability are necessary but not sufficient for their ordinary counterparts, so the proposed notions do not replace the ordinary ones.
Abstract
from arXiv · showhide
We introduce new notions of controllability and observability for networked linear time-invariant (LTI) systems based on $σ$-semistability of quiver representations. Utilizing King's criterion for $σ$-semistability, we define a network generalization of the Kalman decomposition for networked LTI systems, which systematically decomposes the local and interconnection dynamics while respecting the underlying network structure. Furthermore, we present efficient algorithms for deciding the proposed controllability and observability of a given networked LTI system and for finding the Kalman-type decomposition. We also show efficient algorithms for deciding the $σ$-semistability of representations of acyclic quivers with self-loops if the weight $σ$ has the same sign for all vertices with self-loops. Such quiver representations and weights arise from networked LTI systems.
1 Introduction
The paper develops network-structure-aware controllability, observability, and Kalman-type decompositions for networked LTI systems using quiver representations and σ-semistability. It also provides polynomial-time algorithms for these tasks and for a class of quivers with self-loops.
- Motivation: Naively applying the classical Kalman decomposition can mix substates across subsystems and obscure network-structured control properties.The paper identifies a lack of a general framework for systematically analyzing networks of high-dimensional subsystems.
- Our contributions: The paper defines network-respecting controllability and observability by representing networked LTI systems as quivers with self-loops and applying σ-semistability.Bader’s generalized King’s criterion characterizes these notions through collections of invariant subspaces within subsystems.
- Our contributions: The resulting Kalman-type decomposition consistently decomposes local and interconnection dynamics together with input and output matrices.The decomposition is designed to respect the underlying network structure.
- Our contributions: The proposed notions are necessary for ordinary controllability and observability, but the converse fails in general.Thus, they do not replace ordinary notions; instead, they identify subsystem subspaces certifying ordinary uncontrollability and unobservability.
- Efficient Algorithms: The algorithms decide network-respecting controllability and observability and find the Kalman-type decomposition using simple subspace iteration in polynomial time.They construct subrepresentations that maximally violate the generalized King’s criterion.
- Semistability in quivers with self-loops: For acyclic network interconnection quivers, target controllability and observability use weights with a common sign on self-loop vertices, enabling simple subspace iteration.The paper also gives polynomial-time semistability and maximally violating-subrepresentation algorithms under the corresponding self-loop and weight-sign conditions.
2 Preliminaries on quiver representations
The preliminaries define quiver representations, subrepresentations, dimension vectors, vertex weights, and σ-semistability. King’s criterion reduces semistability to a balance condition and inequalities over all subrepresentations.
- Quiver representations: A quiver consists of vertices and directed arcs, while a representation assigns a finite-dimensional vector space to each vertex and a linear map to each arc.After choosing bases, the arc maps can be represented by matrices.
- Quiver representations: The dimension vector records the dimension of the vector space assigned to every vertex, and fixed dimension vectors define representation spaces.The representation space is denoted Rep(Q, α; F).
- Group action and weights: Basis changes act independently at vertices through the product group GL(Q, α), transforming each arc map by head and tail basis changes.This action organizes representations up to vertex-wise changes of basis.
- Group action and weights: An integer vertex weight σ defines a character using the product of determinant powers across vertices.The weight also evaluates a dimension vector as σ(α) = Σ_i σ(i)α(i).
- Semistability: King’s criterion states that σ-semistability requires σ(dim V) = 0 and σ(dim W) ≤ 0 for every subrepresentation W ≤ V.A subrepresentation is a vertex-wise collection of subspaces preserved by every arc map.
- Semistability: σ-stability strengthens semistability by requiring strict negativity for every nonzero proper subrepresentation.Subrepresentations form a modular lattice under vertex-wise sums and intersections.
3 Networked LTI systems and quiver representations
The paper models networked LTI systems as marked-quiver representations and defines network-respecting controllability, observability, and Kalman-type decompositions through σ-semistability. It also gives polynomial-time procedures for deciding these properties and computing the decomposition.
- Quiver representation framework: Networked LTI systems correspond naturally and one-to-one with representations of marked quivers whose structure preserves subsystem interconnections.
- Network-respecting controllability: For controllability, the representation uses weight σ(i) = −1 on subsystem vertices and σ(i) = 0 elsewhere, with σ-semistability defining network-respecting controllability.
- Network-respecting controllability: Network-respecting controllability holds exactly when the controllable subrepresentation equals the full representation at every subsystem vertex.
- Relation to ordinary properties: The proposed controllability and observability notions are necessary for ordinary LTI controllability and observability, but the converse does not generally hold.
- Network-respecting observability: For observability, weight σ(i) = 1 on subsystem vertices and σ(i) = 0 elsewhere, and σ-semistability characterizes network-respecting observability.
- Decomposition and algorithms: The Kalman-type decomposition simultaneously organizes controllable and unobservable subrepresentations, while algorithms decide the properties and compute the decomposition in polynomial time.Algorithm 1 uses subspace iteration, and the stated running time is polynomial in α, m, p, and the size of N.
4 On semistability in acyclic quivers with self-loops
The section reduces σ-semistability for acyclic quivers with self-loops to semistability on an acyclic quiver, yielding polynomial-time decision and maximization algorithms under a same-sign condition.
- Application to networked LTI systems: The construction applies to networked LTI systems whose interconnection quiver is acyclic, because their associated marked quivers are acyclic quivers with self-loops.For network-respecting controllability and observability, the relevant weights already have a uniform sign, while the reduction handles arbitrary weights at vertices without self-loops.
- For acyclic quivers with self-loops, σ-semistability is polynomial-time decidable when all self-loop vertices have nonzero weights with the same sign.The runtime is polynomial in the quiver and representation sizes and the largest absolute weight.
- Reduction to the acyclic case: The reduction replaces each self-loop vertex with two vertices joined by α(i) parallel arcs and assigns matrix powers V(a)^k to those arcs.Non-loop arcs are redirected between the corresponding gadget vertices, with weights assigned to preserve the semistability test.
- Reduction to the acyclic case: When self-loop weights are negative, V is σ-semistable exactly when its reduced representation ˜V is ˜σ-semistable.The positive-sign case follows by applying the analogous argument to the transposed representation and weight −σ.
- Algorithms: The acyclic reduction enables use of the existing acyclic-quiver algorithm to decide semistability and find a subrepresentation maximizing σ(dim W).Maximizing subrepresentations can be transferred between the original and reduced representations.
Declaration of generative AI and AI-assisted technologies in the manuscript preparation process
The authors report using GPT-5.6 Pro to proofread drafts during preparation of the manuscript.
- The authors used GPT-5.6 Pro to proofread drafts written by the authors.They state that an early algorithm was later simplified and extended beyond acyclic interconnection quivers after this proofreading.
A On semistability over the real and complex fields
This appendix establishes that, for real quiver representations, σ-semistability over the real field is equivalent to σ-semistability after complexification.
- A real representation V can be regarded as the complex representation V_C = V ⊗_R C.The appendix uses this complexification to compare semistability over R and C.
- For real representations, σ-semistability over R is equivalent to σ(dim V)=0 and σ(dim W)≤0 for every real subrepresentation W.This gives the real-field form of King’s criterion used in the appendix.
- The same real representation is σ-semistable over R if and only if its complexification is σ-semistable over C.The proof relates complex subrepresentations to real ones through conjugation and real-and-imaginary parts.
- A conjugation-invariant complex subspace is the complexification of a real subspace.This proposition supplies the linear-algebra step needed to recover real subrepresentations from suitable complex subrepresentations.