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.
Absolute gap equals one minus the largest nonconstant eigenvalue modulus
Statement
Let be a finite reversible chain and let . If , then . Otherwise,
and . If there is a fixed function , then its nonzero mean-zero component is fixed by , so the gap is .
Facts & Assumptions
Given: A finite reversible chain with its weighted inner product and mean-zero subspace .
Absolute spectral gap of a finite reversible chain: , with norm when .
A finite reversible transition operator is self-adjoint on weighted L2: is invariant and is a finite-dimensional self-adjoint endomorphism.
Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely: a finite-dimensional complex normal endomorphism has an orthonormal eigenbasis.
Eigenvalues, eigenvectors, eigenspaces , and the spectrum of an endomorphism: an eigenvalue is a scalar with a nonzero eigenvector, and the spectrum is the set of eigenvalues.
Real and complex inner product spaces, with the inner product linear in the first argument: scalar multiplication is linear in the first argument and conjugate-linear in the second.
Proof
If , the restriction has zero domain, so its operator norm is by [F1] and the gap is . Otherwise, [F2] and [F4] give an orthonormal eigenbasis of . Each eigenvalue is real: if , self-adjointness and [F7] give . [F5] identifies these eigenvalues as the spectrum of the restriction.
Write . Orthonormality gives and , with equality at an eigenvector whose eigenvalue has largest modulus. Therefore .
By [F3] the restriction norm is at most , and it is nonnegative by definition; substituting step 1.2 into [F1] proves both the eigenvalue formula and .
If and , put and . The normalization gives , while because is not constant. Since , . Thus is an eigenvalue of and step 1.2 gives , so [F1] gives .
Depends on
- Absolute spectral gap of a finite reversible chain
- A finite reversible transition operator is self-adjoint on weighted L2
- Finite stationary Markov operators contract in weighted L2
- Eigenvalues, eigenvectors, eigenspaces $E_\lambda(T)=\ker(T-\lambda I)$, and the spectrum $\sigma_F(T)$ of an endomorphism
- Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely
- Real and complex inner product spaces, with the inner product linear in the first argument
- Finite reversible Markov chain with positive stationary law
Used by
Dependency tree · two levels
24 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
- Andrew M. Childs, Lecture Notes on Quantum Algorithms, §18.4 (standard reference, not scraped)
- Ronald de Wolf, Quantum Computing: Lecture Notes, §8.1 (standard reference, not scraped)