Spectrum of the lazy Johnson walk

For $0\le k\le r$, let $V_k={\mathbb{C}}^{\left(\genfrac{}{}{0px}{}{[N]}{k}\right)}$ with the standard coordinate inner product, linear in the first argument as in Real and complex inner product spaces, with the inner product linear in the first argument. For $0\le k<r$, define the up map $R_k:V_k\to V_{k+1}$ by $(R_{k}f)(B)={\sum }_{a\in B}f(B\setminus \{a\})$ and the down map $L_{k+1}:V_{k+1}\to V_k$ by $(L_{k+1}g)(A)={\sum }_{b\mathrm{\notin }A}g(A\cup \{b\})$. Expanding the finite sums with this convention gives $⟨R_{k}f,g⟩={\sum }_{A}f(A)\overline{{\sum }_{b\mathrm{\notin }A}g(A\cup \{b\})}=⟨f,L_{k+1}g⟩;$ by [F4], $L_{k+1}=R_k^{\ast }$. Put $L_0:V_0\to \{0\}$ equal to zero. For $0\le k<r$ and $f\in V_k$, the diagonal terms in $L_{k+1}{R}_{k}f$ occur $N-k$ times, the diagonal terms in $R_{k-1}{L}_{k}f$ occur $k$ times, and both have the same off-diagonal replacement terms. Hence $L_{k+1}{R}_k-R_{k-1}{L}_k=(N-2k)I_{V_k}$, where the second term is zero for $k=0$.

Taking the inner product of the identity in step 1.1 with $f$ gives $\mathrm{\parallel }{R}_{k}f{\mathrm{\parallel }}^2=\mathrm{\parallel }{L}_{k}f{\mathrm{\parallel }}^2+(N-2k)\mathrm{\parallel }f{\mathrm{\parallel }}^2$. Since $k<N\mathrm{/}2$ for $0\le k<r$, $R_k$ is injective, so [F2] gives $\dim \mathrm{ran}{R}_k=\dim V_k$. By [F4] and [F5], $\ker L_{k+1}=\ker R_k^{\ast }=(\mathrm{ran}{R}_k{)}^{\perp }$. Apply [F3] to $W=\mathrm{ran}{R}_k$; the projection onto $W$ along $W^{\perp }$ is linear, with image $W$ and kernel $\ker L_{k+1}$, so [F2] gives $\dim V_{k+1}=\dim \mathrm{ran}{R}_k+\dim \ker L_{k+1}$. Applying [F2] to $L_{k+1}$ then yields $\dim \mathrm{ran}{L}_{k+1}=\dim V_k$, so $L_{k+1}:V_{k+1}\to V_k$ is onto. Put $H_0=V_0$ and $H_j=\ker L_j$ for $1\le j\le r$; [F2] gives $\dim H_j=\left(\genfrac{}{}{0px}{}{N}{j}\right)-\left(\genfrac{}{}{0px}{}{N}{j-1}\right)$.

If $h\in H_j$, repeated use of step 1.1 gives, for $t\ge 1$ with $j+t\le r$, $L_{j+t}{R}_{j+t-1}\cdots R_{j}h=t(N-2j-t+1)R_{j+t-2}\cdots R_{j}h\mathrm{.}$ For $t=1$ this is the commutator identity and $L_{j}h=0$. Empty products of raising maps mean the identity. If it holds at $t$ and $j+t<r$, apply the commutator at level $j+t$; the coefficient becomes $t(N-2j-t+1)+(N-2j-2t)=(t+1)(N-2j-t)$, proving the formula for $t+1$.

On $V_r$, the Johnson adjacency operator is $A=R_{r-1}{L}_r-rI$: the $r$ diagonal choices in $R_{r-1}{L}_r$ return the same subset, and every other term replaces exactly one element. Since $L_r=R_{r-1}^{\ast }$ by step 1.1, [F6] gives $A^{\ast }=A$. For $j<r$, applying step 3.1 with $t=r-j$ shows that $R_{r-1}\cdots R_j{H}_j$ is an eigenspace of $A$ with eigenvalue $(r-j)(N-r-j+1)-r$. For $j=r$, the empty raising product is the identity on $H_r$, and $L_r{H}_r=0$ gives $A{\mathrm{\mid }}_{H_r}=-rI$ directly, the same formula. The raising maps are injective by step 2.1, so this eigenspace has dimension $\dim H_j$. These eigenvalues are distinct because consecutive values differ by $N-2j>0$ for $j<r\le N\mathrm{/}2$. For $v,w$ in eigenspaces with distinct eigenvalues $\alpha ,\beta$, self-adjointness gives $(\alpha -\beta )⟨v,w⟩=⟨Av,w⟩-⟨v,Aw⟩=0$; hence the eigenspaces are mutually orthogonal. Their dimensions sum telescopically to $\left(\genfrac{}{}{0px}{}{N}{r}\right)=\dim V_r$, so their direct sum is all of $V_r$.

The nonlazy transition is $A\mathrm{/}[r(N-r)]$ by [F1], and the lazy transition is its average with the identity. Therefore its eigenvalue on the $j$th eigenspace is $\frac{1}{2}(1+\frac{(r-j)(N-r-j+1)-r}{r(N-r)})=1-\frac{j(N+1-j)}{2r(N-r)}\mathrm{.}$ The transitions are symmetric and row-stochastic, so the uniform positive law is stationary and satisfies detailed balance; [F7] makes this a finite reversible chain and defines its absolute gap on the mean-zero subspace. The $j=0$ eigenspace has multiplicity one and is spanned by the constant vector. The other eigenspaces are orthogonal to it by self-adjointness, and their eigenvalues are nonnegative and decreasing in $j$, since $j(N+1-j)$ increases for $0\le j\le r\le N\mathrm{/}2$. If $v={\sum }_{j=1}^r{v}_j$ is the orthogonal decomposition into these eigenspaces, then $\mathrm{\parallel }Pv{\mathrm{\parallel }}^2={\sum }_{j=1}^r{\lambda }_j^2\mathrm{\parallel }{v}_j{\mathrm{\parallel }}^2\le {\lambda }_1^2\mathrm{\parallel }v{\mathrm{\parallel }}^2$, with equality on a nonzero vector in the $j=1$ eigenspace. Hence the norm of $P$ on the mean-zero subspace is ${\lambda }_1$. The smallest eigenvalue is ${\lambda }_r=(N-r-1)\mathrm{/}(2(N-r))\ge 0$, since $N-r\ge 2$. Therefore the absolute gap is $1-{\lambda }_1=N\mathrm{/}[2r(N-r)]$, as stated.