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.