PropositionStatement: 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.

Support connectivity and the unnormalized Laplacian kernel

Statement

Let $(V, A)$ be a network: $V$ is nonempty and finite, $n = ∣ V ∣$ , and $A$ is real, symmetric and entrywise nonnegative. Put $d (x) = \sum_{y} A_{x y}$ , $D = diag (d (x))$ and $L = D - A$ . The loop-free support graph has an edge ${x, y}$ exactly when $x \neq y$ and $A_{x y} > 0$ . For every $f \in C^{V}$ ,

$f^{*} L f = \frac{1}{2} \sum_{x, y \in V} A_{x y} ∣ f (x) - f (y) ∣^{2} .$

The kernel of $L$ consists exactly of functions constant on each connected component of the support graph. In particular, for $n \geq 2$ the support graph is connected if and only if zero is a simple eigenvalue of $L$ , meaning that it occurs once in an eigenvalue list counted with multiplicity. If some $η > 0$ satisfies $f^{*} L f \geq η ∥ f ∥_{2}^{2}$ for every $f \in 1^{⊥}$ , then the support graph is connected. Connectivity alone does not imply such a bound for an arbitrarily prescribed positive $η$ .

Here $1$ is the constant-one function and $1^{⊥} = {f : \sum_{x} f (x) = 0}$ , with the vertex inner product and norm.

Statement references

Finite symmetric networks and loop removal

Finite vertex Hilbert space in the article convention

Connected graphs and connected components defined by the existence of vertex paths

Eigenvalues, eigenvectors, eigenspaces E_λ(T)=ker(T-λ I), and the spectrum σ_F(T) of an endomorphism

Facts & Assumptions

[F1]

The network definition gives $W = A - diag (A_{x x})$ , a symmetric nonnegative zero-diagonal matrix with the same support graph, and $L = diag (\sum_{y} W_{x y}) - W$ . Finite symmetric networks and loop removal

[F2]

For a symmetric nonnegative zero-diagonal weight matrix on a nonempty finite vertex set, its weighted Laplacian has real quadratic form $u^{T} L u = \frac{1}{2} \sum_{x, y} W_{x y} (u (x) - u (y))^{2}$ ; its real kernel consists of functions constant on each support component. Quadratic form and kernel of a weighted graph Laplacian

[F3]

Components consist of vertices joined by paths, and a nonempty graph is connected exactly when all its vertices lie in one component. Connected graphs and connected components defined by the existence of vertex paths

[F4]

The vertex space has inner product $⟨ f, g ⟩ = \sum_{x} \overline{f (x)} g (x)$ , norm $∥ f ∥_{2}^{2} = ⟨ f, f ⟩$ , and matrix action by finite sums; real symmetric matrices are self-adjoint. Finite vertex Hilbert space in the article convention

[F5]

An endomorphism $T$ is normal when $T T^{*} = T^{*} T$ ; a 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 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]

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

Proof

Given: A network $(V, A)$ with the stated matrices and support graph.

Goal: Establish the quadratic identity, kernel characterization, connectivity equivalence and the stated limits on a numerical lower bound.

1.1givenF1F2F4algebra

Write $f = u + i v$ with real functions $u, v$ . By [F1], $L$ is real symmetric and is the weighted Laplacian of $W$ . Expanding with [F4], the imaginary cross terms cancel, so $f^{*} L f = u^{T} L u + v^{T} L v$ . Applying [F2] to $u$ and $v$ gives $f^{*} L f = \frac{1}{2} \sum_{x, y} W_{x y} (∣ u (x) - u (y) ∣^{2} + ∣ v (x) - v (y) ∣^{2})$ . The diagonal terms vanish and $W_{x y} = A_{x y}$ off the diagonal, proving the displayed identity.

2.1F2F3step 1.1algebra

Since $L$ is real, $L f = 0$ exactly when $L u = L v = 0$ . By [F2], this holds exactly when both $u$ and $v$ are constant on each component, equivalently when $f$ is. The component indicators form a basis of this kernel: they span all componentwise constant functions and are independent by evaluation at a vertex in each component. In particular $1 \in \ker L$ , and the kernel dimension equals the number of components.

3.1F3F4F5F6step 2.1algebra

By [F4], $L$ is self-adjoint; the normality identity in [F5] therefore holds, and its spectral theorem supplies an orthonormal eigenbasis. By [F6], in that basis its matrix is diagonal with the eigenvalues on the diagonal; the number of zero entries, equivalently the multiplicity of zero in the eigenvalue list, is $\dim \ker L$ . Thus [F3] and step 2.1 show that the nonempty support graph is connected exactly when zero is simple. This applies in particular for $n \geq 2$ .

3.2F3F4step 2.1algebraconstruct

If the graph is disconnected, choose a nonempty proper component $C$ and put $f = 1_{C} - (∣ C ∣ / n) 1$ . This function is componentwise constant, is nonzero, and has coordinate sum zero. By step 2.1 it belongs to $\ker L \cap 1^{⊥}$ , so a lower bound with $η > 0$ would give $0 \geq η ∥ f ∥_{2}^{2} > 0$ , a contradiction. Hence the stated lower bound implies connectivity.

4.1F3F4step 1.1algebra∎

For the converse limitation, take two vertices, zero diagonal and $A_{12} = A_{21} = 1 / 4$ . The support graph is connected. For $f = (1, - 1) \in 1^{⊥}$ , step 1.1 gives $f^{*} L f = 1$ while $∥ f ∥_{2}^{2} = 2$ , so the bound fails for the prescribed value $η = 1$ . This completes all assertions.

Depends on

Used by · 4

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.