Given a non-negative matrix $A$, we call $A$ primitive if $A^k$ has all strictly positive entries with some $k>0$. Given primitive $A$, is there relation between smallest $k$ such that $A^k>0$ and $rank(A)$?
If $A\in\Bbb Z_{\geq0}^{n\times n}$ with $\max_{i,j}A_{ij}\leq M$, is $log(k(A))\leq(log(rk(A)))^{c_M}$ with some $c_M\geq1$?
Is there a geometric meaning to smallest $k$?
Denote this smallest $k$ by $k(A)$. At least, one has (obvious) $$({\rm rk}(A)=1)\Longrightarrow(k(A)=1).$$ On the other hand, Wielandt's Theorem says that for every primitive matrix $A\ge0_n$, one has $$k(A)\le n^2-2n+2.$$ This bound is optimal: equality holds for the matrix $A=P+E_{n2}$, where $P$ is the matrix of the permutation $i\mapsto i+1$, modulo $n$, and $E_{rs}$ is the matrix with entries $\delta_i^r\delta_j^s$ at positions $(i,j)$.
Do you expect the general formula $$k(A)\le{\rm rk}(A)^2-2{\rm rk}(A)+2\quad?$$ Should be nice.
