arXiv:1801.04086v1 [math.RA] 12 Jan 2018

Maximal and typical nonnegative ranks of
nonnegative tensors
Toshio SUMI∗, Mitsuhiro MIYAZAKI†and Toshio SAKATA‡

Abstract
Let N1 , . . . , Nd be positive integers with N1 ≤ · · · ≤ Nd . Set
N = N1 · · · Nd−1 . We show in this paper that an integer r is a typical
nonnegative rank of nonnegative tensors of format N1 × · · · × Nd if and
only if r ≤ N and r is greater than or equals to the generic rank of
tensors over C of format N1 ×· · ·×Nd . We also show that the maximal
nonnegative rank of nonnegative tensors of format N1 × · · · × Nd is N .
Keywords: tensor rank, typical rank, nonnegative rank, nonnegative
tensor
MSC:15A69, 14P10

1

Introduction

Recently high-dimensional array data are intensively studied in connection
with data analysis. In these areas of research, high-dimensional data are
called tensors. More precisely, a d-dimensional datum aligned in an N1 ×
· · · × Nd high-dimensional box form is called an N1 × · · · × Nd tensor or a
d-tensor of format N1 × · · · × Nd .
Let S be a set. The set of N1 ×· · ·×Nd tensors with entries in S is denoted
S N1 ×···×Nd . An element T ∈ S N1 ×···×Nd is denoted by T = (ti1 ···id )1≤j≤Nj or
simply T = (ti1 ···id ). The case where d = 2, S N1 ×N2 is nothing but the set of
N1 × N2 matrices with entries in S. If S is a field, the rank of an element
M ∈ S N1 ×N2 is defined in linear algebra. The rank of M is identical with
the minimum number r such that M can be expressed as a sum of r rank 1
matrices, where we set empty sum to be zero. Further, a nonzero matrix is
rank 1 if and only if it can be expressed as a product of a nonzero column
∗

Faculty of Arts and Science, Kyushu University, Fukuoka, Japan
Department of Mathematics, Kyoto University of Education, Kyoto, Japan
‡
Emeritus professor, Kyushu University, Fukuoka, Japan

†

1

vector and a nonzero row vector. We generalize the notion of rank to the
general case by using this characterization of ranks of matrices.
Suppose S is a subset of a commutative ring with identity which is
closed under addition and multiplication and contains 0 and 1. A nonzero
element T = (ti1 ···id ) ∈ S N1 ×···×Nd is defined to be S-rank 1 if there are
Q
vj = (vj1 , . . . , vjNj )⊤ ∈ S Nj for 1 ≤ j ≤ d such that ti1 ···id = dj=1 vjij for
any (i1 , . . . , id ). For a general element T ∈ S N1 ×···×Nd , we define the S-rank
of T as the minimum number r such that T can be expressed as a sum of r
S-rank 1 tensors. The S-rank of T is denoted rankS T . We attach the prefix
“S-” since the rank depends on S. In fact, there is an element of R2×2×2 such
that rankR T = 3 and rankC T = 2.
In this paper, we consider the case where S = R≥0 := {x ∈ R | x ≥
0}. Since it is important to work in the set of nonnegative real numbers
in the statistical point of view, R≥0 -rank is studied by several researchers
1 ×···×Nd
[ARSZ, QCL]. They called an element RN
a nonnegative tensor and
≥0
called the R≥0 -rank nonnegative rank. Allman et al. [ARSZ] showed that
under mild condition, nonnegative rank of a nonnegative tensor is identical
with its R-rank if its R-rank is less than or equals to 2.
1 ×···×Nd
We consider in this paper typical nonnegative ranks of RN
(see sec≥0
tion 2 for definition). Suppose that N1 ≤ · · · ≤ Nd and set N = N1 · · · Nd−1 .
We show that r is a typical nonnegative rank of nonnegative N1 × · · · × Nd
tensors if and only if r ≤ N and r is greater than or equals to the minimal
typical R-rank. In the way of proving this fact, we also show that N is the
maximal nonnegative rank of N1 × · · · × Nd nonnegative tensors.

2

Preliminaries

In this section, we fix notation, state definitions and recall some basic facts
in order to prepare for the main argument. Let F be the real number field R
or the complex number field C and let n be a positive integer. We denote by
Fn the vector space of n-dimensional column vectors with entries in F and by
ei the element of Fn whose i-th entry is 1 and other entries are 0. By abuse
of notation, we use the same symbol ei to express an element of Fn and Fm
even if n 6= m. The meaning will be clear from the context.
Let N1 , . . . , Nd be positive integers. Since an element FN1 ⊗F · · · ⊗F FNd
is expressed uniquely as
N1
X

i1 =1

···

Nd
X

ti1 ···id ei1 ⊗ · · · ⊗ eid ,

id =1

2

we identify FN1 ×···×Nd and FN1 ⊗F · · · ⊗F FNd by the correspondence
(ti1 ···id ) ↔

N1
X

i1 =1

···

Nd
X

ti1 ···id ei1 ⊗ · · · ⊗ eid .

id =1

We introduce the Euclidean topology to FN1 ×···×Nd by identifying FN1 ×···×Nd
with FN1 ···Nd .
Let S be R≥0 := {x ∈ R | x > 0}, R or C. We interpret F = R if S = R≥0
or S = R and F = C if S = C in the rest of this section. We define
ΦS1 : S N1 × · · · × S Nd → S N1 ×···×Nd
by ΦS1 ((v11 , . . . , v1N1 )⊤ , . . . , (vd1 , . . . , vdNd )⊤ ) = (v1i1 · · · vdid )1≤ij ≤Nj . Further,
we define for r ≥ 2, ΦSr : (S N1 × · · · × S Nd )r → S N1 ×···×Nd by ΦSr (a1 , . . . , ar ) =
ΦS1 (a1 ) + · · · + ΦS1 (ar ). We define the S-rank of a nonzero element T of
S N1 ×···×Nd is r if T ∈ ImΦSr \ ImΦSr−1 , where we interpret ImΦS0 to be the set
consists of zero element only, and we define the S-rank of the zero element
of S N1 ×···×Nd to be 0. If the set of elements S N1 ×···×Nd whose S-rank is r
contains a nonempty Euclidean open subset of FN1 ×···×Nd , we say that r is a
typical S-rank of N1 × · · · × Nd tensors.
It is known that there exists a unique typical C-rank of N1 × · · · × Nd
tensors over C which is called the generic rank of N1 × · · · × Nd tensors over
C and is denoted grankC (N1 , . . . , Nd ). Further, it is known that the generic
rank of N1 × · · · × Nd tensors over C is identical with the minimal typical
R-rank of N1 × · · · × Nd tensors. See [BT, Theorem 2] or [SSM, Chapter 6].
In this paper, we consider the case where S = R≥0 . In this case an
element of S N1 ×···×Nd is called a nonnegative tensor of format N1 × · · · × Nd
or an N1 × · · · × Nd nonnegative tensor, an S-rank is called a nonnegative
rank and a typical S-rank is called a typical nonnegative rank. In the case
where d = 2, i.e. the matrix case is studied extensively as a nonnegative
matrix factorization.


1 0 1 0
0 1 0 1

Example 2.1 The matrix 
1 0 0 1 has R-rank 3 and nonnegative
0 1 1 0
rank 4. In fact, the column vectors of this matrix span the convex polyhedral cone {(x1 , x2 , x3 , x4 )⊤ ∈ R≥0 | x1 + x2 − x3 − x4 = 0}. See [Sta,
Example 3.6].

3

3

Main result

In this section, we study maximal and typical nonnegative ranks of N1 ×· · ·×
Nd nonnegative tensors with N1 ≤ · · · ≤ Nd . Set N = N1 · · · Nd−1 . First we
state the following upper bound of nonnegative ranks of nonnegative tensors
of format N1 × · · · × Nd .
Lemma 3.1 Let T be a nonnegative tensor of format N1 × · · · × Nd . Then
rankR≥0 T ≤ N.
Proof Set T = (ti1 ···id ). Then
T =

N1
X

i1 =1

Nd−1

···

X

ei1 ⊗ · · · ⊗ eid−1 ⊗ (ti1 ···id−1 1 , . . . , ti1 ···id−1 Nd )⊤ .

id−1 =1

Thus, rankR≥0 T ≤ N.
Next we show the following.
Lemma 3.2 N is a typical nonnegative rank of nonnegative tensors of format N1 × · · · × Nd .
Proof Set I = {(i1 , . . . , id ) | 1 ≤ ij ≤ Nj for
P 1 ≤ j ≤ d and i1 + · · · + id ≡ 0
(mod Nd )}. Then #I = N. Set also T0 = (i1 ,...,id )∈I ei1 ⊗ · · · ⊗ eid and ǫ =
1
1 ×···×Nd
. We show that if T ∈ RN
and ||T − T0 || < ǫ, then rankR≥0 T = N,
≥0
3N
where ||T − T0 || denotes the Euclidean norm.
Assume the contrary and set r = rankR≥0 T . Then by Lemma 3.1, we
P
N
see that r < N. Further set T = rk=1 a1k ⊗ · · · ⊗ adk , where ajk ∈ R≥0j
for any 1 ≤ j ≤ d and 1 ≤ k ≤ r. Set ajk = (ajk1 , . . . , ajkNj )⊤ and for
(i1 , . . . , id ) ∈ I, we set
K(i1 ,...,id ) := {k | 1 ≤ k ≤ r, ajkl < ajkij for any 1 ≤ j ≤ d and l 6= ij .}
It is clear that if (i1 , . . . , id ) 6= (ı′1 , . . . , ı′d ), then K(i1 ,...,id ) ∩ K(ı′1 ,...,ı′d ) = ∅.
Suppose that (i1 , . . . , id ) ∈ I and k0 6∈ K(i1 ,...,id ) . Then there are j and
l with ij 6= l and ajk0 l ≥ ajk0 ij . Since (i1 , . . . , ij−1 , l, ij+1 , . . . , id ) 6∈ I by the
definition of I, we see that (i1 , . . . , ij−1 , l, ij+1 , . . . id ) entry of T0 is 0. Thus,
(i1 , . . . , ij−1, l, ij+1 , . . . id ) entry of T is less than ǫ. Therefore,
a1k0 i1 · · · ajk0 ij · · · adk0 id ≤ a1k0 i1 · · · ajk0 l · · · adk0 id < ǫ,
since ajki ≥ 0 for any j, k and i.
4

P
Set T ′ = k6∈K(i ,...,i ) a1k ⊗ · · · ⊗ adk . Then, by the above argument, we
1
d
see that the (i1 , . . . , id ) entry of T ′ is less than ǫ(r − #K(i1 ,...,id ) ) < ǫN. On
the other hand, since (i1 , . . . , id ) entry of T0 is 1, and ||T − T0 || < ǫ, we see
1
that (i1 , . . . , id ) entry of T is greater than 1 − ǫ. Since ǫ = 3N
, we see that
′
1 − ǫ > ǫN and therefore, T 6= T , i.e. K(i1 ,...,id ) 6= ∅. Thus, we see that
N = #I ≤ r since K(i1 ,...,id ) ∩ K(ı′1 ,...,ı′d ) = ∅ if (i1 , . . . , id ) 6= (ı′1 , . . . , ı′d ). This
contradicts to the assumption that r < N.
By Lemmas 3.1 and 3.2, we see the following fact.
Theorem 3.3 The maximal nonnegative rank of nonnegative tensors of format N1 × · · · × Nd is N.
Next we consider the set of typical nonnegative ranks of nonnegative
tensors of format N1 × · · · × Nd . First we recall the following fact.
Lemma 3.4 (see e.g. [SSM, Chapter 6]) An integer r is greater than
or equals to grankC (N1 , . . . , Nd ) if and only if the Jacobian of ΦCr is row
full rank for some (a1 , . . . , ar ) ∈ (CN1 × · · · × CNd )r . In particular, if
r ≥ grankC (N1 , . . . , Nd ), then there is a nonzero maximal minor of Jacobian of ΦCr as a polynomial.
Note that every Jacobian of ΦCr as a polynomial is a polynomial with coefficients in Z. We also note the following basic fact.
Lemma 3.5 Let R be an integral domain, X1 , . . . , Xn indeterminates and
A1 , . . . , An infinite subsets of R. Then for any nonzero polynomial f ∈
R[X1 , . . . , Xn ], there are a1 , . . . , an with aj ∈ Aj for 1 ≤ j ≤ n such that
f (a1 , . . . , an ) 6= 0.
The following fact is easily verified.
Lemma 3.6 Let T be a nonnegative tensor with nonnegative rank s. Suppose
T = T1 + · · · + Ts with rankR≥0 Tj = 1 for 1 ≤ j ≤ s, then
rankR≥0 (T1 + · · · + Tr ) = r
for any 1 ≤ r ≤ s.
We also note the following fact.
Lemma 3.7 Let r be a typical nonnegative rank of nonnegative tensors of
format N1 × · · · × Nd . Then r ≥ min(trankR (N1 , . . . , Nd )).
5

Proof By the definition of typical nonnegative rank, there is a nonempty
1 ×···×Nd
Euclidean open subset U of RN
such that rankR≥0 T = r for any T ∈ U.
≥0
Since rankR T ≤ rankR≥0 T , U consists of tensors whose R-rank is less than
or equals to r. Therefore, r ≥ min(trankR (N1 , . . . , Nd )).
Now we state the following.
Theorem 3.8 The set of typical nonnegative ranks of nonnegative tensors
of format N1 × · · · × Nd is {r | r ∈ Z, grankC (N1 , . . . , Nd ) ≤ r ≤ N}.
Proof Let r be a typical nonnegative rank of nonnegative tensors of format
N1 × · · · × Nd . By Lemma 3.1, we see that r ≤ N. Further, by Lemma 3.7,
r ≥ min(trankR (N1 , . . . , Nd )) = grankC (N1 , . . . , Nd ).
Conversely assume that grankC (N1 , . . . , Nd ) ≤ r ≤ N. By Lemma 3.4, we
see that there is a maximal minor f of the Jacobian of ΦCr which is nonzero as
a polynomial. Since N is a typical nonnegative rank of nonnegative tensors
of format N1 × · · · × Nd , we see that there is a Euclidean open subset O of
1 ×···×Nd
RN
such that rankR≥0 T = N for any T ∈ O.
≥0
Since
R
Nd N
N1 ×···×Nd
1
ΦN≥0 : (RN
≥0 × · · · × R≥0 ) → R≥0
is continuous and identical with
Nd r
Nd N −r
N1
1 ×···×Nd
1
(RN
→ RN
,
≥0 × · · · × R≥0 ) × (R≥0 × · · · × R≥0 )
≥0
R

R

(A1 , A2 ) 7→ Φr ≥0 (A1 ) + ΦN≥0
−r (A2 ), we see that there are open subsets U1 of
R
Nd r
Nd N −r
N1
1
(R≥0 × · · · × R≥0 ) and U2 of (RN
such that Φr ≥0 (U1 ) +
≥0 × · · · × R≥0 )
R
ΦN≥0
−r (U2 ) ⊂ O.
By Lemma 3.5, we see that there exists A1 ∈ U1 such that f (A1 ) 6= 0.
R
Therefore, by the inverse function theorem, we see that ImΦr ≥0 (U1 ) contains
R
an open neighborhood O ′ of Φr ≥0 (A1 ). On the other hand, by Lemma 3.6,
R
we see that every element of ImΦr ≥0 (U1 ) has nonnegative rank r. Thus, we
see that every element of O ′ has nonnegative rank r. Therefore, r is a typical
nonnegative rank.
Remark 3.9 The fact that the set of typical nonnegative ranks form a consecutive integers can also be proved along the same line with [BBO, Theorem
2.2].

6

References
[ARSZ] Elizabeth S. Allman, John A. Rhodes, Bernd Sturmfels and Piotr
Zwiernik, Tensors of nonnegative rank two, Linear Algebra and its
Applications 473 (2015) 37–53.
[BT]

Grigoriy Blekherman and Zach Teitler, On maximum, typical and
generic ranks. Mathematische Annalen 362 1021-1031, (2015).

[BBO] Alessandra Bernardi, Grigoriy Blekherman and Giorgio Ottaviani,
On real typical ranks, arXiv:1512.01853v1 (2015).
[QCL]

Yang Qi, Pidrre Comon and Lek-Heng Lim, Semialgebraic geometry
of nonnegative tensor rank, SIAM J. Matrix Anal. Appl. 37 (2016)
1556–1580.

[SSM]

Toshio Sakata, Toshio Sumi and Mitsuhiro Miyazaki, Algebraic and
Computational Aspects of Real Tensor Ranks, Springer, (2016)

[Sta]

Richard P. Stanley, Combinatorics and commutative algebra. Second edition. Progress in Mathematics, 41 Birkhauser Boston, Inc.,
Boston, MA, (1996)

7

