Source-linked AI summary
A Unifying Framework for Strong Structural Controllability
Jiajia Jia, Henk J. van Waarde, Harry L. Trentelman, M. Kanat Camlibel
TL;DR
Strong structural controllability has generally been studied for systems whose matrix entries are fixed zero or arbitrary nonzero, although some systems also have entries that may take either value. This paper represents that broader structure with pattern matrices and establishes algebraic rank tests and graph-theoretic conditions using a color change rule. The results provide necessary and sufficient tests and connect earlier results within a unifying framework.
Problem
Method
The paper models fixed-zero, nonzero, and arbitrary entries with pattern matrices, then derives rank tests and graph-theoretic conditions based on a color change rule.
Source: §I · p. 2, §IV · p. 4, §VII · p. 10Results
The paper establishes necessary and sufficient algebraic conditions for strong structural controllability and a necessary and sufficient colorability condition for a pattern matrix to have full row rank.
Source: §I · p. 2, §IV · p. 4Takeaways & Limitations
The results recover seemingly incomparable earlier results and provide a unifying approach to strong structural controllability.
Source: §I · p. 2
Abstract
from arXiv · showhide
This paper deals with strong structural controllability of linear systems. In contrast to existing work, the structured systems studied in this paper have a so-called zero/nonzero/arbitrary structure, which means that some of the entries are equal to zero, some of the entries are arbitrary but nonzero, and the remaining entries are arbitrary (zero or nonzero). We formalize this in terms of pattern matrices whose entries are either fixed zero, arbitrary nonzero, or arbitrary. We establish necessary and sufficient algebraic conditions for strong structural controllability in terms of full rank tests of certain pattern matrices. We also give a necessary and sufficient graph theoretic condition for the full rank property of a given pattern matrix. This graph theoretic condition makes use of a new color change rule that is introduced in this paper. Based on these two results, we then establish a necessary and sufficient graph theoretic condition for strong structural controllability. Moreover, we relate our results to those that exists in the literature, and explain how our results generalize previous work.
I. INTRODUCTION
Strong structural controllability had largely been studied for systems whose entries are fixed zero or arbitrary nonzero, but physical and networked systems can also contain entries that may be zero or nonzero. The paper extends the framework to this broader structure and develops algebraic and graph-theoretic tests.
I. INTRODUCTION
- A zero/nonzero-only model is insufficient when a system entry is neither fixed at zero nor constrained to be nonzero, but can take any real value.The paper motivates this third possibility with physical-system and networked-system examples.Source: §I · p. 1
- Existing strong structural controllability tests, – do not apply when system entries may be zero or nonzero rather than fixed zero or nonzero.The electrical-circuit example has entries that can take either value, including an entry that may be zero when R = G.Source: §I · pp. 1–2
- Network models can have uncertain links, so their system matrices may not have a zero/nonzero structure determined by a known graph.In the three-agent example, link (1, 2) may or may not exist, making its weight arbitrary while weights for existing links are nonzero.Source: §I · p. 2
- The paper extends zero/nonzero structure to zero/nonzero/arbitrary structure, formalizes it with pattern matrices, and gives necessary and sufficient algebraic and graph-theoretic tests for strong structural controllability.It also gives a color change rule for testing full row rank and relates the results to prior work.Source: §I · p. 2
- The paper presents its approach as a unifying theory, showing that seemingly incomparable results of and follow from its main results.It also identifies related lines of work that it does not pursue, including weak structural controllability, parameter dependencies, and minimal input selection.Source: §I · p. 2
II. PRELIMINARIES
The paper defines pattern matrices whose entries encode fixed zeros, arbitrary nonzero values, or arbitrary values. It formulates strong structural controllability for families of systems described by these matrices and relates the broader framework to prior work.
II. PRELIMINARIES
- Pattern matrices use 0, ∗, and ? to encode entries that are fixed at zero, constrained to be nonzero, or arbitrary, respectively.The pattern class contains all real matrices that satisfy those entrywise constraints.Source: §II · p. 3
III. PROBLEM FORMULATION
- Strong structural controllability requires every system in the family specified by (A, B) to be controllable.The family allows A and B to range over the pattern classes of their respective matrices.Source: §III · p. 3
- Earlier networked-system results include special cases of the pattern matrices considered here, including cases with only 0 and ∗ entries or with ? entries only on the diagonal.The cited framework also commonly assumes each input affects a single network node.Source: §III · p. 3
- The paper investigates necessary and sufficient conditions for strong structural controllability when A and B are general {0, ∗, ?} pattern matrices.The authors state that a framework for this general case had not yet been developed.Source: §III · p. 3
- Prior work on weak structural controllability can be applied to the broader systems by replacing ∗ entries with ? entries in A and B.The resulting system is weakly structurally controllable exactly when the original one is, so existing conditions – apply.Source: §III · p. 3
IV. MAIN RESULTS
The section gives algebraic rank tests for strong structural controllability, then characterizes full row rank through a color-change rule. Together, these results yield a necessary and sufficient graph test for structured-system controllability.
IV. MAIN RESULTS
- Controllability is equivalent to full row rank of both [A B] and [bar A B]; neither rank condition implies the other in general.When no diagonal entry of A is zero, the first rank condition is implied by the second.Source: §IV · p. 4
- A pattern matrix has full row rank if and only if its associated graph is colorable under the paper’s color-change rule.A node can change a neighboring node’s color even if the node itself is not black; only nodes 1 through p must become black.Source: §IV · p. 4
- Combining the rank test with the colorability result gives a necessary and sufficient graph condition for structured-system controllability.The condition applies to the graphs associated with A and its diagonal-modified pattern matrix, together with B.Source: §IV · pp. 3, 5
- The circuit example is controllable because both associated graphs are colorable, while the network example is not controllable as modeled.In the network example, setting A21 = * makes the system controllable.Source: §IV · pp. 5–6
- When no diagonal entry of A is zero, controllability is characterized by the colorability condition in Corollary 15.The corresponding rank-test simplification follows because the first rank condition is implied by the second.Source: §IV · pp. 4, 6
- For structured systems, stabilizability holds if and only if controllability holds.The paper notes that this equivalence differs from the general single-system case, where the reverse implication need not hold.Source: §IV · p. 6
V. DISCUSSION OF EXISTING RESULTS
The discussion surveys strong structural controllability results and compares their system classes with the broader structures considered in this paper.
V. DISCUSSION OF EXISTING RESULTS
- The discussion positions the paper's results alongside earlier work rather than treating the existing tests as applicable to every structured-system class.The survey identifies the most relevant prior results as context for the comparison that follows.Source: §V · p. 6
- Earlier strong structural controllability work almost exclusively studied pattern matrices containing only 0 and *, with as an exception.The section also notes that began with the single-input case, later extended in, while and [6] offered other tests and [7] corrected a graph-theoretic test.Source: §V · p. 6
- The networked-system results,, and cover narrower pattern classes, including distinct restrictions on diagonal entries and the input matrix B.The discussion frames the comparison around algorithmic complexity and conceptual simplicity.Source: §V · p. 6
A. Graph theoretic conditions
This subsection compares graph-theoretic tests for strong structural controllability and explains how the paper's colorability conditions relate to earlier zero-forcing results.
A. Graph theoretic conditions
- The earlier graph test in [2] and its multi-input extension [4] require accessibility checks and relations over all state-node subsets.The section says checking those conditions has computational complexity at least exponential in n.Source: A. Graph theoretic conditions · p. 6
- The paper's colorability conditions can be checked in polynomial time in n and are described as simpler and more intuitive than conditions in and.For 's alternative sparse-graph test, the section says an algorithmic checking method is unclear; it also says Theorem 12 is easier to check than [7]'s spanning-cycle-family conditions.Source: A. Graph theoretic conditions · p. 7
- The networked-system frameworks,, and construct A and B from a directed graph and a leader set, with different graph and matrix restrictions.[8] and permit self-loops, whereas does not.Source: A. Graph theoretic conditions · p. 7
- In and [10], constrained matchings characterize controllability, and [10] relates those matchings to loopy zero forcing for loop graphs.The section introduces zero forcing as a rule that repeatedly colors a node when a node has exactly one white out-neighbor.Source: A. Graph theoretic conditions · p. 7
- The earlier characterization in for graphs without self-loops uses ordinary zero forcing, where only a black node with exactly one white out-neighbor can change its color.The section states this as a condition for the pattern matrices defined for 's system class.Source: A. Graph theoretic conditions · p. 7
- The paper shows that its conditions are equivalent to 's two loopy zero-forcing conditions and 's ordinary zero-forcing condition on their respective system classes.Those classes do not overlap: excludes ? entries, while allows them only on A's diagonal.Source: A. Graph theoretic conditions · pp. 7–8
B. Algebraic conditions
This subsection relates the paper's rank tests to algebraic conditions from earlier work, showing equivalence for the corresponding restricted pattern-matrix classes.
B. Algebraic conditions
- For A and B containing only 0 and *, the rank conditions in Theorem 7 are equivalent to the algebraic conditions in Theorem 20.The argument uses the equivalence between full row rank and Form III for the relevant pattern matrices.Source: B. Algebraic conditions · p. 8
- Theorem 20 tests matrices formed from A and B, including A* obtained by replacing every diagonal entry of A with *.Its two conditions require the resulting matrices to be of Form III.Source: B. Algebraic conditions · p. 8
- For the graph-based pattern matrices in [3], the paper's Corollary 8 yields the earlier full-row-rank condition because all diagonal entries of A are ?.In that special case, A equals A-bar.Source: B. Algebraic conditions · p. 8
A. Proof of Theorem 7
The proof of Theorem 7 uses the Hautus test and pattern-matrix constructions to establish the rank conditions associated with controllability.
A. Proof of Theorem 7
- Assuming controllability, the proof invokes the Hautus test and constructs a real vector x from the real and imaginary parts of a vector z.The proof uses coordinatewise equivalences between x_i = 0, z_i = 0, and (x^T A)_i = 0, then uses nonsingularity to derive condition 2.Source: A. Proof of Theorem 7 · pp. 8–9
- To derive the rank conditions, the proof first substitutes λ = 0 for condition 1, then assumes a nonzero vector violates condition 2 and constructs a member of P(A).The construction uses a nonzero real α and a diagonal matrix X; the argument concludes that the violating vector must be zero.Source: A. Proof of Theorem 7 · pp. 8–9
B. Proof of Theorem 11
Theorem 11 characterizes full row rank of a pattern matrix through colorability of its graph. Its proof reduces rank tests using a color-change step, then shows that failure to color implies failure of full row rank.
B. Proof of Theorem 11
- Lemma 23 preserves the full-row-rank test when a row corresponding to a qualifying white out-neighbor is added to the pattern matrix.The proof uses this rank equivalence to support repeated reduction.Source: B. Proof of Theorem 11 · p. 9
- If the graph is colorable, repeated application of Lemma 23 reduces the full-row-rank test to a matrix that has full row rank.The proof concludes that the original matrix has full row rank.Source: B. Proof of Theorem 11 · p. 9
- If the graph is not colorable, the remaining white-node submatrix has no column with exactly one * and all other entries zero.The proof constructs a pattern realization with zero column sums, contradicting full row rank.Source: B. Proof of Theorem 11 · pp. 9–10
C. Proof of Theorem 12
The proof of Theorem 12 uses Theorems 7 and 11 to establish a controllability criterion involving a graph condition.
C. Proof of Theorem 12
- The proof invokes Theorems 7 and 11 to derive Theorem 12's controllability criterion involving a graph condition.The supplied passage states the criterion as an if-and-only-if result, but does not preserve the full graph expression.Source: C. Proof of Theorem 12 · p. 10
- The proof's stated basis for the criterion is Theorem 7 together with Theorem 11.The excerpt does not provide further proof steps.Source: C. Proof of Theorem 12 · p. 10
- Theorem 12's criterion relates controllability to a graph property.The excerpt identifies the relation as an if-and-only-if statement but does not retain the graph's name or form.Source: C. Proof of Theorem 12 · p. 10
D. Proof of Theorem 16
Theorem 16's proof uses the symmetry between A and −A to connect strong structural stabilizability with controllability.
D. Proof of Theorem 16
- If every system in the structured family is stabilizable, then the proof shows each pair (A, B) is controllable.It applies the Hautus test for stabilizability to both (A, B) and (−A, B).Source: D. Proof of Theorem 16 · p. 10
- Because A and −A share the pattern structure, stabilizability of the family entails stabilizability of both pairs.The proof uses this symmetry before applying the Hautus test.Source: D. Proof of Theorem 16 · p. 10
- The proof derives controllability from the two stabilizability tests using the Hautus test for stabilizability.The passage cites [1, Thm. 3.32] for that test.Source: D. Proof of Theorem 16 · p. 10
E. Proof of Lemma 21
The proof of Lemma 21 reduces the pattern matrix by permutations, while the conclusion places the paper's rank and graph conditions in a broader framework. It also reports results on weak controllability and strong stabilizability and identifies possible future applications.
E. Proof of Lemma 21
- Repeatedly permuting rows and columns applies the same rank-preserving argument to reduce the pattern matrix.The proof uses a column with a single * and zeros elsewhere to begin the reduction.Source: E. Proof of Lemma 21 · p. 10
VII. CONCLUSIONS
- The paper extends strong structural controllability to zero/nonzero/arbitrary structures and gives algebraic rank tests and a graph test based on a new color-change rule.The conclusion says the resulting conditions generalize previous work and incorporate results, into the framework.Source: §VII · p. 10
- Weak structural controllability can be checked with existing tests, and strong structural stabilizability is equivalent to strong structural controllability for these systems.Source: §VII · p. 10
- Network identification and fault detection and isolation are named as possible future application areas for the framework.The conclusion leaves these applications for future research.Source: §VII · p. 10