% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P4.36}{22(4)}{2015} \usepackage{mathbbold} \usepackage{amsfonts} \usepackage{pict2e} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} \usepackage{tikz} \usetikzlibrary{arrows,shapes,positioning} \usetikzlibrary{decorations.markings} \tikzstyle arrowstyle=[scale=1] \tikzstyle{bk_circle}=[circle,draw=black!100,very thick,inner sep=0pt,minimum size=7mm] \tikzstyle{b_circle}=[circle,fill=blue!40,inner sep=0pt,minimum size=5mm] \tikzstyle{r_circle}=[circle,fill=red!40,inner sep=0pt,minimum size=5mm] %\tikzstyle{tiny_circle}=[thick,circle,draw=white,inner sep=0pt,minimum size=2mm] \tikzstyle{tiny_circle}=[thick,circle,draw=black,inner sep=0pt,minimum size=2mm] \tikzstyle{blank}=[inner sep=0pt,minimum size=7mm] \tikzstyle{tiny_blank}=[circle,draw=black!0,inner sep=0pt,minimum size=3mm] \tikzstyle{bk_line}=[draw,-,thin] \tikzstyle{curve}=[draw,-,thin,out=70,in=110] \tikzstyle{directed}=[postaction={decorate,decoration={markings,mark=at position .65 with {\arrow[arrowstyle]{stealth}}}}] % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins \DeclareMathOperator{\Ar}{A} %%% Arc Set \DeclareMathOperator{\Ve}{V} %%% Vertex Set \DeclareMathOperator{\SET}{Set} %%% Set \DeclareMathOperator{\PS}{\mathcal{PS}} %%% Phase Space \DeclareMathOperator{\Mat}{Mat} %%% matrix semigroup \DeclareMathOperator{\ld}{ld} %%% longest duration \DeclareMathOperator{\sd}{sd} %%% shortest duration \DeclareMathOperator{\gp}{g} %%% strongly primitive exponent \DeclareMathOperator{\gpp}{g'} %%% primitive exponent \DeclareMathOperator{\gppp}{g''} %%% weakly primitive exponent \DeclareMathOperator{\Prim}{Prim} %%primitive set \DeclareMathOperator{\SL}{StL} \DeclareMathOperator{\WSL}{WStL} \DeclareMathOperator{\MC}{MC} \DeclareMathOperator{\M}{M} % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Lifespan in a strongly primitive \\Boolean linear dynamical system\thanks{This work was supported by the NSFC grant 11271255.}} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{ %Dagwood Remifa\thanks{Supported by NASA grant ABC123.}\\ %\small Department of Inconsequential Studies\\[-0.8ex] %\small Solatido College\\[-0.8ex] %\small North Kentucky, U.S.A.\\ %\small\tt remifa@dis.solatido.edu\\ %\and Yaokun Wu \qquad Yinfeng Zhu\\ \small Department of Mathematics and MOE-LSC \\[-0.8ex] \small Shanghai Jiao Tong University\\[-0.8ex] \small Shanghai, 200240, China\\ \small\tt \{ykwu,fengzi\}@sjtu.edu.cn } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Apr 18, 2015}{Nov 8, 2015}{Nov 27, 2015}\\ \small Mathematics Subject Classifications: 05C50, 15B34, 37F20, 60J10, 93C55} \begin{document} \maketitle \begin{abstract} 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. % keywords are optional \bigskip\noindent \textbf{Keywords:} discrete dynamical system, hitting time, lexicographic order, non-homogeneous matrix product, phase space, strong primitivity, primitivity, weak primitivity, Wielandt matrix. \end{abstract} \section{Strongly primitive matrix sets} Let $A$ be a set. A {\bf word} $w$ over $A$ is a sequence of elements of $A,$ say $w=a_1\cdots a_\ell$ where $a_1, \ldots a_\ell\in A.$ For any $a\in A$, we write $|w|_a$ for the number of occurrences of $a$ in the sequence $w$. We call $\ell$ the length of the word $w$, which surely equals $\sum_{a\in A}|w|_a$ and will be denoted by $|w|.$ We call $w$ a nonempty word provided $|w|>0.$ The free semigroup generated by $A$, in symbols $A^+$, has all the nonempty words over $A$ as its elements and has string concatenation as the semigroup multiplication. For any nonnegative integer $k$, we write $[k]$ for the set $\{1, \ldots, k\}. $ Note that $[0]=\emptyset.$ Pick a positive integer $k$. We use the notation $\Mat_k$ to denote the multiplicative semigroup of all $k\times k$ nonnegative matrices. Let ${\mathcal M}$ be a set of $k\times k$ nonnegative matrices. For any word $w=w_1\cdots w_\ell\in {\mathcal M}^\ell\subseteq {\mathcal M}^+$, we set ${\mathcal M}_w$ to be the product $w_1\cdots w_\ell$ in $\Mat_k$ and call it a {\bf product over $\mathcal M$ of length $\ell.$} The map from ${\mathcal M}^+$ to $\Mat_k$ that sends $w $ to ${\mathcal M}_w$ is a semigroup morphism and the image of it is called the {\bf semigroup of ${\mathcal M}$}. Take a map $\verb"t"$ from $\mathcal M$ to nonnegative integers. Define the length of $\verb"t"$ be be $|\verb"t"|=\sum_{M\in {\mathcal M}} \verb"t"(M).$ When $|\verb"t"|>0,$ the {\bf Hurwitz product of ${\mathcal M}$ of type $\verb"t"$} \cite{FF10} is the matrix \[{\mathcal M}^{\verb"t"}:=\sum_{w}{\mathcal M}_{w},\] where the sum runs over all those sequences $w\in {\mathcal M}^+$ such that $|w|_M =\verb"t"(M)$ holds for every $M\in {\mathcal M}$. The {\bf strong primitivity exponent of ${\mathcal M}$}, denoted by $\gp ({\mathcal M})$, is the minimum positive integer $\ell$ such that all products over ${\mathcal M}$ of length at least $\ell$ is positive; the {\bf primitivity exponent of ${\mathcal M}$}, denoted by $\gpp ({\mathcal M})$, is the minimum positive integer $\ell$ such that there exists a positive product over ${\mathcal M}$ of length $\ell$; and the {\bf weak primitivity exponent of ${\mathcal M}$}, denoted by $\gppp ({\mathcal M})$, is the minimum positive integer $\ell$ such that we can find a positive Hurwitz product of length $\ell$ over ${\mathcal M}$. If the relevant positive integer does not exist, our convention is to set the exponent to be $\infty.$ It is clear that \[\gp ({\mathcal M})\geq \gpp ({\mathcal M})\geq \gppp ({\mathcal M}).\] We say that ${\mathcal M}$ is {\bf strongly primitive}, {\bf primitive}, or {\bf weakly primitive}, respectively, if $\gp ({\mathcal M})<\infty$, $\gpp ({\mathcal M})<\infty$, or $\gppp ({\mathcal M})<\infty$. The weak primitivity property was introduced by Fornasini and Valcher \cite{FV98} and its rich properties and applications were further developed in \cite{BG09, BK03, BM14, FV06,Ole02, Protasov13}. Olesky, Shader and Van den Driessche \cite[Theorem 7]{Ole02} showed for every positive integer $d$ that \[\max \{\gppp ({\mathcal M}):\ {\mathcal M} \in {\Mat_k\choose d}\text{ is weakly primitive}\} = \Theta (k^{d+1}).\] A matrix set ${\mathcal M} \in {\Mat_k\choose d}$ is {\bf irreducible} provided \[\cup_{M\in {\mathcal M}}\{(i,j)\in ([k]\setminus A)\times A:\ M(i,j)\not= 0\}\not= \emptyset\] for every $A\in 2^{[k]}\setminus \{\emptyset, [k]\}.$ If ${\mathcal M} \in {\Mat_k\choose d}$ is irreducible and no matrix of $\mathcal M$ contains a zero row, Protasov \cite[Theorem 2]{Protasov13} found a polynomial time algorithm to decide if ${\mathcal M} $ is weakly primitive. The concept of primitivity property for matrix sets was pioneered by Protasov and Voynov \cite{PV} and has attracted quite some attention \cite{AlAl, BJO15, PV,V13}. Blondel, Jungers and Olshevsky \cite[Theorem 6]{BJO15} proved that recognizing primitivity is decidable but NP-hard as soon as there are three matrices in the set. They \cite[Theorem 10]{BJO15} also showed that the primitivity exponent of a primitive $k\times k$ matrix set $\mathcal M$ could be superpolynomial in the size of the instance $k^2|\mathcal M|$. A nonnegative matrix is {\bf essential} if it has no zero lines. Protasov and Voynov \cite{PV} designed a polynomial time algorithm to test if a given irreducible set of essential matrices is primitive. Voynov discovered that the primitivity exponent of a primitive $k\times k$ essential matrix set is $O(k^3)$ \cite{BJO15,V13}. As pointed out by Cohen and Sellers \cite[p. 187]{cs82}, a strongly primitive matrix set is the combinatorial part of Hajnal's \cite{Hajnal1} concept of ergodic set, and is relevant to inhomogeneous Markov chains, automata, mathematical demography and linear switching systems \cite{FV,Hajnal,H02,HeyCohen,Ole02,Paz,WS12}. It also worths mentioning that strong primitivity property plays a crucial role in approximation theory and functional analysis such as solvability of refinement functional equations with column stochastic matrices \cite{CDM, MP89} and the convergence of subdivision schemes with nonnegative masks \cite{Melkman, YWang, Zhou}. In 1982, Cohen and Sellers \cite[Theorem 1, Theorem 2]{cs82} established the following result. \begin{theorem}[Cohen-Sellers] Let ${\mathcal M}$ be a strongly primitive set of $k\times k$ nonnegative matrices. Then \begin{equation}\gp (\mathcal M)\leq 2^k-2.\label{eq:Peres}\end{equation} Moreover, one can choose a set ${\mathcal M}$ of size $2^k-2$ to guarantee the equality in Eq.~\eqref{eq:Peres}. \label{thm:Prabhu} \end{theorem} Theorem~\ref{thm:Prabhu} tells us that the strong primitivity exponent $\gp (\mathcal M)$ can grow exponentially in dimension $k.$ To understand the strong primitivity property, an important question arising in this context is whether the strong primitivity exponent $\gp (\mathcal M)$ can grow sub-exponentially with respect to the size of the instance $k^2|\mathcal M|$. For any $k\geq 2,$ the first main result of this paper, Theorem~\ref{thm:fabulous}, asserts that there exists a size-$k$ strongly primitive set $\mathcal M$ of $k\times k$ (essential) matrices satisfying $\gp (\mathcal M)= 2^k-2$, thereby giving a positive answer to the previous question. This may be a sign that the strong primitivity property can hardly be decided in polynomial time. Cohen and Sellers concluded the paper \cite{cs82} with the question on determining the smallest size of $\mathcal M$ for which equality is valid in Eq.~\eqref{eq:Peres}. Thus, our Theorem~\ref{thm:fabulous} is also an effort towards answering their question. For each nonnegative matrix $M$, we can replace all its positive entries by $1$ and thus form a $(0,1)$ matrix $\overline{M}$. For $M^t$ to be a positive matrix, it is equivalent to have $\overline{M}^t$ to be the all ones matrix according to the Boolean algebra operation. With this in mind, one can check that all the properties addressed above on nonnegative matrices are indeed properties on Boolean matrices. In mathematics, especially in various kinds of representation theory, to understand the structure of an object, we often let it act on other objects and then turn to the study of this action. In this paper and its subsequent work \cite{WWX,WXZ, WXZ15}, we suggest a genetic approach to understand the structure of a Boolean matrix set or even Boolean tensor set, in which we recast everything in the language of phase spaces. This is to let the Boolean matrices act on Boolean row vectors and then study the corresponding Boolean linear dynamical systems. We believe that this approach leads us to a series of fundamental mathematics structures and problems. In particular, this approach suggests us to consider many natural problems which, at first sight, may look to be far away from the above primitivity problems for nonnegative matrix sets. In \S\ref{sec:Cohen}, we address the above-mentioned question of Cohen and Sellers in the framework of Boolean linear dynamical systems. We hope that the phase space approach adopted in \S\ref{sec:Cohen} will make some readers interested enough to keep reading into \S\ref{sec:life} where we set forth our formal description of primitive discrete dynamical systems, including a definition of phase space. In \S\ref{sec:ergodic} we discuss several aspects of strongly primitive essential Boolean linear dynamical systems and try to show that it is a good playground for mathematicians. The last section, \S\ref{sec:TANGENT}, is devoted to the proofs of those results claimed in \S\ref{sec:life} and \S\ref{sec:ergodic}. \section{The question of Cohen and Sellers}\label{sec:Cohen} A {\bf digraph} $D$ consists of its vertex set $\Ve(D)$ and its arc set $\Ar (D)$ where $\Ar (D)\subseteq \Ve (D)\times \Ve (D)$. A {\bf walk} in a digraph $D$ of length $k$ is a sequence of vertices $v_1, \ldots, v_{k+1}$ such that $(v_{i}, v_{i+1})\in \Ar (D)$ for all $i\in [k]$. We often write this walk as $v_1\to v_2\to \cdots \to v_k\to v_{k+1}$ and call this walk a {\bf closed walk} when $v_1=v_{k+1}$. A {\bf path} in a digraph is a walk without repeated vertices. Every arc is a walk of length 1 but not necessarily a path. A digraph $D$ is {\bf transitive} provided $u\to w$ is an arc in $D$ whenever $u\to v \to w$ is a walk in $D.$ A digraph $D$ is {\bf acyclic} if it has no closed walk of positive length. Recall that a {\bf partially ordered set} (poset) is just an acyclic and transitive digraph, while its arc set is typically called a {\bf partial order} on the vertex set. A {\bf totally ordered set}, also known as a {\bf linearly ordered set}, is a partially ordered set where exactly one of $u\to w$ and $w\to u$ is an arc for every two distinct vertices $u$ and $w.$ The arc set of a totally ordered set is called a {\bf total order} or a {\bf linear o rder}. Fix a positive integer $k$. Let $\SET _k$ denote $2^{[k]}\setminus \{\emptyset \}$. We could naturally identify $\SET _k$ with the set of nonzero Boolean row vectors (binary string) of length $k$, viewing each $A\in \SET_k$ as the $(0,1)$ string of length $k$ whose $i$th position is occupied by a $1$ if and only if $i\in A.$ Let ${\mathcal M}$ be a set of $k\times k$ Boolean matrices. We write $\mathbb{P}_{\mathcal M}$ for the digraph with vertex set $\SET_k$ of which $A\rightarrow B$ is an arc if and only if $\{A, B\}\in {\SET_k\choose 2}$ and there exists a matrix $M$ from the semigroup of ${\mathcal M}$ such that $AM=B.$ Let $\gp (\mathcal M)$ be the length of a longest path in $\mathbb{P}_{\mathcal M}$. We call ${\mathcal M}$ {\bf strongly primitive} provided $\mathbb{P}_{\mathcal M}$ is acyclic and $[k]$ is the unique sink vertex in $\mathbb{P}_{\mathcal M}$. If ${\mathcal M}$ is strongly primitive, $\gp (\mathcal M)$ is known as the {\bf strong primitivity exponent} of ${\mathcal M}$. Take $k\geq 2$ and $i\in [k]$. We define $M_{k,i}$ to be the $k\times k$ Boolean matrix whose $(p,q)$-entry is $1$ if and only if $p=i$ or $q=i$ or $p=q\in [i-1]$. We display some examples below to illustrate the definition. \[M_{6,1}=\begin{pmatrix}\bf{1}&\bf{1}&\bf{1}&\bf{1}&\bf{1}&\bf{1}\\\bf{1}&0&0&0&0&0\\ \bf{1}&0&0&0&0&0\\ \bf{1}&0&0&0&0&0\\ \bf{1}&0&0&0&0&0\\ \bf{1}&0&0&0&0&0\end{pmatrix}\, M_{6,4}=\begin{pmatrix}\bf{1}&0&0&\bf{1}&0&0\\ 0&\bf{1}&0&\bf{1}&0&0\\ 0&0&\bf{1}&\bf{1}&0&0\\ \bf{1}&\bf{1}&\bf{1}&\bf{1}&\bf{1}&\bf{1}\\ 0&0&0&\bf{1}&0&0\\ 0&0&0&\bf{1}&0&0 \end{pmatrix}\, M_{6,6}=\begin{pmatrix}\bf{1}&0&0&0&0&\bf{1}\\0&\bf{1}&0&0&0&\bf{1}\\ 0&0&\bf{1}&0&0&\bf{1}\\ 0&0&0&\bf{1}&0&\bf{1}\\ 0&0&0&0&\bf{1}&\bf{1}\\ \bf{1}&\bf{1}&\bf{1}&\bf{1}&\bf{1}&\bf{1} \end{pmatrix}\] Let $\phi_k$ be the bijection from $\SET_k$ to $[2^k-1]$ that sends $A\in \SET_k$ to the integer \begin{equation}\phi_k (A):=\sum_{i\in A}2^{k-i}. \label{eq:memorandum} \end{equation} The {\bf lexicographic order} on $\SET_k$ is the total order $\pi_k$ in which the following holds: \begin{equation} \phi_k^{-1}(1)\rightarrow \phi_k^{-1}(2)\rightarrow \cdots \rightarrow \phi_k^{-1}(2^k-1)=[k]. \label{eq:GREGORY}\end{equation} The next result not only improves the bound of the matrix set size in Theorem~\ref{thm:Prabhu} from $2^k-2$ to $k$, but also indicates the special role of the lexicographic order $\pi_k$. \begin{theorem}\label{thm:fabulous} Take $k\geq 2$ and let ${\mathcal M_k}=\{M_{k,1}, \ldots, M_{k,k}\}$ be a size-$k$ set of $k\times k$ Boolean matrices. Then $\gp ({\mathcal M_k})=2^k-2$ and $\mathbb{P}_{\mathcal M_k}$ is the lexicographic order on $\SET_k$ as given in Eq.~\eqref{eq:GREGORY}. \end{theorem} \begin{proof} Pick $i\in [k]$ and $A\in \SET_k$. If $i\in [k]\setminus A$, we can check that $AM_{k,i} =\{i\}\cup ([i-1]\cap A)$ and thus $\phi_k (A)< \phi_k (AM_{k,i})$; if $i\in A$, we can check that $AM_{k,i} =[k]$ and thus $\phi_k (A)\leq \phi_k (AM_{k,i})$ where equality holds if and only if $A=[k]$. Especially, if $s\in [2^k-2]$ and $i=\max \{j\in [k]:\ j\notin \phi_k^{-1}(s)\}$, then $\phi_k^{-1}(s)M_{k,i}=\phi_k^{-1}(s+1)$. We illustrate this with two examples below. \[\begin{pmatrix}* & *& *& 0 & \bf{1} & \bf{1}\end{pmatrix} \begin{pmatrix}\bf{1}&0&0&\bf{1}&0&0\\ 0&\bf{1}&0&\bf{1}&0&0\\ 0&0&\bf{1}&\bf{1}&0&0\\ \bf{1}&\bf{1}&\bf{1}&\bf{1}&\bf{1}&\bf{1}\\ 0&0&0&\bf{1}&0&0\\ 0&0&0&\bf{1}&0&0 \end{pmatrix} =\begin{pmatrix}* & *& *& \bf{1} & 0 & 0\end{pmatrix} \] \[\begin{pmatrix}* & *& *& * & * & 0\end{pmatrix}\begin{pmatrix}\bf{1}&0&0&0&0&\bf{1}\\0&\bf{1}&0&0&0&\bf{1}\\ 0&0&\bf{1}&0&0&\bf{1}\\ 0&0&0&\bf{1}&0&\bf{1}\\ 0&0&0&0&\bf{1}&\bf{1}\\ \bf{1}&\bf{1}&\bf{1}&\bf{1}&\bf{1}&\bf{1} \end{pmatrix} =\begin{pmatrix}* & *& *& * & * & \bf{1}\end{pmatrix}\] The above discussion implies that \[\phi_k^{-1}(1)\rightarrow \phi_k^{-1}(2)\rightarrow \cdots \rightarrow \phi_k^{-1}(2^k-1)=[k]\] is a path of length $2^k-2$ in $\mathbb{P}_{\mathcal M_k}$ and that the arcs in $\mathbb{P}_{{\mathcal M_k}}$ are all of the form $\phi_k^{-1}(s)\rightarrow \phi_k^{-1}(t)$ where $1\leq s1; \\ \frac{s}{2}, & \text{if } s\ \text{is even}. \end{cases}\] The renowned Collatz conjecture \cite{Lagarias} just asserts that $(S, f)$ is strongly primitive with $1$ being its black hole! \end{example} For a strongly primitive DDS $ \mathcal D=(S, \mathcal F)$ and every $s\in S,$ the {\bf longest duration} for $s$ is the length of a longest path from $s$ to the black hole of $\mathcal D$ and this length is denoted by $\ld (\mathcal D, s)$ or simply $\ld ( s)$. Similarly, we define the {\bf shortest duration} for $s$ to be the length of a shortest path from $s$ to the black hole of $\mathcal D$ and write it as $\sd (\mathcal D, s)$ or simply $\sd (s)$. The {\bf transient} ({\bf strong primitivity exponent}) of a strongly primitive system $(S, \mathcal F)$ is the minimum nonnegative integer $T$ such that every length $T$ walk in $\PS_{\mathcal F}$ ends at the black hole of $(S, \mathcal F)$, which we denote by $\gp (S, \mathcal F)$ or simply $\gp (\mathcal F)$. The {\bf hitting time} of a strongly primitive DDS $(S, \mathcal F)$ is the minimum nonnegative integer $T$ such that every $s\in S$ can reach the black hole in $T$ steps in $\PS_{\mathcal F}$, which we denote by $ \underline{\gp}(\mathcal D)$, or $\underline{\gp}(S, \mathcal F)$, or simply $\underline{\gp}(\mathcal F)$. In other words, \[\gp (\mathcal F)=\overline{\lim}_{s\in S}\ld (s), \ \ \underline{\gp}(\mathcal F)=\overline{\lim}_{s\in S}\sd ( s).\] If you view each vertex as a birth place and each directed path as the journey of life of someone with the black hole death, then $\gp (\mathcal F)$ is the longest life of any person while $\underline{\gp}(\mathcal F)$ is the minimum time elapsed in evolution until at least one person from each birth place will have died. Clearly, \begin{equation} \underline{\gp}(\mathcal F)\leq \gp (\mathcal F)\leq |S|-1.\label{Eq:HUMANITY}\end{equation} We will thus call $|S|-1 $ the {\bf absolute upper bound} of the life expectancy in $(S, \mathcal F)$. \begin{example} Let $S$ be the set of all nonnegative integers and let $f$ be the map which sends $i$ to $\max (0, i-1)$. Then $(S, f)$ is a strongly primitive DDS with infinite transient. \end{example} A {\bf pointed discrete dynamical system} $\mathcal D'=(\mathcal D, s)$ is a DDS $\mathcal D=(S, \mathcal F)$ together with a {\bf base point} $s\in S.$ Note that under function compositions the set $S^S$ forms a semigroup. For any word $w=w_1\cdots w_\ell\in \mathcal F^+$, $\mathcal F_w$ is the element of $S^S$ obtained by composing functions $w_1, \ldots, w_\ell$ from left to right in this order. The map from ${\mathcal F}^+$ to $S^S$ that sends $w\in \mathcal F^+$ to ${\mathcal F}_w\in S^S$ is a semigroup morphism and the image of it is called the semigroup of ${\mathcal F}$. We say that $w\in \mathcal F^+$ is a {\bf synchronizing word} for $\mathcal D'=(\mathcal D, s)$ if $\mathcal F_w$ maps all elements of $S$ to $s.$ The pointed DDS $\mathcal D'$ is {\bf primitive} provided it has a synchronizing word and the shortest length of such synchronizing words is the {\bf primitivity exponent} of $\mathcal D'$, denoted by $\gpp (\mathcal D')$. By taking $S=\SET_k$, $s=[k]$ and $\mathcal F\subseteq \Mat_k$, since matrix multiplication is nothing but the composition of linear maps, it is easy to see that our definition of primitivity property here is a generalization of the primitivity property of Boolean matrix set. This viewpoint on primitivity property may also support the observation \cite{AVG} that primitivity property and synchronizing property have close connections. \begin{example} Let $S$ be a nonempty set with $s\in S $, let $k=|S|$ and let $\mathcal F$ be a nonempty subset of $S^S$. Assume that the pointed DDS $\mathcal D'=((S, \mathcal F), s)$ is primitive. The famous \v{C}ern\'{y} conjecture \cite{Cerny,Volkov} says that there exists $s'\in S$ such that the primitivity exponent of $((S, \mathcal F), s')$ is at most $(k-1)^2$. If \v{C}ern\'{y} conjecture can be proved true, then we can deduce that the primitive exponent of $\mathcal D'$ is at most $(k-1)k$. \end{example} Take a positive integer $k.$ A map $f$ from $2^{[k]}$ to $2^{[k]}$ is a {\bf Boolean linear map on $2^{[k]}$} \cite{Grin,WXZ} provided \begin{itemize} \item $A^f\cup B^f= (A\cup B)^f$ for all $A, B\in [k]$, and \item $ \emptyset^f=\emptyset$. \end{itemize} A {\bf Boolean linear dynamical system} is a DDS of the form $(2^{[k]}, \mathcal F)$ where $\mathcal F$ is a set of Boolean linear maps on $2^{[k]}$. De Morgan defined the important concept of ``relation'' in mathematics. Closely related to this basic object is the hemimorphisms between Boolean algebras \cite[p. 45]{KRY}. The Boolean linear dynamical system is just a place for the compositions of hemimorphisms and is a special case of the general tropical linear dynamical system \cite{Butkovic,MNSS}. For any positive integer $k $ and a set of Boolean linear maps $\mathcal F$ on $2^{[k]},$ let us consider the pointed DDS $\mathcal D=((2^{[k]}, \mathcal F), \emptyset)$, which arises in considering the zero controllability of positive switched systems \cite{SV08}. It is NP-complete to decide if $\mathcal D$ is primitive and it is NP-hard to calculate $\gpp (\mathcal D)$ \cite{mortal}. The set of synchronizing words for $\mathcal D$ naturally corresponds to paths from $[k]$ to $\emptyset$ in the digraph $\PS_{2^{[k]}, \mathcal F}$. This observation leads to the fact that $\gpp(\mathcal D) \le 2^k-1$ whenever $\mathcal D$ is primitive. Like the problem of Cohen and Sellers, we define $\gamma '_k$ to be the smallest size of a set $\mathcal F$ of Boolean linear maps on $2^{[k]}$ which ensures $\gpp(\mathcal D) = 2^k-1$ and want to determine $\gamma '_k$. The next result says that $\gpp(\mathcal D)$ can grow sub-exponentially with respect to the size of the instance $k^2|\mathcal F|$. \begin{theorem}\label{thm:OCTO} It holds $\gamma '_k\leq k $ for every $k\geq 2.$ \end{theorem} There may exist many reasonable ways of extending the weak primitivity property of nonnegative matrix sets. We illustrate one of them here. Suppose the set $S$ is endowed with a poset structure $(S, \prec)$ and we say that $x$ is bigger than $y$ whenever $y\prec x$ in $(S, \prec)$. Take a map $\verb"t"$ from $\mathcal F$ to nonnegative integers and assume $|\verb"t"|>0$. We say that a pointed DDS $\mathcal D'=((S, \mathcal F), s)$ is {\bf weakly primitive of type $\verb"t"$} (with respect to $\prec$) if, for every $x\in S$, the set \[\{x^{\mathcal F_w}:\ w\in {\mathcal F}^+, |w|_u=\verb"t" (u), \forall u\in S\}\] has $s$ as the unique least upper bound in the poset $(S, \prec)$. The {\bf weak primitivity exponent} of a weakly primitive pointed DDS $\mathcal D'$ with respect to the partial order $\prec$ is the minimum positive integer $\ell$ such that $\mathcal D'$ is weakly primitive of type $\verb"t"$ for some function $\verb"t"$ with $|\verb"t"|=\ell$. The next section will be mainly concerned with the strong primitivity property. Let $\mathcal D=(S, \mathcal F)$ be a strongly primitive DDS. It turns out that the construction of $\mathbb{P}_{\mathcal M}$ in \S\ref{sec:Cohen} gives rise to an important poset structure now for studying strong primitivity property. That is, we can construct a partial order $\prec_{\mathcal D}$ on $S$ by setting $(x,y)\in \prec_{\mathcal D}$, also denoted by $x\prec_{\mathcal D} y$, if and only if $x\not=y$ and there is a path leading from $x$ to $y$ in $\PS_{\mathcal D}$. We write $\mathbb{P}_{\mathcal D}$ to stand for this poset $(S, \prec_{\mathcal D})$. It is not hard to see that every finite poset with a unique maximal element will arise in this way. Recall that a linear extension of a finite poset $(S, \prec)$ is a bijective map $\pi$ from $[|S|]$ to $S$ such that $i1$, namely we are interested in the dynamical behavior of those non-homogeneous products of matrices. Indeed, Protasov \cite{Protasov} explicitly suggested to estimate the parameter $\gp_{k,t}$, where \[\gp_{k,t}:=\max \{\gp (\mathcal F):\ \mathcal F\in\Prim_{k,t}\}.\] Analogously, we let \[\underline{\gp}_{k,t}=\max \{\underline{\gp}(\mathcal F):\ \mathcal F\in\Prim_{k,t}\},\] which is surely not greater than $\gp_{k,t}.$ We make the convention that the maximum over an empty set equals $-\infty$ and the minimum over an empty set is $+\infty$. In view of Theorem~\ref{thm:BELUGA}, we have the absolute upper bound \begin{equation}\underline{\gp}_{k,t}\leq (k-1)^2+1;\label{Eq:ROBOT}\end{equation} On the other hand, Eq.~\eqref{Eq:HUMANITY} gives the absolute upper bound \begin{equation} \gp_{k,t}\leq 2^k-2. \label{EQ:RHYTHM} \end{equation} Besides Eqs.~\eqref{Eq:ROBOT} and \eqref{EQ:RHYTHM}, very little is known about $\gp_{k,t}$ and $\underline{\gp}_{k,t}$. Let us mention that the effort to understand the behavior of $\gp_{k,t}$ and $\underline{\gp}_{k,t}$ from $t=1$ to $t>1$ is part of a nonparametric version of the following proposal of Hajnal \cite[p. 67]{Hajnal}: \begin{quotation} Discussions of Markov chains \ldots are generally restricted to the homogeneous case \ldots In particular, the ergodic properties have only been established in this case. It seems natural to consider to what extent these properties hold for non-homogeneous chains. \end{quotation} As recorded in Theorem~\ref{thm:Prabhu}, Cohen and Sellers \cite[Theorem 1]{cs82} already found Eq.~\eqref{EQ:RHYTHM}. Upon this discovery, they suggested to estimate the parameter $\gamma_k,$ where \[\gamma_k:=\min \{t:\ \gp_{k,t}= 2^k-2 \}.\] Due to Eq.~\eqref{Eq:ROBOT}, we can accordingly define \[\beta_k:=\max \{t:\ \underline{\gp}_{k,t}= (k-1)^2+1\}.\] The parameters $\beta$ and $\gamma$ indicate the extremal size of the strongly primitive matrix sets attaining the absolute upper bounds. In particular, the parameter $\gamma_k$ tells you how much freedom you will need for the possibility of living as long as the absolute upper bound for a strongly primitive essential Boolean linear dynamical system. Pick $k\geq 2.$ Cohen and Sellers \cite[Theorem 2]{cs82} showed that you will need at most $2^k-2$ operators to produce a strongly primitive essential Boolean linear system on $\SET_k$ where you can find someone with a life of maximum possible length, namely $\gamma_k\leq 2^k-2$. By Theorem~\ref{thm:fabulous}, we can formulate the following improvement, namely, to guarantee a lifespan achieving the absolute upper bound, much less freedom will already do the job! \begin{theorem}\label{thm:CONTROLLABILITY} For every integer $k\geq 2,$ $\gamma_k\leq k$ holds. \end{theorem} We can check that $\gamma_2=1, \gamma_3=2, \gamma_4=3, \gamma_5\in \{2, 3, 4\}$ \cite{WWX}. It is not clear if $\gamma_k\leq k-1$ holds for all $k\geq 2$. We still lack some technique to yield a nontrivial lower bound of $\gamma_k$ and we even do not know if \[ \gamma_2\leq \gamma_3\leq \gamma_4 \leq\cdots \] is valid. Take $k\geq 2$ and let $\pi=(\SET_k, <_{\pi})$ be a total order on $\SET_k.$ We say that a set $\mathcal M$ of essential maps on $\SET_k$ is {\bf compatible} with $\pi$ if for every $A\in \SET_k\setminus \{ [k] \}$ and every $M\in \mathcal M$, it holds \[ A <_{\pi} AM, \] namely, if $\pi$ is a linear extension of the poset $\mathbb{P}_{\mathcal M}.$ We define $\MC^{\pi}$ to be the set of primitive matrices of order $k$ which are compatible with $\pi$. It is easy to see that all subsets of $\MC^\pi$ belong to $\Prim_k $ and a set $\mathcal M$ of essential maps on $\SET_k$ is compatible with $\pi$ if and only if $\mathcal M\subseteq \MC^{\pi}$. We may think of the total order $\pi$ as some kind of given ranking and then we want to understand the lifespan in a world where such a ranking is respected. This leads us to the parameter \[\gp (\pi):=\gp (\MC^{\pi}),\] which is $\max \gp (\mathcal M)$ where $\mathcal M$ runs through all sets of essential maps on $\SET_k$ which are compatible with $\pi$, and, for any positive integer $t$, the parameter \[\gp _t(\pi):=\max \{\gp (\mathcal M) :\ \mathcal M\in {\MC^{\pi}\choose t}\}.\] In addition, let \[\gamma (\pi):=\min \{t\geq 1:\ \gp _t(\pi)=2^k-2\},\] which is the minimum number of choices a linear world should possess to produce a life trajectory $\pi$. This parameter is interesting as we have \begin{equation}\gamma_k=\min _\pi \gamma (\pi), \label{eq:CHRISTIAN}\end{equation} where $\pi$ runs through all total orders on $\SET_k.$ The {\bf broken Boolean lattice ${\bf B}_k=(\SET_k, \subsetneq )$} is the poset on $\SET_k$ where $A$ is said to be less than $B$ if and only if $A$ is a proper subset of $B,$ namely $A\subsetneq B.$ \begin{theorem} \label{eq:SHANNON} Take $k\geq 2$ and let $\pi$ be a total order on $\SET_k.$ Then the following are equivalent. \begin{itemize} \item[(i)] $\gamma (\pi)<\infty$. \item[(ii)] $\pi$ is a linear extension of the broken Boolean lattice ${\bf B}_k$. \item[(iii)] $\gamma (\pi)\leq 2^k-3$. \end{itemize} \end{theorem} When $k=2,$ Eq.~\eqref{eq:GREGORY} becomes \[01\to 10\to 11,\] and so $\pi_2$ coincides with $\mathbb{P}_{\{f\}}$ for \[f:=\begin{pmatrix}\bf{1}&\bf{1} \\ \bf{1}& 0 \end{pmatrix}.\] This means that $\gamma (\pi_2)=1.$ \begin{theorem} \label{eq:IGOR} Let $k$ be an integer greater than 2 and let $\pi_k$ be the lexicographic order on $\SET_k$. Then $\gamma (\pi_k)=k.$ \end{theorem} To get a better bound than that of Theorem~\ref{thm:CONTROLLABILITY}, by virtue of Eq.~\eqref{eq:CHRISTIAN}, we should expect the existence of a total order $\tau$ on $\SET_k$ such that $\gamma (\tau) | A|$ and we write $\WSL_f(A)$ for the least weak stride length of $f$ at $A$. How to find some nontrivial upper bound for $\max_{A\in \SET_k\setminus \{[k]\}}\SL_f(A)$ and $\max_{A\in \SET_k\setminus \{[k]\}}\WSL_f(A)$? \begin{example}[Xinmao Wang] For \[f =\begin{pmatrix}0&{\bf 1}&0&0&0\\ 0&0&{\bf 1}&0&0 \\ 0&0&0&{\bf 1}&0\\ {\bf 1}&0&0&0&{\bf 1} \\ 0&0&{\bf 1}&0&0 \end{pmatrix},\] we have \[\max_{A\in \SET_5}\SL_f(A)=7, \max_{A\in \SET_5}\WSL_f(A)=6\] and \[ \{{\bf 2, 5}\}\to \{3\} \to \{4\} \to \{1,5\}\to \{2,3\}\to \{3,4\}\to \{\bf{1,4,5}\}\to \{1,{\bf 2, 3, 5}\} \] is a path showing that $\SL_f(A)=7$ and $\WSL_f(A)=6$ for $A=\{2, 5\}.$ \end{example} \section{Proofs}\label{sec:TANGENT} \begin{proof}[Proof of Theorem~\ref{thm:OCTO}] For any $i\in [k]$, let $F_{k,i}$ be the Boolean linear map on $2^{[k]}$ such that \[s^{F_{k,i}} := \begin{cases} s, & \text{if } s>i;\\ [i-1], & \text{if } s=i;\\ [k], & \text{if } si; \\ (\phi_k^{-1}(t+1) \backslash \{j\} )\cup [j-1] = \phi_k^{-1}(t), & \text{if } j=i; \\ [k] = \phi_k^{-1}(2^k-1), & \text{if } j< i. \end{cases} \] This implies that there exists a word $w=w_1\cdots w_{2^k-2}$ over $\mathcal{F}_k$ such that \[ \phi_k^{-1}(2^k-1)=[k]\xrightarrow{w_1} \phi_k^{-1}(2^k-2)\xrightarrow{w_2} \cdots \xrightarrow{w_{2^k-2}} \phi_k^{-1}(1)=\{1\} \xrightarrow{w_{2^k-1}} \emptyset \] is the unique shortest path in $\PS_{\mathcal {F}_k}$ from $[k]$ to $\emptyset$. Note that $\gpp((2^{[k]}, \mathcal{F}_k), \emptyset) $ is just the length of the shortest path from $[k]$ to $\emptyset$ and so the proof is finished. \end{proof} The next lemma says that for every $\mathcal M\in \Prim_k$, there is a common linear extension of ${\bf B}_k$ and $\mathbb{P}_{\mathcal M}$. \begin{lemma}\label{lem:Mackey} Take a positive integer $k$ and a set $\mathcal M\in \Prim_{k}.$ The poset $\mathbb{P}_{\mathcal M}$ has a linear extension $(\SET _k, \lhd )$ such that $A \lhd B$ holds for every two elements from $\SET _k$ satisfying either $A\subsetneq B$ or $A \prec_{\mathcal M}B$. \end{lemma} \begin{proof} Consider the digraph $D$ with $\Ve (D)=\SET_k$ and $\Ar (D)=\Ar _1 \cup \Ar_2$, where $\Ar_1=\{A\to B:\ A, B\in \SET_k, A\subsetneq B\} $ and $\Ar_2=\{A\to B:\ A, B\in \SET_k, A\prec_{\mathcal M} B\}$. If $D$ is acyclic, then $D$ possesses a linear extension and every such linear extension must be what we wanted. Suppose on the contrary that $D$ is not acyclic and so, considering that both $(\SET_k, \Ar _1)$ and $(\SET_k, \Ar _2)$ are transitive and acyclic digraphs, we can find a closed walk of positive length $2p $ in $D$: \[C_1\prec_{\mathcal M} B_1 \subsetneq C_2 \prec_{\mathcal M} B_2\subsetneq \cdots \subsetneq C_p \prec_{\mathcal M} B_p\subsetneq C_1.\] This means that there are matrices $M_1, \ldots, M_p$ from the multiplicative semigroup generated by $\mathcal M$ such that \[C_1M_1= B_1\subsetneq C_2, \ldots, C_pM_p= B_p\subsetneq C_1,\] and hence \[C_1M_1M_2\cdots M_p \subsetneq C_1.\] Consequently, starting from $C_1$ and applying the map $M_1M_2\cdots M_p$ repeatedly we will be always outside of the black hole $[k]$, which contradicts the assumption that $\mathcal M$ is strongly primitive. \end{proof} Pick a positive integer $k$ and any two elements $A,B\in \SET_k$. We write $f^{(k)}_{B\mapsto A}$ for the essential map on $\SET_k$ such that \begin{equation}Cf^{(k)}_{B\mapsto A}:=\begin{cases} A,& \text{if } C\subseteq B; \\ [k], & \text{if } C\setminus B\not= \emptyset. \end{cases} \label{eq:MARKER}\end{equation} \begin{lemma}\label{lem:Euler} Take $k \ge 2$ and $p\in [2^k-3]$. Let $\pi$ be a linear extension of the broken Boolean lattice ${\bf B}_k$. Let $\mathcal{F}_p = \{M_i : i \in [p]\}$ where $M_i = f^{(k)}_{\pi(i) \mapsto \pi(i+1)}$ for $i\in [p]$. Then $\mathcal {F}_p$ is strongly primitive, $\PS_{\mathcal {F}_p}$ contains the path $\pi(1) \to \pi(2) \to \cdots \to \pi(p+1) \to [k]$, and $\gp (\mathcal {F}_p) = p+1$. \end{lemma} \begin{proof} Since $\pi$ is a linear extension of ${\bf B}_k$, from Eq.~\eqref{eq:MARKER} we can see that \begin{itemize} \item each arc in $\PS_{\mathcal {F}_p}$ is either of the form $\pi(i)\to \pi(j)$ where $1\leq i2^k-2$, Eq.~\eqref{EQ:RHYTHM} tells us $p\notin \mathcal {G}_{k}.$ \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} We dedicate this paper to the memory of John Hajnal (Nov. 26, 1924 -- Nov. 30, 2008) and Peter H. Sellers (Sep. 12, 1930 -- Nov. 15, 2014), whose pioneering work inspires our exploration reported here. We thank Joel Cohen, Andreas Dress and John Goldwasser for their useful remarks. Especially, Goldwasser drew our attention to \cite{Shao} after we submitted the paper for publication. \begin{thebibliography}{99} \bibitem{AlAl} Yu.~A.~Al'pin and V.~S.~Al'pina. \newblock Combinatorial properties of irreducible semigroups of nonnegative matrices. \newblock {\em Journal of Mathematical Sciences}, 191:4--9, 2013. \bibitem{AVG} D.~S.~Ananichev, M.~V.~Volkov and V.~V.~Gusev. \newblock Primitive digraphs with large exponents and slowly synchronizing automata. \newblock {\em Journal of Mathematical Sciences}, 192:263--278, 2013. \bibitem{BG09} L.~B.~Beasley and A.~E.~Guterman. \newblock The characterization of operators preserving primitivity for matrix $k$-tuples. \newblock {\em Linear Algebra and its Applications}, 430:1762--1777, 2009. \bibitem{BK03} L.~B.~Beasley and S.~Kirkland. \newblock A note on $k$-primitive directed graphs. \newblock {\em Linear Algebra and its Applications}, 373:67--74, 2003. \bibitem{BM14} L.~B.~Beasley and S.~Mousley. \newblock $k$-Primitivity of digraphs. \newblock {\em Linear Algebra and its Applications}, 449:512--519, 2014. \bibitem{BJO15} V.~D.~Blondel, R.~M.~Jungers and A.~Olshevsky. \newblock On primitivity of sets of matrices. \newblock {\em Automatica. A Journal of IFAC}, 61:80--88, 2015. \bibitem{mortal} V.~D.~Blondel and J.~N.~Tsitsiklis. \newblock When is a pair of matrices mortal? \newblock {\em Information Processing Letters}, 63:283--286, 1997. \bibitem{BR} R.~Brualdi and H.~J.~Ryser. \newblock Combinatorial Matrix Theory. \newblock Cambridge University Press, Cambridge, 1991. \bibitem{Butkovic} P.~Butkovi\v{c}. \newblock Max-linear Systems: Theory and Algorithms. \newblock {\em Springer Monographs in Mathematics}, Springer, 2010. \bibitem{CDM} A.~S.~Cavaretta, W.~Dahmen and C.~A.~Micchelli. Stationary Subdivision. \newblock {\em Memoirs of the American Mathematical Society}, Vol. 93, AMS, 1991. \bibitem{Cerny} J.~\v{C}ern\'{y}. \newblock Pozn\'{a}mka k homog\'{e}nnym experimentom s kone\v{c}n\'{y}mi automatami. (in Slovak). \newblock {\em Matematicko-fyziklny \v{C}asopis Slovenskej Akad\'{e}mie Vied}, 14:208--216, 1964. \bibitem{cs82} J.~E.~Cohen and P.~H.~Sellers. \newblock Sets of nonnegative matrices with positive inhomogeneous products. \newblock {\em Linear Algebra and its Applications}, 47:185--192, 1982. \bibitem{CJLS} O.~Col\'{o}n-Reyes, A.~S.~Jarrah, R.~Laubenbacher and B.~Sturmfels. \newblock Monomial dynamical systems over finite fields. \newblock {\em Complex Systems}, 16:333--342, 2006. \bibitem{FF10} C.~Fleischhack and S.~Friedland. \newblock Asymptotic positivity of Hurwitz product traces: Two proofs. \newblock {\em Linear Algebra and its Applications}, 432:1363--1383, 2010. \bibitem{FV98} E.~Fornasini and M.~Valcher. \newblock Primitivity of positive matrix pairs: algebraic characterization, graph-theoretic description, and 2D systems interpretation. \newblock {\em SIAM Journal on Matrix Analysis and Applications}, 19:71--88, 1998. \bibitem{FV06} E.~Fornasini and M.~Valcher. \newblock A polynomial matrix approach to the structural properties of 2D positive systems. \newblock {\em Linear Algebra and its Applications}, 413:458--473, 2006. \bibitem{FV} E.~Fornasini and M.~Valcher. \newblock Reachability of a class of discrete-time positive switched systems. \newblock {\em SIAM Journal on Control and Optimization}, 49:162--184, 2011. \bibitem{Grin} V.~S.~Grinberg. \newblock Wielandt-type bounds for primitive mappings of partially ordered sets. \newblock {\em Mathematical Notes}, 45:450--454, 1989. \bibitem{Hajnal} J.~Hajnal. \newblock The ergodic properties of non-homogeneous finite Markov chains. \newblock {\em Mathematical Proceedings of the Cambridge Philosophical Society}, 52:67--77, 1956. \bibitem{Hajnal1} J.~Hajnal. \newblock On products of non-negative matrices. \newblock {\em Mathematical Proceedings of the Cambridge Philosophical Society}, 79:521--530, 1976. \bibitem{H02} D.~J.~Hartfiel. \newblock Nonhomogeneous Matrix Products. World Scientific, River Edge, NJ, 2002. \bibitem{HeyCohen} C.~C.~Heyde and J.~E.~Cohen. \newblock Confidence intervals for demographic projections based on products of random matrices. \newblock {\em Theoretical Population Biology}, 27:120--153, 1985. \bibitem{KRY} J.~P.~S.~Kung, G.-C.~Rota and C.~H.~Yan. \newblock Combinatorics: The Rota Way. \newblock Cambridge University Press, 2009. \bibitem{Lagarias} J.~C.~Lagarias. \newblock The Ultimate Challenge: The $3x+1$ Problem. \newblock AMS, 2010. \bibitem{LeV} M.~Lewin and Y.~Vitek. \newblock A system of gaps in the exponent set of primitive matrices.\newblock {\em Illinois Journal of Mathematics}, 25:87--98, 1981. \bibitem{Louck} J.~D.~Louck and M.~L.~Stein. \newblock The $(1+1)$-Nonlinear Universe Of The Parabolic Map And Combinatorics. \newblock World Scientific, 2015. \bibitem{Melkman} A.~A.~Melkman. \newblock Subdivision schemes with non-negative masks converge always -- unless they obviously cannot? \newblock {\em Annals of Numerical Mathematics}, 4:451--460, 1997. \bibitem{MNSS} G.~Merlet, T.~Nowak, H.~Schneider and S.~Sergeev. \newblock Generalizations of bounds on the index of convergence to weighted digraphs. \newblock {\em Discrete Applied Mathematics}, 178:121--134, 2014. \bibitem{MP89} C.~A.~Micchelli and H.~Prautzsch. \newblock Uniform refinement of curves. \newblock {\em Linear Algebra and its Applications}, 114/115:841--970, 1989. \bibitem{Ole02} D.~D.~Olesky, B.~Shader and P.~van den Driessche. \newblock Exponents of tuples of nonnegative matrices. \newblock {\em Linear Algebra and its Applications}, 356:123--134, 2002. \bibitem{Paz} A.~Paz. \newblock Introduction to Probabilistic Automata. \newblock Academic, New York, 1971. \bibitem{Protasov} V.~Yu.~Protasov. \newblock Semigroups of non-negative matrices. \newblock {\em Communications of the Moscow Mathematical Society}, 65:1186--1188, 2010. \bibitem{Protasov13} V.~Yu.~Protasov. \newblock Classification of $k$-primitive sets of matrices. \newblock {\em SIAM Journal on Matrix Analysis and Applications}, 34:1174--1188, 2013. \bibitem{PV} V.~Yu.~Protasov and A.~S.~Voynov. \newblock Sets of nonnegative matrices without positive products. \newblock {\em Linear Algebra and its Applications}, 437:749--765, 2012. \bibitem{SV08} P.~Santesso and M.~E.~Valcher. \newblock Monomial reachability and zero controllability of discrete-time positive switched systems. \newblock {\em Systems \& Control Letters}, 57:340--347, 2008. \bibitem{Shao} J.-Y.~Shao. \newblock On the properties of nonnegative primitive matrices, irreducible matrices and thier associated directed graphs. Ph.D. thesis, University of Wisconsin-Madison, 1984. \bibitem{Shao85} J.-Y.~Shao. \newblock On a conjecture about the exponent set of primitive matrices. \newblock {\em Linear Algebra and its Applications}, 65:91--123, 1985. \bibitem{Volkov} M.~V.~Volkov. \newblock Synchronizing automata and the \v{C}ern\'{y} conjecture.\newblock {\em Lecture Notes in Computer Science}, 5196:11--27, 2008. \bibitem{V13} A.~Voynov. \newblock Shortest positive products of nonnegative matrices.\newblock {\em Linear Algebra and its Applications}, 439:1627--1634, 2013. \bibitem{WWX} X.~Wang, Y.~Wu and Z.~Xiang. \newblock Wielandt-type matrices and primitive matrix set. \newblock manuscript, 2015. \bibitem{YWang} Y.~Wang. \newblock Subdivision schemes and refinement equations with nonnegative masks. \newblock {Journal of Approximation Theory}, 113:207--220, 2001. \bibitem{Wielandt} H.~Wielandt. \newblock Unzerlegbare, nicht negative Matrizen. \newblock {\em Mathematische Zeitschrift}, 52:642--648, 1959. \bibitem{WS12} Y.~Wu and J.~Shen. \newblock Opinion dynamics with stubborn vertices. \newblock {\em Electronic Journal of Linear Algebra}, 23:790--800, 2012. \bibitem{WXZ} Y.~Wu, Z.~Xu and Y.~Zhu. \newblock Expansion property of Boolean linear maps. submitted. available at \newblock \url{http://math.sjtu.edu.cn/faculty/ykwu/data/Paper/20150815.pdf}. \bibitem{WXZ15} Y.~Wu, Z.~Xu and Y.~Zhu. \newblock Reachability in higher-order Markov chains. manuscript, 2015. \bibitem{zhang} K.~M.~Zhang. \newblock On Lewin and Vitek's conjecture about the exponent set of primitive matrices. \newblock {\em Linear Algebra and its Applications}, 96:101--108, 1987. \bibitem{Zhou} X.~Zhou. \newblock Positivity of refinable functions defined by nonnegative finite masks. \newblock {\em Applied and Computational Harmonic Analysis}, 27:133--156, 2009. \end{thebibliography} \end{document}