Estimates for the condition numbers of large semi-definite Toeplitz matrices

A. Böttcher^{1} and S.M. Grudsky^{2}

This paper is devoted to asymptotic estimates for the condition numbers

κ(T_{n}(a)) = ∥T_{n}(a)∥ ∥T_{n}^{−1}(a)∥

of large n × n Toeplitz matrices T_{n}(a) in the case where a ∈ L^{∞} and Re a ≥ 0. We describe several classes of symbols a for which κ(T_{n}(a)) increases like (log n)^{α}, n^{α}, or even e^{αn}. The consequences of the results for singular values, eigenvalues, and the finite section method are discussed. We also consider Wiener-Hopf integral operators and multidimensional Toeplitz operators.

1. Introduction.

A bounded operator A on a Hilbert space H is called positive semi-definite if the real part of (Af, f) is nonnegative for every f ∈ H, i.e., if Re (Af, f) ≥ 0 for all f ∈ H, and it is said to be positive definite if there is an ε > 0 such that Re (Af, f) ≥ ε(f, f) for all f ∈ H.

We here consider the case where A is given by a Toeplitz matrix on H = l^{2}. Let T be the complex unit circle and denote by L^{∞} := L^{∞}(T) the essentially bounded functions on T. For a ∈ L^{∞}, let {a_{n}}_{n∈Z} stand for the sequence of the Fourier coefficients,

a_{n} := \frac{1}{2π} ∫_{−π}^{π} a(e^{iθ})e^{−inθ}dθ,

and define the finite Toeplitz matrices T_{n}(a) (n ∈ N := {1, 2, 3, …}) and the infinite Toeplitz matrix T (a) by

T_{n}(a) := (a_{j−k})_{j,k=0}^{n−1}, T (a) := (a_{j−k})_{j,k=0}^{∞}.

We tacitly identify the matrices T_{n}(a) and T (a) with the operators they induce on C^{n} = l^{2}({0, 1, …, n − 1}) and l^{2} := l^{2}({0, 1, 2, …}). The boundedness of T (a) follows from the boundedness of a. The function a is usually referred to as the symbol of the matrices/operators T_{n}(a) and T (a).

1Research supported by the Alfried Krupp Förderpreis für junge Hochschullehrer of the Krupp Foundation

2Research supported by the Russian fund of fundamental investigations (Grant No. 96-01-011-95A)

We equip the space L^{2} := L^{2}(T) with the scalar product and the norm

(f, g) := \frac{1}{2π} ∫_{−π}^{π} f(e^{iθ})\overline{g(e^{iθ})} dθ, ∥f∥_{2} := (f, f)^{1/2}.

Let P_{n} and H^{2} denote the functions in L^{2} whose sequence of Fourier coefficients is supported in {0, 1, …, n − 1} and {0, 1, 2, …}, respectively. Clearly, we can also think of T_{n}(a) and T (a) as acting on P_{n} and H^{2}, respectively. Denoting by P_{n} : L^{2} → P_{n} and P : L^{2} → H^{2} the orthogonal projections, we can write

T_{n}(a)f = P_{n}(af) (f ∈ P_{n}), T (a)f = P (af) (f ∈ H^{2}),

which implies that

(T_{n}(a)f, f) = ∫_{−π}^{π} a(e^{iθ})|f(e^{iθ})|^{2} dθ (f ∈ P_{n}),  (1)

(T (a)f, f) = ∫_{−π}^{π} a(e^{iθ})|f(e^{iθ})|^{2} dθ (f ∈ H^{2}).  (2)

From these two equalities we deduce that T_{n}(a) and T (a) are positive semi-definite if only Re a ≥ 0 a.e. and that these operators are positive definite whenever Re a ≥ ε a.e. for some ε > 0.

Given, a ∈ L^{∞}, let R(a) be the essential range of a, i.e., the spectrum of a as an element of the Banach algebra L^{∞}. We denote by conv R(a) the convex hull of R(a). Obviously, conv R(a) is always a compact and convex set. Put

dist (0, conv R(a)) = min {|λ| : λ ∈ conv R(a)}.

Let ∂conv R(a) be the boundary of conv R(a). It is readily seen that

dist (0, conv R(a)) > 0 ⟺ ∃γ ∈ T ∃ε > 0 : Re (γa) ≥ ε a.e.,  (3)
0 ∈ ∂conv R(a) or dist (0, conv R(a)) ≥ 0 ⟺ ∃γ ∈ T : Re (γa) ≥ 0 a.e.. (4)

The following simple fact is well known.

Proposition 1.1. Suppose a ∈ L^{∞} does not vanish identically and conv R(a) is not a line segment containing the origin in its interior. If dist (0, conv R(a)) ≥ 0 or 0 ∈ ∂conv R(a), then T_{n}(a) is invertible for every n ≥ 1.

Proof. Assume T_{n}(a) is not invertible. Then there is a nonzero f ∈ P_{n} such that T_{n}(a)f = 0, and (1) gives ∫ a|f|^{2} = 0. By virtue of (4) there exists a γ ∈ T such that Re (γa) ≥ 0 a.e. Hence Re (γa)|f|^{2} = 0 a.e., and as f vanishes almost nowhere, we deduce that Re (γa) = 0 a.e. Consequently, conv R(γa) = i[m, M] with real numbers m and M. Because ∫ Im (γa)|f|^{2} = 0 and f vanishes almost nowhere, it follows that m < 0 and M > 0, which means that R(a) is a line segment containing the origin in its interior. However, this case was excluded.

We remark that if conv R(a) is a line segment containing the origin in its interior then it may happen that T_{n}(a) is singular for infinitely many n. More about this will be said in the Appendix.

The condition number κ(A) of a bounded Hilbert space operator A is defined by

κ(A) := ∥A∥ ∥A^{−1}∥;

we put κ(A) = ∥A^{−1}∥ = ∞ in case A is not invertible. Proposition 1.1 describes a class of symbols a for which κ(T_{n}(a)) is finite for every n ≥ 1. The next result is also well known.

Proposition 1.2. If a ∈ L^{∞} and

lim sup_{n→∞} κ(T_{n}(a)) < ∞  (5)

then T (a) is invertible.

Proof. Suppose a does not vanish identically. The operators T_{n}(a)P_{n} converge strongly to T (a) on H^{2} as n → ∞. Therefore

0 < ∥a∥_{∞} = ∥T (a)∥ ≤ lim inf_{n→∞} ∥T_{n}(a)∥ ≤ lim sup_{n→∞} ∥T_{n}(a)∥ ≤ ∥a∥_{∞}

and hence ∥T_{n}(a)∥ → ∥a∥_{∞} > 0. Thus

lim sup_{n→∞} κ(T_{n}(a)) < ∞ ⟺ lim sup_{n→∞} ∥T_{n}^{−1}(a)∥ < ∞.

Now assume there is an M < ∞ such that ∥T_{n}^{−1}(a)∥ ≤ M for all n ≥ n_{0}. Then for every f ∈ H^{2},

∥P_{n}f∥ ≤ ∥T_{n}^{−1}(a)∥ ∥T_{n}(a)P_{n}f∥ ≤ M∥T_{n}(a)P_{n}f∥,

and passing to the strong limit, we get ∥f∥ ≤ M∥T (a)f∥. Considering adjoints we obtain analogously that ∥f∥ ≤ M∥T^{∗}(a)f∥. This proves that T (a) is invertible.

Thus, if the condition numbers κ(T_{n}(a)) remain bounded as n → ∞, then T (a) must necessarily be invertible. Criteria for T (a) to be invertible are known for large classes of symbols a (see, e.g., [5] and [4]). We only remark that T (a) is never invertible if a has a zero, i.e., if 0 ∈ R(a) (Hartman-Wintner theorem).

As the following result reveals, things are very simple for positive definite Toeplitz operators (and their rotations).

Proposition 1.3 (Brown-Halmos theorem). Let a ∈ L^{∞} and suppose

d := dist (0, conv R(a)) > 0.  (6)

Then T (a) is invertible and

κ(T (a)) ≤ \frac{∥a∥_{∞}}{d} (1 + \sqrt{1 − \frac{d^{2}}{∥a∥_{∞}^{2}}} ) < \frac{2∥a∥_{∞}}{d} ,  (7)

the operators T_{n}(a) are invertible and

κ(T_{n}(a)) ≤ \frac{∥a∥_{∞}}{d} (1 + \sqrt{1 − \frac{d^{2}}{∥a∥_{∞}^{2}}} ) < \frac{2∥a∥_{∞}}{d} for all n ≥ 1,  (8)

and if, in addition, a is piecewise continuous, then

lim_{n→∞} κ(T_{n}(a)) = κ(T (a)).  (9)

Proof outline. There is a γ ∈ T such that the set γ conv R(a) is contained in the set

{z ∈ C : Re z ≥ d, |z| ≤ ∥a∥_{∞}}.

Multiplying the latter set by λ := d/∥a∥_{∞}^{2} we obtain a set contained in the disk

\{z ∈ C : |z − 1| < r\}, r := \sqrt{1 − d^{2}/∥a∥_{∞}^{2}}.

Hence

∥λγT_{n}(a) − I∥ ≤ ∥λγT (a) − I∥ ≤ ∥λγa − 1∥_{∞} ≤ r < 1,

which implies the invertibility of T_{n}(a) and T (a) and shows that the norms of the inverses are at most

|λγ|\frac{1}{1 − r} = \frac{d}{∥a∥_{∞}^{2}} \frac{1 + r}{1 − r^{2}} = \frac{1}{d}(1 + \sqrt{1 − \frac{d^{2}}{∥a∥_{∞}^{2}}} ).

Since ∥T_{n}(a)∥ ≤ ∥T (a)∥ ≤ ∥a∥_{∞}, this gives (7) and (8).

Gohberg and Feldman (see [5, Theorem II.5.1]) showed that under the hypothesis of the proposition the condition numbers κ(T_{n}(a)) remain bounded. That the limit of κ(T_{n}(a)) exists and equals κ(T (a)) was proved in [15] and [2].

In fact, the converse of Proposition 1.2, i.e., the implication

T (a) is invertible ⟹ lim sup_{n→∞} κ(T_{n}(a)) < ∞  (10)

is true for large classes of symbols a essentially violating (6). For instance, (10) holds if

a ∈ (C + H^{∞}) ∪ (C + \overline{H^{∞}}) ∪ P QC

or if a is locally sectorial over QC (see [5] and [4] and the references therein). Moreover, the implication

T (a) is invertible ⟹ lim_{n→∞} κ(T_{n}(a)) = κ(T (a))

is also valid in many cases, for example if a ∈ P QC or if a is locally normal over QC (see [15] and [2]). Notice, however, that all these results pertain to the case where u = Re a (and thus, all the more, a itself) has no zeros.

Now suppose a ∈ L^{∞} \ {0} and all we know is that u(θ) := Re a(e^{iθ}) ≥ 0 for almost all θ. If a has a zero e^{iθ_{0}} (and therefore u has the zero θ_{0}), then T (a) is not invertible due to the Hartman-Wintner theorem, whence

lim sup_{n→∞} κ(T_{n}(a)) = ∞  (11)

by virtue of Proposition 1.2.

The case where u has a zero θ_{0} but a(e^{iθ_{0}}) ≠ 0 (see Section 3 for the meaning of this inequality) is less transparent. Proceeding as in the proof of Proposition 1.1 and using the F. and M. Riesz theorem which says that nonzero functions in H^{2} vanish almost nowhere, we see that T (a) has necessarily a trivial kernel (i.e., is injective) provided conv R(a) is not a line segment containing the origin in its interior. However, T (a) may be invertible or may not be invertible.

Example 1.4. Let a(e^{iθ}) = sin |θ| + i cos θ. In that case u(θ) = sin |θ| has two zeros in (−π, π] but |a(e^{iθ})| = 1 for all θ. Notice that as θ goes from −π to π, the image a(e^{iθ}) traverses the half-circle {z ∈ C : Re z ≥ 0, |z| = 1} first from −i to i and then back from i to −i. The operator T (a) is invertible (see, e.g., [5, Theorem I.7.1] or [4, Theorem 2.42]) and one can show that

lim_{n→∞} κ(T_{n}(a)) = κ(T (a))

(see [15] and [2]).

Example 1.5. The symbol a(e^{iθ}) = e^{iθ/2} = cos(θ/2) + i sin(θ/2) traverses the half-circle {z ∈ C : Re z ≥ 0, |z| = 1} from −i to i and then jumps back to −i as θ moves from −π to π (+0). Clearly, a itself has no zero, but u(θ) = cos(θ/2) vanishes at θ = −π = π (mod 2π). Because the line segment between the endpoints of the jumps of a passes through the origin (“hidden zero”), the operator T (a) is not invertible (see, e.g., [5, Theorem IV.2.1] or [4, Theorem 2.74]). Thus, κ(T_{n}(a)) cannot be bounded. We will return to this example in Section 4.

In this paper we establish estimates for the growth of κ(T_{n}(a)) provided a ∈ L^{∞}, Re a ≥ 0 a.e., and u = Re a or both u = Re a and a have zeros.

2. The idea behind the approach

The idea of our approach is extremely simple. The purpose of this section is to illustrate this idea by an example.

Consider the Toeplitz matrices

T_{n}(a) = ( \begin{matrix}2 & −1 & 0 & … & 0 \\ −1 & 2 & −1 & … & 0 \\ 0 & −1 & 2 & … & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & 0 & … & 2 \end{matrix} ) .

The symbol is

a(e^{iθ}) = −e^{iθ} + 2 − e^{−iθ} = 2 (1 − cos θ), θ ∈ (−π, π].

Thus, a ≥ 0 but a has a zero at θ = 0. Since

\frac{2}{π^{2}} θ^{2} ≤ 1 − cos θ = 2 sin^{2} \frac{θ}{2} ≤ \frac{1}{2} θ^{2},  (12)

the “order” of the zero is 2.

The operator T (a) is not invertible and hence (11) holds. The eigenvalues of T_{n}(a) can be calculated explicitly: they are

λ_{k}^{(n)} = 2 − 2 cos \frac{kπ}{n + 1} = 4 sin^{2} \frac{kπ}{2(n + 1)} (k = 1, …, n)

(see [8, Example 5.3]). Consequently,

∥T_{n}^{−1}(a)∥ = 1/λ_{1}^{(n)} ∼ \frac{1}{π^{2}} n^{2},

where x_{n} ∼ y_{n} means that x_{n}/y_{n} → 1 as n → ∞. Because ∥T_{n}(a)∥ → ∥T (a)∥ = ∥a∥_{∞} = 4, it follows that

κ(T_{n}(a)) ∼ \frac{4}{π^{2}} n^{2} as n → ∞.  (13)

Here now is how we proceed.

Upper estimate. We replace a by a + ig_{n} where

g_{n}(e^{iθ}) = cos nθ = (e^{inθ} + e^{−inθ})/2.

As the Fourier coefficients (g_{n})_{k} of g_{n} are zero for |k| ≤ n − 1, we have

T_{n}(a) = T_{n}(a + ig_{n}).

Clearly,

d_{n} := dist (0, conv R(a + ig_{n})) > 0.

Our aim is to estimate d_{n} from below.

The graph of a + ig_{n} in C = R^{2} is given by

(2 − 2 cos θ, cos nθ), θ ∈ (−π, π].  (14)

Put

ε_{n} := \frac{2}{3}(1 − cos \frac{π}{3n}) = \frac{4}{3} sin^{2} \frac{π}{6n}.  (15)

The graph of

(2 − 2 cos θ, \frac{1}{2} − \frac{1}{ε_{n}} (2 − 2 cos θ)), θ ∈ R  (16)

is the straight line y = 1/2 − (1/ε_{n})x. We show that the range of a + ig_{n} lies above this line. By virtue of (14) and (16) this is equivalent to showing that

\frac{1}{ε_{n}} (2 − 2 cos θ) + cos nθ > \frac{1}{2}  (17)

for θ ∈ (−π, π]. If |nθ| < π/3, then cos nθ > 1/2 and hence (17) is true. If |nθ| ≥ π/3, then cos θ ≤ cos(π/(3n)), whence, by (15),

\frac{1}{ε_{n}} (2 − 2 cos θ) + cos nθ ≥ \frac{1}{ε_{n}} (2 − 2 cos \frac{π}{3n}) − 1 = 3 − 1 > \frac{1}{2},

which gives (17) again.

Thus, d_{n} ≥ D_{n} where D_{n} is the distance of the origin to the sraight line y = 1/2 − (1/ε_{n})x. Obviously,

D_{n} = \frac{ε_{n}}{4} \frac{1}{\sqrt{1/4 + ε_{n}^{2}/4}},

and since ε_{n} → 0 as n → ∞, we have D_{n} > ε_{n}/4 for all sufficiently large n. Taking into account (8) we therefore obtain

κ(T_{n}(a)) = κ(T_{n}(a + ig_{n})) < \frac{2∥a∥_{∞}}{d_{n}} = \frac{8}{d_{n}} ≤ \frac{8}{D_{n}}
< \frac{32}{ε_{n}} = \frac{24}{sin^{2}(π/(6n))} < 216 n^{2}.  (18)

Lower estimate. We can construct an even trigonometric polynomial p_{m}^{3} of degree 3m such that

∥p_{m}^{3}∥_{∞} = (m + 1)^{3}, ∥p_{m}^{3}∥_{2}^{2} ≥ \frac{16}{9}m^{5}, |p_{m}^{3}(θ)| < \frac{8}{θ^{3}} for θ ≠ 0.

Starting with (12) we get

2π∥ap_{m}^{3}∥_{2}^{2} = ∫_{−π}^{π} |a(e^{iθ})|^{2}|p_{m}^{3}(θ)|^{2}dθ ≤ \frac{1}{2} ∫_{0}^{π} θ^{4}|p_{m}^{3}(θ)|^{2}dθ

< \frac{1}{2} \frac{1}{m^{4}} (m + 1)^{6} ∫_{0}^{1/m}dθ + 8^{2} ∫_{1/m}^{π} θ^{4}θ^{−6}dθ

≤ \frac{1}{2} \frac{1}{m^{4}} 2^{6}m^{6} \frac{1}{m} + 64m < 128m

≤ 128m\frac{9}{16m^{5}} ∥p_{m}^{3}∥_{2}^{2} = \frac{72}{m^{4}} ∥p_{m}^{3}∥_{2}^{2}.

Given n ≥ 9, write n = 3m + k with k ∈ {1, 2, 3}. We then have

∥T_{n}(a)p_{m}^{3}∥_{2}^{2} = ∥P_{n}(ap_{m}^{3})∥_{2}^{2} ≤ ∥ap_{m}^{3}∥_{2}^{2} ≤ \frac{36}{π} \frac{1}{m^{4}} ∥p_{m}^{3}∥_{2}^{2} ≤ \frac{36}{π}(\frac{4}{n})^{4}∥p_{m}^{3}∥_{2}^{2},

whence

∥T_{n}^{−1}(a)∥ ≥ \frac{\sqrt{π}}{6} (\frac{n}{4})^{2}

and thus, for sufficiently large n,

κ(T_{n}(a)) ≥ \begin{matrix}∥a∥ & ∞ \\ √ & \overline{π} \end{matrix} \frac{\sqrt{π}}{6} (\frac{n}{4})^{2} = \frac{1}{24}n^{2}.  (19)

Of course, (18) and (19) are more coarse than (13). However, as will be shown in what follows, the simple arguments we used to derive (18) and (19) work as nicely as above in many situations in which the eigenvalues are not available explicitly.

3. Upper estimates for the condition numbers

Let a ∈ L^{∞} and suppose Re a ≥ 0 a.e. Put

u(θ) := Re a(e^{iθ}), v(θ) := Im a(e^{iθ}), θ ∈ R.

Thus, u(θ) ≥ 0 for almost all θ ∈ R.

A number θ_{0} ∈ (−π, π] is said to be a zero of u if

ess inf {u(θ) : |θ − θ_{0}| < δ} = 0 for each δ > 0.

Assume u has only finitely many zeros θ_{1}, …, θ_{N} in (−π, π]. Then

ess inf u > 0 on (−π, π] \ ⋃_{j=1}^{N}(θ_{j} − δ, θ_{j} + δ)

for each δ > 0. Fix a δ > 0 so that the sets (θ_{j} − δ, θ_{j} + δ) are pairwise disjoint and define functions ω_{j} : N → (0, ∞) by

\frac{1}{ω_{j}(n)} := ess inf \{u(θ) : \frac{1}{n} < |θ − θ_{j}| < δ\}.  (20)

The function ω_{j} characterizes the “order” of the zero θ_{j}. Clearly, ω_{j}(n) → ∞ as n → ∞.

In what follows we write f(θ) ≃ g(θ) to indicate that there is a constant K ∈ [1, ∞) independent of θ such that

0 < (1/K)g(θ) ≤ f(θ) ≤ Kg(θ).

The notation f(n) ≃ g(n) means that there exists a constant K ∈ [1, ∞) such that

0 < (1/K)g(n) ≤ f(n) ≤ Kg(n) for all n ∈ N.

Example 3.1: powerlike zeros. If u(θ) ≃ |θ − θ_{j}|^{α} for |θ − θ_{j}| < δ with some α > 0, then ω_{j}(n) ≃ n^{α}. In case

u(θ) ≃ |θ − θ_{j}|^{α} for θ ∈ (θ_{j}, θ_{j} + δ), u(θ) ≃ |θ − θ_{j}|^{β} for θ ∈ (θ_{j} − δ, θ_{j}),

we have ω_{j}(n) ≃ n^{max{α,β}}.

Example 3.2: logarithmic zeros. Let α > 0 and

u(θ) ≃ 1/| log(|θ − θ_{j}|/π)|^{α} for 0 < |θ − θ_{j}| < δ.

In that case ω_{j}(n) ≃ (log n)^{α}.

Example 3.3: exponential zeros. Suppose γ > 0, α > 0 and

u(θ) ≃ e^{−γ/|θ−θ_{j}|^{α}} for 0 < |θ − θ_{j}| < δ.

Then ω_{j}(n) ≃ e^{γn^{α}}.

Here is the main result of this section.

Theorem 3.4. Let a ∈ L^{∞}, suppose Re a ≥ 0 a.e., and assume u := Re a has exactly N ≥ 1 zeros θ_{1}, …, θ_{N} on (−π, π]. Define ω_{j}(n) by (20), put ω(n) := max{ω_{1}(n), …, ω_{N}(n)}, and let v := Im a. Then

κ(T_{n}(a)) ≤ 12∥a∥_{∞}(∥v∥_{∞} + 1)ω(13^{N+1}n).

for all sufficiently large n.

In the case N = 1 we can modify the trick we used in Section 2 to establish (18). In the N > 1 case we need an additional tool. We don’t know whom the following result has to be attributed to. It was presented as a problem to the 1977 International Mathematics Olympiad by the Polish members of the Scientific Committee. The proof, given for the sake of completeness, is from [10, Problem 5.14].

Lemma 3.5. Let β_{1}, …, β_{N} be real numbers and μ > 0. Then there exists a number q ∈ N such that 1 ≤ q ≤ ([1/μ] + 1)^{N} and

qβ_{j} ∈ Z + (−μ, μ) for all j ∈ {1, …, N}.

Proof. For x ∈ R, denote by [x] and {x} the integral and fractional part of x, respectively. Thus, x = [x] + {x} with [x] ∈ Z and {x} ∈ [0, 1).

Put K = [1/μ] + 1 and divide the cube [0, 1)^{N} into K^{N} congruent cubes of the form

[i_{1}/K, (i_{1} + 1)/K) × … × [i_{N}/K, (i_{N} + 1)/K).  (21)

The K^{N} + 1 points

({lβ_{1}}, …, {lβ_{N}}), l = 0, 1, …, K^{N},

all belong to [0, 1)^{N} and therefore two of them must be located in the same cube (21). Consequently, there are l_{1}, l_{2} such that 0 ≤ l_{1} < l_{2} ≤ K^{N} and

−1/K ≤ l_{2}β_{j} − l_{1}β_{j} < 1/K for all j.

Put q := l_{2} − l_{1} and m_{j} := [l_{2}β_{j}] − [l_{1}β_{j}]. Then

|qβ_{j} − m_{j}| = |l_{2}β_{j} − [l_{2}β_{j}] − (l_{1}β_{j} − [l_{1}β_{j}])| = |{l_{2}β_{j}} − {l_{1}β_{j}}| < 1/K < μ.

Proof of Theorem 3.4. Using Lemma 3.5 with μ = 1/12 and β_{j} = nθ_{j}/(2π) we get an integer q_{n} such that

1 ≤ q_{n} ≤ 13^{N} and nq_{n}θ_{j} ∈ 2πZ + ( − \frac{π}{6} , \frac{π}{6} ).  (22)

We have

cos(nq_{n}θ) = cos(nq_{n}θ_{j}) cos (nq_{n}(θ − θ_{j})) − sin(nq_{n}θ_{j}) sin (nq_{n}(θ − θ_{j}))

and (22) shows that

cos(nq_{n}θ_{j}) > cos \frac{π}{6} = \frac{\sqrt{3}}{2}, sin(nq_{n}θ_{j}) < sin \frac{π}{6} = \frac{1}{2}.

If |nq_{n}(θ − θ_{j})| < π/6, then

cos (nq_{n}(θ − θ_{j})) > cos \frac{π}{6} = \frac{\sqrt{3}}{2}, sin (nq_{n}(θ − θ_{j})) < sin \frac{π}{6} = \frac{1}{2},

and hence we arrive at the conclusion that

cos(nq_{n}θ) > \frac{1}{2} whenever |θ − θ_{j}| < \frac{π}{6nq_{n}} .  (23)

Recall that v is the imaginary part of a. Put

\frac{1}{ε_{n,j}} := 3(∥v∥_{∞} + 1)ω_{j}(\frac{6nq_{n}}{π} ), M := 2(∥v∥_{∞} + 1)  (24)

and consider the function

b_{n}(e^{iθ}) := a(e^{iθ}) + iM cos(nq_{n}θ).  (25)

Since q_{n} ≥ 1, we have T_{n}(a) = T_{n}(b_{n}). Now let n be so large that π/(6nq_{n}) < δ. We claim that the essential range R(b_{n}|(θ_{j} − δ, θ_{j} + δ)) lies above the straight line given by y = 1 − (1/ε_{n,j})x. As

b_{n}(e^{iθ}) = u(θ) + i(v(θ) + M cos(nq_{n}θ)),

this is equivalent to saying that

v(θ) + M cos(nq_{n}θ) > 1 − \frac{1}{ε_{n,j}} u(θ)

for almost all θ ∈ (θ_{j} − δ, θ_{j} + δ). We prove that actually

\frac{1}{ε_{n,j}} u(θ) + M cos(nq_{n}θ) > 1 + ∥v∥_{∞}.  (26)

for almost all θ ∈ (θ_{j} − δ, θ_{j} + δ).

If |θ − θ_{j}| < π/(6nq_{n}) then (23), (24), and the nonnegativity of u(θ) give

\frac{1}{ε_{n,j}} u(θ) + M cos(nq_{n}θ) > \frac{M}{2} = ∥v∥_{∞} + 1.

So let π/(6nq_{n}) < |θ − θ_{j}| < δ. Then u(θ) ≥ 1/ω_{j}(6nq_{n}/π) by (20), whence, by (24),

\frac{1}{ε_{n,j}} u(θ) + M cos(nq_{n}θ) ≥ \frac{1}{ε_{n,j}ω_{j}(6nq_{n}/π)} − M

= 3(∥v∥_{∞} + 1) − 2(∥v∥_{∞} + 1) = ∥v∥_{∞} + 1.

This completes the proof of (26).

Thus, the essential range of the restriction of b_{n} to ⋃_{j}(θ_{j} − δ, θ_{j} + δ) lies above the line

y = 1 − \frac{1}{ε_{n}} x where ε_{n} := min_{j} ε_{n,j}  (27)

(here we took also into account that Re b_{n} ≥ 0). The number η given by

η := ess inf {u(θ) : θ ∈ (−π, π] \ ⋃_{j=1}^{N}(θ_{j} − δ, θ_{j} + δ)}

is positive. If θ ∈ (−π, π] \ ⋃_{j}(θ_{j} − δ, θ_{j} + δ), then b_{n}(e^{iθ}) is located on the right of the vertical line x = η. Since 1/ε_{n} → ∞ as n → ∞, it follows that R(b_{n}) is contained in the half-plane above the line (27) for all sufficiently large n.

The distance of the origin to the line (27) is D_{n} = ε_{n}/\sqrt{1 + ε_{n}^{2}} and thus D_{n} > ε_{n}/2 if only n is large enough. Hence, for all sufficiently large n we obtain from Proposition 1.3 that T_{n}(a) = T_{n}(b_{n}) is invertible and that

∥T_{n}^{−1}(a)∥ < \frac{2}{D_{n}} < \frac{4}{ε_{n}} = 12(∥v∥_{∞} + 1) max_{j} ω_{j}(\frac{6nq_{n}}{π} )

= 12(∥v∥_{∞} + 1)ω(\frac{6}{π} 13^{N}n) ≤ 12(∥v∥_{∞} + 1)ω(13^{N+1}n).

Example 3.6. Let a(e^{iθ}) = sin |θ| + iv(θ) where v ∈ L^{∞} is any real-valued function. The function u(θ) := sin |θ| has exactly two zeros in (−π, π], θ_{1} = 0 and θ_{2} = π. Since

\frac{1}{ω_{1}(n)} = \frac{1}{ω_{2}(n)} = inf \{ sin θ : \frac{1}{n} < θ < δ\} = sin \frac{1}{n} ≃ \frac{1}{n},

Theorem 3.4 yields κ(T_{n}(a)) = O(n) as n → ∞. Notice that this estimate does not depend on v. If v(θ) = cos θ (Example 1.4), then actually κ(T_{n}(a)) = O(1), and O(n) is too crude. However, if v(θ) = O(|θ|) as θ → 0 (which is, for example, the case if v(θ) = 0, v(θ) = sin θ, or v(θ) = sin |θ|), then Theorem 4.1 will show that the estimate O(n) cannot be improved.

4. Lower estimates for the condition numbers

The following theorem provides us with lower asymptotic estimates for the condition numbers of T_{n}(a) in case a is arbitrary (and not necessarily semi-definite) function in L^{∞} which, however, behaves sufficiently well in a vicinity of the zeros.

Theorem 4.1. Let α, β be positive constants, let e^{iθ_{0}} ∈ T, and suppose a ∈ L^{∞}.

(a) If a(e^{iθ}) = O(|θ − θ_{0}|^{α}) as θ → θ_{0} then there is a constant C ∈ (0, ∞) such that κ(T_{n}(a)) ≥ Cn^{α} for all n ≥ 1.

(b) If a(e^{iθ}) = O(1/| log(θ − θ_{0})/π| |^{α}) as θ → θ_{0} then there exists a constant C ∈ (0, ∞) such that

κ(T_{n}(a)) ≥ C(log n)^{α} for all n ≥ 1.

(c) If a(e^{iθ}) = O(e^{−β|θ−θ_{0}|^{−α}}) as θ → θ_{0} then

lim_{n→∞} n^{−k}κ(T_{n}(a)) = ∞

for every k > 0.

Recall that we define κ(T_{n}(a)) = ∞ in case T_{n}(a) is not invertible. The proof of Theorem 4.1 will be based on an auxiliary result.

For j, m ∈ N, consider the trigonometric polynomial

p_{m}^{j}(θ) = (1 + e^{iθ} + … + e^{imθ})^{j} = e^{imjθ/2}(\frac{sin \frac{m+1}{2}θ}{sin \frac{θ}{2}} )^{j}.  (28)

Clearly, p_{m}^{j} ∈ P_{mj+1} and ∥p_{m}^{j}∥_{∞} = (m + 1)^{j}. In the case j = 1, Parseval’s equality gives

∥p_{m}^{1}∥_{2}^{2} = \frac{1}{2π} ∫_{−π}^{π} |p_{m}^{1}(θ)|^{2}dθ = 1^{2} + 1^{2} + … + 1^{2} = m + 1.  (29)

Lemma 4.2. For each j ≥ 1, there exists a constant D_{j} ∈ [1, ∞) such that

(1/D_{j})m^{2j−1} ≤ ∥p_{m}^{j}∥_{2}^{2} ≤ D_{j}m^{2j−1}  (30)

for all m ≥ 1. Proof. For j = 1, this follows from (29). So let j ≥ 2. Then

∥p_{m}^{j}∥_{2}^{2} = \frac{1}{2π} ∫_{−π}^{π} (\frac{sin((m + 1)θ/2)}{θ/2})^{2j}(\frac{θ/2}{sin(θ/2)})^{2j}dθ  (31)
= \frac{1}{2π} ∫_{−π}^{π} (\frac{sin((m + 1)θ/2)}{θ/2})^{2j}(1 + O(θ^{2})) dθ

and

∫_{−π}^{π} (\frac{sin((m + 1)θ/2)}{θ/2})^{2j}θ^{2}dθ = 8(m + 1)^{2j−3} ∫_{−π(m+1)/2}^{π(m+1)/2} (\frac{sin x}{x})^{2j}x^{2}dx = O(m^{2j−3}),

∫_{−π}^{π} (\frac{sin((m + 1)θ/2)}{θ/2})^{2j}dθ = 2(m + 1)^{2j−1} ∫_{−π(m+1)/2}^{π(m+1)/2} (\frac{sin x}{x})^{2j}dx

= 2(m + 1)^{2j−1}( ∫_{−∞}^{∞} (\frac{sin x}{x})^{2j}dx + o(1)),

which shows that

lim_{m→∞} m^{−(2j−1)}∥p_{m}^{j}∥_{2}^{2} = \frac{1}{π} ∫_{−∞}^{∞} (\frac{sin x}{x})^{2j}dx.

Actually we will need only the left estimate of (30). Here is another proof of this estimate, which also specifies the constant 1/D_{j}.

Lemma 4.3. For j, m ∈ N the inequality

∥p_{m}^{j}∥_{2}^{2} > \frac{16}{9π} \frac{1}{\sqrt{j}} (m + 1)^{2j−1}

holds.

Proof. Starting with (31) we obtain

2π∥p_{m}^{j}∥_{2}^{2} > 2 ∫_{0}^{π} (\frac{sin((m + 1)θ/2)}{θ/2})^{2j}dθ

= 4(m + 1)^{2j−1} ∫_{0}^{(m+1)π/2}(\frac{sin x}{x})^{2j}dx > 4(m + 1)^{2j−1} ∫_{0}^{1/\sqrt{j}}(\frac{sin x}{x})^{2j}dx

> 4(m + 1)^{2j−1} ∫_{0}^{1/\sqrt{j}}(1 − \frac{x^{2}}{6} )^{2j}dx > 4(m + 1)^{2j−1} ∫_{0}^{1/\sqrt{j}}(1 − \frac{jx^{2}}{3} ) dx

= \frac{32}{9} \frac{1}{\sqrt{j}} (m + 1)^{2j−1}.

Proof of Theorem 4.1. We first prove part (a). Suppose θ_{0} = 0 and let us assume that |a(e^{iθ})| ≤ K|θ|^{α} for |θ| < δ. Fix n > 1/δ. We have

2π∥ap_{m}^{j}∥_{2}^{2} = ∫_{−π}^{π} |a(e^{iθ})|^{2}(\frac{sin((m + 1)θ/2)}{sin(θ/2)})^{2j}dθ =: ∫_{−π}^{π} f(θ) dθ  (32)

for every m, j ∈ N. Fix any j ∈ N such that j > α + 1/2. Because ∥p_{m}^{j}∥_{∞} = (m + 1)^{j}, we get

∫_{−1/m}^{1/m} f(θ) dθ ≤ K^{2} \frac{1}{m^{2α}} (m + 1)^{2j} ∫_{−1/m}^{1/m} dθ = K^{2} \frac{1}{m^{2α}} (m + 1)^{2j} \frac{2}{m}

and since |p_{m}^{j}(θ)| < 1/(sin \frac{θ}{2})^{2j} < (π/θ)^{2j} for 0 < |θ| < π, we obtain

∫_{1/m<|θ|<δ} f(θ) dθ ≤ 2K^{2} ∫_{1/m}^{δ} θ^{2α}(π/θ)^{2j}dθ = 2π^{2j}K^{2} ∫_{1}^{mδ}(\frac{x}{m})^{2(α−j)} \frac{dx}{m}
< 2π^{2j}K^{2}m^{2j−1}m^{−2α} ∫_{1}^{∞}x^{2(α−j)}dx ≤ M_{1} \frac{m^{2j−1}}{m^{2α}}

with M_{1} < ∞ (note that 2(α − j) < −1). Finally,

∫_{δ<|θ|<π} f(θ) dθ ≤ 2∥a∥_{∞}^{2} ∫_{δ}^{π}(π/θ)^{2j}dθ =: M_{2}.

In summary, there is a constant M_{3} < ∞ such that

∥ap_{m}^{j}∥_{2}^{2} ≤ M_{3} \frac{1}{m^{2α}} m^{2j−1}

for all m > 1/δ, and Lemma 4.2 (or Lemma 4.3) therefore implies that

∥ap_{m}^{j}∥_{2}^{2} ≤ M_{3}D_{j} \frac{1}{m^{2α}} ∥p_{m}^{j}∥_{2}^{2} =: M_{4} \frac{1}{m^{2α}} ∥p_{m}^{j}∥_{2}^{2}.  (33)

Given n, we write n = mj + k with k ∈ {1, …, j}. From (33) we infer that

∥T_{n}(a)p_{m}^{j}∥_{2}^{2} ≤ ∥ap_{m}^{j}∥_{2}^{2} ≤ M_{4} \frac{1}{m^{2α}} ∥p_{m}^{j}∥_{2}^{2} = M_{4} \frac{(2j)^{2α}}{(2mj)^{2α}} ∥p_{m}^{j}∥_{2}^{2} ≤ M_{4} \frac{(2j)^{2α}}{n^{2α}} ∥p_{m}^{j}∥_{2}^{2},

whence ∥T_{n}^{−1}(a)∥ ≥ M_{4}^{−1}(2j)^{−2α}n^{2α}. The proof of part (a) is complete.

To prove (b) suppose |a(e^{iθ})| ≤ K/| log(|θ|/π)|^{α} for |θ| < δ. Put j = 1, m = n, and define f by (32). Then for sufficiently large n,

∫_{−1/n}^{1/n} f(θ) dθ ≤ \frac{K^{2}}{(log(n/π))^{2α}} (n + 1)^{2} ∫_{−1/n}^{1/n} dθ ≤ M_{5} \frac{n}{(log n)^{2α}} ,

∫_{1/n<|θ|<δ} f(θ) dθ ≤ 2K^{2} ∫_{1/n}^{δ} \frac{1}{| log(θ/π)|^{2α}} (\frac{π}{θ} )^{2}dθ = 2K^{2}π ∫_{π/δ}^{πn} \frac{dx}{(log x)^{2α}} ≤ M_{6} \frac{n}{(log n)^{2α}} ,

∫_{δ<|θ|<π} f(θ) dθ ≤ 2∥a∥_{∞}^{2} ∫_{δ}^{π} (\frac{π}{θ} )^{2}dθ = M_{7},

and consequently, by Lemma 4.2 (or Lemma 4.3),

2π∥ap_{n}^{1}∥_{2}^{2} ≤ (M_{5} + M_{6} + M_{7})\frac{1}{(log n)^{2α}} D_{1}∥p_{n}^{1}∥_{2}^{2},

which gives the assertion as in part (a).

Finally, if a is as in part (c) then a(e^{iθ}) = O(|θ − θ_{0}|^{α}) as θ → θ_{0} for every α > 0. The assertion is therefore immediate from part (a).

If θ_{0} ≠ 0, the above arguments work with p_{m}^{j}(θ) replaced by p_{m}^{j}(θ − θ_{0}).

Corollary 4.4. Let a ∈ L^{∞}, suppose Re a ≥ 0 a.e., assume a has exactly N zeros e^{iθ_{1}}, …, e^{iθ_{N}} ∈ T and Re a has no other zeros than those of a. Suppose there are K ∈ [1, ∞), 0 < α_{j} ≤ β_{j} < ∞, δ ∈ (0, 1) such that

(1/K)|θ − θ_{j}|^{β_{j}} ≤ Re a(e^{iθ}) ≤ |a(e^{iθ})| ≤ K|θ − θ_{j}|^{α_{j}}  (34)

for |θ − θ_{j}| < δ. Then there is a constant C ∈ [1, ∞) such that

(1/C)n^{α} ≤ κ(T_{n}(a)) ≤ Cn^{β} for all n ≥ 1  (35)

where α := max{α_{1}, …, α_{N}} and β := max{β_{1}, …, β_{N}}.

Proof. The left inequality of (34) and the definition (20) give ω_{j}(n) ≤ Kn^{β_{j}}, and therefore κ(T_{n}(a)) ≤ C_{1}n^{β} by virtue of Theorem 3.4. Let α = α_{j_{0}}. Taking into account the right inequality of (34) with j = j_{0}, we obtain from Theorem 4.1(a) that κ(T_{n}(a)) ≥ C_{2}n^{α}.

Combining Theorem 3.4 and Theorem 4.1(b) we see that Corollary 4.4 remains true with (34) and (35) replaced by

(1/κ)( log |(θ − θ_{j})/π|)^{−β_{j}} ≤ Re a(e^{iθ}) ≤ |a(e^{iθ})| ≤ κ( log |(θ − θ_{j})/π|)^{−α_{j}}  (36)

and

(1/C)(log n)^{α} ≤ κ(T_{n}(a)) ≤ C(log n)^{β},

respectively.

The zeros occuring in the next corollary have been very popular for a long time in connection with the Fisher-Hartwig conjecture for Toeplitz determinants (see, e.g., [4]).

Corollary 4.5. Let t_{1}, …, t_{n} be distinct points on T, let α_{1}, …, α_{N} be positive real numbers, and let b ∈ L^{∞} be a function such that Re b ≥ ε > 0 a.e. on T. Put

a(t) := |t − t_{1}|^{2α_{1}} … |t − t_{N}|^{2α_{N}} b(t), t ∈ T,

and α := max{α_{1}, …, α_{N}}. Then

κ(T_{n}(a)) ≃ n^{2α}.

Proof. Since |e^{iθ} − e^{iθ_{j}}| ≃ |θ − θ_{j}|, this is immediate from Corollary 4.4.

Note that if, in addition, b is sufficiently smooth, then for the determinants det T_{n}(a) we have

det T_{n}(a) ∼ G(b)^{n}n^{α_{1}^{2}+...+α_{N}^{2}} E(a) as n → ∞

where G(b) = exp(log b)_{0} and E(a) is a nonzero constant (see [19] and [4]). This reveals that determinants are much more sensitive to singularities than condition numbers.

Example 4.6. Let

T_{n}(a) = ( \begin{matrix}1 & 0 & 0 & … & 0 \\ −1 & 1 & 0 & … & 0 \\ 0 & −1 & 1 & … & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & 0 & … & 1 \end{matrix} ) .

The symbol is a(e^{iθ}) = 1 − e^{iθ} and traces out the circle of radius 1 centered at 1. Both a and Re a have a single zero at θ = 0. Since

Re a(e^{iθ}) = 1 − cos θ ≃ θ^{2}, |(a(e^{iθ})| = (2 − 2 cos θ)^{1/2} ≃ |θ|

in a neighborhood of θ = 0, Corollary 4.4. gives

(1/C)n ≤ κ(T_{n}(a)) ≤ Cn^{2}.

As

T_{n}^{−1}(a) = ( \begin{matrix}1 & 0 & … & 0 \\ 1 & 1 & … & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 1 & 1 & … & 1 \end{matrix} ) = T_{n}(p_{n}^{1}),

we see that ∥T_{n}^{−1}(a)∥ = ∥T_{n}(p_{n}^{1})∥ ≤ ∥p_{n}^{1}∥_{∞} = n + 1 (taking the Frobenius norm even gives ∥T_{n}^{−1}(a)∥ ≤ \sqrt{n(n + 1)/2} ). Thus, the truth is κ(T_{n}(a)) ≃ n.

Example 4.7. Consider the Cauchy-Toeplitz matrices

T_{n}(c) = (\frac{1}{π(1/2 − j − k)})_{j,k=0}^{n−1}.

We have

T_{n}(c) = diag ((−1)^{j})T_{n}(a) diag ((−1)^{k})

where

T_{n}(a) = (\frac{(−1)^{j−k}}{π(1/2 − j − k)})_{j,k=0}^{n−1}.

Clearly, κ(T_{n}(c)) = κ(T_{n}(a)). The symbol a(e^{iθ}) is just the function e^{iθ/2} (θ ∈ (−π, π]) of Example 1.5. The real part u(θ) = cos(θ/2) has a single zero at θ = π. Since

\frac{1}{ω(n)} = min \{ cos \frac{θ}{2} : \frac{1}{n} < |θ − π| < δ\} = sin \frac{1}{2n} ≃ \frac{1}{n}

Theorem 3.4 implies that κ(T_{n}(a)) = O(n). Although Re a has a zero of “order” 1, the symbol a itself has no zero. Therefore Theorem 4.1 is not applicable. In the case at hand we actually have

κ(T_{n}(a)) ≃ log n;

this was shown by Tyrtyshnikov [17].

5. Exponentially growing condition numbers

Theorem 4.1 tells us that if a has a “very strong” zero, like e^{−1/|θ−θ_{j}|} say, then κ(T_{n}(a)) increases faster than any polynomial. We are therefore led to the question whether there are symbols a ∈ L^{∞} \ {0} such that κ(T_{n}(a)) grows even faster than e^{αn} (α > 0). The following result shows that this happens if a vanishes on open sets. Theorem 5.1. Let a ∈ L^{∞} \ {0} and suppose a(e^{iθ}) = 0 for |θ| < δ where δ ∈ (0, π). Then

κ(T_{n+1}(a)) ≥ \frac{∥T_{n+1}(a)∥}{∥a∥_{∞}} \frac{2\sqrt{2}}{3\sqrt{π}} \frac{1}{n^{1/4}} (\frac{1}{cos(δ/2)})^{n}  (37)

for all n ≥ 1 and thus

κ(T_{n}(a)) > \frac{1}{2} \frac{1}{n^{1/4}} (\frac{1}{cos(δ/2)})^{n}

for all sufficiently large n. Proof. Consider the polynomials p_{m}^{j} ∈ P_{mj+1} given by (28) and put m = 1. We have

2π∥ap_{1}^{j}∥_{2}^{2} = 2 ∫_{δ}^{π} |a(e^{iθ})|^{2}(\frac{sin θ}{sin(θ/2)})^{2}dθ

= 2 ∫_{δ}^{π} |a(e^{iθ})|^{2}(2 cos \frac{θ}{2})^{2j}dθ ≤ 2^{2j+1}π∥a∥_{∞}^{2}( cos \frac{δ}{2})^{2j}.

From Lemma 4.3 we know that

∥p_{1}^{j}∥_{2}^{2} ≥ \frac{16}{9π} \frac{1}{\sqrt{j}} 2^{2j−1}.

Consequently,

∥T_{j+1}(a)p_{1}^{j}∥_{2}^{2} ≤ ∥ap_{1}^{j}∥_{2}^{2} ≤ \frac{9}{8}π\sqrt{j}∥a∥_{∞}^{2}( cos \frac{δ}{2})^{2j}∥p_{1}^{j}∥_{2}^{2}.

Replacing j by n we obtain (37).

Since r^{n}n^{−1/4} increases faster than s^{n} where s ∈ (1, r), we see from Theorem 5.1 that κ(T_{n}(a)) increases faster than e^{αn} if only δ is sufficiently close to π. Theorem 5.2. Let a ∈ L^{∞} have a zero at e^{iθ_{0}} ∈ T and suppose |a(e^{iθ})| ≤ κe^{−1/|θ−θ_{0}|} with some K ∈ (0, ∞) for |θ − θ_{0}| < δ. Then there is a constant c ∈ (0, ∞) such that

κ(T_{n}(a)) ≥ c(e/2)^{\sqrt{n}}n^{−3/4} for all n ≥ 1.  (38)

Proof. Without loss of generality assume θ_{0} = 0. We start again with (32). For m > 1/δ,

∫_{−1/m}^{1/m} f(θ) dθ ≤ 2K^{2}(m + 1)^{2j} ∫_{0}^{1/m}e^{−2/θ}dθ

and

∫_{0}^{1/m}e^{−2/θ}dθ = ∫_{m}^{∞} \frac{e^{−2x}}{x^{2}} dx ≤ M_{1} \frac{e^{−2m}}{(m + 1)^{2}} .

Further,

∫_{1/m<|θ|<π} f(θ) dθ ≤ 2∥a∥_{∞}^{2} ∫_{1/m}^{π} e^{−2/θ}( sin(θ/2))^{−2j}dθ.  (39)

The maximum of the integrand of the last integral on (0, π) is attained at the solution θ_{j} of the equation

\frac{1}{j} = \frac{θ^{2}}{2} cot \frac{θ}{2}.  (40)

The right-hand side of (40) is θ + O(θ^{3}) as θ → 0, which implies that

θ_{j} = \frac{1}{j}(1 + O(\frac{1}{j^{2}} )) as j → ∞.

Hence, the maximum of e^{−2/θ}(sin(θ/2))^{−2j} is

e^{−2j+O(1/j)}( sin (\frac{1}{2j} + O(\frac{1}{j^{3}} )))^{−2j} ≃ e^{−2j}(\frac{1}{2j} + O(\frac{1}{j^{3}} ))^{−2j}

= e^{−2j}(2j)^{2j}(1 + O(\frac{1}{j^{2}} ))^{−2j} ≃ e^{−2j}(2j)^{2j}.

It follows that (39) is not greater than M_{2} e^{−2j}(2j)^{2j} where M_{2} < ∞ is some constant independent of m and j. In summary,

∥ap_{m}^{j}∥_{2}^{2} ≤ 2K^{2}M_{1} e^{−2m}(m + 1)^{2j−2} + M_{2} e^{−2j}(2j)^{2j}.

Taking into account Lemma 4.3, we get

\frac{∥ap_{m}^{j}∥_{2}^{2}}{∥p_{m}^{j}∥_{2}^{2}} ≤ M_{3} e^{−2m} \frac{\sqrt{j}}{m + 1} + M_{4} \frac{e^{−2j}(2j)^{2j}\sqrt{j}}{(m + 1)^{2j−1}} .  (41)

Now suppose we are given n > 4/δ^{2}. We put m = j = [\sqrt{n}] − 1. From (41) we then obtain

\frac{∥T_{n}(a)p_{m}^{j}∥_{2}^{2}}{∥p_{m}^{j}∥_{2}^{2}} ≤ M_{3} e^{−2m} \frac{\sqrt{m}}{m + 1} + M_{4} \frac{e^{−2m}2^{2m}\sqrt{m}}{(m + 1)^{−1}}

= (\frac{2}{e})^{2m}(m + 1)\sqrt{m}(\frac{M_{3}}{2^{2m}} \frac{1}{(m + 1)^{2}} + M_{4}) ≤ M_{5} (\frac{2}{e})^{2m}m^{3/2},

which implies (38).

The estimate (38) can certainly be improved but we will not embark on this problem. The conclusion of Theorem 5.2 is that even in the case of a single zero κ(T_{n}(a)) may grow faster than e^{α\sqrt{n}}.

6. Singular values, eigenvalues, finite section method

Given a selfadjoint n × n matrix A_{n}, we denote by

λ_{1}(A_{n}) ≤ λ_{2}(A_{n}) ≤ … ≤ λ_{n}(A_{n})  (42)

the eigenvalues of A_{n}. The singular values s_{j}(A_{n}) of an arbitrary n × n matrix A_{n} are the nonnegative square roots of the eigenvalues of the selfadjoint and positive semi-definite matrix A_{n}^{∗}A_{n}, i.e.

s_{j}(A_{n}) = \sqrt{λ_{j}(A_{n}^{∗}A_{n})}.

In accordance with the ordering (42),

0 ≤ s_{1}(A_{n}) ≤ s_{2}(A_{n}) ≤ … ≤ s_{n}(A_{n}).

It is easily seen that

s_{1}(A_{n}) = 1/∥A_{n}^{−1}∥ and s_{n}(A_{n}) = ∥A_{n}∥.

Hence, κ(A_{n}) = s_{n}(A_{n})/s_{1}(A_{n}). If A_{n} is selfadjoint, then λ_{j}(A_{n}) = s_{j}(A_{n}) for all j and κ(A_{n}) = λ_{n}(A_{n})/λ_{1}(A_{n}). The results of the preceding sections can therefore also be stated in terms of the singular values and the eigenvalues.

Asymptotics of singular values and eigenvalues of Toeplitz matrices have been studied by many authors; see, e.g., the recent papers [3], [7], [13], [14], [15], [18] and the literature listed there. In particular, the Avram-Parter theorem says that if a ∈ L^{∞} then the singular values {s_{j}(T_{n}(a))}_{j=1}^{n} and the values {|a(e^{2πij/n})|}_{j=1}^{n} are asymptotically equally distributed in the sense that, for every F ∈ C_{0}^{∞}(R),

\frac{1}{n} ∑_{j=1}^{n} F (s_{j}(T_{n}(a))) → \frac{1}{2π} ∫_{0}^{2π}F (|a(e^{iθ})|) dθ

as n → ∞. This theorem gives us the hint that if, for example, a(θ) = θ^{α} for θ ∈ (−π, π], then s_{j}(T_{n}(a)) should decay as 1/n^{α} for each j, but the theorem does not imply that s_{1}(T_{n}(a)) ≃ 1/n^{α}.

We now quote three sample results which are immediate consequences of the results of Sections 3 and 4.

Corollary 6.1. Under the hypotheses of Corollary 4.4 we have

\frac{1}{D} \frac{1}{n^{β}} ≤ s_{1}(T_{n}(a)) ≤ D\frac{1}{n^{α}} for all n ≥ 1

with some constant D ∈ [1, ∞).

Obviously, replacing (34) by (36) gives

\frac{1}{D} \frac{1}{(log n)^{β}} ≤ s_{1}(T_{n}(a)) ≤ D\frac{1}{(log n)^{α}} for all n ≥ 1,

while the presence of “very strong” zeros, such as e^{−1/|θ−θ_{j}|}, yield that s_{1}(T_{n}(a)) decreases faster than any negative power of n.

Corollary 6.2. Let a ∈ L^{∞} be real-valued and put m := ess inf a. If a − m has exactly N zeros e^{iθ_{1}}, …, e^{iθ_{N}} ∈ T such that

(1/K)|θ − θ_{j}|^{α_{j}} ≤ |a(e^{iθ}) − m| ≤ K|θ − θ_{j}|^{α_{j}}

for |θ − θ_{j}| < δ with K ∈ [1, ∞) and α_{j} ∈ (0, ∞), then there is a constant D ∈ [1, ∞) such that

\frac{1}{D} \frac{1}{n^{α}} ≤ λ_{1}(T_{n}(a)) − m ≤ D\frac{1}{n^{α}} for all n ≥ 1.

where α := max{α_{1}, …, α_{N}}.

In the case N = 1 and α_{j} = 2, this result is essentially already in [8, Example 5.3].

Corollary 6.3. Let T (a) be a selfadjoint Toeplitz band matrix and put m = min a. If T (a) is not a constant multiple of the identity matrix, then there is a constant C ∈ (0, ∞) such that

0 < λ_{1}(T_{n}(a)) − m < C \frac{1}{n^{2}} for all n ≥ 1.

In other words, κ(T_{n}(a) − mI) increases at least as n^{2} to infinity.

Proof. We can write

a(e^{iθ}) − m = \frac{a_{0}}{2} + ∑_{k=0}^{M}(a_{k} cos kθ + b_{k} sin kθ), θ ∈ (−π, π].

The function a(e^{iθ}) − m has at least one zero θ_{0} ∈ (−π, π]. Since a(e^{iθ}) − m is nonnegative, the Taylor expansion at θ_{0} reads

a(e^{iθ}) − m = A(θ − θ_{j})^{2} + O((θ − θ_{0})^{2})

with A ≥ 0. Consequently, a(e^{iθ}) − m has a zero of order at least 2, and Theorem 4.1(a) therefore gives the assertion.

Obviously, the conclusion of Corollary 6.3 remains true for selfadjoint Toeplitz matrices with twice continuously differentiable symbols.

The finite section method for solving the infinite system T (a)x = y consists in passage to the truncated systems

T_{n}(a)x^{(n)} = P_{n}y, x^{(n)} ∈ Im P_{n}  (43)

where P_{n} : l^{2} → l^{2} is the projection defined by

P_{n} : {x_{0}, x_{1}, x_{2}, …} ↦ {x_{0}, x_{1}, …, x_{n−1}, 0, 0, …}.

If T (a) is invertible, then the finite section method is applicable in many cases (see, e.g.,

[5] and [4]). It is in particular applicable if T (a) is positive definite. Things are more complicated if T (a) is merely known to be semi-definite.

Some results are available provided we can estimate the growth of ∥T_{n}^{−1}(a)∥. The following simple proposition is well known (see, e.g., [12]) and is merely cited in order to illustrate the usefulness of such results as Theorem 3.4.

Let l_{α}^{2} (α > 0) denote the Hilbert space of all complex sequences {x_{n}}_{n=0}^{∞} such that ∑(n + 1)^{2α}|x_{n}|^{2} < ∞.

Proposition 6.4. Let a ∈ L^{∞} and suppose Re a ≥ 0 a.e. If

κ(T_{n}(a)) = O(n^{α}) (α ≥ 0)  (44)

and y is an element of l^{2} such that the equation T (a)x = y has a solution x ∈ l_{α}^{2} then the solutions x^{(n)} of (43) converge to x in the norm of l^{2}.

Proof. We observed in the introduction that T (a) is injective and that T_{n}(a) is invertible for all n ≥ 1. Let T_{n}(a)x^{(n)} = P_{n}y. We have

∥x^{(n)} − x∥ ≤ ∥T_{n}^{−1}(a)P_{n}y − P_{n}x∥ + ∥P_{n}x − x∥

and it is clear that ∥P_{n}x − x∥ → 0. By (44),

∥T_{n}^{−1}(a)P_{n}y − P_{n}x∥ ≤ Cn^{α}∥P_{n}y − T_{n}(a)P_{n}x∥
≤ Cn^{α}∥P_{n}y − P_{n}T (a)x∥ + Cn^{α}∥P_{n}T (a)Q_{n}x∥  (45)

where Q_{n} := I − P_{n}. The first term in (45) is zero and the second term is at most

Cn^{α}∥a∥_{∞}∥Q_{n}x∥ = Cn^{α}∥a∥_{∞}( ∑_{j≥n} |x_{j}|^{2})^{1/2}

≤ Cn^{α}∥a∥_{∞} \frac{1}{n^{α}} ( ∑_{j≥n}(j + 1)^{2α}|x_{j}|^{2})^{1/2} = C∥a∥_{∞}∥Q_{n}x∥_{l_{α}^{2}}.

Since ∥Q_{n}x∥_{l_{α}^{2}} → 0 whenever x ∈ l_{α}^{2}, it follows that ∥x^{(n)} − x∥ → 0.

7. Finite Wiener-Hopf integral operators

Let τ ∈ (0, ∞) and a ∈ L^{∞}(R). The Wiener-Hopf integral operator W_{τ}(a) is defined on L^{2}(0, τ) by the formula

(W_{τ}(a)f)(x) = \frac{1}{2π} ∫_{−∞}^{∞} (a(ξ) ∫_{0}^{τ} f(y)e^{iξy}dy)e^{−iξx}dx, x ∈ (0, τ).

We remark that if

a(ξ) = c + ∫_{−∞}^{∞} k(x)e^{iξx}dx, ξ ∈ R,

with some function k ∈ L^{1}(R), then W_{τ}(a) acts by the rule

(W_{τ}(a)f)(x) = cf(x) + ∫_{0}^{τ} k(x − t)f(t) dt, x ∈ (0, τ).

To have another example, note that in the case where a(ξ) = sign ξ we have

(W_{τ}(a)f)(x) = \frac{1}{πi} ∫_{0}^{τ} \frac{f(t)}{x − t} dt, x ∈ (0, τ),

the integral understood in the Cauchy principal sense.

Wiener-Hopf integral operators are the continuous analogues of Toeplitz matrices. The results of the previous sections can be easily extended to Wiener-Hopf operators. The part of e^{inθ} and cos nθ is now played by e^{iτξ} and cos τξ. Notice that

W_{τ}(a) = W_{τ}(a + ig_{σ}) where g_{σ}(ξ) := cos σξ and σ ≥ τ.

Instead of the polynomials p_{n}^{j}(e^{iθ}) employed in Section 4 one can work with the functions

φ_{τ}^{j}(ξ) = ( ∫_{0}^{τ} e^{iξx} dx)^{j} = (\frac{e^{iτξ} − 1}{iξ})^{j}, ξ ∈ R.  (46)

Note that

φ_{τ}^{j}(ξ) = e^{ijτξ/2}(\frac{sin \frac{ξτ}{2}}{ξ/2} )^{j}, ξ ∈ R,  (47)

and that there are constants D_{j} ∈ [1, ∞) such that

(1/D_{j})τ^{j−1/2} ≤ ∥φ_{τ}^{j}∥_{L^{2}(R)} ≤ D_{j}τ^{j−1/2}

for all τ > 0 and all j ∈ N.

Here are the Wiener-Hopf analogous of Theorems 3.4 and 4.1.

Theorem 7.1. Let a ∈ L^{∞}(R), suppose Re a ≥ 0 a.e. on R, and assume u := Re a has exactly N ≥ 1 zeros ξ_{1}, …, ξ_{N} on R. Let

ess inf {u(ξ) : ξ ∈ R \ ⋃_{j=1}^{N}(ξ_{j} − δ, ξ_{j} + δ)} > 0,

put

\frac{1}{ω_{j}(τ)} := ess inf \{u(ξ) : \frac{1}{τ} < |ξ − ξ_{j}| < δ\},

and define ω(τ) := max{ω_{1}(τ), …, ω_{N}(τ)}. Then W_{τ}(a) is invertible for all τ > 0 and

κ(W_{τ}(a)) = O(ω(13^{N+1}τ)) as τ → ∞.

Theorem 7.2. Let α, β, τ_{0} be positive constants, let ξ_{0} ∈ R, and suppose a ∈ L^{∞}(R). (a) If |a(ξ)| = O(|ξ − ξ_{0}|^{α}) as ξ → ξ_{0} then there is a constant C ∈ (0, ∞) such that

κ(W_{τ}(a)) ≥ Cτ^{α} for all τ ≥ τ_{0}.

(b) If |a(ξ)| = O(1/| log |ξ − ξ_{0}| |^{α}) as ξ → ξ_{0} then there exists a constant C ∈ (0, ∞) such that

κ(W_{τ}(a)) ≥ C( log \frac{τ}{τ_{0}} )^{α} for all τ ≥ τ_{0}.

(c) If |a(ξ)| = O(e^{−β|ξ−ξ_{0}|^{−α}}) as ξ → ξ_{0} then

lim_{τ→∞} τ^{−k}κ(W_{τ}(a)) = ∞

for every k > 0.

Corollary 7.3. Let ξ_{1}, …, ξ_{N} be distinct points on R, let α_{1}, …, α_{N} be positive real numbers, and let b ∈ L^{∞}(R) be a function for which Re b ≥ ε > 0 a.e. on R. Put

a(ξ) = |\frac{ξ − ξ_{1}}{ξ + i} |^{2α_{1}} … |\frac{ξ − ξ_{N}}{ξ + i} |^{2α_{N}} b(ξ), ξ ∈ R,

and define α := max{α_{1}, …, α_{N}}. Then for every τ_{0} > 0 there exists a constant C(τ_{0}) ∈ [1, ∞) such that

(1/C(τ_{0}))τ^{2α} ≤ κ(W_{τ}(a)) ≤ C(τ_{0})τ^{2α} for all τ ≥ τ_{0}.

Here is a Wiener-Hopf analogue of Theorem 5.1.

Theorem 7.4. Let a ∈ L^{∞}(R) \ {0} and suppose a(ξ) = 0 for |ξ| > δ where δ ∈ (0, ∞). Then

κ(W_{τ}(a)) > \frac{∥W_{τ}(a)∥}{∥a∥_{∞}} \frac{2}{3\sqrt{π}} (\frac{δ}{4e^{3}} )^{1/4}τ^{1/4}(e^{δ/(4e)})^{τ}

for τ > 8e/δ and thus

κ(W_{τ}(a)) > \frac{1}{2\sqrt{π}} (\frac{δ}{4e^{3}} )^{1/4}τ^{1/4}(e^{δ/(4e)})^{τ}

for all sufficiently large τ.

Proof. Let φ_{τ}^{j} be the function (46). One can show as in the proof of Lemma 4.3 that

∥φ_{τ}^{j}∥_{2}^{2} > \frac{16}{9π} \frac{1}{\sqrt{j}} τ^{2j−1}.

If τ > 0 and j ∈ N, then, by (47),

\frac{∥aφ_{τ/j}^{j}∥_{2}^{2}}{∥φ_{τ/j}^{j}∥_{2}^{2}} ≤ 2∥a∥_{∞}^{2} ∫_{δ}^{∞}(\frac{2}{ξ})^{2j}dξ \frac{9π}{16} \sqrt{j}(\frac{j}{τ} )^{2j−1} = \frac{9π}{4} ∥a∥_{∞}^{2} \frac{\sqrt{j}}{2j − 1}(\frac{2j}{δτ} )^{2j−1}.

Letting j = [τ] + 1 we therefore get

∥W_{τ}^{−1}(a)∥ ≥ \frac{2}{3\sqrt{π}} \frac{1}{∥a∥_{∞}} \frac{(2[τ] + 1)^{1/2}}{([τ] + 1)^{1/4}} (\frac{δτ}{2([τ] + 1)})^{[τ]+1/2}.  (48)

This shows that ∥W_{τ}^{−1}(a)∥ increases exponentially if δ > 2. To cover the case δ ≤ 2, we proceed as follows. For λ > 0, consider the invertible isometry

U_{λ} : L^{2}(0, τ) → L^{2}(0, τ/λ), (U_{λ}f)(x) = \sqrt{λ}f(λx).

A straightforward computation gives

U_{λ}W_{τ}(a)U_{λ}^{−1} = W_{τ/λ}(a_{λ}) where a_{λ}(ξ) = a(ξ/λ).

Applying (48) to W_{τ/λ}(a_{λ}) we get

∥W_{τ}^{−1}(a)∥ = ∥W_{τ/λ}^{−1}(a_{λ})∥ ≥ \frac{2}{3\sqrt{π}} \frac{1}{∥a∥_{∞}} \frac{(2[τ/λ] + 1)^{1/2}}{([τ/λ] + 1)^{1/4}} (\frac{λδτ/λ}{2([τ/λ] + 1)})^{[τ/λ]+1/2}  (49)

(note that a_{λ}(ξ) vanishes for |ξ| < λδ). The function (λδ/4)^{1/λ} attains its maximum at 4e/δ. Thus, let us put λ = 4e/δ in (49) and let us assume that τ > 2λ = 8e/δ. Then

\frac{(2[τ/λ] + 1)^{1/2}}{([τ/λ] + 1)^{1/4}} ≥ \frac{(2[τ/λ])^{1/2}}{(2[τ/λ])^{1/4}} > 2^{1/4}(\frac{τ}{2λ})^{1/4} = (\frac{τ}{λ})^{1/4},

\frac{λδτ/λ}{2([τ/λ] + 1)} > \frac{λδ}{4} = e, [\frac{τ}{λ}] + \frac{1}{2} > \frac{τ}{λ} − \frac{1}{2},

which implies the assertion.

Under the hypotheses of Theorem 7.1 and Corollary 7.3, the operators W_{τ}(a) are invertible for all τ > 0. This is no longer true if the symbol a has a zero at infinity.

Proposition 7.5. Let a ∈ L^{∞}(R) and suppose

lim_{η→∞} ess sup_{ξ>η} |a(ξ)| = 0.

Then W_{τ}(a) is not invertible and thus κ(W_{τ}(a)) = ∞ for all τ > 0.

Proof. Fix τ > 0, put ξ_{n} := πn/τ, and define ψ_{n} ∈ L^{2}(0, τ) by

ψ_{n}(x) = \frac{1}{\sqrt{τ}} e^{−2iξ_{n}x}, 0 < x < τ.

Clearly, ∥ψ_{n}∥_{2} = 1. The Fourier transform ψ̂_{n} of ψ_{n} is

ψ̂_{n}(ξ) = ∫_{0}^{τ} \frac{1}{\sqrt{τ}} e^{ix(ξ−2ξ_{n})}dx = −\frac{i}{\sqrt{τ}} \frac{e^{iξτ} − 1}{ξ − 2ξ_{n}}.

Hence

2π∥W_{τ}(a)ψ_{n}∥_{2}^{2} ≤ ∫_{−∞}^{∞} |a(ξ)ψ̂_{n}(ξ)|^{2}dξ

≤ ∥a∥_{L^{∞}(ξ_{n},3ξ_{n})}^{2}∥ψ̂_{n}∥_{2}^{2} + ∥a∥_{∞}^{2} ∫_{|ξ−2ξ_{n}|>ξ_{n}} \frac{4dξ}{τ|ξ − 2ξ_{n}|^{2}} .

Since ∥ψ̂_{n}∥_{2}^{2} = 2π, ∥a∥_{L^{∞}(ξ_{n},3ξ_{n})} → 0 as n → ∞, and

∫_{|ξ−2ξ_{n}|>ξ_{n}} \frac{4dξ}{τ|ξ − 2ξ_{n}|^{2}} = \frac{8}{τ} ∫_{ξ_{n}}^{∞} \frac{dr}{r^{2}} = \frac{8}{τξ_{n}} = \frac{8}{τ} \frac{τ}{πn} = \frac{8}{πn} → 0 as n → ∞,

it follows that ∥W_{τ}(a)ψ_{n}∥_{2} → 0.

8. Multidimensional Toeplitz matrices

Let Ω ∈ R^{2} be a bounded set whose set of inner points is not empty. Given a function a ∈ L^{∞} on the torus T^{2}, the two-dimensional Toeplitz operator T_{nΩ}(a) is defined on l^{2}(nΩ ∩ Z^{2}) by

(T_{nΩ}(a)φ)_{j} = ∑_{k∈nΩ∩Z^{2}} a_{j−k}φ_{k}, j ∈ nΩ ∩ Z^{2},

where

a_{l,m} := \frac{1}{(2π)^{2}} ∫_{−π}^{π} ∫_{−π}^{π} a(e^{ix}, e^{iy})e^{−ilx}e^{−imy}dx dy, (l, m) ∈ Z^{2}.

If Ω = [0, 1]^{2}, then T_{nΩ}(a) is also referred to as a “two-level” Toeplitz operator, because T_{nΩ}(a) is in a natural manner unitarily equivalent to a matrix of the form

( \begin{matrix}T_{n}(b_{0}) & T_{n}(b_{−1}) & … & T_{n}(b_{−(n−1)}) \\ T_{n}(b_{1}) & T_{n}(b_{0}) & … & T_{n}(b_{−(n−2)}) \\ ⋮ & ⋮ & ... & ⋮ \\ T_{n}(b_{n−1}) & T_{n}(b_{n−2}) & … & T_{n}(b_{0}) \end{matrix} ) .

In the case where Ω is a polygon, criteria for the boundedeness of the condition numbers κ(T_{nΩ}(a)) are known (see [11] and [4]). If Ω is arbitrary and Re a ≥ ε > 0 a.e. on T^{2}, then T_{nΩ}(a) is invertible on l^{2}(nΩ ∩ Z^{2}) for all n ≥ 1 and κ(T_{nΩ}(a)) < 2∥a∥_{∞}/ε. Difficulties arise as soon as only Re a ≥ 0 is required, mainly because the set of zeros of a function of two variables is typically not discrete. However, in case Re a has merely a finite number of zeros, we can proceed as in Section 3.

Let a ∈ L^{∞}(T^{2}) and Re a ≥ 0 a.e. on T^{2}. Put u(x, y) := Re a(e^{ix}, e^{i,y}). For (x_{0}, y_{0}) ∈ R^{2}, let

U_{δ}(x_{0}, y_{0}) := {(x, y) ∈ R^{2} : (x − x_{0})^{2} + (y − y_{0})^{2} < δ^{2}}.

A point (x_{0}, y_{0}) ∈ (−π, π]^{2} is called a zero of u if

ess inf {u(x, y) : (x, y) ∈ U_{δ}(x_{0}, y_{0})} = 0

for every δ > 0. Assume u has exactly N ≥ 1 zeros (x_{1}, y_{1}), …, (x_{N}, y_{N}) in (−π, π]^{2}. Choose δ > 0 so that the disks U_{δ}(x_{j}, y_{j}) are pairwise disjoint, put

\frac{1}{ω_{j}(n)} := ess inf \{u(x, y) : \frac{1}{n^{2}} < (x − x_{j})^{2} + (y − y_{j})^{2} < δ^{2}\},  (50)
ω(n) := max {ω_{1}(n), …, ω_{N}(n)}.  (51)

Finally, let

D_{Ω} := sup \{\sqrt{(x_{1} + x_{2})^{2} + (y_{1} + y_{2})^{2}} : (x_{1}, y_{1}) ∈ Ω, (x_{2}, y_{2}) ∈ Ω\}.

Theorem 8.1. Let a ∈ L^{∞}(T^{2}), suppose u := Re a ≥ 0 a.e., and assume u has exactly N ≥ 1 zeros (x_{1}, y_{1}), …, (x_{N}, y_{N}) in (−π, π]^{2}. Define ω(n) by (50) and (51). Then

κ(T_{nΩ}(a)) ≤ 20(∥Im a∥_{∞} + 1)ω(4D_{Ω}13^{2N}n)

for all sufficiently large n.

Proof outline. The proof is similar to the proof of Theorem 3.4. First, it is easily seen that

nΩ + (−nΩ) ⊂ [−s_{n}, s_{n}]^{2}  (52)

where s_{n} = 2nD_{Ω}. Thus, T_{nΩ}(a) contains only the Fourier coefficients a_{lm} for which |l| ≤ s_{n} and |m| ≤ s_{n}. Application of Lemma 3.5 with μ = 1/12 and the 2N numbers

s_{n}x_{1}/(2π), …, s_{n}x_{N}/(2π), s_{n}y_{1}/(2π), …, s_{n}y_{N}/(2π)

gives an integer q_{n} such that

1 ≤ q_{n} ≤ 13^{2N} and s_{n}q_{n}x_{j}, s_{n}q_{n}y_{j} ∈ 2πZ + ( − \frac{π}{6} , \frac{π}{6} ).

As in the proof of Theorem 3.4 we obtain that

cos(s_{n}q_{n}x) > 1/2, cos(s_{n}q_{n}y) > 1/2

whenever |x − x_{j}| < r_{n}, |y − y_{j}| < r_{n} with r_{n} := π/(6s_{n}q_{n}). Denote by v the imaginary part of a, put

\frac{1}{ε_{n,j}} := 5(∥v∥_{∞} + 1)ω_{j}(\frac{6s_{n}q_{n}}{π} ), M := 4(∥v∥_{∞} + 1),

and consider the function

b_{n}(e^{ix}, e^{iy}) := a(e^{ix}, e^{iy}) + iM cos(s_{n}q_{n}x) cos(s_{n}q_{n}y).

Then T_{nΩ}(a) = T_{nΩ}(b_{n}). Repeating the argument of the proof of Theorem 3.4 we arrive at the conclusion that the essential range of b_{n} lies above the straight line y = 1 − (1/ε_{n})x where ε_{n} := min_{j} ε_{n,j} if only n is sufficiently large, whence ∥T_{nΩ}^{−1}(a)∥ < 4/ε_{n}. This implies the assertion.

Example 8.2. Let a(e^{ix}, e^{iy}) = 2 − cos x − cos y. The zero of this symbol is (x, y) = (0, 0), we have

\frac{1}{ω(n)} = min\{2 − cos x − cos y : x^{2} + y^{2} ≥ 1/n^{2}\}
= 2(1 − cos \frac{\sqrt{2}}{2n}) = 4 sin^{2} \frac{\sqrt{2}}{4n} ≃ \frac{1}{n^{2}}

and thus, κ(T_{nΩ}(a)) = O(n^{2}) as n → ∞.

Theorem 8.1 generalizes to d-dimensional Toeplitz operators. With ω(n) and D_{Ω} defined in the obvious manner, we have

κ(T_{nΩ}(a)) = O(ω(4D_{Ω}13^{dN}n)) as n → ∞.  (53)

Note that if Ω = [0, 1]^{d}, then (52) is true with s_{n} = n, so that in (53) the factor 4D_{Ω}13^{dN} can be replaced by 2 · 13^{dN}. Since 2 · 13^{dN} < 13^{dN+1}, this agrees with Theorem 3.4 in the case d = 1.

The extension of Theorem 4.1 to higher dimensions seems to be difficult. The following result is the d-dimensional analogue of Theorem 5.1.

Theorem 8.3. Suppose Ω = [0, 1]^{d} and a ∈ L^{∞}(T^{d}) \ {0} vanishes on (−δ, δ)^{d} where δ ∈ (0, π). Then

κ(T_{(n+1)Ω}(a)) ≥ \frac{∥T_{(n+1)Ω}(a)∥}{\sqrt{2d}∥a∥_{∞}}(\frac{8}{9π} )^{d/2} \frac{1}{n^{d/4}} (\frac{1}{cos(δ/2)})^{n}

for all n ≥ 1 and thus

κ(T_{nΩ}(a)) > \frac{1}{2\sqrt{d}}(\frac{8}{9π} )^{d/2} \frac{1}{n^{d/4}} (\frac{1}{cos(δ/2)})^{n}

for all suffuiciently large n.

Proof outline. To simplify notation let d = 2. Put

R_{δ} = {(x, y) ∈ (−π, π]^{2} : |x| ≥ δ or |y| ≥ δ},
S_{δ} = {(x, y) ∈ (−π, π]^{2} : |x| ≥ δ}.

With p_{m}^{j} as in Section 4, we have

4π^{2}∥a(p_{1}^{j} ⊗ p_{1}^{j})∥_{2}^{2} ≤ ∥a∥_{∞}^{2} ∫ ∫_{R_{δ}} (\frac{sin x}{sin(x/2)})^{2j}(\frac{sin y}{sin(y/2)})^{2j}dx dy

≤ 2∥a∥_{∞}^{2} ∫ ∫_{S_{δ}} (2 cos \frac{x}{2})^{2j}(2 cos \frac{y}{2} )^{2j}dx dy

≤ 2^{4j+1}∥a∥_{∞}^{2}( cos \frac{δ}{2})^{2j}(2π)^{2}.

Since

∥p_{1}^{j} ⊗ p_{1}^{j}∥_{2}^{2} ≥ (\frac{8}{9π} )^{2} \frac{1}{j} 2^{4j}.

by virtue of Lemma 4.3, it follows that

∥a(p_{1}^{j} ⊗ p_{1}^{j})∥_{2}^{2} ≤ 2∥a∥_{∞}^{2}(\frac{9π}{8} )^{2}j( cos \frac{δ}{2})^{2j}∥p_{1}^{j} ⊗ p_{1}^{j}∥_{2}^{2}.

This gives the assertion as in the proof of Theorem 5.1.

9. Approximation by Toeplitz band matrices

For a ∈ L^{∞} := L^{∞}(T), denote by s_{n}a and σ_{n}a the nth partial sum of the Fourier series and the nth Fejer-Cesaro mean, respectively. Thus,

(s_{n}a)(e^{iθ}) = ∑_{k=−n}^{n} a_{n}e^{inθ},

(σ_{n}a)(e^{iθ}) = \frac{1}{n + 1} ∑_{j=0}^{n}(s_{j}a)(e^{iθ}).

Clearly, T (s_{n}a) and T (σ_{n}a) are Toeplitz band matrices.

Suppose a is smooth, say Hölder continuous. Then both s_{n}a and σ_{n}a converge uniformly to a. Hence, if T (a) is invertible, then T (s_{n}a) and T (σ_{n}a) are invertible for all sufficiently large n and

∥T^{−1}(s_{n}a) − T^{−1}(a)∥ → 0, ∥T^{−1}(σ_{n}a) − T^{−1}(a)∥ → 0,

which implies that

lim_{n→∞} κ(T (s_{n}a)) = lim_{n→∞} κ(T (σ_{n}a)) = κ(T (a)).  (54)

In particular, if Re a ≥ ε > 0 then (54) holds.

Things change if a is smooth and all we know is that Re a ≥ 0 on T. Assume, for example, a(e^{iθ}) = θ^{2}/4 for θ ∈ (−π, π]. The Fourier series is

a(e^{iθ}) = \frac{π^{2}}{12} − cos θ + \frac{1}{2^{2}} cos 2θ − \frac{1}{3^{2}} cos 3θ + − …

and hence

(s_{n}a)(1) = \frac{π^{2}}{12} − 1 + \frac{1}{2^{2}} − \frac{1}{3^{2}} + − … − \frac{1}{n^{2}} < 0

if n is odd. Consequently, T (s_{n}a) is not invertible and thus κ(T (s_{n}a)) = ∞ for every odd number n. It follows that there is no sequence {ω(n)}_{n=1}^{∞} such that κ(T (s_{n}a)) = O(ω(n)) as n → ∞.

The operators T (σ_{n}a) behave much better than the operators T (s_{n}a). We remark that for large classes of symbols a, e.g., for

a ∈ (C + H^{∞}) ∪ (C + \overline{H^{∞}}) ∪ P QC,

the operator T (a) is Fredholm of index k if and only if σ_{n}a is bounded away from zero and has the winding number −k for all sufficiently large n (see [4]).

If a ∈ L^{∞} and κ(T (σ_{n}a)) = O(1) as n → ∞, then T (a) must be invertible (this follows as in the proof of Proposition 1.2 from the fact that T (σ_{n}a) converges strongly to T (a)). Hence, κ(T (σ_{n}a)) is necessarily unbounded in case a has zeros on T. The following theorem provides us with upper bounds for κ(T (σ_{n}a)).

Theorem. Let a ∈ L^{∞}, suppose u(θ) := Re a(e^{iθ}) is nonnegative and has exactly N ≥ 1 zeros θ_{1}, …, θ_{N} in (−π, π], define ω_{j}(n) by (20), and put ω(n) := max{ω_{1}(n), …, ω_{N}(n)}. Then

κ(T (σ_{n}a)) ≤ 12∥a∥_{∞}(∥Im a∥_{∞} + 1)ω(13^{N+1}n)

for all sufficiently large n.

Proof. Let q_{n} be as in the proof of Theorem 3.4 and define b_{n} by (24) and (25). Then T (σ_{n}a) = T (σ_{n}b_{n}) and hence

∥T^{−1}(σ_{n}a)∥ = ∥T^{−1}(σ_{n}b_{n})∥ < 2/dist (0, conv R(σ_{n}, b_{n}))

by Proposition 1.3. Since σ_{n} is a nonnegative apprioximate identity, the inclusion

conv R(σ_{n}b_{n}) ⊂ conv R(b_{n})

holds. Thus,

∥T^{−1}(σ_{n}a)∥ < 2/dist (0, conv R(b_{n})) =: 2/D_{n}.

The assertion now follows as in the proof of Theorem 3.4.

We remark that this theorem extends to quarter-plane Toeplitz operators and their higher-dimensional versions and that it also has analogues for Wiener-Hopf integral operators.

Appendix

Suppose a ∈ L^{∞} \ {0} and conv R(a) ⊂ L where L is a straight line passing through the origin. On replacing a by γa with an appropriate γ ∈ T, we can without loss of generality assume that a is real-valued. Put

m = ess inf a, M = ess sup a.

If 0 ≤ m or M ≤ 0, then Proposition 1.1 tells us that T_{n}(a) is invertible for all n ≥ 1.

Example A.1. Fix α ∈ (−π, π) and define a by

a(e^{iθ}) = 2(cos θ + cos α).

It is easily seen that

det T_{n}(a) = det ( \begin{matrix}2 cos α & 1 & 0 & … & 0 \\ 1 & 2 cos α & 1 & … & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & 0 & … & 2 cos α \end{matrix} ) = \frac{sin(n + 1)α}{sin α}.

Hence, if α/π is irrational then m < 0 < M and det T_{n}(a) ≠ 0 for all n ≥ 1. If α/π is rational and | cos α| < 1, then again m < 0 < M but there are infinitely many n for which det T_{n}(a) = 0 and infinitely many n such that det T_{n}(a) ≠ 0.

Theorem A.2. If a ∈ L^{∞} \ {0} is real-valued then T_{n}(a) is invertible for infinitely many n ≥ 1.

The proof is based on two lemmas.

Lemma A.3. If a ∈ L^{∞}\{0} is real-valued and det T_{n}(a) = 0 for all n ≥ n_{0} then a = s/|q|^{2} where

s(t) = ∑_{ν=−l}^{l} c_{l}t^{l} (t ∈ T)

is a real-valued trigonometric polynomial such that c_{l} = \overline{c}_{−l} ≠ 0 and

q(t) = ∏_{j=1}^{k}(t − α_{j}) (t ∈ T)

with 0 < |α_{j}| < 1 and k ≥ l ≥ 0.

Proof. Let H^{∞} denote the functions in L^{∞} whose Fourier coefficients with negative indices vanish and let R stand for the rational functions in L^{∞}.

Assume det T_{n}(a) = 0 for all n ≥ n_{0}. Heinig [9, Satz 6.1 and Lemma 6.1] showed that then a or \overline{a} belongs to R + H^{∞}. Since a is real-valued, we may suppose that a ∈ R + H^{∞}. Hence, there are analytic polynomials p, r and a function h ∈ H^{∞} such that a = p/r + h. Write

r(t) = t^{k}r_{−}(t) r_{+}(t), r_{−}(t) := ∏_{j=1}^{k} (1 − \frac{α_{j}}{t} ), r_{+}(t) := ∏_{j=1}^{m}(t − β_{j})

where 0 < |α_{j}| < 1 and |β_{j}| > 1. It follows that

a(t)|r_{−}(t)|^{2} = t^{−k}(\frac{p(t)\overline{r_{−}(t)}}{r_{+}(t)} + h(t)(t^{k}r_{−}(t))\overline{r_{−}(t)})

and the function on the right is of the form t^{−k}g(t) with g ∈ H^{∞}. Since a(t)|r_{−}(t)|^{2} is real-valued, so also is t^{−k}g(t). This implies that

t^{−k}g(t) = ∑_{ν=−l}^{l} c_{ν}t^{l}, l ≤ k, c_{l} = \overline{c}_{−l} ≠ 0.

Because |r_{−}(t)| = Π|t − α_{j}|, we arrive at the assertion.

Lemma A.4. For n ∈ N, let

p(n) = ∑_{k=1}^{m} α_{k}e^{ix_{k}n}

with complex numbers α_{k} and distinct real numbers x_{k} ∈ [0, 2π). If p(n) → 0 as n → ∞, then α_{1} = … = α_{m} = 0.

Proof. Let l ∈ N and consider the values of p at the points l, l + 1, …, l + m − 1:

∑_{k=1}^{m} α_{k}e^{ix_{k}(l+ν)} = p(l + ν) where ν = 0, 1, …, m − 1.

We may rewrite these m equations in the form

A diag (e^{ix_{k}l})_{k=1}^{m} α = μ(l)

where α := column (α_{k})_{k=1}^{m}, μ(l) := column (p(l + ν))_{ν=0}^{m−1}, and A is the invertible Vandermonde matrix

A := ( \begin{matrix}1 & 1 & … & 1 \\ e^{ix_{1}} & e^{ix_{2}} & … & e^{ix_{m}} \\ ⋮ & ⋮ & & ⋮ \\ e^{i(m−1)x_{1}} & e^{i(m−1)x_{2}} & … & e^{i(m−1)x_{m}} \end{matrix} ) .

Hence,

α = diag (e^{−ix_{k}l})_{k=1}^{m}A^{−1}μ(l).

Since the entries of A and thus of A^{−1} are independent of l and the components of μ(l) go to zero as l approaches infinity, it follows that the components of α must also tend to zero as l increases to infinity. Because α does actually not depend on l, we arrive at the conclusion that α = 0.

Proof of Theorem A.2. Suppose det T_{n}(a) = 0 for all n ≥ n_{0}. Then, by Lemma A.3, a is necessarily a rational function. By a result of Gorodetsky [6] and Trench [16] (also see [1]), we therefore have

det T_{n}(a) = ∑_{s=0}^{N} ∑_{j=1}^{M_{s}}(c_{j,s}e^{z_{j,s}n})n^{s} (A1)

for all n ≥ 1 with certain nonnegative integers N, M_{s} and complex numbers c_{j,s}, z_{j,s}. In (A1), we may assume that Imz_{j,s} ∈ [0, 2π) and z_{j_{1},s} ≠ z_{j_{2},s} whenever j_{1} ≠ j_{2}. If c_{j,s} = 0 for all j, s, then det T_{n}(a) = 0 for all n ≥ 1, which easily implies that all the matrices T_{n}(a) (n ≥ 1) are zero matrices. As the case where a vanishes identically is excluded, we see that not all the numbers c_{j,s} in (A1) are zero.

Let q := max Re z_{j,s} and rewrite (A1) in the form

det T_{n}(a) = e^{qn} ∑_{s=0}^{N} ∑_{j=1}^{M_{s}}(c_{j,s}e^{y_{j,s}n})n^{s} (A2)

with y_{j,s} := z_{j,s} − q. Clearly, Re y_{j,s} ≤ 0 for all j, s. There is a largest s_{0} ∈ {0, 1, …, N} such that Re y_{j,s_{0}} = 0 and c_{j,s_{0}} ≠ 0 for some j. Suppose

Re y_{j_{1},s_{0}} = … = Re y_{j_{m},s_{0}} = 0

and Re y_{j,s_{0}} < 0 for j ∈ {1, …, M_{s_{0}}} \ {j_{1}, …, j_{m}}. Letting

p(n) := ∑_{k=1}^{m} c_{j_{k},s_{0}}e^{y_{j_{k},s_{0}}n} =: ∑_{k=1}^{m} c_{j_{k},s_{0}}e^{ix_{k}n}

we obtain from (A2) that

det T_{n}(a) = e^{qn}n^{s_{0}} (p(n) + o(1)) as n → ∞. (A3)

Since c_{j_{k},s_{0}} ≠ 0 for some j_{k}, we deduce from Lemma A.4 that there are a δ > 0 and a sequence {n_{i}} of natural numbers such that n_{i} → ∞ and

|p(n_{i})| ≥ δ > 0 for all n_{i}. (A4)

Combining (A3) and (A4) we obtain that det T_{n_{j}}(a) ≠ 0 for all sufficiently large n_{i}.

References

[1] A. Böttcher: Status report on rationally generated block Toeplitz and Wiener-Hopf determinants. Preprint TU Chemnitz, 1990.

[2] A. Böttcher: Pseudospectra and singular values of large convolution operators. J. Integral Equations Appl. 6 (1994), 267–301.

[3] A. Böttcher: On the approximation numbers of large Toeplitz matrices. Documenta Mathematica 2 (1997), 1–31.

[4] A. Böttcher and B. Silbermann: Analysis of Toeplitz Operators. Akademie-Verlag, Berlin 1989 and Springer-Verlag, Berlin, Heidelberg, New York 1990.

[5] I. Gohberg and I.A. Feldman: Convolution Equations and Projection Methods for Their Solution. Amer. Math. Soc., Providence, R.I., 1974 [Russian original: Nauka, Moscow 1971; German transl.: Akademie-Verlag, Berlin 1974].

[6] M. Gorodetsky: Toeplitz determinants generated by rational functions. In: Integral and Differential Equations and Approximate solutions, pp. 49–54, Elista 1985 [Russian]

[7] S.M.Grudsky and A.V. Kozak: On the convergence speed of the norms of the inverses of truncated Toeplitz operators. In: Integro-Differential Eqs. Appl., pp. 45–55, Rostowon-Don Univ. Press 1995 [Russian].

[8] U. Grenander and G. Szegö: Toeplitz Forms and Their Applications. Univ. Calif. Press, Berkeley and Los Angeles 1958 [Russian transl.: Izd. Inostr. Lit., Moscow 1961].

[9] G. Heinig: Endliche Toeplitzmatrizen and zweidimensionale diskrete Wiener-Hopf-Operatoren mit homogenem Symbol. Math. Nachr. 82 (1978), 29–68.

[10] S.V. Konyagin et al.: Mathematics Olympiads Abroad (I.N. Sergeyev, e.d.). Nauka, Moscow 1987 [Russian].

[11] A.V. Kozak: On the reduction method for multidimensional discrete convolutions. Matem. Issled. 8 (1973). 157–160 [Russian].

[12] S. Prössdorf and B. Silbermann: Projektionsverfahren und die näherungsweise Lösung singulärer Gleichungen. Teubner-Verlag, Leipzig 1977.

[13] S. Roch and B. Silbermann: Index calculus for approximation methods and singular value decomposition. Preprint TU Chemnitz-Zwickau, 1996.

[14] S. Roch and B. Silbermann: A note on singular values of Cauchy-Toeplitz matrices. Preprint TU Chemnitz-Zwickau, 1996.

[15] B. Silbermann: On the limiting set of singular values of Toeplitz matrices. Linear Algebra Appl. 182 (1983), 35–43.

[16] W.F. Trench: Solution of systems with Toeplitz matrices generated by rational functions. Linear Algebra Appl. 74 (1986), 191–211.

[17] E.E. Tyrtyshnikov: Singular values of Cauchy-Toeplitz matrices. Linear Algebra Appl. 161 (1992), 99–116.

[18] E.E. Tyrtyshnikov: A unifying approach to some old and new theorems on distribution and clustering. Linear Algebra Appl. 232 (1996), 1–43.

[19] H. Widom: Toeplitz determinants with singular generating functions. Amer. J. Math. 95 (1973), 333–383.

Albrecht Böttcher Fakultät f. Mathematik TU Chemnitz-Zwickau D-09107 Chemnitz, Germany

aboettch@mathematik.tu-chemnitz.de Sergei M. Grudsky Faculty of Mechanics and Mathematics Rostov-on-Don State University Bolshaya Sadovaya 105 344 711 Rostov-on-Don, Russia

grudsk@ns.unird.ac.ru