Recall that a doubly stochastic matrix is a square matrix $A$ with non-negative entries such that the sum of each row is $1$ and the sum of each column is $1$. The Birchoff-von Neumann theorem states that every doubly stochastic matrix is a convex combination of (at most $(n-1)^{2}+1$, by Caratheodory's theorem) permutation matrices.

Let $N_{n}=(1/n)_{i=1,j=1}^{n}$ be the matrix where each of the entries are $1/n$. Then $N$ can be written as a convex combination of $n$ permutation matrices, but $N_{n}$ cannot be written as a convex combination of less than $n$ permutation matrices.

For each $n$, let $t_{n}$ be the least natural number such that there exists a doubly stochastic matrix $A$ that is a convex combination of $t_{n}$ many permutation matrices and where $A^{k}=N_{n}$ for some $k>0$. Observe that $1<t_{n}\leq n$ whenever $n>1$.

Furthermore, $t_{m^{r}}\leq m$ for all $m$. To see this, Consider the functions $$f,f_{1},\dots,f_{m}:\{0,\dots,m-1\}^{r}\rightarrow\{0,\dots,m-1\}^{r}$$ defined by letting $$f(x_{1},\dots,x_{r})=(x_{2},\dots,x_{r},x_{1})$$ and $$f_{i}(x_{1},x_{2},\dots,x_{r})=(x_{1}+i,x_{2},\dots,x_{r})$$ where addition is taken modulo $m$. Then if $$A=\frac{1}{m}(\sigma_{ff_{1}}+\dots+\sigma_{ff_{m}}),$$ then $A^{r}=N_{m^{r}}$. In fact, one can generalize this example to show that $t_{m_{r}}\leq t_{m}$.

We have $t_{mn}\leq t_{m}\cdot t_{n}$ since if $A^{k}=N_{m},B^{k}=N_{n}$, then $(A\otimes B)^{k}=N_{m}\otimes N_{n}=N_{mn}$, and if $A$ is the convex combination of $t_{m}$ permutation matrices and $B$ is the convex combination of $t_{n}$ many permutation matrices, then $A\otimes B$ is the convex combination of $t_{m}t_{n}$ permutation matrices.

By combining these bounds together, we obtain $t_{n}\leq p_{1}\dots p_{k}$ whenever $n=p_{1}^{a_{1}}\dots p_{k}^{a_{k}}$ and $p_{1},\dots,p_{k}$ are distinct primes.

What are the exact values of the constants $t_{n}$? Is $t_{n}$ simply the product of all prime factors of $n$? Can one compute all or some of the sequences of permutations $(f_{1},\dots,f_{r})$ and positive constants $\lambda_{1},\dots,\lambda_{r}$ such that $r=t_{n},\lambda_{1}+\dots+\lambda_{r}=1$, $f_{i}\in S_{n}$ for each $i$, and where there is some $k$ where if $A=\lambda_{1}\sigma_{f_{1}}+\dots+\lambda_{r}\sigma_{f_{r}}$, then $A^{k}=N_{n}$?

If the exact values of $t_{n}$ are difficult to evaluate, then I would like to know good upper and lower bounds for $t_{n}$.

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

Let $N_{n}=(1/n)_{i=1,j=1}^{n}$ be the matrix where each of the entries are $1/n$. Then $N$ can be written as a convex combination of $n$ permutation matrices, but $N_{n}$ cannot be written as a convex combination of less than $n$ permutation matrices.

For each $n$, let $t_{n}$ be the least natural number such that there exists a doubly stochastic matrix $A$ that is a convex combination of $t_{n}$ many permutation matrices and where $A^{k}=N_{n}$ for some $k>0$. Observe that $1<t_{n}\leq n$ whenever $n>1$.

Furthermore, $t_{m^{r}}\leq m$ for all $m$. To see this, Consider the functions $$f,f_{1},\dots,f_{m}:\{0,\dots,m-1\}^{r}\rightarrow\{0,\dots,m-1\}^{r}$$ defined by letting $$f(x_{1},\dots,x_{r})=(x_{2},\dots,x_{r},x_{1})$$ and $$f_{i}(x_{1},x_{2},\dots,x_{r})=(x_{1}+i,x_{2},\dots,x_{r})$$ where addition is taken modulo $m$. Then if $$A=\frac{1}{m}(\sigma_{ff_{1}}+\dots+\sigma_{ff_{m}}),$$ then $A^{r}=N_{m^{r}}$. In fact, one can generalize this example to show that $t_{m_{r}}\leq t_{m}$.

We have $t_{mn}\leq t_{m}\cdot t_{n}$ since if $A^{k}=N_{m},B^{k}=N_{n}$, then $(A\otimes B)^{k}=N_{m}\otimes N_{n}=N_{mn}$, and if $A$ is the convex combination of $t_{m}$ permutation matrices and $B$ is the convex combination of $t_{n}$ many permutation matrices, then $A\otimes B$ is the convex combination of $t_{m}t_{n}$ permutation matrices.

By combining these bounds together, we obtain $t_{n}\leq p_{1}\dots p_{k}$ whenever $n=p_{1}^{a_{1}}\dots p_{k}^{a_{k}}$ and $p_{1},\dots,p_{k}$ are distinct primes.

What are the exact values of the constants $t_{n}$? Is $t_{n}$ simply the product of all prime factors of $n$? Can one compute all or some of the sequences of permutations $(f_{1},\dots,f_{r})$ and positive constants $\lambda_{1},\dots,\lambda_{r}$ such that $r=t_{n},\lambda_{1}+\dots+\lambda_{r}=1$, $f_{i}\in S_{n}$ for each $i$, and where there is some $k$ where if $A=\lambda_{1}\sigma_{f_{1}}+\dots+\lambda_{r}\sigma_{f_{r}}$, then $A^{k}=N_{n}$?

If the exact values of $t_{n}$ are difficult to evaluate, then I would like to know good upper and lower bounds for $t_{n}$.