IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 49 (2011), 1164
ISSN 2232-2094
BOUNDS ON THE GENERALIZED AND THE JOINT SPECTRAL RADIUS OF HADAMARD PRODUCTS
OF BOUNDED SETS OF POSITIVE OPERATORS ON SEQUENCE SPACES
Aljosa Peperko
Ljubljana, September 28, 2011
BOUNDS ON THE GENERALIZED AND THE JOINT SPECTRAL RADIUS OF HADAMARD PRODUCTS OF BOUNDED SETS OF POSITIVE OPERATORS ON SEQUENCE SPACES
CD
CD
a
CD CO
ALJOSA PEPERKO
Abstract. Recently, K.M.R. Audenaert (2010), R.A. Horn and F. Zhang (2010), Z. Huang (2011) and A.R. Schep (2011) proved inequalities between the spectral radius of Hadamard products of finite and infinite non-negative matrices that define operators on
sequence spaces and the spectral radius of their ordinary matrix product. We extend these results to the generalized and the joint spectral radius of bounded sets of such operators. Moreover, we prove new inequalities even in the case of the usual spectral radius of non-negative matrices. We also obtain related results in max algebra.
£
Math. Subj. Classification (2010): 15A18, 15A45, 15A60, 15B48, 47B65 Key words: Hadamard-Schur product; Spectral radius ; Non-negative matrices; Positive operators; Generalized spectral radius; Joint spectral radius; Maximum circuit geometric mean; Max algebra; Matrix inequality
1. Introduction
£
CO	In [29], X. Zhan conjectured that for non-negative n x n matrices A and B the spectral
radius p(A o B) of the Hadamard product satisfies
p(A o B) < p(AB),
where AB denotes teh usual matrix product of A and B. This conjecture was confirmed by K.M.R. Audenaert in [2] by proving
(1)	p(A o B) < p1 ((A o A)(B o B)) < p(AB).
CD
These inequalities were established via a trace description of the spectral radius. Using the fact that the Hadamard product is a principal submatrix of the Kronecker product,
R.A. Horn and F. Zhang proved in [15] the inequalities (2)	p(A o B) < p2 (AB o BA) < p(AB)
a
CD -
Date: September 9, 2011.
CU	1
00 CM
a
CD CO
CO CD
Jh
and also the right-hand side inequality in (1). Applying the techniques of [15], Huang proved that
(3)	p(Ai o A2 o ■ ■ ■ o Am) < p(A\A2 ■ ■ ■ Am)
for n x n non-negative matrices A1,A2, ■ ■ ■ ,Am (see [16]). In [22] and [23], A.R. Schep extended inequalities (1) and (2) to non-negative matrices that define bounded operators on sequence spaces (in particular on lp spaces, 1 < p < to). In the proofs certain results on the Hadamard product from [8] were used. In [22] it was claimed in Theorem 2.7 that
(4)	p(A o B) < p2 ((A o A)(B o B)) < p 1 (AB o BA) < p(AB).
However, the proof of Theorem 2.7 actually demonstrates that
(5)	p(A o B) < p2((A o A)(B o B)) < p2(AB o AB) < p(AB).
It turns out that p(AB o BA) and p(AB o AB) may in fact be different and that (4) is false in general. This typing error was corrected in [23].
In this paper we generalize the mentioned results to the setting of the generalized and the joint spectral radius of bounded sets of non-negative matrices that define bounded operators on Banach sequence spaces. Moreover, we also prove new inequalities even in the case of the usual spectral radius of non-negative matrices. In particular, we prove that
p(A o B) < p2((A o A)(B o B)) < p(AB o AB) 1 p(BA o BA)4 < p(AB)
and
cm	1	1	1
p(A o B) < p2 (AB o BA) < p(AB o AB)ip(BA o BA) 4 < p(AB) (see Corollary 3.9).
CO	In the last section we also obtain related results in max algebra, which is an attractive
setting for describing certain conventionally non-linear problems in a linear fashion.
2. Preliminaries
Throughout the paper, let R denote the set {1,..., n} for some n G IN or the set IN of all natural numbers. Let S(R) be the vector lattice of all complex sequences (xj)ieR. A Banach space L C S(R) is called a Banach sequence space if x G S(R), y G L and |x| < |y| imply that x G L and ||x||L < ||y||L. Note that in the literature such a space L
is usually called a Banach function space over a measure space (R,p), where p denotes the counting measure on R. The cone of non-negative elements in L is denoted by L+.
Similarly as in [9] and [21] let us denote by L the collection of all Banach sequence spaces L satisfying the property that e^ = X{t} G L and ||ej||L = 1 for all i G R. Standard a	examples of spaces from L are Euclidean spaces, the well known lp spaces (1 < p < to)
and the space c0 of all null convergent sequences, equipped with the usual norms. The
cm
u
CD
CO CD
set L also contains all cartesian products L = X x Y for X, Y E L, equipped with the norm ||(x,y)||L = max{||x||x, ||y||y}.
A matrix A = [aij]i,jGR is called non-negative if aij > 0 for all i, j E R. Given matrices A and B, we write A < B if the matrix B — A is non-negative.
By an operator on a Banach sequence space L we always mean a linear operator on L. We say that a non-negative matrix A defines an operator on L if Ax E L for all x E L, where (Ax)j = EjeR ajXj. Then Ax E L+ for all x E L+ and so A defines a positive operator on L. Recall that this operator is always bounded, i.e., its operator norm
||A|| = sup{||Ax|| : x E L+, ||x|| < 1}
is finite. Also, its spectral radius p(A) is always contained in the spectrum. For the theory of Banach function spaces, Banach lattices and positive operators we refer the reader to the books [28], [17] and [1].
Given non-negative matrices A = [aj]i,jGR and B = [bj]itjGR, let A o B = [ajbj]ijGR be the Hadamard (or Schur) product of A and B and let A(t) = [aj]ijGR be the Hadamard (or Schur) power of A for t > 0. Here we use the convention 00 = 1.
Let S be a bounded set of bounded operators on L. For m > 1, let
Sm = {Ai A 2 ••• Am : Ai E S}.
o
The generalized spectral radius of S is defined by
i
(6)	p(S) = limsup [ sup p(A)]1/m
m—AGS"
nm
and is equal to
p(S) = sup [ sup p(A)]1/m mG IN AeSm
The joint spectral radius of S is defined by
(7)	p(S) = lim [ sup ||A|]1/m.
It is well known that p(S) = p?(S) for a precompact set S of compact operators on L (see e.g. [25], [26]), in particular for a bounded set of complex n x n matrices (see e.g. [5], [10], [24], [7]). This equality is called the Berger-Wang formula or also the generalized spectral radius theorem (for a new elegant proof in the finite dimensional case see [7]). However, in general p(S) and p(S) may differ even in the case of a bounded set S of compact positive operators on L as the following example from [24] shows. Let S = {A1, A2,...} be a bounded set of compact operators on L = /2 defined by Akek = ek+1, (k E IN) and Akej = 0 for j = k. Then (Ai1 Ai2 ■ ■ ■ Aik)2 = 0 for arbitrary k E IN and any subset {i1, i2,..., ik} C IN. Thus p(S) = 0. Since
AmAm-1 ••• A1e1 = em+1, m E IN,
CD
AmAm-1 ■ ■ ■ A1ej = 0, j = 1,
00 CM
Jh
CD
rO
a
CD
a
CD CO
VD
we have /5(E) > limsupm^^ ||Am ■ ■ ■ A^1^ = 1 and so p(E) = /5(E).
In [13], the reader can find an example of two positive non-compact weighted shifts A and B on L = /2 such that p({A, B}) = 0 < p({A, B}).
The theory of the generalized and the joint spectral radius has many important applications for instance to discrete and differential inclusions, wavelets, invariant subspace theory (see e.g. [5], [7], [27], [25], [26] and the references cited there). In particular, /5(E) plays a central role in determining stability in convergence properties of discrete and differential inclusions. In this theory the quantity log /5(E) is known as the maximal Lyapunov exponent (see e.g. [27]).
We will frequently use the following well known fact that
p(tfE) = p(Etf) and p(tfE) = p(Etf), where tfE = {AB : A G tf, B G E}.
3. Results on the generalized and joint spectral radius
0
o
CM
1
CM CO CM CM
£ CO CO
Before proving our main results, let us first state some results that we will need in our proofs. The following result was proved in [8, Theorem 3.3] and [19, Theorem 5.1 and Remark 5.2] using only basic analythic methods and elementary facts.
Theorem 3.1. Given L G L, let {Aj}i^,j=1 be non-negative matrices that define operators on L. If a1, a2,..., am are positive numbers such that a > 1, then the matrix
also defines an operator on L and satisfies
A
(«1)
11 ° ■ ■ ■ ° Aim
the inequalities t8)
i (am)
A
(am)
A
(ai) k1
° Akmm)
(a^ ) ° ■ ■ ■ ° A1am^... (Aka0 ° ■ ■ ■ ° a^) < (au ■ ■ ■ Ak1 )(ai) ° ■ ■ ■ ° (A1m ■ ■ ■ a^ )(am)
(9
and (10) P
A
(ai) 11
A
(am) 1m
A(111) °
A
(am) 1m
Ak1i) °
Aka11) °
A
(am ) km
)|| < 11 An ■■■ Ak1||ai
|A
1m
A
km1
A^)) < P (A11 ■ ■ ■ Ak1)ai ■ ■ ■ p (A1m ■ ■ ■ Akm)C
CO CD
Jh
CD CO
u
a
CD U
The following special case of Theorem 3.1 was considered in the finite dimensional case by several authours using different methods (for references see e.g. [9], [8], [19]).
Corollary 3.2. Given L G L, let A1,..., Am be non-negative matrices that define operators on L and a1, a2,..., am positive numbers such that m=1 a > 1. Then we have
||A1ai) ° A2a2) ° ■ ■ ■ ° A^^ < 11 A1 | ai || A2 |a2 ■ ■ ■ ||Am||am
and (11)
p(A1ai) ° A2a2) ° ■ ■ ■ ° Aiam)) < p(A1)ai p(A2)a2 ■ ■ ■ p(Am)a
a
m
O
o
D
m
a
a
m
00 CM
$H
CD
rO
a
CD
a
CD CO
vO
0 Ö
o
CM
1
CM CO CM CM
£ CO CO
CO CD
$H
CD CO
u
a
CD U
We will also need the following result.
Proposition 3.3. Given L e L, let A, B, C and D be non-negative matrices that define operators on L. Then the following inequalities hold
(12)	(A o B)(C o D) < (A(2)D(2))(2) 0 (B(2)C(2))( 1),
(13)	(A o B)(C o D) < AC o BD,
(14)	(A o B)(C o D) < AD o BC.
Proof. Using A = (A(2))( 2) (and similarly for B, C and D) and applying (8) we obtain
(A o B)(C o D) = (A o B)(D o C) < (A(2)D(2))(2) o (B(2)C(2))(2),
which proves (12) (for a simple direct proof see [22, Proposition 2.3]).
The inequality (13) is a special case of (8). We include a simple proof for completeness. The (i, j)th entry of the matrix (A o B)(C o D) equals k^R aikbikckjdkj and we have
bik ckj dkj = Y^(aik Ckj )(bik dkj ) < ^^ aik ckj ^^ bik dkj,
k£R	k£R	k£R	k£R
which proves (13). By (13) we have
(A o B)(C o D) = (A o B)(D o C) < AD o BC, which proves (14).	□
Let ^ and E be sets of non-negative matrices and a > 0. Then ^ o E and denote
respectively the Hadamard (Schur) product of ^ and E and the Hadamard (Schur) power of ^ e.g.,
^ o E = {A o B : A e tf, B e E} and = {A(a) : A e
The following result on the generalized and the joint spectral radius was stated in ([19, Corollary 5.3]) only in the case of bounded sets of n x n non-negative matrices, however the same proof works in our more general setting by using Theorem 3.1.
Theorem 3.4. Given L e L, let ^i,... ^m be bounded sets of non-negative matrices that define operators on L and let a1, we have
(15) and
(16)
p(*

.. am be positive numbers such thatY^™1 ai > 1. Then o ^m™)) < p(^i)"2 •••
p(^(iai) ◦ ■ ■ ■ O ^) < p(^l)"1 ■ ■ ■ p(^m)C
o
(
m
We are now ready to prove the following result for the generalized and joint spectral radius, which generalizes (5). 00
Theorem 3.5. Given L e L, let ^ and £ be bounded sets of non-negative matrices that define operators on L. Then we have
(17)	o £) < p(^(2)£(2))1 < p((tf o tf)(£ o £))1 < p(^£ o 1 < p(^£)
vD

m
CD
$h
CD
m
and
(18)	o £) < p(^(2)£(2))1 < p((tf o tf)(£ o £))2 < p(^£ o 1 < p(tf£).
Proof. To prove the first inequality in (17), choose A e (^ o £)2m. Then there exist Ai e ^ and Bi e £ for i = 1,..., 2m, such that
A = (Ai o bi)(a2 o B2) ■ ■ ■ (A2m-1 o B2m-l)(A2m o B2J. By (12) and (8) we have
O	A < ((Al2)B22))(2) o (b(2)a22))(2)) ■ ■ ■ ((A2m-iB^)(2) o (B^iA22m)(2))
< B(2) o C2),
where
CD	B = Al2)B22)... A22i-iB22„l e (*(2)£(2) )m
and
c = b(2)a22) ••• B222_iA222 e (£(2)*(2)r.
CO	i i
By Corollary 3.2 we obtain p(A) < p(B) 2p(C) 2. This implies
p(tf o £)2 < p(^(2)£(2))i/2p(£(2)^(2))i/2.
Therefore
p(* o £)2 < p(^(2)£(2)),
since
p(^(2)£(2)) = p(£(2)^(2)).
This proves the first inequality in (17). The second inequality in (17) is trivial, since ^(2)£(2) c (^ o ^)(£ o £). For the proof of the third inequality in (17) take A e ((^ o ^)(£ o £))m. Then there exist Ai, Bi e ^ and Cj, Di e £ for i = 1,..., m such that
A = (Ai o Bi)(Ci o Di) ••• (Am o Bm)(Cm o D„).
By (13) we have
A < (AiCi o BiDi)... (AmCm o B„D„) e (*£ o ^£)m,
which implies p((^ o ^)(£ o £)) < p(^£ o ^£). The last inequality in (17) follows from
Theorem 3.4. This completes the proof of (17) and the inequalities (18) are proved simply
_
by replacing the spectral radius with the operator norm || ■ || in the proof above.	□
CD
If we interchange the roles of ^ and £ in Theorem 3.5, we obtain the following result.
00 CM
and
CD
CM
¡5 CO
Corollary 3.6. Given L e L, let ^ and E be bounded sets of non-negative matrices that define operators on L. Then we have
p((tf O O E))1 < p(E^ O Etf)2 < p(^E)
p((tf o tf)(E o E))1/2 < p(E^ o E^)1/2 < p(^E). The following result generalizes and sharpens the inequalities (2).
CD
Theorem 3.7. Given L e L, let ^ and E be bounded sets of non-negative matrices that define operators on L. Then we have
(19)
OE) < p(^EOEtf)2 < p((^E)(2))4p((E^)(2))4 < p(^EOtfE)1 p(E^oEtf)1 < p(^E)
and
(20)
p(^OE) < p(^EOEtf)2 < p((^E)(2))4p((E^)(2))1 < p(^EOtfE)4p(E^oEtf)1 < p(^E).
O £
Proof. For the proof of the first inequality in (19), choose A e (^ o E)2m. Then there exist Aj e ^ and Bj e E for i = 1,..., 2m, such that
A = (Ai O bI)(a2 O B2) ■ ■ ■ (A2m-1 O B2m-l)(A2m O B2m).
By (14) we obtain
A < (AiB2 o B1A2) ■ ■ ■ (A2m-lB2m O B2m-lA2m) e (*E O E^)™
2 and thus
p(A) < p((A1B2 O B1A2) ■ ■ ■ (A2m-1B2m O B^-^m)). This implies the first inequality in (19).
Also AiBi+1 o BiAi+1 = ((AiBi+1)(2) o (BiAi+1)(2))( 1) for i = 1,..., 2m - 1 and thus we have by (8)
(A1 B2 o B1 A2) ■ ■ ■ (A2m-1B2m O B2m-1A2m) <
fc	((A1B2)(2) ■ ■ ■ (A2m-1B2m)(2))(2) O ((B1A2)(2) ■ ■ ■ (B2m-1 A2m)(2))(1)
By (11) we obtain
i i
p((A1B2 O B1A2) ■ ■ ■ (A2m-1B2m O B2m-1A2m)) < p(B)1 p(C)1,
CO
where
B = (A1B2P ■ ■ ■ (A2m-1B2m)(2) e ((^E)(2))m
and
C = (B1A2)(2) ■ ■ ■ (B2m-1A2m)(2) e ((Etf)(2))m.
This implies
p(^E o Etf) < p((^E)(2))1 p((E^)(2))1, which proves the second inequality in (19).
O
CM
00 CM
$H
CD
rO
a
CD
a
CD CO
vD
The third inequality in (19)is trivial, since (^E)(2) C ^E o ^E. The fourth inequality in (19) follows from Theorem 3.4 since
p(^E o ^E)4p(E^ o Etf)4 < p(^E)2p(Etf)2 = p(^E).
The inequalites (20) are proved by replacing the spectral radius with the operator norm || • || in the proof above.	□
The following result complements Theorems 3.5 and 3.7.
Proposition 3.8. Given L E L, let ^ and E be bounded sets of non-negative matrices that define operators on L. Then we have
(21)	p((tf o tf)(E o E)) < p(^E o tfE)1 p(E^ o Etf)2
and (22)
p((tf O tf)(E O E)) < p(^E O ^E) 1 p(E^ O Etf) 1.
0 o
CM
1
CM CO CM CM
£ CO CO
Proof. By Theorem 3.5 we have
p((tf o tf)(E o E)) = p((tf o tf)(E o E))1 p((E o E)(tf o tf))2 < p(^E o tfE)2p(E^ o Etf)2,
which proves (21). The inequality (22) is proved similarly.	□
The following result follows from Theorem 3.5, Theorem 3.7 and Proposition 3.8 by taking ^ = {A} and E = {B}.
Corollary 3.9. Given L E L, let A and B be non-negative matrices that define operators on L. Then we have
(23)	p(A o B) < p2((A o A)(B o B)) < p(AB o AB)1 p(BA o BA)4 < p(AB) and
(24)	p(A o B) < p2 (AB o BA) < p(AB o AB)1 p(BA o BA)4 < p(AB).
m
CD
$H
CD
m
u
a
CD U
The following example shows that p(AB o AB), p(BA o BA) and p(AB o BA) may in fact be different.
Example 3.10. Let A
and so
0 2
33
and B
33 9 15
AB AB
36 36 81 144
BA BA
01
33
99 81 225
Then AB
66 9 12
BA
AB BA
18 18 81 180
It follows p(AB o AB) = 18(5 + 3^2) = 166.368, p(BA o BA) = 9(13 + 3^17) = 228.324 and p(AB o BA) = 9(11 + 3VTT) = 188.549. We see that p(AB o AB) < p(AB o BA) < p(BA o BA) and thus in general neither of the inequalities between p(AB o AB) and
00 CM
$H
CD
rO
a
CD
a
CD CO
vO
p(AB o BA) hold. This fact was independently observed by A. Schep ([23] and private communication).
Remark 3.11. The previous example also shows that the second inequality in (24) may be strict. This is also true for the second inequality in (23), since p((A o A)(B o B)) = 9(7 + 3^5) = 123.374.
On the otherhand both of the mentioned inequalities are sharp (take e.g. A = B = I or 0).
The following result follows from Theorem 3.5.
Proposition 3.12. Given L e L, let ^ and £ be bounded sets of non-negative matrices that define operators on L. Then we have
(25)	p(^£ o < p(^2£2) and p(^£ o < p(^2£2).
0 Ö
o
CM
1
CM 00 CM CM
£ CO CO
CO CD
$H
CD CO
u
a
CD U
Proof. By Theorem 3.5 applied to and we have
p(^£ o	< p(^££^) = p(^2£2),
which proves the first inequality in (25). The second inequality in (25) is proved similarly.
□
Corollary 3.13. Given L e L, let A and B be non-negative matrices that define operators on L. Then we have
(26)	p(AB o BA) < p(A2B2).
The inequality (26) is not weaker than the inequality (24) as the following example from [23] shows.
Example 3.14. Let A
0 0 1 0
and B
A)(B o B)
00 01
BA = BA o BA
01 00 10 00
. Then AB = AB o AB = (A o while AB BA = A2 = B2 = 0.
Therefore p(ABoBA) = p(A2B2) = 0, while p(AB) = p((Ao A)(BoB)) = p(ABo AB) = p(BA o BA) = 1.
This example also illustrates that in (26) we can not replace AB o BA by (A o A)(B o B) or AB o AB.
To conclude this section we prove the following generalization of the inequality (3).
Theorem 3.15. Given L e L, let ^i, ..., ^m be bounded sets of non-negative matrices that define operators on L. Then we have
(27)	1 o ^2 o ■ ■ ■ o ^m) < p(^i^2 ■ ■ ■ ^m)
and
(28)	p(^i o ^2 o ■ ■ ■ o ^m) < p(^1^2 ■ ■ ■ ^m).
00 CM
Jh
CD
rO
a
CD
a
CD CO
vD
0 ^
&
O
CM
1
CM CO CM CM
£ CO CO
Proof. Take A e (^ o ◦ ■ ■ ■ ◦ ^m)mk. Then A = A^2 ■ ■ ■ Ak, where
A = (Ai 11 o Ai 12 o ■ ■ ■ o Ai 1 m) (Ai 21 o Ai 22 o ■ ■ ■ o Aj 2 m) . . . (Aim1 ◦ Aim2 ◦ ■ ■ ■ o Aimm) for some Aij 1 e ..., Aijm e and all j = 1,...,m, i = 1,... ,k. Then
Ai = (Ai 11 o Ai 12 o ■ ■ ■ o Ai 1 m) (Ai 22 o ■ ■ ■ o Ai 2 m o Ai 21) . . . (Aimm o Aim 1 o ■ ■ ■ o Aimm-1)
By (8) we have
A = A1A2 ■ ■ ■ Ak < B1 o B2 o ■ ■ ■ o Bm,
where
k
B1 = n Ai 11Ai 22 ••• Aimm e (M2 ^m)k,
i=1 k
B2 = n Ai 12Ai 23 ••• Aim 1 e (^2^3 ^)k,
i=1
k
Bm = JT Ai 1 mAi21 ■ ■ ■ Aimm-1 e (^m' ' ' ^m-1)k.
i=1
By Corollary 3.2 we have
p(A) < p(B1)p(B2) ••• p(Bm),
which implies
1 o ^2 o ■ ■ ■ o ^m)m <	■ ■ ■ ^m)p(^2^3 ■ ■ ■ ^1) ■ ■ ■	■ ■ ■ ^m-1) =
= p(^2 ••• ^m)m.
This proves (27) and the inequality (28) is proved similarly.	□
4. Related results in max algebra
CO CD
Jh
CD CO
u
a
CD U
In this final section we prove some related results in max algebra. 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. [4], [6], [3], [21] and the references cited there). Max algebra's usefulness arises from a fact that these non-linear problems become linear when described in the max algebra language. Moreover, recently max algebra techniques were used to solve certain linear algebra problems (see e.g. [11], [12]).
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. The operations between matrices and vectors in the max algebra are defined by analogy with the usual linear algebra. For instance, the product of n x n non-negative matrices A and B in the max algebra is denoted by
A 0 B (not the Kronecker product), where [A 0 B]j = maxk=i.....n aik bkj. The notation A|
means A 0 A, and A^ denotes the k-th max power of A. If x = [x] G IRn is a non-negative vector, then the notation A 0 x means [A 0 x]i = maxj=1,...,n aijXj. The usual associative and distributive laws hold in this algebra. The role of the spectral radius in max algebra is played by the maximum circuit geometric mean.
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 vO	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. [18] and the references cited there). 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 e.g. [4, Theorem 2], [6], [3]). Also, the max version of Gelfand formula holds, i.e.,
MA) = lim ||Am||1/m
m.—>oo
CM
for an arbitrary vector norm || • || on |Rnxn (see e.g. [18] and the references cited there). \k
CD CO
CM 00 CM CM
CO CO
Thus ^(A|) = ^(A)k for all k G IN.
Let tf be a bounded set of n x n non-negative matrices. For m > 1, let
= {A1 0 A2 0 • • • 0 Am : Ai G tf }. The max algebra version of the generalized spectral radius M^) of tf, is defined by
^(tf) = lim sup [ sup p,(A)]1/m
and is equal to

^(tf) = sup [ sup p,(A)]1/m me IN
Also the max algebra version of the Berger-Wang formula holds, i.e.,
CO
M*) = lim [sup ||A||]1/m
CD
for an arbitrary vector norm || • || on |Rnxn (see e.g. [18]). The quantity logMtf) measures the worst case cycle time of certain discrete event systems and it is sometimes called the worst case Lyapunov exponent (see e.g. [3], [20], [14] and the references cited there). It is not difficult to see that
(29)	Af 0 • • • 0 A« = (A1 0 • • • 0 Am)(t)
for all nxn non-negative matrices Ai,..., Am and t > 0. This implies that j(tf(t)) = ^(tf)4 for all t > 0 (see also [18]). We also have j(tf 0 E) = j(E 0 tf), where tf 0 E = {A 0 B : A G tf, B G E}.
For proving the max algebra analogues of the results from the previous section we will need the following result, which was essentially proved in [19]. It follows from [19, Theorem 5.1 and Remark 5.2] and (29).
CSI
u
CD

co
CD
$H
CD
Theorem 4.1. Let {Aj	be n x n non-negative matrices and let ai, a2,..., am be
positive numbers. Then we have
(An0 o ■ ■ ■ o A^) 0 ... 0 (a^ o ■ ■ ■ o A^)
<	(All 0 ■ ■ ■ 0 Afci)(ai) o ■ ■ ■ o (Aim 0 ■ ■ ■ 0 Akm)(am) and
^	j ((a^ o ■ ■ ■ o A^) 0 ... 0 (a^ o ■ ■ ■ o A^))
<	j (A 11 0 ■ ■ ■ 0 Ak i)ai ■ ■ ■ j (Aim 0 ■ ■ ■ 0 Akm)am .
The following result on the max version of the generalized spectral radius was already stated in [19, Corollary 5.3].
o
Corollary 4.2. Let	tfm be bounded sets of n x n non-negative matrices and let
ai,... am be positive numbers.
(30)	o...o ¥"am)) <	•••	.
In contrast with the linear algebra case, we also have the following result. Corollary 4.3. If tf is a bounded set of n x n non-negative matrices, then
l-H	„
(31)	j(tf o tf) = j(tf)2. Proof. Since tf(2) C tf o tf, we have
j(tf(2)) < j(tf o tf) < j(tf)2,
l-H
where the second inequality follows from (30). Since also j(tf(2)) = j(tf)2, the result follows.	□
By replacing the sums with maxk=i.....n in the proof of (13) and (14), we obtain the
following result.
Proposition 4.4. Let A, B, C and D be n x n non-negative matrices. Then we have (32) (A o B) 0 (C o D) < A 0 C o B 0 D and (A o B) 0 (C o D) < A 0 D o B 0 C.
CD
CO
u
a
Remark 4.5. It is easy to verify that
(33)	A 0 C = (A(2) 0 C(2))(2)
00
for n x n non-negative matrices A and C. Thus the max version of (12) is only a restatement of (32).
CD
By applying Theorem 4.1 an Corollary 4.2 we can now prove the following max algebra version of Theorem 3.15. We omit the proof, since it is similar to the proof of Theorem 3.15.
ft
Theorem 4.6. If tf^ tf2,..., tfm are bounded sets of n x n non-negative matrices, then „(tf i o ^2 o ■ ■ ■ o tfm) < „(tf i 0 ^2 0 ■ ■ ■ 0 tfm)
vO
Moreover, applying Proposition 4.4 and Corollary 4.2 we can also prove the following max algebra analogue of Theorem 3.7 and Proposition 3.12. The proof is similar as in the previous section and we omit the details.
o
Theorem 4.7. If tf and £ are bounded sets of n x n non-negative matrices, then we have
„(tf o £) < „(tf 0 £ o £ 0 tf)i/2 < „(tf 0 £)
and
o
CM
i
CM CO
„(tf 0 £ o £ 0 tf) < „(tf| 0 £2).
For single matrices we obtain the following result.
Corollary 4.8. Let Ai,..., Am, A, B be n x n non-negative matrices. Then the following inequalities hold:
„(Ai o ■ ■ ■ o Am) < „(Ai 0 ■ ■ ■ 0 Am), (34)	„(A o B) < „(A 0 B o B 0 A)i/2 < „(A 0 B),
(35)	p,(A 0 B o B 0 A) < „(A| 0 B2).
Remark 4.9. Let tf and £ be bounded sets of n x n non-negative matrices. In contrast with the linear algebra case, we have the following
(36)
„(tf(2) 0£(2)) 2 = „((tfotf)0(£o£))1 = „(tf0£otf0£) 2 = „(£0tfo£0tf) 2 = „(tf0£). Indeed, similarly as in the proof Theorem 3.5 (and using (31)) one can prove
„(tf(2) 0 £(2))1 < „((tf o tf) 0 (£ o £))1 < „(tf 0 £ o tf 0 £)1 = „(tf 0 £).
However, by (33) we have tf 0 £ = (tf(2) 0 £(2))(2) and this implies (36). Of course, we also have
„(tf 0 £) — „((tf 0 £)(2))4 „((£ 0 tf)(2)^
„(tf 0 £) = „((tf 0 £)(2)) 1 „((£ 0 tf)(2))4 = „(tf 0 £ o tf 0 £) 1 „(£ 0 tf o £ 0 tf)4.
00 CM
Jh
CD
rO
a
CD
a
CD CO
vD
0 ^
&
O
CM
1
CM CO CM CM
£ CO CO
m
CD
$H
CD
m
u
a
CD U
We conclude the paper with some examples, showing that the inequalities in (34) and (35) may be strict. All these inequalities are also sharp (take e.g. A = B = 0 or I).
Examples 4.10. (i) Let A
1 1 0 0
and B
00
11
B 0 A = B2 = B and so A o B = A 0 B o B 0 A = 0and A| 0 B2 = A 0 B
Then A 0 B
A2
A,
A. Thus
p(A o B) = p(A 0 B o B 0 A) = 0 < p(A 0 B) = p(A| 0 B|) = 1. So (35) and the second inequality in (34) may be strict.
(ii) Let A
and B = I. Then ^B
B 0 A = A and so
I, A 0 B
A 0 B o B 0 A = A(2). Thus p(A o B) = 1 < p(A 0 B o B 0 A)1 = p(A 0 B) = V2. So also the first inequality in (34) may be strict.
(iii) Let A and B be from Example 3.14. Then p(A o B) = p(A 0 B o B 0 A) = p(A|, 0 B22) = 0 < p(A 0 B) = 1. Thus (35) is not weaker than the second inequality in (34).
Acknowledgments. The author would like to thank Professor R. Drnovsek for several valuable remarks on the first version of this paper and for pointing out papers [22] and [16]. The author would also like to thank Professor A.R. Schep for useful private communications and for sending the preprint [23].
This work was supported by the Slovenian Research Agency.
References
[1]	C.D. Aliprantis and O. Burkinshaw, Positive operators, Academic Press, Orlando, 1985.
[2]	K.M.R. Audenaert, Spectral radius of Hadamard product versus conventional product for nonnegative matrices, Linear Algebra Appl. 432(1) (2010), 366-368.
[3]	F.L. Baccelli, G. Cohen, G.-J. Olsder and J.-P.Quadrat, Synchronization and Linearity, John Wiley, Chichester, New York, 1992.
[4]	R.B. Bapat, A max version of the Perron-Frobenius theorem, Linear Algebra Appl. 275-276, (1998), 3-18.
[5]	M.A. Berger and Y. Wang, Bounded semigroups of matrices, Linear Algebra Appl. 166 (1992), 21-27.
[6]	P. Butkovic, Max-linear systems: theory and algorithms, Springer-Verlag, London, 2010.
[7]	X. Dai, Extremal and Barabanov semi-norms of a semigroup generated by a bounded family of matrices, J. Math. Anal. Appl. 379 (2011) 827-833.
[8]	R. Drnovsek and A. Peperko, Inequalities for the Hadamard weighted geometric mean of positive kernel operators on Banach function spaces, Positivity 10 (2006), 613-626.
[9]	R. Drnovsek and A. Peperko, On the spectral radius of positive operators on Banach sequence spaces, Linear Algebra Appl. 433 (2010) 241-247.
[10]	L. Elsner, The generalized spectral radius theorem: An analytic-geometric proof, Linear Algebra Appl. 220 (1995), 151-159.
[11]	L. Elsner and P. van den Driessche, Bounds for the Perron root using max eigenvalues, Linear Algebra Appl. 428 (2008), 2000-2005.
[12]	S. Gaubert and M. Sharify, Tropical scaling of polynomial matrices, Lecture Notes in Control and Information Sciences 389 (2009), 291-303.
[13]	P.S. Guinand, On quasinilpotent semigroup of operators, Proc. Amer. Math. Soc. 86 (1982), 485486.
00 CM
$H
CD
rO
a
CD
a
CD CO
vO
0 Ö
o
CM
1
CM CO CM CM
£ CO CO
[14
[1B
[16
[1T [1S
[19
[20
[21
[22
[23
[24
[2B
[26
[2T
[2S [29
on H C max	Smax
properties and asymptotic stability in the max algebra,
B.B. Gursoy and O. Mason, P^ Lin. Algebra Appl. 435 (2011), 1008-1018.
R.A. Horn and F. Zhang, Bounds on the spectral radius of a Hadamard product of nonnegative
or positive semidefinite matrices, Electron. J. Linear Algebra 20, (2010), 90-94.
Z. Huang, On the spectral radius and the spectral norm of Hadamard products of nonnegative
matrices, Linear Algebra Appl. 434 (2011), 457-462.
P. Meyer-Nieberg, Banach lattices, Springer-Verlag, Berlin, 1991.
A. Peperko, On the max version of the generalized spectral radius theorem, Linear Algebra Appl. 428 (2008), 2312-2318.
A. Peperko, Inequalities for the spectral radius of non-negative functions, Positivity 13 (2009), 255-272.
A. Peperko, On the continuity of the generalized spectral radius in max algebra, Linear Algebra Appl. 435 (2011), 902-907.
A. Peperko, On the functional inequality for the spectral radius of compact operators, Linear and Multilinear Algebra 59 (4) (2011), 357-364
A.R. Schep, Bounds on the spectral radius of Hadamard products of positive operators on lp-spaces, Electronic J. Linear Algebra 22, (2011), 443-447.
A.R. Schep, Corrigendum for "Bounds on the spectral radius of Hadamard products of positive operators on lp-spaces", preprint 2011.
M.-H. Shih, J.-W. Wu, C.-T. Pang, Asymptotic stability and generalized Gelfand spectral radius formula, Linear Alg. Appl. 252 (1997), 61-70.
V.S. Shulman and Yu.V. Turovskii, Joint spectral radius, operator semigroups and a problem of W.Wojtynski, J. Fund. Anal. 177 (2000), 383-441.
V. S. Shulman, Yu. V. Turovskii, Application of topological radicals to calculation of joint spectral radii, (2008), arxiv:0805.0209v1 [math.FA].
F. Wirth, The generalized spectral radius and extremal norms, Linear Algebra Appl. 342 (2002), 17-40.
A.C. Zaanen, Riesz spaces II, North Holland, Amsterdam, 1983.
X. Zhan, Unsolved matrix problems, Talk given at Advanced Workshop on Trends and Developments in Linear Algebra, ICTP, Trieste, Italy, July 6-10, 2009.
Aljosa Peperko
Faculty of Mechanical Engeenering University of Ljubljana Aškerčeva 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
CO CD
$H
CD CO
u
a
CD U