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

Ordered eigenvalues and the centered regular norm

Statement

Let $A$ be the adjacency matrix of a labelled simple $d$ -regular graph on $n \geq 2$ vertices, with $d > 0$ . Order its real eigenvalues with multiplicity as $λ_{1} \geq \dots \geq λ_{n}$ , and let $J$ be the all-ones matrix. Then $λ_{1} = d$ and, with $ρ_{0} (A) = ∥ A - (d / n) J ∥_{o p}$ ,

$ρ_{0} (A) = \max_{2 \leq i \leq n} ∣ λ_{i} ∣ = \max {λ_{2}, ∣ λ_{n} ∣} .$

Only one copy of the eigenvalue $d$ is removed; no connectedness or nonbipartiteness assumption is made. For any finite probability space $(Ω, w)$ and any map $ω \mapsto G (ω)$ into labelled simple $d$ -regular graphs on the same $n$ vertices, let $A (ω)$ be the adjacency matrix of $G (ω)$ and $λ_{i} (ω)$ its eigenvalues in the order above. For every real $t$ , the following subsets of $Ω$ are equal events:

${ω \in Ω : ρ_{0} (A (ω)) \geq t} = {ω \in Ω : \max {λ_{2} (ω), ∣ λ_{n} (ω) ∣} \geq t} .$

Facts & Assumptions

[F1]

Regular adjacency spectra and normalized expansion gives $A 1 = d 1$ , the invariance of $1^{⊥}$ , and the identity between the centered norm and the maximum absolute value of all eigenvalues after removing the constant eigenvector.

[F2]

Pairings, simple-graph conditioning and model transfer defines the finite labelled simple regular graph model.

[F3]

The adjacency matrix of a finite simple graph defines the adjacency matrix in a fixed vertex order: its entry is $1$ precisely for an edge and $0$ otherwise. For a simple graph it is real symmetric and has nonnegative entries.

[F4]

Finite probability spaces, outcome weights, events, and event probabilities defines a finite probability space $(Ω, w)$ and makes every subset of $Ω$ an event.

Proof

Given: The matrix and ordered eigenvalues in the statement; for the event assertion, also the finite probability space and graph-valued map specified there.

Goal: Identify the ordered spectral maximum with the centered norm, and their threshold events.

1.1F1F2F3givenalgebra

By [F2] and [F3], $A$ is real symmetric with nonnegative entries and every row sum $d$ , so [F1] applies. Choose a nonzero real eigenvector $x$ for any eigenvalue $λ$ and a coordinate $v$ maximizing $∣ x_{v} ∣$ . The nonnegative adjacency entries and row sum $d$ imply $∣ λ ∣ ∣ x_{v} ∣ = ∣ \sum_{w} A_{v w} x_{w} ∣ \leq d ∣ x_{v} ∣$ , whence $∣ λ ∣ \leq d$ . Since the constant vector has eigenvalue $d$ , the first ordered eigenvalue is $d$ . Choose that constant vector first in the orthonormal eigenbasis from [F1]. The other eigenvalues, including every remaining copy of $d$ , are exactly $λ_{2}, \dots, λ_{n}$ .

2.1F1step 1.1algebra

The largest absolute value of a decreasing finite real list occurs at an endpoint. If $λ_{2} \geq 0$ , that value is $\max {λ_{2}, ∣ λ_{n} ∣}$ . If $λ_{2} < 0$ , all remaining eigenvalues are negative and $∣ λ_{n} ∣ \geq ∣ λ_{2} ∣$ , giving the same formula. Apply the norm identity in [F1] to this list to obtain the displayed equality for $ρ_{0} (A)$ .

3.1F4givenstep 2.1algebra∎

For each $ω \in Ω$ , the graph $G (ω)$ satisfies the same hypotheses, so step 2.1 gives $ρ_{0} (A (ω)) = \max {λ_{2} (ω), ∣ λ_{n} (ω) ∣}$ . Thus $ω$ belongs to the left threshold subset exactly when it belongs to the right threshold subset, for every real $t$ . Both subsets are events by [F4], proving the event equality.

Depends on

Used by · 5

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.