% 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 s<t\leq 2^k-1$.
  This proves that $\gp ({\mathcal M_k})=2^k-2$  and  that  $\mathbb{P}_{\mathcal M_k}$ is the claimed total order,  as was to be shown.
\end{proof}





\section{Discrete dynamical systems}\label{sec:life}




Let  $S$ be a nonempty  set and let $\mathcal F$ be a family of    maps from $S$ to $S.$
Viewing the maps in $\mathcal F$ as a set of time-evolution laws
and $S$ the set of possible states, the pair $\mathcal D=(S, \mathcal F)$ forms
a {\bf discrete dynamical system} ({\bf DDS})  on the ground set $S$, where the    dynamics are given by iterating the maps in $\mathcal F$  and hence time changes in discrete steps. The fundamental role of the mathematical operation of function compositions makes DDS a very basic mathematical object which models many practical systems  \cite{CJLS, Louck}.

   We have used prefix notation for function values, that is, we put  the function name  followed by the input name inside parentheses. When
   talking about the functions in a DDS, we will use
    postfix notation instead. That is, when considering the DDS $(S, \mathcal F)$,
for any $f\in \mathcal F$ and $s\in S$, we adopt the notation $s^f$ for the image of $s$ under $f.$  When $s$ is a row vector and $f$ is a matrix that acts
 on $x$  by multiplication on the right, we often directly write  $s^f$ as $sf.$


 The  {\bf  phase space} of the DDS $(S, \mathcal F)$, which encodes all the phase transitions of the system, is the digraph with vertex set $S$ and arc set $\{s\to s^f:\ s\in S, f\in  \mathcal F\}$, and will  be  denoted by $\PS_{S,\mathcal F}$ or simply $\PS_{\mathcal F}$.  We call  $b\in S$ a {\bf black hole} of $(S, \mathcal F)$ provided $b$ is fixed by all $f\in \mathcal F$ and that for every $s\in S$, every long enough walk starting from $s$ in $\PS_{\mathcal F}$ will end at $b.$
A DDS $\mathcal D$ is  {\bf strongly primitive} if it has a black hole. Clearly, every strongly primitive DDS $\mathcal D$  has exactly one    black hole, which we often denote by $\mathbbold{1}=\mathbbold{1}_{\mathcal D}$,
and one may imagine that the so-called
`time's arrow' just points towards this black hole   $\mathbbold{1}$.


\begin{example}   Let $S$ be the set of positive integers. Let $f\in S^S$ be given by
 \[s^f :=   \begin{cases} 1,&  \text{if }  s=1; \\   3s+1,  &  \text{if }  s\ \text{is odd and } s>1;  \\ \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
    $i<j$ holds whenever    $\pi (i)\prec \pi (j)$.  If it happens that  $\gp (\mathcal D)= |S|-1<\infty$, we will have a longest path  in $\PS_{\mathcal D}$ of length $|S|-1$, say \[x_1\rightarrow x_2\rightarrow \cdots \rightarrow x_{|S|-1}\rightarrow x_{|S|}=\mathbbold{1},\] which means that the poset $\mathbb{P}_{\mathcal D}$ is the total order
\[x_1\prec_{\mathcal D} x_2\prec_{\mathcal D} \cdots \prec_{\mathcal D}x_{|S|-1}\prec_{\mathcal D} x_{|S|}=\mathbbold{1}.\] Actually, when  $S$ is a finite set, $\gp (\mathcal D)= |S|-1$ if and only if    $\mathbb{P}_{\mathcal D}$ is a total order if and only if $\mathbb{P}_{\mathcal D}$ allows a unique linear extension.








\section{Strongly primitive Boolean linear dynamical systems}\label{sec:ergodic}




Take a positive integer $k.$
A map $f$  from $\SET _k$ to $\SET _k$ is  {\bf  essential} provided
\begin{itemize}
\item $A^f\cup B^f= (A\cup B)^f$ for all $A, B\in \SET_k$, and
\item $ [k]^f=[k]$.
\end{itemize}
An essential map from $\SET _k$ to $\SET _k$  is the combinatorial  counterpart of a $k$ by $k$ matrix  without zero lines. Indeed,  we could  think of
such a map  $f$  as the
  $k$ by $k$ Boolean matrix $\M_f$ whose $(i,j)$-entry is $1$ if and only if $j\in i^f.$   We thus do not distinguish between an essential map $f$ and the corresponding matrix $\M_f $ and so the image $A^f$  of $A\in \SET_k$  under the map $f$ could be conveniently written as   $A\M_f$ or even just $Af.$  For ease of illustration, we use $A  \xrightarrow{f}B$ to mean that $B=Af$ and we do not distinguish an element $i\in [k]$ and the corresponding singleton set $\{i\}.$



Let $\mathcal F$ be a  family of essential maps on $\SET _k$. We call $(\SET_k, \mathcal F)$ an  {\bf essential Boolean linear dynamical system}. We refer to $\mathcal F$ as a {\bf strongly primitive  set of essential maps} on $\SET _k$ of size $t$
if $|\mathcal F|=t$ and  $(\SET_k, \mathcal F)$ is strongly primitive. If $(\SET_k, \mathcal F)$ is strongly primitive, it is clear that its  black hole
must be $[k]$.
 By identifying essential maps on $\SET _k$ with $k\times k$ Boolean matrices without zero lines, the strong primitivity concept defined here coincides with the one given in \S\ref{sec:Cohen}.
 If $\mathcal F$ is a singleton set, being strongly primitive and being primitive are the same. Thus, we call
a $k\times k$ Boolean matrix  $M$     {\bf primitive} if $(\SET_k, \mathcal F)$ is (strongly) primitive for $\mathcal F =\{M\}$.


Choose $k\geq 2$ and $i\in [k-1].$
We adopt the notation $W_{k;i}$ for the essential map $f$ on $\SET_k$ satisfying $i^f:=i+1  $ for $i\in [k-1]$
and $k^f:=\{1, 1+i\}$. A {\bf Wielandt matrix} is a matrix which is  permutation  similar to $W_{k;1} $ \cite{Wielandt}.   In general,  a {\bf Wielandt-type} matrix, as introduced in \cite{WWX}, is a matrix which is permutation  similar to a matrix $W_{k;i}$ where $\gcd (k,i)=1.$
One can check that $\gp (W_{k;i})=k+(k-2)(k-i)$ when $\gcd (k,i)=1$. We display several Wielandt-type matrices below and present the phase space of $W_{4;1}$
in Fig.~\ref{Fig:resilience}.

\[W_{4;1}=\begin{pmatrix}0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&1&0&0\end{pmatrix}, W_{4;3}=
\begin{pmatrix}0&1&0&0\\ 0&0&1&0\\0&0&0&1\\ 1&0&0&1\end{pmatrix},  W_{5;4}=\begin{pmatrix}0&1&0&0&0\\ 0&0&1&0&0\\ 0&0&0&1&0\\ 0&0&0&0&1\\1&0&0&0&1\end{pmatrix}.\]




\begin{figure}
\begin{center}\setlength{\unitlength}{0.95pt}
\begin{picture}(330,70)
\put(10,60){\makebox(0,0){\small 1000}}
\put(40,60){\makebox(0,0){\small 0100}}
\put(70,60){\makebox(0,0){\small 0010}}
\put(100,60){\makebox(0,0){\small 0001}}
\put(100,40){\makebox(0,0){\small 1001}}
\put(130,50){\makebox(0,0){\small 1100}}
\put(160,50){\makebox(0,0){\small 0110}}
\put(190,50){\makebox(0,0){\small 0011}}
\put(220,40){\makebox(0,0){\small 1101}}
\put(190,30){\makebox(0,0){\small 1011}}
\put(250,25){\makebox(0,0){\small 1110}}
\put(280,25){\makebox(0,0){\small 0111}}
\put(310,25){\makebox(0,0){\small 1111}}
\put(190,10){\makebox(0,0){\small 1010}}
\put(220,10){\makebox(0,0){\small 0101}}
\put(20,60){\vector(1,0){10}}
\put(50,60){\vector(1,0){10}}
\put(80,60){\vector(1,0){10}}
\put(110,60){\vector(2,-1){10}}
\put(110,40){\vector(2,1){10}}
\put(140,50){\vector(1,0){10}}
\put(170,50){\vector(1,0){10}}
\put(200,50){\vector(2,-1){10}}
\put(200,30){\vector(2,1){10}}
\put(200,10){\vector(1,0){10}}
\put(230,40){\vector(1,-1){10}}
\put(230,10){\vector(1,1){10}}
\put(260,25){\vector(1,0){10}}
\put(290,25){\vector(1,0){10}}
\put(320,25){\arc[-150,150]{15}}
\put(320,40){\vector(1,0){3}}
\end{picture}\end{center}
\caption{$\PS_{W_{4;1}}$.}\label{Fig:resilience}
\end{figure}





\begin{theorem}[Wielandt \cite{Wielandt}] For every primitive matrix $M$  of order $k\geq 2$, it holds $\gp (M)\leq (k-1)^2+1,$ with equality  if and only if $M$ is a Wielandt matrix. \label{thm:BELUGA}
\end{theorem}


 For any positive integers $k $ and $t,$  let $\Prim_k$ be the set of all strongly primitive sets of
 essential maps on  $\SET _k$  and let    $\Prim_{k,t}$ be the set of those elements from $\Prim_k$ of size $t$.
 Theorem~\ref{thm:BELUGA}     gives an upper bound for the transients of elements of $\Prim_{k,1}$.
  It is natural to wonder
which kind of   upper bound can be obtained when we turn to $\Prim_{k,t}$ for $t>1$, 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)<k$ holds.
Theorem~\ref{eq:IGOR} says that this $\tau$, if any, could not be the   lexicographic order when $k\geq 3$. Note that
 our proof of Theorem~\ref{thm:fabulous}, and hence Theorem~\ref{thm:CONTROLLABILITY},    makes use of a strongly primitive matrix set   compatible with the  lexicographic order on $\SET_k$ and
 this explains the main difficulty in extending our work here for a possible better bound.
It may be interesting to determine $\gamma (\tau)$ for some other natural total orders on $\SET_k$.





Given an element  $\mathcal M$  from $\Prim_k$,  how to prolong the longest lifespan by adding some more suitable essential maps without making someone live forever, namely without losing the strong primitivity property?  Let $\gamma (\mathcal M)$ be the minimum size of
  $\mathcal F$ such that   $\gp (\mathcal F\cup \mathcal M)=2^k-2$.
As illustrated by the next theorem, it turns out that we can always enlarge a strongly primitive matrix set into a bigger one  in which the longest life duration achieves the absolute upper bound  (Eq.~\eqref{EQ:RHYTHM}), which means that $\gamma (\mathcal M)$ is well-defined.



\begin{theorem}\label{thm:MASCHKE} Let $k$ be an   integer not less than 2 and  $\mathcal M$  an element from $\Prim_k$. Then it holds  $\gamma (\mathcal M)\leq 2^k-3$.
\end{theorem}


Theorem~\ref{thm:MASCHKE} establishes an absolute upper bound for  $\gamma (\mathcal M)$, which implies the first half of Theorem~\ref{thm:Prabhu} by
 taking $\mathcal M=\emptyset$.  It will be interesting to develop some tools to get the exact value of $\gamma (\mathcal M)$ for some explicit $\mathcal M$, say some singleton set $\mathcal M.$ Recently, Wang, Wu and Xiang \cite{WWX}  found that \[\gamma (W_{k; k-1})\leq  \binom{k-2}{\lfloor(k-2)/2\rfloor}\]   for all  integers $k\geq 2$, from which  $ \gamma_5\leq  4$ follows.
For a set $\mathcal M$  of essential maps    on $\SET _k$ and any positive integer $t$, let
$\gp_{t}(\mathcal M)=\max \{\gp (\mathcal F):\ \mathcal M\subseteq \mathcal F, |\mathcal F\setminus \mathcal M|=t\}$.
 Besides some trivial examples, it seems that no result about   $\gp_{t}(\mathcal M)$ is known.




For each positive integer $k$, let  $\alpha_k=\max \{t:\  \Prim_{k,t}\not= \emptyset\}$. It is obvious that $\alpha_k$ will never decrease when $k$ becomes bigger. Indeed, for any strongly primitive  set $\mathcal F$  of essential maps on $\SET _k$, we can create a strongly primitive  set $\mathcal F'$  of essential maps on $\SET _{k+1}$ of equal size  by putting \[\mathcal F':=\{f':\ f\in    \mathcal F\},\]
where $f'$ is the essential map on $\SET_{k+1}$ such that $i^{f'}=i^{f}\cup \{k+1\}$ if $i\in [k]$ and $(k+1)^{f'}=[k+1]$ for all $f\in \mathcal F$.


\begin{theorem}\label{lem:GOLD}  For all positive integers $k$,  $\alpha_k\geq 1+{2^k-2\choose 2}$.
\end{theorem}



 It is clear that $\Prim_k$ forms an abstract simplicial complex
of  dimension $\alpha_k-1.$   We wonder whether or not
$\Prim_k$ is    a pure simplicial complex, i.e., whether or not all maximal elements of
$\Prim_k$ under the inclusion relationship   are of the same size  $\alpha_k.$ Note that if $\Prim_k$ is indeed  a pure simplicial complex, the ensuing result
will follow easily from this fact.


\begin{theorem} \label{thm:LOLITA}   It holds for every positive integer $k$  that  \begin{equation}
 \gp_{k,1}\leq \gp_{k,2}\leq \cdots \leq \gp_{k,\alpha_k}.\label{eq:SOFIA}\end{equation}
\end{theorem}



Compared with the inequalities in \eqref{eq:SOFIA}, it is trivial to prove the following analogue for the hitting time $\underline{\gp}$:
\[
 \underline{\gp}_{k,1}\leq \underline{\gp}_{k,2}\leq \cdots \leq \underline{\gp}_{k,\alpha_k}.\]
 Recall that Theorem~\ref{thm:CONTROLLABILITY} means that the absolute upper bound described in Eq.~\eqref{EQ:RHYTHM} can be achieved at a small $t.$
  Accordingly, regarding the absolute upper bound listed in Eq.~\eqref{Eq:ROBOT}, the following theorem states that it is achievable only when the
strongly primitive matrix set is a very specific singleton set.


\begin{theorem}\label{thm:chromosome} Take $k\geq 2 $   and  $\mathcal F\in   \Prim_k$. Then
$\underline{\gp}(\mathcal F)\leq (k-1)^2+1$, with equality   if and only if $\mathcal F$ is a singleton set consisting of a Wielandt matrix. In particular, we have
 $\beta_k=1$.
\end{theorem}




So far, we have been discussing the extremal behaviors of the indexes $\underline{\gp}$  and  $\gp$ for strongly primitive set of essential Boolean linear maps.
For a deeper understanding of the two indexes, we may want to understand the four index sets defined as below:
\[ \left\{
                                                         \begin{array}{l}
                                                         \mathcal {G}_{k,t}:=\{\gp (\mathcal F):\ \mathcal F\in\Prim_{k,t}\}; \\
                                                      \underline{\mathcal {G}}_{k,t}:=\{ \underline{\gp}(\mathcal F):\ \mathcal F\in\Prim_{k,t}\}; \\
                                                    \mathcal {G}_{k}:= \{\gp (\mathcal F):\ \mathcal F\in\Prim_{k}\};\\
                                                    \underline{\mathcal {G}}_{k}:=\{ \underline{\gp}(\mathcal F):\ \mathcal F\in\Prim_{k}\}.
                                                         \end{array}
                                                       \right.
\]
The community of combinatorics matrix theory has made clear the structure of the set $\mathcal {G}_{k,1}=\underline{\mathcal {G}}_{k,1}$ \cite{LeV,Shao85,zhang};  see    \cite[\S 3.5]{BR}. %\cite{BR}.
Moreover,  Shao    determined the set $\mathcal {G}_{k}$ in his PhD thesis  \cite[pp. 120--124]{Shao}.  We report his result below and present
a proof of it in \S\ref{sec:TANGENT}. Our proof of   Theorem~\ref{thm:Shao}  follows the same idea with that of Shao but is written in the language of our phase space approach.

\begin{theorem}[Shao]  For every  positive integer $k,$  $\mathcal {G}_{k}=[2^k-2]$ holds.
    \label{thm:Shao}
\end{theorem}




We have discussed above some results about the primitivity  exponent and the hitting time of a strongly primitive essential Boolean linear dynamical system. In general,
we may ask what is the shape of $\mathbb{P}_{\mathcal D}$ for a strongly primitive essential binary linear system $\mathcal D$, what can be said on the M\"obius function of this poset, and so forth.  It may be useful to develop more concepts and apparatus for thinking further about combinatorial properties of (inhomogeneous) products of Boolean matrices.
Let us  end this section with one question about the dynamics generated by  a single matrix.



Pick $f\in \Prim_k$.
 For every $A\in \SET _k$, we say that a positive integer  $i$ is a {\bf  stride length} of $f$ at $A$  provided     $Af^i\supsetneq A$ and we write $\SL_f(A)$ for the least  stride length of $f$ at $A$.
 Similarly, for every $A\in \SET _k$, we say that a positive integer  $i$ is a {\bf weak stride length} of $f$ at $A$  provided     $|Af^i|>  | 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 }  s<i;
        \end{cases}
     \]
for every $s \in [k].$
    Let $\mathcal{F}_k = \{F_{k,i} :\ i\in [k]\}$.

     Recall the definition of  $\phi_k$ in Eq.~\eqref{eq:memorandum}.
    Take $t \in [2^k-2]$ and let $j$ be the smallest element of $\phi_k^{-1}(t+1)$. For any $i \in [k],$
    we can check that
    \[
        (\phi_k^{-1}(t+1))^{F_{k,i}} =
        \begin{cases}  \phi_k^{-1}(t+1), & \text{if } j>i;      \\
            (\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 i<j\leq p+1$, or of the form  $\pi(i)\to \pi(2^k-1)$
    for $i\in  [2^k-1]$; and that
    \item $\pi(1) \xrightarrow{M_1} \pi(2)  \xrightarrow{M_2}  \cdots  \xrightarrow{M_{p}} \pi(p+1) \xrightarrow{M_{p}} [k]$ is a path of length $p+1$ in $\PS_{\mathcal {F}_p}$.
    \end{itemize}
  The claims about   $\mathcal {F}_p$ now follow directly.
    \end{proof}





\begin{proof}[Proof of Theorem~\ref{eq:SHANNON}] The implication (iii) to (i) is a triviality.

We now prove that  (i) implies  (ii).
From $\gamma (\pi)<\infty$ we obtain the existence of $\mathcal M\subseteq \MC^\pi$ such that $\gp (\mathcal M)=2^k-2.$
Note that  $\mathbb{P}_{\mathcal M}$ is the total order
\[\pi(1)<\cdots < \pi (2^k-2)< \pi (2^k-1)=[k]. \] By Lemma~\ref{lem:Mackey}, this total order $\pi$ has to be a linear extension of the broken Boolean lattice.

Finally, we need to establish the   direction of (ii) $\Rightarrow$ (iii). By Lemma~\ref{lem:Euler},
$\mathcal{F}_{2^k-3}\in \MC^{\pi}$ and
 $\gp (\mathcal{F}_{2^k-3})=2^k-2 $,   proving the desired fact that $\gamma (\pi)\leq 2^k-3$.
\end{proof}






\begin{proof}[Proof of Theorem~\ref{eq:IGOR}] Theorem~\ref{thm:fabulous}  means that $\gamma (\pi_k)\leq  k$. It suffices to show $\gamma (\pi_k)\geq k$.
Let \[
     a_k:=\   \phi_k^{-1}(4)=\{k-2\}  \to \{k-2,k\}=\phi_k^{-1}(5)
    \] and
\[a_i:=\ \phi_k^{-1}(2^k-2^{i-1}-1)=[k]\setminus \{i\}\rightarrow  [i]= \phi_k^{-1}(2^k-2^{i-1})  \] for $i\in [k-1]$.
They are $k$ arcs   in the Hasse diagram of the total order $\pi_k$. By way of contradiction, let us assume  $\gamma (\pi_k)< k$ and thus there should be a primitive matrix $M$ of order $k$ such that  $\PS_{M}$ contains two arcs $a_p$ and $a_q$ where $1\leq p<q\leq k.$   From $a_p\in \Ar (\PS_{M})$ we deduce that \begin{equation}([k]\setminus \{p\})M\subseteq [p]. \label{eq:BENDICKS}\end{equation}
Considering that $M$ is primitive and so $[k]M=[k]$ holds, we reach the conclusion  that \begin{equation}[k]\setminus [p]\subseteq \{p\}M.
\label{eq:SPARSITY}\end{equation}


\medskip


\noindent {\sc  Case 1.}  $q\in [k-1].$

We get Eq.~\eqref{eq:BENDICKS} just from the fact that $p\in [k-1]$. So, we can also get from  $q\in [k-1]$  that  $k\notin ([k]\setminus \{q\})M$ and hence $k\notin \{p\}M$, contradicting  Eq.~\eqref{eq:SPARSITY}.


\medskip


\noindent {\sc  Case 2.}  $q=k.$

  From $a_q\in \Ar (\PS_{M})$ we see that \begin{equation}\{k-2, k\} = \{k-2\}M.  \label{eq:ALBERT}\end{equation} Since $k\in   \{k-2\}M,$
   Eq.~\eqref{eq:BENDICKS} gives $p= k-2.$
 Applying Eq.~\eqref{eq:SPARSITY} now yields $k-1\in \{k-2\}M,$ violating Eq.~\eqref{eq:ALBERT}.
   \end{proof}


\begin{proof}[Proof of Theorem~\ref{thm:MASCHKE}]
  By Lemma~\ref{lem:Mackey}, we can take $\pi$ to be a  common linear extension of ${\bf B}_k$  and $\mathbb{P}_{\mathcal M}$.
Now,
 Theorem~\ref{eq:SHANNON} guarantees the existence of a set $\mathcal F\in {\MC^{\pi}\choose t}$ for some $t\leq 2^k-3$ such that $\mathcal F\cap \mathcal M=\emptyset$ and $\gp (\mathcal F\cup \mathcal M)=2^k-2$.
\end{proof}



\begin{proof}[Proof of Theorem~\ref{lem:GOLD}]
Take any linear order $\pi$ on $\SET_k$ which   is a linear extension of the broken Boolean lattice ${\bf B}_k,$
say  \[\pi (1)<\ldots <\pi (2^k-2)<\pi (2^k-1)=[k].\]
Let \begin{equation}\mathcal F:=\{M_{i,j}:\ 1\leq i<j\leq 2^k-2\}\cup \{f^{(k)}_{[k]\mapsto [k]}\},  \label{eq:BARLEY} \end{equation} where $M_{i,j}=f^{(k)}_{\pi (i)\mapsto \pi(j)}$ for those $i,j$ satisfying $1\leq i<j \leq 2^k-2.$ It follows from Eq.~\eqref{eq:MARKER} that
  $\PS_{\mathcal F}$ is the total order $\pi$ and so $\gp (\mathcal F)=2^k-2.$ It is clear that $\mathcal F$ consists of $1+{2^k-2\choose 2}$  different maps and so the theorem follows.
\end{proof}


For every integer $k\geq 2,$ Theorem~\ref{lem:GOLD} tells us that \begin{equation}\alpha_k\geq 1+{2^k-2\choose 2}\geq 2^k-2\geq k, \label{eq:POSITIVE}
\end{equation} where the second inequality is strict  for $k\geq 3.$   The subsequent two lemmas
 determine   the values of  $\gp_{k, k}, \ldots, \gp_{k,2^k-2}, \gp_{k,2^k-1}, \ldots, \gp_{k,\alpha_k}$.



\begin{lemma}\label{lem:ANDREAS} Let $k$ be an integer greater than $1$.  Then   $\gp_{k,k}= \gp_{k,k+1}= \cdots = \gp_{k,2^k-2}=2^k-2$.
\end{lemma}

\begin{proof}
 For ${\mathcal M_k}=\{M_{k,1}, \ldots, M_{k,k}\}$, Theorem~\ref{thm:fabulous} claims that $\gp (\mathcal M_k)=2^k-2 $ and   $\mathbb{P}_{\mathcal M_k}$ is the lexicographic   order  $\pi_k$ on $\SET_k$.

Taking $\pi=\pi_k$, we now consider the family of essential maps $\mathcal F$ as given in
Eq.~\eqref{eq:BARLEY}.  By  Eq.~\eqref{eq:POSITIVE}, we have \[|\mathcal F\setminus {\mathcal M_k}|\geq  2^k-2-k.\]
   The lexicographic   order  $\pi_k=\mathbb{P}_{\mathcal M_k}$ is surely a linear extension of the broken Boolean lattice ${\bf B}_k$. This along with  Eq.~\eqref{eq:MARKER} tells us that $\gp (\mathcal F'\cup \mathcal M_k)=2^k-2$ for every $\mathcal F'\subseteq \mathcal F\setminus {\mathcal M_k}.$ It follows that   $\gp_{k,k}= \gp_{k,k+1}= \cdots = \gp_{k, 2^k-2+k}=2^k-2$, finishing the proof.
\end{proof}


\begin{lemma}\label{lem:Vincent}   Let $k$ be an integer greater than $2$.  Then   $\gp_{k,2^k-1}=\cdots = \gp_{k,\alpha_k}=2^k-2$.
\end{lemma}

\begin{proof}
Take $\mathcal A\in \Prim_{k,\alpha_k}$ and,   thanks to Lemma~\ref{lem:Mackey},  pick a common linear extension of $\bf B_k$ and   $\mathbb{P}_{\mathcal A}$, say  \[(\SET _k, \lhd ):\ A_1 \lhd A_2 \lhd \cdots \lhd A_{2^k-1}=[k]=\mathbbold{1}.  \]
Let \[\mathcal F:=\{M_i:\ i\in [2^k-2]\},\] where $M_i=f^{(k)}_{A_i\mapsto A_{i+1}}$ for $i\in [2^k-2].$ It follows from Eq.~\eqref{eq:MARKER} that
$\mathcal F\cup \mathcal A$ is strongly  primitive and so the definition of $\alpha_k$ leads to $\mathcal F\subseteq \mathcal A$. Take an integer $t$ satisfying $2^k-1\leq t\leq \alpha_k$. We can find a set $\mathcal F_t$ such that $\mathcal F\subseteq \mathcal F_t\subseteq \mathcal A$ and $|\mathcal F_t|=t.$ It is clear that $\mathcal F_t\in \Prim_{k,t}$ and $\gp (\mathcal F_t)=2^k-2$. Since $2^k-2$ is the absolute upper bound for the strong primitivity exponent here, we conclude that $\gp _{k,t}=2^k-2,$ as desired.
\end{proof}






\begin{proof}[Proof of Theorem~\ref{thm:LOLITA}]
When $k=2$, the primitive matrices of order $k$ can be listed as
\[\begin{pmatrix}\bf{1}&\bf{1} \\ \bf{1}&\bf{1}\end{pmatrix},   \begin{pmatrix}\bf{1}&\bf{1} \\ \bf{1}& 0 \end{pmatrix},   \begin{pmatrix}0&\bf{1} \\ \bf{1}&\bf{1} \end{pmatrix}. \]
It is thus easy to see that $\alpha_2=2=2^2-2$.



 Combining   Lemma~\ref{lem:ANDREAS} and
  Lemma~\ref{lem:Vincent}, our task is  now reduced to establishing
\begin{equation}\label{eq:PROUST} \gp_{k,1}\leq   \cdots \leq \gp_{k, k}. \end{equation}
We will be able to obtain Eq.~\eqref{eq:PROUST} provided,  for each $t\in [k-1]$ and each $\mathcal A\in \Prim_{k,t}$, we can find $\mathcal B\in \Prim_{k,t+1}$ such that $\mathcal A\subseteq   \mathcal B.$ Lemma~\ref{lem:Mackey} allows us to get  a common linear extension of   $\bf B_k$ and  $\mathbb{P}_{\mathcal A}$, say
\[(\SET _k, \lhd ):\ A_1 \lhd A_2 \lhd \cdots \lhd A_{2^k-1}=\mathbbold{1}.  \]
Let $\mathcal F=\{M_i:\ i\in [2^k-2]\}$ where $M_i=f^{(k)}_{A_i\mapsto A_{i+1}}$ for $i\in [2^k-2].$ It follows from Eq.~\eqref{eq:MARKER} that
$\mathcal F\cup \mathcal A$ is strongly  primitive.  Since   $t+1\leq k\leq 2^k-2,$ we can get $F\in     \mathcal F\setminus \mathcal A$. Letting   $ \mathcal B=  \mathcal A\cup \{F\}$,  it is not hard to check that $\mathcal B\in \Prim_{k,t+1}$ and hence we are done!
    \end{proof}


\begin{proof}[Proof of Theorem~\ref{thm:chromosome}] Pick arbitrarily an element  $M$ from $ \mathcal F.$  Theorem~\ref{thm:BELUGA} gives
$\underline{\gp}(M) \leq (k-1)^2+1$ and the equality holds if and only if $M$ is permutation  similar to $W_{k;1}$.
It is obvious that
 $\underline{\gp}(\mathcal F)\leq  \underline{\gp}(M) \leq (k-1)^2+1$. Consequently, to complete  the proof, it suffices to demonstrate that
 $\{W_{k;1}, M\}$ is not strongly primitive for  every Wielandt matrix  $M$  other than $W_{k;1}$. Let us assume that $M=PW_{k;1}P^{-1}$, where $P$ is a permutation matrix which is not equal to the identity matrix.

\medskip


\noindent {\sc  Case 1.} $k\xrightarrow{P}i\in [k-1]$.

In this case, we have  $j \in [k-1]$ such that
$k\xrightarrow{P}i\xrightarrow{W_{k;1}}i+1 \xrightarrow{P^{-1}}j$, namely  $k\xrightarrow{M} j$.
In $\PS_{W_{k;1}}$, we have a path $j\to j+1\to \cdots \to k$, which, combined with the arc $k\to j$ from $\PS_{M}$, gives a cycle in $\PS_{W_{k;1}, M}$.
This shows that $\{W_{k;1}, M\}$ is not strongly primitive.

\medskip


\noindent {\sc  Case 2.}  $k\xrightarrow{P}k$.

As $P$ is not the identity matrix, we can set $i=\max \{j:\ jP\not= j\}\in [k-1]$.
 It follows that
$i\xrightarrow{P}g\leq   i-1\in [k-2]$.  Henceforth,
$i\xrightarrow{P}g\xrightarrow{W_{k;1}}g+1\in [i]$. This in turns gives
$i\xrightarrow{P}g\xrightarrow{W_{k;1}}g+1 \xrightarrow{P^{-1}}h<i\leq k-1$.
Now, we can find the following cycle in the phase space of $\{W_{k;1}, M\}$: \[h \xrightarrow{W_{k;1}}h+1  \xrightarrow{W_{k;1}}\cdots  \xrightarrow{W_{k;1}}
i\xrightarrow{M} h,\]  proving that    $\{W_{k;1}, M\}$ is not strongly primitive, as desired.
  \end{proof}



\begin{proof}[Proof of Theorem~\ref{thm:Shao}]
For $p=1,$  it is immediate that $\gp({\mathcal F}) =p$
for   ${\mathcal F}=\{f^{(k)}_{[k]\mapsto [k]}\}$ (c.f. Eq.~\eqref{eq:MARKER}).
If
  $2 \le p \le 2^k-2$, it follows from
  Lemma~\ref{lem:Euler} that $p\in   \mathcal {G}_{k}.$  For any $p>2^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}




