The transition matrix for a $d$-regular digraph (with no multi-edges but can have self-loops) is a matrix with $d$ non-zero entries of values $\frac{1}{d}$ in each row.
Given such an $m \times m$ matrix $A$, we would like to find the set of the maximum values in $A^n$ for all positive $n$. Suppose the size of the distinct values in that set is $r$. It is possible that $r$ is infinite. Our algorithm should be able to detect this case as well.
Does there exist an algorithm that runs in time $O(poly(d,m,r))$ that outputs the values of the maximum elements in $A^n$ for all $n$?
We would really want to make the running time independent from $n$. The usual $n$th power of matrix algorithm is overkill.
To make things more clear:
Let the max value of $A^i$ be $m_i$. We want the result set $S$ to consist of all pairs of $(i,m_i)$ such that all $m_i$ are distinct and only the minimum $i$ associated with $m_i$ is kept.
Update: Since the value of $A^n$ is infeasible in general. We save the index pair of $(r,c)$ where $A^n[r,c]$ is the maximum for step $n$. $S$ consists of $(i,r,c)$ triplets.