IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 48 (2010), 1126
issn 2232-2094
ON THE CONTINUITY OF THE GENERALIZED SPECTRAL RADIUS IN MAX ALGEBRA
Aljosa Peperko
Ljubljana, August 13, 2010
CO
ON THE CONTINUITY OF THE GENERALIZED SPECTRAL RADIUS
IN MAX ALGEBRA
ALJOSA PEPERKO
denote the generalized spectral radius of ^ and its max version, respectively. We show
Abstract. Given a bounded set ^ of n x n non-negative matrices, let p(^) and
that
1 /t
mW = sup (n-1p(^(t))) , where ^(t) denotes the Hadamard power of We apply this result to give a new short proof of a known fact that	is continuous on the Hausdorff metric space (f3, H) of
all nonempty compact collections of n x n non-negative matrices.
fi
Math. Subj. Classification (2000): 15A18, 15A48, 15A60
Key words: Maximum circuit geometric mean; Max algebra; Non-negative matrices; Generalized spectral radius; Joint spectral radius; Continuity; Hausdorff metric; Hadamard powers; Schur powers.
CO
1. Introduction
£ CO
The algebraic system max algebra and its isomorphic versions provide an attractive way of describing a class of non-linear problems appearing for instance in manufacturing and transportation scheduling, information technology, discrete event-dynamic systems, combinatorial optimisation, mathematical physics, DNA analysis, ... (see e.g. [8], [9], [1], [37], [16], [2], [7], [3], [23], [24], [25], [32]). Max algebra's usefulness arises from a fact that these non-linear problems become linear when decribed in the max algebra language.
Following the notation from ([2], [11], [26], [27], [34], [28], [19]), the max algebra consists
of the set of non-negative numbers with sum a © b = maxja, b} and the standard product
ab, where a,b > 0. Let A = [aj] be a n x n non-negative matrix, i.e., aj > 0 for all
i, j = 1,..., n. We may denote aj also by [A]j. Let |Rraxra be the set of all n x n real
matrices and IR+xn the set of all n x n non-negative matrices. The operations between
matrices and vectors in the max algebra are defined by analogy with the usual linear
algebra. For instance, the product of A,B G IR+xn in the max algebra is denoted by
A ® B, where [A ® B]j = maxk=i.....n aikbkj. The notation A| means A ® A, and A^
Jh	' '
Date: July 23, 2010.
denotes the k-th max power of A. If x = [xj] E IRn is a non-negative vector, then the notation A ® x means [A ® x]j = maxj=1,...,ra ajXj. The usual associative and distributive laws hold in this algebra. Note that the standard products are denoted by AB and Ax.
The weighted directed graph D(A) associated with A has a vertex set {1, 2,... ,n} and edges (i, j) from a vertex i to a vertex j with weight aj if and only if aj > 0. A path of length k is a sequence of edges (i1, i2), (i2,i3),..., (ik, ik+1). A circuit of length k is a path with ik+1 = i1, where i1 ,i2,... ,ik are distinct. Associated with this circuit is the circuit geometric mean known as (ai1i2 ai2i3... aiki1 )1/k. The maximum circuit geometric mean in D(A) is denoted by MA). Note that circuits (i1,i1) of length 1 (loops) are included here and that we also consider empty circuits, i.e., circuits that consist of only one vertex and have length 0. For empty circuits, the associated circuit geometric mean is zero.
There are many different descriptions of the maximum circuit geometric mean MA) (see e.g. [14], [15], [10], [22, p. 366], [3, p. 130], [11], [31], [29], [26], [34], [33], [18]). It was proved in [15] that given A E IR+Xn
(1)	MA) = lim p(A(t))1/t,
t—» oo
CSI
00 CSI
£
where A(t) = [aj] is a Hadamard (or also Schur) power of A and p the spectral radius. Alternative and simplified proofs of (1) can be found in ([10], [22, p. 366], [3, p. 130], [11], [34]). We also have
(2)	MA) < p(A) < nMA)
(see e.g. [10], [22, p. 366], [26], [27], [34]).
It is known that MA) is the largest max eigenvalue of A. Moreover, if A is irreducible,
then MA) is the unique max eigenvalue and every max eigenvector is positive (see [2,
Theorem 2] and [26, Theorem 1]). We also have
(3)	MA) = lim ||A*||1/k
k^x
for an arbitrary vector norm || • || on |RnXn (see [11, Lemma 4.1], [26], [27], [34]).
Given an irreducible non-negative matrix A, algorithms for computing MA) and the max eigenvector x were established in [11], [12] and [13]. On the other hand, the infinite-dimensional generalizations of ^ can be found in [31], [29] and [33].
CO
Let S be a bounded set of n x n complex matrices. For m > 1, let
£m = {A1A 2 ••• Am : Aj E S}.
CO
The generalized spectral radius of S is defined by
(4)	p(S) = lim sup [ sup p(A)]1/m.
(5)	p(S) = lim [ sup ||A||]1/m
m^x AgYm
It was shown in [5] that p(S) is equal to the joint spectral radius of S, i.e.,
where || • || is any vector norm on Cnxn. This equality is called the Berger-Wang formula or also the generalized spectral radius theorem. Since then many different type of proofs of (5) were obtained (for references see e.g. [27]). The theory of the generalized spectral radius p(£) has many important applications (see e.g. [5], [36], [4], [20], [35], [30] and the references cited there). In particular, p(£) plays a central role in determining stability in convergence properties of discrete and differential inclusions. In this theory the quantity logp(£) is known as the maximal Lyapunov exponent (see e.g. [36]).
Let tf be a bounded set of n x n non-negative matrices. For m > 1, let
2
= {Al 0 A2 0 • • • 0 Am : A e tf }.
for an arbitrary vector norm || • || on IRnxn. The quantity log^(tf) measures the worst
The max algebra version of the generalized spectral radius ^(tf) of tf, defined by
(6)	^(tf) = lim sup [ sup MA)]1/m,
has recently received increasing attention (see e.g. [1], [17], [6], [27], [34], [33], [28], [19]). In [27] the max algebra version of the generalized spectral radius theorem was proved, i.e., ^(tf) is equal to the max algebra version of the joint spectral radius n(tf) of tf, which is defined by
(7)	n(tf) = lim [ sup ||A||]Vm
CO
case cycle time of certain discrete event systems and it is sometimes called the worst case Lyapunov exponent (see e.g. [17], [6], [1] and the references cited there).
A short proof of the max algebra version of the generalized spectral radius theorem was given in [34]. More precisely, it was shown that
(8)	Mtf) = lim p(tf(t))1/t = n(tf).
t—*oo
Here tf(t) denotes the Hadamard power of tf for t > 0, i.e.,
tf(t) = {A(t) : A e tf},
which is also a bounded set of n x n non-negative matrices. Also, p(tf(t))1/t is decreasing
in t e (0, to) and
(D	v ;
(9)	Mtf)= inf ,p(tf(t))1/t
m
(see [34, Proposition 2.2]). The basic tool in [34] was the inequality
(10)	Mtf) < p(tf) < n^(tf)
Jh
(see [34, Proposition 2.3] and [27, Theorem 3(ii)]), which generalizes (2).
Let K denote the collection of all compact nonempty sets £ of n x n complex matrices. The space K becomes a complete metric space if it is endowed with the usual Hausdorff
metric defined by
f
H(E, r) =	maxdist(A, r), :maxdist(B, E) }> ,
CSI
CO
CO CD
CO
CD U
CU
wxn
where dist(A,r) = infBer ||A — B||. Note that the choice of a vector norm || ■ || on C is irrelevant, since they are all equivalent (see e.g. [21, p. 272]). The following result is well known ([4], [20], [36, Lemma 3.5], [35]).
£
Theorem 1.1. The generalized spectral radius p(E) is continuous on (K,H).
$
This result was applied to wavelets in [20] (in the case E = {A, B}). In [36] and [35] some additional results were proved. vO	Let (P, H) denote the closed metric subspace of (K, H) of all nonempty compact subsets
of n x n non-negative matrices. The central result of [28] was the following max algebra version of Theorem 1.1.
Theorem 1.2. The max version of the generalized spectral radius is continuous on (P,H).
The main goal of this paper is to give a short proof of Theorem 1.2 by using Theorem
Theorem 2.1. Let ^ be a bounded set of n x n non-negative matrices. Then fii\	,.fm\- ^ U-i^AT,(th )1/t
CO
1.1.
2. The main results The following observation is the key to our proof.
(11)	^(tf) = sup (n-1p(^(t)))
te(o,ro)
Proof. Let t > 0. It is easy to see that p.(^(t)) =	(see e.g. the proof of [34, Theorem
2.4]). By (10) we have
n-1p(^(t)) < M^(t)) = M^f.
Therefore it follows that
n-
te(o,ro)
On the other hand, we have by (8)
sup (n-1p(^(t)))1/t < M^).
M^) = lim p(^(t))1/t = lim (n-1p(^(t)))1/t < sup (n-1p(^(t)))1/t
This completes the proof.	□
Corollary 2.2. If A e IR+Xn; then
U
p,(A) = sup (n-1p(A(t)))1/t te(o,^)
Remark 2.3. In (11) (and (9)) it suffices to take the supremum (infimum) over all t e IN.
Let us recall that a function f from a metric space (X, d) into IR is lower semi-continuous if and only if the sets {x G X : f (x) > a} are open in (X, d) for all a G IR. It is well known that the supremum of a family of lower semi-continuous functions is lower semi-continuous. A function f is upper semi-continuous if and only if — f is lower semi-continuous. Thus the infimum of a family of upper semi-continuous functions is upper semi-continuous. A function f is continuous if and only if it is both lower semi-continuous and upper semi-continuous.
Now, in view of (9), (11) and Theorem 1.1 we only need the following two results for the proof of Theorem 1.2.
m 2
vO
o

Lemma 2.4. If tf G ft then tf(t) G ft for all t> 0.
Proof. Let t > 0, tf G ft, e> 0 and || ■ a vector norm on |Rnxn defined by maxiJ=1,...,ra |aj|. Since tf(t) is obviously nonempty and bounded, we only need to show that it is also a closed subset of IR+xn. To prove this, let {An}neN c tf such that
II An — B^ 0 as n ^ to for some B G IR+xn. If M = supAe^ ||A(t)||^, then it is easy to see that ||B< M + 1. Since x ^ x1/t is an uniformly continuous function from the compact interval [0, M + 1] to [0, (M + 1)1/4], there exists 8 > 0 such that |x — y| <5 implies |x1/t — y1/t| < e.
Let C = B(1/t) and thus B = C(t). Since there exists no G IN such that || A^ — C(t) |U <8 for all n > n0, we also have ||An — C< e for these n. Therefore ||An — C^ 0 as n ^ oo. Since tf is a closed subset of IR+xn, we have C G tf and thus B G tf(t), which
completes the proof.	□
Lemma 2.5. Let t > 0. The map tf ^ tf(t) is a homeomorphism from (ft, H) onto (ft, H).
Proof. It suffices to prove that the map tf ^ tf(t) is continuous on (ft, H), since the rest is obvious. To prove this, choose tf G ft and 0 < e < 1. Let K(tf,e) denote the open ball in (ft, H) with the center tf and the radius e, i.e.,
K(tf,e) = {r G ft : H(tf, r) < e}.
If M = sup^e* ||A||^, then
CD
sup ||B|U < M + e < M + 1 Be r
CO
for all r G K(tf,e). Similarly as in the proof of Lemma 2.4 there exists 81 > 0 such that |x — y| < 81 and x, y G [0, M + 1] imply |x* — y*| < e.
Let 8 = min{e, 81}, r G K (tf,8), A G tf and B G r. Then there exist C G r and D G tf such that ||A — C<8 and ||B — D||^ < 8. Since aij, by, cj,dij G [0, M + 1] for all i, j = 1,... ,n, we have that ||A(t) — C(t)||^ < e and ||B(t) — D(t)||^ < e. This implies H(tf(t), r(t)) < e, which completes the proof.	□
CO
Having all the preliminaries prepared it is now easy to prove Theorem 1.2.
Proof of Theorem 1.2. By Lemma 2.5 and Theorem 1.1 the function ^ ^ p(^(t)) is continuous on H) for every t > 0. Therefore is upper semi-continuous on H) by (9) and it is lower semi-continuous on H) by (11). This completes the proof. □
m 2
Acknowledgments. The author would like to thank Professor Roman Drnovsek for reading the first version of this paper.
This work was supported by the Slovenian Research Agency.
References
F.L.	Baccelli, G. Cohen, G.-J. Olsder and J.-P.Quadrat, Synchronization and Linearity, John Wiley, Chichester, New York, 1992.
R.B. Bapat, A max version of the Perron-Frobenius theorem, Linear Algebra Appl. 275-276, (1998), 3-18.
R.B. Bapat and T.E.S. Raghavan, Nonnegative Matrices and Applications, Encyclopedia of Mathematics and its Applications 64, Cambridge, 1997.
N.E. Barabanov, Lyapunov indicator of discrete inclusions, I-III, Autom. Remote Control 49 (1988), 152-157, 283-287, 558-565.
M.A. Berger and Y. Wang, Bounded semigroups of matrices, Linear Algebra Appl. 166 (1992), 21-27.
V.D. Blondel, S. Gaubert and J.N. Tsitsiklis, Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard, IEEE Transactions on Automatic Control, 45:9 (2000), 1762-1765. P. Butkovic, Max-algebra: the linear algebra of combinatorics?, Linear Algebra Appl. 367 (2003), 313-335.
R.A. Cuninghame-Green, Minimax Algebra, Lecture Notes in Economics and Math. Systems, vol. 166, Springer, Berlin, 1979.
R.A. Cuninghame-Green, Minimax algebra and applications, Advances in Imaging and Electron Physics, vol. 90, pp. 1-121, Academic Press, New York, 1995.
L. Elsner, C.R. Johnson and J.A. Dias Da Silva, The Perron root of a weighted geometric mean of nonnegative matrices, Linear and Multilinear Algebra 24 (1988), 1-13.
L. Elsner and P. van den Driessche, On the power method in max algebra, Linear Algebra Appl. 302-303 (1999), 17-32.
L. Elsner and P. van den Driessche, Modifying the power method in max algebra, Linear Algebra Appl. 332-334 (2001), 3-13.
L. Elsner and P. van den Driessche, Max-algebra and pairwise comparison matrices, Linear Algebra Appl. 385 (2004), 47-62.
G.M.	Engel and H. Schneider, Diagonal similarity and equivalence for matrices over groups with 0, Czechoslovak. Math. J. 25 (1975), 389-403.
S. Friedland, Limit eigenvalues of nonnegative matrices, Linear Algebra Appl. 74 (1986), 173-178. S. Gaubert, Theorie des systemes lineaires dans les dioides, These, Ecole des Mines de Paris, 1992. S. Gaubert, Performance evaluation of (max, +) automata, IEEE Trans. Automata Contr., vol 40, Dec. 1995.
S. Gaubert and S. Sergeev, The level set method for the two-sided max-plus eigenproblem, (2010), E-print: arXiv 1006.5702v1 [math.MG].
B.B.	Gursoy and O. Mason, Spectral properties of matrix polynomials in the max algebra, Linear Algebra Appl. (2010), doi:10.1016/j.laa.2010.01.014
C.	Heil and G. Strang, Continuity of the joint spectral radius: application to wavelets, Linear Algebra for Signal Processing, The IMA Volumes in Mathematics and its Applications, vol.69, Springer, New York, 1995, pp. 51-61.
R.A. Horn and C.R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985.
CO
CO 2
vD
0 o
1
CO ^
CO CO
[22 [23 [24 [25 [26 [27 [28 [29
[30 [31 [32 [33 [34 [35 [36 [37
R.A. Horn and C.R. Johnson, Topics in -matrix analysis, Cambridge University Press, Cambridge, 1999.
V.N. Kolokoltsov and V.P. Maslov, Idempotent analysis and its applications, Kluwer Acad. Publ., 1997.
G.L. Litvinov, V.P. Maslov and G.B. Shpiz, Idempotent functional analysis: An algebraic approach, Math Notes 69, no. 5-6 (2001) 696-729, E-print: arXiv:math.FA/0009128 G.L. Litvinov and V.P. Maslov (eds.), Idempotent mathematics and mathematical physics, Con-temp. Math. Vol. 377, Amer.Math. Soc., Providence, RI, 2005.
Y.Y. Lur, On the asymptotic stability of nonnegative matrices in max algebra, Linear Algebra Appl. 407 (2005), 149-161.
Y.Y. Lur, A max version of the generalized spectral radius theorem, Linear Algebra Appl. 418 (2006), 336-346.
Y.Y. Lur and W.W. Yang, Continuity of the generalized spectral radius in max algebra, Linear Algebra Appl. 430 (2009), 2301-2311.
J. Mallet-Paret and R.D. Nussbaum, Eigenvalues for a class of homogeneous cone maps arising from max-plus operators, Discrete and Continuous Dynamical Systems, vol 8, num 3, (2002), 519-562.
B. Moision, A. Orlitsky and P.H. Siegel, On codes with local joint constraints, Linear Algebra Appl. 422 (2007), 442-454.
R.D. Nussbaum, Convexity and log convexity for the spectral radius, Linear Algebra Appl. 73 (1986), 59-122.
L. Pachter and B. Sturmfels (eds.), Algebraic statistics for computational biology, Cambridge Univ. Press, New York, 2005.
A. Peperko, Inequalities for the spectral radius of non-negative functions, Positivity 13 (2009), 255-272.
A. Peperko, On the max version of the generalized spectral radius theorem, Linear Algebra Appl. 428 (2008), 2312-2318.
V.S. Shulman and Yu.V. Turovskii, Joint spectral radius, operator semigroups and a problem of W.Wojtynski, J. Funct. Anal. 177 (2000), 383-441.
F. Wirth, The generalized spectral radius and extremal norms, Linear Algebra Appl. 342 (2002), 17-40.
U. Zimmermann, Linear and Combinatorial Optimization in Ordered Algebraic Structures, Ann. Discrete Math., vol 10, North Holland, Amsterdam, 1981.
CO CD
Jh
CD CO
Aljosa Peperko
Faculty of Mechanical Engeenering University of Ljubljana AskerCeva 6
SI-1000 Ljubljana, Slovenia and
Institute of Mathematics, Physics and Mechanics Jadranska 19
SI-1000 Ljubljana, Slovenia e-mail : aljosa.peperko@fmf.uni-lj.si
U
a
CD U