On the Sequence of Consecutive Powers of a Matrix in a Boolean Algebra.
In this paper we consider the sequence of consecutive powers of a matrix in a Boolean algebra. We characterize the ultimate behavior of this sequence, we study the transient part of the sequence, and we derive upper bounds for the length of this transient part. We also indicate how these results can be used in the analysis of Markov chains and in max-plus algebraic system theory for discrete event systems.
Introduction
. In this paper we consider the sequence of consecutive powers
of a matrix in a Boolean algebra. This sequence reaches a \cyclic" behavior
after a nite number of terms. Even for more complex algebraic structures, such as
the max-plus algebra (which has maximization and addition as its basic operations)
this ultimate behavior has already been studied extensively by several authors (See,
e.g., [1, 9, 13, 26] and the references therein). In this paper we completely characterize
the ultimate behavior of the sequence of the consecutive powers of a matrix in
a Boolean algebra. Furthermore, we also study the transient part of this sequence.
More specically, we give upper bounds for the length of the transient part of the
sequence as a function of structural parameters of the matrix.
Our main motivation for studying this problem lies in the max-plus-algebraic
system theory for discrete event systems. Furthermore, our results can also be used
in the analysis of the transient behavior of Markov chains.
This paper is organized as follows. In x2 we introduce some of the notations and
concepts from number theory, Boolean algebra, matrix algebra and graph theory that
will be used in the paper. In x3 we characterize the ultimate behavior of the sequence
of consecutive powers of a given matrix in a Boolean algebra, and we derive upper
bounds for the length of the transient part of this sequence. In x4 we brie
y sketch
how our results can be used in the analysis of Markov chains and in the max-plus-
algebraic system theory for discrete event systems. In this section we also explain
why we have restricted ourselves to Boolean algebras in this paper and we indicate
some of the phenomena that should be taken into account when extending our results
to more general algebraic structures. Finally we present some conclusions in x5.
2. Preliminaries.
2.1. Notation, denitions and some lemmas from number theory. In
this paper we use \vector" as a synonym for \column matrix". If a is a vector, then
a i is the ith component of a. If A is a matrix, then a ij or (A) ij is the entry on the
ith row and the jth column, and A is the submatrix of A obtained by removing all
rows that are not indexed by the set  and all columns that are not indexed by the
set .
Control Laboratory, Faculty of Information Technology and Systems, Delft University of Tech-
nology, P.O. Box 5031, 2600 GA Delft, The Netherlands (b.deschutter@its.tudelft.nl).
y ESAT/SISTA, K.U.Leuven, Kardinaal Mercierlaan 94, B-3001 Heverlee (Leuven), Belgium
(bart.demoor@esat.kuleuven.ac.be).

Table
The operations
and
for the Boolean algebra (f0; 1g;
The set of the real numbers is denoted by R, the set of the nonnegative integers
by N, and the set of the positive integers by N 0 .
If S is a set, then the number of elements of S is denoted by #S. If
is a set of
positive integers then the least common multiple of the elements of
is denoted by
lcm
and the greatest common divisor of the elements of
is denoted by gcd
If x 2 R then dxe is the smallest integer that is larger than or equal to x, and bxc
is the largest integer that is less than or equal to x.
Lemma 2.1. Let p; q 2 N 0 be coprime. The smallest integer n such that for any
integer m  n, there exist two nonnegative integers  and  such that
is given by
Proof. See, e.g., the proof of Lemma 3.5.5 of [5].
Let a 1 , a 2 , . , an 2 N 0 with an an ) to
be the largest positive integer N for which the equation a
subject to x 1 has no solution. From Lemma 2.1 it follows that
ab a b. Although a formula exists for the case where
are known for However, some upper bounds have
been proved [4, 11]:
Lemma 2.2. If a 1 ; a an 2 N 0 with a 1 < a < an and gcd(a an
an )  (a 1 1)(a n 1) 1.
Lemma 2.3. If a 1 ; a an 2 N 0 with a 1 < a < an and gcd(a an
1, then we have g(a an )  2an 1
an
an .
2.2. Boolean algebra. A Boolean algebra is an algebraic structure of the form
such that the operations
and
applied on 0 and 1 yield
the results of Table 2.1, where
and
are associative, and
where
is distributive
with respect to . The element 0 is called the Boolean zero element, 1 is called the
Boolean identity element,  is called the Boolean addition
and
is called the Boolean
multiplication.
Some examples of Boolean algebras are: (ffalse; trueg; or; and), (f0; 1g; min; +),
and so on (see
[1, 15]). In this paper we shall use the following examples of Boolean algebra in order to
transform known results from max-plus algebra and from nonnegative matrix algebra
to Boolean algebra:
1. The Boolean algebra (f1; 0g; max; +) is a subalgebra of the max-plus algebra
2. The Boolean algebra (f0; pg; +; ) where p stands for an arbitrary positive
number 1 can be considered as a Boolean restriction of nonnegative algebra.
A matrix with entries in B is called a Boolean matrix. The operations
and
are extended to matrices as follows. If then we have
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 3
for all
a
ik
for all j. Note that these denitions resemble the denitions of the sum and the
product of matrices in linear algebra but with  instead of
and
instead of .
The n by n Boolean identity matrix is denoted by In , the m by n Boolean zero
matrix is denoted by Omn , and the m by n matrix all the entries of which are equal
to 1 is denoted by Emn . If the dimensions of these matrices are not indicated they
should be clear from the context.
The Boolean matrix power of the matrix A 2 B nn is dened as follows:
In ; and
A
A
A
If we permute the rows or the columns of the Boolean identity matrix, we obtain a
Boolean permutation matrix. If P 2 B nn is a Boolean permutation matrix, then we
have
In . A matrix R 2 B mn is a Boolean upper triangular
2.3. Boolean algebra and graph theory. We assume that the reader is familiar
with basic concepts of graph theory such as directed graph, path, (elementary)
circuit, and so on (see, e.g., [1, 18, 27]). In this paper we shall use the denitions of [1]
since they are well suited for our proofs. Sometimes these denitions dier slightly
from the denitions adopted by other schools in the literature. The most important
dierences are:
In this paper we also consider empty paths, i.e., paths that consist of only
one vertex and have length 0. However, unless it is explicitly specied, we always
assume that paths have a nonzero length.
The precedence graph of the matrix A 2 B nn , by denoted by G(A), is a
directed graph with vertices 1, 2, . , n and an arc for each a ij 6= 0. Note that
vertex i is the end point of this arc.
A directed graph is called strongly connected if for any two dierent vertices
there exists a path from v i to v j . Note that this implies that a graph consisting
of one vertex (with or without a loop) is always strongly connected.
A matrix is irreducible if its precedence graph is strongly connected. Since
according to the denition we use a graph with only one vertex is always strongly
connected, the 1 by 1 Boolean zero matrix [ 0 ] is irreducible. However, the 1 by 1
Boolean zero matrix [ 0 ] is the only Boolean zero matrix that is irreducible.
Let us now give a graph-theoretic interpretation of the Boolean matrix power.
Let A 2 B nn and let k 2 N 0 . Recall that there is an arc only if
a iia i
a
for all since 0 is absorbing
for
equal to 1 if and only if there
exists a path of length k from vertex j to vertex i in G(A).
A maximal strongly connected subgraph (m.s.c.s.) G sub of a directed graph G is
a strongly connected subgraph that is maximal, i.e., if we add an extra vertex (and
some extra arcs) of G to G sub then G sub is no longer strongly connected.
4 B. DE SCHUTTER AND B. DE MOOR
A well-known result from matrix algebra states that any square matrix can be
transformed into a block upper diagonal matrix with irreducible blocks by simultaneously
reordering the rows and columns of the matrix (see, e.g., [1, 2, 5, 12, 17, 22]
for the proof of this theorem and for its interpretation in terms of graph theory and
Markov chains):
Theorem 2.4. If A 2 B nn then there exists a permutation matrix
such that the matrix ^
A
P T is a block upper triangular matrix of the form
A 11
A 1l
A 2l
(1)
with l  1 and where the matrices ^
A
A 22 , . ,
A ll are square and irreducible. The
A
A 22 , . ,
A ll are uniquely determined to within simultaneous permutation
of their rows and columns, but their ordering in (1) is not necessarily unique.
The form in (1) is called the Frobenius normal form of the matrix A. If A is irreducible
then there is only one block in (1) and then A is a Frobenius normal form of itself.
Each diagonal block of ^
A corresponds to an m.s.c.s. of the precedence graph of ^
A.
Theorem 2.5. If A 2 B nn is irreducible, then
A
k+c
c
A
(2)
where  is equal to 1 if there exists a circuit in G(A), and equal to 0 otherwise.
Proof. See, e.g., [1, 7, 13].
The smallest c for which (2) holds is called the cyclicity [1], index of cyclicity [2] or
index of imprimitivity 2 [5, 12] of the matrix A. The cyclicity c(A) of a matrix A is
equal to the cyclicity of the precedence graph G(A) of A and can be computed as
follows. The cyclicity of a strongly connected graph or of an m.s.c.s. is the greatest
common divisor of the lengths of all the circuits of the given graph or m.s.c.s. If an
m.s.c.s. or a graph contains no circuits then its cyclicity is equal to 0 by denition.
The cyclicity of general graph is the least common multiple of the nonzero cyclicities
of the m.s.c.s.'s of the given graph.
Lemma 2.6. If A 2 B nn is irreducible then c(A)  n.
Proof. Let A is irreducible, G(A) contains only one m.s.c.s.
If
From now on we assume that A 6= O. Since c is the greatest common divisor of the
lengths of the (elementary) circuits in G(A), c is maximal if there is only one circuit
and if this circuit has length n. In that case we have In the other cases, c will
be less than n.
Lemma 2.7. Let A 2 B nn be irreducible and let c be the cyclicity of A. Consider
ng. If c > 0 and if there exists a (non-empty) path of length l 1 from
j to i and a (non-empty) path of length l 2 from j to i then there exists a (possibly
negative) integer z such that l
We prefer to use the word \cyclicity" or \index of cyclicity" in this paper in order to avoid
confusion with the concept \index of primitivity" [2, 25] of a nonnegative matrix A, which is dened
to be the least positive integer
(A) such that all the entries of A
are positive.
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 5
Proof. This lemma is a reformulation of Lemma 3.4.1 of [5] that states that if G
is a strongly connected directed graph with cyclicity c then for each pair of vertices j
and i of G, the lengths of the paths from j to i are congruent modulo c.
Remark 2.8. Consider A 2 B nn and ng. Let l ij be the length of
the shortest path from vertex j to vertex i in G(A). Note that Lemma 2.7 does not
imply that there exists a path of length l ij + kc from j to i for every k 2 N. 3
In the next section we discuss upper bounds for the integer k 0 that appears in Theorem
2.5. We also extend this theorem to Boolean matrices that are not irreducible.
3. Consecutive powers of a Boolean matrix. In this section we consider
the sequence
A
where A is a Boolean matrix. First we consider matrices
with a cyclicity that is equal to 0. Next we consider matrices with a cyclicity that
is larger than or equal to 1. Here we shall make a distinction between four dierent
cases depending on whether the given matrix is irreducible or not, and on whether its
cyclicity is equal to 1, or larger than or equal to 1. Of course the last case that will
be considered is the most general one, but for the other cases we can provide tighter
upper bounds on the length of the transient part of the sequence
A
k=1 and that
is why we consider four dierent cases.
If possible we also give examples of matrices for which the sequence of the consecutive
matrix powers exhibits the longest possible transient behavior.
3.1. Boolean matrices with a cyclicity that is equal to 0. Lemma 3.1.
Let A 2 B nn . If then we have
A
Proof. If the cyclicity of A is equal to 0, then there are no circuits in G(A), which
means that there do not exist paths in G(A) with a length that is larger than or equal
to n since in such paths at least one vertex would appear twice, which implies that
such paths contain a circuit. Therefore, we have
A
O for all k  n.
Example 3.2. If there exists a permutation matrix P such that A 2 B nn can be
written as
A
then the upper bound of Lemma 3.1 is tight, i.e., we have
A
A
O for all k  n. The graph of the matrix ^
A is represented
in Figure 3.1. Note that
contains no circuits and
since the transformation from A to ^
A corresponds to a simultaneous reordering of the
rows and the columns of A (or of the vertices of G(A)). 3
From now on we only consider matrices with a cyclicity that is larger than or equal
to 1.
3.2. Boolean matrices with cyclicity 1. Theorem 3.3. Let A 2 B nn . If
the cyclicity of A is equal to 1 and if A is irreducible, then we have
A
A
Enn for all k  (n
Proof. This theorem can be considered as the Boolean equivalent of Theorem 4.14
of [2] or of Theorem 3.5.6 of [5]. Note that A cannot be equal to [ 0 ] since
6 B. DE SCHUTTER AND B. DE MOOR
Fig. 3.1. The precedence graph of the matrix ^
A of Example 3.2.
If more information about the structure of A is known (such as the number of diagonal
entries that are equal to 1, the length of the shortest elementary circuit of G(A), or
whether A is symmetrically nonnegative) other upper bounds for the length of the
transient part of the sequence
A
where A is a Boolean matrix with cyclicity
1 can be found in x2.4 of [2].
Example 3.4. If there exists a permutation matrix P such can be written
as
A
. 0
then the bound in Theorem 3.3 is tight: we have
A
A
6= 1. Let us now show that the latter part of this statement indeed holds.
Since the transformation from A to ^
A
corresponds to a simultaneous
reordering of the rows and the columns of A, we may assume without loss of generality
that P is the identity matrix.
A. If then we have (n 2.
Since
and
we indeed have
A
2.
From now on we assume that n > 2. In Figure 3.2 we have drawn G(A). There are
two elementary circuits in G(A): circuit of length
n and circuit length n 1. Note that only the
longest circuit passes through vertex n. Furthermore, if n > 2 then gcd(n
Any circuit that passes through vertex n can be considered as a concatenation of
times C 1 , a path from vertex n to a vertex t in C 2 ,  times C 2 , and a path from t
to n for some nonnegative integers  and . The length of this circuit is equal to
2.1 the smallest integer N such that for any integer
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 7n
Fig. 3.2. The precedence graph of the matrix ^
A of Example 3.4.
N there exist nonnegative integers  and  such that
given by This implies that (n 1)(n cannot be written
as
This implies that there does not exist a circuit
of length that passes through vertex n. Hence,
A
nn
A
A
P T is the Frobenius normal form of A, then we have
A
P . Hence,
A
A
A
for all k 2 N. Therefore, we may consider without loss of generality the sequence
A
instead of the sequence
A
. Furthermore, since the transformation
from A to ^
A corresponds to a simultaneous reordering of the rows and columns of A
(or to a reordering of the vertices of G(A)), we have
A).
Theorem 3.5. Let ^
be a matrix of the form (1) where the matrices
A
A 22 , . ,
A ll are irreducible and such that c( ^
such that ^
A ij for all

for all
Let

8 B. DE SCHUTTER AND B. DE MOOR
for all we have for all
A
On
for all k
For all
A
On
for all k
Remark 3.6. Note that ^
A ij is an n i by n j matrix for all
Let us now give a graphical interpretation of the sets S ij and ij .
Let C i be the m.s.c.s. of G( ^
that corresponds to ^
A ii for is the
set of vertices of C i .
If there exists a path from a vertex in C i r
to a vertex in C i r 1
for each each m.s.c.s. C i of G( ^
either is
strongly connected or consists of only one vertex, this implies that there exists a path
from a vertex in C j to a vertex in C i that passes through C i s 1
there does not exist any path from a vertex in C j to a vertex in C i .
The set ij is the set of indices of the m.s.c.s.'s of G( ^
through which some path
from a vertex of C j to a vertex of C i passes.
is the smallest m.s.c.s. of G(A) that contains a circuit and through
which some path from a vertex of C j to a vertex of C i passes 3 . 3
Proof. Proof of Theorem 3.5.
Let C i be the m.s.c.s. of G( ^
that corresponds to ^
A ii for
O if i > j, there are no arcs from any vertex of C j to a vertex in C i . As a consequence,
(5) holds if i > j.
Note that c( ^
A ii
since
each
A ii corresponds to an m.s.c.s. of G( ^
A).
A is irreducible and then (4) holds by Theorem 3.3. It is easy to verify
that (4) holds if
From now on we assume that l > 1 and i < j.
there does not exist a path from a vertex in C j to a vertex in C i .
A
O for all k 2 N.
. So there exist paths
from a vertex in C j to a vertex in C i , but each path passes only through m.s.c.s.'s
that consist of one vertex and contain no loop. Such a path passes through at most
3 Or more precisely:
belongs to the set of the smallest m.s.c.s.'s of G(A) that
contain a circuit and through which some path from a vertex of C j to a vertex of C i passes.
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 9
s
r
s
r r
r
r
r
r
Fig. 3.3. Illustration of the proof of Theorem 3.5. There exists a path from vertex us of m.s.c.s.
C j to vertex v 0 of m.s.c.s. C i that passes through the m.s.c.s.'s C
ij of such m.s.c.s.'s (C j and C i included). This implies that there does not exist
a path with a length that is larger than or equal to # ij from a vertex in C j to a
vertex in C i . Hence, we have
A
O for all k  # ij .
From now on we assume that l > 1, i there exists
a set fi and there exist indices
for
A ur vr+1 6= 0 for each r. So there exists an arc from vertex v r+1 of C i r+1
to vertex u r
of
for each r 2 f0; 1g. Select an arbitrary vertex u s of C i s
and an
arbitrary vertex v 0 of C i 0
Recall that the only Boolean zero matrix that is irreducible is the 1 by 1 Boolean zero
Now we distinguish between two cases:
. So in this case we could
say that there exists an empty path of length l r = 0 from vertex u r to vertex v r of
On the other hand, if
there exists a (possibly empty) path
of length l r  n i r
1 from vertex u r to vertex v r of C i r
since
strongly
connected. If u r then this path is empty and has length 0.
So for each r 2 f0; there exists a (possible empty) path of length l r  n i rfrom vertex u r to vertex v r of C i r
Clearly, we have ^
is irreducible and since
it follows from Theorem 3.3 that there exists a path of length k from
vertex
r to vertex v ~ r of C i ~ r
for any k  k i ~ r i ~ r
s
r 6=~r
So if we have an integer k  k ij then we can decompose it as
with ~ k 2 N. By Theorem 3.3 there exists a path of length k ~ t ~ t from u ~
r to v ~ r in
r
for each ~ k 2 N. This implies that there exists a path from vertex u s to vertex
v 0 of length k in G( ^
A). This path consists of the concatenation of paths of length l r
from vertex u r to vertex v r of C i r
for
r paths of length
1 from vertex v r+1 of C i r+1
to vertex u r of C i r
for a path of
length from vertex u ~ r to vertex v ~
r of C i ~ r
(See

Figure

3.3). This implies that
A
us is an arbitrary vertex of C j and since v 0 is an
arbitrary vertex of C i , this implies that ^
A
Example 3.7. Consider the following matrix:
This matrix is in Frobenius normal form and its block structure is indicated by the
vertical and horizontal lines. The precedence graph of ^
A is represented in Figure 3.4.
Using the notations and denitions of Theorem 3.5, we have
A 11 =4
A 12 =4 015 and ^
Furthermore,
We have
Note that ^
A 11 is a matrix of the form (3). So the smallest K 11 for which ^
A
k  K 11 is equal to k 5. Furthermore, the smallest K 12 such that ^
A
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 1131
Fig. 3.4. The precedence graph of the matrix ^
A of Example 3.7.
for all k  K 12 is equal to k
A of this example all the bounds
ij that appear in Theorem 3.5 are tight.
It is easy to verify that for a matrix of the
all the bounds k ij that appear in Theorem 3.5 are tight. 3
Lemma 3.8. Let A 2 B nn with 1. Then we have
A
A
for all
Proof. If A is irreducible, then we have
A
A
k for all k  (n
Theorem 3.3.
So from now on we assume that A is not irreducible. Let ^
A
P T be the
Frobenius normal form of A. Assume that ^
A is of the form (1) where the ^
A ii 's are
square and irreducible. Let the numbers  ij , n i and the sets  i and ij be
dened as in Theorem 3.5.
We have k
Let us now prove that k ij  (n
We have n  (n
have
lg and since l  1, we have
l
t6=s
l
t6=s
12 B. DE SCHUTTER AND B. DE MOOR
Hence,
l
l
t6=s
then we have
l
l
l
l
l
l
l
l
t6=s
l
l
t6=s
l
As a consequence, it follows from
Theorem 3.5 that ^
A
A
for all k  (n
A
A
k for all k  (n 1) 2 +1. Since
A
A
this implies that
A
A
for all k  (n
3.3. Boolean matrices with a cyclicity that is larger than or equal to
1. Lemma 3.9. Let A 2 B nn be an irreducible matrix with c(A)  2 and let
ng. Then there exists a (possibly empty) path P ij from j to i in G(A)
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 13
that passes through at least one vertex of each (elementary) circuit of G(A) and that
has a length that is less than or equal to n 2 1
.
Proof. Since the cyclicity of A is larger than or equal to 2, there are no loops in
G(A). Hence, A contains at least one circuit. Since A is irreducible, this implies that
j has to belong to an elementary circuit of G(A). Since the length of any elementary
circuit of G(A) is larger than or equal to 2, there exists a set
ng with m
n such that any (elementary) circuit of G(A) contains at
least one vertex that belongs to S. Dene i strongly connected
there exists a (possibly empty) path P k with length l k  n 1 from vertex i k to vertex
mg. Let l k be the length of P k . There exists a path P ij
from j to i that contains at least one vertex of each (elementary) circuit of G(A): this
path consists of the concatenation of P 1 , P 2 , . , Pm . If l ij is the length of P ij , then
we have
(n
Remark 3.10. Note that we could have derived an upper bound that is more tight in
Lemma 3.9. The upper bound of Lemma 3.9 will be used in the proof of Theorem 3.11.
However, in that proof we shall also use Lemmas 2.2 and 2.3 which also yield upper
bounds, and therefore we do not rene the upper bound of Lemma 3.9. 3
Theorem 3.11. Let A 2 B nn be irreducible and let
(n
c
then we have
A
k+c
A
and
A
A
A
Proof. From Theorem 3.3 it follows that (8) holds if c is equal to 1. Furthermore,
if the rst part of (8) holds, then the second part also holds since A is irreducible.
From now on we assume that c > 1. Let ng.
Cm be the elementary circuits of G(A). Let l i be the length of C i for
is irreducible, we have
exist positive integers w 1 , w 2 , . , wm such that w and such that
First we consider the case where there is only one elementary circuit or where all the
elementary circuits have the same length. Hence, Since A is irreducible, both
have to belong to some elementary circuit. We may assume without loss of
generality that j belongs to C 1 . Since A is irreducible there exist paths from vertex
j to vertex i of G(A). Let P ij be the shortest (possibly empty) path from j to i and
ij be the length of this path. We have l ij  n 1 (Note that l
to j. For any integer k 2 N there exists a path of length l ij + kc from j to i: this
path consists of k times C 1 followed by P ij . Hence
A
l 2 N with l  n 1. Now there are two possibilities. If l can be written as
for some k 2 N, then we have
A
l
1. If l cannot be written as
any k 2 N, then it follows from Lemma 2.7 that there does not exist a path from j to
14 B. DE SCHUTTER AND B. DE MOOR
i and then we have
A
l
This implies that (8) holds if all the elementary circuits of G(A) have the same length.
From now on we assume that there exist at least two elementary circuits in G(A) that
have dierent lengths.
Since A is irreducible it follows from Lemma 3.9 that there exists a (possibly empty)
path P ij from vertex j to vertex i of G(A) with length l ij  n 2 1
2 that passes through
at least one vertex of each elementary circuit of G(A). For each circuit C k we select
one vertex v k that belongs to the path P ij . Let l be an integer that can be written
as
exist nonnegative integers  1 ,  2 , . , m such that
As a consequence, we have
there exists a path of length l from j to i: this path consists of the concatenation
of times the circuit C k (v
A
Let us now determine an upper bound for g(w
Therefore, we may assume without loss of generality that all the w i 's are dierent and
thus also that w 1 < w
Since there are at least two elementary circuits in G(A) that have dierent lengths, we
have m  2. We have w
c  n
c for all k. Hence, wm  n
c and w 1  n
2. As a consequence, we have
c
c
c
If we dene
n
c
c
c
then we have l ij
c  K. So if we have an integer l that is
larger than K then it can either be written as
and then
A
l
l cannot be written as pc for any p 2 N and then it
follows from Lemma 2.7 that there does not exist a path of length l from j to i, i.e.,
A
l
that K  k n;c .
Hence, (8) also holds in this case.
Remark 3.12. In the proof of Theorem 3.11 we could also have used Lemma 2.3
to determine an upper bound for g(w thus also
wm  2. Furthermore, wm 1  n
c 1. Hence,
wm
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 15
c
c
In the second part of the proof of Theorem 3.11 we have c  2. Since A is irreducible,
it follows from Lemma 2.6 that c  n. Hence, 1  n
c  n
2 . It is easy to verify that
the upper bound of (10) is less than the upper bound of (9) if n
c < 3
2 . However, if
c < 3
, then we would have wm 1  1
2 , which is not possible. This implies that for
combinations of n and c for which there are at least two elementary circuits in G(A)
with dierent lengths, the upper bound of (9) is less than or equal to the upper bound
of (10). 3
The Boolean sum of sequences is dened as follows. Consider sequences
k. The sequence
is dened by
Lemma 3.13. Consider sequences
B for all i; k. Suppose that for each i 2 there exist integers K
such that
If
then the sequence
Proof. Note that (11) implies that
First we assume that there exists an index i 2 mg such that c
1. Then we have (g i
From now on we assume that there does not exist any index i 2
that c
1.
exist positive integers w wm such that
m. Consider an integer k  K. We have
Example 3.14. Consider the sequences
If we use the notation of Lemma 3.13 then we have c
Hence, We have
It is easy to verify that g k+6 = g k for all k  1. 3
Theorem 3.15. Let ^
be a matrix of the form (1) where the matrices
A
A 22 , . ,
A ll are irreducible. Dene sets  1 ,  2 , . ,  l such that ^
for all
A ii ) for all i. Dene:

for all
Let
is dened as in (7)
with kn i
For each for each
c
if


lcmfc
for each
c
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 17
for all
Then we have for all
A
A
for all k
and
A
A
A
On
for all k  k ij .
For all
A
On
for all k
Proof. Let C i be the m.s.c.s. of G( ^
that corresponds to ^
A ii for
Let lg. In the proof of Theorem 3.15 is has already been proved that
holds if i > j, and that (13) and (14) hold if i
hold by Theorem 3.11 if
So from now on we assume that i <
that l > 1.
Select an arbitrary vertex u of C i and an arbitrary vertex v of C j .
there exists at least one set
which
ij is well dened. Note that k ij
there
do not exist paths from v to u of length n  # ij that correspond to
. So from now
on we only consider sets
which
Let
we assume that
for at least one index i r 2
. Assume that
is given by
s g. Dene
ur vr+1 6= 0 for
g. Let P(
be the set of paths from v to u that pass through m.s.c.s. C i r
for
that enter C i r
at vertex u r for that exit from C i r
through
vertex v r for 3.3). Let the sequences f(g
and f(g
k=1 be dened by
(g
1 if there exists a path of length k that belongs to P(
(g
1 if there exists a path of length k that belongs to P(
for some pair (U;
g. Let us now show that the sequences f(g
k=1 and
f(g
(g
(g
(g
(g
Note that if (16) and (17) hold for each pair (U;
Therefore, we now show that (16) and (17) hold. Dene ~ u
for
s. We consider three cases:
Case A: c j ~
r
In this case we have c
1.
l r be the length of the shortest (possibly empty) path from vertex ~
u r to
vertex ~ v r of C jr for each r 2 f0; We have l r  n jr 1 for each r.
r
is irreducible and since c j ~
r
it follows from Theorem 3.3 that
for any integer p  (n j ~ r
exists a path of length p from vertex
~
r to vertex ~
r of C j ~ r
. If we also take into account that there are s arcs of
the form v r+1 ! u r for that for any
r 6=~r
there exists a path of length k that belongs to P(
us now show
that KA  k ij . Let r 2 f0; it follows from the
denition of kn j r ;c j r
that
. Furthermore, if c
have
. Since c j ~ r
r
. Furthermore,
which
implies that (16) and (17) hold in this case.
Case B: c
and c t 6= 1 for all t 2
.
Assume that c j ~ r
with ~ r 2 f0;
sg.
l r be the length of the shortest (possibly empty) path from vertex ~
u r to
vertex ~
v r of C jr for each r 2 f0;
r
each r 6= ~ r. From Lemma 2.7 and from the proof of Theorem 3.11 it follows
that there exists an integer K ~
r with kn j ~
r
r
r
1 such
that there exist paths of length K ~ r
from vertex ~
r to vertex ~ v ~ r of C j ~ r
for any p 2 N, while there do not exist paths of length K ~
q from ~
r
to ~ v ~
r for any p 2 N and any q 2
r
1g. So if we dene
r 6=~r
r
then it follows from Lemma 2.7 that for any k  KB either there exists a
path of length k
that belongs to P(
N, or there do
not exist paths of length k
that belong to P(
It
is easy to verify that KB  k ij . Hence, (16) and (17) also hold in this case.
Case C: c jr 6= 1 for all r 2 f0;
for some a; b 2 f0;
From Lemma 2.7 and from the proof of Theorem 3.11 it follows that for each
there exists an integer K r with kn j r ;c j r
c jr 1 such that there exist paths of length K r c jr from ~ u r to ~ v r for each
while there do not exist paths of length K r +p c jr +q from ~ u r to ~
v r for
any p 2 N and for any q 2 1g. This implies that there exist
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 19
paths of length K 0
that belong to
P(
each choice of for each r. Dene
there exist positive integers
s such that c
for each r 2 f0; and such that
1. So for any integer q  g(w
exist nonnegative integers
s such that
s .
we have w a 6= w b . Therefore, we may assume without loss
of generality that w 0 < w 2. We have
c
s
c
c
c
thus 2. Using a reasoning that is similar to the one used in the proof
of Theorem 3.11 and Remark 3.12 we can show that
c
c
So if we dene
c
c
then we have KC  K
. Let k 2 N with k  KC .
Now there are two possibilities:
If k can be written as K
with q  g(w
we have
which implies that there exists a path of length k that belongs to P(
On the other hand, if k cannot be written as K
for any q 2 N
then it follows from Lemma 2.7 that there does not exist a path of length k
that belongs to P(
this implies that (16) and (17) also hold in this case.
If we consider all possible paths from vertex v to vertex u of length k 2 N with
then each of these paths corresponds to some set
A
is equal to 1 if and only if there exists a path of length k from v to u,
we have
A
uv
(g
Note that if c
then we have (g
1. Since each
sequence f(g
it follows from Lemma 3.13 that
A
uv
A
uv
for all k
Furthermore, since each sequence f(g
k=1 satises (19), we have
A
A
A
uv
20 B. DE SCHUTTER AND B. DE MOOR
Remark 3.16. Note that if
2 then we do not have to consider
1 when we are determining S ij . Hence, we could have dened S ij as the set of
maximal subsets fi of f1;
Let us now give an example in which the various sets and indices that appear in the
formulation of Theorem 3.15 are illustrated.
Example 3.17. Consider the matrix
This matrix is in Frobenius normal form and its block structure is indicated by the
horizontal and vertical lines. The precedence graph of A is represented in Figure 3.5.
We have
A
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 2131562C
Fig. 3.5. The precedence graph G(A) of the matrix A of Example 3.17. The subgraphs C 1 , C2 ,
C 3 and C 4 are the m.s.c.s.'s of G(A).
A
A
k for all k  2.
We have
us now look at the sequence
A
. We have
with
and c
3. We have
and r
Note that we indeed have
A
A
14 for all k  9. 3
Lemma 3.18. Consider m positive integers c 1 , c 2 , . , c m . Let
c m ). Consider r non-empty subsets  1 ,  2 , . ,  r of f1; mg. Dene d
for each i. If is a divisor of c.
Proof. We may assume without loss of generality that c i 6= c j for all
If d is a divisor of lcm(c also is a divisor of lcm(c
Therefore, we may assume without loss of generality that  1 [
mg. If  i   j then d j is a divisor of d i and then lcm(d
which implies that  j is redundant and may be
removed. If d redundant and may be removed. It is easy to
22 B. DE SCHUTTER AND B. DE MOOR
verify that if we remove all redundant sets, then the resulting number of sets  i is
less than or equal to m (The worst cases being when
or when  Hence, we may assume without
loss of generality that r  m and that d i 6= d j for all
can select indices l 1 , l 2 , . , l r such that l i 2  i for
is a divisor of c l i
for each i.
Since all c i 's are dierent we have
We also have
Since d i is a divisor of c l i
there exist integers w i 2 N such that
c l i
then we
have
Y
d
where
Y
c i is equal to 1 by denition. So
implies that d is a divisor of c.
Lemma 3.19. Let n 2 N and let c 2 f0; ng. If k n;c is dened by (7) if
then we have k n;c  (n
Proof. It is obvious that the lemma holds if 1. So from now on we
assume that c > 1.
us now show that f(c)  (n
We have df
2. So f reaches a local minimum in
pand is decreasing if
pand increasing if c > n
pLet us rst consider the cases where n is equal to 2 or to 3. If then we have
does
not belong to the interval [2; 3] and then the maximal value of f in [2; 3] is equal to
From now on we assume that n is larger than or equal to 4. If n  4, then n
pbelongs
to the interval [2; n] and then the maximal value of f in [2; n] is equal to
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 23
Hence, k n;c  (n
Theorem 3.20. Let A 2 B nn and let c be the cyclicity of A. We have
A
A
for all k  2n 2.
Proof. Let
A
P T be the Frobenius normal from of A where P is a
permutation matrix. Assume that ^
A is a matrix of the form (1) with ^
A ii irreducible
dened as in Theorem 3.15. Let us now show that k ij  2(n
It is easy to verify that this holds if from now on
we assume that  ij 6= 0. Hence,
c
Since we have kn i ;c i
from the proof of Lemma 3.8 that
Let us now show that
c
for each
;. From Lemma 2.6 it follows that
c t  n t for each t 2
. Hence, 1  c
2c. From the proof of Lemma 3.19 it follows that f is
decreasing if c < nr ij
pand increasing if c > nr ij
then the maximum value of f in the interval [1;
is equal to
2. Furthermore, c ij is a divisor of c by
Lemma 3.18. Hence, ^
A
A
k for all k  2n 2 3n+2. Since,
A
A
for all k 2 N, this implies that
A
k+c
A
for all k  2n 2.
4. Applications and extensions.
4.1. Markov chains. It is often possible to represent the behavior of a physical
system by describing all the dierent states the system can occupy and by specifying
how the system moves from one state to another at each time step. If the state space
of the system is discrete and if the future evolution of the system only depends on the
current state of the system and not on past history, the system may be represented by
a Markov chain. Markov chains can be used to describe a wide variety of systems and
phenomena in domains such as diusion processes, genetics, learning theory, sociology,
economics, and so on [22].
A nite homogeneous Markov chain is a stochastic process with a nite number of
states s 1 , s 2 , . , s n where the transition probability to go from one state to another
state only depends on the current state and is independent of the time step. We
dene an n by n matrix P such that p ij is equal to the probability that the next
state is s i given that the current state is s j . Note that
a sequence of vectors
(k)k=0 with
i is the probability
that the system is in state s i at time step k. If the initial probability vector (0) is
given, the evolution of the system is described by
Hence,
So if we consider the Boolean algebra (f0; pg; +; ) where p stands for an arbitrary
positive number and if we dene a matrix ~
nn such that ~
and ~
then we can give the following interpretation to the Boolean
matrix power ~
. We can go from state s j to state s i in k steps if and only if
equivalently if ~
p. As a consequence, the results of this paper
can also be used to obtain upper bounds for the length of the transient behavior of a
nite homogeneous Markov chain.
For more information on Markov chains and their applications the interested
reader is referred to [2, 12, 20, 22] and the references therein.
4.2. Max-plus algebra. Our main motivation for studying sequences of consecutive
powers of a matrix in a Boolean algebra lies in the max-plus-algebraic system
theory for discrete event systems. Typical examples of discrete event systems are
exi-
ble manufacturing systems, telecommunication networks, parallel processing systems,
trac control systems and logistic systems. The class of the discrete event systems
essentially consists of man-made systems that contain a nite number of resources
(e.g., machines, communications channels or processors) that are shared by several
users (e.g., product types, information packets or jobs) all of which contribute to the
achievement of some common goal (e.g., the assembly of products, the end-to-end
transmission of a set of information packets, or a parallel computation).
There are many modeling and analysis techniques for discrete event systems, such
as queuing theory, (extended) state machines, max-plus algebra, formal languages,
automata, temporal logic, generalized semi-Markov processes, Petri nets, perturbation
analysis, computer simulation and so on (See [1, 6, 19, 23, 24] and the references cited
therein). In general models that describe the behavior of a discrete event system are
nonlinear in conventional algebra. However, there is a class of discrete event systems
{ the max-linear discrete event systems { that can be described by a model that is
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 25
\linear" in the max-plus algebra [1, 7, 8]. The model of a max-linear discrete event
system can be characterized by a triple of matrices (A; B; C), which are called the
system matrices of the model.
One of the open problems in the max-plus-algebraic system theory is the minimal
realization problem, which consists in determining the system matrices of the
model of a max-linear discrete event system starting from its \impulse response 4 "
such that the dimensions of the system matrices are as small as possible (See [1] for
more information). In order to tackle the general minimal realization problem it is
useful to rst study a simplied version: the Boolean minimal realization problem, in
which only models with Boolean system matrices are considered. The results of this
paper on the length of the transient part of the sequence of consecutive powers of a
matrix in a Boolean algebra can be used to obtain some results for the Boolean minimal
realization problem in the max-plus-algebraic system theory for discrete event
systems [10]: they can be used to obtain a lower bound for the minimal system order
(i.e., the smallest possible size of the system matrix A) and to prove that the Boolean
minimal realization problem in the max-plus algebra is decidable (and can be solved
in a time that is bounded from above by a function that is exponential in the minimal
system order).
Both Boolean algebras and the max-plus algebra are special cases of a dioid (i.e.,
an idempotent semiring) [1, 16]. For applications of dioids in graph theory, generating
languages and automata theory the interested reader is referred to [14, 15, 16].
4.3. Extensions. In this paper we have restricted ourselves to Boolean algebras.
In this section we give some examples that illustrate some of the phenomena that could
occur when we want to extend our results to more general algebraic structures. In
our examples we shall use the max-plus algebra (R [ f1g;max; +), but for other
extensions of Boolean algebras similar examples can be constructed.
In contrast to Boolean algebra (cf. Theorem 3.20) the sequence of consecutive
powers of a matrix in a more general algebraic structure does not always reach a
stationary or cyclic regime after a nite number of terms as is shown by the following
example.
Example 4.1. Consider the matrix
Since the kth max-plus-algebraic power of A is given by
A
for k 2 N 0 , the sequence
A
does not reach a stationary or cyclic regime in a
nite number of steps. 3
Note that the matrix A of Example 4.1 is not irreducible. However, if a matrix is
irreducible then it can be shown [1, 7, 13] that the sequence of consecutive max-plus-
algebraic powers of the given matrix always reaches a cyclic regime of the form (2)
after a nite number of terms. However, even if the sequence of consecutive powers
reaches a stationary regime then in general the length of the transient part will not
4 This is the output of the system when a certain standardized input sequence is applied to the
system.
26 B. DE SCHUTTER AND B. DE MOOR
only depend on the size and the cyclicity of the matrix but also on the range and the
resolution (i.e., on the size of the representation) of the nite elements of the matrix
as is shown by the following examples.
Example 4.2. Let N 2 N and consider
The matrix A(N) is irreducible and has cyclicity 1 and its -value 5 is equal to 0. The
kth max-plus-algebraic power of A(N) is given by
max( k; N) N
for each k 2 N 0 . This implies that the smallest integer k 0 for which (2) holds, is given
by depends on the range of the nite entries of A(N ). 3
Example 4.3. Let " > 0 and consider the matrix
This matrix is irreducible, has cyclicity 1 and its -value is equal to 0. Since the kth
max-plus-algebraic power of A(") is given by
the smallest integer k 0 for which (2) holds, is k
. So this example | which has
been inspired by the example on p. 152 of [1] | shows that in general the length of
the transient part of the sequence
A
depends on the resolution of the nite
entries of A. 3
5. Conclusions. In this paper we have studied the ultimate behavior of the
sequence of consecutive powers of a matrix in a Boolean algebra, and we have derived
some upper bounds for the length of the transient part of this sequence. The results
that have been derived in this paper can be used in the analysis of the transient
behavior of Markov chains and in the max-plus-algebraic system theory for discrete
event systems.
Topics for future research are the derivation of tighter upper bounds for the length
of the transient part of the sequence of consecutive power of a matrix in a Boolean
algebra, and extension of our results to more general algebraic structures such as the
max-plus algebra.

Acknowledgments

. The authors want to thank the anonymous reviewers for
their useful comments and remarks, and for pointing out the connection with Markov
chains.
Bart De Moor is a research associate with the F.W.O. (Fund for Scientic Research
{ Flanders). This research was sponsored by the Concerted Action Project of the
Flemish Community, entitled \Model-based Information Processing Systems" (GOA-
MIPS), by the Belgian program on interuniversity attraction poles (IUAP P4-02 and
IUAP P4-24), by the ALAPEDES project of the European Community Training and
Mobility of Researchers Program.
5 For methods to compute the number  that appears in Theorem 2.5 for a max-plus-algebraic
matrix the reader is referred to [1, 3, 7, 21].
CONSECUTIVE POWERS OF A BOOLEAN MATRIX 27



--R

Synchronization and Linearity
Nonnegative Matrices in the Mathematical Sciences
The power algorithm in max algebra
On a problem of partitions
Combinatorial Matrix Theory
Introduction to the modelling
A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing


On the boolean minimal realization problem in the max-plus algebra

The Theory of Matrices
On rational series in one variable over certain dioids
Eigenvalues and eigenvectors in semimodules and their interpretation in graph theory


A graph theoretic approach to matrix inversion by partitioning

Discrete Event Dynamic Systems: Analyzing Complexity and Performance in the Modern World
Theory and Applications
A characterization of the minimum cycle mean in a digraph

Petri Net Theory and the Modeling of Systems

Matrix Iterative Analysis
On periodicity analysis and eigen-problem of matrix in max- algebra
Introduction to graph theory
--TR

--CTR
Martin Kutz, The complexity of Boolean matrix root computation, Theoretical Computer Science, v.325 n.3, p.373-390, 6 October 2004
Vincent J. Carey, Ontology concepts and tools for statistical genomics, Journal of Multivariate Analysis, v.90 n.1, p.213-228, July 2004
transient behavior;max-plus algebra;boolean matrices;boolean algebra;markov chains