DefinitionDefinition: AI-generatedProof: AI-generated

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.

Normalized graph Laplacian and its nontrivial spectrum

Definition

Let $G$ be a simple graph on $V = {1, \dots, n}$ , $n \geq 2$ , with adjacency matrix $A$ , degrees $d_{i} = \sum_{j} A_{i j} > 0$ , and $D = diag (d_{1}, \dots, d_{n})$ . Define $L = D - A$ and the symmetric normalized Laplacian $L = D^{- 1 / 2} L D^{- 1 / 2} = I - D^{- 1 / 2} A D^{- 1 / 2}$ , where the diagonal matrix $D^{- 1 / 2}$ has entries $d_{i}^{- 1 / 2}$ . List its real eigenvalues with multiplicity as $0 = λ_{1} \leq \dots \leq λ_{n}$ . It is positive semidefinite, and its kernel consists of vectors $D^{1 / 2} f$ with $f$ constant on each connected component. In particular, connectedness is equivalent to $λ_{2} > 0$ . For a connected graph define its spectral deviation $η (G) = \max_{2 \leq i \leq n} ∣ 1 - λ_{i} ∣$ and its nonzero spectral condition number $κ (G) = λ_{n} / λ_{2}$ .

Facts & Assumptions

[F1]

A simple graph, its edges and connectedness are defined by the edge-process interface (Uniform edge orderings, graph-process times and independent labels).

[F2]

The unnormalized graph Laplacian has quadratic form $f^{*} L f = \frac{1}{2} \sum_{i, j} A_{i j} ∣ f_{i} - f_{j} ∣^{2}$ and kernel equal to the functions constant on each component (Support connectivity and the unnormalized Laplacian kernel).

[F3]

A Hermitian matrix is positive semidefinite when its quadratic form is nonnegative on every vector (Self-adjoint order, norm bounds and diagonal tests).

[F4]

In a chosen vertex order, the adjacency matrix of a finite simple graph has $A_{i j} = 1$ exactly when ${i, j}$ is an edge, and $A_{i j} = 0$ otherwise. It is real symmetric, entrywise nonnegative and zero on the diagonal (The adjacency matrix of a finite simple graph).

[F5]

A normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis (Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely).

[F6]

Vertices are in the same connected component exactly when a path joins them; a nonempty graph is connected exactly when it has one component. Connected graphs and connected components defined by the existence of vertex paths

[F7]

An eigenvector of an endomorphism $T$ is a nonzero vector $u$ with $T u = λ u$ ; $λ$ is its eigenvalue, and the corresponding eigenspace is $\ker (T - λ I)$ . Eigenvalues, eigenvectors, eigenspaces E_λ(T)=ker(T-λ I), and the spectrum σ_F(T) of an endomorphism

[F8]

A finite-dimensional inner-product-space endomorphism $T$ is self-adjoint when $T^{*} = T$ and normal when $T T^{*} = T^{*} T$ . Every self-adjoint endomorphism is normal, since $T T^{*} = T^{2} = T^{*} T$ . Self-adjoint and normal endomorphisms of a finite-dimensional real or complex inner product space

Justification

Given: The objects and hypotheses in the definition.

Goal: Establish all stated claims.

1.1 By [F4], $A$ is real symmetric and nonnegative, and its loop-free support graph is $G$ in [F1], so [F2] applies to $L = D - A$ . Positive degrees make $D^{1 / 2}$ and $D^{- 1 / 2}$ invertible real diagonal matrices. The displayed identity for $L$ follows by multiplication. For every $x \in C^{V}$ , $x^{*} L x = (D^{- 1 / 2} x)^{*} L (D^{- 1 / 2} x) \geq 0$ by [F2]. Also $L$ is real symmetric, hence Hermitian and therefore normal by [F8], so [F3] makes it positive semidefinite and [F5] gives an orthonormal eigenbasis. For every nonzero eigenvector $u$ with eigenvalue $λ$ as in [F7], $λ = (u^{*} L u) / (u^{*} u)$ is real and nonnegative. Thus its eigenvalues can be ordered as stated. [given, F1, F2, F3, F4, F5, F7, F8, algebra]

2.1 Multiplication by the invertible matrices shows $L x = 0$ exactly when $L (D^{- 1 / 2} x) = 0$ . Hence [F2] gives the stated kernel description. By [F6], the indicator functions of the connected components form a basis of $\ker L$ , and multiplication by $D^{1 / 2}$ is an isomorphism from $\ker L$ onto $\ker L$ . Thus the latter kernel has dimension equal to the number of components, which is at least one. In the eigenbasis of step 1.1, that dimension is the number of zero eigenvalues counted with multiplicity. Consequently $λ_{1} = 0$ , and zero is simple exactly when $G$ is connected by [F6]; since all eigenvalues are nonnegative and $n \geq 2$ , this is equivalent to $λ_{2} > 0$ . In that case the maximum and ratio defining $η (G)$ and $κ (G)$ are well-defined finite real numbers, with positive denominator. [given, step 1.1, F1, F2, F5, F6, F7, algebra] ∎

Depends on

Used by · 3

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.