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 be a finite simple graph with vertex set , and let be positive edge weights. The weighted Laplacian is
that is, with the weighted adjacency matrix and the diagonal matrix of weighted degrees. It is symmetric and positive semidefinite, and it annihilates the constant vector . When is connected its eigenvalues can be written
The number is the algebraic connectivity of the weighted graph [1], and an eigenvector of 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 be a connected graph on vertices. A weight vector is separating if
(S1) the eigenvalues of are pairwise distinct;
(S2) no eigenvector of has a zero coordinate;
(S3) every eigenvector of orthogonal to has pairwise distinct coordinates.
We write for the set of separating weights.
Under (S1) the eigenvectors orthogonal to are exactly the eigenvectors of , 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 be a connected graph on vertices. There is a nonzero homogeneous polynomial of degree
such that, for every ,
Consequently is an open dense cone in , and its complement in is a relatively closed set of Lebesgue measure zero, contained in the real algebraic set .
The polynomial is explicit: , where 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 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 be a connected graph on vertices.
(i) For every and every there is with .
(ii) For every , the set of perturbations for which lies in and is not separating has Lebesgue measure zero.
Hence the property “ 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 be a connected graph on vertices and the degree (2).
(i) If the positive numbers are algebraically independent over , then is separating.
(ii) If is a random vector whose law is absolutely continuous with respect to Lebesgue measure on , then is separating almost surely.
(iii) If the weights are independent and uniformly distributed on , then fails to be separating with probability at most . In particular there are separating integer weights with for every edge.
The examples of § 6 show what the exceptional set looks like. Symmetric weightings are always exceptional when (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 with , the Krylov matrix of the coordinate vector has nonzero determinant exactly when has simple spectrum and no eigenvector vanishes at ; the nonvanishing of this determinant is Kalman’s rank condition for controllability [5]. In the same way, the Krylov matrix of the difference inside the invariant hyperplane has full rank exactly when the spectrum on is simple and no eigenvector there takes equal values at and . Since the columns of this matrix lie in , one maximal minor already detects its rank. Multiplying the determinants for all vertices and these minors for all pairs gives a polynomial in the entries of whose nonvanishing is equivalent to (S1)–(S3) (Proposition 3.3).
A witness. The certificate reduces genericity to a single separating weighting, which shows that 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 with a small weight to a tree that already has separating weights. The eigenvectors that continue those of keep their separated coordinates and acquire a small nonzero coordinate at . The difficulty is the new eigenvector, whose eigenvalue tends to zero: in the limit it equals on all of and at , so its coordinates on coincide to order zero. A summation identity over the two sides of an edge (Lemma 4.1) gives the expansion
where is the vertex of attachment, is the path from to and is the set of vertices cut off from by the edge . The error is quadratic in , with an explicit constant (Lemma 4.4(iii)), and this precision is what allows the first-order term to separate the coordinates. The numbers are pairwise distinct for all weights outside a nowhere dense set, and then the coordinates are separated for small (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 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 are columns indexed by ; is the standard basis, , and or denotes the coordinate of at . The Euclidean norm and the induced operator norm are both written . We write
for the space of symmetric matrices with zero row sums. For the hyperplane is invariant, since . Conditions (S1)–(S3) make sense for every in place of , and we call separating when they hold.
A graph is finite, simple and undirected. For a graph and an arbitrary real vector , formula (1) defines ; the map is linear. If and vanishes outside , then
Lemma 2.1. Let be a graph and . Then
so is positive semidefinite, and its kernel consists of the vectors that are constant on each connected component of . If is connected, the kernel is spanned by , every nonzero eigenvalue is positive, and its eigenvectors are orthogonal to .
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 for every edge. Eigenvectors of a symmetric matrix for different eigenvalues are orthogonal. □
Zero sets of polynomials
Lemma 2.2. Let be a nonzero polynomial and . Then is closed, has Lebesgue measure zero, and has empty interior. Consequently, for every nonempty open set , the set is open, dense in , and of full measure in .
Proof. is closed because is continuous. We prove by induction on that it is a null set. For it is finite. Let and write with and . By induction the set is null in . For the polynomial is nonzero, so the slice is finite. By Tonelli’s theorem, applied to the indicator function of the closed set , the measure of is the integral over of the one-dimensional measures of its slices, which vanish outside the null set . A null set has empty interior, and the remaining assertions follow. □
Two perturbation facts
For a real symmetric matrix of order let be its eigenvalues. Weyl’s inequality [11 Section 4.3] states that
for real symmetric and .
Lemma 2.3 (Stability of a simple eigenpair). Let be real symmetric with a simple eigenvalue , unit eigenvector , and gap . Let be real symmetric with . Then has exactly one eigenvalue , counted with multiplicity, in the interval ; it satisfies , and it has a unit eigenvector with
Proof. Let . By (4), satisfies , while for we have . This proves the first two assertions. Let be a unit eigenvector of for and write with . Then
whose norm is at most . On the symmetric operator has all its eigenvalues of absolute value at least , so and . Replacing by if necessary we may assume , so and
because for . Take . □
A polynomial certificate
Krylov matrices
For a square matrix , a vector and an integer , the Krylov matrix is the matrix with columns .
Lemma 3.1 (Krylov determinants). Let be a real symmetric matrix and an -invariant subspace of dimension . Let be an orthonormal basis of consisting of eigenvectors of , with . For put . Then
If , so that and is square, then
Proof. Since , we have for . Hence
The matrix is a Vandermonde matrix, with . Since , we get , which gives (5). If , then is orthogonal, , and . □
In words: if and only if the restriction of to has distinct eigenvalues and is orthogonal to none of its eigenvectors. Such a vector is called cyclic for .
Lemma 3.2 (Reduced Gram determinants). Let be a matrix whose columns lie in , and let be the square matrix obtained by deleting its last row. Then
Proof. For let be the matrix obtained from by deleting row , so that . By the Cauchy–Binet formula,
Let be the rows of . Since every column lies in , . Let . Adding to the row of all its other rows does not change the determinant and replaces by . The resulting matrix differs from only by the sign of one row and the position of that row. Hence for every , and the sum equals .
The polynomial
Let . For , a vertex and a pair define
where is obtained from by deleting its last row, and
The columns of lie in , because and is -invariant; by Lemma 3.2, . For the matrix is the matrix and .
Proposition 3.3 (Certificate). Let and . Let be an orthonormal basis of eigenvectors of , with eigenvalues . Then
Consequently if and only if is separating, that is, if and only if (S1), (S2) and (S3) hold for .
Proof. Such a basis exists because is an eigenvector for the eigenvalue and is invariant. Formula (10) is (6) with , since and . Formula (11) follows from (5), applied with , , the basis , and , since , together with .
Suppose . Then , so by (10) the numbers are pairwise distinct, which is (S1). Every eigenvector is then a multiple of some . The eigenvector has no zero coordinate, and for and every because ; this is (S2). The eigenvectors orthogonal to are the multiples of , and for because ; 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 be a graph on vertices.
is a polynomial in the variables with integer coefficients. It is either zero or homogeneous of degree .
If with , and vanishes outside , then .
If is disconnected, then .
Proof. (i) The entries of are linear forms in with integer coefficients, so the entries of are integer polynomials, each zero or homogeneous of degree . In the expansion of the determinant (7) every term takes one entry from each of the columns , ; hence is zero or homogeneous of degree . In the same way, the column of formed by the first entries of has degree for , so is zero or homogeneous of degree . Adding the degrees of the factors and the factors gives
(ii) follows from (3), because depends on only through the matrix . (iii) If is disconnected, then for every the matrix annihilates the indicator vector of each connected component, so is a multiple eigenvalue and (S1) fails; by Proposition 3.3, for all .
Remark 3.5. The factors alone certify (S1) and (S2), which are the properties shown to be structurally generic in [4]. The factors are responsible for (S3): by Lemma 3.2, vanishes exactly when fails to be cyclic for the restriction of to . The Gram determinants have the same zero sets, but using them would double the contribution of these factors to the degree. The degree 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 be a graph with real edge weights and Laplacian , and let be a set of vertices such that exactly one edge , with and , joins to its complement. If , then
Proof. By (1), , the sum running over the neighbours of . Sum this over . An edge with both ends in contributes , and the only other edge meeting is , which contributes . The left side of therefore sums to and the right side to .
Attaching a leaf
Fix the following data for this subsection (Figure 1).
Figure 1. Attaching a leaf at the vertex of a tree with a small weight . The edge separates the shaded vertex set from . The eigenvector of the new small eigenvalue is constant on in the limit; the cut identity gives its first-order profile , which separates the coordinates when the numbers are pairwise distinct.
is a tree with vertex set , , and is a separating weight vector. Let , with eigenvalues and unit eigenvectors .
is a vertex, and is the tree obtained from by adding a new vertex and the edge . For we give this edge the weight and write . Ordering the vertices of as ,
For an edge of , the graph has two connected components; denotes the vertex set of the component that does not contain . For , denotes the set of edges of the path from to in , and
We use the positive constants
which are positive because is separating, and
Lemma 4.2 (Spectrum of ). Let . Then has distinct eigenvalues: the eigenvalue ; one eigenvalue ; and, for each , exactly one eigenvalue with .
Proof. By (12), has norm , and the eigenvalues of in nondecreasing order are . Let be the eigenvalues of . By (4), and for . Since is connected and its weights are positive, Lemma 2.1 gives ; put and . Because and consecutive differ by at least , the intervals and , , are pairwise disjoint. Hence the eigenvalues are distinct. □
Lemma 4.3 (Eigenvectors continuing those of ). Let and . Every eigenvector of for has nonzero, pairwise distinct coordinates.
Proof. In the spectrum of the eigenvalue is simple, with unit eigenvector and gap at least . Apply Lemma 2.3 with , and : the eigenvalue of in is , and it has a unit eigenvector with
Every coordinate of on is therefore within of the corresponding coordinate of . By the definition of ,
The row of in reads , that is,
Thus , because , and for every , so differs from all other coordinates. Since is simple, every eigenvector is a multiple of . □
Lemma 4.4 (The new eigenvector). Let , let , and let be an eigenvector of for .
(i) . Normalizing so that , we have .
(ii) With this normalization, for every ; in particular .
(iii) With this normalization, for all ,
Proof. (i) Since , Lemma 2.1 applied to gives , that is, . Suppose . Then , and the row of , , gives . By (12), the rows of then read for , and because . So would be an eigenvalue of in , whereas has no eigenvalue in . This contradiction proves , and the normalization gives .
(ii) Let be an edge of with . The vertex does not belong to , so no vertex of is adjacent to , and is the only edge of joining to its complement. Lemma 4.1 gives
Let . Since , the right side of (14) is at most in absolute value. Two vertices of are joined in by a path with at most edges, so for all . The mean of the over equals ; hence and . As , we get and .
(iii) Let be the path from to and . The end of in is , so summing (14) over gives
By (ii), . Comparing with (13),
and the claim follows by subtracting the same estimate for .
Proposition 4.5 (Leaf attachment). In the setting above, suppose that the numbers , , are pairwise distinct, and let . Then for every
Proof. By Lemma 4.2 the spectrum of is simple, which is (S1), and every eigenvector is a multiple of , of an eigenvector of some , or of an eigenvector of . 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 on and , so no coordinate vanishes and differs from every . For in , part (iii) of that lemma and give
Hence (S2) and (S3) hold.
Every tree has separating weights
Lemma 4.6 (The profile is generically injective). Let be a tree on , , let , and let be vertices. The set of with is closed in and has empty interior.
Proof. The paths from to and from to share an initial segment and then separate; the symmetric difference of and is the edge set of the path from to , which is nonempty. By (13),
with at least one term and all . Multiplying by gives a polynomial in which the monomials , for the edges of the path from to , are distinct and have the nonzero coefficients . Thus , and on the equation is equivalent to . Lemma 2.2 applies. □
Proposition 4.7 (Trees). For every tree on vertices, .
Proof. By induction on . For the Laplacian is , with eigenvalues and and eigenvectors and , so every is separating.
Let be a tree on vertices. It has a leaf ; let be its neighbour and , a tree on vertices. By the induction hypothesis , and by Proposition 3.3, is open. By Lemma 4.6, the set of weights for which two of the numbers coincide is the zero set in of the nonzero polynomial , with 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 . Choose with pairwise distinct . By Proposition 4.5, for all sufficiently small . □
Proofs of the main results
Proof of Theorem 1.2. Let . By Proposition 3.3 applied to , the weight vector is separating if and only if .
We show that is not the zero polynomial. Choose a spanning tree of and, by Proposition 4.7, a weight vector . Let agree with on the edges of and vanish on the other edges. By Lemma 3.4(ii) and Proposition 3.3,
By Lemma 3.4(i), has integer coefficients and is homogeneous of degree .
Finally, . By Lemma 2.2 it is open and dense in , and its complement there is relatively closed and null. It is a cone because is homogeneous. □
When is not a tree, the witness 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 .
Proof of Corollary 1.3. (i) is the density of in . For (ii), the set in question is , 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 is called structurally generic when two conditions hold [4 Definitions 2.1 and 2.2]. First, every can be brought into the subset of having the property by an arbitrarily small perturbation that changes only the nonzero off-diagonal entries of , symmetrically, and adjusts the diagonal so that row sums remain zero. Second, the perturbations of this kind that give a matrix without the property form a set of Lebesgue measure zero in the space of all tuples indexed by pairs , the coordinates of pairs outside the support of being irrelevant.
Let be the class of Laplacian matrices of connected undirected graphs with positive weights and . The perturbations described above produce the matrices , . The first condition is (i). For the second, can belong to only if has nonnegative entries. If some entry vanishes, lies in one of the finitely many hyperplanes ; otherwise , and failure of the property means . By (ii) the exceptional form a null set , and the corresponding set of tuples is the cylinder , which is null. The same argument applies if perturbations are parametrized by the new weights instead of the increments , 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 and those at which it fails lie in the complement of ; this applies to “ is simple and its eigenvector has pairwise distinct coordinates”.
Proof of Corollary 1.4. (i) is a nonzero polynomial with integer coefficients, so it cannot vanish at a point with algebraically independent coordinates. (ii) The complement of in is Lebesgue null. (iii) By the Schwartz–Zippel lemma [12, 13], a nonzero polynomial of total degree over a field vanishes at a point whose coordinates are independent and uniform on a finite set with probability at most . Apply this to over with . For the probability of failure is less than one, so a separating point of exists.
Examples, symmetry and sharpness
Small graphs
The degrees (2) are , , , and . The polynomial 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 and weight , , and , so . Every positive weight is separating.
Example 6.2 (The path on three vertices). Let be the path with weights on and on . A direct computation gives
and therefore
The positive weights that are not separating are exactly those with . For the nonconstant eigenvectors are and : the first has a zero coordinate and the second has two equal coordinates. For the eigenvalues are and both nonconstant eigenvectors have nonzero, pairwise distinct coordinates.
Example 6.3 (The triangle). Let with weights , and , so that each weight is named after the opposite vertex. Then , , and the other factors are obtained by permuting the vertices, up to sign. Altogether
The positive weights that are not separating are exactly the isosceles ones, with two equal weights. Indeed, a vector orthogonal to with is a multiple of , and is a multiple of it exactly when ; similarly is an eigenvector exactly when . Setting gives , the polynomial of the path , in accordance with Lemma 3.4(ii) and Example 6.2.
Symmetric weightings are exceptional
An automorphism of the weighted graph is a permutation of that maps edges to edges and preserves their weights; equivalently, its permutation matrix commutes with .
Proposition 6.4. Let be a connected graph on vertices and . Then the weighted graph has no automorphism other than the identity. In particular, if has a nontrivial automorphism, the constant weights are not separating.
Proof. Let be the permutation matrix of an automorphism , so that for . If is a unit eigenvector, then is a unit eigenvector for the same simple eigenvalue, so . Suppose for some eigenvector . Then is constant on the cycles of , and (S3) forces to be the identity. Otherwise for every eigenvector orthogonal to , and , so . The off-diagonal entries of this matrix equal , which is neither nor when , so it is not a permutation matrix.
For the transposition is an automorphism and every weight is separating, so the hypothesis is needed. Every graph on at most five vertices has a nontrivial automorphism; accordingly vanishes at the constant weights for all connected graphs with . 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 be the path with weights . Then
and the characteristic polynomial is . Thus is simple and the Fiedler vector 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 be the cycle with weights . Then
and the characteristic polynomial is . The quadratic factor is positive at and has its minimum at , so both of its roots exceed 25. Hence is simple, and the Fiedler vector 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 be the path , , with positive weights . Every eigenvalue of is simple, and every Fiedler vector is strictly monotone along the path; in particular its coordinates are pairwise distinct.
Proof. Write . If , the first row gives , and row , for , gives . Since every is positive, determines recursively. Hence every eigenspace has dimension one, so every eigenvalue is simple, and every eigenvector has .
::: Let be a Fiedler vector and put and for . For every ,
since the right side equals . Let be the vector with . By Lemma 2.1, , while
On the Rayleigh quotient of is at least by the Courant–Fischer theorem [11 Section 4.2], and because is not constant. Hence , and equality holds throughout. The term then gives , so the nonzero share one sign; replacing by , we may assume that is nondecreasing.
Suppose that for some . Lemma 4.1, applied to and the edge , gives , because ; hence . Monotonicity gives and , so . Then and force , which contradicts the first paragraph. Therefore every is nonzero, and 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 is disconnected, by Lemma 3.4(iii), and no weight vector, positive or not, satisfies (S1). Connectedness is thus necessary and sufficient for .
Remark 6.9 (Real weights). Proposition 3.3 does not use positivity. Hence, for a connected graph, the matrix satisfies (S1)–(S3) for every real weight vector outside the proper algebraic set , for instance for generic signed weights. Positivity is used only to identify 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 is not separating, and . The nonvanishing of for small is therefore a statement about the lowest-order term of this polynomial in . Lemma 4.4 computes that term for the factors with : by (11), each of them vanishes to order exactly one in when .
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 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 be connected. What is the smallest degree of a polynomial whose zero set in is the complement of ? For the path on three vertices the answer is 1, while . 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 be for the unit Fiedler vector ? A polynomial lower bound in 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]M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal 23 (1973), 298–305.DOI
- [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]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]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]R. E. Kalman. On the general theory of control systems. Proceedings of the First IFAC Congress (1960).
- [6]K. Uhlenbeck. Generic properties of eigenfunctions. American Journal of Mathematics 98 (1976), 1059–1078.DOI
- [7]C. Godsil. Controllable subsets in graphs. Annals of Combinatorics 16 (2012), 733–744.
- [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]T. Tao and V. Vu. Random matrices have simple spectrum. Combinatorica 37 (2017), 539–553.arxiv.org/abs/1412.1438
- [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]R. A. Horn and C. R. Johnson. Matrix Analysis. Second edition, Cambridge University Press, 2013.
- [12]J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM 27 (1980), 701–717.DOI
- [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
