---
title: "Admissibility, Mean, and Spectral Contraction of the Fixed-Epoch Averaging Matrix"
author: "Guillaume Bolduc"
version: "v01"
format: "Derived Markdown edition"
source_tex_sha256: "569a2707d023505d86bbdd0aa60446fd71dbbac4c634e80cdf79ff31676943c6"
---

# Admissibility, Mean, and Spectral Contraction of the Fixed-Epoch Averaging Matrix

**Author:** Guillaume Bolduc  
**Version:** v01  
**Status:** current companion note

> This Markdown edition was mechanically derived from the selected LaTeX source. LaTeX mathematics and any complex layout commands are intentionally retained where a safe Markdown equivalent was not available. The exact source binding is SHA-256 `569a2707d023505d86bbdd0aa60446fd71dbbac4c634e80cdf79ff31676943c6`.

{BOLDUC: ADMISSIBILITY, MEAN, AND SPECTRAL CONTRACTION OF THE FIXED-EPOCH AVERAGING MATRIX}

## Abstract

This note isolates the fixed-epoch averaging result used as Lemma~2.1 of *Priority-State Dynamics in Open Multi-Agent Systems: Dynamic Membership and History-Dependent Consensus Endpoints*. For a connected simple undirected graph with Laplacian $L$, maximum degree $d_{\max}$, and gain $0<c<d_{\max}^{-1}$, the matrix $P=I-cL$ is nonnegative, symmetric, doubly stochastic, and has positive diagonal. It preserves the nonnegative and strictly positive row-stochastic state spaces and their population mean. On the disagreement subspace it contracts geometrically in Frobenius norm with factor $\rho=\max_{j\ge 2}|1-c\lambda_j(L)|<1$. We give a self-contained proof, identify the exact spectral-contraction range $0<c<2/\lambda_n(L)$ when stochasticity is not required, show why the strict governing gain bound cannot be replaced uniformly by $c\le d_{\max}^{-1}$, exhibit the attainable case $\rho=0$, and separate positive-state invariance from positive-diagonal and contraction requirements. These statements concern one fixed connected averaging epoch only; they do not establish results for delayed, asynchronous, open-membership, or distributed membership-transition dynamics.

\begin{IEEEkeywords}
average consensus, graph Laplacian, spectral contraction, stochastic matrix, simplex invariance.
\end{IEEEkeywords}

## Relation to the Governing Article

The governing article~[citation: bolduc_priority] defines the fixed-population update

$$

P=I-cL, \qquad W(k+1)=P W(k),
<a id="eq:update"></a>

$$

for a connected simple undirected graph. Its Lemma~2.1 states the admissibility, mean-preservation, and contraction properties used to interpret later event histories through the endpoint of a subsequent fixed epoch. The same article now contains a concise proof in its Appendix~A. The purpose here is narrower: to isolate that fixed-epoch result, give the proof in full, and separate the distinct thresholds governing stochasticity, positive diagonal, positive-state invariance, and spectral contraction. The result itself is standard average-consensus mathematics; no novelty claim is attached to the underlying spectral argument~[citation: olfati2007,horn2013,godsil2001].

Nothing below changes the state-transition semantics or open-membership results of~[citation: bolduc_priority]. In particular, the proof does not cover stale packets, asynchronous updates, changing membership, or a distributed agreement mechanism for event boundaries. Those require separate assumptions and results.

## Fixed-Epoch Averaging

### Setting and notation

Let $n\ge 2$. Let $G$ be a connected simple undirected graph with zero-diagonal adjacency matrix $H$, degrees

$$

d_i=\sum_j H_{ij}, \qquad d_{\max}=\max_i d_i,

$$

and Laplacian

$$

L=\operatorname{diag}(d)-H.

$$

Choose

$$

0<c<d_{\max}^{-1}, \qquad P=I-cL.
<a id="eq:gain"></a>

$$

For $n=1$, define $P=[1]$ and omit the gain condition.

Define the row-stochastic and strictly positive row-stochastic spaces

$$

\mathcal{S}_n
&=\{W\in\R^{n\times n}: W\ge 0,\; W\one_n=\one_n\},\\
\mathcal{S}_n^{+}
&=\{W\in\mathcal{S}_n: W_{ij}>0\ \text{for all }i,j\},

$$

where inequalities are entrywise. The mean row is

$$

\mrow(W)=\frac{1}{n}\one_n^{\top}W.
<a id="eq:mean"></a>

$$

Let

$$

J=\frac{1}{n}\one_n\one_n^{\top},
<a id="eq:J"></a>

$$

so that $JW=\one_n\mrow(W)$ for every $W\in\R^{n\times n}$.

### Lemma: Admissibility, mean and spectral contraction

<a id="lem:governing"></a>
Under~\eqref{eq:update}--\eqref{eq:gain}, $P$ is nonnegative, symmetric and doubly stochastic with positive diagonal. It maps $\mathcal{S}_n$ into itself and $\mathcal{S}_n^{+}$ into itself. If $n\ge 2$, there exists $0\le \rho<1$ such that, for every $W\in\R^{n\times n}$ and every $k\ge 1$,

$$

\left\|P^kW-\one_n\mrow(W)\right\|_F
\le
\rho^k\left\|W-\one_n\mrow(W)\right\|_F.
<a id="eq:contraction"></a>

$$

For $k=0$ the same inequality holds with factor one. Moreover $\mrow(PW)=\mrow(W)$. For $n=1$, consensus is already attained.

## Proof of Lemma 2.1

### Structure of the averaging matrix

Since $L=\operatorname{diag}(d)-H$,

$$

P_{ij}=cH_{ij}\quad(i\ne j),
\qquad
P_{ii}=1-cd_i.
<a id="eq:Pentries"></a>

$$

The off-diagonal entries are nonnegative. Since $d_i\le d_{\max}$ and $c<d_{\max}^{-1}$,

$$

cd_i\le cd_{\max}<1,

$$

so every diagonal entry is strictly positive. Hence $P\ge 0$ with positive diagonal.

The graph is undirected, so $H=H^{\top}$ and $L=L^{\top}$; therefore $P=P^{\top}$. Also $L\one_n=0$, and consequently

$$

P\one_n=\one_n.

$$

Symmetry then gives $\one_n^{\top}P=\one_n^{\top}$. Thus $P$ is doubly stochastic.

### Invariance of the priority-state spaces

Take $W\in\mathcal{S}_n$. Nonnegativity of $P$ and $W$ gives $PW\ge 0$, while

$$

(PW)\one_n=P(W\one_n)=P\one_n=\one_n.

$$

Hence $PW\in\mathcal{S}_n$.

Now take $W\in\mathcal{S}_n^{+}$. For every $i,j$,

$$

(PW)_{ij}=\sum_{r=1}^{n}P_{ir}W_{rj}
\ge P_{ii}W_{ij}>0.
<a id="eq:positive"></a>

$$

Thus $PW\in\mathcal{S}_n^{+}$. Section~IV-D below shows that the positive diagonal used in~\eqref{eq:positive} is sufficient but not necessary for this last conclusion.

### Mean preservation

Since $P$ is column stochastic,

$$

\mrow(PW)
=\frac{1}{n}\one_n^{\top}PW
=\frac{1}{n}\one_n^{\top}W
=\mrow(W).
<a id="eq:meanpres"></a>

$$

This identity holds for every real matrix $W$ of the proper dimension; stochasticity of $W$ is not required.

### Spectrum of the Laplacian and of $P$

For every $x\in\R^n$,

$$

x^{\top}Lx
=\sum_{\{i,j\}\in E}(x_i-x_j)^2\ge 0,
<a id="eq:quad"></a>

$$

so $L$ is positive semidefinite. Because $G$ is connected,

$$

\ker L=\operatorname{span}\{\one_n\},

$$

and its ordered eigenvalues satisfy

$$

0=\lambda_1<\lambda_2\le\cdots\le\lambda_n.
<a id="eq:lap_spec"></a>

$$

Also,

$$

x^{\top}Lx
&=\sum_{\{i,j\}\in E}(x_i-x_j)^2\\
&\le 2\sum_{\{i,j\}\in E}(x_i^2+x_j^2)\\
&=2\sum_i d_i x_i^2
\le 2d_{\max}\|x\|_2^2.

$$

The Rayleigh quotient therefore gives

$$

\lambda_n\le 2d_{\max}.
<a id="eq:lmax"></a>

$$

Since $P=I-cL$, it has the same orthonormal eigenvectors as $L$, with eigenvalues

$$

\mu_i=1-c\lambda_i.

$$

The consensus eigenvalue is $\mu_1=1$. For $i\ge 2$, positivity of $c$ and~\eqref{eq:lap_spec} give $\mu_i<1$. Moreover, by~\eqref{eq:gain} and~\eqref{eq:lmax},

$$

c\lambda_i\le c\lambda_n\le 2cd_{\max}<2,

$$

so $\mu_i>-1$. Define

$$

\rho=\max_{2\le i\le n}|1-c\lambda_i|.
<a id="eq:rho"></a>

$$

Then $0\le\rho<1$.

### Contraction on the disagreement subspace

The projector~\eqref{eq:J} satisfies

$$

PJ=J,\qquad JP=J,

$$

because $P\one_n=\one_n$ and $\one_n^{\top}P=\one_n^{\top}$. Hence $P^kJ=J$ for every $k\ge 0$, and

$$

P^kW-\one_n\mrow(W)
&=P^kW-JW\\
&=P^k(I-J)W.
<a id="eq:projected"></a>

$$

Set

$$

M=(I-J)W=W-\one_n\mrow(W).

$$

Every column of $M$ lies in $\one_n^{\perp}$. The restriction of the symmetric matrix $P$ to $\one_n^{\perp}$ has eigenvalues $\mu_2,\ldots,\mu_n$, so its Euclidean operator norm is exactly $\rho$. Thus, for every $v\in\one_n^{\perp}$,

$$

\|P^k v\|_2\le \rho^k\|v\|_2.

$$

Applying this column by column to $M$ gives

$$

\|P^kM\|_F^2
&=\sum_{j=1}^{n}\|P^kM_{\cdot j}\|_2^2\\
&\le \rho^{2k}\sum_{j=1}^{n}\|M_{\cdot j}\|_2^2
=\rho^{2k}\|M\|_F^2.

$$

Taking square roots and using~\eqref{eq:projected} proves~\eqref{eq:contraction}. For $k=0$, the two disagreement norms coincide, so the appropriate multiplicative factor is one. This separate statement avoids assigning a meaning to $0^0$ when $\rho=0$.

### Singleton case

For $n=1$, $P=[1]$ and $J=[1]$. Therefore $W-\one_1\mrow(W)=0$ for every $1\times 1$ state, and consensus is already attained. This completes the proof of Lemma~2.1. \hfill$\square$

## Gain Conditions and Sharpness

The governing hypothesis $0<c<d_{\max}^{-1}$ simultaneously guarantees a nonnegative stochastic matrix, positive diagonal, and strict spectral contraction. Those requirements have different exact thresholds.

### Exact spectral-contraction range

### Proposition: Exact contraction range

<a id="prop:exactrange"></a>
For a connected graph with $n\ge 2$ and $c>0$, the restriction of $P=I-cL$ to $\one_n^{\perp}$ is a strict Euclidean contraction if and only if

$$

0<c<\frac{2}{\lambda_n(L)}.
<a id="eq:exactrange"></a>

$$

Equivalently, the factor~\eqref{eq:rho} satisfies $\rho<1$ exactly on this interval.

\begin{IEEEproof}
The condition $\rho<1$ is equivalent to

$$

|1-c\lambda_i|<1\qquad \text{for every }i\ge 2.

$$

Since $c>0$ and every $\lambda_i>0$ for $i\ge 2$, the left inequality is automatic and the right inequality is $c\lambda_i<2$. The strongest condition occurs at $\lambda_n$, yielding~\eqref{eq:exactrange}.
\end{IEEEproof}

By~\eqref{eq:lmax}, $c<d_{\max}^{-1}$ implies~\eqref{eq:exactrange}; the implication can be strict. For the star $K_{1,6}$, $d_{\max}=6$ and $\lambda_n=7$, so

$$

\frac{1}{d_{\max}}=\frac{1}{6}<\frac{2}{7}=\frac{2}{\lambda_n}.

$$

The larger spectral interval is relevant only when nonnegativity of $P$ is not required. In the priority-state dynamics of~[citation: bolduc_priority], $P$ must remain a stochastic mixing matrix, so the governing stochasticity restriction remains operative.

### Why the strict governing bound is load-bearing

### Proposition: The endpoint cannot be admitted uniformly

<a id="prop:boundary"></a>
There exist connected graphs for which $c=d_{\max}^{-1}$ gives $\rho=1$. In particular, this occurs for every connected $d_{\max}$-regular bipartite graph.

\begin{IEEEproof}
Let $G$ be connected, $d$-regular, and bipartite with parts $V_1,V_2$. Let $x_i=1$ on $V_1$ and $x_i=-1$ on $V_2$. Every edge joins opposite signs, so

$$

\frac{x^{\top}Lx}{\|x\|_2^2}
=\frac{4|E|}{n}
=2d.

$$

Together with $\lambda_n\le 2d$, this forces $\lambda_n=2d$. At $c=d^{-1}$ the corresponding eigenvalue of $P$ is $1-c\lambda_n=-1$, hence $\rho=1$.
\end{IEEEproof}

The minimal example is $K_2$. Here $d_{\max}=1$, $c=1$, and

$$

P=\begin{bmatrix}0&1\\1&0\end{bmatrix}.

$$

Unequal rows are swapped at every iteration, so disagreement is periodic rather than contracting. The governing strict inequality therefore cannot be weakened uniformly to $c\le d_{\max}^{-1}$.

### The contraction factor can equal zero

### Proposition: Exact one-step consensus

<a id="prop:rhozero"></a>
On the complete graph $K_n$, the admissible choice $c=1/n$ gives $P=J$ and hence $\rho=0$.

\begin{IEEEproof}
For $K_n$,

$$

L=nI-\one_n\one_n^{\top}.

$$

Therefore

$$

P=I-\frac{1}{n}L
=\frac{1}{n}\one_n\one_n^{\top}=J.

$$

Thus $PW=JW=\one_n\mrow(W)$ after one update for every $W$.
\end{IEEEproof}

This explains why Lemma~2.1 states $0\le\rho<1$, rather than $0<\rho<1$, and why the $k=0$ case is written separately.

### Positive-state invariance needs no positive diagonal

### Remark: Endpoint invariance of $\mathcal{S}_n^{+}$

<a id="rem:positive"></a>
If $P$ is any nonnegative row-stochastic matrix and $W\in\mathcal{S}_n^{+}$, then $PW\in\mathcal{S}_n^{+}$. Each row of $P$ contains at least one positive entry because its entries are nonnegative and sum to one; for such an index $r$,

$$

(PW)_{ij}\ge P_{ir}W_{rj}>0.

$$

Consequently, for $P=I-cL$, strict positivity of the state is preserved throughout the full nonnegative-stochastic range $0\le c\le d_{\max}^{-1}$. The strict inequality in Lemma~2.1 is required for its literal positive-diagonal claim and for a uniform contraction guarantee, not for positive-state invariance itself.

## Verification and Scope

As a regression check against transcription or sign errors, the formulas above were evaluated on 4000 pseudorandom connected simple graphs with $2\le n\le 8$, gains sampled strictly inside $(0,d_{\max}^{-1})$, positive row-stochastic states and unrestricted Gaussian matrices. The checks covered nonnegativity, symmetry, double stochasticity, positive diagonal, mean preservation, the Laplacian bounds, $\rho<1$, and~\eqref{eq:contraction} for $k=1,\ldots,8$. Separate deterministic checks covered the boundary swap on $K_2$, $P=J$ on complete graphs at $c=1/n$, the strict interval separation on $K_{1,6}$, and positive-state invariance at $c=d_{\max}^{-1}$. No violation was observed beyond floating-point tolerance. These computations corroborate finite instances only; the proof above carries the general result.

The distinction among assumptions should remain explicit. Proposition~\ref{prop:exactrange} concerns spectral contraction even when $P$ is no longer a nonnegative mixing matrix. Lemma~2.1 requires the stronger gain condition because later priority-state arguments need stochastic admissibility as well as contraction. Remark~\ref{rem:positive} concerns only preservation of strict positivity under a nonnegative row-stochastic map. None of these fixed-epoch facts supplies delay compensation, open-membership invariance, agreement on an active label set, or a distributed implementation of membership events.

## Conclusion

Lemma~2.1 follows directly from the graph-Laplacian spectrum and the orthogonal decomposition into the consensus direction and its disagreement subspace. The governing gain condition is a conservative condition that simultaneously preserves stochastic admissibility, positive diagonal, and strict contraction. The separate sharpness results show which clauses survive at or beyond that bound and which do not. In particular, contraction alone permits $c<2/\lambda_n(L)$, positive-state invariance survives at the nonnegative-stochastic endpoint $c=d_{\max}^{-1}$, but uniform strict contraction does not.

## Acknowledgment

AI agents assisted drafting and refinement throughout this manuscript, including mathematical formulation, proof construction and adversarial examination. They also assisted development and execution of verification checks. They are not authors. No simulation result is presented. Human final review and acceptance remain pending; the human author is responsible for the manuscript.

## References

1.
G. Bolduc, “Priority-State Dynamics in Open Multi-Agent Systems: Dynamic Membership and History-Dependent Consensus Endpoints,” working preprint, full ed., version 07, Sep. 7, 2026.

1.
R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” *Proc. IEEE*, vol. 95, no. 1, pp. 215--233, Jan. 2007, doi: 10.1109/JPROC.2006.887293.

1.
R. A. Horn and C. R. Johnson, *Matrix Analysis*, 2nd ed. Cambridge, U.K.: Cambridge University Press, 2013.

1.
C. Godsil and G. Royle, *Algebraic Graph Theory*. New York, NY, USA: Springer, 2001.