{"id":"91b9a4b1-41f5-4cfe-afb4-c302d9f4c3a5","arxiv_id":"1908.05797","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A split-and-refine algorithm enumerates the full lattice of invariant synchrony subspaces for sets of square and non-square matrices, unifying equitable, balanced, and tactical partition concepts.","lead":"This paper presents an algorithm that finds all coordinate-equality patterns preserved by a set of matrices, and extends the method to non-square matrices. It connects these invariant patterns, called synchrony subspaces, to equitable partitions of graphs, synchronized clusters in coupled cell networks, and tactical decompositions in design theory.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Split-and-cir pseudocode omits the coarsest invariant partition from invPartitions, so the algorithm as printed does not return the full lattice; Section 8 also lacks an explicit completeness proof.","rationale":"I verified the main mathematical steps that the reader flagged as load-bearing: the row-equality characterization in Corollary 6.5 holds, and Proposition 7.3's induction is valid. The split-and-cir enumeration is also mathematically complete once the root is included: for any invariant P below the current invariant A, a class of A can be split compatibly with P so that P lies below cir(split), giving strict progress toward P. However, the manuscript's actual pseudocode misses this root, so the central algorithmic claim is not literally supported as written. The non-square sections have additional minor proof typos: Proposition 9.6's displayed inclusion uses M on the A-coordinate rather than the needed M sys(B*) subset sys(A*), and Proposition 10.1 writes an equality M(∩ V_i) = ∩ M(V_i) that is not generally true, though the subset direction suffices. These are fixable and do not undermine the underlying mathematics. The unresolved placeholder citations and malformed companion URL are further mechanical blemishes. On balance, the paper's core theory is correct, but the algorithm's published presentation should be corrected and a completeness statement added before acceptance.","tokens_in":24802,"tokens_out":32199,"duration_ms":319917,"concrete_test":"Implement Figure 8.1 literally for n=2 and M=[[0,1],[0,0]], whose only M-invariant partition is 1|2. If invPartitions is empty upon termination, the root-omission is confirmed; a corrected algorithm should return {1|2}.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The algebraic core is sound: Corollary 6.5 and Proposition 7.3 correctly establish that the cir iteration converges to the coarsest invariant refinement, and I found no flaw in the row-equality characterization or the column-inclusion argument. The gap is in the presentation of the central algorithm, Figure 8.1. The queue is initialized with cir(singleton), but the popped partition A is never added to invPartitions; only cir(B) for lower covers B is added. Thus the coarsest invariant partition, which is the root of the lattice, is never written to the output. For example, with n=2 and M=[[0,1],[0,0]], the only M-invariant partition is 1|2, and since 1|2 has no lower covers, the printed algorithm returns an empty set. The same root-omission occurs in the tactical-decomposition version in Section 11. Additionally, Section 8 gives no theorem stating that repeated splitting plus cir visits every invariant partition; the claim is only argued informally. The missing completeness argument is easy to supply by splitting a class compatibly with any target invariant partition and applying cir, but as written the central claim that the algorithm finds the full lattice is over-stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops the theory of synchrony subspaces invariant under a finite set of square matrices, identifying these subspaces with partitions of {1,...,n} that are invariant under each matrix. It proves that the invariant partitions form a lattice, surveys a broad range of applications (equitable and almost equitable graph partitions, balanced and exo-balanced cell-network partitions, Cayley graphs, weighted networks, network controllability, and finite-difference PDE discretizations), and introduces the cir algorithm for computing the coarsest invariant refinement of a given partition (Proposition 7.3) together with the split-and-cir algorithm for computing the full lattice of invariant partitions (Section 8). The framework is then extended to non-square matrices, where the analogue is the lattice of tactical decompositions, with matching algorithms in Sections 9--11.","tokens_in":25007,"tokens_out":5885,"duration_ms":60803,"significance":"The algebraic core of the paper is sound and valuable. Corollary 6.5 gives a clean row-equality characterization of invariance, and Propositions 7.3 and 10.3 provide explicit, checkable convergence proofs for the cir iteration. The applications section successfully unifies several independently studied notions under a single lattice-theoretic umbrella, and the companion website and examples give concrete evidence that the algorithms are usable. However, the central algorithmic contribution as printed in Figure 8.1 and Section 11 has load-bearing presentation gaps: the pseudocode omits the coarsest invariant partition from the output, does not guard against revisiting already-processed partitions, and Section 8 gives no explicit completeness proof for the split-and-cir traversal. These issues are local and readily fixable, but they must be corrected before the claimed 'split and cir algorithm finds this lattice' can be accepted as stated.","major_comments":[{"comment":"The pseudocode never inserts the coarsest invariant partition into invPartitions. The queue is initialized with cir(A), and the loop only adds cir(B) for lower covers B; the popped partition A is not added to invPartitions. Thus the top element of the lattice is omitted from the output. In a case where the coarsest invariant partition is the only invariant partition (for example, n=2 with M=[[0,1],[0,0]]), the printed algorithm returns an empty set. The same omission occurs in the tactical-decomposition version described in Section 11, where the initial cirM(A,A) is never added to the output. The fix is to add the popped partition to invPartitions when it is processed, or to add the initial cir(A) to invPartitions before the loop.","section":"§8, Figure 8.1"},{"comment":"The guard 'if B is not in queue' is not sufficient to prevent duplicate processing or non-termination. If the same invariant partition is generated from two different parents, it may be added to invPartitions and pushed onto the queue twice. Once it has been popped and processed, it is no longer in the queue; if it is generated again later, the condition 'B is not in queue' is true and the partition is added and pushed again, potentially leading to duplicate output or an infinite loop. The algorithm needs a visited/discovered set, for example testing membership in invPartitions as well as in the queue, before adding and pushing B.","section":"§8, Figure 8.1"},{"comment":"There is no explicit completeness theorem stating that repeated splitting plus cir visits every M-invariant partition. The prose in Section 8 argues this informally, but the central claim of the paper is that the algorithm finds the full lattice. A short inductive proof should be supplied: for any target invariant partition Q and any current invariant partition A with Q <= A, if Q is not equal to A then some class of A is split in Q, giving a lower cover B of A with Q <= B; since Q is invariant and Q <= B, Q <= cir(B); one then continues inductively inside the down-set of cir(B). The base case is the root cir(singleton). Adding this argument, with a corresponding statement for the tactical-decomposition algorithm in Section 11, would make the algorithmic claim precise.","section":"§8"}],"minor_comments":[{"comment":"The text contains unresolved citation placeholders '[?]' in Conjecture 5.6 and in the discussion after Example 8.3; these should be replaced with actual references or removed.","section":"§5.1 and §8.3"},{"comment":"Reference [31] contains a typo: 'Unversity' should be 'University'.","section":"References"},{"comment":"The phrase 'NP-complete problem of finding the lattice of invariant partitions' is stated without a citation or proof. If this complexity claim is intended, it should be substantiated; otherwise it should be softened.","section":"§1"},{"comment":"The two-line permutation notation used to describe the self-duality is not introduced; a sentence explaining the notation would improve readability.","section":"§11, Example 11.2"},{"comment":"The symbol 'Pm @Pn' appears to be a rendering artifact for the Cartesian product; it would be clearer to use the standard notation Pm □ Pn consistently.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The mathematical core of the paper is sound, and the algorithmic ideas are correct in substance. The remaining issues are concentrated in the presentation of the split-and-cir pseudocode and the missing completeness argument; they are fixable within the scope of a revision. I would be comfortable seeing the paper accepted once the pseudocode is corrected and the completeness proof is added."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this is a solid, useful paper. The split-and-cir algorithm for enumerating all invariant synchrony subspaces for finite sets of matrices is the actual contribution, and the main convergence proofs hold up. The non-square/tactical-decomposition extension is genuinely new, as is the recursive split-and-cir combination for multiple matrices. The authors are also honest about what is inherited: the cir step is a slight generalization of color refinement in [22,49], and [27] already computed lattices by brute force with cir.\n\nWhat the paper does well: the algebraic core is clean. Corollary 6.5's row-equality characterization is correct, and the induction in Proposition 7.3 is explicit enough to follow. I checked the step where sys(cirM(A)) contains M_i sys(A_k): it works because invariance gives M_i sys(cirM(A)) subset sys(cirM(A)) and linear images preserve the already known inclusion. The applications section is broad without being padded; balanced/exo-balanced partitions, Cayley coset partitions, Laplacian almost-equitable partitions, and the controllability connection are placed in one framework. That is worth having.\n\nThe soft spot is real but mechanical. The pseudocode in Figure 8.1 never adds the popped invariant partition to invPartitions. It pushes cir(singleton), pops it, and only adds cir(B) for lower covers B. So the coarsest invariant partition, the root of the lattice, is missing from the output. With n=2 and M=[[0,1],[0,0]], the only invariant partition is 1|2, which has no lower covers; the printed algorithm returns the empty set. The same root omission appears in the tactical-decomposition description in Section 11. This is not a flaw in the mathematics, but it is a flaw in the statement of the central algorithm. It needs a one-line fix and a regression test.\n\nThe other soft spot is that Section 8 gives no explicit completeness theorem for split-and-cir. The paper says the queue process finds all invariant partitions but does not prove it. The missing argument is short: if C is invariant and A is a current invariant partition above C, split a class of A into two unions of C-classes to get a lower cover B with C <= B < A; then cir(B) is invariant, coarser than B, and still above C. Induction gives C. I would want that written down.\n\nMinor: there are placeholder [?] citations and the companion URL contains a comma. Those are copyedit level. The claimed running times are empirical; the paper does not oversell them.\n\nWho for: anyone computing equitable partitions, working on coupled cell networks, or needing to enumerate invariant synchrony subspaces. The paper deserves a serious referee and, after a short revision, acceptance. The central claims are sound; the defects are presentational and easily fixed.","headline":"Sound and useful paper: the split-and-cir algorithm is the real contribution, but the printed pseudocode omits the root partition and Section 8 lacks an explicit completeness proof.","tokens_in":25527,"tokens_out":4049,"would_cite":true,"duration_ms":38569,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A72","34C14","34C15","37C80","06B23","90C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Invariant synchrony subspaces of a set of matrices form a computable lattice, and a split-and-cir algorithm finds all of them.","keywords":["coupled cell network","synchrony subspace","equitable partition","almost equitable partition","balanced partition","exo-balanced partition","tactical decomposition","split and cir algorithm"],"falsifier":"Take a small digraph, for instance the 7-vertex example of Section 8.1, run the split-and-cir code, and compare its output against an exhaustive check of all 877 partitions of 7 elements: any missing invariant partition, or any returned partition $A$ with $M\\,\\mathrm{sys}(A)\\not\\subseteq \\mathrm{sys}(A)$, would refute the completeness claim. A more direct test would be to pick random partitions and matrices and brute-force check the equivalence $A\\in\\Pi_M \\iff A\\le \\psi([M_1P(A)\\ \\cdots\\ M_rP(A)])$.","tokens_in":24600,"feed_emoji":"🧮","tokens_out":11313,"duration_ms":95937,"temperature":0.7,"pith_summary":"This paper shows that the subspaces of $\\mathbb{R}^n$ obtained by forcing certain coordinates to be equal—the synchrony subspaces—and preserved by every matrix in a finite set form a lattice, and that this lattice can be computed in practice. The main contribution is the split and cir algorithm: a color-refinement iteration that provably returns the coarsest invariant refinement of any partition, combined with a recursive splitting step that visits every invariant partition. The same machinery extends to non-square matrices, where the invariant objects are the tactical decompositions of incidence structures. This unifies computations for equitable and almost equitable graph partitions, balanced and exo-balanced coupled-cell partitions, and coset partitions of Cayley graphs.","feed_headline":"A refinement loop enumerates all invariant synchrony subspaces","feed_subtitle":"For any finite set of matrices, including non-square ones, the lattice of such subspaces can be computed exactly.","key_machinery":"The load-bearing objects are the characteristic matrix $P(A)$ of a partition (columns are the indicator vectors of its classes) and the induced partition $\\psi(Q)$ that identifies rows that are equal in a matrix $Q$. Corollary 6.5 provides the row-equality test that makes the algorithm work: $A$ is invariant under $M$ if and only if $A$ is finer than the partition induced by the rows of $[M_1P(A)\\ \\cdots\\ M_rP(A)]$. The cir iteration applies this test repeatedly, producing a descending chain in the finite partition lattice, and the test guarantees that the terminal partition actually is invariant. In implementation the algorithm works directly with coloring vectors and computes $MP(A)$ by adding matrix entries into color classes, avoiding explicit matrix multiplication.","core_discovery":"The central claim is that, for any finite set of matrices $M=\\{M_1,\\ldots,M_r\\}\\subseteq \\mathbb{R}^{n\\times n}$, a partition $A$ is $M$-invariant exactly when $A\\le \\psi([M_1P(A)\\ \\cdots\\ M_rP(A)])$, where $P(A)$ is the characteristic matrix of the partition and $\\psi(Q)$ groups equal rows of $Q$. Proposition 7.3 turns this characterization into an algorithm: starting from any partition, iterate $A_{k+1} = A_k \\wedge \\psi([M_1P(A_k)\\ \\cdots\\ M_rP(A_k)])$ until it stabilizes; the fixed point is the coarsest $M$-invariant refinement. Section 8 combines this cir map with class splitting to enumerate the whole lattice of invariant partitions without brute-force over all partitions. For non-square matrices the analogous iteration (Proposition 10.3) converges to the coarsest tactical decomposition. If these results are correct, the algorithm gives an exact, integer-only method for a problem previously approached by exponential brute force.","pith_inferences":["The row-equality characterization suggests a symbolic variant: for matrices whose entries are polynomials in parameters, the same iteration could compute parameter-dependent invariant subspaces, which would be useful in bifurcation problems.","Because the algorithm operates on coloring vectors, the queue of splits can be processed in parallel, potentially scaling to very large grids or networks where the full Bell number is intractable.","The non-square version could be applied directly to bipartite graphs and hypergraphs, where equitable partitions of the two sides are coupled; this would give a unified way to compute equitable partitions of incidence structures.","The authors' observation that cell-type partitions can be replaced by loop arrows suggests a simple preprocessing step that lets network-control analysis use the multi-matrix algorithm unchanged."],"forward_implications":["For any finite set of square matrices, the lattice of invariant synchrony subspaces can be enumerated exactly, with no need to check every Bell-many partition.","Equitable partitions of a graph are exactly the adjacency-matrix-invariant partitions, and almost equitable partitions are the Laplacian-invariant ones, so the algorithm computes both from a single procedure.","Balanced partitions of a coupled cell network are exactly the robustly polysynchronous partitions, so the algorithm lists all possible robust cluster patterns.","For non-square matrices the same approach computes all tactical decompositions, giving a computational handle on incidence structures and design theory.","The observed running time scales roughly exponentially in the size of the coarsest invariant partition, so the method is practical when refinement does substantial work and degrades to brute force (e.g., complete graphs)."],"supporting_citations":[{"why":"Supplies the original coarsest-invariant-refinement (cir) procedure for a single matrix, which Proposition 7.3 generalizes to sets of matrices.","marker":"[49]"},{"why":"Along with [22], inspired the efficient implementation of the cir iteration.","marker":"[48]"},{"why":"Provides the induced-partition notation $\\psi(Q)$ and the standard fact that equitable partitions are adjacency-matrix-invariant.","marker":"[22]"},{"why":"Gives the closest prior algorithm—enumerating the invariant lattice by brute-force checks—which the split-and-cir algorithm is designed to outperform.","marker":"[27]"},{"why":"Characterizes the lattice of synchrony subspaces of a coupled cell network and supplies the prior computation algorithm this paper extends.","marker":"[1]"},{"why":"Establishes that balanced partitions are exactly the robustly polysynchronous partitions, grounding the main application to coupled cell networks.","marker":"[25]"},{"why":"Proves that Laplacian-invariant partitions are the almost equitable partitions, which the algorithm computes as a special case.","marker":"[15]"},{"why":"Provides the theorem that balanced partitions of weighted cell networks are the invariant partitions of the weighted adjacency matrix.","marker":"[3]"}],"fun_headline_variants":["Exact algorithm enumerates all invariant synchrony subspaces","Refinement loop computes full lattice of invariant subspaces","Matrix sets: enumerate invariant subspaces without brute force","New method finds invariant synchrony subspaces exactly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the row-equality characterization—a partition is invariant exactly when its classes match the row-equality classes of $[M_1P(A)\\ \\cdots\\ M_rP(A)]$—so if that equivalence failed, the iteration could stop at a non-invariant partition.","fun_headline_variants_meta":{"raw":{"variants":["Exact algorithm enumerates all invariant synchrony subspaces","Refinement loop computes full lattice of invariant subspaces","Matrix sets: enumerate invariant subspaces without brute force","New method finds invariant synchrony subspaces exactly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000184,"raw_usage":{"total_tokens":1295,"prompt_tokens":901,"completion_tokens":394,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":517,"completion_tokens_details":{"reasoning_tokens":331}},"tokens_in":517,"tokens_out":394,"duration_ms":3752,"temperature":1.0,"reasoning_tokens":331,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:04:24.758562+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small digraph, for instance the 7-vertex example of Section 8.1, run the split-and-cir code, and compare its output against an exhaustive check of all 877 partitions of 7 elements: any missing invariant partition, or any returned partition $A$ with $M\\,\\mathrm{sys}(A)\\not\\subseteq \\mathrm{sys}(A)$, would refute the completeness claim. A more direct test would be to pick random partitions and matrices and brute-force check the equivalence $A\\in\\Pi_M \\iff A\\le \\psi([M_1P(A)\\ \\cdots\\ M_rP(A)])$.","supporting_citations":[{"cited_title":"Kanat Camlibel","cited_arxiv_id":null,"evidence_quote":"Supplies the original coarsest-invariant-refinement (cir) procedure for a single matrix, which Proposition 7.3 generalizes to sets of matrices."},{"cited_title":"Kanat Camlibel, and Ming Cao","cited_arxiv_id":null,"evidence_quote":"Along with [22], inspired the efficient implementation of the cir iteration."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the closest prior algorithm—enumerating the invariant lattice by brute-force checks—which the split-and-cir algorithm is designed to outperform."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Characterizes the lattice of synchrony subspaces of a coupled cell network and supplies the prior computation algorithm this paper extends."},{"cited_title":"Patterns of synchrony in coupled cell networks with multiple arrows.SIAM J","cited_arxiv_id":null,"evidence_quote":"Establishes that balanced partitions are exactly the robustly polysynchronous partitions, grounding the main application to coupled cell networks."},{"cited_title":"Cardoso, Charles Delorme, and Paula Rama","cited_arxiv_id":null,"evidence_quote":"Proves that Laplacian-invariant partitions are the almost equitable partitions, which the algorithm computes as a special case."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the theorem that balanced partitions of weighted cell networks are the invariant partitions of the weighted adjacency matrix."}],"review_version":1}