Matrix inequalities with applications to the theory of iterated kernels

William Banks  Asma Harcharras  Stefan Neuwirth  Éric Ricard

Abstract

For an m × n matrix A with nonnegative real entries, Atkinson, Moran and Watterson proved the inequality s(A)^{3} ⩽ mns(AA^{t}A), where A^{t} is the transpose of A, and s(·) is the sum of the entries. We extend this result to finite products of the form AA^{t}AA^{t} …A or AA^{t}AA^{t} …A^{t} and give some applications to the theory of iterated kernels.

1 Introduction

For any matrix A, let s(A) denote the sum of its entries. For any integer k ≥ 1, we define

A^{(2k)} = (AA^{t})^{k}, A^{(2k+1)} = (AA^{t})^{k}A,

where A^{t} denotes the transpose of A. In Section 2, we prove the following sharp inequalities:

Theorem 1.1. Let A be an m×n matrix with nonnegative real entries. Then for every integer k ⩾ 1, the following matrix inequalities hold:

s(A)^{2k} ⩽ m^{k−1} n^{k}s(A^{(2k)} ), s(A)^{2k+1} ⩽ m^{k}n^{k}s(A^{(2k+1)} ).

For the special case of symmetric matrices, this theorem was proved in 1959 by Mulholland and Smith [4], thus settling an earlier conjecture of Mandel and Hughes [3] that had been based on the study of certain genetical models. For arbitrary matrices (with nonnegative entries), Theorem 1.1 also generalises the matrix inequality

s(A)^{3} ⩽ mns(AA^{t}A),

which was first proved in 1960 by Atkinson, Moran and Watterson [1] using methods of perturbation theory.

Theorem 1.1 has a graph theoretic interpretation when applied to matrices with entries in {0, 1}. Let G be a graph with red vertices labeled 1, …, m and blue vertices labeled 1, …, n such that every edge connects only vertices of distinct colours: G is a bipartite graph. Its reduced incidence matrix is an m × n matrix A such that a_{i,j} = 1 if red vertex i is adjacent to blue vertex j, and a_{i,j} = 0 otherwise. Then s(A) is the size of G, while s(A^{(ℓ)}) is the number of walks on G of length ℓ starting from a red vertex, i.e., the number of sequences (v_{0}, …, v_{ℓ}) such that v_{0} is a red vertex and every pair {v_{i}, v_{i+1} } is an edge in G. Theorem 1.1 then yields the optimal lower bound of the number of walks in terms of the size of G. We do not know of a corresponding lower bound for the number of trails (walks with no edge repeated) or paths (walks with no vertex repeated).

Recall that an m × n matrix A is said to be bistochastic if every row sum of A is equal to s(A)/m, and every column sum of A is equal to s(A)/n. In Section 3 we prove the following asymptotic form of Theorem 1.1:

Theorem 1.2. Let A be an m × n matrix with nonnegative real entries. If A is bistochastic, then for all k ⩾ 1,

s(A)^{2k} = m^{k−1} n^{k}s(A^{(2k)} ), s(A)^{2k+1} = m^{k}n^{k}s(A^{(2k+1)} ).

If A is not bistochastic, then there exist constants c > 0 and γ > 1 (depending only on A) such that for all ℓ ⩾ 1,

s(A)^{ℓ} < cγ^{−ℓ} (mn)^{ℓ/2}s(A^{(ℓ)}).

As we show in Sections 2 and 3, both of the above theorems, though stated for arbitrary rectangular matrices with nonnegative entries, follow from the special case of square matrices.

Theorem 1.2 has an immediate application. Atkinson, Moran and Watterson [1] conjectured that for a nonnegative symmetric kernel function K(x, y) that is integrable (in a suitable sense) over the square 0 ⩽ x, y ⩽ a, the inequality

∫_{0}^{a} ∫_{0}^{a} K_{ℓ}(x, y) dx dy ⩾ \frac{1}{a^{ℓ−1}} ( ∫_{0}^{a} ∫_{0}^{a} K(x, y) dx dy) ^{ℓ}  (1)

holds for all ℓ ⩾ 1. Here K_{ℓ}(x, y) denotes the ℓ-th order iterate of K(x, y), which is defined recursively by

K_{1}(x, y) = K(x, y), K_{ℓ}(x, y) = ∫_{0}^{a} K_{ℓ−1} (x, t)K(t, y) dt.

Beesack [2] showed that the Atkinson-Moran-Watterson conjecture follows from the matrix identities of Mulholland and Smith described above. Using Beesack’s ideas together with Theorem 1.2, we prove in Section 4 the following asymptotic form of the Atkinson-Moran-Watterson inequality (1):

Theorem 1.3. Let K(x, y) be a nonnegative symmetric kernel function that is integrable over the

square 0 ⩽ x, y ⩽ a, and consider the function f(x) = ∫_{0}^{a} K(x, y) dy defined on the interval 0 ⩽ x ⩽ a.

If f(x) is constant almost everywhere, then for all ℓ ⩾ 1

∫_{0}^{a} ∫_{0}^{a} K_{ℓ}(x, y) dx dy = \frac{1}{a^{ℓ−1}} ( ∫_{0}^{a} ∫_{0}^{a} K(x, y) dx dy) ^{ℓ}.

If not, there exist constants c > 0 and γ > 1 (depending only on K) such that for all ℓ ⩾ 1

∫_{0}^{a} ∫_{0}^{a} K_{ℓ}(x, y) dx dy > \frac{cγ^{ℓ}}{a^{ℓ−1}} ( ∫_{0}^{a} ∫_{0}^{a} K(x, y) dx dy) ^{ℓ}.

Remark 1.4. Using an approximation argument as in the proof of Theorem 1.3, Theorem 1.1 can be also applied to establish an analogue to inequalities (1) and Theorem 1.3 in the case of nonsymmetric kernel functions. Let K(x, y) be any nonnegative kernel function that is integrable on the rectangle 0 ⩽ x ⩽ a, 0 ⩽ y ⩽ b and let K_{ℓ} be the ℓ-th order iterate of K defined by K_{1}(x, y) = K(x, y) and for each integer k ≥ 1,

K_{2k}(x, x′) = ∫_{0}^{b} K_{2k−1} (x, y)K(x′, y) dy,

K_{2k+1} (x, y) = ∫_{0}^{a} K_{2k}(x, x′)K(x′, y) dx′.

In this case, inequalities (1) become

∫_{0}^{a} ∫_{0}^{b} K_{2k+1} (x, y) dx dy ≥ \frac{1}{a^{k}b^{k}}( ∫_{0}^{a} ∫_{0}^{b} K(x, y) dx dy) ^{2k+1}

∫_{0}^{a} ∫_{0}^{a} K_{2k}(x, x′) dx dx′ ≥ \frac{1}{a^{k−1} b^{k}}( ∫_{0}^{a} ∫_{0}^{b} K(x, y) dx dy) ^{2k}.

The analogue of Theorem 1.3 is then obvious.

2 Matrix inequality

Given a matrix A = (a_{i,j} ) and an integer ℓ ⩾ 0, we denote by a_{i,j}^{(ℓ)} the (i, j)-th entry of A^{(ℓ)}, so that A^{(ℓ)} = (a_{i,j}^{(ℓ)}). This notation will be used often in the sequel.

Lemma 2.1. Let B = (b_{i,j} ) be a d × d matrix with nonnegative real entries. For any two sequences {α_{i}} and {β_{i}} of nonnegative real numbers, the following inequality holds:

(I′_{2}) :  ∑_{i,j=1}^{d} α_{i}β_{i}b_{i,j} ⩽ d^{\frac{1}{2}} ( ∑_{i,j=1}^{d} α_{i}^{2}β_{j}^{2}b_{i,j}^{(2)}) ^{\frac{1}{2}} .

Proof. To prove the lemma, we apply the Cauchy-Schwarz inequality twice as follows:

∑_{i,j=1}^{d} α_{i}β_{i}b_{i,j} = ∑_{i,k=1}^{d} α_{i}β_{i}b_{i,k} ⩽ d^{\frac{1}{2}} ( ∑_{k=1}^{d} ( ∑_{i=1}^{d} α_{i}β_{i}b_{i,k} )^{2}) ^{\frac{1}{2}} .  (2)

∑_{i,j=1}^{d} α_{i}β_{i}b_{i,j} ≤ d^{\frac{1}{2}} ( ∑_{i,j,k=1}^{d} α_{i}α_{j} β_{i}β_{j} b_{i,k} b_{j,k} ) ^{\frac{1}{2}}

= d^{\frac{1}{2}} ( ∑_{i,j=1}^{d} α_{i}α_{j} β_{i}β_{j} b_{i,j}^{(2)}) ^{\frac{1}{2}}

= d^{\frac{1}{2}} ( ∑_{i,j=1}^{d} α_{i}β_{j} (b_{i,j}^{(2)})^{\frac{1}{2}} · α_{j} β_{i}(b_{j,i}^{(2)})^{\frac{1}{2}} ) ^{\frac{1}{2}}

⩽ d^{\frac{1}{2}} ( ∑_{i,j=1}^{d} α_{i}^{2}β_{j}^{2}b_{i,j}^{(2)}) ^{\frac{1}{2}} .

Here we have used the fact that B^{(2)} = BB^{t} is a symmetric matrix.

Theorem 2.2. Let B = (b_{i,j} ) be a square d × d matrix with nonnegative real entries, and let {α_{i}} be any sequence of nonnegative real numbers. Then for each integer ℓ ⩾ 1, we have

(I_{ℓ}) :  ∑_{i,j=1}^{d} α_{i}b_{i,j} ⩽ d^{\frac{ℓ−1}{ℓ}} ( ∑_{i,j=1}^{d} α_{i}^{ℓ}b_{i,j}^{(ℓ)}) ^{\frac{1}{ℓ}} .

Proof of Theorem 2.2. The case ℓ = 1 is trivial while the case ℓ = 2 is a consequence of the lemma above. We prove the general case by induction. Suppose that p ⩾ 2, and the inequalities (I_{1}), (I_{2}), …, (I_{p}) hold for all square matrices with nonnegative real entries. If p = 2k − 1 is an odd integer, then the inequality (I_{p+1} ) follows immediately from (I_{2}) and (I_{k}). Indeed, since B^{(2k)} = B^{(2)(k)} , we have

∑_{i,j=1}^{d} α_{i}b_{i,j} ⩽ d^{\frac{1}{2}} ( ∑_{i,j=1}^{d} α_{i}^{2}b_{i,j}^{(2)}) ^{\frac{1}{2}} ⩽ d^{\frac{1}{2}} ( d^{\frac{k−1}{k}} ( ∑_{i,j=1}^{d} α_{i}^{2k}b_{i,j}^{(2)(k)} ) ^{\frac{1}{k}} ) ^{\frac{1}{2}} .  (3)

Thus

∑_{i,j=1}^{d} α_{i}b_{i,j} ⩽ d^{\frac{2k−1}{2k}} ( ∑_{i,j=1}^{d} α_{i}^{2k}b_{i,j}^{(2k)} ) ^{\frac{1}{2k}} .

If p = 2k is an even integer, then the inequality (I_{p+1} ) follows from Hölder’s inequality, and the inequalities (I_{k}) and (I′_{2}). Indeed, by Hölder’s inequality, we have

∑_{i,j=1}^{d} α_{i}b_{i,j} ⩽ d^{\frac{1}{2k+1}} ( ∑_{i=1}^{d} αi^{\frac{2k+1}{2k}} ( ∑_{j=1}^{d} b_{i,j} ) ^{\frac{2k+1}{2k}} ) ^{\frac{2k}{2k+1}} .  (4)

Let I denote the term between parentheses, and set β_{i} = ∑_{j=1}^{d} b_{i,j} for each i. Then

I = ∑_{i=1}^{d} αi^{\frac{2k+1}{2k}} ( ∑_{j=1}^{d} b_{i,j} ) ^{\frac{2k+1}{2k}} = ∑_{i,j=1}^{d} αi^{\frac{2k+1}{2k}} βi^{\frac{1}{2k}} b_{i,j} .

Applying (I_{k}), it follows that

I ⩽ d^{\frac{k−1}{k}} ( ∑_{i,j=1}^{d} αi^{\frac{2k+1}{2}} βi^{\frac{1}{2}} b_{i,j}^{(k)}) ^{\frac{1}{k}} .

Applying the lemma to the sequences \{αi^{\frac{2k+1}{2}} \} and \{βi^{\frac{1}{2}} \}, and using the fact that B^{(k)(2)} = B^{(2k)} , we see that

I ⩽ d^{\frac{k−1}{k}} ( d^{\frac{1}{2}} ( ∑_{i,j=1}^{d} α_{i}^{2k+1} β_{j} b_{i,j}^{(k)(2)} ) ^{\frac{1}{2}} ) ^{\frac{1}{k}} = d^{\frac{2k−1}{2k}} ( ∑_{i,j=1}^{d} α_{i}^{2k+1} β_{j} b_{i,j}^{(2k)} ) ^{\frac{1}{2k}} .

Putting everything together, we have therefore shown that

∑_{i,j=1}^{d} α_{i}b_{i,j} ⩽ d^{\frac{2k}{2k+1}} ( ∑_{i,j=1}^{d} α_{i}^{2k+1} β_{j} b_{i,j}^{(2k)} ) ^{\frac{1}{2k+1}} .

Finally, note that

∑_{j=1}^{d} β_{j} b_{i,j}^{(2k)} = ∑_{ℓ=1}^{d} b_{i,ℓ}^{(2k)} β_{ℓ} = ∑_{j,ℓ=1}^{d} b_{i,ℓ}^{(2k)} b_{ℓ,j} = ∑_{j=1}^{d} b_{i,j}^{(2k+1)}

since B^{(2k+1)} = B^{(2k)} B. Consequently,

∑_{i,j=1}^{d} α_{i}b_{i,j} ⩽ d^{\frac{2k}{2k+1}} ( ∑_{i,j=1}^{d} α_{i}^{2k+1} b_{i,j}^{(2k+1)} ) ^{\frac{1}{2k+1}}  (5)

and (I_{p+1} ) holds for the case p = 2k. Theorem 2.2 now follows by induction.

Proof of Theorem 1.1. For the case of square matrices, Theorem 1.1 follows immediately from Theorem 2.2. Indeed, taking α_{i} = 1 for each i, the inequality (I_{ℓ}) yields the corresponding inequality in Theorem 1.1.

Now, let A be an m × n matrix with nonnegative real entries, put d = mn, and let B be the d × d matrix with nonnegative real entries defined as the tensor product B = A ⊗ J_{n,m} , where J_{n,m} is the n × m matrix with every entry equal to 1. For any integers ℓ, k ⩾ 0, the relations

B^{(ℓ)} = A^{(ℓ)} ⊗ J_{n,m}^{(ℓ)} , s(B^{(ℓ)}) = s(A^{(ℓ)})s(J_{n,m}^{(ℓ)} ),
s(J_{n,m}^{(2k)} ) = m^{k}n^{k+1} , s(J_{n,m}^{(2k+1)} ) = m^{k+1} n^{k+1} .

are easily checked. In particular, s(B) = mns(A). Applying Theorem 1.1 to the matrix B and using these identities, the inequalities of Theorem 1.1 follow for the matrix A.

3 Asymptotic matrix inequality

As will be shown below, Theorem 1.2 is a consequence of the following more precise theorem for square matrices:

Theorem 3.1. Let B be a square d × d matrix with nonnegative real entries and s(B) ≠ 0. Let λ be the largest eigenvalue of B^{(2)} = BB^{t}, and put γ = λd^{2}/s(B)^{2}. Then γ ⩾ 1, and there exists a constant c > 0 (depending only on B) such that for all integers ℓ ⩾ 0,

s(B)^{ℓ} < cγ^{− \frac{ℓ}{2}} d^{ℓ−1} s(B^{(ℓ)}).  (6)

Moreover, the following assertions are equivalent:

(a) γ = 1,

(b) s(B)^{ℓ} = d^{ℓ−1} s(B^{(ℓ)}) for every integer ℓ ⩾ 0,

(c) s(B)^{ℓ} = d^{ℓ−1} s(B^{(ℓ)}) for some integer ℓ ⩾ 3,

(d) B is bistochastic.

Proof. We express B^{(2)} = BB^{t} in the form B^{(2)} = U^{t}DU, where U = (u_{i,j} ) is an orthogonal matrix, and D is a diagonal matrix diag(λ_{1}, …, λ_{d}) with λ_{1} ⩾ … ⩾ λ_{d} ⩾ 0. Here λ = λ_{1}. For each ν = 1, …, d, let E_{ν} be the projection matrix whose (ν, ν)-th entry is 1, and all other entries are equal to 0. Put A_{ν} = U^{t}E_{ν}U for each ν. Then for all integers k ⩾ 0,

B^{(2k)} = ∑_{ν=1}^{d} λ_{ν}^{k}A_{ν}, B^{(2k+1)} = ∑_{ν=1}^{d} λ_{ν}^{k}A_{ν}B.

By a straightforward calculation, we see that for each ν

s(A_{ν}) = ( ∑_{i=1}^{d} u_{ν,i} )^{2},  s(A_{ν}B) = ( ∑_{i=1}^{d} u_{ν,i} ) ( ∑_{j,k=1}^{d} u_{ν,k} b_{k,j} ) .  (7)

In particular, s(A_{ν}) ⩾ 0. By Theorem 2.2, it follows that

\frac{s(B)^{2}}{d} ⩽ s(B^{(2)}) = ∑_{ν=1}^{d} λ_{ν}s(A_{ν}) ⩽ λ ∑_{ν=1}^{d} s(A_{ν}) = λd.  (8)

Therefore, γ = \frac{λd^{2}}{s(B)^{2}} ⩾ 1. Now, from the definition of γ, we have

\frac{γ^{\frac{ℓ}{2}} s(B)^{ℓ}}{d^{ℓ−1} s(B^{(ℓ)})} = d\frac{λ^{\frac{ℓ}{2}}}{s(B^{(ℓ)})} ·

Then, in order to show inequality (6), we will show that the λ^{\frac{ℓ}{2}} /s(B^{(ℓ)}) are bounded above by a constant that is independent of ℓ. Indeed, let C_{ℓ} = B^{(ℓ)}/s(B^{(ℓ)}) for every ℓ ⩾ 0. Since each C_{ℓ} has nonnegative real entries, and s(C_{ℓ}) = 1, the entries of C_{ℓ} all lie in the closed interval [0, 1]. Thus the entries of the matrices UC_{2k}U^{t} and UC_{2k+1} B^{t}U^{t} are bounded by a constant that depends only on B. Noting that for each nonnegative integer k, we have

UC_{2k}U^{t} = \frac{D^{k}}{s(B^{(2k)} )} , UC_{2k+1} B^{t}U^{t} = \frac{D^{k+1}}{s(B^{(2k+1)} )} ,

and on examining the (1, 1)th entry for each of these matrices, we see that λ^{k} /s(B^{(2k)} ) and λ^{k+1} / s(B^{(2k+1)} ) are both bounded above by a constant that is independent of k. Consequently, inequality (6) holds.

(a)⇒ (b): If γ = 1, then λd = s(B)^{2}/d, hence from (8) we see that s(A_{ν}) = 0 whenever λ_{ν} ≠ λ. By (7), we also have that s(A_{ν}B) = 0 whenever λ_{ν} ≠ λ. Thus

s(B^{(2k)} ) = ∑_{ν=1}^{d} λ_{ν}^{k}s(A_{ν}) = λ^{k} ∑_{ν:λ_{ν} =λ} s(A_{ν})

= λ^{k} ∑_{ν=1}^{d} s(A_{ν}) = λ^{k}d = \frac{s(B)^{2k}}{d^{2k−1}} ,

s(B^{(2k+1)} ) = ∑_{ν=1}^{d} λ_{ν}^{k}s(A_{ν}B) = λ^{k} ∑_{ν:λ_{ν} =λ} s(A_{ν}B)

= λ^{k} ∑_{ν=1}^{d} s(A_{ν}B) = λ^{k}s(B) = \frac{s(B)^{2k+1}}{d^{2k}} ·

(b)⇒ (a): If (b) holds, then inequality (6) implies 1 < cγ^{− \frac{ℓ}{2}} for some γ ≥ 1 and all integers ℓ ≥ 0. This forces γ = 1.

(b)⇒ (c): Trivial.

(c)⇒ (d): Suppose that ℓ = 2k + 1 ⩾ 3 is an odd integer such that s(B)^{ℓ} = d^{ℓ−1} s(B^{(ℓ)}). Taking every α_{i} = 1 in the proof of Theorem 2.2, our hypothesis means that equality holds in (5), hence (4) must also hold with equality:

∑_{i,j=1}^{d} b_{i,j} = d^{\frac{1}{2k+1}} ( ∑_{i=1}^{d} ( ∑_{j=1}^{d} b_{i,j} ) ^{\frac{2k+1}{2k}} ) ^{\frac{2k}{2k+1}} .

By Hölder’s inequality, this is only possible if all of the row sums of B are equal. Since ℓ is odd and s is transpose-invariant, we also have

s(B^{t})^{ℓ} = d^{ℓ−1} s((B^{(ℓ)})^{t}) = d^{ℓ−1} s((B^{t})^{(ℓ)}).

Thus all of the row sums of B^{t} are equal as well, and B is bistochastic.

Now suppose that ℓ = 2k ⩾ 4 is an even integer such that s(B)^{ℓ} = d^{ℓ−1} s(B^{(ℓ)}). By taking every α_{i} = 1 in (3), we see that s(B)^{2} = ds(B^{(2)}). Then, taking every α_{i} = β_{i} = 1 in the proof of the lemma, we see that equality holds in (2) which is only possible if all of the column sums of B are equal. Therefore s(BA) = βs(A) for every d × d matrix A, where β = s(B)/d is the sum of each column of B. In particular,

\begin{aligned}s(B)^{ℓ} & = d^{ℓ−1} s(B^{(ℓ)}) = d^{ℓ−1} βs((B^{t})^{(ℓ−1)} ) \\ & = d^{ℓ−1} βs((B^{(ℓ−1)} )^{t}) = d^{ℓ−1} βs(B^{(ℓ−1)} ), \end{aligned}

thus s(B)^{ℓ−1} = d^{ℓ−2} s(B^{(ℓ−1)} ). Since ℓ − 1 is odd, we can apply the previous result to conclude that B is bistochastic.

(d)⇒ (b): Suppose B is bistochastic, with every row or column sum equal to β = s(B)/d. For any d × d matrix A, one has s(AB) = βs(A) and s(AB^{t}) = βs(A). In particular, s(B^{(2k+1)} ) = βs(B^{(2k)} ) and s(B^{(2k+2)} ) = βs(B^{(2k+1)} ) for all k ⩾ 0. Consequently,

s(B^{(ℓ)}) = β^{ℓ−1} s(B) = \frac{s(B)^{ℓ}}{d^{ℓ−1}} , ℓ ⩾ 0.

This completes the proof.

Corollary 3.2. Let B be a square d × d matrix with nonnegative real entries and s(B) ≠ 0. Let β_{j} be the j-th column sum of B for each j, and put

δ = 1 + \frac{1}{2s(B)^{2}} ∑_{i,j=1}^{d} (β_{i} − β_{j})^{2}.

Then there exists a constant c > 0 (depending only on B) such that for all ℓ ⩾ 0, we have

s(B)^{ℓ} < cδ^{− \frac{ℓ}{2}} d^{ℓ−1} s(B^{(ℓ)}).

Proof. Note first that for any d × d matrix B, if β_{j} denotes the j-th column sum of B, then it is easily seen that

s(B^{(2)}) = \frac{s(B)^{2}}{d} + \frac{1}{2d} ∑_{i,j=1}^{d} (β_{i} − β_{j})^{2}.  (9)

Using the notation of Theorem 3.1 and applying the relations (8) and (9), we have

γ = \frac{λd^{2}}{s(B)^{2}} ⩾ \frac{ds(B^{(2)})}{s(B)^{2}} = 1 + \frac{1}{2s(B)^{2}} ∑_{i,j=1}^{d} (β_{i} − β_{j})^{2} = δ.

The corollary therefore follows from (6).

Proof of Theorem 1.2. Given an m × n matrix A with nonnegative real entries, we proceed as in the proof of Theorem 1.1: put d = mn, and let B = A⊗J_{n,m} . Note that A is bistochastic if and only if B is bistochastic. Applying the corollary above to B, Theorem 1.2 follows immediately for the matrix A. The details are left to the reader.

4 Asymptotic kernel inequality

Proof of Theorem 1.3. By changing variables if necessary, we can assume that a = 1. For simplicity, we will also assume that K(x, y) is continuous. Consider the function f(x) defined by

f(x) = ∫_{0}^{1} K(x, y) dy, x ∈ [0, 1].

If f(x) is a constant function, then since K(x, y) is symmetric, the equality

∫_{0}^{1} ∫_{0}^{1} K_{ℓ}(x, y) dx dy = ( ∫_{0}^{1} ∫_{0}^{1} K(x, y) dx dy) ^{ℓ}

for all ℓ ⩾ 1 follows from an easy inductive argument.

Now suppose that f(x) is not constant, and let m and M denote respectively the minimum and maximum value of f(x) on [0, 1]. Choose ε > 0 such that 4ε < M − m. For every integer d ⩾ 1, let 𝒰_{i}^{[d]} be the open interval

𝒰_{i}^{[d]} = ( \frac{i − 1}{d} , \frac{i}{d}) , 1 ⩽ i ⩽ d,

and let 𝒰_{i,j}^{[d]} be the rectangle 𝒰_{i}^{[d]} × 𝒰_{j}^{[d]} for 1 ⩽ i, j ⩽ d. Let K^{[d]}(x, y) be defined on [0, 1] × [0, 1] as follows:

min\{K(s, t) : (s, t) ∈ \overline{𝒰_{i,j}^{[d]}} \} if (x, y) ∈ 𝒰_{i,j}^{[d]} for some 1 ⩽ i, j ⩽ d
K(x, y)  otherwise.

Here \overline{𝒰_{i,j}^{[d]}} denotes the closure of 𝒰_{i,j}^{[d]}. Noting that K^{[d]}(x, y) is constant on each rectangle 𝒰_{i,j}^{[d]}, let B_{[d]} be the d × d matrix whose (i, j)-th entry is equal to K^{[d]}(𝒰_{i,j}^{[d]}). Let K_{ℓ}^{[d]}(x, y) denote the ℓ-th order iterate of K^{[d]}(x, y) for each ℓ ⩾ 1. Then

K_{ℓ}^{[d]}(x, y) = ∫_{0}^{1} K_{ℓ−1}^{[d]} (x, t)K^{[d]}(t, y) dt = ∑_{k=1}^{d} ∫_{𝒰_{k}^{[d]}} K_{ℓ−1}^{[d]} (x, t)K^{[d]}(t, y) dt.

It follows by induction that K_{ℓ}^{[d]}(x, y) is also constant on each rectangle 𝒰_{i,j}^{[d]}, and

K_{ℓ}^{[d]}(𝒰_{i,j}^{[d]}) = \frac{1}{d} ∑_{k=1}^{d} K_{ℓ−1}^{[d]} (𝒰_{i,k}^{[d]})K^{[d]}(𝒰_{k,j}^{[d]});

by induction, this is the (i, j)-th entry of the matrix \frac{1}{d^{ℓ−1}} B_{[d]}^{(ℓ)}. In other words,

( K_{ℓ}^{[d]}(𝒰_{i,j}^{[d]})) = \frac{1}{d^{ℓ−1}} B_{[d]}^{(ℓ)},  for all ℓ, d ⩾ 1.  (10)

Now since f(x) is continuous, we can choose d sufficiently large such that for some integers 1 ⩽ i_{m}, i_{M} ⩽ d, we have

f(x) < m + ε, for all x ∈ 𝒰_{i_{m}}^{[d]},
f(x) > M − ε, for all x ∈ 𝒰_{i_{M}}^{[d]}.

Taking d larger if necessary, we can further assume that

0 ⩽ K(x, y) − K^{[d]}(x, y) < ε

for all 0 ⩽ x, y ⩽ 1. Fixing this value of d, we define

γ = 1 + \frac{ε^{2}}{2d^{2}( ∫_{0}^{1} ∫_{0}^{1} K(x, y) dx dy)^{2}} .

Finally, since γ^{− \frac{1}{4}} < 1, we can choose e sufficiently large so that K^{[de]}(x, y) > γ^{− \frac{1}{4}} K(x, y) for all 0 ⩽ x, y ⩽ 1. For this value of e, we therefore have

∫_{0}^{1} ∫_{0}^{1} K^{[de]}(x, y) dx dy > γ^{− \frac{1}{4}} ∫_{0}^{1} ∫_{0}^{1} K(x, y) dx dy.

By the corollary to Theorem 3.1 applied to the matrix B_{[de]}, there exists a constant c > 0, which is independent of ℓ, such that

s(B_{[de]})^{ℓ} < cδ^{− \frac{ℓ}{2}} (de)^{ℓ−1} s(B_{[de]}^{(ℓ)})

for all integers ℓ ⩾ 0, where

δ = 1 + \frac{1}{2s(B_{[de]})^{2}} ∑_{i,j=1}^{de} (β_{[de],i} − β_{[de],j} )^{2}.

Here β_{[de],j} denotes the j-th column sum of B_{[de]} for each j. We now claim that δ > γ. Granting this fact for the moment, we apply (10) to K^{[de]}(x, y) and obtain:

∫_{0}^{1} ∫_{0}^{1} K_{ℓ}(x, y) dx dy ⩾ ∫_{0}^{1} ∫_{0}^{1} K_{ℓ}^{[de]}(x, y) dx dy = \frac{1}{(de)^{2}} ∑_{i,j=1}^{de} K_{ℓ}^{[de]}( 𝒰_{i,j}^{[de]})

= \frac{1}{(de)^{ℓ+1}} s(B_{[de]}^{(ℓ)}) > c^{−1} δ^{\frac{ℓ}{2}} (de)^{−2ℓ} s(B_{[de]})^{ℓ}

= c^{−1} δ^{\frac{ℓ}{2}} ( \frac{1}{(de)^{2}} ∑_{i,j=1}^{de} K^{[de]}( 𝒰_{i,j}^{[de]}) ) ^{ℓ}= c^{−1} δ^{\frac{ℓ}{2}} ( ∫_{0}^{1} ∫_{0}^{1} K^{[de]}(x, y) dx dy) ^{ℓ}

> c^{−1} δ^{\frac{ℓ}{2}} γ^{− \frac{ℓ}{4}} ( ∫_{0}^{1} ∫_{0}^{1} K(x, y) dx dy) ^{ℓ}> c^{−1} γ^{\frac{ℓ}{4}} ( ∫_{0}^{1} ∫_{0}^{1} K(x, y) dx dy) ^{ℓ}.

This completes the proof of the theorem modulo our claim that δ > γ. To see this, let 𝒱 be any interval of the form 𝒰_{i}^{[de]} such that 𝒱 ⊂ 𝒰_{i_{m}}^{[d]}. Note that there are e such intervals. Since B^{[de]} is a symmetric matrix, the column sum β_{[de],𝒱} of B_{[de]} corresponding to the interval 𝒱 is equal to the “𝒱 -th” row sum, which can be bounded as follows:

β_{[de],𝒱} = ∑_{j=1}^{de} K^{[de]}(𝒱 , 𝒰_{j}^{[de]}) = (de)^{2} ∫_{𝒱} ∫_{0}^{1} K^{[de]}(x, y) dy dx

⩽ (de)^{2} ∫_{𝒱} ∫_{0}^{1} K(x, y) dy dx = (de)^{2} ∫_{𝒱} f(x) dx < de(m + ε).

Similarly, let 𝒲 be any interval of the form 𝒰_{i}^{[de]} such that 𝒲 ⊂ 𝒰_{i_{M}}^{[d]}. Again, there are e such intervals, and by a similar calculation, the column sum β_{[de],𝒲} satisfies the bound

β_{[de],𝒲} = ∑_{j=1}^{de} K^{[de]}(𝒲 , 𝒰_{j}^{[de]}) > de(M − 2ε).

Thus

∑_{i,j=1}^{de} (β_{[de],i} − β_{[de],j} )^{2} ⩾ ∑_{𝒱 ,𝒲} (β_{[de],𝒲} − β_{[de],𝒱} )^{2} > d^{2}e^{4}(M − m − 3ε)^{2} > d^{2}e^{4}ε^{2}.

On the other hand, we have

s(B_{[de]}) = (de)^{2} ∫_{0}^{1} ∫_{0}^{1} K^{[de]}(x, y) dx dy ⩽ (de)^{2} ∫_{0}^{1} ∫_{0}^{1} K(x, y) dx dy,

and the claim follows.

Bibliography

[1] F. V. Atkinson, G. A. Watterson, and P. A. P. Moran. A matrix inequality. Quart. J. Math. Oxford Ser. (2), 11:137–140, 1960. (pp. 1 and 2).

[2] Paul R. Beesack. Inequalities involving iterated kernels and convolutions. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., 274–301:11–16, 1969. (p. 2).

[3] S. P. H. Mandel and I. M. Hughes. Change in mean viability at a multi-allelic locus in a population under random mating. Nature, 182:63–64, 1958. (p. 1).

[4] H. P. Mulholland and C. A. B. Smith. An inequality arising in genetical theory. Amer. Math. Monthly, 66:673–683, 1959. (p. 1).

Keywords. Matrix inequality, iterated kernel.

2000 Mathematics Subject Classification. 15A45.