# On the exponent set of nonnegative primitive tensors 111P. Yuan’s research
is supported by the NSF of China (Grant No. 11271142) and the Guangdong
Provincial Natural Science Foundation(Grant No. S2012010009942), L. You’s
research is supported by the Zhujiang Technology New Star Foundation of
Guangzhou (Grant No. 2011J2200090) and Program on International Cooperation
and Innovation, Department of Education, Guangdong Province (Grant
No.2012gjhz0007).

Zilong He222Email address<EMAIL_ADDRESS>Pingzhi Yuan333Corresponding author:
<EMAIL_ADDRESS>Lihua You444Email address<EMAIL_ADDRESS>
(School of Mathematical Sciences, South China Normal University,
Guangzhou, 510631, P.R. China
)

###### Abstract

In this paper, we present a necessary and sufficient condition for a
nonnegative tensor to be a primitive one, show that the exponent set of
nonnegative primitive tensors with order $m(\geq n)$ and dimension $n$ is
$\\{k|1\leq k\leq(n-1)^{2}+1\\}.$ AMS classification: 05C50; 15A69 Keywords:
tensor; the exponent set; primitive tensor; primitive degree.

##  1 Introduction

An $n\times n$ nonnegative square matrix $A=(a_{ij})$ is nonnegative primitive
(or simply, primitive) if $A^{k}>0$ for some positive integer $k$. The least
such $k$ is called the primitive exponent (or simply, exponent) of $A$ and is
denoted by $\gamma(A)$.

Let $a,b,n$ be positive integers with $b>a$, $[a,b]^{o}=\\{k|k\mbox{ is an
integer and }a\leq k\leq b\\}$, $[n]=[1,n]^{o}=\\{1,2,\ldots,n\\}$,
$E_{n}=\\{k|\mbox{ there exists a primitive matrix }A\mbox{ of order }n\mbox{
such that }$ $\gamma(A)=k\\}.$

In 1950, H. Wielandt [9] first stated the sharp upper bound for $\gamma(A)$,
that is, $\gamma(A)\leq w_{n}=(n-1)^{2}+1$ for all $n\times n$ primitive
matrices and showed that $E_{n}\subseteq[1,w_{n}]^{o}$. In 1964, A. L. Dulmage
and N. S. Mendelsohn [3] revealed the so-called gaps in the exponent set of
primitive matrices, that is, $E_{n}\subset[1,w_{n}]^{o}$, where “gap” is a set
of consecutive integers $[a,b]^{o}(\subset[1,w_{n}]^{o})$, such that no
$n\times n$ matrix $A$ satisfying $\gamma(A)\in[a,b]^{o}$. In 1981, M. Lewin
and Y. Vitek [4] found all gaps in
$[\lfloor\frac{1}{2}w_{n}\rfloor+1,w_{n}]^{o}$, and conjectured that
$[1,\lfloor\frac{1}{2}w_{n}\rfloor]^{o}$ has no gaps, where $\lfloor x\rfloor$
denotes the greatest integer $\leq x$. In 1985, Shao [10] proved that this
Lewin-Vitek Conjecture is true for all sufficiently large $n$, and the
conjecture has one counterexample when $n=11$ since $48\not\in E_{11}$.
Finally, in 1987, Zhang [13] continued and completed the work. He showed that
the Lewin-Vitek Conjecture holds for all $n$ except $n=11$. Thus the exponent
set $E_{n}$ for primitive matrices of order $n$ is completely determined.

Since the work of Qi [8] and Lim [5], the study of tensors and the spectra of
tensors (and hypergraphs) and their various applications have attracted much
attention and interest. In [1] and [2], Chang et al. defined the
irreducibility of tensors, the primitivity of nonnegative tensors, and
extended many important properties of (nonnegative) primitive matrices to
(nonnegative) primitive tensors. As an application of the general tensor
product defined by Shao [11], Shao presented a simple characterization of the
primitive tensors in terms of the zero pattern of the powers of $\mathbb{A}$.
He also proposed a conjecture on the primitive degree $\gamma(\mathbb{A})$.
Recently, the authors [12] confirmed the conjecture of Shao by proving Theorem
1.1.

######  Theorem 1.1.

([12] Theorem 1.2) Let $\mathbb{A}$ be a nonnegative primitive tensor with
order $m$ and dimension $n$. Then its primitive degree
$\gamma(\mathbb{A})\leq(n-1)^{2}+1$, and the upper bound is sharp.

Therefore, it is natural to consider the question to completely determine the
exponent set of primitive tensors with order $m$ and dimension $n$. Let
$m(\geq 2),n$ be positive integers and

$E(m,\,n)=\\{k|\mbox{ there exists a primitive tensor }\mathbb{A}\mbox{ of
order }m\mbox{ and dimension }n\mbox{ such that }k=\gamma(\mathbb{A})\\}.$

The main result of this paper is as follows.

######  Theorem 1.2.

Let $m,n$ be positive integers with $m\geq n\geq 3$. Then
$E(m,\,n)=[1,(n-1)^{2}+1]^{o}$.

The above theorem shows that there are no gaps in tensor case when $m\geq
n\geq 3$. It is well-known that there exist gaps when $m=2$, therefore it is
an interesting open problem to determine whether there exist gaps when $3\leq
m<n$.

The arrangement of the paper is as follows. In Section 2, we will give some
definitions and properties. In Section 3, we present a necessary and
sufficient condition for a nonnegative tensor to be a primitive one (Theorem
3.4). In Section 4, We prove the main result (Theorem 1.2).

##  2 Preliminaries

An order $m$ dimension $n$ tensor $\mathbb{A}=(a_{i_{1}i_{2}\cdots
i_{m}})_{1\leq i_{j}\leq n\hskip 5.69046pt(j=1,\ldots,m)}$ over the complex
field $\mathbb{C}$ is a multidimensional array with all entries
$a_{i_{1}i_{2}\cdots
i_{m}}\in\mathbb{C}\,(i_{1},\ldots,i_{m}\in[n]=\\{1,\ldots,n\\})$. The
majorization matrix $M(\mathbb{A})$ of the tensor $\mathbb{A}$ is defined as
$(M(\mathbb{A}))_{ij}=a_{ij\cdots j}(i,j\in[n])$ by Pearson [6].

Let $\mathbb{A}$ (and $\mathbb{B}$) be an order $m\geq 2$ (and $k\geq 1$),
dimension $n$ tensor, respectively. In [11], Shao defines a general product
$\mathbb{A}\mathbb{B}$ to be the following tensor $\mathbb{D}$ of order
$(m-1)(k-1)+1$ and dimension $n$:

$d_{i\alpha_{1}\cdots\alpha_{m-1}}=\sum\limits_{i_{2},\ldots,i_{m}=1}^{n}a_{ii_{2}\cdots
i_{m}}b_{i_{2}\alpha_{1}}\cdots
b_{i_{m}\alpha_{m-1}}\quad(i\in[n],\,\alpha_{1},\ldots,\alpha_{m-1}\in[n]^{k-1}).$

The tensor product possesses a very useful property: the associative law ([11]
Theorem 1.1).

In [2] and [7], Chang et al. and Pearson define the primitive tensors as
follows.

######  Definition 2.1.

([2, 7])  Let $\mathbb{A}$ be a nonnegative tensor with order $m$ and
dimension $n$, $x=(x_{1},x_{2},\ldots,x_{n})^{T}\in\mathbb{R}^{n}$ a vector
and $x^{[r]}=(x_{1}^{r},x_{2}^{r},\ldots,x_{n}^{r})^{T}$. Define the map
$T_{\mathbb{A}}$ from $\mathbb{R}^{n}$ to $\mathbb{R}^{n}$ as:
$T_{\mathbb{A}}(x)=(\mathbb{A}x)^{[\frac{1}{m-1}]}$. If there exists some
positive integer $r$ such that $T_{\mathbb{A}}^{r}(x)>0$ for all nonnegative
nonzero vectors $x\in\mathbb{R}^{n}$, then $\mathbb{A}$ is called primitive
and the smallest such integer $r$ is called the primitive degree of
$\mathbb{A}$, denoted by $\gamma(\mathbb{A})$.

In [11], Shao shows the following results and defines the primitive degree by
using the properties of tensor product and the zero patterns.

######  Proposition 2.2.

([11] Theorem 4.1) A nonnegative tensor $\mathbb{A}$ is primitive if and only
if there exists some positive integer $r$ such that $\mathbb{A}^{r}$ is
essentially positive. Furthermore, the smallest such $r$ is the primitive
degree of $\mathbb{A}$, $\gamma(\mathbb{A})$.

In [12], the authors prove some necessary conditions for a nonnegative tensor
to be a primitive one, and they also prove the following result.

######  Proposition 2.3.

([12] Remark 2.6) Let $\mathbb{A}$ be a nonnegative tensor with order $m$ and
dimension $n$. Then $\mathbb{A}$ is primitive if and only if there exists some
positive integer $r$ such that $M(\mathbb{A}^{r})>0.$ Furthermore, the
smallest such $r$ is the primitive degree of $\mathbb{A}$,
$\gamma(\mathbb{A})$.

In [12], the authors introduce some theoretical concepts of digraphs and
matrices.

Let $D=(V,A)$ denote a digraph on $n$ vertices. Loops are permitted, but no
multiple arcs. A $u\rightarrow v$ walk in $D$ is a sequence of vertices
$u,u_{1},\ldots,u_{k}=v$ and a sequence of arcs
$e_{1}=(u,u_{1}),e_{2}=(u_{1},u_{2}),\ldots,e_{k}=(u_{k-1},v)$, where the
vertices and the arcs are not necessarily distinct. We use the notation
$u\rightarrow u_{1}\rightarrow u_{2}\rightarrow\cdots\rightarrow
u_{k-1}\rightarrow v$ to refer to this $u\rightarrow v$ walk. A closed walk is
a $u\rightarrow v$ walk where $u=v$. A path is a walk with distinct vertices.
A cycle is a closed $u\rightarrow v$ walk with distinct vertices except for
$u=v$. The length of a walk $W$ is the number of arcs in $W$, denoted by
$l(W)$. A $k$-cycle is a cycle of length $k$, denoted by $C_{k}$.

######  Definition 2.4.

([12] Definition 2.9) Let $D=(V,A)$ denote a digraph on $n$ vertices. A
digraph $D^{\prime}=(V,A^{\prime})$ is called the reversed digraph of $D$
where $(j,i)\in A^{\prime}$ if and only if $(i,j)\in A$ for any $i,j\in V$,
denoted by $\overleftarrow{D}$.

Let $M=(m_{ij})$ be a square nonnegative matrix of order $n$. The associated
digraph $D(M)=(V,A)$ of $M$ (possibly with loops) is defined to be the digraph
with vertex set $V=\\{1,2,\ldots,n\\}$ and arc set $A=\\{(i,j)|m_{ij}\neq
0\\}$. The associated reversed digraph $\overleftarrow{D(M)}=(V,A^{\prime})$
of $M$ (possibly with loops) is defined to be the digraph with vertex set
$V=\\{1,2,\ldots,n\\}$ and arc set $A=\\{(j,i)|m_{ij}\neq 0\\}$. Clearly, the
associated reversed digraph of $M$ is the reversed digraph of the associated
digraph of $M$.

Let $N^{+}_{D}(i)=\\{j\in V(D)|(i,j)\in E(D)\\}$ denote the out-neighbors of
$i$ and $d^{+}_{i}=|N^{+}_{D}(i)|$ denote the out-degree of the vertex $i$ in
$D$. The following Proposition is the graph theoretical version of Proposition
2.7 in [12].

######  Proposition 2.5.

([12] Proposition 2.7) Let $\mathbb{A}$ be a nonnegative primitive tensor with
order $m$ and dimension $n$, $M(\mathbb{A})$ the majorization matrix of
$\mathbb{A}$. Then in the digraph
$\overleftarrow{D(M(\mathbb{A}))}=(V,A^{\prime})$, we have:

(i)  For each $j\in V$, the out-degree of the vertex $j$, $d^{+}_{j}\geq 1$
and $N^{+}_{D}(j)\neq\\{j\\}$.

(ii)  There exists at least a vertex $j\in V$, the out-degree of the vertex
$j$, $d^{+}_{j}\geq 2$.

The authors [12] also presented the definition of $j$-primitive degree for a
nonnegative tensor and obtained the following result.

######  Definition 2.6.

([12] Definition 2.13) Let $\mathbb{A}$ be a nonnegative tensor with order $m$
and dimension $n$. For a fixed integer $j\in[n]$, if there exists a positive
integer $k$ such that

$(M(\mathbb{A}^{k}))_{uj}>0,\hskip 5.69046pt{\mbox{f}or\,\,all}\,u\in[n],$

then $\mathbb{A}$ is called $j$-primitive and the smallest such integer $k$ is
called the $j$-primitive degree of $\mathbb{A}$, denoted by
$\gamma_{j}(\mathbb{A})$.

######  Proposition 2.7.

([12] Proposition 2.14) Let $\mathbb{A}$ be a nonnegative primitive tensor
with order $m$ and dimension $n$. Then $\gamma(\mathbb{A})=\max\limits_{1\leq
j\leq n}\\{\gamma_{j}(\mathbb{A})\\}.$

##  3 Necessary and sufficient conditions for nonnegative tensors to be
primitive

In this section, we will present necessary and sufficient conditions for a
nonnegative tensor to be a primitive one. Let $\mathbb{A}$ be a nonnegative
tensor with order $m$ and dimension $n$. For positive integers $k$ and
$j\in[n]$, we put

$S_{k}(\mathbb{A},j)=\\{u\in[n]\hskip 2.27626pt|\hskip
2.27626pt(M(\mathbb{A}^{k}))_{uj}>0\\},k=1,2,\ldots.$

Then $S_{1}(\mathbb{A},j)=\\{u\in[n]\hskip 2.27626pt|\hskip
2.27626pt(M(\mathbb{A}))_{uj}>0\\}=N_{\overleftarrow{D(M(\mathbb{A}))}}^{+}(j)$.

By the definitions of the general tensor product and the majorization matrix
of a tensor, we can show that

$(M(\mathbb{A}^{k+1}))_{uj}=\sum\limits_{j_{2},\ldots,j_{m}=1}^{n}a_{uj_{2}\cdots
j_{m}}(M(\mathbb{A}^{k}))_{j_{2}j}\cdots(M(\mathbb{A}^{k}))_{j_{m}j},$ (3.1)

it follows that $u\in S_{k+1}(\mathbb{A},j)$ if and only if there exist
indices $j_{2},\ldots,j_{m}\in S_{k}(\mathbb{A},j)$ and $a_{uj_{2}\cdots
j_{m}}>0$. Thus

$S_{k+1}(\mathbb{A},j)=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there
exist }j_{2},\ldots,j_{m}\in S_{k}(\mathbb{A},j)\mbox{ and }a_{uj_{2}\cdots
j_{m}}>0\\}.$ (3.2)

By the definition of $S_{k}(\mathbb{A},j)$, we have the following result.

######  Lemma 3.1.

Let $\mathbb{A}$ be a nonnegative tensor with order $m$ and dimension $n$.

(i)  Let $k,l,i,j$ be positive integers such that $1\leq i,j\leq n$. Suppose
that $S_{k}(\mathbb{A},i)=S_{l}(\mathbb{A},j)$, then
$S_{k+r}(\mathbb{A},i)=S_{l+r}(\mathbb{A},j)$ holds for every positive integer
$r$.

(ii)  For any $j\in[n]$, let $k$ be the least positive integer such that
$S_{k}(\mathbb{A},j)=[n]$. Then for any integer $l\geq k$,
$S_{l}(\mathbb{A},j)=[n]$.

###### Proof.

(i) Since $S_{k}(\mathbb{A},i)=S_{l}(\mathbb{A},j)$, by (3.2), we have

$S_{k+1}(\mathbb{A},i)=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there
exist }j_{2},\ldots,j_{m}\in S_{k}(\mathbb{A},i)\mbox{ and }a_{uj_{2}\cdots
j_{m}}>0\\}$

$=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there exist
}j_{2},\ldots,j_{m}\in S_{l}(\mathbb{A},j)\mbox{ and }a_{uj_{2}\cdots
j_{m}}>0\\}$

$=S_{l+1}(\mathbb{A},j).$

Therefore (i) follows by induction on $r$.

(ii) Let $k$ be the least positive integer such that
$S_{k}(\mathbb{A},j)=[n]$. We complete the proof by the following two cases.

Case 1:  $k>1$.

Then $S_{k-1}(\mathbb{A},j)\subset[n]$, by (3.2), we have

$[n]=S_{k}(\mathbb{A},j)$

$=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there exist
}j_{2},\ldots,j_{m}\in S_{k-1}(\mathbb{A},j)\subset[n]\mbox{ and
}a_{uj_{2}\cdots j_{m}}>0\\}$

$\subseteq\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there exist
}j_{2},\ldots,j_{m}\in S_{k}(\mathbb{A},j)=[n]\mbox{ and }a_{uj_{2}\cdots
j_{m}}>0\\}$

$=S_{k+1}(\mathbb{A},j)\subseteq[n]$.

Thus $S_{k+1}(\mathbb{A},j)=[n],$ and we can show $S_{k+r}(\mathbb{A},j)=[n]$
for any nonnegative integer $r$ by induction on $r$.

Case 2:  $k=1$.

Then $S_{1}(\mathbb{A},j)=[n]$, i.e., $(M(\mathbb{A}))_{uj}>0$ for all
$u\in[n]$. By taking $j_{2}=j_{3}=\cdots=j_{m}=j$, it is easy to show that
$S_{2}(\mathbb{A},j)=[n]$. Therefore $S_{l}(\mathbb{A},j)=[n]$ for any
positive integer $l$ by induction on $l$. ∎

######  Remark 3.2.

Let $\mathbb{A}$ be a nonnegative tensor with order $m$ and dimension $n$.
Then for any $j\in[n]$, $\gamma_{j}(\mathbb{A})$ is the least positive integer
$k$ satisfying $S_{k}(\mathbb{A},j)=[n]$ by Definition 2.6.

Denote $e_{j}$ the vector (of dimension $n$) whose $j$th component is $1$ and
others are $0$ for any $j=1,\ldots,n$. Let $x_{j}^{(0)}=e_{j}$ and for any
nonnegative integer $k$, we define

$x^{(k+1)}_{j}=\mathbb{A}x^{(k)}_{j}.$

By the definition of the general tensor product by Shao, we know
$x_{j}^{(0)},x_{j}^{(1)},\ldots$ are vectors (of dimension $n$). Let

$T_{k}(\mathbb{A},j)=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{the
$u$th component of }x^{(k)}_{j}\mbox{ is larger than 0}\\}.$

By the definition of $x_{j}^{(1)}$, for $u\in[n]$, we have

$\left(x_{j}^{(1)}\right)_{u}=a_{uj\cdots j}=(M(\mathbb{A}))_{uj},$

it follows that $S_{1}(\mathbb{A},j)=T_{1}(\mathbb{A},j)$ by the definitions
of $S_{1}(\mathbb{A},j)$ and $T_{1}(\mathbb{A},j)$. Since

$\left(x^{(k+1)}_{j}\right)_{u}=\sum_{i_{2},\ldots,i_{m}=1}^{n}a_{ui_{2}\cdots
i_{m}}\left(x^{(k)}_{j}\right)_{i_{2}}\cdots\left(x^{(k)}_{j}\right)_{i_{m}},$

it follows that $\left(x^{(k+1)}_{j}\right)_{u}>0$ if there exist some indices
$i_{2},\ldots,i_{m}\in T_{k}(\mathbb{A},j)$ and $a_{ui_{2}\cdots i_{m}}>0$,
thus $S_{k+1}(\mathbb{A},j)=T_{k+1}(\mathbb{A},j)$. Now by induction on $k$
and the definitions of $S_{k}(\mathbb{A},j)$ and $T_{k}(\mathbb{A},j)$, we see
that $S_{k}(\mathbb{A},j)=T_{k}(\mathbb{A},j)$ for all $k$ and $j\in[n]$.
Therefore, we have

######  Theorem 3.3.

Let $\mathbb{A}$ be a nonnegative tensor with order $m$ and dimension $n$. For
a fixed integer $j\in[n]$, $\mathbb{A}$ is $j$-primitive if and only if there
exists some positive integer $k$ such that $x^{(k)}_{j}>0$ and the smallest
such integer $k$ is the $j$-primitive degree $\gamma_{j}(\mathbb{A})$.

######  Theorem 3.4.

Let $\mathbb{A}$ be a nonnegative tensor with order $m$ and dimension $n$.
Then $\mathbb{A}$ is primitive if and only if there exists some positive
integer $k$ such that $x^{(k)}_{j}>0$ for all $j\in[n]$. Furthermore, the
smallest such integer $k$ is the primitive degree $\gamma(\mathbb{A})$ and
$\gamma(\mathbb{A})\leq(n-1)^{2}+1$.

###### Proof.

By Proposition 2.3, Definition 2.6 and Theorem 3.3, we know that

$\mathbb{A}$ is primitive

$\Longleftrightarrow$ there exists some positive $k$ such that
$M(\mathbb{A}^{k})>0$

$\Longleftrightarrow$ for all $j\in[n]$, there exists some positive $k$ such
that $(M(\mathbb{A}^{k}))_{uj}>0$ for all $u\in[n]$

$\Longleftrightarrow$ for all $j\in[n]$, $\mathbb{A}$ is $j$-primitive

$\Longleftrightarrow$ for all $j\in[n]$, there exists some positive integer
$k$ such that $x^{(k)}_{j}>0$.

Thus by Theorem 1.1, Proposition 2.7, Theorem 3.3 and the above arguments, we
know that the smallest such integer $k$ is the primitive degree
$\gamma(\mathbb{A})$ and $\gamma(\mathbb{A})\leq(n-1)^{2}+1$. ∎

##  4 Proof of the main result

By the relation between matrices and digraphs, we know that

$(A^{k})_{uj}>0\Longleftrightarrow\mbox{ there exists a walk of length $k$
from $u$ to $j$ in the digraph }D(A)$

$\Longleftrightarrow\mbox{ there exists a walk of length $k$ from $j$ to $u$
in the digraph }\overleftarrow{D(A)}.$

Then we obtain the following proposition.

######  Proposition 4.1.

Let $A$ be a nonnegative matrix of order $n$, $j\in[n],k$ be positive
integers, $S_{k}(A,j)=\\{u\in[n]\hskip 2.27626pt|\hskip
2.27626pt(A^{k})_{uj}>0\\}$. Then

$S_{k}(A,j)=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there exists a
walk of length $k$ from $j$ to $u$ in the digraph }\overleftarrow{D(A)}\\}.$

######  Lemma 4.2.

Let $\mathbb{A}$ be a nonnegative tensor with order $m$ and dimension $n$ such
that $a_{ii_{2}\cdots i_{m}}=0$ if $i_{2}\cdots i_{m}\not=i_{2}\cdots i_{2}$
for any $i\in[n]$. Then for any positive integers $j\in[n]$ and $k$,

$S_{k}(\mathbb{A},j)=S_{k}(M(\mathbb{A}),j).$ (4.1)

###### Proof.

We prove $S_{k}(\mathbb{A},j)=S_{k}(M(\mathbb{A}),j)$ by induction on $k$.
Clearly, $k=1$ is obvious by the fact $S_{1}(\mathbb{A},j)=\\{u\in[n]\hskip
2.27626pt|\hskip
2.27626pt(M(\mathbb{A}))_{uj}>0\\}=N_{\overleftarrow{D(M(\mathbb{A}))}}^{+}(j)=S_{1}(M(\mathbb{A}),j).$

Assume that (4.1) holds for $k=l\geq 1$. Then by (3.1), (3.2) and Proposition
4.1, we have

$S_{l+1}(\mathbb{A},j)$$=\\{u\in[n]\hskip 2.27626pt|\hskip
2.27626pt(M(\mathbb{A}^{l+1}))_{uj}>0\\}$

$=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there exist
}j_{2},\ldots,j_{m}\in S_{l}(\mathbb{A},j)\mbox{ and }a_{uj_{2}\cdots
j_{m}}>0\\}$

$=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there exist }v\in
S_{l}(\mathbb{A},j)\mbox{ and }a_{uv\cdots v}>0\\}$

$=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there exist }v\in
S_{l}(M(\mathbb{A}),j)\mbox{ and }(M(\mathbb{A}))_{uv}>0\\}$

$=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there exists a walk of
length $l$ from $j$ to $v$ and arc $(v,u)$ in
}\overleftarrow{D(M(\mathbb{A}))}\\}.$

$=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there exists a walk of
length $l+1$ from $j$ to $u$ in }\overleftarrow{D(M(\mathbb{A}))}\\}.$

$=S_{l+1}(M(\mathbb{A}),j)$.

Thus, for any positive integers $j\in[n]$ and $k$,
$S_{k}(\mathbb{A},j)=S_{k}(M(\mathbb{A}),j)$ holds. ∎

######  Lemma 4.3.

([12] Corollary 3.4) Let $\mathbb{A}$ be a nonnegative primitive tensor with
order $m$ and dimension $n$ such that $a_{ii_{2}\cdots i_{m}}=0$ if
$i_{2}\cdots i_{m}\not=i_{2}\cdots i_{2}$ for any $i\in[n]$. If
$M(\mathbb{A})$ is primitive, then $\gamma(\mathbb{A})=\gamma(M(\mathbb{A})).$

Let $M_{1}=\left(\begin{array}[]{ccccc}0&0&\cdots&1&1\\\ 1&0&\cdots&0&0\\\
0&1&\cdots&0&0\\\ 0&0&\ddots&0&0\\\ 0&0&\cdots&1&0\\\ \end{array}\right)$. It
is well known that $M_{1}$ is primitive, and $\gamma(M_{1})=(n-1)^{2}+1$.

$\textstyle{n}$$\textstyle{\hskip
3.0pt{n-1}}$$\textstyle{\mathrm{1}}$$\textstyle{2}$$\textstyle{\hskip
3.0pt{n-2}}$ $\mbox{ \qquad Figure 1. digraph }\overleftarrow{D(M_{1})}$

Let $\mathbb{A}_{0}$ be the nonnegative primitive tensor with order $m$ and
dimension $n$ such that $a_{ii_{2}\cdots i_{m}}=0$ if $i_{2}\cdots
i_{m}\not=i_{2}\cdots i_{2}$ for any $i\in[n]$, and $M(\mathbb{A}_{0})=M_{1}$.
Then by Lemma 4.2, we have $S_{k}(\mathbb{A}_{0},j)=S_{k}(M_{1},j)$ for any
$j\in[n]$ and any positive integer $k$, and by Lemma 4.3, we have
$\gamma(\mathbb{A}_{0})=(n-1)^{2}+1$.

The following result is well known.

######  Proposition 4.4.

Let $a,b$ be positive integers, if $a,b$ are coprime $(g.c.d.(a,b)=1)$, then
equation $ax+by=ab-a-b$ has no nonnegative integral solutions $(x,y)$.

######  Proposition 4.5.

Let $\mathbb{A}_{0}$ be the nonnegative primitive tensor with order $m$ and
dimension $n$ defined as above. Then
$\gamma_{n-1}(\mathbb{A}_{0})=n^{2}-3n+3$.

###### Proof.

By Remark 3.2, Proposition 4.1 and Lemma 4.2, we know

$\gamma_{n-1}(\mathbb{A}_{0})=\min\\{k\hskip 2.27626pt|\hskip
2.27626ptS_{k}(\mathbb{A}_{0},n-1)=[n]\\}$

$=\min\\{k\hskip 2.27626pt|\hskip 2.27626ptS_{k}(M_{1},n-1)=[n]\\}$

$=\min\\{k\hskip 2.27626pt|\hskip 2.27626pt\mbox{there exists a walk of length
$k$ from $n-1$ to $u$ in }\overleftarrow{D(M_{1})}\mbox{ for all }u\in[n]\\}$.

Let $W$ be any walk of length $n^{2}-3n+2$ from vertex $n-1$ to vertex $n$ in
$\overleftarrow{D(M_{1})}$. Then $W$ is a union of the unique path $P$ from
$n-1$ to $n$ (of length 1) and several cycles of length $n-1$ and several
cycles of length $n$. Let $l(W)$ be the length of $W$. Then there exist two
nonnegative integer $a,b$ such that

$n^{2}-3n+2=l(W)=1+na+(n-1)b,\hskip 2.84544pta\geq 0,\hskip 2.84544ptb\geq 0.$

Note that $n,n-1$ are coprime, by Proposition 4.4, we know that equation
$n^{2}-3n+1=nx+(n-1)y$ has no nonnegative integral solutions $(x,y)$. It is a
contradiction. Therefore there does not exist a walk of length $n^{2}-3n+2$
from $n-1$ to $n$ in $\overleftarrow{D(M_{1})}$, it implies
$S_{n^{2}-3n+2}(M_{1},n-1)\not=[n]$ and thus
$\gamma_{n-1}(\mathbb{A}_{0})>n^{2}-3n+2$.

Let $u\in[n]$ be any vertex in $\overleftarrow{D(M_{1})}$, $P$ be the path of
length $l=l(P)$ from vertex $n-1$ to vertex $u$, then

$l=\left\\{\begin{array}[]{ll}0,&\mbox{ if }u=n-1;\\\ 1,&\mbox{ if }u=n;\\\
u\mbox{ or }u+1,&\mbox{ if }u=1,2,\ldots,n-2.\end{array}\right.$

Let $C_{n-1}$ and $C_{n}$ be the cycles of length $n-1$ and $n$ in
$\overleftarrow{D(M_{1})}$, respectively. Take

$W=\left\\{\begin{array}[]{ll}(n-3)C_{n-1}+C_{n},&\mbox{ if }u=n-1;\\\
1+(n-2)C_{n-1},&\mbox{ if }u=1\mbox{ or }u=n;\\\
l+(l-3)C_{n-1}+(n-l)C_{n},&\mbox{ if }u=2,3,\ldots,n-2,\mbox{ where }3\leq
l\leq n-1.\end{array}\right.$

Clearly, the length of $W$, $l(W)=n^{2}-3n+3$. Therefore there exists a walk
of length $n^{2}-3n+3$ from $n-1$ to any $u\in[n]$ in
$\overleftarrow{D(M_{1})}$, it implies $S_{n^{2}-3n+3}(M_{1},n-1)=[n]$ and
thus $\gamma_{n-1}(\mathbb{A}_{0})\leq n^{2}-3n+3$.

Combining the above arguments, we have
$\gamma_{n-1}(\mathbb{A}_{0})=n^{2}-3n+3$. ∎

######  Remark 4.6.

Similar to the proof of Proposition 4.5, take

$W=\left\\{\begin{array}[]{ll}(n-2)C_{n-1},&\mbox{ if }u=n-1;\\\
l+(l-2)C_{n-1}+(n-l-1)C_{n},&\mbox{ if }u=1,2,\ldots,n-2,\mbox{ where }2\leq
l\leq n-1.\end{array}\right.$

We can show that there exists a walk of length $n^{2}-3n+2$ from $n-1$ to any
$u\in[n-1]$ in $\overleftarrow{D(M_{1})}$, it implies that
$S_{n^{2}-3n+2}(M_{1},n-1)=[n-1]$ and there does not exist a walk of length
$n^{2}-3n+2$ from $n-1$ to $n$ in $\overleftarrow{D(M_{1})}$.

Note that $S_{1}(\mathbb{A}_{0},n-1)=\\{1,n\\}$, then for any positive integer
$k$ with $1\leq k\leq n^{2}-3n+2$, we can show that
$2\leq|S_{k}(\mathbb{A}_{0},n-1)|=|S_{k}(M_{1},n-1)|\leq n-1$ by Proposition
4.1, Proposition 4.5 and Remark 4.6.

######  Proposition 4.7.

([11] Corollary 4.1 ) Let $\mathbb{A}$ be a nonnegative tensor with order $m$
and dimension $n$. If $M(\mathbb{A})$ is primitive, then $\mathbb{A}$ is also
primitive.

######  Proposition 4.8.

Let $m,n,k$ be positive integers with $m\geq n\geq 3$ and $1\leq k\leq
n^{2}-3n+2$, $\mathbb{A}_{k}$ be the nonnegative tensor with order $m$ and
dimension $n$ such that for any $i\in[n]$,

$(\mathbb{A}_{k})_{ii_{2}\cdots i_{m}}=\left\\{\begin{array}[]{ll}1,&\mbox{ if
}\\{i_{2},\ldots,i_{m}\\}=S_{k}(\mathbb{A},n-1);\\\
(\mathbb{A}_{0})_{ii_{2}\cdots i_{m}},&otherwise.\end{array}\right.$

Then $M(\mathbb{A}_{k})=M(\mathbb{A}_{0})=M_{1}$ and $\mathbb{A}_{k}$ is
primitive.

###### Proof.

Clearly, $\mathbb{A}_{k}$ is well-defined since $m\geq n$ and
$|S_{k}(\mathbb{A},n-1)|\leq n-1$.

Since $|S_{k}(\mathbb{A},n-1)|\geq 2$ for any $k$, then $i_{2}\ldots
i_{m}\not=i_{2}\ldots i_{2}$ when
$\\{i_{2},\ldots,i_{m}\\}=S_{k}(\mathbb{A},n-1)$, and thus
$M(\mathbb{A}_{k})=M(\mathbb{A}_{0})=M_{1}$ by the definition of the
majorization matrix of a tensor.

Note that $M_{1}$ is primitive, then $\mathbb{A}_{k}$ is primitive by
Proposition 4.7. ∎

######  Proposition 4.9.

Let $k$ be positive integer with $1\leq k\leq n^{2}-3n+2$. Then
$S_{1}(\mathbb{A}_{0},n-1),S_{2}(\mathbb{A}_{0},n-1),\ldots,S_{k}(\mathbb{A}_{0},n-1)$
are pairwise distinct proper subsets of $[n]$.

###### Proof.

Clearly,
$S_{1}(\mathbb{A}_{0},n-1),S_{2}(\mathbb{A}_{0},n-1),\ldots,S_{k}(\mathbb{A}_{0},n-1)$
are proper subsets of $[n]$ by $2\leq|S_{p}(\mathbb{A}_{0},n-1)|\leq n-1$ for
all $p\in[k]$.

If $S_{p}(\mathbb{A}_{0},n-1)=S_{q}(\mathbb{A}_{0},n-1)$ for $1\leq p<q\leq
k$, then by (i), (ii) of Lemma 3.1 and Proposition 4.5, we have

$S_{n^{2}-3n+2}(\mathbb{A}_{0},n-1)=S_{q+(n^{2}-3n+2-p)}(\mathbb{A}_{0},n-1)=S_{n^{2}-3n+3}(\mathbb{A}_{0},n-1)=[n],$

but $S_{n^{2}-3n+2}(\mathbb{A}_{0},n-1)=[n-1]\not=[n]$ by Remark 4.6, it is a
contradiction. Thus
$S_{1}(\mathbb{A}_{0},n-1),S_{2}(\mathbb{A}_{0},n-1),\ldots,S_{k}(\mathbb{A}_{0},n-1)$
are pairwise distinct. ∎

######  Theorem 4.10.

Let $m,n,k$ be positive integers with $m\geq n\geq 3$ and $1\leq k\leq
n^{2}-3n+2$, $\mathbb{A}_{k}$ be the nonnegative primitive tensor defined as
above. Then $\gamma(\mathbb{A}_{k})=\gamma_{n}(\mathbb{A}_{k})=n+k$.

###### Proof.

Firstly, we show that $S_{t}(\mathbb{A}_{k},n-1)=S_{t}(\mathbb{A}_{0},n-1)$
for any positive integer $t\in[k]$ by induction on $t$.

By Proposition 4.8, we have $S_{1}(\mathbb{A}_{k},n-1)=\\{u\in[n]\hskip
2.27626pt|\hskip 2.27626pt(M(\mathbb{A}_{k}))_{u,n-1}>0\\}=\\{u\in[n]\hskip
2.27626pt|\hskip
2.27626pt(M(\mathbb{A}_{0}))_{u,n-1}>0\\}=S_{1}(\mathbb{A}_{0},n-1)=\\{1,n\\}$.
Then $t=1$ holds.

Assume that $S_{t}(\mathbb{A}_{k},n-1)=S_{t}(\mathbb{A}_{0},n-1)$ for $t=l\geq
1$ holds. Then for $t=l+1\leq k$,
$S_{l}(\mathbb{A}_{0},n-1)\not=S_{k}(\mathbb{A}_{0},n-1)$ by Proposition 4.9.
If $i_{2},\ldots,i_{m}\in S_{l}(\mathbb{A}_{0},n-1)$, we have
$(\mathbb{A}_{k})_{ui_{2}\ldots
i_{m}}>0\Longleftrightarrow(\mathbb{A}_{k})_{ui_{2}\ldots
i_{m}}=(\mathbb{A}_{0})_{ui_{2}\ldots i_{m}}>0$ by the definition of
$\mathbb{A}_{k}$. Thus by (3.2),

$S_{l+1}(\mathbb{A}_{k},n-1)=\\{u\in[n]\hskip 2.27626pt|\hskip
2.27626pt\mbox{there exist }i_{2},\ldots,i_{m}\in
S_{l}(\mathbb{A}_{k},n-1)\mbox{ and }(\mathbb{A}_{k})_{ui_{2}\ldots
i_{m}}>0\\}$

$=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there exist
}i_{2},\ldots,i_{m}\in S_{l}(\mathbb{A}_{0},n-1)\mbox{ and
}(\mathbb{A}_{k})_{ui_{2}\ldots i_{m}}>0\\}$

$=\\{u\in[n]\hskip 2.27626pt|\hskip 2.27626pt\mbox{there exist
}i_{2},\ldots,i_{m}\in S_{l}(\mathbb{A}_{0},n-1)\mbox{ and
}(\mathbb{A}_{0})_{ui_{2}\ldots i_{m}}>0\\}$

$=S_{l+1}(\mathbb{A}_{0},n-1)$.

It follows that $S_{t}(\mathbb{A}_{k},n-1)=S_{t}(\mathbb{A}_{0},n-1)$ for any
positive integer $t$ with $1\leq t\leq k$, and thus
$S_{1}(\mathbb{A}_{k},n-1),S_{2}(\mathbb{A}_{k},n-1),\ldots,S_{k}(\mathbb{A}_{k},n-1)$
are pairwise distinct proper subsets of $[n]$ for $1\leq k\leq n^{2}-3n+2$ by
Proposition 4.9.

Since $(\mathbb{A}_{k})_{ii_{2}\cdots i_{m}}=1$ for any $i\in[n]$ when the set
$\\{i_{2},\ldots,i_{m}\\}=S_{k}(\mathbb{A}_{k},n-1)$, we have

$S_{k+1}(\mathbb{A}_{k},n-1)=\\{u\in[n]\hskip 2.27626pt|\hskip
2.27626pt\mbox{there exist }j_{2},\ldots,j_{m}\in S_{k}(\mathbb{A},n-1)\mbox{
and }(\mathbb{A}_{k})_{uj_{2}\cdots j_{m}}>0\\}=[n].$

and thus $\gamma_{n-1}(\mathbb{A}_{k})=k+1$ by Remark 3.2.

By the definition of $\mathbb{A}_{k}$, an easy computation shows that

$S_{1}(\mathbb{A}_{k},n-1)=S_{2}(\mathbb{A}_{k},n-2)=S_{3}(\mathbb{A}_{k},n-3)=\cdots=S_{n-1}(\mathbb{A}_{k},1)=S_{n}(\mathbb{A}_{k},n).$

By (i) of Lemma 3.1 and the definition of $j$-primitive degree, we have

$S_{1}(\mathbb{A}_{k},n-1)=S_{2}(\mathbb{A}_{k},n-2)$

$\Longrightarrow\left\\{\begin{array}[]{ll}([n]\not=)S_{1+r}(\mathbb{A}_{k},n-1)=S_{2+r}(\mathbb{A}_{k},n-2),&\mbox{
if }1\leq r\leq k-1;\\\
([n]=)S_{1+k}(\mathbb{A}_{k},n-1)=S_{2+k}(\mathbb{A}_{k},n-2),&\mbox{ if
}r=k.\end{array}\right.$

$\Longrightarrow\gamma_{n-2}(\mathbb{A}_{k})=k+2$.

Similarly, we can prove
$\gamma_{n-3}(\mathbb{A}_{k})=k+3,\ldots,\gamma_{1}(\mathbb{A}_{k})=n+k-1,\gamma_{n}(\mathbb{A}_{k})=n+k.$
Then following form Proposition 2.7, we have
$\gamma(\mathbb{A}_{k})=\max\limits_{1\leq j\leq
n}\gamma_{j}(\mathbb{A}_{k})=\gamma_{n}(\mathbb{A}_{k})=n+k$.∎

Proof of Theorem 1.2: Let $t$ be any positive integer with $1\leq
t\leq(n-1)^{2}+1$, we will show that there exists a nonnegative primitive
tensor $\mathbb{B}_{t}$ with order $m$ and dimension $n$ such that
$\gamma(\mathbb{B}_{t})=t$. We complete the proof by the following two cases.

Case 1:  $1\leq t\leq n$.

It is well known that there exists a primitive matrix $A_{t}$ of order $n$
such that $\gamma(A_{t})=t$. We define the tensor $\mathbb{B}_{t}$ to be the
nonnegative primitive tensor with order $m$ and dimension $n$ such that
$(\mathbb{B}_{t})_{ii_{2}\cdots i_{m}}=0$ if $i_{2}\cdots
i_{m}\not=i_{2}\cdots i_{2}$ for any $i\in[n]$, and $M(\mathbb{B}_{t})=A_{t}$.
Then $\gamma(\mathbb{B}_{t})=\gamma(A_{t})=t$ by Lemma 4.3.

Case 2:  $n+1\leq t\leq(n-1)^{2}+1$.

We choose $\mathbb{B}_{t}=\mathbb{A}_{t-n}$. Then
$\gamma(\mathbb{B}_{t})=n+(t-n)=t$ by Theorem 4.10. ∎

## References

  * [1] K. C. Chang, K. Pearson, and T. Zhang, Perron-Frobenius theorem for nonnegative tensors, Commun. Math. Sci. 6(2008), 507–520.
  * [2] K. C. Chang, K. Pearson, and T. Zhang, Primitivity, the convergence of the NQZ method, and the largest eigenvalue tensors, SIAM J. Matrix Anal. Appl. 32(2011), 806–819.
  * [3] A. L. Dulmage and N. S. Mendelsohn, Gaps in the exponent set of primitive matrices, Zllitwis J. Math. (1964), 8642–656.
  * [4] M. Lewin and Y. Vitek, A system of gaps in the exponent set of primitive matrices, Illinois J. Math. 25(1981), 87–98.
  * [5] L.H. Lim, Singular values and eigenvalues of tensors, a rational approach, in proceedings 1st IEEE international workshop on computational advances of adaptive processing (2005), 129–132.
  * [6] K. Pearson, Essentially positive tensors, Int. J. Algebra 4(2010),421–427.
  * [7] K. Pearson, Primitive tensors and convergence of an iterative process for the eigenvalues of a primitive tensor, arXiv: 1004-2423v1, 2010.
  * [8] L. Qi, Eigenvalues of a real supersymmetric tensor, Symbolic Comput. 40(2005), 1302–1324.
  * [9] H. Wielandt, Unzerlegbare, nicht negative matrizen, Math. Z. 52(1950), 642–648.
  * [10] J.Y. Shao, On a conjecture about the exponent set of primitive matrices, Linear Algebra Appl. 65(1985), 91–123.
  * [11] J.Y. Shao, A general product of tensors with applications, Linear Algebra and its Appl. 439(2013), 2350–2366.
  * [12] P.Z. Yuan, Z.L. He, and L.H. You, A conjecture on the primitive degree of Tensors, Linear Algebra and its Appl. 450(2014), 175–185.
  * [13] K.M. Zhang, On Lewin and Vitek’s conjecture about the exponent set of primitive matrices, Linear Algebra Appl. 96(1987), 101–108.