How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Constant vector is a top eigenvector
Statement
For a finite -regular adjacency-slot multigraph, , every eigenvalue of lies in , and is invariant. The multiplicity of eigenvalue equals the number of connected components. For a connected graph, is an eigenvalue if and only if its positive slots join opposite parts of a bipartition, so in particular it has no loop slots.
Facts & Assumptions
Given: the objects and hypotheses in the statement above.
A finite -regular adjacency-slot multigraph on , with and integer , is a symmetric matrix with every row sum . counts slots from to ; diagonal entries count loop slots. Its normalized adjacency is . We use unless an unnormalized inner product is explicitly specified. An adjacency list records the destinations per vertex, including repetitions. An ordinary undirected edge has two incidence slots paired by reversal; an ordinary loop has two slots at the same vertex. Such a representation requires even diagonal entries. Any symmetric integer matrix can be converted to it by doubling every slot. Uniform directed-slot sampling chooses one of the slots; for a reverse-paired graph it induces the uniform distribution on its ordinary edges. Connectivity uses positive off-diagonal entries. When , the mean-zero subspace is . (Regular multigraph and normalized adjacency).
Let be a finite-dimensional real inner product space and let be self-adjoint. Then has an orthonormal basis consisting of eigenvectors of . (Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis).
Proof
The row sums give ; symmetry gives . The real spectral theorem applies since is a symmetric endomorphism of a finite-dimensional real inner product space. If and is maximal and nonzero, then , proving the interval bound.
Expansion of the squares gives . Its zero vectors are exactly functions constant on each connected component. Thus the eigenspace for eigenvalue one has dimension the component count; the spectral theorem identifies this with multiplicity.
Similarly . For a nonzero eigenvector all positive slots force . Connectivity propagates one nonzero absolute value to every vertex, excludes loops, and partitions the vertices by sign. Conversely on such a bipartition the vector taking values has . At positive degree forces loops and , so no eigenvalue occurs and the mean-zero space is zero.
Depends on
Used by
- Spectral edge and vertex expansion Definition
Dependency tree · two levels
5 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §2.3 spectral properties, pp20–21. (standard reference, not scraped)