Vanishing zeroes in matrix powers For a matrix $M\in\mathbb{R}^{n\times n}_{\geq 0}$ with nonnegative entries, we define $m$ as the smallest positive integer such that all the entries of $M^m$ are strictly positive (if there is one). 
What is, as a function of $n$, the maximum possible (finite) value of $m$ over all possible choices of $M$?
My attempt: By taking the matrix $M(i,i+1)=M(1,1)=M(1,n)=1$ else $M(i,j)=0$ I got $m=6,12,18$ for $n=4,7,10$. So it seems that $m=2n-2$?
I added the "probability" tag because Markov chain convergence was the motivation.
 A: This is a combination of the answer Gerry Myerson gave on MSE, the paper linked there, and the comments here.
The largest possible minimum $m$ is $(n-1)^2+1 = n^2-2n+2$. This was proved by Wielandt, although this proof was not published. He claimed the result in H. Wielandt, “Unzerlegbare, nicht negative Matrizen,” Math. Z., 52, 642–648 (1950). There is an essentially unique matrix showing that this is sharp, although there are many examples built from similar ideas showing that the minimum $m$ is $\Omega(n^2)$. 
$$\begin{pmatrix}0 & 0  & \cdots & 0 & 1 \newline 1 & 0 & \cdots & 0 & 0 \newline \epsilon & 1 & \cdots & 0  & 0 \newline  \vdots & \vdots & \ddots & \vdots \newline 0 & 0 & \cdots & 1 & 0 \end{pmatrix}$$
Except for the $\epsilon$, this is a circulant matrix. 
For example, let $n=8$, and set $\epsilon=1$. Here is the $40$th power:
$$\begin{pmatrix}1 & 0 & 0 & 1 & 5 & 10 & 10 & 5 \newline 5 & 1 & 0 & 0 & 1 & 5 & 10& 10 \newline 15 & 5 & 1 & 0 & 1 & 6 & 15 & 20 \newline 20 & 10 & 5 & 1 & 0 & 1 & 6 & 15 \newline 15 & 10 & 10 & 5 & 1 & 0 & 1 & 6\newline 6& 5& 10 & 10 & 5 & 1 & 0 & 1 \newline 1 & 1 & 5 & 10 & 10 & 5 & 1 & 0 \newline 0 & 0 & 1 & 5 & 10 & 10 & 5 & 1  \end{pmatrix}$$
Here is some Mathematica code you can use to animate the powers of the matrix.
wmat[n_] := Table[If[Mod[i - j, n] == 1 || (i == 2 && j == 0), 1, 0], {i, 0, n - 1}, {j, 0, n - 1}]
ListAnimate[Table[TableForm[MatrixPower[wmat[8], i]], {i, 1, 50}]]

A: There is an example in the book "Essentials of Stochastic processes" of Durrett, which shows that, in general, $m$ need not be equal to $2n-2$ (it is Example 4.5 of the chapter devoted to Markov chains, Durrett calls this example "Mathematician's nightmare"). The state space of the chain is $\{0,1,\ldots,14\}$, from $0$ it jumps to $5,9,14$ with equal probabilities, from other states $x>0$ it always jumps to $x-1$. It is then claimed that $m$ is at least $30$ for this chain (I didn't do the calculations myself, though).
