{"id":"edaf9da3-5623-4917-8138-3e737060577c","arxiv_id":"1908.05732","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper introduces positive and negative signed zero forcing sets and shows that, when the sign pattern admits only real eigenvalues, a signed network is strongly structurally controllable if the control nodes form a signed, positive signed, and negative signed zero forcing set.","lead":"This paper develops coloring games on signed networks to test whether the networks can be controlled. It gives a sufficient condition for strong structural controllability that handles positive, negative, and zero eigenvalues separately.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1 is false: clause 1 can blacken a white vertex v through its own self-loop while ν_v(A_vv−λ)=0 allows ν_v≠0. This yields a two-node signed graph where a positive signed zero forcing set fails to make a positive eigenvalue controllable, disproving Theorem 2.","rationale":"The reader's conditional verdict pointed to rule 3 and zero eigenvector entries; that is one gap, but the decisive failure is in clause 1, which supports a concrete counterexample. I verified the zero-forcing game on the two-node directed signed graph: with Z={1}, rule 4 marks node 2, then clause 1 with v=2 white and W(2)={2} blackens node 2, making Z a positive signed zero forcing set. For A=[[2,1],[0,1]] with B=e1, λ=1 has left eigenvector w=[0,1] and w^T B=0, so the eigenvalue is uncontrollable although the theorem predicts it is strongly structurally controllable. The flaw traces to the proof of Lemma 1: equation (3) for v white with a self-loop includes ν_v(A^+_{vv}−λ), which vanishes for λ=A^+_{vv} without forcing ν_v=0, contrary to the proof's assertion ν_v A^+_{vv}=0. Because Theorem 2 is the paper's central contribution and is false as stated for directed signed graphs, the appropriate verdict is REJECT, unless the authors restrict the scope and re-prove the result. The paper's upper-bound Proposition 2 depends on the same Lemma 1 and is likewise unsupported. I found no basis to accuse the authors of anything beyond a genuine mathematical gap; the counterexample is explicit and checkable.","tokens_in":10509,"tokens_out":16626,"duration_ms":152275,"concrete_test":"Implement the two-node check exactly: graph with V={1,2}, edge (2,1) labeled +, P_s entries ?, and initial black set Z={1}. Run the signing/coloring rule on G^+_s; confirm that rule 4 marks node 2 with + and then clause 1 (white node 2 with self-loop) blackens node 2. Then set A=[[2,1],[0,1]], B=e_1, and apply the PBH test to λ=1: the left eigenvector [0,1] satisfies w^T B=0. If this reproduces, Lemma 1 and Theorem 2 fail; a revised paper must either restrict to undirected/symmetric graphs or fix clause 1 by ensuring self-loop-forcing steps only blacken nodes already known to have zero eigenvector entries.","verdict_should_be":"REJECT","load_bearing_attack":"Lemma 1 is the load-bearing step for Theorem 2: it claims that once Z is black, any left eigenvector of a positive eigenvalue that vanishes on Z must vanish on the whole positive derived set. The proof of clause 1 of the signing/coloring rule is invalid when the unique white out-neighbor is the vertex itself. In that case v is white and W(v)={v}; equation (3) for column v reduces to ν_v(A^+_{vv}−λ)=0, which does not imply ν_v=0 when the loop weight equals λ. The paper drops the ν_v(A^+_{vv}−λ) term and asserts ν_v A^+_{vv}=0. This is not a mere technicality: take V={1,2}, a positive edge 2→1, and ? self-loops on both nodes, with A=[[2,1],[0,1]]∈Q_s(G_s), B=e_1. The positive looped game blackens {1}; rule 4 marks node 2 with +, then clause 1 applied to white node 2 (self-loop) colors node 2 black, so {1} is a positive signed zero forcing set. Yet λ=1 is a positive eigenvalue of A with left eigenvector w=[0,1], and w^T B=0, so the eigenvalue is uncontrollable. Thus Theorem 2 is false for directed signed graphs as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10879,"tokens_out":6663,"duration_ms":63948,"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":[{"comment":"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.","section":"Section IV, Lemma 1, clause 1 of the signing and coloring rule"},{"comment":"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.","section":"Section IV, Lemma 1, rules 2 and 3 of the signing and coloring rule"},{"comment":"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.","section":"Section IV, Lemma 1, setup after equation (3)"},{"comment":"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.","section":"Section IV, Theorem 2 and Theorem 3"}],"minor_comments":[{"comment":"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.","section":"Section IV, proof of Theorem 2"},{"comment":"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.","section":"Section II, Example 1"},{"comment":"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.","section":"Section IV, proof of Lemma 1"},{"comment":"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.","section":"Section III, Definition 4"}],"recommendation":"reject","confidential_remarks":"The main theorem is disproved by a simple two-node counterexample, so the central contribution is invalid. The self-loop issue in Lemma 1 is not a local gap; it affects the definition of the positive/negative zero forcing game and the main controllability theorems. The authors may be able to repair the result by excluding '?' self-loops or by modifying the game to track A_ii − λ, but such a repair would require reworking the main definitions and proofs, which is beyond a revision of this manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main take: Theorem 2 is false for directed signed graphs as stated. The stress-test counterexample is real: two nodes, a positive edge 2→1, B=e1, and A=[[2,1],[0,1]] lies in the qualitative class. λ=1 is a positive eigenvalue with left eigenvector [0,1], orthogonal to B, so it is uncontrollable. Yet {1} is a positive signed zero forcing set because the self-loop on node 2 makes node 2 its own unique white out-neighbor, and clause 1 blackens it. Lemma 1's proof of clause 1 drops the −λ term: the equation is ν_v(A^+_{vv}−λ)=0 when u=v, which does not imply ν_v=0. That is not a minor typo; it breaks the induction carrying zero entries along the forcing chain.\n\nCredit where it is due: positive and negative signed zero forcing sets are new constructs, and the idea of using zero forcing games for eigenvalue-specific strong structural controllability is a natural extension of the Trefois–Delvenne characterization. The paper engages honestly with the relevant literature (Goldberg–Berman, Tsatsomeros) and the high-level approach is plausible for undirected or self-loop-free signed graphs. Proposition 2 would follow cleanly if Lemma 1 were fixed.\n\nThe other soft spot the reader flagged is also genuine: in rule 3, the proof assumes that previously marked nodes' signs match nonzero eigenvector entries, but the game can mark a node based on a node whose eigenvector entry is zero. The paper never justifies that step. So there are two unresolved gaps, one fatal for directed graphs and one affecting the general induction.\n\nPossible fixes: restrict the main theorem to signed graphs without self-loops, modify the forcing rule so a self-loop cannot force itself, or add an explicit exclusion of loop weights equal to the eigenvalue. For undirected signed graphs the counterexample does not transfer, and the result may well be correct there. But as written, the claim overreaches.\n\nWho this is for: researchers in zero forcing and strong structural controllability. The definitions and the eigenvalue-specific framing are worth knowing. A serious referee could salvage the idea, so I would send it out rather than desk-reject, with the clear expectation of major revision. Recommendation: accept for peer review as a conditional advance; the counterexample belongs in the referee report.","headline":"Theorem 2 fails for directed signed graphs because Lemma 1 mishandles self-loops; the signed zero forcing idea is still worth a serious look.","tokens_in":11261,"tokens_out":2736,"would_cite":false,"duration_ms":27040,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["93B05","05C50","15A18","93C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A combinatorial game on signed graphs decides which eigenvalues of a network are strongly structurally controllable.","keywords":["signed networks","strong structural controllability","signed zero forcing","sign pattern","LTI systems","eigenvalue controllability","geometric multiplicity"],"falsifier":"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.","tokens_in":10342,"feed_emoji":"🎯","tokens_out":4929,"duration_ms":47099,"temperature":0.7,"pith_summary":"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.","feed_headline":"Signed zero forcing sets guarantee eigenvalue controllability","feed_subtitle":"A combinatorial game tells you which control nodes make every positive, negative, or zero eigenvalue controllable.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the classical result that controllability of a graph is equivalent to the control set being both a classical and a strong zero forcing set, the template that the signed games extend.","marker":"[10]"},{"why":"Introduces the signed zero forcing game and the same-sign summand argument that Lemma 1 adapts for positive and negative eigenvalues.","marker":"[24]"},{"why":"Provides the zero-forcing/minimum-rank framework and the geometric-multiplicity argument reused in Proposition 2.","marker":"[22]"},{"why":"Defines sign controllability and gives the restrictive algebraic conditions that the paper's combinatorial test avoids.","marker":"[20]"},{"why":"Characterizes sign patterns that require real eigenvalues, the hypothesis needed for the full-network controllability statement in Theorem 3.","marker":"[25]"},{"why":"States the PBH test for eigenvalue controllability, which is the algebraic criterion that the zero forcing sets are designed to satisfy.","marker":"[26]"}],"fun_headline_variants":["Eigenvalue controllability via signed zero forcing games","Signed graph game certifies every eigenvalue controllable","Positive and negative eigenvalues yield to zero forcing","Zero forcing sets decide signed network controllability"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Eigenvalue controllability via signed zero forcing games","Signed graph game certifies every eigenvalue controllable","Positive and negative eigenvalues yield to zero forcing","Zero forcing sets decide signed network controllability"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000498,"raw_usage":{"total_tokens":2377,"prompt_tokens":819,"completion_tokens":1558,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":435,"completion_tokens_details":{"reasoning_tokens":1501}},"tokens_in":435,"tokens_out":1558,"duration_ms":11077,"temperature":1.0,"reasoning_tokens":1501,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:06:05.639007+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Zero forcing number, constrained matchings and strong structural controllability,","cited_arxiv_id":null,"evidence_quote":"Supplies the classical result that controllability of a graph is equivalent to the control set being both a classical and a strong zero forcing set, the template that the signed games extend."},{"cited_title":"Zero forcing for sign patterns,","cited_arxiv_id":null,"evidence_quote":"Introduces the signed zero forcing game and the same-sign summand argument that Lemma 1 adapts for positive and negative eigenvalues."},{"cited_title":"Zero forcing sets and the minimum rank of graphs,","cited_arxiv_id":null,"evidence_quote":"Provides the zero-forcing/minimum-rank framework and the geometric-multiplicity argument reused in Proposition 2."},{"cited_title":"Sign controllability: Sign patterns that require complete controllability,","cited_arxiv_id":null,"evidence_quote":"Defines sign controllability and gives the restrictive algebraic conditions that the paper's combinatorial test avoids."},{"cited_title":"Sign patterns that require real, nonreal or pure imaginary eigenvalues,","cited_arxiv_id":null,"evidence_quote":"Characterizes sign patterns that require real eigenvalues, the hypothesis needed for the full-network controllability statement in Theorem 3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the PBH test for eigenvalue controllability, which is the algebraic criterion that the zero forcing sets are designed to satisfy."}],"review_version":1}