Simple Cuts, Simple Landscapes: Global Synchronization and Rank-Width-One Matrices

Introduction

Synchronization of coupled oscillators on graphs raises a basic question: how do local interactions produce collective agreement? Answering this question is fundamental to understanding the phenomenon of synchronization itself and its role in technological systems, such as power grids, oscillatory neural networks, and Transformer dynamics [DCB13, VPdBS11, GLPR25]; biological systems, such as circadian clocks and neural circuits [37, 10]; and social systems, such as rhythmic applause and pedestrian motion on footbridges [24, 30], and so on.

The Kuramoto model, introduced by Yoshiki Kuramoto in 1975 [Kur75], serves as a canonical model for studying this question. It is a system of ordinary differential equations of the form

Here, the $i$th equation describes the evolution of the phase (angle) $\theta_i(t)$ of oscillator $i$, placed at vertex $i$ of an undirected graph $G=(V,E)$ with $V=\{1,\ldots,n\}$. Each oscillator has its own intrinsic frequency $\omega_i\in\mathbb{R}$, which determines its rotation rate in the absence of coupling. Its actual rotation rate is also influenced by phase differences with its neighbors, with coupling strengths $A_{ij}>0$ along the edges. These coupling strengths form the weighted adjacency matrix $A=(A_{ij})$ of $G$; positive coupling tends to align neighboring phases.

In this work, we assume a common intrinsic frequency, $\omega_i=\omega$ for all $i$. Passing to a rotating frame via the change of variables $\theta_i(t)\mapsto\theta_i(t)-\omega t$, we obtain

To understand whether all oscillators synchronize (i.e., $\theta_1=\cdots=\theta_n$ (mod $2\pi$)) as $t\to\infty$, the energy perspective offers a clean view: stack all angles $\theta_1,\ldots,\theta_n$ into a vector $\theta=(\theta_1,\ldots,\theta_n)$, and write (1) as $\dot{\theta}=-\nabla E_A(\theta)$, where

This shows that the Kuramoto model (1) is a gradient flow: each trajectory $\theta(t)$ moves in the direction of steepest descent of $E_A$, and along every trajectory, $\frac{d}{dt}E_A(\theta(t))=-\lVert\nabla E_A(\theta(t))\rVert^2\le0$, indicating that the energy is nonincreasing. Therefore, the geometry of $E_A$ reveals the asymptotic dynamics of (1). For rigorous results on the relationship between the asymptotic behavior of gradient flows and the geometry of their energy functions, we refer to [3, 15].

One nice property of $E_A$ is that, when the support graph is connected, every global minimizer is a fully synchronized state. Indeed, since $A_{ij}\ge0$,

Equality holds precisely when the phases agree along every edge, which, by connectedness, means $\theta_1=\cdots=\theta_n$ (mod $2\pi$).

However, the first-order points of $E_A$ other than its global minimizers can have a much more complicated structure. In general, $E_A$ may have nonsynchronized local minima. Nevertheless, in some cases, the energy landscape is rather simple: every local minimum is fully synchronized. Therefore, the question now is to understand which coupling matrices yield such a simple landscape and why.

This problem is known as global synchronization (GS) [21, 20 KST21, 2, 16 LZ26]. In this work, we ask it in the local-minimum sense²:

Whether all local minima of $E_A$ are synchronized depends on both the topology of the support graph and the coupling weights.

Topology matters. In the unweighted case, $A_{ij}=1$ if vertices $i$ and $j$ are adjacent and $A_{ij}=0$ otherwise, so the energy is determined entirely by the graph structure. For some graph structures, the corresponding energy $E_A(\theta)$ has nonsynchronized local minima. For example, on a cycle graph $C_n$ with $n\ge5$, the equally spaced phases $\theta_k=2\pi(k-1)/n$ form a nonsynchronized strict local minimum modulo global rotation³ [36].

Weights matter. In the weighted case, even when the energy associated with the underlying unweighted graph has no nonsynchronized local minima, assigning positive weights to its existing edges can create such minima in the weighted energy $E_A(\theta)$. For instance, the unweighted complete graph $K_5$ is almost globally synchronizing: almost every initial phase configuration converges to a synchronized configuration [31 Corollary 4.1]. However, assigning weight $1$ to the edges of a five-cycle and a small positive weight to its diagonals yields a weighted $K_5$ whose coupling matrix is close to that of the unweighted $C_5$. Taking the diagonal weights to be $1/10$ produces a nonsynchronized strict local minimum of $E_A(\theta)$ modulo global rotation at the equally spaced phase configuration; see § 4.2, Example 4.2 for the explicit configuration and its verification. Figure 1 compares these three graphs.

Main result and its scope

Our main result shows that if the coupling matrix $A$ has rank-width one over $\mathbb{R}$, then every local minimum of $E_A$ is a fully synchronized state.

Here, a first- and second-order point $\theta$ is a stationary point with positive semidefinite Hessian of the energy function $E_A(\theta)$. We call a configuration $\theta$ non-flat if the only straight-line phase variations along which the energy is locally constant are common rotations; see § 2.2 for the precise definition.

A symmetric entrywise nonnegative matrix $A$ with zero diagonal represents a weighted graph: vertices $i$ and $j$ are adjacent if $A_{ij} > 0$, and the edge $ij$ has weight $A_{ij}$. Informally, $A$ has rank-width at most one if there exists a rank-decomposition tree such that the submatrix across each cut induced by an edge of the tree has rank at most one. We denote the rank-width over $\mathbb{R}$ by $\operatorname{rw}_{\mathbb{R}}(A)$. This condition concerns the ranks of cut submatrices, rather than the rank of $A$ itself. Our proof replaces a global rank-one factorization by rank-one factorizations across cuts of a decomposition tree, along which synchronized blocks can be merged. We use the matrix rank-width framework of Oum [28]; see § 2.3 for the precise definitions of a rank-decomposition tree and rank-width.

When all entries of $A$ belong to $\{0,1\}$, it is the adjacency matrix of an unweighted simple graph. In this setting, a graph with adjacency matrix that has rank-width at most one is exactly distance-hereditary. These form a well-studied class in structural and algorithmic graph theory, with close connections to split decomposition and rank-width [14, 27]. Their definition is based on the preservation of distances: a graph is distance-hereditary if, in every connected induced subgraph, the distance between any two vertices equals their distance in the original graph, where distance is the length of a shortest path. Oum [27] established the following characterization, with cut-ranks computed over the two-element field $\mathbb{F}_2$.

Combining Theorems 1.1 and 1.2 gives the following consequence.

Proof. Let $G$ be a connected graph with adjacency matrix $A_G$. The single-vertex case is immediate, so assume that $G$ has at least two vertices. Theorem 1.1 gives the conclusion whenever $\operatorname{rw}_{\mathbb{R}}(A_G)=1$. For any $0/1$ matrix $M$, $\operatorname{rank}_{\mathbb{R}}(M)\le1$ if and only if $\operatorname{rank}_{\mathbb{F}_2}(M)\le1$. Hence

Since $G$ is connected and has at least two vertices, both rank-widths are nonzero. Thus the condition $\operatorname{rw}_{\mathbb{R}}(A_G)=1$ is equivalent, by Theorem 1.2, to $G$ being distance-hereditary. □

In the unweighted setting, the rank-width bound underlying Corollary 1.3 is sharp. Every unweighted cycle $C_n$, $n \ge5$, has real rank-width two and admits a nonsynchronized configuration that is both a local minimum and a non-flat first- and second-order point (Proposition 4.1). In the weighted setting, Example 4.2 establishes sharpness of both conclusions of Theorem 1.1: a positively weighted $K_5$ has a coupling matrix of real rank-width two and admits a nonsynchronized configuration with both properties.

Cornelsen and Di Stefano [CD09] proved that the underlying undirected graph of the transitive closure of any directed tree is distance-hereditary. Combining this fact with Corollary 1.3 yields the following consequence.

Proof. The graph $G$ is connected and distance-hereditary, so Corollary 1.3 applies. □

Synchronization properties and terminology

Different notions of global synchronization appear in the literature. In this section, we provide an overview of these notions and their relationships.

This dynamical property is called almost global synchronization in [8, 9]. It is called global synchronization (GS) in [35 Definition 1.1], [2 Definition 1.1], and [16 Introduction]. We distinguish AGS from the following energy-landscape properties:

1. Local-minimum GS: Every local minimum of $E_A(\theta)$ is a fully synchronized state.

2. Second-order GS: Every first- and second-order point of $E_A(\theta)$ is a fully synchronized state.

3. Non-flat second-order GS: Every non-flat first- and second-order point of $E_A(\theta)$ is a fully synchronized state.

Property (ii) implies (i), since every local minimum satisfies the first- and second-order conditions, and it implies (iii) directly. It also implies AGS: real analyticity gives convergence of trajectories to equilibria, and every nonsynchronized equilibrium then has a negative Hessian eigenvalue. A center-stable manifold argument shows that the set of initial conditions converging to these equilibria has measure zero; see [35 Introduction] and the references therein. Local minima may have flat directions, whereas non-flat first- and second-order points need not be local minima; these observations alone do not give an implication between (i) and (iii).

Lepsveridze and Zhang [LZ26, Remark 1] adopt property (i) as their definition of global synchronization in their work on the density conjecture, explicitly distinguishing it from AGS. Other results establishing property (i) include [21, 20]. Property (ii) follows from the minimum-degree criteria [31, 21, 20 KST21], spectral and random-graph criteria [18, 2, 16, 1, 12], weighted landscape criteria [4, 29, 23], and the results on threshold graphs and quasi-threshold graphs [34, 35].

For the classes considered here, Theorem 1.1 and Corollary 1.3 establish (i) and (iii), but not (ii). We do not establish AGS from either (i) or (iii) alone.

Related work

For unweighted graphs, a central question is the critical minimum-degree threshold $\mu_c(n-1)$ for local-minimum GS. Earlier upper bounds on $\mu_c$ [31, 21, 20] were improved to $3/4$ [KST21]. Lepsveridze and Zhang [LZ26] recently lowered this bound strictly below $3/4$, refuting the sharpness conjecture in [BKMR25, Conjecture 5]. Lower bounds from counterexample constructions [32 YTT21] were improved to $11/16$ [6] and most recently to $0.6929077063\ldots$ [25]. The exact value of the local-minimum GS threshold remains open.

Expansion criteria offer another approach. Abdalla et al. [2] proved that a $d$-regular graph with adjacency matrix $A$ is almost globally synchronizing whenever

Rakoto Endor and Waldspurger [29] and McRae [23] established synchronization criteria based on Laplacian condition numbers, involving the ordinary Laplacian $L$ and the normalized Laplacian $\mathcal{L}$. For a connected graph, second-order GS holds if

where eigenvalues are ordered increasingly.

A common starting point for many of the preceding results is the complete graph, which satisfies both second-order GS and local-minimum GS. Since diagonal entries only add a constant to $E_A$, its adjacency matrix $\mathbf{1}\mathbf{1}^{\mathsf{T}}-I$ can be replaced by the rank-one matrix $\mathbf{1}\mathbf{1}^{\mathsf{T}}$ without changing the landscape geometry. Minimum-degree and spectral conditions can then be interpreted as controlling departures from this rank-one benchmark [35 Section 1.1].

This perspective leaves a broader structural question: which graphs ensure local-minimum or second-order GS beyond the rank-one benchmark and the regimes covered by these criteria? Recent progress on this question has identified structural mechanisms for synchronization that do not require density, expansion, or spectral assumptions. Wu and Brandes [34] proved that every connected threshold graph is second-order globally synchronizing by exploiting geometric relations between vertices introduced along the graph’s construction sequence. For the larger class of connected quasi-threshold graphs, they established second-order GS through a different structural argument based on the underlying rooted-tree skeleton [35]. This argument propagates synchronization from the leaves toward the root, without relying on a construction sequence.

Our work differs from [34, 35] in two respects. First, our proof reveals a mechanism of GS distinct from those based on construction sequences or graph skeletons: simple cuts induce a simple energy landscape. Specifically, if a connected positively weighted graph admits a tree-like decomposition in which the coupling submatrix across each induced cut has rank one, then the associated energy has no spurious local minima. Second, the results in [34, 35] establish second-order GS, whereas our main conclusion concerns local-minimum GS. The stronger second-order GS requirement does not hold for all distance-hereditary graphs. For example, the four-cycle $C_4$ is distance-hereditary, and the configuration $(0,\pi/2,\pi,3\pi/2)$, with vertices labeled cyclically, has zero gradient and zero Hessian. It is therefore a nonsynchronized first- and second-order point. Nevertheless, Corollary 1.3 shows that every local minimum is a fully synchronized state for every connected distance-hereditary graph. In addition, our result excludes nonsynchronized non-flat first- and second-order points.

Existing results also address global synchronization on weighted graphs, including [23 Theorem 3.4] and the weighted extension of [2 Theorem 1.4]. These results do not cover the full class considered here: real rank-width one constrains the ranks of cut submatrices but does not imply the required spectral bounds. Theorem 1.1 broadens the rank-one benchmark for local-minimum GS to real rank-width one.

1.4. Organization. § 2 introduces the first- and second-order conditions for the Kuramoto energy function (2). In particular, we define non-flatness, a key concept in Theorem 1.1. We then introduce matrix rank-width over $\mathbb{R}$, specializing Oum’s definition [28] to the real field. Finally, we derive geometric consequences of the stationary conditions across rank-one cuts. § 3 proves Theorem 1.1. The key step is an induction lemma that allows synchronized vertex sets to be merged. We then apply this lemma recursively along a rank-decomposition tree to complete the proof. § 4 establishes sharpness in the unweighted and weighted settings using cycles and a positively weighted complete graph, respectively.

Preliminaries

Notation

Sets and vectors.

For a finite set $W$, let $\mathbb{R}^{W}$ denote the space of real vectors indexed by $W$. For $S \subseteq V$, write $S^{c}:=V\setminus S$. For $p\in\mathbb{R}^{W}$ and $U\subseteq W$, define

Let $\mathbf{1}_U\in\{0,1\}^{W}$ be the indicator vector of $U$, with ambient set understood from context. We write $\mathbf{1}$ and $\mathbf{0}$ for the all-ones and zero vectors of the appropriate dimension, and $\mathbf{0}_W$ for the zero vector indexed by $W$. We use $\langle\cdot,\cdot\rangle$ and $\lvert\cdot\rvert$ for the Euclidean inner product and norm, respectively, and write $\mathbf{1}^{\perp}=\{x:\langle x,\mathbf{1}\rangle=0\}$.

Matrices and graphs.

For $A\in\mathbb{R}^{V\times V}$ and $U,W\subseteq V$, let $A[U,W]$ denote the submatrix with row set $U$ and column set $W$. We write $\mathcal{S}_0^n$ for the space of real symmetric $n\times n$ matrices with zero diagonal. Throughout this work, the coupling matrix $A$ belongs to $\mathcal{S}_0^n$. Its support graph $G_A$ has vertex set $V$, with distinct vertices $i,j$ adjacent if and only if $A_{ij}\ne0$. For a real symmetric matrix $M$, we write $M\succeq0$ if $M$ is positive semidefinite. Matrix ranks are taken over $\mathbb{R}$ unless another field is specified.

Phase vectors.

We write $\mathbb{S}^1$ for the unit circle in $\mathbb{R}^2$ and associate with each phase $\theta_i\in\mathbb{R}$ the vector $v_i=(\cos\theta_i,\sin\theta_i)\in\mathbb{S}^1$.

First- and second-order conditions and flat directions

We recall the first- and second-order conditions for the energy (2). Throughout this subsection, we assume only that $A\in\mathcal{S}_0^n$; any additional nonnegativity assumptions will be stated explicitly.

First-order condition. A point $\theta$ is called a first-order point of $E_A(\theta)$ if

A point $\theta$ is called a second-order point of $E_A(\theta)$ if its Hessian $H=\nabla^2E_A(\theta)$ satisfies

where

A point satisfying both conditions (FOC) and (SOC) is called a first- and second-order point of $E_A(\theta)$. Clearly, every local minimum of $E_A(\theta)$ satisfies both conditions, as every local minimum is a first- and second-order point.

We make the following observations.

(1) Every nonzero multiple $\alpha\mathbf{1}$ is a flat direction, corresponding to a common rotation of all phases. We call such directions trivial; all other flat directions are called nontrivial. A point is called non-flat if it has no nontrivial flat direction.

(2) If $\theta$ is a first- and second-order point of $E_A(\theta)$ and $d$ is a flat direction at $\theta$, then

equivalently,

Proof of (2). Write $H=\nabla^2E_A(\theta)$. For a fixed flat direction $d$, Taylor expansion at $\theta$ gives

Dividing by $t^2$ for $t\ne0$, we obtain

The first-order condition makes the first term zero. Since $r(t)$ is bounded near zero, we have $tr(t) \to0$ as $t \to0$. Taking limits in the preceding equality therefore gives $d^{\mathsf{T}}Hd = 0$. Since $H \succeq0$, we may write $H = B^{\mathsf{T}}B$. Then $\lVert Bd\rVert^2 = d^{\mathsf{T}}Hd = 0$, so $Bd = 0$ and hence $Hd = 0$. $\square$

Since $H\mathbf{1}=0$, observation (2) gives the following sufficient condition for non-flatness.

Proof. By observation (2), every flat direction belongs to $\ker H = \mathbb{R}\mathbf{1}$, so no flat direction is nontrivial. $\square$

Rank-width

We specialize Oum’s definition of rank-width for symmetric matrices over an arbitrary field [28] to $\mathbb{R}$.

Throughout this paper, we use subcubic trees $T=(V(T),E(T))$ whose vertices have degree one or three. The degree-one vertices are called leaves, and their set is denoted by $L(T)$; the degree-three vertices are called internal vertices. An edge incident to a leaf is called a pendant edge; all other edges are called nonpendant edges. Each edge $e \in E(T)$ partitions $L(T)$ into two nonempty sets, given by the two components of $T-e$. We call this partition the cut induced by $e$.

Remark 2.4. For an unweighted graph with adjacency matrix $B$, $\operatorname{rw}_{\mathbb{R}}(B)$ equals the $\mathbb{Q}$-rank-width studied by Oum, Sæther, and Vatshelle [26 Section 3], since a rational matrix has the same rank over $\mathbb{Q}$ and $\mathbb{R}$. This need not equal the usual graph rank-width, which uses $\mathbb{F}_2$, although the conditions of having rank-width at most one coincide, as explained in the proof of Corollary 1.3.

Examples 2.5.

(1) The path $P_4$. Let $A$ be the adjacency matrix of the path $P_4$ with edges $\{1,2\}$, $\{2,3\}$, and $\{3,4\}$. Figure 3 shows its support graph, matrix, and a rank-decomposition. The nonpendant edge $e$ gives $S_e=\{1,2\}$ and $S_e^{\mathrm{c}}=\{3,4\}$; the highlighted submatrix has rank one. Every pendant edge gives a nonzero singleton cut, also of rank one. Thus this decomposition has width one and $\operatorname{rw}_{\mathbb{R}}(A)=1$.

(2) The cycle $C_4$. Let $\mathbf{A}$ be the adjacency matrix of $C_4$, with vertices labeled cyclically by $1,2,3,4$. Choose a rank-decomposition whose single nonpendant edge induces the cut $(\{1,3\},\{2,4\})$. Its cut matrix $\mathbf{A}[\{1,3\},\{2,4\}]$ is the $2 \times2$ all-ones matrix and hence has rank one. Thus this decomposition has width one and $\operatorname{rw}_{\mathbb{R}}(\mathbf{A})=1$.

(3) The cycle $C_n$, $n \ge5$. Let $n \ge5$, and let $\mathbf{A}$ be the adjacency matrix of $C_n$, with vertices labeled cyclically by $1,\ldots,n$. Then $\operatorname{rw}_{\mathbb{R}}(\mathbf{A})=2$. Indeed, every rank-decomposition tree has a nonpendant edge inducing a cut $(S,S^c)$ with $|S|,|S^c|>1$. Every such cut of $C_n$ has rank at least two. Hence every rank-decomposition has width at least two, giving $\operatorname{rw}_{\mathbb{R}}(\mathbf{A}) \ge2$. To show that $\operatorname{rw}_{\mathbb{R}}(\mathbf{A}) \le2$, let $S_k=\{1,\ldots,k\}$ for $2 \le k \le n-2$. Each cut matrix $\mathbf{A}[S_k,S_k^c]$ has rank two. The caterpillar tree in Figure 4 gives a rank-decomposition whose nonpendant edges induce exactly these cuts. Thus this decomposition has width two, giving $\operatorname{rw}_{\mathbb{R}}(\mathbf{A}) \le2$. Together, these bounds give $\operatorname{rw}_{\mathbb{R}}(\mathbf{A})=2$.

First- and second-order conditions on rank-one cuts

Throughout this subsection, let $\mathbf{A} \in S_0^n$. We derive consequences of the first- and second-order conditions for cuts, and express them using weighted phasor sums when the cut has rank one. These results will be used to prove the induction lemma in § 3.1. For a cut $(S,S^c)$ with $\rho_{\mathbf{A}}(S)=1$, choose nonzero vectors $\mathbf{p} \in\mathbb{R}^{S}$ and $\mathbf{q} \in\mathbb{R}^{S^c}$ such that

Figure 5 illustrates the edges across such a cut.

Summing the first-order condition on any cut gives the following identity.

Proof. Summing (FOC) over $i\in S$ gives

The terms with $i,j\in S$ cancel pairwise because $A_{ij}=A_{ji}$ and $\sin(\theta_i-\theta_j)=-\sin(\theta_j-\theta_i)$.

For a cut with rank one, this identity implies that the two weighted phasor sums are parallel whenever both are nonzero.

Proof. Let

denote the counterclockwise rotation matrix through an angle $\pi/2$. Since $\langle Rv_i,v_j\rangle=-\sin(\theta_i-\theta_j)$, the factorization (5) and Lemma 2.6 give

Since both weighted sums are nonzero vectors in $\mathbb{R}^2$, this implies that they are parallel, as claimed.

The second-order condition gives the following inequality for any cut.

Proof. Set $\mathbf{x}=\mathbf{1}_{S}$. We verify that $\mathbf{x}^{\mathsf{T}}H\mathbf{x}=\sum_{i\in S}\sum_{j\in S^{c}} A_{ij}\langle v_i,v_j\rangle$. Indeed, by the Hessian formula (4),

The second equality holds because $(x_i-x_j)^2=1$ if $i,j$ lie on opposite sides of the cut $(S,S^{c})$, and $(x_i-x_j)^2=0$ otherwise. The conclusion follows from (SOC). □

For a cut with rank one, this inequality says that the two weighted phasor sums have a nonnegative inner product.

Proof. By Lemma 2.8, the factorization (5), and bilinearity of the inner product,

□

For a cut with rank one, combining the parallelism of the two nonzero weighted sums in Corollary 2.7 with their nonnegative inner product in Corollary 2.9 gives the following corollary.

Proof. By Corollary 2.7, there exists $\mu\ne0$ such that

By Corollary 2.9,

Since the second vector is nonzero and $\mu\ne0$, we obtain $\mu>0$. □

Proof of the main theorem

Proof strategy. Across a cut with rank one, the interaction energy is determined by two weighted phasor sums, one on each side. The first- and second-order conditions force these sums to point in the same direction whenever both are nonzero.

At each internal node of a rank-decomposition tree, the three branches partition $V$ into $X$, $Y$, $Z$. Compatibility of the three rank-one factorizations allows us to merge synchronized sets $X$ and $Y$: their common phases must agree. This is the induction lemma proved in § 3.1, which we apply along the tree in § 3.2.

The main difficulty is that a weighted phasor sum may vanish. When $X$ and $Y$ interact only through $Z$, a vanishing sum on $Z$ would allow $Z$ to rotate without changing the energy. Non-flatness excludes this directly; local minimality excludes it through the second-order conditions along this constant-energy path.

The induction lemma

Lemma 3.1 (Extension of a rank-one factorization). Let $B \in\mathbb{R}^{m \times r}$ and $C \in\mathbb{R}^{m \times s}$ satisfy $\operatorname{rank}[B\ C] = 1$. Suppose that $C = p q^{\mathsf{T}} \ne0$, where $p \in\mathbb{R}^{m}$ and $q \in\mathbb{R}^{s}$. Then there exists a vector $f \in\mathbb{R}^{r}$ such that

Proof. Choose $j$ with $q_j \ne0$. The $j$th column of $C$ is $q_jp \ne0$. Since $[B\ C]$ has rank one, every column of $B$ is a scalar multiple of this column, and hence of $p$. Writing the $k$th column as $f_kp$ gives $B = pf^{\mathsf{T}}$. Together with $C = pq^{\mathsf{T}}$, this yields the claimed factorization. $\square$

Lemma 3.2 (Uniqueness of rank-one factorizations). Let $a,c \in\mathbb{R}^{m}$ and $b,d \in\mathbb{R}^{n}$ satisfy $ab^{\mathsf{T}} = cd^{\mathsf{T}} \ne0$. Then there exists a unique scalar $\alpha\in\mathbb{R} \setminus\{0\}$ such that

Proof. Since the common matrix is nonzero, all four vectors are nonzero. Multiplying the identity on the right by $b$ gives

The left-hand side is nonzero, so $d^{\mathsf{T}}b \ne0$. Thus $a = \alpha c$ with $\alpha:= (d^{\mathsf{T}}b)/\lVert b\rVert^2 \ne0$. Substituting this into the assumed identity gives $c(\alpha b-d)^{\mathsf{T}} = 0$. Since $c \ne0$, we obtain $d = \alpha b$. The uniqueness of $\alpha$ follows from $c \ne0$. $\square$

Proof. We show that $\theta_X \equiv\theta_Y \pmod{2\pi}$ by considering three mutually exclusive and exhaustive cases, addressed by the three auxiliary lemmas proved below. If $A[X,Y] = 0$, connectedness forces both $A[X,Z]$ and $A[Y,Z]$ to be nonzero; otherwise, $X$ or $Y$ would be disconnected from its complement. If $A[X,Y] \ne0$, then at least one of $A[X,Z]$ and $A[Y,Z]$ must be nonzero; otherwise, $X \cup Y$ would be disconnected from the nonempty set $Z$, contradicting the connectedness of the support graph.

If $A[X,Y]=0$, the conclusion follows from Lemma 3.4. If $A[X,Y]\ne0$ and both $A[X,Z]$ and $A[Y,Z]$ are nonzero, the conclusion follows from Lemma 3.5. In the remaining case, exactly one of $A[X,Z]$ and $A[Y,Z]$ is nonzero, and the conclusion follows from Lemma 3.6. □

We now prove the three auxiliary lemmas used in the proof of Lemma 3.3, one for each interaction pattern. To simplify their proofs, we introduce the following notation. Since $\theta$ is synchronized on $X$ and $Y$, let $v_X,v_Y\in S^1$ denote their common unit vectors; thus $v_i=v_X$ for $i\in X$, and $v_j=v_Y$ for $j\in Y$.

By symmetry of $A$, $\rho_A(X\cup Y)=\rho_A(Z)=1$. Hence there exist $p\in\mathbb{R}^{X\cup Y}$ and $q\in\mathbb{R}^{Z}$ such that

Since $A_{ij}\ge0$ for all $i,j=1,\ldots,n$, we may choose the factorization in (7) so that $p_i,q_j\ge0$ for all $i\in X\cup Y$ and $j\in Z$.

Figure 6 illustrates the three interaction patterns treated in the auxiliary lemmas.

The first three terms are independent of $t$, since all phase differences within each set are unchanged. Moreover, $E_{X\leftrightarrow Y}(\theta^t)=0$ because $A[X,Y]=0$. By (7),

The same calculation gives $E_{Y\leftrightarrow Z}(\theta^t)=0$. Thus

Case (a): $\theta$ is a non-flat first- and second-order point. The energy identity above contradicts non-flatness because $\mathbf{1}_Z$ is a nontrivial flat direction.

Case (b): $\theta$ is a local minimum. Since $\theta$ is a local minimum, there is an open neighborhood $\mathcal{U}$ of $\theta$ on which $E_A(\phi)\ge E_A(\theta)$ for every $\phi\in\mathcal{U}$. For sufficiently small $t$, we have $\theta^t\in\mathcal{U}$ and $E_A(\theta^t)=E_A(\theta)$. Thus $\theta^t$ also minimizes the energy on $\mathcal{U}$, so it is a local minimum. Consequently, $\mathbf{H}(t):=\nabla^2E_A(\theta^t)\succeq0$. Since $A[X,Y]=0$ and $\mathbf{w}_Z(t)=0$,

Since $\mathbf{H}(t)\succeq0$, the vanishing quadratic form implies $\mathbf{H}(t)\mathbf{1}_X=0$ for every sufficiently small $t$. Since $A[X,Z]\ne0$, we have $p(X)>0$ and can fix $j\in Z$ with $q_j>0$. The $j$th coordinate of this identity gives

Since $p(X)q_j>0$, it follows that

This is impossible because the cosine function does not vanish on any interval. Hence $\mathbf{w}_Z\ne0$ in both cases.

Step 2. We show that $\sum_{j\in Z}q_j\mathbf{v}_j=\lambda_X\mathbf{v}_X$ for some $\lambda_X>0$.

Since $\rho_A(X)=1$, the cut matrix $A[X,Y\cup Z]$ has rank one. By (7), we have

Together with $A[X,Y]=0$, this gives

By Step 1, $\sum_{j\in Z}q_j\mathbf{v}_j\ne0$. Moreover, since $\theta$ is synchronized on $X$,

Since $p(X)>0$ and $\mathbf{v}_X\ne0$, this weighted sum is nonzero. By Corollary 2.10, since both $\sum_{i\in X}p_i\mathbf{v}_i$ and $\sum_{j\in Z}q_j\mathbf{v}_j$ are nonzero, the factorization (8) gives a scalar $\mu>0$ such that

Since $p(X)>0$ and $\mu>0$, we conclude that

Step 3. We show that $\sum_{j\in Z}q_jv_j=\lambda_Yv_Y$ for some $\lambda_Y>0$. Similarly, switching the roles of $X$ and $Y$ in Step 2, we obtain

Step 4. We show that $\theta$ is synchronized on $X\cup Y$. From (9), (10), and $\lVert v_X\rVert=\lVert v_Y\rVert=1$, we obtain $\lambda_X=\lambda_Y$ and hence $v_X=v_Y$. Thus $\theta_X\equiv\theta_Y\pmod{2\pi}$.

Proof. Step 1. We show that $A[X,Y]=p_Xf^{\mathsf T}$ for some $f\in\mathbb{R}^{Y}$. By (7), we have $A[X,Z]=p_Xq^{\mathsf T}\ne0$. Since $\rho_A(X)=1$, the submatrix $A[X,Y\cup Z]=[A[X,Y]\ \ A[X,Z]]$ has rank one. Applying Lemma 3.1, we obtain a vector $f\in\mathbb{R}^{Y}$ such that

Consequently,

Step 2. We show that $A[Y,X]=p_Ye^{\mathsf T}$ for some $e\in\mathbb{R}^{X}$. Similarly, switching the roles of $X$ and $Y$ in Step 1, there exists $e\in\mathbb{R}^{X}$ such that

Consequently,

Step 3. We show that $f=\alpha p_Y$ and $e=\alpha p_X$ for some $\alpha>0$. By (11) and (12), and by symmetry of $A$, we have $A[Y,X]=A[X,Y]^{\mathsf T}$. Thus, $p_Ye^{\mathsf T}=fp_X^{\mathsf T}$. Applying Lemma 3.2, we obtain a scalar $\alpha\ne0$ such that

Consequently,

Since $p_X$ and $p_Y$ are nonzero and entrywise nonnegative, and $A[X,Y]$ is entrywise nonnegative, it follows that $\alpha>0$. We can therefore write the two cut matrices as

Step 4. We show that $\theta$ is synchronized on $X\cup Y$. For the cut $(X,Y\cup Z)$ with the factorization in (13), the two weighted sums are

Here we used $v_i=v_X$ for $i\in X$ and $v_j=v_Y$ for $j\in Y$, since $\theta$ is synchronized on each of $X$ and $Y$, together with $p(X)=\sum_{i\in X}p_i$ and $p(Y)=\sum_{j\in Y}p_j$. By Corollary 2.10, if both sums are nonzero, they point in the same direction. The first sum is nonzero because $p(X)>0$ and $v_X\ne0$. We next show that the second sum is nonzero. Set $w_Z := \sum_{k\in Z}q_kv_k$. Suppose, to the contrary, that $\alpha p(Y)v_Y+w_Z=0$, so that $w_Z=-\alpha p(Y)v_Y$. Applying Corollary 2.9 to the cuts $(Y,X\cup Z)$ and $(Z,X\cup Y)$, using (13) and (7), respectively, gives

Adding these inequalities yields $0\le-2\alpha p(Y)^2<0$, a contradiction. Thus the second sum is also nonzero. Applying Corollary 2.10 to these two nonzero sums and using $p(X)>0$, we obtain a scalar $\lambda_X>0$ such that

Similarly, applying the same argument to the cut $(Y,X\cup Z)$ gives a scalar $\lambda_Y>0$ such that

Eliminating the common term $\sum_{k\in Z}q_kv_k$ from (14) and (15), we obtain

Since $\alpha>0$, $p(X)>0$, $p(Y)>0$, $\lambda_X>0$, and $\lambda_Y>0$, both coefficients are strictly positive. Therefore, $v_X=v_Y$, and hence $\theta_X\equiv\theta_Y\pmod{2\pi}$.

Proof. By symmetry, we may assume that

Since $\rho_A(Y)=1$, the cut matrix $A[Y,X\cup Z]$ has rank one. Moreover,

and $A[Y,X]\ne0$. Hence we may write

where $a\in\mathbb{R}^{Y}$ and $b\in\mathbb{R}^{X}$ are nonzero and entrywise nonnegative. Thus

For the cut $(Y,X\cup Z)$, the corresponding weighted sums are

Since $\theta$ is synchronized on both $X$ and $Y$,

Both coefficients are strictly positive, so both weighted sums are nonzero. Corollary 2.10 therefore implies that they point in the same direction. Hence $v_X=v_Y$, and consequently $\theta_X\equiv\theta_Y\pmod{2\pi}$. □

:::

Proof of Theorem 1.1

Figure 7 illustrates the tree labeling used in the proof below.

Proof. Assume $\theta$ is a local minimum or a non-flat first- and second-order point of $E_A(\theta)$. In either case, it satisfies (FOC) and (SOC). The support graph of $A$ is connected by assumption.

Let $(T,L)$ be a rank-decomposition of $A$ of width one. Choose an arbitrary edge $e=uv$ of $T$. Deleting $e$ from $T$ produces two subtrees $T_u$ and $T_v$, which we view as rooted at $u$ and $v$, respectively. Let $S_u,S_v\subseteq V$ be the sets corresponding, via $L$, to the leaves of these rooted trees. Thus $V=S_u\mathbin{\dot\cup}S_v$.

We now label each node $t$ of $T_u$ by a set $S_t\subseteq V$. For $t\ne u$, let $e_t$ be the unique edge incident to $t$ on the path from $t$ to $u$. Deleting $e_t$ from $T_u$ produces a component containing $t$; view this component as a tree $T_t$ rooted at $t$. Let $S_t$ be the set of vertices corresponding, via $L$, to the leaves of $T_t$. In particular, if $t=L(i)$ is a leaf of $T$, then $S_t=\{i\}$. Apply the same procedure to the nodes of $T_v$. Here a rooted tree consisting of a single node has that node as its leaf.

The cut $(S_t,V\setminus S_t)$ is induced by $e$ when $t\in\{u,v\}$, and by $e_t$ otherwise. Since $(T,L)$ has width one, $\rho_A(S_t)\le1$. Connectedness of the support graph and $\varnothing\ne S_t\subsetneq V$ imply that the corresponding cut matrix is nonzero. Hence $\rho_A(S_t)=1$ for every node $t$ of $T$.

We first show that $\theta$ is synchronized on $S_t$ for every node $t$, by induction on $|S_t|$. If $|S_t|=1$, there is nothing to prove. Assume $|S_t|\ge2$. Then $t$ is not a leaf; let $t_1,t_2$ be its two children. By construction, $S_t=S_{t_1}\mathbin{\dot\cup}S_{t_2}$, so $S_{t_1},S_{t_2},V\setminus S_t$ partition $V$ into three nonempty sets. By the induction hypothesis, $\theta$ is synchronized on $S_{t_1}$ and on $S_{t_2}$. Since

Lemma 3.3 implies that $\theta$ is synchronized on $S_{t_1}\cup S_{t_2}=S_t$. This completes the induction.

It remains to show that the phases on $S_u$ and $S_v$ agree. Let $w_u,w_v$ be their respective common unit vectors. The cut matrix $A[S_u,S_v]$ is nonzero, entrywise nonnegative, and of rank one, so write

with nonzero, entrywise nonnegative vectors $p\in\mathbb{R}^{S_u}$ and $q\in\mathbb{R}^{S_v}$. The corresponding weighted sums are

Both are nonzero because $p(S_u),q(S_v)>0$. By Corollary 2.10, they point in the same direction. Since $w_u$ and $w_v$ are unit vectors, they are equal. As $S_u\cup S_v=V$, it follows that

Sharpness and examples

Sharpness in the unweighted case

Neither conclusion of Corollary 1.3 extends to all unweighted graphs of real rank-width two, as witnessed by every cycle $C_n$ with $n \ge5$. We use the standard twisted-state construction on rings; see [36] for background.

Figure 8 illustrates the case $n=5$.

Proof. The rank-width assertion follows from Example 2.5(3). Label the vertices of $C_n$ cyclically by $1,\ldots,n$ and consider the 1-twisted state

Its phases are not all equal, so $\theta$ is nonsynchronized. At every vertex, the phase differences with its two neighbors are $\pm2\pi/n$ modulo $2\pi$. The two sine terms in (FOC) therefore cancel, so $\theta$ is a first-order point of $E_A(\theta)$.

At this state, every edge satisfies $\cos(\theta_i-\theta_j)=\cos(2\pi/n)$. Therefore, the Hessian is

where $L_{C_n}=2I-A$ is the graph Laplacian of $C_n$ and $I$ is the $n \times n$ identity matrix. Since $n \ge5$, we have $\cos(2\pi/n)>0$. Since $C_n$ is connected,

so $\theta$ satisfies both the first- and second-order conditions. Lemma 2.2 implies that it is non-flat. Therefore, it is a non-flat nonsynchronized first- and second-order point.

To verify local minimality, let $\boldsymbol{h} \in\mathbb{R}^{n}$ be an arbitrary sufficiently small perturbation and set $g(t)=E_A(\boldsymbol{\theta}+t\boldsymbol{h})$ for $t\in[0,1]$. Stationarity gives $g'(0)=0$, and

where indices are interpreted modulo $n$. Since every edge satisfies $\cos(\theta_i-\theta_{i+1})=\cos(2\pi/n)>0$, all cosine factors remain positive for every $t\in[0,1]$ when $\boldsymbol{h}$ is sufficiently small. Consequently,

Equality holds if and only if $h_1=\cdots=h_n$, that is, the perturbation is a common rotation. Thus $\boldsymbol{\theta}$ is a strict local minimum modulo global rotation, and in particular a local minimum. □

Sharpness in the weighted case

The weighted graph in Figure 1(C) establishes sharpness of both conclusions of Theorem 1.1, even when the support graph is complete.

and $\ker H = \operatorname{span}\{1\}$, so Lemma 2.2 gives non-flatness. Since the phases are not all equal, the configuration is not a global minimum by (3). □

For example, $\varepsilon= 1/10$ gives nonzero Hessian eigenvalues approximately 0.13435 and 1.00623, each with multiplicity two. The corresponding equilibrium is locally asymptotically stable modulo global rotation, because the linearization of (1) is $-H$. Hence it attracts an open set of initial conditions and also rules out almost-everywhere convergence to a synchronization configuration. In particular, the distance-hereditary support condition cannot replace the weighted cut-rank condition in Theorem 1.1.

Acknowledgements

The author thanks Monique Laurent for helpful discussions, careful reading of the manuscript, and valuable suggestions on the proofs and presentation.

Declaration of AI use

Large language models were used to improve the presentation of the results through language editing and assistance with TikZ code for figures. All mathematical results and proofs are the author’s own, and the author takes full responsibility for all content.

References