Pith. sign in

REVIEW 4 major objections 4 minor 27 references

Strong Structural Controllability of Signed Networks

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A combinatorial game on signed graphs decides which eigenvalues of a network are strongly structurally controllable.

desk verdict Theorem 2 fails for directed signed graphs because Lemma 1 mishandles self-loops; the signed zero forcing idea is still worth a serious look. read the letter →

arxiv 1908.05732 v3 pith:TVQBJE3T submitted 2019-08-15 math.OC

Shima Sadat Mousavi , Mohammad Haeri , Mehran Mesbahi This is my paper · ORCID
classification math.OC MSC 93B0505C5015A1893C05
keywords signednetworksstrongstructuralcontrollabilityzeroforcingsignpatternLTIsystemseigenvaluegeometricmultiplicity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper gives a purely combinatorial sufficient condition for strong structural controllability of linear time-invariant networks whose interaction graphs carry positive and negative edge signs. It introduces positive and negative signed zero forcing sets, graph-theoretic signing and coloring games, and proves that if the control nodes form such a set, then every positive (resp., negative, zero) eigenvalue of every system matrix compatible with the sign pattern is controllable. For networks whose sign patterns only admit real eigenvalues, having all three types of zero forcing sets guarantees controllability of the whole network. The same tools bound the maximum geometric multiplicity of positive and negative eigenvalues over the entire qualitative class of matrices.

What carries the argument

The load-bearing object is a pair of new combinatorial games: the positive and negative signed zero forcing games, played on the graph obtained by adding positive (resp., negative) self-loops to every node without a specified loop. A set $Z$ is a positive signed zero forcing set if, starting with $Z$ black, repeated application of the four signing-and-coloring rules blackens every vertex. The rules mirror the terms in the column equation $\nu^T A = \lambda \nu^T$: blackening a unique white out-neighbor encodes that its eigenvector entry must be zero, marking an unmarked neighbor encodes that its sign is forced by the signs of the already marked neighbors, and blackening a whole set encodes that a signed sum of same-sign terms must vanish. This correspondence is what lets the game propagate both zeros and signs of a left eigenvector from the control nodes to the entire graph.

What would settle it

Find one signed graph $G_s$, one control set $V_C$ that is a positive signed zero forcing set, and one matrix $A$ in the sign class with a positive eigenvalue $\lambda$ whose left eigenvector vanishes on $V_C$; such an example would refute Theorem 2. A concrete construction to look for is a small directed graph in which the third clause of the rule marks a node while another previously marked node in the same column equation has a zero eigenvector entry, so the 'all summands have the same sign' argument collapses.

Watch

Extended reading notes

Core claim

The central claim is that eigenvalue-specific controllability of a signed network can be certified by a finite combinatorial game. For a signed graph $G_s$ and a control set $V_C$, if $V_C$ is a positive signed zero forcing set, then every positive eigenvalue of every real matrix $A$ whose sign pattern is that of $G_s$ is controllable; replacing 'positive' by 'negative' or 'zero' gives the analogous statement with negative signed zero forcing sets or signed zero forcing sets. The proof takes a left eigenvector $\nu$ with $\nu^T A = \lambda \nu^T$ that vanishes on $V_C$ and shows, game-step by game-step, that the signed zero forcing rules force $\nu$ to vanish everywhere, contradicting the PBH eigenvector condition for an uncontrollable eigenvalue. When the sign pattern permits only real eigenvalues, having all three zero forcing properties makes the whole network strongly structurally controllable, and the game yields an upper bound on the maximum geometric multiplicity of positive and negative eigenvalues in the whole qualitative class.

Load-bearing premise

The proof of Lemma 1 assumes that, whenever rule 3 marks the last unmarked white out-neighbor with a sign, the true eigenvector entry actually has that sign; this inference is valid only if all previously marked nodes entering the same column equation have nonzero entries with the signs the game assigned, and the paper does not fully justify that the game's marks track eigenvectors when some marked nodes have zero entries.

Editorial extensions

If this is right

  • If $V_C$ is a positive signed zero forcing set, no choice of nonzero edge weights consistent with the sign pattern can create an uncontrollable positive eigenvalue; the guarantee is uniform over the whole qualitative class.
  • Networks whose sign pattern allows only real eigenvalues become fully strongly structurally controllable once $V_C$ is simultaneously a signed, positive signed, and negative signed zero forcing set.
  • The positive and negative signed zero forcing numbers bound the largest possible geometric multiplicity of positive and negative eigenvalues across all matrices in the sign class.
  • Verifying the condition is a graph game, so the sufficient test is combinatorial and does not require solving the NP-hard algebraic sign-controllability checks used in earlier work.
  • The same reasoning treats zero eigenvalues through the ordinary signed zero forcing game, completing an eigenvalue-by-eigenvalue controllability picture.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the conditions are only sufficient, minimal positive signed zero forcing sets may be strictly larger than the true minimum number of control nodes needed for positive-eigenvalue controllability; a necessary and sufficient combinatorial test, if one exists, would need a game with additional rules or tie-breaking.
  • The game's sign propagation suggests a natural extension to robust strong structural controllability under edge additions and deletions, where a control set must survive all graphs in an uncertainty set; the signed rules could be adapted to that setting.
  • The geometric-multiplicity bound invites a signed analogue of the minimum-rank program: computing the positive and negative signed zero forcing numbers could yield inertia or eigenvalue-location bounds for matrices with a given sign pattern.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper studies strong structural controllability of linear time-invariant networks defined on signed graphs. It introduces two new combinatorial notions, positive and negative signed zero forcing sets, and claims that these sets provide sufficient conditions for the strong structural controllability of positive and negative eigenvalues, respectively, of every matrix in a signed qualitative class (Theorem 2). A further theorem (Theorem 3) gives a sufficient condition for full strong structural controllability when the sign pattern admits only real eigenvalues, and Proposition 2 gives an upper bound on the maximum geometric multiplicity of positive and negative eigenvalues in terms of the new zero forcing numbers. The proofs of these results rest on Lemma 1, which asserts that a left eigenvector of a positive eigenvalue that vanishes on the initial black set must vanish on the entire positive derived set and that signs of nonzero eigenvector entries agree with the signs assigned by the signed zero forcing game.

Significance. If valid, the proposed combinatorial criteria would be a useful bridge between graph-theoretic zero forcing and eigenvalue-specific strong structural controllability of signed networks. The paper is clearly written and the link to the PBH test is natural. However, the central lemma is false as stated, and the paper itself allows the self-loop configurations that break it. The concrete counterexample in the report shows that Theorem 2 fails already for a two-node directed signed graph with real eigenvalues. Since Lemma 1 is the load-bearing step for Theorem 2, Theorem 3, and Proposition 2, the central contribution of the paper is not established.

major comments (4)
  1. [Section IV, Lemma 1, clause 1 of the signing and coloring rule] The proof of clause 1 is invalid when the unique white out-neighbor is the vertex itself. The game explicitly allows u = v, and in the positive looped graph every vertex has a self-loop, so W(v) = {v} is possible. Equation (3) then reduces to ν_v(A^+_{vv} − λ) = 0, which does not imply ν_v = 0 when the loop weight equals λ. The proof silently drops the −λ term and asserts ν_u A^+_{uv} = 0 with A^+_{uv} nonzero. This is not a technicality: take V = {1,2}, a positive edge 2→1, '?' self-loops on both vertices, A = [[2,1],[0,1]] ∈ Q_s(G_s), and B = e_1. The set {1} is a positive signed zero forcing set: rule 4 marks node 2 '+', and then clause 1 applied to white node 2 with W(2) = {2} blackens node 2. Yet λ = 1 is a positive eigenvalue of A with left eigenvector w = [0,1], and w^T B = 0, so the eigenvalue is uncontrollable. This disproves Theorem 2 for directed signed graphs as stated.
  2. [Section IV, Lemma 1, rules 2 and 3 of the signing and coloring rule] The induction hypothesis only controls the sign of marked nodes whose eigenvector entries are nonzero. The proofs of clauses 2 and 3 assume, with the phrase 'without loss of generality', that all marked out-neighbors in W_+(v) or W_s(v) have nonzero eigenvector entries, so that all summands in the cancellation argument have the same sign. When some marked out-neighbor has ν_u = 0, its summand is zero, the common-sign claim is vacuous for that term, and the equation no longer determines the sign of the remaining unmarked node. This gap is load-bearing because the induction is the mechanism that propagates signs and zeros through the derived set, and it is not filled elsewhere in the paper.
  3. [Section IV, Lemma 1, setup after equation (3)] The sign bookkeeping between equation (3) and the positive looped graph is inconsistent. The proof states that for sign(A_ii) ≤ 0 one has sign(A_ii − λ) ≤ 0, and otherwise sign(A_ii − λ) can be positive, negative, or zero, and then says this is represented by a self-loop labeled '−' or '?'. However, the positive looped graph G_s^+ labels every self-loop '+', i.e., it records the sign of A_ii, not the sign of A_ii − λ. The game on G_s^+ therefore does not encode equation (3); this mismatch is the root cause of the clause 1 failure described above.
  4. [Section IV, Theorem 2 and Theorem 3] Since Theorem 2 is proved directly from Lemma 1 and the counterexample above satisfies the hypotheses of Theorem 2, the theorem is false as stated. Theorem 3 and Proposition 2 are derived from the same lemma, so they inherit the invalidity; the counterexample also shows that restricting to real eigenvalues does not remedy the self-loop problem, because the matrix A in the example is triangular and therefore has only real eigenvalues.
minor comments (4)
  1. [Section IV, proof of Theorem 2] The proof refers to 'some A ∈ P_s(G_s)', but the qualitative class was defined as Q_s(G_s); this appears to be a typo.
  2. [Section II, Example 1] The zero-nonzero pattern P is displayed as a 3×3 matrix while the sign pattern P_s is displayed as a 4×4 matrix; the dimensions should be reconciled.
  3. [Section IV, proof of Lemma 1] The sentence 'we claim that the theorem is not only true for C_K and M_K, but also for any C_j and M_j' should read 'that the claim is true for every C_j and M_j', since there is no separate theorem being proved inside the lemma.
  4. [Section III, Definition 4] The naming of the derived sets D^+_c and D^-_c is confusing: D^+_c is defined using the negative looped graph G^-_s, and D^-_c using G^+_s. A sentence explaining the intended mnemonic (e.g., that the superscript refers to the eigenvalue sign being controlled) would help the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the signed zero forcing conditions are derived graph-theoretic sufficient conditions, not fitted inputs or self-referential restatements.

full rationale

The paper's derivation chain is self-contained: Theorem 2 follows from Lemma 1, which starts from the eigenvector equation ν^T A = λν^T and, via equation (3), tracks the signing and coloring game on the positive looped graph G^+_s. The positive (resp., negative) signed zero forcing set is defined purely combinatorially in Definition 4 in terms of a coloring game; it is not defined in terms of eigenvalues, controllability, or eigenvectors. Thus the statement that such a set makes certain eigenvalues controllable is a substantive implication rather than a restatement of the definition. No parameter is fitted to data, no quantity called a prediction is a renamed input, and no uniqueness or existence theorem is imported from the authors' own prior work to force the conclusion. The cited external results ([22], [24], [25], [27]) are standard graph-theoretic references and are used as proof ingredients, not as substitutes for the paper's argument. The authors' self-citations in the introduction concern related strong structural controllability results but are not load-bearing for Theorem 2 or Proposition 2. A reader-supplied counterexample alleges that Lemma 1 is false, but an incorrect induction step is a correctness risk, not circularity: the claimed derivation is not equivalent to its assumptions by construction. Therefore no circular step is identified and the paper receives a score of 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

The central claim rests on the PBH test (standard), the restriction to symmetric matrices (domain assumption), and two proof-specific assumptions about the signed zero forcing game: the correspondence between the shifted eigenvector equation and the positive looped graph, and the soundness of marking an arbitrary node with plus. No free parameters are fitted. No physical entities are postulated.

assumptions (4)
  • standard math The PBH test for controllability of eigenvalues (Proposition 1).
    Used to reduce strong structural controllability to nonexistence of a nonzero left eigenvector orthogonal to the input matrix; cited from Sontag [26].
  • domain assumption The qualitative class Q_s(G_s) consists of symmetric matrices (undirected signed graph).
    The paper restricts to undirected signed graphs so that all matrices are symmetric and have real eigenvalues; stated in Section II.
  • ad hoc to paper The column equation (3) can be represented by the signed zero forcing game on the positive looped graph G^+_s with self-loop signs plus or question mark.
    The proof of Lemma 1 asserts this correspondence, but the text contains a sign inconsistency (it writes minus or question mark before invoking G^+_s), and the correspondence is not rigorously established.
  • ad hoc to paper The zero forcing game's marking rule 4 can choose an arbitrary white node to mark with plus by flipping the global sign of the eigenvector.
    Used in Lemma 1 proof; validity depends on the chosen node having a nonzero eigenvector entry, which is not guaranteed or handled.
invented entities (2)
  • Positive signed zero forcing set
    purpose: Combinatorial control set condition for strong structural controllability of positive eigenvalues
    New definition in Section III; no external falsifiable prediction; purely internal construct.
  • Negative signed zero forcing set
    purpose: Combinatorial control set condition for strong structural controllability of negative eigenvalues
    New definition in Section III; no external falsifiable prediction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Strong Structural Controllability of Signed Networks." pith.science (2026). https://pith.science/paper/TVQBJE3T

@misc{pith2026190805732,
  author       = {Pith},
  title        = {Pith review of: Strong Structural Controllability of Signed Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TVQBJE3T}},
  note         = {Machine review of arXiv:1908.05732}
}
read the original abstract

In this paper, we discuss the controllability of a family of linear time-invariant (LTI) networks defined on a signed graph. In this direction, we introduce the notion of positive and negative signed zero forcing sets for the controllability analysis of positive and negative eigenvalues of system matrices with the same sign pattern. A sufficient combinatorial condition that ensures the strong structural controllability of signed networks is then proposed. Moreover, an upper bound on the maximum multiplicity of positive and negative eigenvalues associated with a signed graph is provided.

Figures

Figures reproduced from arXiv: 1908.05732 by the authors.

Figure 1
Figure 1. a) Graph G, b) looped graph G× [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. a) Graph Gs, b) positive looped graph G + s , c) negative looped graph G − s . For a (undirected) graph G = (V, E, P), the qualitative class, denoted by Q(G), is defined as the set of all (sym￾metric) matrices in R n×n whose zero-nonzero pattern is P. Similarly, for a (undirected) signed graph Gs = (V, E, Ps), the qualitative class Qs(Gs), is the set of all (symmetric) matrices in R n×n whose sign pattern is Ps. We … view at source ↗
Figure 3
Figure 3. An example for the classical coloring rule. [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: a) Graph G, b) the associated looped graph G×. B. Signed Zero Forcing Sets Signed zero forcing game is indeed a signing and coloring game played on the nodes of a signed graph. In the first part of this game, we assume that some nodes of the signed graph Gs = (V, E, Ps…
Figure 5
Figure 5. Figure 5: An example of the signing and coloring rule. [PITH_FULL_IMAGE:figures/full_fig_p004_5.png]
Figure 6
Figure 6. Figure 6: a) Negative looped graph G − s , b) positive looped graph G + s (associated with Gs in [PITH_FULL_IMAGE:figures/full_fig_p004_6.png]
Figure 7
Figure 7. Figure 7: An example of the signing and coloring rule. [PITH_FULL_IMAGE:figures/full_fig_p006_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    On the controllability of nearest neighbor intercon- nections,

    H. G. Tanner, “On the controllability of nearest neighbor intercon- nections,” in Proc. 43rd IEEE Conf. on Decision and Control , vol. 3, 2004, pp. 2467–2472

    work page 2004

  2. [2]

    Inter- acting with networks: How does structure relate to controllability in single-leader, consensus networks?

    M. Egerstedt, S. Martini, M. Cao, K. Camlibel, and A. Bicchi, “Inter- acting with networks: How does structure relate to controllability in single-leader, consensus networks?” IEEE Control Syst. Mag., vol. 32, no. 4, pp. 66–73, 2012

    work page 2012

  3. [3]

    Controllability analysis of networks through their topologies,

    S. S. Mousavi and M. Haeri, “Controllability analysis of networks through their topologies,” in Proc. 55th IEEE Conf. on Decision and Control, 2016, pp. 4346–4351

    work page 2016

  4. [4]

    Controllability analysis of threshold graphs and cographs,

    S. S. Mousavi, M. Haeri, and M. Mesbahi, “Controllability analysis of threshold graphs and cographs,” in 2018 European Control Conf. , 2018, pp. 1–6

    work page 2018

  5. [5]

    Laplacian Dynamics on Cographs: Controllability Analysis through Joins and Unions

    S. S. Mousavi, M. Haeri, and M. Mesbahi, “Laplacian dynamics on cographs: Controllability analysis through joins and unions,” arXiv:1802.03599, 2018

    work page Pith review arXiv 2018

  6. [6]

    Strong structural controllability,

    H. Mayeda and T. Yamada, “Strong structural controllability,” SIAM J. Contr. and Optimiz. , vol. 17, no. 1, pp. 123–138, 1979

    work page 1979

  7. [7]

    Strong structural controllability of linear systems revisited,

    J. C. Jarczyk, F. Svaricek, and B. Alt, “Strong structural controllability of linear systems revisited,” in Proc. 50th IEEE Conf. on Decision and Control and Eur. Control Conf. , Orlando, FL, 2011, pp. 1213–1218

    work page 2011

  8. [8]

    On strong structural controllability of networked systems, a constrained matching approach,

    A. Chapman and M. Mesbahi, “On strong structural controllability of networked systems, a constrained matching approach,” in Proc. American Control Conf. , Washington, DC, 2013, pp. 6126–6131

    work page 2013

Show all 27 references
  1. [9]

    Zero forcing sets and controllability of dynamical systems defined on graphs,

    N. Monshizadeh, S. Zhang, and M. K. Camlibel, “Zero forcing sets and controllability of dynamical systems defined on graphs,” IEEE Trans. Automat. Contr., vol. 59, no. 9, pp. 2562–2567, 2014

    2014

  2. [10]

    Zero forcing number, constrained matchings and strong structural controllability,

    M. Trefois and J.-C. Delvenne, “Zero forcing number, constrained matchings and strong structural controllability,” Linear Alg. and its Applic., vol. 484, pp. 199–218, 2015

    2015

  3. [11]

    On the structural and strong structural controllability of undirected networks,

    S. S. Mousavi, M. Haeri, and M. Mesbahi, “On the structural and strong structural controllability of undirected networks,” IEEE Trans. Automat. Contr., vol. 63, no. 7, pp. 2234–2241, 2018

    2018

  4. [12]

    Robust strong structural controllability of networks with respect to edge additions and dele- tions,

    S. S. Mousavi, M. Haeri, and M. Mesbahi, “Robust strong structural controllability of networks with respect to edge additions and dele- tions,” in Proc. American Control Conf. , 2017, pp. 5007–5012

    2017

  5. [13]

    Null space strong structural controllability via skew zero forcing sets,

    S. S. Mousavi, A. Chapman, M. Haeri, and M. Mesbahi, “Null space strong structural controllability via skew zero forcing sets,” in 2018 European Control Conf., 2018, pp. 1845–1850

    2018

  6. [14]

    Strong structural control- lability under network perturbations,

    S. S. Mousavi, M. Haeri, and M. Mesbahi, “Strong structural control- lability under network perturbations,” arXiv:1904.09960, 2019

    1904 arXiv

  7. [15]

    Controllability of multiagent networks with antagonistic interactions,

    C. Sun, G. Hu, and L. Xie, “Controllability of multiagent networks with antagonistic interactions,” IEEE Trans. Automat. Contr., vol. 62, no. 10, pp. 5457–5462, 2017

    2017

  8. [16]

    Controllability ensured leader group selection on signed multiagent networks,

    B. She, S. Mehta, C. Ton, and Z. Kan, “Controllability ensured leader group selection on signed multiagent networks,” IEEE Trans. cybernetics, 2018

    2018

  9. [17]

    Consensus problems on networks with antagonistic in- teractions,

    C. Altafini, “Consensus problems on networks with antagonistic in- teractions,” IEEE Trans. Automat. Contr., vol. 58, no. 4, pp. 935–946, 2013

    2013

  10. [18]

    Wasserman and K

    S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications. Cambridge university press, 1994, vol. 8

    1994

  11. [19]

    Sign controllability of a nonnegative matrix and a positive vector,

    C. R. Johnson, V . Mehrmann, and D. D. Olesky, “Sign controllability of a nonnegative matrix and a positive vector,”SIAM J. Matrix Analysis and Applic., vol. 14, no. 2, pp. 398–407, 1993

    1993

  12. [20]

    Sign controllability: Sign patterns that require complete controllability,

    M. J. Tsatsomeros, “Sign controllability: Sign patterns that require complete controllability,”SIAM J. Matrix Analysis and Applic., vol. 19, no. 2, pp. 355–364, 1998

    1998

  13. [21]

    Characterization of sign controllability for linear systems with real eigenvalues,

    C. Hartung, G. Reissig, and F. Svaricek, “Characterization of sign controllability for linear systems with real eigenvalues,” in 2013 Australian Contr. Conf., 2013, pp. 450–455

    2013

  14. [22]

    Zero forcing sets and the minimum rank of graphs,

    AIM Minimum Rank–Special Graphs Work Group, “Zero forcing sets and the minimum rank of graphs,” Linear Alg. and its Applic. , vol. 428, no. 7, pp. 1628–1648, 2008

    2008

  15. [23]

    Computational approaches for zero forcing and related problems,

    B. Brimkov, C. C. Fast, and I. V . Hicks, “Computational approaches for zero forcing and related problems,” Europ. J. Operational Research , vol. 273, no. 3, pp. 889–903, 2019

    2019

  16. [24]

    Zero forcing for sign patterns,

    F. Goldberg and A. Berman, “Zero forcing for sign patterns,” Linear Alg. and its Applic. , vol. 447, pp. 56–67, 2014

    2014

  17. [25]

    Sign patterns that require real, nonreal or pure imaginary eigenvalues,

    C. A. Eschenbach and C. R. Johnson, “Sign patterns that require real, nonreal or pure imaginary eigenvalues,” Linear and Multilinear Algebra, vol. 29, no. 3-4, pp. 299–311, 1991

    1991

  18. [26]

    E. D. Sontag, Mathematical Control Theory: Deterministic Finite Dimensional Systems. New York: Springer Verlag, 1998

    1998

  19. [27]

    On the minimum rank of not necessarily symmetric matrices: a preliminary study,

    F. Barioli, S. M. Fallat, H. T. Hall, D. Hershkowitz, L. Hogben, H. Van der Holst, and B. Shader, “On the minimum rank of not necessarily symmetric matrices: a preliminary study,” Electron. J. Linear Algebra, vol. 18, no. 1, pp. 126–145, 2009

    2009

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.