ISSN 2590-9770
The Art of Discrete and Applied Mathematics 4 (2021) #P1.05
https://doi.org/10.26493/2590-9770.1280.4da
(Also available at http://adam-journal.eu)
An alternate proof of the monotonicity of the
number of positive entries in nonnegative matrix
powers*
Slobodan Filipovski†
FAMNIT, University of Primorska, Glagoljaška 8, Koper, Slovenia
Comenius University, Mlynská dolina, 842 48, Bratislava, Slovakia
Received 6 December 2018, accepted 19 July 2020, published online 23. January 2021
Abstract
Let A be a nonnegative real matrix of order n and f(A) denote the number of positive
entries in A. In 2018, Xie proved that if f(A) ≤ 3 or f(A) ≥ n2 − 2n + 2, then the
sequence (f(Ak))∞k=1 is monotone for positive integers k. In this note we give an alternate
proof of this result by counting walks in a digraph of order n.
Keywords: Digraphs, walks, monotonicity, adjacency matrix.
Math. Subj. Class. (2020): 05C20, 05C81, 15B48
1 Introduction
A matrix is nonnegative (respectively, positive) if all its entries are nonnegative (re-
spectively, positive) real numbers. Nonnegative matrices are widely applied in science,
engineering and technology, see [1] and [2]. A nonnegative square matrix A is said to be
primitive if there exists a positive integer k such that Ak is positive. By f(A) we denote
the number of positive entries in A. In [4] Šidák proved that there exists a primitive matrix
A of order 9 satisfying f(A) = 18 > f(A2) = 16. Motivated by this observation, in [5]
Xi proved that if f(A) ≤ 3 or f(A) ≥ n2 − 2n + 2, then the sequence (f(Ak))∞k=1 is
monotone for positive integers k. The proof of this result relies on linear algebra approach
considering A as a 0 − 1 square matrix, that is, a matrix from the vector space Mn(R)
whose entries are either 0 or 1. Recall, Mn(R) is the set of all square matrices of size n
under the ordinary addition and scalar multiplication of matrices. Clearly, the above re-
striction on the entries of A is valid since the value of each positive entry in A does not
*We would like to thank the anonymous referee for helpful comments which have improved the paper.
†Supported by VEGA 1/0423/20.
E-mail address: slobodan.filipovski@famnit.upr.si (Slobodan Filipovski)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Art Discrete Appl. Math. 4 (2021) #P1.05
effect f(Ak) for all positive integers k. In this note we give an alternate proof of this result
using counting method from graph theory.
By a digraph we mean a structure G = (V,A), where V (G) is a finite set of vertices,
and A(G) is a set of ordered pairs (u, v) of vertices u, v ∈ V (G) called arcs. The order of
the digraph G is the number of vertices in G. An in-neighbour of a vertex v in a digraph G
is a vertex u such that (u, v) ∈ A(G). Similarly, an out-neighbour of a vertex v is a vertex
w such that (v, w) ∈ A(G). The in-degree, respectively out-degree, of a vertex v ∈ V (G)
is the number of its in-neighbours, respectively out-neighbours, in G. A walk w of length
k in G is an alternating sequence (v0a1v1a2 . . . akvk) of vertices and arcs in G such that
ai = (vi−1, vi) for each i. If the arcs a1, a2, . . . , ak of a walk w are distinct, w is called
a trail. A cycle Ck of length k is a closed trial of length k > 0 with all vertices distinct
(except the first and the last).
If a digraph G has n vertices v1, v2, . . . , vn, a useful way to represent it is with an n×n
matrix of zeros and ones called its adjacency matrix, AG. The ij-th entry of the adjacency
matrix, (AG)ij , is 1 if there is an arc from vertex vi to vertex vj and 0 otherwise. That is,
(AG)ij =
{
1, if (vi, vj) ∈ A(G)
0, otherwise
The length-k walk counting matrix for an n-vertex digraph G is the n × n matrix C such
that
Cuv := the number of length-k walks from u to v.
The main result in this note is based on the following well-known result:
Theorem 1.1 ([3]). The length-k counting matrix of a digraph, G, is (AG)k, for all k ∈ N.
2 Main results
In the following proposition we reprove Theorem 1 and Theorem 2 from [5].
Proposition 2.1. Let A be a 0 − 1 matrix of order n. If f(A) ≤ 3, then the sequence
(f(Ak))∞k=1 is monotone.
Proof. Let G be a digraph on n vertices v1, v2, . . . , vn corresponding to the adjacency
matrix A, that is, there is an arc from vertex vi to vertex vj in G (vi → vj) if (A)ij = 1.
We deal with four possible cases.
1. The case when f(A) = 0 is trivial. Since Ak = On, then f(Ak) = 0 for any positive
integer k.
2. If f(A) = 1, then G contains exactly one arc a = (vi, vj).
• If vi = vj , then for any positive integer k there exists a unique k-walk from
vi to vi. Therefore (Ak)ii = 1. Moreover, since there exists no other k-walk
between the vertices of G, the remaining n2− 1 entries of Ak are zeros. In this
case, for any positive integer k we have f(Ak) = 1.
• If vi 6= vj , then (A)ij = 1. It is easy to see that G does not contain a walk of
length k ≥ 2, that is, for any k ≥ 2 Ak is a zero matrix. Therefore, for any
k ≥ 2 we obtain 1 = f(A) > f(Ak) = 0.
S. Filipovski: An alternate proof of the monotonicity of the number of positive entries 3
3. Let f(A) = 2, i.e., let a1 = (vi, vj) and a2 = (vr, vs) be two distinct arcs of G.
If G contains two loops, then we consider one possible case:
• Let vi = vj 6= vr = vs. For any positive integer k ≥ 1 there exists exactly
one k-walk from vertex vi to vertex vj and exactly one k-walk from vertex vr
to vertex vs. It yields f(Ak) = 2.
If G contains one loop, we consider the following three cases:
• If vi = vj = vr 6= vs, then f(Ak) = 2 for any positive integer k ≥ 1.
• If vi = vj = vs 6= vr, then f(Ak) = 2 for any positive integer k ≥ 1.
• If vi = vj , vr 6= vs, vi 6= vr and vi 6= vs, then f(Ak) = 1 for any positive
integer k ≥ 2.
If G does not contain loops, then we focus on the cases when at least one of the
vertices vi, vj , vr and vs has positive in-degree and positive out-degree. Otherwise,
G does not contain a k-walk for k ≥ 2.
• If vi 6= vj = vr 6= vs and vi 6= vs, then G contains exactly one 2-walk from
vi to vs. Moreover, there is no k-walk when k ≥ 3. Thus 2 = f(A) > 1 =
f(A2) > f(Ak) = 0 for any positive integer k ≥ 3.
• If vi 6= vj = vr 6= vs and vi = vs, then f(Ak) = 2 for any positive integer k.
4. The proof when f(A) = 3 follows the same reasoning as the previous cases.
Let a1 = (vi, vj), a2 = (vr, vs) and a3 = (vp, vt) be three distinct arcs of G.
If G contains three loops, then we have:
• Let vi = vj , vr = vs and vp = vt. It is easy to see that f(Ak) = 3 for any
positive integer k ≥ 1.
Similarly, if G contains two loops, we treat the following cases.
• If vi = vj , vr = vs, vp 6= vt and if there is no common vertex between the arcs
a1, a2 and a3, then f(Ak) = 2 for any positive integer k ≥ 2.
• If vi = vj = vp 6= vt = vr = vs, then f(Ak) = 3 for any positive integer
k ≥ 1.
• If vi = vj = vp 6= vt 6= vr = vs, then f(Ak) = 3 for any positive integer
k ≥ 1.
• If vi = vj = vt 6= vp 6= vr = vs, then f(Ak) = 3 for any positive integer
k ≥ 1.
If G contains one loop, we obtain the following cases.
• If vi = vj , vr = vt 6= vs = vp and vi 6= vr, vi 6= vs, then f(Ak) = 3 for any
positive integer k ≥ 1.
• If vi = vj , vr 6= vs, vp 6= vt and if there is no a common vertex between the
arcs a1, a2 and a3, then f(Ak) = 1 for any positive integer k ≥ 2.
• If vi = vj , vr 6= vs = vp 6= vt, vr 6= vt and if there is no common vertex
between a1 and a2 and a1 and a3, then f(A2) = 2 and f(Ak) = 1 for any
positive integer k ≥ 3.
4 Art Discrete Appl. Math. 4 (2021) #P1.05
• If vi = vj 6= vr = vp 6= vt, vr 6= vs, vs 6= vt, vi 6= vs and vi 6= vt, then
f(Ak) = 1 for any positive integer k ≥ 2.
• If vi = vj , vr 6= vs = vt 6= vp, vr 6= vp and if there is no common vertex
between a1 and a2 and a1 and a3, then f(Ak) = 1 for any positive integer
k ≥ 2.
• If vi = vj = vr 6= vs, vp 6= vt and if there is no common vertex between a1
and a3 and between a2 and a3 , then f(Ak) = 2 for any positive integer k ≥ 2.
• If vi = vj = vs 6= vr, vp 6= vt and if there is no common vertex between a1
and a3 and between a2 and a3 , then f(Ak) = 2 for any positive integer k ≥ 2.
• If vi = vj = vr 6= vs = vp 6= vt and vi 6= vt, then f(Ak) = 3 for any positive
integer k ≥ 1.
• If vi = vj = vs 6= vr = vp 6= vt and vi 6= vt, then f(Ak) = 2 for any positive
integer k ≥ 2.
• If vi = vj = vs 6= vr = vt 6= vp and vi 6= vp, then f(Ak) = 3 for any positive
integer k ≥ 1.
• If vi = vj = vr 6= vs = vt 6= vp and vi 6= vp, then f(Ak) = 2 for any positive
integer k ≥ 2.
• If vi 6= vj = vr = vs = vp 6= vt and vi 6= vt, then f(Ak) = 3 for any positive
integer k ≥ 1.
• If vi 6= vj = vr = vs = vt 6= vp, then f(Ak) = 3 for any positive integer
k ≥ 1.
• If vj 6= vi = vr = vs = vp 6= vt, then f(Ak) = 3 for any positive integer
k ≥ 1.
• If vi 6= vj = vr = vs = vp 6= vt and vi = vt, then f(Ak) = 4 for any positive
integer k ≥ 2.
If G does not contain loops, then each k-walk of G, k ≥ 3, contains at least two
vertices of positive in-degree and positive out-degree. Based on this observation we
consider the following cases.
• If vi = vs 6= vj = vr, vp 6= vt and if there is no common vertex between the
arcs a1 and a3, then f(Ak) = 2 for any positive integers k ≥ 2.
• If vi 6= vj , vr 6= vs, vp 6= vt, vj = vr, vs = vp and vt = vi, then f(Ak) = 3
for any positive integer k ≥ 1.
• If vi 6= vj , vr 6= vs, vp 6= vt, vj = vr, vs = vp and vi 6= vt 6= vj , then
f(A2) = 2, f(A3) = 1 and f(Ak) = 0 for any positive integer k ≥ 4.
• If vt 6= vp = vs = vi 6= vj = vr and vj 6= vt, then f(Ak) = 3 for any positive
integer k ≥ 1.
• If vp 6= vt = vs = vi 6= vj = vr and vj 6= vp, then f(Ak) = 3 for any positive
integer k ≥ 1.
The following result is a reproof of Theorem 5 from [5].
Theorem 2.2. Let A be a 0−1 matrix of order n. If f(A) ≥ n2−2n+2, then the sequence
(f(Ak))∞k=1 is non-decreasing.
S. Filipovski: An alternate proof of the monotonicity of the number of positive entries 5
Proof. Let G be a digraph on n vertices v1, v2, . . . , vn which corresponds to the matrix A
(A is the adjacency matrix of G consisting of at most 2n−2 zeros). According to Theorem
1.1, proving f(Ak+1) ≥ f(Ak) for every positive integer k, is equivalent to proving that
the number of pairs of vertices of G for which there exists at least one (k + 1)-walk is
greater or equal than the number of pairs of vertices of G for which there exists at least one
k-walk.
Let us suppose that G contains a walk of length k, i.e. let w = (vi, vi+1, . . . , vj) be a
k-walk from vi to vj = vi+k. Thus (Ak)ij ≥ 1. We prove the following five claims.
Claim 1: If w contains at least four distinct vertices, then there exists at least one (k+1)-
walk from vi to vj . Therefore (Ak+1)ij ≥ 1.
Let w = (vi, vi+1, . . . , vj) contain at least four distinct vertices vi, vt, vs and vj . If
w contains a loop, then G contains at least one (k + 1)-walk from vi to vj . There-
fore we assume that (A)ii = (A)tt = (A)ss = (A)jj = 0. Thus vi 6= vi+1 and
vi+1 6= vi+2. If there exists no (k + 1)-walk from vi to vj , then for each vertex
v ∈ V (G)\{vi, vi+1}, G does not contain 2-walks of type (vi, v, vi+1). Other-
wise we obtain (k + 1)-walk (vi, v, vi+1, vi+2, . . . , vj). This implies an existence
of at least n− 2 non-connected pairs of vertices among (vi, v) and (v, vi+1), where
v ∈ V (G)\{vi, vi+1}. Similarly, for each vertex v ∈ V (G)\{vi+1, vi+2}, G does
not contain 2-walks of type (vi+1, v, vi+2). Otherwise we obtain (k + 1)-walk
(vi, vi+1, v, vi+2, . . . , vj).This implies an existence of at least n − 3 non-connected
pairs of vertices among (vi+1, v) and (v, vi+2), where v ∈ V (G)\{vi, vi+1, vi+2}.
Since G does not contain at least four loops, we obtain at least (n−2)+(n−3)+4 =
2n− 1 non-connected pairs of vertices in G, which is not possible.
Claim 2: If k ≥ 3 and w contains three distinct vertices, then there exists at least one
(k + 1)-walk from vi to vj . Therefore (Ak+1)ij ≥ 1.
We proceed similarly as in the previous case. Let w = (vi, vi+1, . . . , vj) contain
three distinct vertices vi, vt and vj . If w contains a loop, then there exists at least
one (k + 1)-walk from vi to vj . Therefore we suppose (A)ii = (A)tt = (A)jj = 0.
Clearly vi+1 6= vi and vt 6= vt+1. Without loss of generality let vi+1 = vt. If G does
not contain a (k + 1)-walk from vi to vj , then for each v ∈ V (G)\{vi, vt, vj} there
exist no walks of type (vi, v, vi+1) and (vt, v, vt+1). Otherwise we obtain the walks
(vi, v, vi+1, . . . , vj) and (vi, vi+1, . . . , vt, v, vt+1, . . . , vj), both of length k+1. The
non-existence of the walks (vi, v, vi+1) and (vt, v, vt+1) implies an existence of at
least 2(n − 3) non-connected pairs of vertices among the pairs (vi, v), (v, vi+1 =
vt), (vt, v) and (v, vt+1).
Let vi+2 = vi. We suppose that the walks (vi, vj , vt) and (vt, vj , vi) do not exist.
Otherwise we obtain (k + 1)-walks from vi to vj (vi, vj , vi+1, vi+2, . . . , vj) and
(vi, vi+1, vj , vi+2, . . . , vj), respectively. This yields an existence of at least two non-
connected pairs among the pairs (vi, vj), (vj , vt), (vt, vj) and (vj , vi). In this case G
contains at least 2n− 1 = 3 + 2(n− 3) + 2 non-connected pairs of vertices, which
is not possible.
Let vi+2 = vj . Similarly as in the previous case, we conclude that there exists no
a walk (vi, vj , vt). Otherwise we obtain the walk (vi, vj , vi+1, vi+2, . . . , vj). This
yields an existence of at least one non-connected pair among the pairs (vi, vj) and
(vj , vt). In this case G contains at least 2n − 2 non-connected pairs of vertices.
6 Art Discrete Appl. Math. 4 (2021) #P1.05
Since A contains at most 2n − 2 zeros, we obtain that vt and vj are connected to
vi. For any even k ≥ 4 we obtain a k-walk (vi, vt, vi, vt, . . . , vi, vt, vj). Similarly,
if k = 5 we obtain the walk (vi, vt, vj , vi, vt, vj). If k ≥ 7 is an odd number, then
k = 2s + 1 = (2s − 4) + 5 where s ≥ 3. In this case we obtain a k-walk from vi
to vj by connecting the walk (vi, vt, vi, vt, . . . , vt, vi) of length 2s− 4 and the walk
(vi, vt, vj , vi, vt, vj) of length 5.
Claim 3: If k = 2 and w = (vi, vt, vj), then (A3)ij ≥ 1 or the number of positive entries
of A3 at (i, i), (i, t), (i, j), (t, i), (t, t), (t, j), (j, i), (j, t) and (j, j) position is greater
or equal than the number of positive entries of the matrix A2 at the same positions.
Let G does not contain 3-walk from vi to vj and let v ∈ V (G)\{vi, vt, vj}. If G con-
tains walks of type (vi, v, vt) and (vt, v, vj), then there exist 3-walks (vi, v, vt, vj)
and (vi, vt, v, vj). In this case (A3)ij ≥ 1.
On the other hand, the non-existence of the walks (vi, v, vt) and (vt, v, vj) implies
an existence of at least 2(n− 3) non-connected pairs among the pairs (vi, v), (v, vt),
(vt, v) and (v, vj). Now, if vi is connected to vj , then vj is not connected to vi and
vt. Otherwise we obtain the walks (vi, vj , vi, vj) and (vi, vj , vt, vj). Since (A)ji =
(A)jt = 0 the matrix A contains at least 3+2(n−3)+2 = 2n−1 zeros. This is not
possible. If vi is not connected to vj , then A contains at least 2n−2 zeros. Therefore
vj is connected to vi and vt, and vt is connected to vi. By counting 2-walks between
the vertices vi, vt and vj , we find that the matrix A2 consists of seven positive entries
and two zeros at (i, i), (i, t), (i, j), (t, i), (t, t), (t, j), (j, i), (j, t) and (j, j) position.
On the other hand, by counting the 3-walks between the vertices vi, vt and vj we
conclude that A3 consists eight positive entries and one zero at the same positions.
Claim 4: Let w = (vi, vi+1, . . . , vj) contain two distinct vertices vi and vj . The number
of positive entries of Ak+1 at (i, i), (i, j), (j, i) and (j, j) position is greater or equal
than the number of positive entries of the matrix Ak at the same positions.
Let k ≥ 2. If the walk w contains a loop, then it is easy to conclude that G contains
a (k + 1)-walk from vi to vj . In this case (Ak)ij ≥ 1 implies (Ak+1)ij ≥ 1.
If w does not contain loops, then k is an odd number. We observe that G contains a k-
walk from vertex vj to vertex vi, which implies (Ak)ji ≥ 1. If there exists no k-walk
from vi to vi and if there exists no k-walk from vj to vj , then (Ak)ii = (Ak)jj = 0.
Since k + 1 is an even number, G contains (k + 1)-walks from vi to vi and from vj
to vj , that is, (Ak+1)ii ≥ 1 and (Ak+1)jj ≥ 1. Moreover, the digraph G does not
contain (k+1)-walk from vertex vi to vertex vj and from vertex vj to vertex vi, that
is, (Ak+1)ij = (Ak+1)ji = 0. Thus, the matrices Ak and Ak+1 contain two zeros
and two positive entries at (i, i), (i, j), (j, i) and (j, j) position.
Similarly, (Ak)ii ≥ 1 implies (Ak+1)ij ≥ 1 and (Ak)jj ≥ 1 implies (Ak+1)ji ≥ 1.
Let k = 1. If vj is connected to vi, we have the same case as k ≥ 2. If vj is not
connected to vi, then there exists at least one 2-walk from vj to vi or from vi to vj .
Otherwise we have at least 2n − 1 non-connected pairs of vertices in G, that is, at
least 2n− 1 zeros in A, a contradiction.
Claim 5: If w contains exactly one vertex vi, then there exists a (k + 1)-walk from vi to
vi. Therefore (Ak+1)ii ≥ 1.
In this case the walk w is obtained repeating the loop vi → vi k-times. Thus, there
exists a (k + 1)-walk from vi to vi.
S. Filipovski: An alternate proof of the monotonicity of the number of positive entries 7
As a conclusion, in the four cases (whether the k-walk from vertex vi to vertex vj
contains one, two, three or more distinct vertices), we obtain that the number of
positive entries in Ak+1 is greater or equal than the number of positive entries in Ak,
that is, f(Ak+1) ≥ f(Ak).
ORCID iDs
Slobodan Filipovski https://orcid.org/0000-0002-7286-4954
References
[1] R. B. Bapat and T. E. S. Raghavan, Nonnegative matrices and applications, volume 64 of En-
cyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1997,
doi:10.1017/CBO9780511529979.
[2] A. Berman and R. J. Plemmons, Nonnegative matrices in the mathematical sciences, volume 9
of Classics in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM),
Philadelphia, PA, 1994, doi:10.1137/1.9781611971262, revised reprint of the 1979 original.
[3] E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, 12th Media
Services, 2017.
[4] Z. Šidák, On the number of positive elements in powers of a non-negative matrix, C̆asopis Pěst.
Mat. 89 (1964), 28–30.
[5] Q. Xie, Monotonicity of the number of positive entries in nonnegative matrix powers, J. Inequal.
Appl. (2018), Paper No. 255, 5, doi:10.1186/s13660-018-1833-5.