# Weak ergodicity of nonhomogenous products of 0-1 matrices

Here is a question which probably has a negative answer, but I couldn't find any literature directly on it.

Let $(A_n)$ be a sequence of rectangular 0-1 matrices (that is, the entries are restricted to zero or one), such that for all $n$, the matrix product $A_n A_{n-1}$ makes sense. Suppose in addition that the following hold:

(i) there is a bound on the dimensions (sizes) of all the $A_n$;

(ii) for all $k$, there exists $N(k)$ such that the product $$A_{N(k)+k}\cdot A_{N(k) + k-1} \cdot \dots \cdot A_{k+1}$$ is strictly positive (meaning, every entry is nonzero);

(iii) every $A_n$ has at least one nonzero entry in each of its columns and in each of its rows.

Then is it true that the sequence $(A_n)$ is weakly ergodic?

That is, for every $k$, given any two states at time $k$, call them $i$ and $j$ (corresponding to the transition by $A_{k+1}$), and given $\epsilon > 0$, there exists $K > k$ such that for every state $m$ at time $K$, the number of paths from $i$ to $m$ divided by the number of paths from $j$ to $m$ is within $\epsilon$ of a real number depending only on $i$ and $j$.

[This is the translation to weak ergodicity in the non-stochastic case. It is really a statistical criterion about numbers of paths joining states $\dots$. It is also necessary and sufficient for a dimension group with Bratteli diagram implemented by the sequence of matrices to be simple and have unique trace.]

It $is$ true if $N(k)$ is bounded above (use Birkhoff metric and the corresponding contraction theorem) or if the matrices are all square of size two (since then, the matrices satisfying (iii) have determinant plus or minus one or are all ones). The theorem is also true if infinitely many $A_n$ have rank one (trivial), or a bit less trivially, if there is a telescoping so that infinitely many of the telescoped products have rank one. Also sufficient is a condition like $N(k) = o(\ln k)$, but this is far from what I want.

There is almost certainly a reduction to the case that the $A_n$ are all square, so (i) is probably a red herring, that is, we just assume they are all square of the same size. The 0-1 condition can be replaced by having uniform upper and lower bounds on the nonzero entries of the nonnegative matrices $A_n$.

There is a considerable amount of literature on similar-sounding problems (e.g., variations on Wolkowitz' theorem, where it is assumed that the $A_n$ and their products are at least primitive or similar, or the $A_n$ are column- or row-stochastic or at least have a strictly positive column, ...), but this one seems far harder, and thus more likely to fail. If there is a counter-example, I would like to see minimal strengthening hypotheses so that there is a positive (!) answer.

I think there's a counterexample to the statement in the generality given here (with 6*6 matrices).

There are 2 matrix types in the counterexample:

$$C=\begin{pmatrix} 1&1&0&0&0&0\\ 1&1&0&0&0&0\\ 0&0&1&1&0&0\\ 0&0&1&1&0&0\\ 0&0&0&0&1&0\\ 0&0&0&0&0&1\end{pmatrix} \text{ and } D=\begin{pmatrix} 1&1&0&0&1&0\\ 1&1&0&0&1&0\\ 0&0&1&1&0&1\\ 0&0&1&1&0&1\\ 0&0&1&1&0&0\\ 1&1&0&0&0&0 \end{pmatrix}.$$

I'm thinking of 1 and 2 as a communicating class; 3 and 4 as another communicating class; and 5's as being a wormhole from 1's and 2's to 3's and 4's; and 6's as being a wormhole from 3's and 4's to 1's and 2's.

The sequence I have in mind is something like $\ldots A_nA_{n-1}\ldots A_1=\ldots DC^{1600}DC^{800}DC^{400}DC^{200}DC^{100}$. It has the mixing property because for any $k$, choosing $N(k)$ large enough that $A_{k+N(k)}\ldots A_{k+1}$ contains two $D$'s satisfies the property.

Next, I claim that it doesn't satisfy weak ergodicity. In particular, I want to say that the large majority of paths starting in the $\{1,2\}$ class stay in that class forever.

Let $t_1,t_2,t_3,\ldots$ be the times with the $D$'s. Label the equivalence classes as $1=\{1,2\}$; $2=\{3,4\}$; $3=\{5\}$ and $4=\{6\}$ [ apologies for the notation ].Let $Z^{(m,n)}_{ij}$ be the 4*4 matrix giving the number of paths from an element of type $i$ at time $m$ to an element of type $j$ at time $n$.

Then $Z^{(t_j,t_{j+1})}$ looks like $$\begin{pmatrix} 2^{2^j}&1&2^{2^j}&0\\ 1&2^{2^j}&0&2^{2^j}\\ 0&1&0&0\\ 1&0&0&0 \end{pmatrix}$$ When you take products of these, you never get a substantial flow from the 1 class to the 2 class.

• What a neat example! (Minor correction: five, not two, $D$s are required to make the product strictly positive.) I had been flailing around with powers of upper triangular, followed by lower triangular matrices. It does suggest other questions, e.g., if the matrices are restricted to full rank, or even if they are unimodular, then perhaps weak ergodicity holds? – David Handelman Jan 9 '14 at 15:12