Invariant synchrony subspaces of sets of matrices

James W. Swift; John M. Neuberger; Nandor Sieben

REVIEW 3 major objections 5 minor 51 references

Invariant synchrony subspaces of sets of matrices

T0 review · 3 major / 5 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 Invariant synchrony subspaces of a set of matrices form a computable lattice, and a split-and-cir algorithm finds all of them.

desk verdict 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. read the letter →

arxiv 1908.05797 v2 pith:6D36NFCM submitted 2019-08-15 math.DS math.CO

John M. Neuberger , Nandor Sieben , James W. Swift This is my paper · ORCID

classification math.DSmath.CO MSC 15A7234C1434C1537C8006B2390C35

keywords coupledcellnetworksynchronysubspaceequitablepartitionalmostbalancedexo-balancedtacticaldecompositionsplitandciralgorithm

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 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.

What carries the argument

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.

What would settle it

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)])$.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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).

Reading between the lines

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

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.

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.

Desk Editor's Note

read the 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.

What 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.

The 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.

The 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.

Minor: 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.

Who 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.

Referee Report

3 major / 5 minor

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.

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 (3)

[§8, Figure 8.1] 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.
[§8, Figure 8.1] 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.
[§8] 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.

minor comments (5)

[§5.1 and §8.3] 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.
[References] Reference [31] contains a typo: 'Unversity' should be 'University'.
[§1] 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.
[§11, Example 11.2] The two-line permutation notation used to describe the self-duality is not introduced; a sentence explaining the notation would improve readability.
[Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the cir convergence proof is self-contained, and self-citations are motivational only.

full rationale

The paper's load-bearing mathematical claim is Proposition 7.3, which proves that the iterated refinement A_{k+1} = psi([P(A_k) | M_1 P(A_k) ... M_r P(A_k)]) converges to cir_M(A) = join(Π_M(n) ∩ downset(A)). The proof is a direct argument from the row-equality characterization in Corollary 6.5, Proposition 6.1, and Lemma 6.2, all of which are proved in the text rather than imported from the authors' prior work. No parameter is fitted and no output quantity is an input by construction. The characterization in Corollary 6.5 is derived from Proposition 6.4, whose proof is included. Self-citations [34]-[37] and [39] appear only as motivation and application context in Sections 5.5 and 5.7, and do not support the convergence or correctness of the main algorithm. The closest algorithmic antecedent, [49], is external work by other authors and is explicitly credited as an inspiration rather than used as a black-box justification. The split-and-cir lattice search in Section 8 combines splitting with cir recursively; even if the printed pseudocode has a presentation gap concerning the root invariant partition, that is a correctness or completeness issue, not circularity. The mathematical derivation of the cir algorithm is self-contained and does not reduce to its own inputs by definition or through a self-citation chain.

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

No free parameters are fitted and no new entities are postulated. The central claims rest on standard lattice-theoretic and linear-algebra facts, mostly cited explicitly. The imported cell-network theorem [25, Theorem 4.3] is a domain assumption linking the formalism to applications, but the algorithm proofs do not depend on it.

assumptions (4)

standard math Every finite poset in which all joins exist is a complete lattice.
Used in Propositions 4.5 and 9.7 to derive lattice structure from closure under joins; cited to [26, Lemma 34].
standard math sys(⋁S) = ∩_{A∈S} sys(A) for collections of partitions.
Used in Propositions 3.5, 4.3, and 7.1 to show joins of invariant partitions remain invariant; imported from [48, Lemma 2].
domain assumption Balanced partitions of coupled cell networks are exactly robustly polysynchronous partitions.
Connects the matrix-invariance formalism to network synchrony in Section 5.2; cited to [25, Theorem 4.3].
standard math The row-equality and column-inclusion criteria in Proposition 6.4 and Lemma 6.2 characterize M-invariance.
This is proved in the paper with an elementary RREF argument; it is the algebraic foundation of the cir algorithm.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Invariant synchrony subspaces of sets of matrices." pith.science (2026). https://pith.science/paper/6D36NFCM

@misc{pith2026190805797,
  author       = {Pith},
  title        = {Pith review of: Invariant synchrony subspaces of sets of matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6D36NFCM}},
  note         = {Machine review of arXiv:1908.05797}
}

read the original abstract

A synchrony subspace of R^n is defined by setting certain components of the vectors equal according to an equivalence relation. Synchrony subspaces invariant under a given set of square matrices form a lattice. Applications of these invariant synchrony subspaces include equitable and almost equitable partitions of the vertices of a graph used in many areas of graph theory, balanced and exo-balanced partitions of coupled cell networks, and coset partitions of Cayley graphs. We study the basic properties of invariant synchrony subspaces and provide many examples of the applications. We also present what we call the split and cir algorithm for finding the lattice of invariant synchrony subspaces. Our theory and algorithm is further generalized for non-square matrices. This leads to the notion of tactical decompositions studied for its application in design theory.

Figures

Figures reproduced from arXiv: 1908.05797 by the authors.

**Figure 4.1.** A matrix M and the lattice of M-invariant partitions. 1 2 3 4 5 a b a b a a b b a b a b c d c A5 A8 A5 ∧ A8 balanced balanced not balanced [PITH_FULL_IMAGE:figures/full_fig_p005_4_1.png] view at source ↗

**Figure 4.2.** Balanced partitions whose infimum in Π is not balanced. Proof. We verify the conditions of Proposition 4.4. The discrete partition is invariant under any M, so it is the bottom element of ΠM(n). Let ∅ 6= S ⊆ ΠM(n) and W S be the supremum of S taken in the lattice Π(n). Then W S ∈ ΠM(n) by Proposition 4.3. So the supremum of S in ΠM(n) is W S. Example 4.6 [PITH_FULL_IMAGE:figures/full_fig_p005_4_2.png] view at source ↗

**Figure 4.** shows a matrix [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗

Figures from the paper (27 more)

**Figure 5.1.** Figure 5.1: (i) Graph G. (ii) The coarsest equitable partition A1 of G. (iii) The quotient digraph G/A1. equitable partitions are of this type. Equitable partitions can be used to create quotient digraphs. If i is a vertex of a digraph, then the neighborhood of i is denoted by N…

**Figure 5.** Figure 5: (ii) shows the coarsest of the eight equitable partitions of the graph [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]

**Figure 5.2.** Figure 5.2: Equitable partitions. (i) The coarsest equitable partition of P4@ P2. (ii) The coarsest equitable partition of P4 @ P4 . (iii) The orbit partition of the Z4 action on P4 @ P4. partitions is isomorphic to the lattice of subgroups exactly when there is a vertex with tr…

**Figure 5.3.** Figure 5.3: (i) A coupled cell network. (ii) Balanced partitions. (iii) Lattice of balanced partitions. Example 5.7. The matrix of Example 4.6 shown in [PITH_FULL_IMAGE:figures/full_fig_p008_5_3.png]

**Figure 5.** Figure 5: shows the balanced partitions of a cell network with a single [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]

**Figure 5.4.** Figure 5.4: (i) A coupled cell network with two cell types and two arrow types. (ii) M-invariant partitions. (iii) Lattice of M-invariant partitions, with the balanced partitions for the network circled. (iv) Another coupled cell network with only one cell type and four arrow ty…

**Figure 5.** Figure 5: (iv) shows another coupled cell network whose balanced partitions are also [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]

**Figure 5.5.** Figure 5.5: (i) The Cayley color digraph Cay{i,j} (Q8) of the quaternion group Q8 and its lattice of subgroups. A solid arrow of the Cayley digraph is colored with i while a dotted arrow is colored with j. (ii) The balanced partitions of the cell network. (iii) The corresponding…

**Figure 5.6.** Figure 5.6: A graph and its almost equitable partitions. The boxed partitions are equitable. gig −1 j along the edges colored with s1, . . . , sk respectively leads to gig −1 j s1 · · · sk = gi . Since [gi ] = [gj ], the repeated application of Lemma 5.18 implies that [e] = [gj…

**Figure 5.** Figure 5: shows a graph with its almost equitable partitions. Only par [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]

**Figure 5.7.** Figure 5.7: Three of the 13 almost equitable, but not equitable, partitions of P4P4. 1 2 3 123 12|3 1|2|3 A1 A2 A3 [PITH_FULL_IMAGE:figures/full_fig_p012_5_7.png]

**Figure 5.** Figure 5: shows a coupled cell network and its exo-balanced partitions. [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]

**Figure 5.9.** Figure 5.9: (i) Weighted cell network G. Weights of 1 are not printed. (ii) Weighted cell network GL. (iii) Balanced partitions of GL and exo-balanced partitions of G. Definition 5.34. Consider a weighted coupled cell network with weighted adjacency matrix W. A cell partition A …

**Figure 5.** Figure 5: (i) shows a weighted cell network [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]

**Figure 7.1.** Figure 7.1: Efficient computation of MP(A) using c(A) avoiding the computation of P(A). k Ak c(Ak) P(Ak) [PITH_FULL_IMAGE:figures/full_fig_p019_7_1.png]

**Figure 7.2.** Figure 7.2: The steps of the cir algorithm, starting with A0 = 14|235. The third and fifth rows of [c(A2) | Q2] are equal, so A2 = A3 = cir(A0). If the matrices in M are sparse, then a further speedup is possible with a modification of the code segment that uses sparse matrix re…

**Figure 7.** Figure 7: shows the steps for finding [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]

**Figure 8.1.** Figure 8.1: The split and cir algortihm for finding the M-invariant partitions. 8. The split and cir algorithm for finding the lattice of invariant partitions Proposition 2.3 and the cir algorithm can be combined into a split and cir algorithm to find all M-invariant partitions …

**Figure 8.** Figure 8: shows the steps of our algorithm to find the 4 balanced partitions [PITH_FULL_IMAGE:figures/full_fig_p020_8.png]

**Figure 8.2.** Figure 8.2: (i) A cell network and its in-adjacency matrix. (ii) Steps in the split and cir algorithm for finding the lattice of balanced partitions. Straight arrows point to lower covers, corresponding to splits. Squiggly arrows show the steps from Ak to Ak+1 in the cir algorit…

**Figure 9.1.** Figure 9.1: (i) The star graph K1,3 and its incidence graph. (ii) The tactical decompositions of the incidence matrix. (iii) Lattice of tactical decompositions. partition is the discrete partition, then our algorithm does no splitting. Our split and cir algorithm performs best …

**Figure 9.** Figure 9: (i) shows the star graph [PITH_FULL_IMAGE:figures/full_fig_p022_9.png]

**Figure 9.2.** Figure 9.2: (i) Edge colored incidence graph of an incidence structure. (ii) Tactical decompositions of M = {M1, M2}. (iii) Lattice of tactical partitions. 1 2 1 2 [ 1 0 0 1 ] [ 0 1 1 0 ] 12 12 (A1, B1) 1|2 1|2 (A2, B2) (A2,B2) (A1,B1) 1 2 3 4 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 …

**Figure 9.3.** Figure 9.3: (i) Edge colored incidence graph K2,2. (ii) Tactical decompositions. (iii) Lattice of tactical decompositions. (iv) Cell network on K2,2 with two cell and arrow types. (v) M-invariant partitions. (vi) Lattice of M-invariant partitions with balanced partitions circle…

**Figure 11.1.** Figure 11.1: (i) The Fano plane. (ii) The incidence matrix M. (iii) The incidence graph of the Fano plane. a b b c a a a 1234567 1234567 1234|56|7 16|2345|7 12|34|56|7 1|2345|6|7 (A1, B1) (A4, B4) (A7, B7) 123456|7 167|2345 1234|5|6|7 16|25|34|7 12|34|5|6|7 1|25|34|6|7 (A2, B2) …

**Figure 11.2.** Figure 11.2: (i) The tactical decomposition (A4, B4). (ii) Orbit representatives of the tactical decompositions of M. (iii) The tactical decomposition (A4, B4) on the incidence graph. 11. Finding the lattice of tactical decompositions An element (C, D) of Π(m, n) covers another…

**Figure 11.** Figure 11: (iii) [PITH_FULL_IMAGE:figures/full_fig_p027_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 48 canonical work pages

[27]

Hiroko Kamei and Peter J. A. Cock. Computation of balanced equivalence relations and their lattice for a coupled cell network.SIAM J. Appl. Dyn. Syst., 12(1):352–382, 2013

work page 2013
[1]

Manuela A. D. Aguiar and Ana Paula S. Dias. The lattice of synchrony subspaces of a coupled cell network: characterization and computation algorithm.J. Nonlinear Sci., 24(6):949–996, 2014

work page 2014
[2]

Manuela A. D. Aguiar and Ana Paula S. Dias. Synchronization and equitable partitions in weighted networks. Chaos, 28(7):073105, 8, 2018

2018
[3]

Manuela A. D. Aguiar, Ana Paula S. Dias, and Flora Ferreira. Patterns of synchrony for feed-forward and auto-regulation feed-forward neural networks.Chaos, 27(1):013103, 9, 2017

work page 2017
[4]

Aguilar and Bahman Gharesifard

Cesar O. Aguilar and Bahman Gharesifard. On almost equitable partitions and network controllability. American Control Conference (ACC), Boston, MA, pages 179–184, 2016

work page 2016
[5]

Aguilar and Bahman Gharesifard

Cesar O. Aguilar and Bahman Gharesifard. Almost equitable partitions and new necessary conditions for network controllability.Automatica J. IFAC, 80:25–31, 2017

work page 2017
[6]

John W. Aldis. A polynomial time algorithm to determine maximal balanced equivalence relations. Internat. J. Bifur. Chaos Appl. Sci. Engrg., 18(2):407–427, 2008

work page 2008
[7]

PhD thesis, University of Warwick, 2010

John William Aldis.On balance. PhD thesis, University of Warwick, 2010

work page 2010

Show all 51 references

[8]

Computing equitable partitions of graphs.Match, (40):265–272, 1999

Oliver Bastert. Computing equitable partitions of graphs.Match, (40):265–272, 1999

1999
[9]

Mesoscale and clusters of synchrony in networks of bursting neurons

Igor Belykh and Martin Hasler. Mesoscale and clusters of synchrony in networks of bursting neurons. Chaos, 21(1):016106, 11, 2011

2011
[10]

A tactical decomposition for incidence structures

Dieter Betten and Mathias Braun. A tactical decomposition for incidence structures. InCombinatorics ’90 (Gaeta, 1990), volume 52 ofAnn. Discrete Math., pages 37–43. North-Holland, Amsterdam, 1992

1990
[11]

Bonaccorsi, S

S. Bonaccorsi, S. Ottaviano, D. Mugnolo, and F. De Pellegrini. Epidemic outbreaks in networks with equitable or almost-equitable partitions.SIAM J. Appl. Math., 75(6):2421–2443, 2015

2015
[12]

Stanley Burris and H. P. Sankappanavar.A course in universal algebra, volume 78 ofGraduate Texts in Mathematics. Springer-Verlag, New York-Berlin, 1981

1981
[13]

P. J. Cameron and R. A. Liebler. Tactical decompositions and orbits of projective groups.Linear Algebra Appl., 46:91–102, 1982

1982
[14]

Cardoso, Maria Aguieiras A

Domingos M. Cardoso, Maria Aguieiras A. de Freitas, Enide Andrade Martins, and María Robbiano. Spectra of graphs obtained by a generalization of the join graph operation.Discrete Math., 313(5):733– 741, 2013

2013
[15]

Cardoso, Charles Delorme, and Paula Rama

Domingos M. Cardoso, Charles Delorme, and Paula Rama. Laplacian eigenvectors and eigenvalues and almost equitable partitions.European J. Combin., 28(3):665–673, 2007

2007
[16]

Verallgemeinerungen von Transitivitätsklassen endlicher projektiver Ebenen.Math

Peter Dembowski. Verallgemeinerungen von Transitivitätsklassen endlicher projektiver Ebenen.Math. Z., 69:59–89, 1958

1958
[17]

Classics in Mathematics

Peter Dembowski.Finite geometries. Classics in Mathematics. Springer-Verlag, Berlin, 1997. Reprint of the 1968 original

1997
[18]

Interacting with networks: How does structure relate to controllability in single-leader, consensus networks? IEEE Control Systems Magazine, 32(4):66–73, 8 2012

Magnus Egerstedt, Simone Martini, Ming Cao, Kanat Camlibel, and Antonio Bicchi. Interacting with networks: How does structure relate to controllability in single-leader, consensus networks? IEEE Control Systems Magazine, 32(4):66–73, 8 2012. Relation: https://www.rug.nl/resear...

2012
[19]

A criterion for stability of cluster synchronization in networks with external equitable partitions.Automatica J

Lucia Valentina Gambuzza and Mattia Frasca. A criterion for stability of cluster synchronization in networks with external equitable partitions.Automatica J. IFAC, 100:212–218, 2019

2019
[20]

A. Gerbaud. Spectra of generalized compositions of graphs and hierarchical networks.Discrete Math., 310(21):2824–2830, 2010

2010
[21]

Patterns in square arrays of coupled cells.J

David Gillis and Martin Golubitsky. Patterns in square arrays of coupled cells.J. Math. Anal. Appl., 208(2):487–509, 1997

1997
[22]

C. D. Godsil.Algebraic combinatorics. Chapman and Hall Mathematics Series. Chapman & Hall, New York, 1993

1993
[23]

C. D. Godsil. Equitable partitions. InCombinatorics, Paul Erdős is eighty, Vol. 1, Bolyai Soc. Math. Stud., pages 173–192. János Bolyai Math. Soc., Budapest, 1993

1993
[24]

Gohberg, P

I. Gohberg, P. Lancaster, and L. Rodman.Invariant subspaces of matrices with applications. Canadian Mathematical Society Series of Monographs and Advanced Texts. John Wiley & Sons, Inc., New York,
[25]

Patterns of synchrony in coupled cell networks with multiple arrows.SIAM J

Martin Golubitsky, Ian Stewart, and Andrei Török. Patterns of synchrony in coupled cell networks with multiple arrows.SIAM J. Appl. Dyn. Syst., 4(1):78–100, 2005

2005
[26]

Birkhäuser/Springer Basel AG, Basel, 2011

George Grätzer.Lattice theory: foundation. Birkhäuser/Springer Basel AG, Basel, 2011

2011
[28]

Graph partitions and the controllability of directed signed networks

Xianzhu Liu, Zhijian Ji, and Ting Hou. Graph partitions and the controllability of directed signed networks. Sci. China Inf. Sci., 62(4):042202, 11, 2019

2019
[29]

Controllability of complex networks

Yang-Yu Liu, Jean-Jacques Slotine, and Albert-Laszlo Barabasi. Controllability of complex networks. Nature, 473:167–73, 05 2011

2011
[30]

Controllability decomposition of networked systems through quotient graphs

Simone Martini, Magnus Egerstedt, and Antonio Bicchi. Controllability decomposition of networked systems through quotient graphs. pages 5244–5249, 01 2008

2008
[31]

Brendan D. McKay. Backtrack Programming and the Graph Isomorphism Problem. Master’s thesis, Unversity of Melbourne, 1976

1976
[32]

Brendan D. McKay. Practical graph isomorphism. Numerical mathematics and computing, Proc. 10th Manitoba Conf., Winnipeg/Manitoba 1980, Congr. Numerantium 30, 45-87 (1981)., 1981

1981
[33]

On multi-consensus and almost equitable graph parti- tions

Salvatore Monaco and Lorenzo Ricciardi Celsi. On multi-consensus and almost equitable graph parti- tions. Automatica J. IFAC, 103:53–61, 2019

2019
[34]

Neuberger, Nándor Sieben, and James W

John M. Neuberger, Nándor Sieben, and James W. Swift. Computing eigenfunctions on the Koch snowﬂake: a new grid and symmetry.J. Comput. Appl. Math., 191(1):126–142, 2006

2006
[35]

Neuberger, Nándor Sieben, and James W

John M. Neuberger, Nándor Sieben, and James W. Swift. Symmetry and automated branch following for a semilinear elliptic PDE on a fractal region.SIAM J. Appl. Dyn. Syst., 5(3):476–507 (electronic), 2006

2006
[36]

Neuberger, Nándor Sieben, and James W

John M. Neuberger, Nándor Sieben, and James W. Swift. Automated bifurcation analysis for nonlinear elliptic partial diﬀerence equations on graphs.Internat. J. Bifur. Chaos Appl. Sci. Engrg., 19(8):2531– 2556, 2009

2009
[37]

Neuberger, Nándor Sieben, and James W

John M. Neuberger, Nándor Sieben, and James W. Swift. Newton’s method and symmetry for semilinear elliptic PDE on the cube.SIAM J. Appl. Dyn. Syst., 12(3):1237–1279, 2013

2013
[38]

Neuberger, Nándor Sieben, and James W

John M. Neuberger, Nándor Sieben, and James W. Swift. Invariant Synchrony Subspaces of Sets of Matrices (companion web site), 2019.http://jan.ucc,nau.edu/ns46/invariant

2019
[39]

Neuberger, Nándor Sieben, and James W

John M. Neuberger, Nándor Sieben, and James W. Swift. Synchrony and Antisynchrony for Diﬀerence- Coupled Vector Fields on Graph Network Systems.SIAM J. Appl. Dyn. Syst., 18(2):904–938, 2019

2019
[40]

Pecora, Francesco Sorrentino, Aaron M

Louis M. Pecora, Francesco Sorrentino, Aaron M. Hagerstrom, Thomas E. Murphy, and Rajarshi Roy. Cluster synchronization and isolated desynchronization in complex networks with symmetry.Nature Communications, 5(5079):1–8, 2014

2014
[41]

Controllability of multi-agent systems from a graph-theoretic perspective.SIAM J

Amirreza Rahmani, Meng Ji, Mehran Mesbahi, and Magnus Egerstedt. Controllability of multi-agent systems from a graph-theoretic perspective.SIAM J. Control Optim., 48(1):162–186, 2009

2009
[42]

Understanding cancer complexome using networks, spectral graph theory and multilayer frame- work

Aparna Rai, Priodyuti Pradhan, Jyothi Nagraj, Lohitesh Kovooru, Rajdeep Chowdhury, and Sarika Jalan. Understanding cancer complexome using networks, spectral graph theory and multilayer frame- work. Scientiﬁc Reports, 7:41676, 02 2017. INV ARIANT SYNCHRONY SUBSPACES 29

2017
[43]

Schaub, Neave O’Clery, Yazan N

Michael T. Schaub, Neave O’Clery, Yazan N. Billeh, Jean-Charles Delvenne, Renaud Lambiotte, and Mauricio Barahona. Graph partitions and cluster synchronization in networks of oscillators.Chaos, 26(9):094821, 14, 2016

2016
[44]

Pecora, Aaron M

Francesco Sorrentino, Louis M. Pecora, Aaron M. Hagerstrom, Thomas E. Murphy, and Rajarshi Roy. Complete characterization of the stability of cluster synchronization in complex dynamical networks. Sci. Adv., 2:1–8, 2016

2016
[45]

The lattice of balanced equivalence relations of a coupled cell network.Math

Ian Stewart. The lattice of balanced equivalence relations of a coupled cell network.Math. Proc. Cam- bridge Philos. Soc., 143(1):165–183, 2007

2007
[46]

Symmetry groupoids and patterns of synchrony in coupled cell networks.SIAM J

Ian Stewart, Martin Golubitsky, and Marcus Pivato. Symmetry groupoids and patterns of synchrony in coupled cell networks.SIAM J. Appl. Dyn. Syst., 2(4):609–646, 2003

2003
[47]

SageMath, the Sage Mathematics Software System (Version 8.7) , 2019

The Sage Developers. SageMath, the Sage Mathematics Software System (Version 8.7) , 2019. https://www.sagemath.org

2019
[48]

Kanat Camlibel, and Ming Cao

Shuo Zhang, M. Kanat Camlibel, and Ming Cao. Controllability of diﬀusively-coupled multi-agent systems with general and distance regular coupling topologies. In Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC) , pages 759–
[49]

Kanat Camlibel

Shuo Zhang, Ming Cao, and M. Kanat Camlibel. Upper and lower bounds for controllable subspaces of networks of diﬀusively coupled agents.IEEE Trans. Automat. Control, 59(3):745–750, 2014. Current address: Northern Arizona University, Department of Mathematics and Statistics, Fl...

2014
[764]

Relation: https://www.rug.nl/fmns-research/itm/index Rights: University of Groningen, Research Institute of Technology and Management

University of Groningen, Research Institute of Technology and Management, 2011. Relation: https://www.rug.nl/fmns-research/itm/index Rights: University of Groningen, Research Institute of Technology and Management

2011
[1986]

A Wiley-Interscience Publication

Pith tools

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

[1] [27]

Hiroko Kamei and Peter J. A. Cock. Computation of balanced equivalence relations and their lattice for a coupled cell network.SIAM J. Appl. Dyn. Syst., 12(1):352–382, 2013

work page 2013

[2] [1]

Manuela A. D. Aguiar and Ana Paula S. Dias. The lattice of synchrony subspaces of a coupled cell network: characterization and computation algorithm.J. Nonlinear Sci., 24(6):949–996, 2014

work page 2014

[3] [2]

Manuela A. D. Aguiar and Ana Paula S. Dias. Synchronization and equitable partitions in weighted networks. Chaos, 28(7):073105, 8, 2018

2018

[4] [3]

Manuela A. D. Aguiar, Ana Paula S. Dias, and Flora Ferreira. Patterns of synchrony for feed-forward and auto-regulation feed-forward neural networks.Chaos, 27(1):013103, 9, 2017

work page 2017

[5] [4]

Aguilar and Bahman Gharesifard

Cesar O. Aguilar and Bahman Gharesifard. On almost equitable partitions and network controllability. American Control Conference (ACC), Boston, MA, pages 179–184, 2016

work page 2016

[6] [5]

Aguilar and Bahman Gharesifard

Cesar O. Aguilar and Bahman Gharesifard. Almost equitable partitions and new necessary conditions for network controllability.Automatica J. IFAC, 80:25–31, 2017

work page 2017

[7] [6]

John W. Aldis. A polynomial time algorithm to determine maximal balanced equivalence relations. Internat. J. Bifur. Chaos Appl. Sci. Engrg., 18(2):407–427, 2008

work page 2008

[8] [7]

PhD thesis, University of Warwick, 2010

John William Aldis.On balance. PhD thesis, University of Warwick, 2010

work page 2010