Lifespan in a Primitive Boolean Linear Dynamical System

Yaokun Wu, Yinfeng Zhu


Let $\mathcal F$ be  a set of $k$ by $k$ nonnegative matrices such that every "long" product of elements of $\mathcal F$ is positive.   Cohen and Sellers (1982) proved that, then,  every such product of length $2^k-2$ over $\mathcal F$ must be positive. They suggested to investigate the minimum size of such $\mathcal F$ for which there exists a non-positive  product of length $2^k-3$ over $\mathcal F$ and they constructed one example of size $2^k-2$.  We construct one of size $k$ and further discuss relevant basic problems in the framework of Boolean linear dynamical systems. We also formulate several primitivity properties for general discrete dynamical systems.


Boolean lattice; Hitting time; Non-homogeneous matrix product; Phase space; Primitive index; Wielandt matrix

Full Text: PDF