The second largest eigenvalue of $A$ is $$\lambda_2(A) = 1 - 2 \eta + 2 \eta \cos \frac{2 \pi}{n},$$ (see Eq. (3.7) of [@G06]). Therefore, using the inequality $\cos x \geq 1- x^2/2$, $$\lambda_2(A) \geq 1 - \frac{4 \eta \pi^2}{n^2}.$$ [For $n$ large enough,]{} the quantity on the right-hand side is nonnegative. Let the initial [vector]{} $x(0)$ be the eigenvector corresponding to [$\lambda_2(A)$.]{} Then, $$\frac{V(kB)}{V(0)} = \lambda_2(A)^{2k} \geq \Big(1 - \frac{8 \eta
\pi^2}{n^2}\Big)^k.$$ [For the right-hand side to become]{} less than $\epsilon$, we need $k = \Omega( (n^2/\eta) \log (1/\epsilon))$. [This implies that for $V(k)/V(0)$ to become less than $\epsilon$, we need]{} $k=\Omega( (n^2/\eta) B \log (1/\epsilon))$.

Saving a [factor of]{} $n$: faster averaging on undirected graphs {#matrixpicking}
=================================================================

In the previous section, we have shown that a large class of averaging algorithms have $O(B (n^2/\eta) ~\alexo{ \log
1/\epsilon}) $

In this section, we consider decentralized ways of synthesizing the weights $a_{ij}(k)$ while satisfying Assumptions \[weights\] and \[weakconnect\].

We assume that the communications of the nodes are governed by an exogenous sequence of graphs $\Gb(k)=(N,\Eb(k))$ that provides strong connectivity over time periods of length $B$. in particular, we require that $a_{ij}(k)=0$ if $(j,i)\notin\Eb(k)$. Naturally, we assume that $(i,i)\in\Eb(k)$ for every 