How quickly can irreducible aperiodic convex combinations of permutation matrices converge to the stationary distribution?

Question

Recall that a doubly stochastic matrix is a square matrix with non-negative entries where the sum of each row and the sum of each column is 1. The Birkhoff-von Neumann theorem states that every doubly stochastic matrix is a linear combination of permutation matrices. By combining the Birkhoff-von Neumann theorem with Caratheodory's theorem, we conclude that every $n\times n$-doubly stochastic matrix is a convex combination of at most $(n-1)^{2}+1$ many permutation matrices.

Now, let $N_{n}=(1/n)_{i=1,j=1}^{n}$. In other words, $N_{n}$ is the matrix where every entry is $1/n$.

Suppose that $A$ is the aperiodic and irreducible convex combination of $r$ many $n\times n$ permutation matrices. Then I want to know how quickly can the Markov chain that corresponds to $A$ can converge to the stationary distribution. Said differently, I want to know how quickly can the sequence $(A^{k})_{k}$ converge to $N_{n}$.

To make this more precise, if $A$ is an aperiodic and irreducible doubly stochastic matrix, then let $$\lambda_{\star,A}=\max\{|\lambda|:\lambda\,\text{is an eigenvalue of $A$},\lambda\neq 1\}.$$ If $A$ is a periodic irreducible doubly stochastic matrix, then $(1,\dots,1)$ is the eigenvector that corresponds to the eigenvalue $1$, so let $V=\mathbb{R}^{n}/\text{span}((1,\dots,1))$, and let $A^{\circ}:V\rightarrow V$ be the linear transformation where $$A^{\circ}(\mathbf{x}+\text{span}((1,\dots,1)))=A(\mathbf{x})+\text{span}((1,\dots,1)).$$ Then $\lambda_{\star,A}$ is simply the spectral radius of $A^{\circ}$.

If $1<r\leq n$, then let $\gamma_{n,r}$ be the minimum of all $\lambda_{\star,A}$ where $A$ is an irreducible aperiodic convex combination of $r$ many permutation matrices.

I am looking for good estimates of the constants $\gamma_{n,r}$. I was able to obtain upper bounds for the constants of the form $\gamma_{n,r}$ that I am satisfied with, but I wonder if these upper bounds can be improved, and I was not able to obtain good lower bounds for the constsnts of the form $\gamma_{n,r}$.

This question is a follow-up of this question.

Basic facts

We are now going to prove a few inequalities involving the constants $\gamma_{n,r}$ to get people started on this problem.

We observe that if $r\leq s$, then $\gamma_{n,r}\geq\gamma_{n,s}$. We observe that since $N_{n}$ is the mean of $n$ many permutation matrices, we conclude that $\gamma_{n,n}=0$.

To do this, we define the tensor power of matrices by letting $A^{\otimes 1}=A$ and $A^{\otimes(k+1)}=A^{\otimes k}\otimes A=A\otimes A^{\otimes k}$ for all $k\geq 1$.

Lemma: For each $r\geq 2,n\geq 1,r\leq 1$, we have $\gamma_{n^{k},r}^{k}\leq\gamma_{n,r}$.

Proof: Let $A$ be an irreducible and aperiodic $n\times n$ matrix that is the convex combination of $r$ many permutation matrices. Then let $B$ be the $n^{k}\times n^{k}$ matrix where $B(u_{1}\otimes\dots\otimes u_{k})=u_{2}\otimes\dots\otimes u_{k}\otimes u_{1}$ for all choices of $u_{1},\dots,u_{k}$. Then observe that $[B(A\otimes I_{n^{k-1}})]^{k}=A^{\otimes k}$. Observe furthermore that $B$ is a permutation matrix and $(A\otimes I_{n^{k-1}})$ is the convex combination of $r$ many permutation matrices. Therefore, $B(A\otimes I_{n^{k-1}})$ is the convex combination of $r$ many permutation matrices as well, and $B(A\otimes I_{n^{k-1}})$ is both aperiodic and irreducible. Now, observe that $\lambda_{\star,A^{\otimes k}}=\lambda_{\star,A}=\lambda_{n,r}$. Therefore, $$\gamma_{n^{k},r}^{k}\leq\lambda_{\star}[B(A\otimes I_{n^{k-1}})]^{k} =\lambda_{\star}[(B(A\otimes I_{n^{k-1}}))^{k}]=\lambda_{\star}[A^{\otimes k}]=\lambda_{n,r}.$$

Q.E.D.

Lemma: $\gamma_{mn,rs}\leq\max(\gamma_{m,r},\gamma_{n,s})$ whenever $m,n,r,s>1$.

Proof: Suppose that $A,B$ are irreducible aperiodic $m\times m,n\times n$ respectively matrices with $\lambda_{\star,A}=\gamma_{m,r},\lambda_{\star,B}=\gamma_{n,s}$ and where $A,B$ are the convex combination of $r,s$ many permutation matrices. Then $A\otimes B$ is an irreducible and aperiodic matrix that is the linear combination of $rs$ many permutation matrices. Furthermore, $\lambda_{\star,A\otimes B}=\max(\gamma_{m,r},\gamma_{n,s})$. Q.E.D.

Lemma: $\gamma_{n,r^{k}}\leq\gamma_{n,r}^{k}$ whenever $n\geq 1,r>1,k\geq 1$.

Proof: Let $A$ be a irreducible aperiodic $n\times n$ matrix that is the convex combination of $r$ many permutation matrices where $\lambda_{\star}[A]=\gamma_{n,r}$. Then $A^{k}$ is an irreducible aperiodic $n\times n$ matrix that is the convex combination of $r^{k}$ many permutation matrices. Therefore, $$\gamma_{n,r^{k}}\leq\lambda_{\star}[A^{k}]=\lambda_{\star}[A]^{k}=\gamma_{n,r}^{k}.$$ Q.E.D.

Therefore, since $\gamma_{n^{k},n}^{k}\leq\gamma_{n,n}=0$, we conclude that $\gamma_{n^{k},n}=0$ for all $k\geq 1,n\geq 1$. In particular, if $n=p_{1}^{a_{1}}\dots p_{k}^{a_{k}}$ where $p_{1},\dots,p_{k}$ are distinct primes and $r=p_{1}\dots p_{k}$, then $\gamma_{n,r}=\max(\gamma_{p_{1}^{a_{1}},p_{1}},\dots,\gamma_{p_{k}^{a_{k}},p_{k}})=0$.

Lemma: Suppose now that $n$ is a natural number and $r$ is relatively prime to $n$. Then $\gamma_{n,r}\leq\frac{1}{r}$.

Proof: Consider the Markov chain $(X_{n})_{n}$ that takes values in $\mathbb{Z}_{n}$ where $X_{n+1}=rX_{n}+Y_{n}$ such that $(Y_{n})_{n}$ are iid random variables selected uniformly at random from $\{[0]_{n},\dots,[r-1]_{n}\}$. Then for each $m$, we have $X_{n+m}=r^{m}X_{n}+[Z]_{n}$ where $Z$ is a random variable that assumes a value selected uniformly at random from $\{0,\dots,r^{m}-1\}$. Therefore, $P(X_{n+m}=a|X_{n}=b)=r^{-m}\lfloor\frac{r^{m}}{n}\rfloor$ or $P(X_{n+m}=a|X_{n}=b)=r^{-m}(\lfloor\frac{r^{m}}{n}\rfloor+1)$ whenever $a,b\in\mathbb{Z}_{n}$. Let $f_{0},\dots,f_{r-1}:\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n}$ be the functions defined by letting $f_{i}([x]_{n})=[rx+i]_{n}$. Let $A=\frac{1}{r}(\rho_{f_{0}}+\dots+\rho_{r-1})$. Then $\lambda_{\star,A}=\sigma(A^{\circ})=\frac{1}{r}$ (Observe that $((rA^{\circ})^{k}$ is the identity matrix for some $k$; you can easily make $rA^{\circ}$ unitary by endowing $V$ with an inner product). Therefore, $\gamma_{n,r}\leq\frac{1}{r}$. Q.E.D.

We have a partial converse to the above result.

Proposition: Suppose that $A=\frac{1}{r}(\rho_{f_{0}}+\dots+\rho_{f_{r-1}})$ where $f_{0},\dots,f_{r-1}\in S_{n}$. Then $\lambda_{\star,A}=0$ or $\lambda_{\star,A}\geq\frac{1}{r}$.

Proof: Let $B=\rho_{f_{0}}+\dots+\rho_{f_{r-1}}$. Then since the spectral radius of $B^{\circ}$ is $r\cdot \lambda_{\star,A}$, it suffices to show that the spectral radius of $B^{\circ}$ is either $0$ or at least $1$. Now, $V$ is generated by the elements of the form $(x_{1},\dots,x_{n})+\langle(1,\dots,1)\rangle$ where $x_{1},\dots,x_{n}$ are integers. If the spectral radius of $B^{\circ}$ is not zero, then for each $N$, we have $(B^{\circ})^{N}\neq 0$, so there is some $$(x_{1},\dots,x_{n})+\langle(1,\dots,1)\rangle\in V$$ with $x_{1},\dots,x_{n}$ integers such that $$(B^{\circ})^{N}((x_{1},\dots,x_{n})+\langle(1,\dots,1)\rangle)\neq 0.$$ However, since the entries in $A$ are integers, we conclude that $$(B^{\circ})^{N}((x_{1},\dots,x_{n})+\langle(1,\dots,1)\rangle)=(y_{1},\dots,y_{n})+\langle(1,\dots,1)\rangle$$ for some integers $y_{1},\dots,y_{n}$. However, this is only possible if the spectral radius of $B^{\circ}$ is at least $1$. Q.E.D.

Answer 1

I believe we can show $$\gamma_{n,r} =\begin{cases} 0 & \textrm{if } n\mid r^k \textrm{ for some }k \\ \frac{1}{r} & \textrm{otherwise} \end{cases}.$$

First, let us show $\gamma_{n,r} \leq \frac{1}{r}$ for all $r$. Let $g =\gcd(n,r)$.

Let the $i$'th permutation send $x\in \mathbb Z/n$ to $$rx + \left(i+ \lfloor \frac{x g }{n} \rfloor\mod r\right)$$ where the $\mod r$ function is understood to take an integer to the residue class mod $r$

Let's examine what this horrible formula does. The ratio $\frac{x g }{n} $ varies between $0$ and $g$, so $\lfloor \frac{x g }{n} \rfloor$ is an integer from $0$ to $g-1$, with each integer occurring for $x$ in an interval of length $n/g$.

So letting $i$ range from $0$ to $r-1$, each $x$ is sent to $rx, \dots, rx+ (r-1)$, so this Markov chain has eigenvalues at most $\frac{1}{r}$ for the reasons given in your post.

On the other hand, fixing $i$, let's check that this is a permutation. Supppose $x_1$ and $x_2$ are taken to the same element of $\mathbb Z/n$. Then we have

$$rx_1 + \left(i+ \lfloor \frac{x_1 g }{n} \rfloor\mod r\right)\equiv rx_2 + \left(i+ \lfloor \frac{x_2 g }{n} \rfloor\mod r\right) \mod n$$ and thus $$rx_1 + \left(i+ \lfloor \frac{x_1 g }{n} \rfloor\mod r\right)\equiv rx_2 + \left(i+ \lfloor \frac{x_2 g }{n} \rfloor\mod r\right) \mod g$$ which implies $$ i+ \lfloor \frac{x_1 g }{n}\rfloor = i+ \lfloor \frac{x_2 g }{n}\rfloor \mod r$$

so now $x_1, x_2$ are in the same interval of length $n/g$, and thus $$ i+ \lfloor \frac{x_1 g }{n}\rfloor = i+ \lfloor \frac{x_2 g }{n}\rfloor ,$$ so subtracting this term

$$r x_1 \equiv rx_2 \mod n$$ which implies $x_1$ and $x_2$ differ by a multiple of $n/g$, hence $x_1=x_2$.

In fact, if a power of $r$ is a multiple of $n$, then this Markov chain which multiplies $r$ and then adds a random number from $0$ to $r-1$ converges to the uniform distribution in finite time (enough time that the power of $r$ achieved by composing the steps is a multiple of $n$ and thus washes out the contribution of the starting value), so $\gamma_{n,r}=0$.

Moreover, no power of $r$ is a multiple of $n$, then clearly the $n$th power of any sum of adjacency matrices can't be have all entries equal, as that would require the columns to sum to a multiple of $n$, so your $\lambda =0$ case can't happen and $\gamma_{n,r}=\frac{1}{r}$.