betaFeedback

WorksMathematics

Laplacian Eigenvectors of Generically Weighted Graphs Have Pairwise Distinct Coordinates

Abstract

Poignard, Pereira and Pade conjectured that, for a generic choice of the nonzero weights of a given graph, the Fiedler vector of the weighted Laplacian has pairwise distinct coordinates. We give a proof that also covers every nonconstant eigenvector. For each connected graph on n vertices we construct a nonzero homogeneous polynomial with integer coefficients in the edge weights, of degree n(n-1)(n^2-n+2)/4, which vanishes at a positive weighting exactly when the Laplacian has a repeated eigenvalue, an eigenvector with a zero coordinate, or a nonconstant eigenvector with two equal coordinates. The exceptional weights therefore lie in an algebraic hypersurface, which gives structural genericity in the sense of Poignard, Pereira and Pade; algebraically independent weights are never exceptional, and there are good integer weights not exceeding the degree plus one. The polynomial is a product of Krylov determinants. Its nonvanishing follows by induction on trees: when a leaf is attached with a small weight, a cut identity gives the first-order profile of the new eigenvector and separates the coordinates that coincide in the limit. Exact small cases show that exceptional weightings need not be symmetric.

Introduction

The conjecture

Let Γ=(V,E)\Gamma=(V,E) be a finite simple graph with vertex set V={1,…,n}V=\{1,\ldots,n\}, and let w=(we)e∈Ew=(w_e)_{e\in E} be positive edge weights. The weighted Laplacian is

LΓ(w)=∑{i,j}∈Ewij(ei−ej)(ei−ej)T(1)L_{\Gamma}(w)=\sum_{\{i,j\}\in E}w_{ij}(e_i-e_j)(e_i-e_j)^{\mathsf T} \tag*{(1)}

that is, LΓ(w)=D−WL_{\Gamma}(w)=D-W with WW the weighted adjacency matrix and DD the diagonal matrix of weighted degrees. It is symmetric and positive semidefinite, and it annihilates the constant vector 1\mathbf{1}. When Γ\Gamma is connected its eigenvalues can be written

0=λ1<λ2≤⋯≤λn.0=\lambda_1<\lambda_2\le\cdots\le\lambda_n.

The number λ2\lambda_2 is the algebraic connectivity of the weighted graph [1], and an eigenvector of λ2\lambda_2 is a Fiedler vector. Its coordinates order and split the vertices in spectral partitioning and seriation [2, 3], and they govern how diffusively coupled networks gain or lose synchronization when the coupling structure is modified [4].

Poignard, Pereira and Pade [4] studied which spectral properties hold for a generic choice of the weights when the graph, that is, the set of nonzero weights, is kept fixed. For connected undirected graphs with positive weights they proved that the following properties are generic in this structural sense: all eigenvalues are simple [4 Theorem 3.1]; the Fiedler vector has no zero entry [4 Theorem 3.2]; and there is a basis of eigenvectors without zero entries [4 Corollary 5.1]. Their paper closes with a conjecture [4 Section 7]: for a generic choice of the nonzero weights of a given graph, “the Fiedler vector has only distinct coordinates”. We show that the same holds for every nonconstant eigenvector simultaneously and that the exceptional weights are cut out by a single explicit polynomial; simplicity of the spectrum and the absence of zero coordinates come out of the same argument.

Results

Throughout, an eigenvector is a nonzero vector, and all statements about eigenvectors are invariant under rescaling.

Definition 1.1 (Separating weights). Let Γ\Gamma be a connected graph on n≥2n \ge2 vertices. A weight vector w∈(0,∞)Ew \in(0,\infty)^E is separating if

(S1) the nn eigenvalues of LΓ(w)L_\Gamma(w) are pairwise distinct;

(S2) no eigenvector of LΓ(w)L_\Gamma(w) has a zero coordinate;

(S3) every eigenvector of LΓ(w)L_\Gamma(w) orthogonal to 1\mathbf{1} has pairwise distinct coordinates.

We write SΓ⊂(0,∞)ES_\Gamma\subset(0,\infty)^E for the set of separating weights.

Under (S1) the eigenvectors orthogonal to 1\mathbf{1} are exactly the eigenvectors of λ2,…,λn\lambda_2,\ldots,\lambda_n, that is, the nonconstant eigenvectors. In particular, for separating weights the Fiedler vector is unique up to a scalar, and its coordinates are nonzero and pairwise distinct.

Theorem 1.2 (Separating weights are generic). Let Γ=(V,E)\Gamma= (V,E) be a connected graph on n≥2n \ge2 vertices. There is a nonzero homogeneous polynomial PΓ∈Z[we:e∈E]P_\Gamma\in\mathbb{Z}[w_e : e \in E] of degree

dn=n(n−1)(n2−n+2)4(2)d_n = \frac{n(n-1)(n^2-n+2)}{4} \tag*{(2)}

such that, for every w∈(0,∞)Ew \in(0,\infty)^E,

w is separating⟺PΓ(w)≠0.w\text{ is separating}\quad\Longleftrightarrow\quad P_\Gamma(w)\ne0.

Consequently SΓS_\Gamma is an open dense cone in (0,∞)E(0,\infty)^E, and its complement in (0,∞)E(0,\infty)^E is a relatively closed set of Lebesgue measure zero, contained in the real algebraic set {PΓ=0}\{P_\Gamma=0\}.

The polynomial is explicit: PΓ(w)=Pn(LΓ(w))P_\Gamma(w)=P_n(L_\Gamma(w)), where PnP_n is the product of Krylov determinants defined in (9). The theorem is the equivalence of Proposition 3.3, which is linear algebra, together with the assertion that PΓP_\Gamma is not the zero polynomial, which requires one separating weighting of one spanning tree and is the substance of the proof.

In the language of [4], Theorem 1.2 reads as follows.

Corollary 1.3 (Structural genericity; the conjecture). Let Γ\Gamma be a connected graph on n≥2n \ge2 vertices.

(i) For every w∈(0,∞)Ew \in(0,\infty)^E and every ϵ>0\epsilon> 0 there is w′∈SΓw' \in S_\Gamma with max⁡e∈E∣we′−we∣<ϵ\max_{e\in E}|w'_e-w_e|<\epsilon.

(ii) For every w∈(0,∞)Ew \in(0,\infty)^E, the set of perturbations t∈REt \in\mathbb{R}^E for which w+tw+t lies in (0,∞)E(0,\infty)^E and is not separating has Lebesgue measure zero.

Hence the property “λ2\lambda_2 is simple and the Fiedler vector has pairwise distinct coordinates”, and more strongly the conjunction of (S1)–(S3), is structurally generic among the Laplacian matrices of connected undirected graphs in the sense of [4 Definition 2.2]. In particular the conjecture of [4 Section 7] holds.

Since the polynomial has integer coefficients, genericity also takes arithmetic and probabilistic forms.

Corollary 1.4 (Arithmetic and probabilistic forms). Let Γ\Gamma be a connected graph on n≥2n \ge2 vertices and dnd_n the degree (2).

(i) If the positive numbers (we)e∈E(w_e)_{e\in E} are algebraically independent over Q\mathbb{Q}, then ww is separating.

(ii) If ww is a random vector whose law is absolutely continuous with respect to Lebesgue measure on (0,∞)E(0,\infty)^E, then ww is separating almost surely.

(iii) If the weights are independent and uniformly distributed on {1,…,N}\{1,\ldots,N\}, then ww fails to be separating with probability at most dn/Nd_n/N. In particular there are separating integer weights with 1≤we≤dn+11 \le w_e \le d_n+1 for every edge.

The examples of § 6 show what the exceptional set looks like. Symmetric weightings are always exceptional when n≥3n \ge3 (Proposition 6.4), which explains why unweighted graphs so often have Fiedler vectors with repeated entries; the converse fails, since some weightings without any symmetry have a Fiedler vector with a zero coordinate or with two equal coordinates (Examples 6.5 and 6.6). For the path on three vertices and for the triangle the exceptional sets are computed exactly (Examples 6.2 and 6.3), and on every weighted path the Fiedler vector is strictly monotone, although it may vanish at a vertex and the other eigenvectors may have ties (Proposition 6.7).

Strategy

The proof combines an algebraic certificate with an explicit witness.

A certificate. For a symmetric matrix AA with A1=0A\mathbf{1}=0, the Krylov matrix of the coordinate vector eve_v has nonzero determinant exactly when AA has simple spectrum and no eigenvector vanishes at vv; the nonvanishing of this determinant is Kalman’s rank condition for controllability [5]. In the same way, the Krylov matrix of the difference ei−eje_i-e_j inside the invariant hyperplane 1⊥\mathbf{1}^{\perp} has full rank exactly when the spectrum on 1⊥\mathbf{1}^{\perp} is simple and no eigenvector there takes equal values at ii and jj. Since the columns of this matrix lie in 1⊥\mathbf{1}^{\perp}, one maximal minor already detects its rank. Multiplying the determinants for all vertices and these minors for all pairs gives a polynomial Pn(A)P_n(A) in the entries of AA whose nonvanishing is equivalent to (S1)–(S3) (Proposition 3.3).

A witness. The certificate reduces genericity to a single separating weighting, which shows that PΓ=Pn∘LΓP_{\Gamma}=P_n\circ L_{\Gamma} is not identically zero. Setting to zero the weights outside a spanning tree reduces this to trees (Lemma 3.4), and trees are handled by induction, attaching one leaf uu with a small weight ε\varepsilon to a tree TT that already has separating weights. The eigenvectors that continue those of TT keep their separated coordinates and acquire a small nonzero coordinate at uu. The difficulty is the new eigenvector, whose eigenvalue μ(ε)\mu(\varepsilon) tends to zero: in the limit it equals 11 on all of TT and −n-n at uu, so its coordinates on TT coincide to order zero. A summation identity over the two sides of an edge (Lemma 4.1) gives the expansion

xv−xa=μhv+O(μ2),hv=∑e∈[a,v]∣De∣we,x_v-x_a=\mu h_v+O(\mu^2), \qquad h_v=\sum_{e\in[a,v]}\frac{\lvert D_e\rvert}{w_e},

where aa is the vertex of attachment, [a,v][a,v] is the path from aa to vv and DeD_e is the set of vertices cut off from aa by the edge ee. The error is quadratic in μ\mu, with an explicit constant (Lemma 4.4(iii)), and this precision is what allows the first-order term to separate the coordinates. The numbers hvh_v are pairwise distinct for all weights outside a nowhere dense set, and then the coordinates are separated for small ε\varepsilon (Proposition 4.5).

Related work

Genericity of simple spectrum, and of nondegeneracy properties of eigenfunctions, is classical for Laplace operators on manifolds under perturbations of the metric [6]. For graphs with a fixed support the corresponding statements are due to Poignard, Pereira and Pade [4]. The argument given here is of a different kind: a polynomial identity takes the place of the perturbation of an arbitrary weighting, so that a single good weighting implies genericity. In this way it also yields the three genericity results of [4] quoted above, for undirected graphs, together with the separation of coordinates.

Krylov determinants of graph matrices are the subject of controllability theory. Godsil asked how often the pair formed by an adjacency matrix and the all-ones vector is controllable [7], and O’Rourke and Touri proved that this holds for almost all graphs [8]; simplicity of the spectrum of random symmetric matrices was established by Tao and Vu [9]. Those are statements about random discrete matrices. Here the support is arbitrary and fixed, and the weights are continuous parameters, which makes an algebraic argument available. Nodal properties of Laplacian eigenvectors on graphs are surveyed in [10].

Organization

Section § 2 collects notation, a lemma on zero sets of polynomials and two elementary perturbation facts. § 3 constructs the polynomial PnP_n and proves the certificate. § 4 treats trees. § 5 proves Theorem 1.2 and its corollaries. § 6 contains exact examples, the relation with symmetry and the case of paths, and § 7 collects remarks and open questions.

Preliminaries

Notation

Vectors in Rn\mathbb{R}^n are columns indexed by V={1,…,n}V=\{1,\ldots,n\}; e1,…,ene_1,\ldots,e_n is the standard basis, 1=e1+⋯+en\mathbf{1}=e_1+\cdots+e_n, and xvx_v or x(v)x(v) denotes the coordinate of xx at vv. The Euclidean norm and the induced operator norm are both written ∥⋅∥\|\cdot\|. We write

Zn={A∈Rn×n:A=AT, A1=0}\mathcal{Z}_n=\{A\in\mathbb{R}^{n\times n}: A=A^T,\ A\mathbf{1}=0\}

for the space of symmetric matrices with zero row sums. For A∈ZnA\in\mathcal{Z}_n the hyperplane 1⊥\mathbf{1}^{\perp} is invariant, since ⟨Ax,1⟩=⟨x,A1⟩=0\langle Ax,\mathbf{1}\rangle=\langle x,A\mathbf{1}\rangle=0. Conditions (S1)–(S3) make sense for every A∈ZnA\in\mathcal{Z}_n in place of LΓ(w)L_{\Gamma}(w), and we call AA separating when they hold.

A graph is finite, simple and undirected. For a graph Γ=(V,E)\Gamma=(V,E) and an arbitrary real vector w∈REw\in\mathbb{R}^{E}, formula (1) defines LΓ(w)∈ZnL_{\Gamma}(w)\in\mathcal{Z}_n; the map w↦LΓ(w)w\mapsto L_{\Gamma}(w) is linear. If E′⊂EE'\subset E and ww vanishes outside E′E', then

LΓ(w)=LΓ′(w∣E′),Γ′=(V,E′).(3)L_{\Gamma}(w)=L_{\Gamma'}(w|_{E'}),\qquad\Gamma'=(V,E'). \tag*{(3)}

Lemma 2.1. Let Γ\Gamma be a graph and w∈(0,∞)Ew\in(0,\infty)^E. Then

xTLΓ(w)x=∑{i,j}∈Ewij(xi−xj)2(x∈Rn)x^T L_{\Gamma}(w)x=\sum_{\{i,j\}\in E}w_{ij}(x_i-x_j)^2\qquad(x\in\mathbb{R}^n)

so LΓ(w)L_{\Gamma}(w) is positive semidefinite, and its kernel consists of the vectors that are constant on each connected component of Γ\Gamma. If Γ\Gamma is connected, the kernel is spanned by 1\mathbf{1}, every nonzero eigenvalue is positive, and its eigenvectors are orthogonal to 1\mathbf{1}.

Proof. The identity is immediate from (1). A positive semidefinite matrix annihilates exactly the vectors on which its quadratic form vanishes, which here are the vectors with xi=xjx_i=x_j for every edge. Eigenvectors of a symmetric matrix for different eigenvalues are orthogonal. □

Zero sets of polynomials

Lemma 2.2. Let P∈R[x1,…,xm]P\in\mathbb{R}[x_1,\ldots,x_m] be a nonzero polynomial and Z(P)={x∈Rm:P(x)=0}Z(P)=\{x\in\mathbb{R}^m:P(x)=0\}. Then Z(P)Z(P) is closed, has Lebesgue measure zero, and has empty interior. Consequently, for every nonempty open set U⊂RmU\subset\mathbb{R}^m, the set U∖Z(P)U\setminus Z(P) is open, dense in UU, and of full measure in UU.

Proof. Z(P)Z(P) is closed because PP is continuous. We prove by induction on mm that it is a null set. For m=1m=1 it is finite. Let m>1m>1 and write P=∑j=0dPj(x′)xmjP=\sum_{j=0}^{d}P_j(x')x_m^j with x′=(x1,…,xm−1)x'=(x_1,\ldots,x_{m-1}) and Pd≠0P_d\ne0. By induction the set N′={x′:Pd(x′)=0}N'=\{x':P_d(x')=0\} is null in Rm−1\mathbb{R}^{m-1}. For x′∉N′x'\notin N' the polynomial P(x′,⋅)P(x',\cdot) is nonzero, so the slice {xm:P(x′,xm)=0}\{x_m:P(x',x_m)=0\} is finite. By Tonelli’s theorem, applied to the indicator function of the closed set Z(P)Z(P), the measure of Z(P)Z(P) is the integral over x′x' of the one-dimensional measures of its slices, which vanish outside the null set N′N'. A null set has empty interior, and the remaining assertions follow. □

Two perturbation facts

For a real symmetric matrix AA of order NN let λ1(A)≤⋯≤λN(A)\lambda_1(A) \le\cdots\le\lambda_N(A) be its eigenvalues. Weyl’s inequality [11 Section 4.3] states that

∣λk(A)−λk(B)∣≤∥A−B∥(1≤k≤N)(4)\left|\lambda_k(A)-\lambda_k(B)\right| \le\lVert A-B\rVert\qquad(1 \le k \le N) \tag*{(4)}

for real symmetric AA and BB.

Lemma 2.3 (Stability of a simple eigenpair). Let AA be real symmetric with a simple eigenvalue λ\lambda, unit eigenvector ϕ\phi, and gap δ=min⁡{∣λ−λ′∣:λ′∈spec⁡(A), λ′≠λ}>0\delta= \min\{|\lambda-\lambda'|:\lambda' \in\operatorname{spec}(A),\ \lambda' \ne\lambda\} > 0. Let BB be real symmetric with ρ=∥B−A∥<δ/2\rho= \lVert B-A\rVert< \delta/2. Then BB has exactly one eigenvalue λB\lambda_B, counted with multiplicity, in the interval (λ−δ/2,λ+δ/2)(\lambda-\delta/2,\lambda+\delta/2); it satisfies ∣λB−λ∣≤ρ|\lambda_B-\lambda| \le\rho, and it has a unit eigenvector ϕB\phi_B with

∥ϕB−ϕ∥≤22ρδ.\lVert\phi_B-\phi\rVert\le\frac{2\sqrt{2}\rho}{\delta}.

Proof. Let λ=λk(A)\lambda= \lambda_k(A). By (4), λB:=λk(B)\lambda_B := \lambda_k(B) satisfies ∣λB−λ∣≤ρ<δ/2|\lambda_B-\lambda| \le\rho< \delta/2, while for j≠kj \ne k we have ∣λj(B)−λ∣≥∣λj(A)−λ∣−ρ≥δ−ρ>δ/2|\lambda_j(B)-\lambda| \ge|\lambda_j(A)-\lambda|-\rho\ge\delta-\rho> \delta/2. This proves the first two assertions. Let yy be a unit eigenvector of BB for λB\lambda_B and write y=cϕ+ry = c\phi+r with r⊥ϕr \perp\phi. Then

(A−λ)r=(A−λ)y=(A−B)y+(λB−λ)y,(A-\lambda)r=(A-\lambda)y=(A-B)y+(\lambda_B-\lambda)y,

whose norm is at most 2ρ2\rho. On ϕ⊥\phi^\perp the symmetric operator A−λA-\lambda has all its eigenvalues of absolute value at least δ\delta, so ∥(A−λ)r∥≥δ∥r∥\lVert(A-\lambda)r\rVert\ge\delta\lVert r\rVert and ∥r∥≤2ρ/δ<1\lVert r\rVert\le2\rho/\delta< 1. Replacing yy by −y-y if necessary we may assume c≥0c \ge0, so c=1−∥r∥2c=\sqrt{1-\lVert r\rVert^2} and

∥y−ϕ∥2=(1−c)2+∥r∥2=2−21−∥r∥2≤2∥r∥2,\lVert y-\phi\rVert^2=(1-c)^2+\lVert r\rVert^2=2-2\sqrt{1-\lVert r\rVert^2}\le2\lVert r\rVert^2,

because 1−1−s≤s1-\sqrt{1-s}\le s for 0≤s≤10\le s\le1. Take ϕB=y\phi_B=y. □

A polynomial certificate

Krylov matrices

For a square matrix AA, a vector bb and an integer r≥1r \ge1, the Krylov matrix is the matrix with columns b,Ab,…,Ar−1bb, Ab,\ldots,A^{r-1}b.

Lemma 3.1 (Krylov determinants). Let AA be a real symmetric n×nn\times n matrix and H⊂RnH \subset\mathbb{R}^n an AA-invariant subspace of dimension r≥1r \ge1. Let u1,…,uru_1,\ldots,u_r be an orthonormal basis of HH consisting of eigenvectors of AA, with Auk=μkukAu_k=\mu_k u_k. For b∈Hb \in H put K=[b,Ab,…,Ar−1b]∈Rn×rK=[b,Ab,\ldots,A^{r-1}b]\in\mathbb{R}^{n\times r}. Then

det⁡(KTK)=∏k=1r⟨uk,b⟩2∏1≤k<l≤r(μl−μk)2.(5)\det(K^{T}K)=\prod_{k=1}^{r}\langle u_k,b\rangle^2\prod_{1\le k<l\le r}(\mu_l-\mu_k)^2. \tag*{(5)}

If H=RnH=\mathbb{R}^n, so that r=nr=n and KK is square, then

det⁡K=±∏k=1n⟨uk,b⟩∏1≤k<l≤n(μl−μk).(6)\det K=\pm\prod_{k=1}^{n}\langle u_k,b\rangle\prod_{1\le k<l\le n}(\mu_l-\mu_k). \tag*{(6)}

Proof. Since b=∑k⟨uk,b⟩ukb=\sum_k\langle u_k,b\rangle u_k, we have Ajb=∑k⟨uk,b⟩μkjukA^j b=\sum_k\langle u_k,b\rangle\mu_k^j u_k for j≥0j\ge0. Hence

K=UCM,U=[u1,…,ur],C=diag⁡(⟨uk,b⟩)k=1r,M=(μkj−1)k,j=1r.K=UCM,\qquad U=[u_1,\ldots,u_r],\qquad C=\operatorname{diag}(\langle u_k,b\rangle)_{k=1}^{r},\qquad M=(\mu_k^{j-1})_{k,j=1}^{r}.

The matrix MM is a Vandermonde matrix, with det⁡M=∏k<l(μl−μk)\det M=\prod_{k<l}(\mu_l-\mu_k). Since UTU=IrU^TU=I_r, we get KTK=MTC2MK^TK=M^TC^2M, which gives (5). If r=nr=n, then UU is orthogonal, det⁡U=±1\det U=\pm1, and det⁡K=det⁡Udet⁡Cdet⁡M\det K=\det U\det C\det M. □

In words: det⁡(KTK)≠0\det(K^TK)\ne0 if and only if the restriction of AA to HH has rr distinct eigenvalues and bb is orthogonal to none of its eigenvectors. Such a vector bb is called cyclic for A∣HA|_H.

Lemma 3.2 (Reduced Gram determinants). Let K∈Rn×(n−1)K\in\mathbb{R}^{n\times(n-1)} be a matrix whose columns lie in 1⊥\mathbf{1}^{\perp}, and let K~\widetilde{K} be the square matrix obtained by deleting its last row. Then

det⁡(KTK)=n(det⁡K~)2.\det(K^TK)=n\left(\det\widetilde{K}\right)^2.

Proof. For r∈Vr \in V let K(r)K^{(r)} be the matrix obtained from KK by deleting row rr, so that K~=K(n)\widetilde{K}=K^{(n)}. By the Cauchy–Binet formula,

det⁡(KTK)=∑r=1n(det⁡K(r))2.\det(K^{T}K)=\sum_{r=1}^{n}\left(\det K^{(r)}\right)^2.

Let ρ1,…,ρn\rho_1,\ldots,\rho_n be the rows of KK. Since every column lies in 1⊥\mathbf{1}^{\perp}, ρ1+⋯+ρn=0\rho_1+\cdots+\rho_n=0. Let r<nr<n. Adding to the row ρr\rho_r of K(n)K^{(n)} all its other rows does not change the determinant and replaces ρr\rho_r by ρ1+⋯+ρn−1=−ρn\rho_1+\cdots+\rho_{n-1}=-\rho_n. The resulting matrix differs from K(r)K^{(r)} only by the sign of one row and the position of that row. Hence ∣det⁡K(r)∣=∣det⁡K~∣\lvert\det K^{(r)}\rvert=\lvert\det\widetilde{K}\rvert for every rr, and the sum equals n(det⁡K~)2n(\det\widetilde{K})^2.

The polynomial

Let n≥2n\ge2. For A∈ZnA\in\mathbb{Z}_n, a vertex vv and a pair i<ji<j define

κv(A)=det⁡[ev,Aev,…,An−1ev],(7)\kappa_v(A)=\det[e_v,Ae_v,\ldots,A^{n-1}e_v], \tag*{(7)}
Kij(A)=[ei−ej,A(ei−ej),…,An−2(ei−ej)]∈Rn×(n−1),K_{ij}(A)=[e_i-e_j,A(e_i-e_j),\ldots,A^{n-2}(e_i-e_j)]\in\mathbb{R}^{n\times(n-1)},
δij(A)=det⁡K~ij(A),(8)\delta_{ij}(A)=\det\widetilde{K}_{ij}(A), \tag*{(8)}

where K~ij(A)\widetilde{K}_{ij}(A) is obtained from Kij(A)K_{ij}(A) by deleting its last row, and

Pn(A)=∏v=1nκv(A)⋅∏1≤i<j≤nδij(A),PΓ(w)=Pn(LΓ(w))(w∈RE).(9)P_n(A)=\prod_{v=1}^{n}\kappa_v(A)\cdot\prod_{1\le i<j\le n}\delta_{ij}(A),\qquad P_{\Gamma}(w)=P_n(L_{\Gamma}(w))\quad(w\in\mathbb{R}^{E}). \tag*{(9)}

The columns of Kij(A)K_{ij}(A) lie in 1⊥\mathbf{1}^{\perp}, because ei−ej∈1⊥e_i-e_j\in\mathbf{1}^{\perp} and 1⊥\mathbf{1}^{\perp} is AA-invariant; by Lemma 3.2, det⁡(Kij(A)TKij(A))=nδij(A)2\det(K_{ij}(A)^{T}K_{ij}(A))=n\delta_{ij}(A)^2. For n=2n=2 the matrix K~12(A)\widetilde{K}_{12}(A) is the 1×11\times1 matrix (1)(1) and δ12=1\delta_{12}=1.

Proposition 3.3 (Certificate). Let n≥2n\ge2 and A∈ZnA\in\mathbb{Z}_n. Let u1=1/n,u2,…,unu_1=1/\sqrt{n},u_2,\ldots,u_n be an orthonormal basis of eigenvectors of AA, with eigenvalues μ1=0,μ2,…,μn\mu_1=0,\mu_2,\ldots,\mu_n. Then

κv(A)=±1n∏k=2nuk(v)∏1≤k<l≤n(μl−μk).(10)\kappa_v(A)=\pm\frac{1}{\sqrt{n}}\prod_{k=2}^{n}u_k(v)\prod_{1\le k<l\le n}(\mu_l-\mu_k). \tag*{(10)}
δij(A)2=1n∏k=2n(uk(i)−uk(j))2∏2≤k<l≤n(μl−μk)2.(11)\delta_{ij}(A)^2=\frac{1}{n}\prod_{k=2}^{n}(u_k(i)-u_k(j))^2\prod_{2\le k<l\le n}(\mu_l-\mu_k)^2. \tag*{(11)}

Consequently Pn(A)≠0P_n(A)\ne0 if and only if AA is separating, that is, if and only if (S1), (S2) and (S3) hold for AA.

Proof. Such a basis exists because 1\mathbf{1} is an eigenvector for the eigenvalue 00 and 1⊥\mathbf{1}^{\perp} is invariant. Formula (10) is (6) with b=evb=e_v, since ⟨uk,ev⟩=uk(v)\langle u_k,e_v\rangle=u_k(v) and u1(v)=n−1/2u_1(v)=n^{-1/2}. Formula (11) follows from (5), applied with H=1⊥H=\mathbf{1}^{\perp}, r=n−1r=n-1, the basis u2,…,unu_2,\ldots,u_n, and b=ei−ej∈1⊥b=e_i-e_j\in\mathbf{1}^{\perp}, since ⟨uk,ei−ej⟩=uk(i)−uk(j)\langle u_k,e_i-e_j\rangle=u_k(i)-u_k(j), together with det⁡(KijTKij)=nδij2\det(K_{ij}^{T}K_{ij})=n\delta_{ij}^2.

Suppose Pn(A)≠0P_n(A)\ne0. Then κ1(A)≠0\kappa_1(A)\ne0, so by (10) the numbers μ1,…,μn\mu_1,\ldots,\mu_n are pairwise distinct, which is (S1). Every eigenvector is then a multiple of some uku_k. The eigenvector u1u_1 has no zero coordinate, and uk(v)≠0u_k(v)\ne0 for k≥2k\ge2 and every vv because κv(A)≠0\kappa_v(A)\ne0; this is (S2). The eigenvectors orthogonal to 1\mathbf{1} are the multiples of u2,…,unu_2,\ldots,u_n, and uk(i)≠uk(j)u_k(i)\ne u_k(j) for i<ji<j because δij(A)≠0\delta_{ij}(A)\ne0; this is (S3). Conversely, if (S1)–(S3) hold, every factor on the right of (10) and (11) is nonzero.

:::

Lemma 3.4 (Integrality, degree, restriction). Let Γ=(V,E)\Gamma=(V,E) be a graph on n≥2n\ge2 vertices.

  1. PΓP_{\Gamma} is a polynomial in the variables (we)e∈E(w_e)_{e\in E} with integer coefficients. It is either zero or homogeneous of degree dn=n(n−1)(n2−n+2)/4d_n=n(n-1)(n^2-n+2)/4.

  2. If Γ′=(V,E′)\Gamma'=(V,E') with E′⊂EE'\subset E, and w∈REw\in\mathbb{R}^{E} vanishes outside E′E', then PΓ(w)=PΓ′(w∣E′)P_{\Gamma}(w)=P_{\Gamma'}(w|_{E'}).

  3. If Γ\Gamma is disconnected, then PΓ=0P_{\Gamma}=0.

Proof. (i) The entries of L=LΓ(w)L=L_{\Gamma}(w) are linear forms in ww with integer coefficients, so the entries of LkL^k are integer polynomials, each zero or homogeneous of degree kk. In the expansion of the determinant (7) every term takes one entry from each of the columns eve_v, Lev,…,Ln−1evLe_v,\ldots,L^{n-1}e_v; hence κv\kappa_v is zero or homogeneous of degree 0+1+⋯+(n−1)=n(n−1)/20+1+\cdots+(n-1)=n(n-1)/2. In the same way, the column of K~ij\widetilde{K}_{ij} formed by the first n−1n-1 entries of Lk(ei−ej)L^k(e_i-e_j) has degree kk for 0≤k≤n−20\leq k\leq n-2, so δij\delta_{ij} is zero or homogeneous of degree 0+1+⋯+(n−2)=(n−1)(n−2)/20+1+\cdots+(n-2)=(n-1)(n-2)/2. Adding the degrees of the nn factors κv\kappa_v and the (n2)\binom{n}{2} factors δij\delta_{ij} gives

n⋅n(n−1)2+(n2)(n−1)(n−2)2=n(n−1)2⋅2n+(n−1)(n−2)2=dn.n\cdot\frac{n(n-1)}{2}+\binom{n}{2}\frac{(n-1)(n-2)}{2} =\frac{n(n-1)}{2}\cdot\frac{2n+(n-1)(n-2)}{2}=d_n.

(ii) follows from (3), because PΓ(w)P_{\Gamma}(w) depends on ww only through the matrix LΓ(w)L_{\Gamma}(w). (iii) If Γ\Gamma is disconnected, then for every w∈REw\in\mathbb{R}^{E} the matrix LΓ(w)L_{\Gamma}(w) annihilates the indicator vector of each connected component, so 00 is a multiple eigenvalue and (S1) fails; by Proposition 3.3, PΓ(w)=0P_{\Gamma}(w)=0 for all ww.

Remark 3.5. The factors κv\kappa_v alone certify (S1) and (S2), which are the properties shown to be structurally generic in [4]. The factors δij\delta_{ij} are responsible for (S3): by Lemma 3.2, δij(A)\delta_{ij}(A) vanishes exactly when ei−eje_i-e_j fails to be cyclic for the restriction of AA to 1⊥\mathbf{1}^{\perp}. The Gram determinants det⁡(KijTKij)=nδij2\det(K_{ij}^{T}K_{ij})=n\delta_{ij}^{2} have the same zero sets, but using them would double the contribution of these factors to the degree. The degree dnd_n is not claimed to be minimal; see Question 7.3.

Trees

We now show that every tree on at least two vertices has separating weights (Proposition 4.7).

A summation identity

Lemma 4.1 (Cut identity). Let GG be a graph with real edge weights and Laplacian LL, and let DD be a set of vertices such that exactly one edge e={p,q}e=\{p,q\}, with q∈Dq\in D and p∉Dp\notin D, joins DD to its complement. If Lx=μxLx=\mu x, then

we(xq−xp)=μ∑v∈Dxv.w_e(x_q-x_p)=\mu\sum_{v\in D}x_v.

Proof. By (1), (Lx)v=∑v′wvv′(xv−xv′)(Lx)_v=\sum_{v'}w_{vv'}(x_v-x_{v'}), the sum running over the neighbours v′v' of vv. Sum this over v∈Dv\in D. An edge with both ends in DD contributes wvv′(xv−xv′)+wvv′(xv′−xv)=0w_{vv'}(x_v-x_{v'})+w_{vv'}(x_{v'}-x_v)=0, and the only other edge meeting DD is ee, which contributes we(xq−xp)w_e(x_q-x_p). The left side of Lx=μxLx=\mu x therefore sums to we(xq−xp)w_e(x_q-x_p) and the right side to μ∑v∈Dxv\mu\sum_{v\in D}x_v.

Attaching a leaf

Fix the following data for this subsection (Figure 1).

Figure 1. Attaching a leaf uu at the vertex aa of a tree TT with a small weight ε\varepsilon. The edge e={p,q}e=\{p,q\} separates the shaded vertex set DeD_e from aa. The eigenvector of the new small eigenvalue μ=μ(ε)\mu=\mu(\varepsilon) is constant on TT in the limit; the cut identity gives its first-order profile μhv\mu h_v, which separates the coordinates when the numbers hvh_v are pairwise distinct.

  • TT is a tree with vertex set V={1,…,n}V=\{1,\ldots,n\}, n≥2n\geq2, and w∈STw\in S_T is a separating weight vector. Let L=LT(w)L=L_T(w), with eigenvalues 0=λ1<λ2<⋯<λn0=\lambda_1<\lambda_2<\cdots<\lambda_n and unit eigenvectors ϕ1=1/n,ϕ2,…,ϕn\phi_1=\mathbf{1}/\sqrt{n},\phi_2,\ldots,\phi_n.

  • a∈Va\in V is a vertex, and T′T' is the tree obtained from TT by adding a new vertex uu and the edge {a,u}\{a,u\}. For ε>0\varepsilon>0 we give this edge the weight ε\varepsilon and write Lε=LT′(w,ε)L_{\varepsilon}=L_{T'}(w,\varepsilon). Ordering the vertices of T′T' as 1,…,n,u1,\ldots,n,u,

Lε=(L000)+ε(ea−eu)(ea−eu)T.(12)L_{\varepsilon} = \begin{pmatrix} L & 0\\ 0 & 0 \end{pmatrix} +\varepsilon(e_a-e_u)(e_a-e_u)^T. \tag*{(12)}
  • For an edge ee of TT, the graph T−eT-e has two connected components; De⊂VD_e\subset V denotes the vertex set of the component that does not contain aa. For v∈Vv\in V, [a,v][a,v] denotes the set of edges of the path from aa to vv in TT, and

hv=∑e∈[a,v]∣De∣we,ha=0.(13)h_v=\sum_{e\in[a,v]}\frac{|D_e|}{w_e},\qquad h_a=0. \tag*{(13)}

We use the positive constants

δ=min⁡1≤k<n(λk+1−λk),η=min⁡{∣ϕk(v)∣, ∣ϕk(i)−ϕk(j)∣: 2≤k≤n, v∈V, i≠j},\delta=\min_{1\leq k<n}(\lambda_{k+1}-\lambda_k),\qquad \eta=\min\left\{|\phi_k(v)|,\ |\phi_k(i)-\phi_k(j)|:\ 2\leq k\leq n,\ v\in V,\ i\ne j\right\},

which are positive because ww is separating, and

c=(n−1)2min⁡ewe,hmax⁡=max⁡v∈Vhv>0.c=\frac{(n-1)^2}{\min_e w_e},\qquad h_{\max}=\max_{v\in V}h_v>0.

Lemma 4.2 (Spectrum of LεL_\varepsilon). Let 0<ε<δ/40<\varepsilon<\delta/4. Then LεL_\varepsilon has n+1n+1 distinct eigenvalues: the eigenvalue 00; one eigenvalue μ(ε)∈(0,2ε]\mu(\varepsilon)\in(0,2\varepsilon]; and, for each k=2,…,nk=2,\ldots,n, exactly one eigenvalue λk(ε)\lambda_k(\varepsilon) with ∣λk(ε)−λk∣≤2ε|\lambda_k(\varepsilon)-\lambda_k|\leq2\varepsilon.

Proof. By (12), Lε−L0=ε(ea−eu)(ea−eu)TL_\varepsilon-L_0=\varepsilon(e_a-e_u)(e_a-e_u)^{\mathsf T} has norm 2ε2\varepsilon, and the eigenvalues of L0=L⊕0L_0=L\oplus0 in nondecreasing order are 0,0,λ2,…,λn0,0,\lambda_2,\ldots,\lambda_n. Let ν1≤⋯≤νn+1\nu_1\leq\cdots\leq\nu_{n+1} be the eigenvalues of LεL_\varepsilon. By (4), ∣ν1∣,∣ν2∣≤2ε|\nu_1|,|\nu_2|\leq2\varepsilon and ∣νk+1−λk∣≤2ε|\nu_{k+1}-\lambda_k|\leq2\varepsilon for 2≤k≤n2\leq k\leq n. Since TT is connected and its weights are positive, Lemma 2.1 gives ν1=0<ν2\nu_1=0<\nu_2; put μ(ε)=ν2\mu(\varepsilon)=\nu_2 and λk(ε)=νk+1\lambda_k(\varepsilon)=\nu_{k+1}. Because λ2≥δ\lambda_2\geq\delta and consecutive λk\lambda_k differ by at least δ>4ε\delta>4\varepsilon, the intervals [0,2ε][0,2\varepsilon] and [λk−2ε,λk+2ε][\lambda_k-2\varepsilon,\lambda_k+2\varepsilon], 2≤k≤n2\leq k\leq n, are pairwise disjoint. Hence the n+1n+1 eigenvalues are distinct. □

Lemma 4.3 (Eigenvectors continuing those of TT). Let 0<ε<min⁡{δ/4,δη/(122)}0<\varepsilon<\min\{\delta/4,\delta\eta/(12\sqrt{2})\} and 2≤k≤n2\leq k\leq n. Every eigenvector of LεL_\varepsilon for λk(ε)\lambda_k(\varepsilon) has nonzero, pairwise distinct coordinates.

Proof. In the spectrum {0,λ2,…,λn}\{0,\lambda_2,\ldots,\lambda_n\} of L0L_0 the eigenvalue λk\lambda_k is simple, with unit eigenvector (ϕk,0)(\phi_k,0) and gap at least δ\delta. Apply Lemma 2.3 with A=L0A=L_0, B=LεB=L_\varepsilon and ρ=2ε<δ/2\rho=2\varepsilon<\delta/2: the eigenvalue of LεL_\varepsilon in (λk−δ/2,λk+δ/2)(\lambda_k-\delta/2,\lambda_k+\delta/2) is λk(ε)\lambda_k(\varepsilon), and it has a unit eigenvector xx with

∥x−(ϕk,0)∥≤42εδ<η3.\lVert x-(\phi_k,0)\rVert\leq\frac{4\sqrt{2}\varepsilon}{\delta}<\frac{\eta}{3}.

Every coordinate of xx on VV is therefore within η/3\eta/3 of the corresponding coordinate of ϕk\phi_k. By the definition of η\eta,

∣xv∣>23η(v∈V),∣xi−xj∣>13η(i≠j in V).|x_v|>\frac{2}{3}\eta\quad(v\in V),\qquad|x_i-x_j|>\frac{1}{3}\eta\quad(i\ne j\text{ in }V).

The row of uu in Lεx=λk(ε)xL_\varepsilon x=\lambda_k(\varepsilon)x reads ε(xu−xa)=λk(ε)xu\varepsilon(x_u-x_a)=\lambda_k(\varepsilon)x_u, that is,

xu=−εxaλk(ε)−ε,λk(ε)−ε≥λk−3ε≥δ−3ε>δ4.x_u=-\frac{\varepsilon x_a}{\lambda_k(\varepsilon)-\varepsilon},\qquad \lambda_k(\varepsilon)-\varepsilon\geq\lambda_k-3\varepsilon\geq\delta-3\varepsilon>\frac{\delta}{4}.

Thus xu≠0x_u\ne0, because xa≠0x_a\ne0, and ∣xu∣<4ε/δ<η/3<∣xv∣|x_u|<4\varepsilon/\delta<\eta/3<|x_v| for every v∈Vv\in V, so xux_u differs from all other coordinates. Since λk(ε)\lambda_k(\varepsilon) is simple, every eigenvector is a multiple of xx. □

Lemma 4.4 (The new eigenvector). Let 0<ε<min⁡{δ/4,1/(4c)}0 < \varepsilon< \min\{\delta/4, 1/(4c)\}, let μ=μ(ε)\mu= \mu(\varepsilon), and let xx be an eigenvector of LεL_{\varepsilon} for μ\mu.

(i) ∑v∈Vxv≠0\sum_{v\in V} x_v \ne0. Normalizing xx so that ∑v∈Vxv=n\sum_{v\in V} x_v = n, we have xu=−nx_u = -n.

(ii) With this normalization, ∣xv−1∣≤2cμ\lvert x_v - 1\rvert\le2c\mu for every v∈Vv \in V; in particular xv>0x_v > 0.

(iii) With this normalization, for all v,v′∈Vv,v' \in V,

∣xv−xv′−μ(hv−hv′)∣≤4chmax⁡μ2.\lvert x_v-x_{v'}-\mu(h_v-h_{v'})\rvert\le4c h_{\max}\mu^2.

Proof. (i) Since μ≠0\mu\ne0, Lemma 2.1 applied to T′T' gives x⊥1x \perp\mathbf{1}, that is, ∑v∈Vxv+xu=0\sum_{v\in V}x_v+x_u=0. Suppose ∑v∈Vxv=0\sum_{v\in V}x_v=0. Then xu=0x_u=0, and the row of uu, ε(xu−xa)=μxu\varepsilon(x_u-x_a)=\mu x_u, gives xa=0x_a=0. By (12), the rows of VV then read Ly=μyLy=\mu y for y=(xv)v∈Vy=(x_v)_{v\in V}, and y≠0y\ne0 because x≠0x\ne0. So μ\mu would be an eigenvalue of LL in (0,2ε]⊂(0,δ)(0,2\varepsilon]\subset(0,\delta), whereas LL has no eigenvalue in (0,δ)(0,\delta). This contradiction proves ∑v∈Vxv≠0\sum_{v\in V}x_v\ne0, and the normalization gives xu=−nx_u=-n.

(ii) Let e={p,q}e=\{p,q\} be an edge of TT with q∈Deq\in D_e. The vertex aa does not belong to DeD_e, so no vertex of DeD_e is adjacent to uu, and ee is the only edge of T′T' joining DeD_e to its complement. Lemma 4.1 gives

xq−xp=μwe∑v∈Dexv.(14)x_q-x_p=\frac{\mu}{w_e}\sum_{v\in D_e}x_v. \tag*{(14)}

Let M=max⁡v∈V∣xv∣M=\max_{v\in V}\lvert x_v\rvert. Since ∣De∣≤n−1\lvert D_e\rvert\le n-1, the right side of (14) is at most μ(n−1)M/min⁡ewe\mu(n-1)M/\min_e w_e in absolute value. Two vertices of VV are joined in TT by a path with at most n−1n-1 edges, so ∣xv−xv′∣≤cμM\lvert x_v-x_{v'}\rvert\le c\mu M for all v,v′∈Vv,v'\in V. The mean of the xv′x_{v'} over VV equals 11; hence ∣xv−1∣≤cμM\lvert x_v-1\rvert\le c\mu M and M≤1+cμMM\le1+c\mu M. As cμ≤2cε≤1/2c\mu\le2c\varepsilon\le1/2, we get M≤2M\le2 and ∣xv−1∣≤2cμ<1\lvert x_v-1\rvert\le2c\mu<1.

(iii) Let a=v0,v1,…,vr=va=v_0,v_1,\ldots,v_r=v be the path from aa to vv and es={vs−1,vs}e_s=\{v_{s-1},v_s\}. The end of ese_s in DesD_{e_s} is vsv_s, so summing (14) over ss gives

xv−xa=μ∑e∈[a,v]1we∑v′∈Dexv′.x_v-x_a=\mu\sum_{e\in[a,v]}\frac{1}{w_e}\sum_{v'\in D_e}x_{v'}.

By (ii), ∣∑v′∈Dexv′−∣De∣∣≤2cμ∣De∣\left\lvert\sum_{v'\in D_e}x_{v'}-\lvert D_e\rvert\right\rvert\le2c\mu\lvert D_e\rvert. Comparing with (13),

∣xv−xa−μhv∣≤2cμ2hv≤2chmax⁡μ2,\lvert x_v-x_a-\mu h_v\rvert\le2c\mu^2h_v\le2c h_{\max}\mu^2,

and the claim follows by subtracting the same estimate for v′v'. □\square

Proposition 4.5 (Leaf attachment). In the setting above, suppose that the numbers hvh_v, v∈Vv\in V, are pairwise distinct, and let θ=min⁡v≠v′∣hv−hv′∣>0\theta=\min_{v\ne v'}\lvert h_v-h_{v'}\rvert>0. Then (w,ε)∈ST′(w,\varepsilon)\in S_{T'} for every

0<ε<ε0:=min⁡{δ4,δ122,14c,θ8chmax⁡}.0<\varepsilon<\varepsilon_0:=\min\left\{\frac{\delta}{4},\frac{\delta}{12\sqrt{2}},\frac{1}{4c},\frac{\theta}{8c h_{\max}}\right\}.

Proof. By Lemma 4.2 the spectrum of LεL_\varepsilon is simple, which is (S1), and every eigenvector is a multiple of 1\mathbf{1}, of an eigenvector of some λk(ε)\lambda_k(\varepsilon), or of an eigenvector of μ(ε)\mu(\varepsilon). The first has no zero coordinate. The second kind has nonzero, pairwise distinct coordinates by Lemma 4.3. For the third, normalize as in Lemma 4.4: then xv>0x_v>0 on VV and xu=−n<0x_u=-n<0, so no coordinate vanishes and xux_u differs from every xvx_v. For v≠v′v\ne v' in VV, part (iii) of that lemma and μ≤2ε\mu\le2\varepsilon give

∣xv−xv′∣≥μ(θ−4chmax⁡μ)≥μ(θ−8chmax⁡ε)>0.\lvert x_v-x_{v'}\rvert\ge\mu(\theta-4c h_{\max}\mu)\ge\mu(\theta-8c h_{\max}\varepsilon)>0.

Hence (S2) and (S3) hold. □\square

Every tree has separating weights

Lemma 4.6 (The profile hh is generically injective). Let TT be a tree on VV, n≥2n\ge2, let a∈Va\in V, and let v≠v′v\ne v' be vertices. The set of w∈(0,∞)E(T)w\in(0,\infty)^{E(T)} with hv(w)=hv′(w)h_v(w)=h_{v'}(w) is closed in (0,∞)E(T)(0,\infty)^{E(T)} and has empty interior.

Proof. The paths from aa to vv and from aa to v′v' share an initial segment and then separate; the symmetric difference of [a,v][a,v] and [a,v′][a,v'] is the edge set of the path from vv to v′v', which is nonempty. By (13),

hv−hv′=∑e∈[a,v]∖[a,v′]∣De∣we−∑e∈[a,v′]∖[a,v]∣De∣weh_v-h_{v'}=\sum_{e\in[a,v]\setminus[a,v']} \frac{|D_e|}{w_e}-\sum_{e\in[a,v']\setminus[a,v]} \frac{|D_e|}{w_e}

with at least one term and all ∣De∣≥1|D_e|\ge1. Multiplying by ∏ewe\prod_e w_e gives a polynomial Qvv′Q_{vv'} in which the monomials ∏e′≠ewe′\prod_{e'\ne e}w_{e'}, for the edges ee of the path from vv to v′v', are distinct and have the nonzero coefficients ±∣De∣\pm|D_e|. Thus Qvv′≠0Q_{vv'}\ne0, and on (0,∞)E(T)(0,\infty)^{E(T)} the equation hv=hv′h_v=h_{v'} is equivalent to Qvv′(w)=0Q_{vv'}(w)=0. Lemma 2.2 applies. □

Proposition 4.7 (Trees). For every tree TT on n≥2n\ge2 vertices, ST≠∅S_T\ne\varnothing.

Proof. By induction on nn. For n=2n=2 the Laplacian is w(1−1−11)w\begin{pmatrix}1&-1\\-1&1\end{pmatrix}, with eigenvalues 00 and 2w2w and eigenvectors (1,1)T(1,1)^{T} and (1,−1)T(1,-1)^{T}, so every w>0w>0 is separating.

Let T′T' be a tree on n+1≥3n+1\ge3 vertices. It has a leaf uu; let aa be its neighbour and T=T′−uT=T'-u, a tree on nn vertices. By the induction hypothesis ST≠∅S_T\ne\varnothing, and by Proposition 3.3, ST={w∈(0,∞)E(T):PT(w)≠0}S_T=\{w\in(0,\infty)^{E(T)}:P_T(w)\ne0\} is open. By Lemma 4.6, the set of weights for which two of the numbers hvh_v coincide is the zero set in (0,∞)E(T)(0,\infty)^{E(T)} of the nonzero polynomial ∏v<v′Qvv′\prod_{v<v'}Q_{vv'}, with Qvv′Q_{vv'} as in the proof of that lemma, and so has empty interior by Lemma 2.2. It therefore does not contain the nonempty open set STS_T. Choose w∈STw\in S_T with pairwise distinct hvh_v. By Proposition 4.5, (w,ε)∈ST′(w,\varepsilon)\in S_{T'} for all sufficiently small ε>0\varepsilon>0. □

Proofs of the main results

Proof of Theorem 1.2. Let w∈(0,∞)Ew\in(0,\infty)^E. By Proposition 3.3 applied to A=LΓ(w)A=L_\Gamma(w), the weight vector ww is separating if and only if PΓ(w)=Pn(LΓ(w))≠0P_\Gamma(w)=P_n(L_\Gamma(w))\ne0.

We show that PΓP_\Gamma is not the zero polynomial. Choose a spanning tree TT of Γ\Gamma and, by Proposition 4.7, a weight vector wT∈STw_T\in S_T. Let w∘∈REw^\circ\in\mathbb{R}^E agree with wTw_T on the edges of TT and vanish on the other edges. By Lemma 3.4(ii) and Proposition 3.3,

PΓ(w∘)=PT(wT)≠0.P_\Gamma(w^\circ)=P_T(w_T)\ne0.

By Lemma 3.4(i), PΓP_\Gamma has integer coefficients and is homogeneous of degree dnd_n.

Finally, SΓ=(0,∞)E∖Z(PΓ)S_\Gamma=(0,\infty)^E\setminus Z(P_\Gamma). By Lemma 2.2 it is open and dense in (0,∞)E(0,\infty)^E, and its complement there is relatively closed and null. It is a cone because PΓP_\Gamma is homogeneous. □

When Γ\Gamma is not a tree, the witness w∘w^\circ lies on the boundary of the positive orthant, and no perturbation is needed to move it inside: a polynomial that is nonzero at one point is nonzero, and a nonzero polynomial cannot vanish on the open set (0,∞)E(0,\infty)^E.

Proof of Corollary 1.3. (i) is the density of SΓS_\Gamma in (0,∞)E(0,\infty)^E. For (ii), the set in question is ((0,∞)E∖SΓ)−w((0,\infty)^E\setminus S_\Gamma)-w, a translate of a null set.

It remains to match these statements with the definitions of [4]. There, a property of matrices in a class M⊂Zn\mathcal{M}\subset\mathcal{Z}_n is called structurally generic when two conditions hold [4 Definitions 2.1 and 2.2]. First, every M∈MM\in\mathcal{M} can be brought into the subset of M\mathcal{M} having the property by an arbitrarily small perturbation that changes only the nonzero off-diagonal entries of MM, symmetrically, and adjusts the diagonal so that row sums remain zero. Second, the perturbations of this kind that give a matrix MM without the property form a set of Lebesgue measure zero in the space Rn(n−1)/2\mathbb{R}^{n(n-1)/2} of all tuples indexed by pairs i<ji<j, the coordinates of pairs outside the support of MM being irrelevant.

Let M\mathcal{M} be the class of Laplacian matrices of connected undirected graphs with positive weights and M=LΓ(w)∈MM=L_\Gamma(w)\in\mathcal{M}. The perturbations described above produce the matrices LΓ(w+t)L_\Gamma(w+t), t∈REt\in\mathbb{R}^E. The first condition is (i). For the second, LΓ(w+t)L_\Gamma(w+t) can belong to M\mathcal{M} only if w+tw+t has nonnegative entries. If some entry vanishes, tt lies in one of the finitely many hyperplanes {te=−we}\{t_e=-w_e\}; otherwise w+t∈(0,∞)Ew+t\in(0,\infty)^E, and failure of the property means w+t∉SΓw+t\notin S_\Gamma. By (ii) the exceptional tt form a null set N⊂REN\subset\mathbb{R}^E, and the corresponding set of tuples is the cylinder N×R(n2)−∣E∣N\times\mathbb{R}^{\binom{n}{2}-|E|}, which is null. The same argument applies if perturbations are parametrized by the new weights w+tw+t instead of the increments tt, since Lebesgue measure is invariant under translation. Both conditions thus hold for the conjunction of (S1)–(S3). They also hold for every property implied by it, because the weights at which such a property holds contain SΓS_\Gamma and those at which it fails lie in the complement of SΓS_\Gamma; this applies to “λ2\lambda_2 is simple and its eigenvector has pairwise distinct coordinates”.

Proof of Corollary 1.4. (i) PΓP_\Gamma is a nonzero polynomial with integer coefficients, so it cannot vanish at a point with algebraically independent coordinates. (ii) The complement of SΓS_\Gamma in (0,∞)E(0,\infty)^E is Lebesgue null. (iii) By the Schwartz–Zippel lemma [12, 13], a nonzero polynomial of total degree dd over a field vanishes at a point whose coordinates are independent and uniform on a finite set SS with probability at most d/∣S∣d/|S|. Apply this to PΓP_\Gamma over Q\mathbb{Q} with S={1,…,N}S=\{1,\ldots,N\}. For N=dn+1N=d_n+1 the probability of failure is less than one, so a separating point of {1,…,dn+1}E\{1,\ldots,d_n+1\}^E exists.

Examples, symmetry and sharpness

Small graphs

The degrees (2) are d2=2d_2=2, d3=12d_3=12, d4=42d_4=42, d5=110d_5=110 and d6=240d_6=240. The polynomial PΓP_\Gamma is far from minimal: it is a product of many factors, several of which never vanish on positive weights, and the examples below show much smaller exceptional sets.

Example 6.1 (One edge). For n=2n=2 and weight ww, κ1=−w\kappa_1=-w, κ2=w\kappa_2=w and δ12=1\delta_{12}=1, so PΓ(w)=−w2P_\Gamma(w)=-w^2. Every positive weight is separating.

Example 6.2 (The path on three vertices). Let Γ\Gamma be the path 1−2−31-2-3 with weights aa on {1,2}\{1,2\} and bb on {2,3}\{2,3\}. A direct computation gives

κ1=−a2b,κ2=ab(a−b),κ3=ab2,δ12=−b,δ13=b−a,δ23=a,\kappa_1=-a^2b,\qquad\kappa_2=ab(a-b),\qquad\kappa_3=ab^2,\qquad\delta_{12}=-b,\qquad\delta_{13}=b-a,\qquad\delta_{23}=a,

and therefore

PΓ(a,b)=−a5b5(a−b)2.P_\Gamma(a,b)=-a^5b^5(a-b)^2.

The positive weights that are not separating are exactly those with a=ba=b. For a=ba=b the nonconstant eigenvectors are (1,0,−1)T(1,0,-1)^T and (1,−2,1)T(1,-2,1)^T: the first has a zero coordinate and the second has two equal coordinates. For a≠ba\ne b the eigenvalues are a+b±a2−ab+b2a+b\pm\sqrt{a^2-ab+b^2} and both nonconstant eigenvectors have nonzero, pairwise distinct coordinates.

Example 6.3 (The triangle). Let Γ=K3\Gamma=K_3 with weights a=w23a=w_{23}, b=w13b=w_{13} and c=w12c=w_{12}, so that each weight is named after the opposite vertex. Then κ3=(a−b)(ab+bc+ca)\kappa_3=(a-b)(ab+bc+ca), δ12=b−a\delta_{12}=b-a, and the other factors are obtained by permuting the vertices, up to sign. Altogether

PΓ(a,b,c)=−(ab+bc+ca)3((a−b)(b−c)(c−a))2.P_\Gamma(a,b,c)=-(ab+bc+ca)^3\bigl((a-b)(b-c)(c-a)\bigr)^2.

The positive weights that are not separating are exactly the isosceles ones, with two equal weights. Indeed, a vector orthogonal to 1\mathbf{1} with x1=x2x_1=x_2 is a multiple of (1,1,−2)T(1,1,-2)^T, and L(1,1,−2)T=(3b,3a,−3(a+b))TL(1,1,-2)^T=(3b,3a,-3(a+b))^T is a multiple of it exactly when a=ba=b; similarly (1,−1,0)T(1,-1,0)^T is an eigenvector exactly when a=ba=b. Setting c=0c=0 gives −a5b5(a−b)2-a^5b^5(a-b)^2, the polynomial of the path 1−3−21-3-2, in accordance with Lemma 3.4(ii) and Example 6.2.

Symmetric weightings are exceptional

An automorphism of the weighted graph (Γ,w)(\Gamma,w) is a permutation σ\sigma of VV that maps edges to edges and preserves their weights; equivalently, its permutation matrix commutes with LΓ(w)L_\Gamma(w).

Proposition 6.4. Let Γ\Gamma be a connected graph on n≥3n \ge3 vertices and w∈SΓw \in S_{\Gamma}. Then the weighted graph (Γ,w)(\Gamma,w) has no automorphism other than the identity. In particular, if Γ\Gamma has a nontrivial automorphism, the constant weights are not separating.

Proof. Let Π\Pi be the permutation matrix of an automorphism σ\sigma, so that ΠL=LΠ\Pi L = L\Pi for L=LΓ(w)L=L_{\Gamma}(w). If xx is a unit eigenvector, then Πx\Pi x is a unit eigenvector for the same simple eigenvalue, so Πx=±x\Pi x=\pm x. Suppose Πx=x\Pi x=x for some eigenvector x⊥1x\perp\mathbf{1}. Then xx is constant on the cycles of σ\sigma, and (S3) forces σ\sigma to be the identity. Otherwise Πx=−x\Pi x=-x for every eigenvector orthogonal to 1\mathbf{1}, and Π1=1\Pi\mathbf{1}=\mathbf{1}, so Π=2n11T−I\Pi=\frac{2}{n}\mathbf{1}\mathbf{1}^{T}-I. The off-diagonal entries of this matrix equal 2/n2/n, which is neither 00 nor 11 when n≥3n\ge3, so it is not a permutation matrix. □\square

For n=2n=2 the transposition is an automorphism and every weight is separating, so the hypothesis n≥3n\ge3 is needed. Every graph on at most five vertices has a nontrivial automorphism; accordingly PΓP_{\Gamma} vanishes at the constant weights for all connected graphs with 3≤n≤53\le n\le5. This is the phenomenon behind the repeated or vanishing Fiedler entries of small unweighted graphs.

Exceptional weightings without symmetry

In Examples 6.2 and 6.3 the exceptional weightings are exactly the symmetric ones. This is not the general situation. The next two examples exhibit Fiedler vectors with a zero coordinate, and with two equal coordinates, on weighted graphs whose only automorphism is the identity.

Example 6.5 (A path with a vanishing Fiedler coordinate). Let Γ\Gamma be the path 1−2−3−41-2-3-4 with weights (w12,w23,w34)=(1,3,2)(w_{12},w_{23},w_{34})=(1,3,2). Then

L=(1−100−14−300−35−200−22),L(−3012)=(−3012),L=\begin{pmatrix}1&-1&0&0\\-1&4&-3&0\\0&-3&5&-2\\0&0&-2&2\end{pmatrix},\qquad L\begin{pmatrix}-3\\0\\1\\2\end{pmatrix}=\begin{pmatrix}-3\\0\\1\\2\end{pmatrix},

and the characteristic polynomial is z(z−1)(z−3)(z−8)z(z-1)(z-3)(z-8). Thus λ2=1\lambda_2=1 is simple and the Fiedler vector (−3,0,1,2)T(-3,0,1,2)^T vanishes at vertex 2. The weights are not palindromic, so the reflection of the path is not an automorphism.

Example 6.6 (A cycle with two equal Fiedler coordinates). Let Γ\Gamma be the cycle 1−2−3−4−11-2-3-4-1 with weights (w12,w23,w34,w41)=(8,15,35,12)(w_{12},w_{23},w_{34},w_{41})=(8,15,35,12). Then

L=(20−80−12−823−1500−1550−35−120−3547),L(−4121)=25(−4121),L=\begin{pmatrix}20&-8&0&-12\\-8&23&-15&0\\0&-15&50&-35\\-12&0&-35&47\end{pmatrix},\qquad L\begin{pmatrix}-4\\1\\2\\1\end{pmatrix}=25\begin{pmatrix}-4\\1\\2\\1\end{pmatrix},

and the characteristic polynomial is z(z−25)(z2−115z+2448)z(z-25)(z^2-115z+2448). The quadratic factor is positive at z=25z=25 and has its minimum at z=115/2>25z=115/2>25, so both of its roots exceed 25. Hence λ2=25\lambda_2=25 is simple, and the Fiedler vector (−4,1,2,1)T(-4,1,2,1)^T takes the same value at the vertices 2 and 4. The four weights are distinct, and no nonidentity automorphism of the 4-cycle fixes all four edges, so the weighted graph has trivial automorphism group.

Paths

On a path the conclusion of the conjecture holds for every positive weighting.

Proposition 6.7 (Paths). Let Γ\Gamma be the path 1−2−⋯−n1-2-\cdots-n, n≥2n\ge2, with positive weights wi=wi,i+1w_i=w_{i,i+1}. Every eigenvalue of LΓ(w)L_{\Gamma}(w) is simple, and every Fiedler vector is strictly monotone along the path; in particular its coordinates are pairwise distinct.

Proof. Write L=LΓ(w)L=L_{\Gamma}(w). If Lx=λxLx=\lambda x, the first row gives w1(x1−x2)=λx1w_1(x_1-x_2)=\lambda x_1, and row kk, for 1<k<n1<k<n, gives wk(xk−xk+1)=λxk−wk−1(xk−xk−1)w_k(x_k-x_{k+1})=\lambda x_k-w_{k-1}(x_k-x_{k-1}). Since every wkw_k is positive, x1x_1 determines x2,…,xnx_2,\ldots,x_n recursively. Hence every eigenspace has dimension one, so every eigenvalue is simple, and every eigenvector has x1≠0x_1\ne0.

::: Let xx be a Fiedler vector and put di=xi+1−xid_i=x_{i+1}-x_i and Si=x1+⋯+xiS_i=x_1+\cdots+x_i for 1≤i<n1\le i<n. For every z⊥1z\perp\mathbf{1},

∥z∥2=1n∑1≤i<j≤n(zj−zi)2\lVert z\rVert^2=\frac{1}{n}\sum_{1\le i<j\le n}(z_j-z_i)^2

since the right side equals ∥z∥2−1n(1Tz)2\lVert z\rVert^2-\frac{1}{n}(\mathbf{1}^{T}z)^2. Let y⊥1y\perp\mathbf{1} be the vector with yi+1−yi=∣di∣y_{i+1}-y_i=|d_i|. By Lemma 2.1, yTLy=∑iwidi2=xTLx=λ2∥x∥2y^T Ly=\sum_i w_i d_i^2=x^T Lx=\lambda_2\lVert x\rVert^2, while

∥y∥2=1n∑i<j(∑k=ij−1∣dk∣)2≥1n∑i<j(∑k=ij−1dk)2=∥x∥2.\lVert y\rVert^2=\frac{1}{n}\sum_{i<j}\left(\sum_{k=i}^{j-1}|d_k|\right)^2\ge\frac{1}{n}\sum_{i<j}\left(\sum_{k=i}^{j-1}d_k\right)^2=\lVert x\rVert^2.

On 1⊥\mathbf{1}^{\perp} the Rayleigh quotient of LL is at least λ2\lambda_2 by the Courant–Fischer theorem [11 Section 4.2], and y≠0y\ne0 because xx is not constant. Hence λ2∥y∥2≤yTLy=λ2∥x∥2\lambda_2\lVert y\rVert^2\le y^T Ly=\lambda_2\lVert x\rVert^2, and equality holds throughout. The term (i,j)=(1,n)(i,j)=(1,n) then gives ∣∑kdk∣=∑k∣dk∣|\sum_k d_k|=\sum_k|d_k|, so the nonzero dkd_k share one sign; replacing xx by −x-x, we may assume that xx is nondecreasing.

Suppose that di=0d_i=0 for some i<ni<n. Lemma 4.1, applied to D={i+1,…,n}D=\{i+1,\ldots,n\} and the edge {i,i+1}\{i,i+1\}, gives widi=λ2(xi+1+⋯+xn)=−λ2Siw_i d_i=\lambda_2(x_{i+1}+\cdots+x_n)=-\lambda_2S_i, because x⊥1x\perp\mathbf{1}; hence Si=0S_i=0. Monotonicity gives 0=Si≤ixi0=S_i\le ix_i and 0=xi+1+⋯+xn≥(n−i)xi+1=(n−i)xi0=x_{i+1}+\cdots+x_n\ge(n-i)x_{i+1}=(n-i)x_i, so xi=0x_i=0. Then x1≤⋯≤xi=0x_1\le\cdots\le x_i=0 and Si=0S_i=0 force x1=0x_1=0, which contradicts the first paragraph. Therefore every did_i is nonzero, and xx is strictly increasing. □

The Fiedler vector of a path can nevertheless vanish at a vertex, and the other eigenvectors can repeat a coordinate, as Examples 6.2 and 6.5 show; so (S2) and (S3) may fail on paths.

Scope of the hypotheses

Remark 6.8 (Connectedness). If Γ\Gamma is disconnected, PΓ=0P_\Gamma=0 by Lemma 3.4(iii), and no weight vector, positive or not, satisfies (S1). Connectedness is thus necessary and sufficient for PΓ≠0P_\Gamma\ne0.

Remark 6.9 (Real weights). Proposition 3.3 does not use positivity. Hence, for a connected graph, the matrix LΓ(w)L_\Gamma(w) satisfies (S1)–(S3) for every real weight vector ww outside the proper algebraic set Z(PΓ)⊂REZ(P_\Gamma)\subset\mathbb{R}^{E}, for instance for generic signed weights. Positivity is used only to identify λ2\lambda_2 as the smallest nonzero eigenvalue.

Remarks and questions

Remark 7.1 (Why a first-order expansion is unavoidable). In the induction of § 4 the matrix L0=L⊕0L_0=L\oplus0 is not separating, and PT′(w,0)=0P_{T}'(w,0)=0. The nonvanishing of PT′(w,ε)P_{T}'(w,\varepsilon) for small ε>0\varepsilon>0 is therefore a statement about the lowest-order term of this polynomial in ε\varepsilon. Lemma 4.4 computes that term for the factors δij\delta_{ij} with i,j∈Vi,j\in V: by (11), each of them vanishes to order exactly one in μ\mu when hi≠hjh_i\ne h_j.

Remark 7.2 (Spectral orderings). For separating weights, sorting the vertices by the Fiedler vector gives a strict total order, unique up to reversal, and the sign of the Fiedler vector splits VV into two nonempty sets without ties. By Fiedler’s theorem [2] each of the two sets induces a connected subgraph. Theorem 1.2 says that, for a fixed graph, ties in these constructions occur only on a null algebraic set of weights.

Question 7.3 (The exceptional hypersurface). Let Γ\Gamma be connected. What is the smallest degree of a polynomial whose zero set in (0,∞)E(0,\infty)^E is the complement of SΓS_\Gamma? For the path on three vertices the answer is 1, while d3=12d_3=12. Which irreducible components does the exceptional set have, and which of them correspond to a zero coordinate, to two equal coordinates, or to a multiple eigenvalue?

Question 7.4 (Quantitative separation). For random weights with a bounded density, how small can min⁡i≠j∣ϕ(i)−ϕ(j)∣\min_{i\ne j}|\phi(i)-\phi(j)| be for the unit Fiedler vector ϕ\phi? A polynomial lower bound in nn with high probability would make the spectral order numerically stable.

Question 7.5 (Other operators). Do the analogues of Theorem 1.2 hold for normalized Laplacians, for adjacency matrices with a fixed support, and for directed graphs with a spanning diverging tree, the setting in which simple spectrum is generic by [4 Theorem 6.6]? The Krylov certificate of § 3 adapts to any family of symmetric matrices; the construction of a witness is the part that depends on the operator.

Universidad Nacional de Colombia

Email address: [email protected]

Universidad EAFIT

Email address: [email protected]

Universidad Nacional de Colombia

Email address: [email protected]

Universidad de Antioquia

Email address: [email protected]

References

  1. [1]M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal 23 (1973), 298–305.DOI
  2. [2]M. Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal 25 (1975), 619–633.
  3. [3]J. E. Atkins, E. G. Boman, and B. Hendrickson. A spectral algorithm for seriation and the consecutive ones problem. SIAM Journal on Computing 28 (1998), 297–310.
  4. [4]C. Poignard, T. Pereira, and J. P. Pade. Spectra of Laplacian matrices of weighted graphs: structural genericity properties. SIAM Journal on Applied Mathematics 78(1) (2018), 372–394. https://doi.org/10.1137/17M1124474. arXiv:1704.01677.
  5. [5]R. E. Kalman. On the general theory of control systems. Proceedings of the First IFAC Congress (1960).
  6. [6]K. Uhlenbeck. Generic properties of eigenfunctions. American Journal of Mathematics 98 (1976), 1059–1078.DOI
  7. [7]C. Godsil. Controllable subsets in graphs. Annals of Combinatorics 16 (2012), 733–744.
  8. [8]S. O’Rourke and B. Touri. On a conjecture of Godsil concerning controllable random graphs. SIAM Journal on Control and Optimization 54 (2016), 3347–3378.arxiv.org/abs/1511.05080
  9. [9]T. Tao and V. Vu. Random matrices have simple spectrum. Combinatorica 37 (2017), 539–553.arxiv.org/abs/1412.1438
  10. [10]T. Bıyıkoğlu, J. Leydold, and P. F. Stadler. Laplacian Eigenvectors of Graphs: Perron–Frobenius and Faber–Krahn Type Theorems. Lecture Notes in Mathematics 1915, Springer, 2007.DOI
  11. [11]R. A. Horn and C. R. Johnson. Matrix Analysis. Second edition, Cambridge University Press, 2013.
  12. [12]J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM 27 (1980), 701–717.DOI
  13. [13]R. Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation (EUROSAM ’79), Lecture Notes in Computer Science 72, Springer, 1979, pp. 216–226.DOI

Paper details

vlnc:W_p8v6h5vc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents