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.

Matrix powers count closed labelled slot walks

Statement

For a finite $d$ -regular adjacency-slot matrix $A$ on $V = {1, \dots, n}$ , with $n \geq 1$ and integer $d > 0$ , fix reversible slot labels representing $A$ . For every integer $m \geq 0$ and $x, y \in V$ , the entry $(A^{m})_{x y}$ equals the number of labelled length- $m$ walks from $x$ to $y$ . Consequently, for every integer $k \geq 0$ , $tr (A^{2 k}) = \sum_{x} (A^{2 k})_{x x}$ counts all closed length- $2 k$ walks with specified starting vertex. Here the trace is the sum of diagonal matrix entries, and $A^{0} = I$ .

Statement references

Regular multigraph and normalized adjacency

Reversible labels for adjacency slots

Facts & Assumptions

Given: The objects and hypotheses in the statement.

Goal: Establish every assertion in the statement.

[F1]

Reversible slot labels represent exactly $A_{x y}$ choices for a step from $x$ to $y$ ; labelled walks retain their actual slot labels (Reversible labels for adjacency slots).

[F2]

The adjacency-slot matrix is a symmetric nonnegative integer matrix indexed by the finite vertex set $V = {1, \dots, n}$ , with row sum $d$ ; diagonal entries count loop slots (Regular multigraph and normalized adjacency).

Proof

1.1F1F2algebra

At length zero there is one walk from $x$ to itself and none to a different vertex, agreeing with $I$ . Suppose the count equals $(A^{m})_{x z}$ for length $m$ . A walk of length $m + 1$ from $x$ to $y$ has a unique last intermediate vertex $z$ , a length- $m$ prefix to $z$ , and one of $A_{z y}$ last slots. The resulting disjoint count is $\sum_{z} (A^{m})_{x z} A_{z y} = (A^{m + 1})_{x y}$ . Induction proves the entry formula.

2.1F2step 1.1algebra∎

Taking $y = x$ counts precisely the closed walks with starting vertex $x$ . Summing these counts over the finitely many vertices gives the trace formula. Distinct parallel labels and distinct loop labels remain distinct choices in this count.

Depends on

Used by · 1

Extracting a nonconstant eigenvalue from closed-walk moments

Dependency tree · 1 level

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.