Could matrix powers be bounded?

Question

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?

The form of the bound that you wrote is not very restrictive. It doens't prevent choosing $f(t,B)=B^{t-1}$. — user647486, Apr 28 '19 at 13:06
See, this comment. The method described there allows you to compute the powers and incidentally bound them. — user647486, Apr 28 '19 at 13:18

score 1 · Answer 1 · answered May 08 '19 at 15:59

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.

Could matrix powers be bounded?

1 Answers1