BOUNDED INDECOMPOSABLE SEMIGROUPS OF NON-NEGATIVE MATRICES

HAILEGEBRIEL GESSESSE, ALEXEY I. POPOV, HEYDAR RADJAVI, EUGENIU SPINU, ADI TCACIUC, AND VLADIMIR G. TROITSKY

Abstract. A semigroup 𝔖 of non-negative n × n matrices is indecomposable if for every pair i, j ⩽ n there exists S ∈ 𝔖 such that (S)_{ij} ≠ 0. We show that if there is a pair k, l such that {(S)_{kl} : S ∈ 𝔖} is bounded then, after a positive diagonal similarity, all the entries are in [0, 1]. We also provide quantitative versions of this result, as well as extensions to infinite-dimensional cases.

1. Introduction

The following general type of question has been of interest in various contexts, including linear representations of groups and semigroups: if something about a group or a semigroup 𝔖 is ”small” in some sense, then is 𝔖 itself small? For example, it is well known that if 𝔖 is an irreducible group of matrices, and if the trace functional takes a finite number of values on 𝔖, then 𝔖 is itself finite (irreducible means no common proper non-trivial invariant subspaces). Okninsky in [Ok98, Proposition 4.9] generalizes this to irreducible semigroups. A further extension to another version of “smallness” is given in [RR08]: it replaces the trace functional with any nontrivial linear functional. Yet another measure of ”smallness” is boundedness. For example, if the values of a nontrivial linear functional on an irreducible semigroup 𝔖 form a bounded set, then 𝔖 itself is bounded. For this and other instances of this local-to-global phenomena see [RR08].

In this paper we discuss another variation on this question which is more suitable in the positivity setting. We consider semigroups of non-negative matrices, replace the irreducibility assumption on 𝔖 with the weaker hypothesis of indecomposablity, i.e., no common invariant ideals, and ask: if a non-negative linear functional has bounded values on 𝔖, then is 𝔖 necessarily bounded? The version of this problem in which ”smallness” is interpreted as finiteness has also been studied in [LMR].

Positivity, 14(3) (2010), 383–394

1 2 H. GESSESSE, A. I. POPOV, H. RADJAVI, E. SPINU, A. TCACIUC, AND V. G. TROITSKY

Date: May 19, 2009.

2000 Mathematics Subject Classification. Primary: 15A48. Secondary: 20M20, 47D03, 47B65.

Key words and phrases. non-negative matrices, semigroups of matrices, positive operators.

The third, fifth, and sixth authors were supported by NSERC.

Throughout this paper, all the matrices are taken over ℝ. For two n × n matrices A and B, we write A ⩽ B if (A)_{ij} ⩽ (B)_{ij} for every pair i, j ⩽ n. A matrix A is non-negative if A ⩾ 0 and positive if (A)_{ij} > 0 for every i, j.^{1} We will write M_{n}^{+}(ℝ) for all non-negative n × n real matrices. By E_{ij} we will denote the ij-th elementary matrix.

A (multiplicative) semigroup 𝔖 of M_{n}^{+}(ℝ) is said to be indecomposable if for every i, j ⩽ n there exists S ∈ 𝔖 with (S)_{ij} > 0. The following two lemmas are straightforward and standard; see [Min88] for more details.

Proposition 1. Let 𝔖 be a semigroup in M_{n}^{+}(ℝ). Then the following statements are equivalent.

(i) 𝔖 is indecomposable; (ii) 𝔖 has no common non-trivial proper invariant ideals (i.e., subspaces spanned

by a subset of the standard basis); (iii) No permutation of the basis reduces 𝔖 to the block form [ \begin{matrix}∗ & ∗ \\ 0 & ∗ \end{matrix}] .

Remark 2. Let A, D ∈ M_{n}(ℝ) such that D is diagonal and invertible, A = (a_{ij}) and D = diag(d_{1}, …, d_{n}). Then the ij-th entry of D^{−1}AD equals \frac{d_{j}}{d_{i}} a_{ij}. In particular, the diagonal entries of A and of D^{−1}AD agree.

Remark 3. Let 𝔖 be a semigroup in M_{n}^{+}(ℝ). Since M_{n}(ℝ) is finite-dimensional, the following are equivalent:

(i) 𝔖 is norm bounded; (ii) 𝔖 is bounded entry-wise, i.e., sup{(S)_{ij} : S ∈ 𝔖} < +∞ for every pair

i, j ⩽ n; (iii) 𝔖 is order bounded, i.e., there exists T ∈ M_{n}(ℝ) such that S ⩽ T for every

S ∈ 𝔖. In this case, we write 𝔖 ⩽ T. In this case, sup 𝔖 is defined. That is, sup 𝔖 is the matrix whose ij-th entry is sup{(S)_{ij} : S ∈ 𝔖}.

Lemma 4. Let 𝔖 be a bounded semigroup in M_{n}^{+}(ℝ) and D a diagonal matrix with positive diagonal entries. Then D^{−1}𝔖D is again a bounded semigroup and sup(D^{−1}𝔖D) = D^{−1}(sup 𝔖)D.

A matrix T = (t_{ij}) will be called compressed if T ⩾ 0 and t_{ij}t_{jk} ⩽ t_{ik} for all i, j, and k. The following observations are straightforward.

1Note that in Banach lattice theory, A ⩾ 0 is usually termed “positive”, while ∀i, j (A)_{ij} > 0 is termed “strictly positive”.

INDECOMPOSABLE SEMIGROUPS 3

Lemma 5. (i) If T = (t_{ij}) is compressed then t_{ii} ⩽ 1 for all i.

(ii) If 𝔖 is a bounded semigroup in M_{n}^{+}(ℝ) then T = sup 𝔖 is compressed. In this

case, 𝔖 is indecomposable iff T is positive. (iii) Let T be a compressed matrix and D a diagonal matrix with positive diagonal

entries. Then D^{−1}T D is compressed.

2. Main results

Let 𝔖 be an indecomposable semigroup in M_{n}^{+}(ℝ). In this section we show that if 𝔖 is bounded then, after a positive diagonal similarity, all its entries are bounded by 1. Moreover, it suffices to assume only that the set {(S)_{ij} : S ∈ 𝔖} is bounded for some pair (i, j). Next, we will show that if the diagonal entries in 𝔖 are (uniformly) bounded by some ϵ > 0, then, after a positive diagonal similarity, all the entries are uniformly bounded by \sqrt[n]{ε}.

Given r > 0, we write M_{n}([0, r]) for the set of all n × n matrices with entries in [0, r].

Lemma 6. Suppose that r ⩾ 1 and T ∈ M_{n}([0, r]) is compressed. Then there exists D = diag(d_{m})_{m=1}^{n} with (d_{m}) ⊂ [\frac{1}{r}, r] such that D^{−1}T D ∈ M_{n}([0, 1]).

Proof. Let T = (t_{ij}). Since T is compressed, t_{ii} ⩽ 1 for all i. We will inductively construct (d_{m})_{m=1}^{n}. For every m ⩽ n we will put

D_{m} = diag(d_{1}, …, d_{m}, 1, 1, …, 1).

Note that for every m > 1, D_{m}^{−1}T D_{m} can be obtained from D_{m−1}^{−1}T D_{m−1} by scaling the m-th column of the latter by d_{m} and the m-th row by \frac{1}{d_{m}}. It follows that the upper left m × m corners of D_{k}^{−1}T D_{k} are the same for all k ⩾ m and agree with the upper left m × m corner of D^{−1}T D. Therefore, it suffices to show that the m × m upper left corner of D_{m}^{−1}T D_{m} is in M_{m}([0, 1]) for every m = 1, …, n.

Put d_{1} = 1. Suppose that d_{1}, …, d_{m−1} have already been constructed (in the interval [\frac{1}{r}, r]) so that U := D_{m−1}^{−1}T D_{m−1} is in M_{n}([0, r]) and its (m − 1) × (m − 1) upper left corner is in M_{m−1}([0, 1]). Put U = (u_{ij}). Once we assign a value to d_{m}, we will write V = D_{m}^{−1}T D_{m}, V = (v_{ij}). Put

a = max_{i=1,...,m−1} u_{im}  and  b = max_{j=1,...,m−1} u_{mj}.

Suppose first that both a and b are less then or equal to 1. In this case, the m × m upper left corner of U is already in M_{m}([0, 1]). Take d_{m} = 1; then V = U. Suppose now that max{a, b} > 1.

4 H. GESSESSE, A. I. POPOV, H. RADJAVI, E. SPINU, A. TCACIUC, AND V. G. TROITSKY

Case a ⩾ b. Then 1 < a ⩽ r and there exists k < m such that u_{km} = a. In this case, we put d_{m} = \frac{1}{a}, then \frac{1}{r} ⩽ d_{m} < 1. Since the m-th column of V is obtained by dividing the m-th column of U by a (except v_{mm} which equals t_{mm} ⩽ 1), we have v_{im} ⩽ 1 as i = 1, …, m and v_{im} ⩽ u_{im} ⩽ r as i > m. Also, v_{km} = 1. Since V is compressed, for every j ≠ m we have

v_{mj} = v_{km}v_{mj} ⩽ v_{kj} = u_{kj}

because k < m. It follows that v_{mj} ⩽ 1 for j = 1, …, m and v_{mj} ⩽ r for every j > m. Hence, V is in M_{n}([0, r]) and its m × m upper left corner is in M_{m}([0, 1]).

Case b > a. This case is similar. We have 1 < b ⩽ r and there exists k < m such that u_{mk} = b. Put d_{m} = b. Since the m-th row of V is obtained by dividing the m-th row of U by b (except v_{mm} which equals t_{mm} ⩽ 1), we have v_{mj} ⩽ 1 as j = 1, …, m and v_{mj} ⩽ u_{mj} ⩽ r as j > m. Also, v_{mk} = 1. Since V is compressed, for every i ≠ m we have

v_{im} = v_{im}v_{mk} ⩽ v_{ik} = u_{ik}

as before. It follows that v_{im} ⩽ 1 for i = 1, …, m and v_{im} ⩽ r for i > m. Hence, V is in M_{n}([0, r]) and its m × m upper left corner is in M_{m}([0, 1]). □

Theorem 7. Let r ⩾ 1 and 𝔖 be a semigroup in M_{n}([0, r]). Then there exists D = diag(d_{m})_{m=1}^{n} with (d_{m}) ⊂ [\frac{1}{r}, r] such that D^{−1}𝔖D ∈ M_{n}([0, 1]).

Proof. Let T = sup 𝔖. Then T is compressed. Let D be as in Lemma 6. Now Lemma 4 yields D^{−1}𝔖D ⩽ D^{−1}T D, and the result follows. □

Proposition 8. Let 𝔖 be an indecomposable semigroup in M_{n}^{+}(ℝ). Suppose that there exists a non-zero non-negative functional ϕ ∈ (M_{n}(ℝ))^{∗} such that the set {ϕ(S) : S ∈ 𝔖} is bounded. Then 𝔖 is bounded.

Proof. Write

ϕ(A) = ∑_{i,j=1}^{n} c_{ij}a_{ij}, A = (a_{ij}),

where c_{ij} ⩾ 0. Since ϕ is non-zero, there exist k, l such that c_{kl} ≠ 0. Since ϕ(A) ⩾ c_{kl}a_{kl} for every positive matrix A = (a_{ij}), the set {(S)_{kl} : S ∈ 𝔖} is bounded.

To finish the proof, it suffices to show that the set {(S)_{ij}: S ∈ 𝔖} is bounded for every pair of indices i, j ⩽ n. Suppose that this statement is not true: there exist two indices i, j ⩽ n and a sequence (S_{m}) in 𝔖 such that (S_{m})_{ij} → ∞ as m → ∞. There are two matrices A = (a_{ij}) and B = (b_{ij}) in 𝔖 such that a_{ki} ≠ 0 and b_{jl} ≠ 0. Then

a_{ki}(S_{m})_{ij}b_{jl} ⩽ (AS_{m}B)_{kl} ⩽ sup{(S)_{kl}: S ∈ S} < ∞ holds for every m ∈ ℕ, which is impossible. □

Combining Theorem 7 with Proposition 8, we immediately get the following results.

Corollary 9. Let 𝔖 be an indecomposable semigroup in M_{n}^{+}(ℝ) such that φ(𝔖) is bounded for some positive functional ϕ ∈ (M_{n}(ℝ))^{∗}. Then there exists a diagonal matrix D with positive diagonal entries such that D^{−1}𝔖D ⊆ M_{n}([0, 1]).

Corollary 10. Let 𝔖 be an indecomposable semigroup in M_{n}^{+}(ℝ) such that the set {(S)_{ij} : S ∈ 𝔖} is bounded for some pair (i, j). Then there exists a diagonal matrix D with positive diagonal entries such that D^{−1}𝔖D ⊆ M_{n}([0, 1]).

We have proved that if 𝔖 is bounded at a single entry then, after a positive diagonal similarity, all its entries are bounded by 1. Next, we will try to replace “bounded” with “small”. We will show that if all the diagonal entries of 𝔖 are small then all the entries are small (after a positive diagonal similarity).

Lemma 11. Let T = (t_{ij}) be an n × n positive compressed matrix and ε > 0. If t_{ii} < ε for all i ⩽ n then there exists a diagonal matrix D with positive diagonal entries such that D^{−1}T D ∈ M_{n}([0, \sqrt[n]{ε}]).

Proof. If ε = 1, the result follows immediately from Lemma 6. So we assume for the rest of the proof that ε < 1. Let

(1)  δ = inf_{D}{max_{i,j}(D^{−1}T D)_{ij}},

where the infimum is taken over all diagonal matrices D with positive diagonal entries. Let t_{max} = max_{i,j} t_{ij} and t_{min} = min_{i,j} t_{ij}. Note that t_{min} > 0 as T is positive. Put

D = \{diag(d_{1}, …, d_{n}) : 1 ⩽ d_{i} ⩽ \frac{t_{max}}{t_{min}} for all i = 1, …, n\}.

We claim that the infimum in (1) can be taken over all D ∈ D. Indeed, let D be a diagonal matrix with positive diagonal entries. Scaling D by a positive scalar we may assume that min d_{i} = 1 without changing D^{−1}T D. Let i_{0} ⩽ n be such that d_{i_{0}} = 1; put V = D^{−1}T D, V = (v_{ij}). If there is a pair (i, j) such that v_{ij} > t_{max} then replacing D with I will only decrease max_{i,j}(D^{−1}T D)_{ij}; and I ∈ D. So we may assume that v_{ij} ⩽ t_{max} for all i and j. Then, for every j we have

t_{max} ⩾ v_{i_{0}j} = t_{i_{0}j} \frac{d_{j}}{d_{i_{0}}} ⩾ t_{min}d_{j},

so that d_{j} ⩽ \frac{t_{max}}{t_{min}} , hence D ∈ D. This completes the proof of the claim.

6 H. GESSESSE, A. I. POPOV, H. RADJAVI, E. SPINU, A. TCACIUC, AND V. G. TROITSKY

Since D is compact, it follows that the infimum in (1) is, actually, attained at some D. Let D = diag(d_{1}, …, d_{n}) and put V = D^{−1}T D, V = (v_{ij}). Then δ = max_{i,j} v_{ij}. Moreover, we may choose D so that the number of occurrences of δ in V is the smallest possible. Note that V is compressed by Lemma 5. It is left to show that δ ⩽ \sqrt[n]{ε}. Suppose that, on the contrary, δ > \sqrt[n]{ε}.

It follows that δ > ε, so that δ never occurs on the diagonal of V. Hence, after a permutation of the basis, we may assume that v_{12} = δ. We claim that v_{2j} = δ for some j. Indeed, otherwise, we could slightly decrease d_{2} so that the non-diagonal entries in the second row of V increase but stay below δ, but then the non-diagonal entries in the second column of V would decrease, so that v_{12} would become less then δ; but this would contradict our assumption that V has the smallest possible number of occurrences of δ. Since δ never occurs on the diagonal of V we know that j ≠ 2. Note also that j ≠ 1 as, otherwise,

δ^{n} ⩽ δ^{2} = v_{12}v_{21} ⩽ v_{11} = t_{11} ⩽ ε

would contradict our assumption that δ > \sqrt[n]{ε}. Thus, j > 2. Again, by a permutation of the basis vectors e⃗_{3}, …, e⃗_{n}, we may assume that j = 3, so that v_{23} = δ.

As in the preceding paragraph, we observe that v_{3j} = δ for some j. Again, we must have j > 3 because

if j = 1 then δ^{n} ⩽ δ^{3} = v_{12}v_{23}v_{31} ⩽ v_{11} = t_{11} ⩽ ε,
if j = 2 then δ^{n} ⩽ δ^{2} = v_{23}v_{32} ⩽ v_{22} = t_{22} ⩽ ε,
if j = 3 then δ^{n} ⩽ δ = v_{33} = t_{33} ⩽ ε;

each case contradicts δ > \sqrt[n]{ε}. Again, by a permutation of the basis vectors e⃗_{4}, …, e⃗_{n}, we may assume that j = 4, so that v_{34} = δ.

Proceeding inductively, we show that for each m ⩽ n we have (after a permutation of the basis) v_{12} = ⋯ = v_{m−1,m} = δ, and that v_{mj} = δ for some j. Furthermore, j > m as, otherwise, we would get δ^{n} ⩽ δ^{m} ⩽ ε. But this leads to a contradiction for m = n as j > n is impossible. □

Theorem 12. Let 𝔖 be an indecomposable semigroup in M_{n}^{+}(ℝ) and ε > 0. If all the diagonal entries in all the matrices in 𝔖 are less than or equal to ε then there exists a diagonal matrix D with positive diagonal entries such that D^{−1}𝔖D ⊆ M_{n}([0, \sqrt[n]{ε}]).

Proof. By Proposition 8, 𝔖 is bounded. Let T = sup 𝔖. Then T is positive and compressed by Lemma 5. By Lemma 11, there exists a diagonal matrix D with positive

INDECOMPOSABLE SEMIGROUPS 7

diagonal entries such that D^{−1}T D ∈ M_{n}([0, \sqrt[n]{ε}]). By Lemma 4, D^{−1}𝔖D ⩽ D^{−1}T D, so that D^{−1}𝔖D ⊆ M_{n}([0, \sqrt[n]{ε}]). □

The following example shows that the estimate obtained in Theorem 12 is sharp.

Example 13. Take any ε ∈ (0, 1] and put δ = \sqrt[n]{ε}. Let

P = [\begin{matrix}0 & δ & 0 & 0 & … & 0 \\ 0 & 0 & δ & 0 & … & 0 \\ ⋮ & ⋮ & ... & ... & ... & 0 \\ 0 & 0 & … & 0 & δ & 0 \\ 0 & 0 & … & … & 0 & δ \\ δ & 0 & … & … & 0 & 0 \end{matrix}]

Let 𝔖 = {P^{k} : k = 1, 2, … }. Clearly, 𝔖 is an indecomposable semigroup. The diagonal elements of P^{k} are all zeros for each 1 ⩽ k ⩽ n−1, and P^{n} = δ^{n}I = εI. Also, P^{k+n} = P^{k}P^{n} = δ^{n}P^{k} ⩽ P^{k}. Thus, the maximal value for every diagonal element over all the matrices in 𝔖 is ε. On the other hand, (P)_{i,i+1} = (P)_{n,1} = δ = \sqrt[n]{ε} for all 1 ⩽ i < n. It is clear that this bound cannot be decreased by a positive diagonal similarity.

It might be natural to ask whether the assumption about the smallness of the diagonal entries in Theorem 11 could be replaced with smallness of some other functionals. For example, could it be sufficient to assume that a certain entry is small in all the matrices of 𝔖? The following example shows that the answer is negative.

Example 14. Let ε > 0. Generate a semigroup 𝔖 by the following matrices:

A = [\begin{matrix}ε & 0 \\ 0 & 0 \end{matrix}] , B = [\begin{matrix}0 & ε \\ 0 & 0 \end{matrix}] , C = [\begin{matrix}0 & 0 \\ ε & 0 \end{matrix}] , D = [\begin{matrix}0 & 0 \\ 0 & 1 \end{matrix}] .

Clearly, 𝔖 is indecomposable. Also, it can be easily checked that

B^{2} = C^{2} = AC = BA = DA = DB = CD = 0,

AB ⩽ B, CA ⩽ C, BC ⩽ A, CB ⩽ D, BD = B, DC = C, A^{2} ⩽ A, and D^{2} = D. Hence, (S)_{11} ⩽ ε, (S)_{12} ⩽ ε, and (S)_{21} ⩽ ε for all S ∈ 𝔖. Nevertheless, (D)_{22} = 1, and this cannot be made any smaller by applying a diagonal similarity since a diagonal similarity does not change diagonal entries of matrices.

3. An extension to infinite matrices

In this section, we extend Lemma 6 and Theorem 7 to the infinite-dimensional case. We start with extending our terminology. By an infinite non-negative matrix we will mean a double sequence S = (s_{ij})_{i,j=1}^{∞} with s_{ij} ⩾ 0 for all i, j ∈ ℕ. The set of

8 H. GESSESSE, A. I. POPOV, H. RADJAVI, E. SPINU, A. TCACIUC, AND V. G. TROITSKY

all such matrices will be denoted M_{∞}^{+}(ℝ). We will write S ∈ M_{∞}([0, r]) if s_{ij} ⩽ r for some fixed r > 0. We say that T = (t_{ij}) ∈ M_{∞}^{+}(ℝ) is compressed if t_{ik}t_{kj} ⩽ t_{ij} for all i, j, and k. For S, T, R ∈ M_{∞}^{+}(ℝ), we write R = ST if r_{ij} = ∑_{k=1}^{∞} s_{ik}t_{kj} for every i and j in ℕ (in particular, the series converges). A subset 𝔖 of M_{∞}^{+}(ℝ) will be called a semigroup if ST exists and belongs to 𝔖 whenever S, T ∈ 𝔖. It is easy to see that in this case the multiplication is associative on 𝔖. A semigroup 𝔖 in M_{∞}^{+}(ℝ) is said to be indecomposable if for every i, j ∈ ℕ there exists A ∈ 𝔖 such that (A)_{ij} ≠ 0. A semigroup 𝔖 in M_{∞}^{+}(ℝ) is said to bounded entry-wise if t_{ij} := sup{(S)_{ij} : S ∈ 𝔖} is finite for every pair i, j. In this case, we write T = sup 𝔖 where T = (t_{ij}). It is easy to see that, in this case, T is compressed. Then 𝔖 is indecomposable iff t_{ij} > 0 for all i and j.

The following lemma is straightforward.

Lemma 15. Suppose that D = diag(d_{m})_{m=1}^{∞} ∈ M_{∞}^{+}(ℝ) such that d_{m} > 0 for all i. (i) D^{−1} := diag(d_{m}^{−1}) ∈ M_{∞}^{+}(ℝ) and D^{−1}D = DD^{−1} = I. (ii) For every A ∈ M_{∞}^{+}(ℝ), A = (a_{ij}), the matrix D^{−1}AD ∈ M_{∞}^{+}(ℝ) and its ij-th

entry equals a_{ij} \frac{d_{j}}{d_{i}}. If S is compressed then so is D^{−1}AD. (iii) If 𝔖 ⊂ M_{∞}^{+}(ℝ) is an entry-wise bounded semigroup then so is D^{−1}𝔖D. More-

over, if 𝔖 is bounded entry-wise, then D^{−1}𝔖D is bounded entry-wise and sup D^{−1}𝔖D = D^{−1} sup 𝔖D.

The proofs of Lemma 16 and Theorem 17 repeat almost verbatim the proofs of Lemma 6 and Theorem 7; just replace n with ∞.

Lemma 16. Suppose that r ⩾ 1 and T ∈ M_{∞}([0, r]) is compressed. Then there exists D = diag(d_{m}) with (d_{m}) ⊂ [\frac{1}{r}, r] such that D^{−1}T D ∈ M_{∞}([0, 1]).

Theorem 17. Let r ⩾ 1 and 𝔖 be a semigroup in M_{∞}([0, r]). Then there exists D = diag(d_{m}) with (d_{m}) ⊂ [\frac{1}{r}, r] such that D^{−1}𝔖D ∈ M_{∞}([0, 1]).

Next, we will prove an analogue of Corollary 10.

Lemma 18. Suppose that T ∈ M_{∞}^{+}(ℝ) is positive and compressed. Then there exists D = diag(d_{m}) with d_{m} > 0 for all m such that D^{−1}T D ∈ M_{∞}([0, 1]).

Proof. Put d_{1} = 1. Inductively define positive numbers d_{2}, d_{3} …, so that, for D = diag(d_{m}), V = D^{−1}T D, V = (v_{ij}), we have for every m:

(i) v_{im} ⩽ 1 whenever i ⩽ m, and

(ii) there exists i_{m} < m such that v_{i_{m}m} = 1.

INDECOMPOSABLE SEMIGROUPS 9

Indeed, once d_{1}, …, d_{m−1} are chosen, put D_{m−1} = diag(d_{1}, …, d_{m−1}, 1, 1, …), and take d_{m} to be the reciprocal of the maximal element in the m-th column of D_{m−1}^{−1}T D_{m−1} above the diagonal.

By Lemma 15, V is compressed and v_{ii} = t_{ii} ⩽ 1 for every i. To show that V ∈ M_{n}([0, 1]), we will prove by induction on m that the m × m upper-left corner of V is in M_{m}([0, 1]). For m = 1 we have v_{11} = t_{11} ⩽ 1. Suppose that m > 1 and the (m−1)×(m−1) upper-left corner of V is in M_{m−1}([0, 1]). Take i, j ⩽ m; we will show that v_{ij} ⩽ 1. If i, j < m, there is nothing to prove. If j = m then we are done by (i). Suppose that j < i = m. Note that v_{i_{m},m} = 1 by (ii). By Lemma 15, V is compressed, so that

v_{ij} = v_{mj} = v_{i_{m},m}v_{mj} ⩽ v_{i_{m},j} ⩽ 1

by the induction hypothesis, as i_{m} < m and j < m. □

Theorem 19. Let 𝔖 be an indecomposable semigroup in M_{∞}^{+}(ℝ). If there exist k, l ∈ ℕ such that the set {(S)_{kl} : S ∈ 𝔖} is bounded then there exists D = diag(d_{m}) with d_{m} > 0 for all m such that D^{−1}𝔖D ∈ M_{∞}([0, 1]).

Proof. First, we will show that 𝔖 is entry-wise bounded. Suppose not. Then there exist i, j ∈ ℕ and a sequence (S_{n}) in 𝔖 such that (S_{n})_{ij} → +∞ as n → +∞. Since 𝔖 is indecomposable, there exist A, B ∈ 𝔖 such that (A)_{ki} ≠ 0 and (B)_{jl} ≠ 0. Then (AS_{n}B)_{kl} ⩾ (A)_{ki}(S_{n})_{ij}(B)_{jl} → +∞; a contradiction. Hence, 𝔖 is entry-wise bounded.

Put T = sup 𝔖, then T is compressed. Let D be as in Lemma 18. Lemma 15 yields D^{−1}𝔖D ⩽ D^{−1}T D, so that D^{−1}𝔖D ∈ M_{∞}([0, 1]). □

We would like to mention an immediate application to discrete Banach lattices. For the relevant terminology and more details, we refer the reader to [AA02, LT77]. Suppose that X is a Banach lattice where the order is generated by a 1-unconditional basis (e_{n}), that is, ∑_{n=1}^{∞} α_{n}e_{n} ⩽ ∑_{n=1}^{∞} β_{n}e_{n} iff α_{n} ⩽ β_{n} for all n (for example, X could be ℓ_{p} with 1 ⩽ p < 1 or c_{0}). By scaling the vectors of the basis, we may usually assume without loss of generality that the basis is normalized, i.e., ∥e_{i}∥ = 1 for every i.

Recall that an operator T: X → X determines an infinite matrix t_{ij} via T e_{j} = ∑_{i=1}^{∞} t_{ij}e_{i}. The product of any two bounded operators agrees with the matrix product of their infinite matrices. An operator T is said to be positive if T x ⩾ 0 whenever x ⩾ 0 or, equivalently, if its matrix is non-negative. In this case, T is automatically bounded (see, e.g., [AA02]).

10 H. GESSESSE, A. I. POPOV, H. RADJAVI, E. SPINU, A. TCACIUC, AND V. G. TROITSKY

An operator D is called diagonal if its infinite matrix is diagonal. Suppose D = diag(d_{m})_{m=1}^{∞}, then D is bounded iff the sequence (d_{m}) is bounded; D is invertible with D^{−1} = diag(d_{m}^{−1}) as long as inf d_{m} > 0.

Corollary 20. Let X be a Banach lattice with the order given by a 1-unconditional basis, and 𝔖 a semigroup of positive operators on X. If there exists r ⩾ 1 such that (S)_{ij} ⩽ r for all S ∈ 𝔖 and i, j ∈ ℕ then there exists D = diag(d_{m}) with (d_{m}) ⊂ [\frac{1}{r}, r] such that all the entries of D^{−1}𝔖D are in [0, 1].

Corollary 21. Let X be a Banach lattice with the order given by a 1-unconditional normalized basis, and 𝔖 a semigroup of positive operators on X. If 𝔖 ⩽ T for some bounded operator T, then there exists an invertible positive diagonal operator D such that all the entries of D^{−1}𝔖D are in [0, 1].

Proof. The matrix of T is entry-wise bounded because t_{ij}e_{i} ⩽ T e_{j} yields t_{ij} ⩽ ∥T ∥ for all i, j. Now apply Corollary 20 with r = ∥T ∥. □

The following example shows that Theorem 19 cannot be extended to bounded operators on discrete Banach lattices.

Example 22. An entry-wise bounded semigroup 𝔖 of bounded positive operators on ℓ_{1} such that there is no positive diagonal operator D: ℓ_{1} → ℓ_{1} with all the entries of D^{−1}𝔖D in [0, 1].

Let 𝔖 = \{\frac{i}{j} E_{ij} : i, j ∈ ℕ\} ∪ \{0\}. It can be easily verified that 𝔖 is an entrywise bounded semigroup 𝔖 of bounded positive operators on ℓ_{1}. Suppose that D = diag(d_{i})_{i=1}^{∞} such that d_{i} > 0 for all i and all the entries of D^{−1}𝔖D are in [0, 1]. In particular, for any i ∈ ℕ we have iE_{i1} ∈ 𝔖 and the (i, 1)th entry of D^{−1}(iE_{i1})D is i\frac{d_{1}}{d_{i}}, so that d_{i} → +∞ as i → +∞. It follows that D is not an operator on ℓ_{1}.

Note that 𝔖 is the semigroup generated by nE_{n1} and \frac{1}{n}E_{1n} for all n ∈ ℕ. If, instead, we generate 𝔖 by E_{11}, \frac{1}{2}E_{12}, 3E_{13}, \frac{1}{4}E_{14},... and 2E_{21}, \frac{1}{3}E_{31}, 4E_{41}, etc, then neither D nor D^{−1} can be chosen to be bounded so that D^{−1}𝔖D in [0, 1].

Finally, we should mention that there seems to be no reasonable extension of Theorem 12 to the infinite-dimensional case because the estimate there essentially depends on the dimension.

4. The continuous case

Let K be a compact Hausdorff space, and μ be a Borel measure on K. Then K × K equipped with the product topology is also a compact Hausdorff space. As usual, C(K)

INDECOMPOSABLE SEMIGROUPS 11

and C(K × K) will stand for the spaces of all real-valued continuous functions on K and K × K, respectively. It is well known that these spaces are Banach lattices with respect to point-wise order. We equip C(K × K) with convolution defined via

(S ∗ T)(x, y) = ∫_{K} S(x, t)T (t, y) dμ

for S, T ∈ C(K × K).

Let us introduce some terminology. Let F be a subset of C(K × K). We say that F is a convolution semigroup in C(K × K) if it is closed under convolution. We say that F is equicontinuous if for every a, b ∈ K and every ε > 0 there exists a neighborhood V of (a, b) in K × K such that |S(x, y) − S(a, b)| < ε for every S ∈ F and every pair (x, y) ∈ V. We say that F is bounded at some (a, b) in K × K if the set {S(a, b) : S ∈ F} is bounded. We write ker F for the set of all pairs (x, y) such that S(x, y) = 0 for all S ∈ F. That is, ker F is the intersection of the kernels of all members of F. It follows that ker F is closed.

Theorem 23. Suppose that μ is positive on the non-empty open subsets of K. Let 𝔖 be an equicontinuous convolution semigroup of non-negative functions in C(K × K) such that

(i) ker 𝔖 contains no non-empty open sets, and (ii) there exists (a_{1}, a_{2}) ∈ K × K such that 𝔖 is bounded at (a_{1}, a_{2}).

Then 𝔖 is relatively norm compact in C(K × K).

Proof. Equicontinuity of 𝔖 implies that there exists a neighborhood U of (a_{1}, a_{2}) such that 𝔖 is uniformly bounded on W. Without loss of generality, W = W_{1} × W_{2}, where W_{1} and W_{2} are open neighborhoods of a_{1} and a_{2}, respectively.

We claim that {S(u_{1}, u_{2}) : S ∈ 𝔖} is uniformly bounded on K × K. First, show that it is bounded at every point of K × K. Suppose not. Then there exists a point (u_{1}, u_{2}) ∈ K × K and a sequence S_{n} ∈ 𝔖 with S_{n}(u_{1}, u_{2}) ⩾ n + 1. Since 𝔖 is equicontinuous, we can find a neighborhood U of (u_{1}, u_{2}) such that S_{n} ⩾ n on U. Again, without loss of generality, U = U_{1}×U_{2}, where U_{1} and U_{2} are open neighborhoods of u_{1} and u_{2}, respectively.

Since W_{1} × U_{1} is open, it is not contained in ker 𝔖, so that there exists a pair (b_{1}, v_{1}) ∈ W_{1} × U_{1} and A ∈ 𝔖 such that A(b_{1}, v_{1}) > 0. Similarly, there exist b_{2} ∈ W_{2}, v_{2} ∈ U_{2}, and B ∈ 𝔖 such that B(v_{2}, b_{2}) > 0. Since A and B are continuous, we can find ε > 0 and open neighborhoods V_{1} of v_{1} and V_{2} of v_{2} such that V_{1} ⊆ U_{1}, V_{2} ⊆ U_{2},

12 H. GESSESSE, A. I. POPOV, H. RADJAVI, E. SPINU, A. TCACIUC, AND V. G. TROITSKY

A(b_{1}, ·) > ε on V_{1}, and B(·, b_{2}) > ε on V_{2}. Then

(A ∗ S_{n} ∗ B)(b_{1}, b_{2}) = ∫_{K×K} A(b_{1}, s)S_{n}(s, t)B(t, b_{2}) dμ ⊗ μ

⩾ ∫∫_{(s,t)∈V_{1}×V_{2}} A(b_{1}, s)S_{n}(s, t)B(t, b_{2}) dμ ⊗ μ

⩾ ε^{2}nμ(V_{1})μ(V_{2}) → +∞.

This contradicts the fact that 𝔖 is bounded at (b_{1}, b_{2}) because (b_{1}, b_{2}) ∈ W. Therefore, 𝔖 is bounded at every point of K × K.

For every point (u_{1}, u_{2}) ∈ K × K, put T (u_{1}, u_{2}) = sup{S(u_{1}, u_{2}) : S ∈ 𝔖}. By the preceding claim, T (u_{1}, u_{2}) is finite. Equicontinuity of 𝔖 implies that T is continuous. Since K × K is compact, there exists M > 0 such that T (u_{1}, u_{2}) ⩽ M for all (u_{1}, u_{2}) ∈ K × K. Hence S(u_{1}, u_{2}) ⩽ M for all S ∈ 𝔖 and all (u_{1}, u_{2}) ∈ K × K. The result now follows by Arzela-Ascoli’s Theorem. □

Clearly, condition (i) in the preceding theorem is analogous to indecomposability of 𝔖. Since ker 𝔖 is closed, (i) is equivalent to ker 𝔖 being nowhere dense. In particular, it is satisfied when ker 𝔖 has zero measure. On the other hand, viewing the elements of C(K × K) as kernels of integral operators on L_{p}(μ) for 1 ⩽ p < ∞ (under the assumption that μ is finite), we can consider the natural embedding of C(K × K) into the space L(L_{p}(μ)) of all bounded operators on L_{p}(μ). Moreover, the corresponding integral operators are Hilbert-Schmidt. Thus, C(K × K) embeds into the space of Hilbert-Schmidt integral operators on L_{2}(μ) equipped with the Hilbert-Schmidt norm. Since the two embeddings are clearly continuous, Theorem 23 guarantees that 𝔖 is relatively compact as a subset of L(L_{p}(μ)) and as a subset of the space of Hilbert-Schmidt integral operators.

The following example shows that the natural analogue of Corollary 10 or Theorems 17 or 19 fails in the case of convolution semigroups, where instead of D^{−1}SD we consider S(x, y)\frac{g(y)}{g(x)} for some g ∈ C[0, 1].

Example 24. A convolution semigroup 𝔖 of non-negative functions in C([0, 1]^{2}) such that S(x, x) ⩽ 1 for all S ∈ 𝔖, but there is no g ∈ C[0, 1] with inf g > 0 such that S(x, y)\frac{g(y)}{g(x)} ⩽ 1 for all S ∈ 𝔖 and all x, y ∈ [0, 1]^{2}.

Let S(x, y) = \frac{3}{2}(x − y)^{2}, and let 𝔖 consist of the convolution powers of S. Observe that if 0 ⩽ z ⩽ \frac{1}{2} then S(x, z) = S(z, x) ⩽ S(z, 1) for every x ∈ [0, 1], and if \frac{1}{2} ⩽ z ⩽ 1 then S(x, z) = S(z, x) ⩽ S(z, 0) for every x ∈ [0, 1]. It follows that for every (x, y) ∈ [0, 1]^{2} we have

(S ∗ S)(x, y) ⩽ ∫0^{\frac{1}{2}} S(z, 1)^{2} dz + ∫ 1_{\frac{1}{2}} S(z, 0)^{2} dz < 1.

Put E(x, y) = 1 for every (x, y) ∈ [0, 1]^{2}. Then S ∗ S ⩽ E. Also,

(S ∗ E)(x, y) = ∫_{0}^{1} \frac{3}{2}(x − t)^{2} dt = \frac{1}{2}(3x^{2} − 3x + 1) ⩽ \frac{1}{2}

for all (x, y) ∈ [0, 1]. Hence, S ∗ E ⩽ \frac{1}{2}E. Combining this with S ∗ S ⩽ E, we get that S^{n} ⩽ \frac{1}{2^{n−2}} E for all n ⩾ 2, where S^{n} is the n-th convolution power of S. In particular, S^{n}(x, x) ⩽ 1 for all x ∈ [0, 1] and all n.

On the other hand, suppose that g ∈ C[0, 1] with inf g > 0. Let α = S(1, 0)\frac{g(0)}{g(1)} and

β = S(0, 1)\frac{g(1)}{g(0)}. Then αβ = S(1, 0)S(0, 1) = \frac{9}{4} > 1. It follows that either α > 1 or β > 1.

Hence, 𝔖 is indeed as we claimed above. Moreover, 0 ⩽ S^{n} ⩽ \frac{1}{2^{n−2}} E implies that S^{n} → 0 in the uniform topology, hence 𝔖 ∪ {0} is a compact semigroup which still has (or, rather, fails) the desired property.

References

[AA02] Y. A. Abramovich and C. D. Aliprantis, An invitation to operator theory, Graduate Studies in Mathematics, vol. 50, American Mathematical Society, Providence, RI, 2002.

[LT77] J. Lindenstrauss and L. Tzafriri, Classical Banach spaces. I, Springer-Verlag, Berlin, 1977, Sequence spaces, Ergebnisse der Mathematik und ihrer Grenzgebiete, Vol. 92.

[LMR] L. Livshits, G. MacDonald, and H. Radjavi, Semigroups of zero-one matrices, preprint.

[Min88] H. Minc, Nonnegative matrices, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., New York, 1988, A Wiley-Interscience Publication.

[Ok98] J. Okninski, Semigroups of Matrices, World Scientific, Singapore, 1998.

[RR08] H. Radjavi and P. Rosenthal, Limitations on the size of semigroups of matrices, Semigroup Forum 76 (2008), 25–31.

(H. Gessesse, A. I. Popov, E. Spinu, and V. G. Troitsky) Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, AB, T6G 2G1. Canada

  E-mail address: hgessesse@math.ualberta.ca, apopov@math.ualberta.ca, spinu@ualberta.ca,
vtroitsky@math.ualberta.ca

(H. Radjavi) Department of Pure Mathematics, University of Waterloo, Waterloo, ON, N2L 3G1. Canada.

  E-mail address: hradjavi@math.uwaterloo.ca

(A. Tcaciuc) Mathematics and Statistics Department, Grant MacEwan College, Edmonton, Alberta, Canada T5J P2P, Canada

  E-mail address: tcaciuc@math.ualberta.ca