Let's say we have a matrix $A$. It is a sparse matrix with entries less than one for example adjacency matrix of a sparse graph. i.e. a social network.
We derive the matrix $B$ from $A$ as follows: $B=A^2 (1/c)$; $c=\sum_{i,j} A^2(i,j)$ is a normalizing constant to make all the entries of $B$ add to 1.
I am looking for an equation like: $B^t\leq f(t,B) B$, where $f(t,B)$ has the form $f(t,B)=poly(t)g(B)$ basically we don't want $f(t,B)$ to be a computationally costly function (Matrix multiplication is) . Do we know such bounds?
Let $A=[a_{i,j}]\in M_n(\mathbb{R})$ st $0\leq a_{i,j}\leq M$ and $U$ be the matrix with entries $1$. Let $B\leq C$ denote for every $i,j$, $b_{i,j}\leq c_{i,j}$.
Then $A^t\leq n^{t-1}M^t U$.
Your proposed bound is polynomial (and therefore not exponential) in $t$ and, consequently, does not work.