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.

Regular adjacency spectra and normalized expansion

Statement

Let $V$ be a finite set with $n = ∣ V ∣ \geq 1$ , and let $A = (A_{x y})_{x, y \in V}$ be a real symmetric matrix with nonnegative entries and every row sum equal to $d > 0$ . Write $1$ for the constant-one vector, $J$ for the all-ones matrix, and $1^{⊥} = {f : \sum_{x} f (x) = 0}$ . Use the Euclidean operator norm induced by $∥ f ∥_{2}^{2} = \sum_{x} ∣ f (x) ∣^{2}$ . Then $A 1 = d 1$ , $1^{⊥}$ is invariant under $A$ , and

${∥ A - \frac{d}{n} J ∥}_{o p} = {∥ A ∣_{1^{⊥}} ∥}_{o p} .$

The norm of an operator on the zero space is zero. For $n \geq 2$ , choose an orthonormal real eigenbasis of $A$ whose first vector is $1 / \sqrt{n}$ , and denote the corresponding eigenvalues by $d = λ_{1}, λ_{2}, \dots, λ_{n}$ , with multiplicity. Then both norms equal $\max_{i \geq 2} ∣ λ_{i} ∣$ . A further eigenvector with eigenvalue $d$ , or an eigenvector with eigenvalue $- d$ , is included in this maximum. For $n = 1$ both norms are zero and the maximum over $i \geq 2$ is not used.

Put $M = A / d$ . Its restriction to $1^{⊥}$ has norm $α = ∥ A - (d / n) J ∥_{o p} / d$ . If $A$ is specifically the integer adjacency-slot matrix of a finite $d$ -regular graph in the convention of Regular multigraph and normalized adjacency, then for subsets $S, T \subseteq V$ , with $e (S, T) = \sum_{x \in S, y \in T} A_{x y}$ counting ordered slots, the expander mixing estimate is

$∣ e (S, T) - \frac{d ∣ S ∣ ∣ T ∣}{n} ∣ \leq d α \sqrt{∣ S ∣ (1 - ∣ S ∣ / n) ∣ T ∣ (1 - ∣ T ∣ / n)} .$

Here diagonal entries count loop slots; overlap between $S$ and $T$ is allowed. For a disconnected slot graph, another eigenvector of $A$ with eigenvalue $d$ exists. For a connected slot graph whose positive slots join opposite parts of a bipartition, $- d$ is an eigenvalue. In either case the corresponding eigenvalue is retained in the mean-zero spectrum.

Facts & Assumptions

Given: The matrix and, where invoked, the adjacency-slot graph described in the statement.

Goal: Prove the centered norm identity, its normalized form, and the stated graph consequences.

[F1]

The vertex space has the stated Euclidean inner product and matrix action; a real symmetric matrix acts self-adjointly (Finite vertex Hilbert space in the article convention).

[F2]

A self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis (Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis).

[F3]

For a symmetric real square matrix of positive order, its Euclidean operator norm is the largest absolute value of its eigenvalues (A symmetric matrix operator norm is its largest absolute Rayleigh quotient).

[F4]

Orthogonal projection onto a subspace sends each vector to its component in that subspace along its orthogonal complement (The orthogonal projection P_Wv is the W-component in V=W⊕ W^⊥).

[F5]

In the adjacency-slot convention, $A$ is a symmetric nonnegative integer matrix with row sum the positive integer $d$ ; $A_{x y}$ counts slots, diagonal entries count loop slots, and normalized adjacency is $M = A / d$ (Regular multigraph and normalized adjacency). The normalized spectral parameter is $α = ∥ M ∣_{1^{⊥}} ∥$ , with $α = 0$ for $n = 1$ (Spectral edge and vertex expansion).

[F6]

For such a slot graph the multiplicity of eigenvalue $1$ of $M$ is the number of connected components. For a connected graph, $- 1$ is an eigenvalue exactly when its positive slots join opposite parts of a bipartition (Constant vector is a top eigenvector).

[F7]

The expander mixing lemma gives the displayed ordered-slot estimate for the conventions and parameter in [F5], including loops and overlapping subsets (Expander mixing lemma).

[F8]

For a linear map $T : E \to F$ between finite-dimensional real or complex inner product spaces, its operator norm is $\max_{∥ v ∥ = 1} ∥ T v ∥$ when $E \neq {0}$ and is zero when $E = {0}$ (The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖).

Proof

1.1F1F4algebra

The row-sum condition gives $A 1 = d 1$ . For any $f$ , self-adjointness gives $⟨ 1, A f ⟩ = ⟨ A 1, f ⟩ = d ⟨ 1, f ⟩$ ; hence $A$ preserves $1^{⊥}$ . The vector $(n^{- 1} \sum_{x} f (x)) 1$ lies in the constant subspace and its difference from $f$ is mean zero. By [F4], $P = J / n$ is the orthogonal projection onto the constants. Thus $A - (d / n) J = A - d P$ is zero on constants and agrees with $A$ on $1^{⊥}$ .

2.1F2F3F8step 1.1algebra

The restriction of $A$ to the real mean-zero subspace is self-adjoint. If $n \geq 2$ , apply [F2] to that restriction and adjoin $1 / \sqrt{n}$ to obtain the stated eigenbasis. In this basis $A - d P$ has eigenvalues $0, λ_{2}, \dots, λ_{n}$ . By [F3], its norm is $\max_{i \geq 2} ∣ λ_{i} ∣$ ; the same calculation on the restriction gives the same norm. A real eigenbasis also computes the complex operator norm: expanding a complex vector in this basis gives the same upper bound, attained at a real maximizing eigenvector. When $n = 1$ , $P = I$ and the mean-zero space is zero, so both norms are zero.

3.1F1F8step 1.1step 2.1algebra

A second independent $d$ -eigenvector can be made orthogonal to $1$ by subtracting its constant projection, leaving a nonzero $d$ -eigenvector. A $- d$ -eigenvector is orthogonal to $1$ because self-adjointness and $d > 0$ give $- d ⟨ 1, v ⟩ = d ⟨ 1, v ⟩$ . Thus neither is discarded when the first constant vector is removed. Division by $d$ gives $∥ M ∣_{1^{⊥}} ∥ = ∥ A - (d / n) J ∥_{o p} / d$ , including the zero-space case.

4.1F5F6F7step 3.1algebra∎

Under the additional integer slot hypotheses, [F5] identifies this normalized norm with the mixing lemma's $α$ , and [F7] gives the displayed estimate with precisely its ordered-slot, loop and overlap conventions. By [F6], disconnectedness supplies a second $1$ -eigenvector of $M$ , while the stated connected bipartition supplies a $- 1$ -eigenvector. Multiplication by $d$ and step 3.1 give the final assertions. This proves all claims.

Depends on

Used by · 8

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.