SPECTRAL DISTRIBUTIONS AND ISOSPECTRAL SETS OF TRIDIAGONAL MATRICES

PETER C. GIBSON

Abstract. We analyze the correspondence between finite sequences of finitely supported probability distributions and finite-dimensional, real, symmetric, tridiagonal matrices. In particular, we give an intrinsic description of the topology induced on sequences of distributions by the usual Euclidean structure on matrices. Our results provide an analytical tool with which to study ensembles of tridiagonal matrices, important in certain inverse problems and integrable systems. As an application, we prove that the Euler characteristic of any generic isospectral set of symmetric, tridiagonal matrices is a tangent number.

Contents

1. Introduction 1 2. Sequences of distributions, direct sums of Jacobi matrices 2 2.1. Notation, basic facts, and definitions; Problem 1 2 2.2. Preliminary observations, further notation 8 2.3. A blow-up of the standard simplex 10 2.4. Stable sequences 13 2.5. Two technical lemmas 16 2.6. The flip transpose 20 2.7. The main result 22 2.8. The solution to Problem 1 24 3. Isospectral sets of tridiagonal matrices 25 3.1. Symmetric, tridiagonal matrices; Problem 2 26 3.2. The facial structure of B^{Λ} 26 3.3. Permutahedra 30 3.4. A polyhedral complex over T^{Λ} 32 3.5. Illustration of the results, Euler characteristics 34 References 36

1. Introduction

In this paper we analyze the correspondence between finite sequences of finitely supported probability distributions and finite-dimensional, real, symmetric, tridiagonal matrices. In particular, we give an intrinsic description of the topology induced on sequences of distributions by the usual Euclidean structure on matrices. Our results provide an analytical tool with which to study ensembles of tridiagonal matrices, which are important in a variety of contexts, including inverse problems [9] and integrable systems [1].

Research at MSRI was supported in part by NSF grant DMS-9810361. The author’s research is supported also by NSERC Postdoctoral Fellowship 231108-2000.

The paper is divided into two parts. In the first part, Section 2, we study the map f that takes the spectral distribution of a finite Jacobi matrix to that matrix. The open d-simplex S naturally represents probability distributions whose support is a fixed (d + 1)-element set Λ of reals, and it is well-known that f maps S homeomorphically onto the manifold M of Jacobi matrices having spectrum Λ. However, viewed as a map on the closed simplex \overline{S}, f has points of indeterminacy on the boundary ∂S. Our main result is the explicit construction of a blow-up (B, π) of \overline{S}, centred at ∂S, that eliminates the points of indeterminacy of f, establishing a homeomorphism h from B onto the closure of M.

The original motivation was to better understand geometrically solutions to certain ill-posed inverse problems concerning Jacobi matrices, specifically [8, Theorem 6.4] and [9, Theorem 2.3]. The essential question, Problem 1 on p.7, is to describe intrinsically the topology induced on sequences of distributions by their correspondence with direct sums of Jacobi matrices. A complete answer to the question is implicit in the blow-up (B, π) itself. As far as we know, these results are new; their application to inverse problems will appear in a future article.

The second part of the paper, Section 3, consists of an application of the first part to isospectral sets of real, symmetric, tridiagonal matrices. It turns out that B, although not convex, has a facial structure like that of a convex polytope. Based on this, we use the homeomorphism h : B → M to construct a family of polyhedral complexes \overline{P}_{d} that encode the topology of the isospectral sets in question. This enables us to prove that the Euler characteristic of a generic isospectral set of symmetric, tridiagonal matrices is a tangent number. From the point of view of discrete geometry, the complexes \overline{P}_{d} are remarkable in their own right. They have a simple description, yet exhibit exotic combinatorial properties.

The topology of isospectral sets of tridiagonal matrices has been considered independently, and much earlier, by Tomei, Nanda, Deift, Flaschka and others [10], [6], [7]. But whereas these authors make essential use of the Toda flow, our methods are more purely combinatorial. In place of a dynamical system, we exploit the abovementioned blow-up construction, which is completely explicit. Tomei also computed Euler characteristics, but does not seem to have noticed that hyperbolic tangent is a generating function for them. In any case, it is of interest to try to understand what connections exist between the two apparently different approaches.

Acknowledgement. Thanks both to Richard Cushman and Jürgen Bokowski for many helpful conversations at various points in the preparation of this article. Thanks also to Gunther Uhlmann and MSRI for the stimulating research environment of the MSRI semester in inverse problems, Fall 2001.

2. Sequences of distributions, direct sums of Jacobi matrices

Probability distributions proved useful in [9] for parametrizing solution sets of certain classes of inverse problems concerning finite Jacobi matrices, based on the well-known correspondence between distributions, orthogonal polynomials and Jacobi matrices—see [5]. In the present section, we study an extension of the standard correspondence, considering sequences of distributions and direct sums of Jacobi matrices in place of, respectively, distributions and Jacobi matrices. As will be explained in a future article, this extension gives a clearer geometric interpretation of the abovementioned solution sets.

In Sections 2.1 and 2.2 we assemble the standard facts, without proof, and establish the basic notation to be used throughout Section 2. A precise formulation of the main problem is given at the end of Section 2.1. With the exception of the formula cited in Proposition 14 of Section 2.6, the material in Sections 2.3-2.8 is new and so we give detailed proofs of all results.

2.1. Notation, basic facts, and definitions; Problem 1. We are interested in the correspondence between probability distributions on the real line and Jacobi matrices, restricted to the finite-dimensional setting. With respect to this correspondence, sequences of orthogonal polynomials play a useful auxiliary role.

Let J denote the set of finite-dimensional Jacobi matrices, that is, matrices of the form

(1)  J = ( \begin{matrix}a_{1} & a_{2} & 0 & ⋯ & 0 \\ a_{2} & a_{3} & a_{4} & ... & ⋮ \\ 0 & a_{4} & a_{5} & ... & 0 \\ ⋮ & ... & ... & ... & a_{2(d−1)} \\ 0 & ⋯ & 0 & a_{2(d−1)} & a_{2d−1} \end{matrix} ) ,

for some d ≥ 1, where each a_{n} ∈ R, and each a_{n} that has even index n is strictly positive. We label the entries of J as in (1) in order to suggest the map

(2)  J ↦ (a_{1}, a_{2}, …, a_{2d−1}),

whereby d × d Jacobi matrices correspond to points in R^{2d−1}.

Let D denote the set of finitely supported probability distributions on the real line. Elements of D are most simply represented by combinations of translates of the Dirac delta function, of the form

(3)  dα(λ) = ∑_{n=1}^{d} w_{n}δ(λ − λ_{n}),

where each λ_{n} ∈ R, each w_{n} > 0, and ∑_{n=1}^{d} w_{n} = 1. For technical reasons we shall adopt a slightly more cumbersome, equivalent representation, whereby the weights w_{n} in (3) function as homogeneous, rather than absolute, coordinates. More precisely, let D′ denote the set of distributions of the form (3), where each λ_{n}, w_{n} ∈ R and each w_{m}w_{n} > 0. For dα, dβ ∈ D′, write

dα ∼ dβ

if dα = rdβ for some non-zero r ∈ R. Then an element of D is represented by the equivalence class modulo ∼ of a distribution in D′, consisting of its scalar multiples. In symbols, D = D′/ ∼. Having established the precise meaning we will be less formal in practise; given dα ∈ D′, we will simply write dα ∈ D, letting the representative stand in for its class. The point of this notation is that we are free to rescale probability distributions without changing them.

Let MOP denote the set of finite sequences of monic, orthogonal polynomials. These are sequences of the form

(p_{0}, p_{1}, …, p_{d}),

where d ≥ 1 and each p_{n}(λ) ∈ R[λ] is monic of degree n, and for which there exists a probability distribution dα on R such that

⟨p_{n}, p_{n}⟩_{dα} = ∫_{−∞}^{∞} p_{n}^{2} dα > 0 for each n,
⟨p_{m}, p_{n}⟩_{dα} = ∫_{−∞}^{∞} p_{m}p_{n} dα = 0 if m ≠ n.

Each J ∈ J corresponds to a unique dα ∈ D, its spectral distribution function, as follows. Orthogonally diagonalize J as

J = OΛO^{T} ,

where OO^{T} = I and Λ = diag(λ_{1}, …, λ_{d}), and set

(4)  dα_{J}(λ) = ∑_{n=1}^{d} (O(1, n))^{2} δ(λ − λ_{n}),

where O(i, j) denotes the (i, j)-entry of the matrix O. This is the (normalized representor of the) spectral distribution of J in the sense that for any analytic function f,

f(J)(1, 1) = ∫_{−∞}^{∞} f dα_{J}.

An equivalent characterization is the formula

(5)  (zI − J)^{−1}(1, 1) = ∫_{−∞}^{∞} \frac{dα_{J}(λ)}{z − λ}.

The map J ↦ dα_{J} is a bijection from J onto D. Our main focus in the present paper is its inverse

f : D → J .

Here we define f explicitly, along with an auxiliary map

Ψ : D → MOP .

Definition 1. Let dα ∈ D be given, and write d = |supp dα|. Define

(6)  f(dα) = ( \begin{matrix}a_{1} & a_{2} & 0 & ⋯ & 0 \\ a_{2} & a_{3} & a_{4} & ... & ⋮ \\ 0 & a_{4} & a_{5} & ... & 0 \\ ⋮ & ... & ... & ... & a_{2(d−1)} \\ 0 & ⋯ & 0 & a_{2(d−1)} & a_{2d−1} \end{matrix} ) ,

(7)  Ψ(dα) = (p_{0}, p_{1}, …, p_{d}),

where the sequences (a_{1}, …, a_{2d−1}) and (p_{0}, …, p_{d}) are constructed recursively as follows. \underline{Initial step} For the purpose of notation set a_{0} = 0. Set

p_{0}(λ) = 1, a_{1} = \frac{⟨1, λ⟩_{dα}}{⟨1, 1⟩_{dα}} , p_{1}(λ) = λ − a_{1}.

\underline{Continuing step} Given a_{2n−2}, a_{2n−1} and p_{n−1}, p_{n}, for n in the range 1 ≤ n ≤ d − 1, set

(8)  a_{2n} = \sqrt{\frac{⟨p_{n}, p_{n}⟩_{dα}}{⟨p_{n−1}, p_{n−1}⟩_{dα}}} ,

(9)  a_{2n+1} = \frac{⟨p_{n}, λp_{n}⟩_{dα}}{⟨p_{n}, p_{n}⟩_{dα}} ,
(10)  p_{n+1}(λ) = (λ − a_{2n+1})p_{n}(λ) − a_{2n}^{2} p_{n−1}(λ).

The sequence of polynomials Ψ(dα) has a direct relationship to the matrix J = f(dα), namely, p_{n} = Ψ_{n}(dα) is the characteristic polynomial of the leading n × n submatrix of J; in particular, p_{d} is the characteristic polynomial of J. (This fact will be needed in technical arguments later on.) Also, the truncated sequence (p_{0}, …, p_{d−1}) is orthogonal with respect to the starting distribution dα, but

∫_{−∞}^{∞} p_{d}^{2} dα = 0

is degenerate. Indeed supp dα is the set of roots of p_{d}. If one extends J to a (d + 1) × (d + 1) matrix J′ by choosing arbitrary entries a_{2d}, a_{2d+1}, then the full sequence (p_{0}, …, p_{d}) is orthogonal with respect to the spectral distribution dα_{J′} of J′. We index the components f_{n} of f according to the sequence (a_{1}, …, a_{2d−1}), so that

a_{n} = f_{n}(dα).

Let us consider a fixed d = |supp dα|, and write

dα(λ) = ∑_{n=1}^{d} w_{n}δ(λ − λ_{n}).

Observe that, according to Definition 1, for 1 ≤ n ≤ d − 1, • f_{2n}^{2} and f_{2n+1} are rational functions in the variables w_{1}, …, w_{d}, λ_{1}, …, λ_{d};

• f_{2n}^{2} and f_{2n+1} are homogeneous functions of degree 0 in the variables w_{1}, …, w_{d}.

Now, f itself is not rational, because of the square root (8). We have chosen the positive square root, and in some sense this choice is artificial. It is more natural to allow both square roots, and thus to make f a multi-valued function (precisely, a 2^{d−1}-valued function for fixed d = |supp dα|). This point of view is developed fully in Section 3; for now we leave f as single-valued.

Having determined the nature of the functions f_{n} in terms of the weights w_{n}, let us briefly consider the reverse question, restricted to to matrices J having a prescribed set {λ_{1}, …, λ_{d}} of eigenvalues. To that end, let

(11)  ∑_{n=1}^{d} w_{n}δ(λ − λ_{n}) = dα_{J}

denote the normalized spectral distribution of J, as defined in (4). Then the normalized weights w_{n} are polynomials in the entries a_{1}, …, a_{2d−1} of J, a fact easily inferred from (5), as follows. Let J^{11} denote the submatrix of J obtained by deleting the first row and column, and let

p_{d}(λ) = ∏_{n=1}^{d}(λ − λ_{n})

be the characteristic polynomial of J. Then the left-hand side of (5) has the form

det(zI − J^{11})/p_{d}(z),

while the right-hand side of (5), expressed in terms of (11), is the partial fraction decomposition

∑_{n=1}^{d} \frac{w_{n}}{z − λ_{n}} .

Comparing these two expressions yields

w_{n} = det(λ_{n}I − J^{11})/p′_{d}(λ_{n}),

which, for fixed λ_{1}, …, λ_{d}, is a polynomial in the entries of J.

The set of d × d symmetric, tridiagonal matrices is a subspace of R^{d^{2}}, isomorphic (indeed isometric) to R^{2d−1} by the map (2). With this isometry in mind, we will usually write J ∈ R^{2d−1} when J is a d × d symmetric, tridiagonal matrix. Now, because J ∩R^{2d−1} is not closed, it is useful to consider the extended class of matrices

\overline{J} = ⋃_{d≥1} cl(J ∩ R^{2d−1}).

\overline{J} consists of direct sums

J = J_{1} ⊕ ⋯ ⊕ J_{r}

of Jacobi matrices J_{1}, …, J_{r} ∈ J, where r ≥ 1. By analogy we extend D to the class \overline{D} consisting of all sequences

dα_{1} ⊕ ⋯ ⊕ dα_{r}

of distributions dα_{1}, …, dα_{r} ∈ D, where r ≥ 1. (We could alternatively write (dα_{1}, …, dα_{r}) for a sequence of distributions; the symbol ⊕ just serves to emphasize the connection with matrices.) The map

f : D → J

extends to a map

\overline{f} : \overline{D} → \overline{J}

in the obvious way, namely, by defining

\overline{f}(dα_{1} ⊕ ⋯ ⊕ dα_{r}) = f(dα_{1}) ⊕ ⋯ ⊕ f(dα_{r}).

Note that, by its very definition, \overline{f} is a bijection.

For each d ≥ 1, \overline{J} ∩ R^{2d−1} inherits the Euclidean structure of R^{2d−1}. But it is unclear a priori what it should mean for two points,

dα_{1} ⊕ ⋯ ⊕ dα_{r}, dβ_{1} ⊕ ⋯ ⊕ dβ_{s},

in \overline{D} to be “close”. Thus, roughly speaking, a basic problem is to describe intrinsically the topology which \overline{D} acquires from \overline{J} via \overline{f}. We make this more specific as follows. Fix a d-element set Λ ⊂ R. Denote by \overline{J}^{Λ} the set of d × d matrices J ∈ \overline{J} having spectrum Λ,

\overline{J}^{Λ} = \{J ∈ \overline{J} | J ∈ R^{2d−1} and spec J = Λ\} .

Write \overline{D}^{Λ} to denote the corresponding set of sequences of distributions, that is, sequences

dα_{1} ⊕ ⋯ ⊕ dα_{r} ∈ \overline{D}

such that 1 ≤ r ≤ d,

(12)  ∑_{n=1}^{r} |supp dα_{n}| = d and ⋃_{n=1}^{r} supp dα_{n} = Λ.

With this notation, the restriction of \overline{f},

\overline{f} : \overline{D}^{Λ} → \overline{J}^{Λ},

is a bijection.

Problem 1 Describe intrinsically the topology which \overline{J}^{Λ} induces on \overline{D}^{Λ} via \overline{f}. That is, characterize convergent sequences of points in \overline{D}^{Λ}, and show how to compute limits of such sequences without evaluating \overline{f}.

We illustrate Problem 1 with a simple example. Let dα_{0}, dα_{1} ∈ D denote the distributions

dα_{0}(λ) = δ(λ),
dα_{1}(λ) = δ(λ − 1) + δ(λ − 2),

and consider the limit

L = \overline{f}^{−1} ( lim_{t→0^{+}} f(dα_{0} + t dα_{1})) .

Given that the limit exists, what is L? A naive guess might be L = dα_{0} ⊕ dα_{1}, but this is wrong, as can be verified numerically by coding the recursive definition of f (in, say, Matlab) and then computing f(dα_{0} + tdα_{t}) for decreasing values of t. In fact, L = dα_{0} ⊕ dα′_{1}, where

dα′_{1}(λ) = δ(λ − 1) + 4δ(λ − 2)
= λ^{2}dα_{1}(λ).

In other words, for Λ = {0, 1, 2}, the curve dβ_{t} = dα_{0}+tdα_{1} (or equivalently, sequence, if we set t = 1/n, n ∈ Z^{+}) converges in \overline{D}^{Λ}, with respect to the topology induced by \overline{f}, to dα_{0} ⊕ λ^{2} dα_{1}. And although dβ_{t} ∈ D for every t > 0, its limiting value as t → 0^{+} is not in D. Rather, dβ_{t} “splits” in the limit into a pair of smaller distributions. Problem 1 calls, in part, for a full description of this phenomenon.

2.2. Preliminary observations, further notation. Let Λ ⊂ R be a d-element set, for some d ≥ 1, to be held fixed throughout the present section. As a first step toward solving Problem 1, we note that \overline{D}^{Λ} is a disjoint union of open discs of various dimensions. The essence of Problem 1 then consists in describing how these component discs fit together.

The notion of an ordered partition is useful for present considerations. Given a set S, a sequence

(S_{1}, …, S_{r})

of sets is an ordered partition of S if: each S_{n} is non-empty; S_{m} ∩ S_{n} = ∅ whenever m ≠ n; and ⋃_{n=1}^{r} S_{n} = S. Denote the set of ordered partitions of S by P_{S}. The condition (12) for dα_{1} ⊕ ⋯ ⊕ dα_{r} to belong to \overline{D}^{Λ} is precisely that

(supp dα_{1}, …, supp dα_{r})

be an ordered partition of Λ. And for each ordered partition (S_{1}, …, S_{r}) ∈ P_{Λ}, there corresponds a piece of \overline{D}^{Λ},

(13)  \{dα_{1} ⊕ ⋯ ⊕ dα_{r} ∈ \overline{D} | (supp dα_{1}, …, supp dα_{r}) = (S_{1}, …, S_{r})\} ,

which is isomorphic to an open disc of dimension

∑_{n=1}^{r} |S_{n}| − 1 = d − r.

A member of (13) has the form

(14)  dα_{1} ⊕ ⋯ ⊕ dα_{r} = ∑_{λ_{n}∈S_{1}} w_{n}δ(λ − λ_{n}) ⊕ ⋯ ⊕ ∑_{λ_{n}∈S_{r}} w_{n}δ(λ − λ_{n}),

the weights w_{n} of which serve as coordinates on (13). Indeed the notation is simplest if we fix an indexing of Λ,

Λ = {λ_{1}, …, λ_{d}},

and then work with partitions of

[d] = {1, …, d}

rather than of Λ. We set up notation for our coordinate space as follows. Given a non-empty set S ⊆ [d], we write W^{S} for the projective space

W^{S} = {w : S → R | supp w ≠ ∅}/ ∼,

where w ∼ w′ if w = rw′ for some non-zero r ∈ R. Thus W^{S} consists of sequences indexed by S, distinguished up to proportionality, and is isomorphic to RP^{|S|−1}. It is important to distinguish W^{S} from W^{S′} whenever S ≠ S′. When it is desirable to emphasize the domain of w : S → R, we append it as a superscript, writing w^{S}. As usual, we write w_{n}, or w_{n}^{S}, to denote the value of w at n ∈ S. We will always use homogeneous coordinates on W^{S}, treating w ∈ W^{S} as a particular map w : S → R, and letting the equivalence relation ∼ be understood. We write W_{+}^{S} for the open subset of W^{S} defined by

W_{+}^{S} = {w : S → R | w_{m}w_{n} > 0 ∀m, n ∈ S } .

Referring to (13), let (S′_{1}, …, S′_{r}) ∈ P_{[d]} be the partition corresponding to (S_{1}, …, S_{r}) ∈ P_{Λ}, so that for each n,

S′_{n} = {i ∈ [d] | λ_{i} ∈ S_{n} } .

Then the weights w_{n} in (14) belong to the coordinate patch

(15)  W_{+}^{(S′_{1},...,S′_{r})} = W_{+}^{S′_{1}} ⊕ ⋯ ⊕ W_{+}^{S′_{r}},

and we may identify (13) with W_{+}^{(S′_{1},...,S′_{r})}. We denote an element

w^{S_{1}} ⊕ ⋯ ⊕ w^{S_{r}} ∈ W_{+}^{(S_{1},...,S_{r})},

using the abbreviated notation

w^{(S_{1},...,S_{r})} = w^{S_{1}} ⊕ ⋯ ⊕ w^{S_{r}}.

Now, W_{+}^{(S′_{1},...,S′_{r})} is a direct product of open subsets of finite-dimensional projective space, and carries its own topology. By the natural topology of (13), we mean the topology of this direct product. We identify \overline{D}^{Λ} with the union of coordinate patches (15), indexed by partitions of [d],

\overline{D}^{Λ} = ⋃_{(S_{1},...,S_{r})∈P_{[d]}} W_{+}^{(S_{1},...,S_{r})},

and use the obvious notation for the function \overline{f} : \overline{D}^{Λ} → \overline{J}^{Λ}. Namely, for w^{S} ∈ W_{+}^{S}, f(w^{S}) denotes

f (∑_{n∈S} w_{n}^{S}δ(λ − λ_{n})) ,

and, given a point w^{(S_{1},...,S_{r})} ∈ W_{+}^{(S_{1},...,S_{r})}, we write

\overline{f}(w^{(S_{1},...,S_{r})}) = f(w^{S_{1}}) ⊕ ⋯ ⊕ f(w^{S_{r}}).

It is easy to see that the topology on \overline{D}^{Λ} induced by \overline{f}, restricted to a given piece W_{+}^{(S_{1},...,S_{r})}, agrees with the natural topology. The restriction to W_{+}^{(S_{1},...,S_{r})} of each component \overline{f}_{n} of \overline{f} is either a rational function without singularities, or the square root of such a function, and the components w_{n} of the normalized representor of the of the restriction of \overline{f}^{−1} to \overline{f}(W_{+}^{(S_{1},...,S_{r})}) are polynomials in the matrix entries a_{1}, …, a_{2d−1}. Therefore the restriction to W_{+}^{(S_{1},...,S_{r})} of \overline{f} is a homeomorphism. But there is no natural topology on \overline{D}^{Λ} as a whole; we need to analyze \overline{f} directly to determine how its pieces fit together in the induced topology. Note that \overline{D}^{Λ} has a single piece, W_{+}^{[d]}, of maximum dimension d − 1, corresponding to the trivial ordered partition ([d]) ∈ P_{[d]}. We refer to W_{+}^{[d]} as the principal component of \overline{D}^{Λ}. It turns out that the induced structure of \overline{D}^{Λ} is determined by sequences, or curves, in the principal component which tend to the boundary of W_{+}^{[d]} in W^{[d]}. In fact it is enough just to consider moment curves in W_{+}^{[d]} tending to the boundary. Note that W_{+}^{[d]} may be thought of as the standard, open, (d − 1)-dimensional simplex, as each point in W_{+}^{[d]} has a unique representative w satisfying ∑_{n=1}^{d} w_{n} = 1, with each w_{n} > 0.

2.3. A blow-up of the standard simplex. Given a d-element set

Λ = {λ_{1}, …, λ_{d}} ⊂ R,

we construct a pair (B^{Λ}, π), consisting of a semi-algebraic set B^{Λ} and a bijective map

π : B^{Λ} → \overline{D}^{Λ}.

The set B^{Λ} is defined in a relatively high-dimensional projective space W by quadratic equations and inequalities. The W-structure of B^{Λ} encodes the topology on \overline{D}^{Λ} induced by \overline{f} in that the map

\overline{f} ∘ π : B^{Λ} → \overline{J}^{Λ}

is a homeomorphism. (This latter fact will be proved in Section 2.7.) The pair (B^{Λ}, π) is a blow-up of W_{+}^{(S_{1},...,S_{r})} ⊂ \overline{D}^{Λ} with centre

D^{(S_{1},...,S_{r})} = the boundary of W_{+}^{(S_{1},...,S_{r})} in W^{(S_{1},...,S_{r})},

for every ordered partition (S_{1}, …, S_{r}) ∈ P_{[d]}, in the sense that there is a coordinate projection π^{(S_{1},...,S_{r})} on W such that:

• π^{(S_{1},...,S_{r})}(B^{Λ}) = W_{+}^{(S_{1},...,S_{r})} ∪ D^{(S_{1},...,S_{r})};

• the restriction of π to π^{−1}(W_{+}^{(S_{1},...,S_{r})}) coincides with π^{(S_{1},...,S_{r})}.

In particular, (B^{Λ}, π) is a blow-up of the standard simplex W_{+}^{[d]} ⊂ \overline{D}^{Λ}.

We now describe (B^{Λ}, π) in detail. B^{Λ} is contained in the ambient space

W = ∏_{∅≠S⊆[d]} W^{S}.

The dimension of W is easily computed to be (d − 2)2^{d−1} + 1. Given w ∈ W, we write w^{S} for its coordinate projection onto the factor W^{S}, and w_{n}^{S} for the entry of w^{S} corresponding to n ∈ S. Note that, as established earlier, these are homogeneous coordinates. The equations defining B^{Λ} involve the following scalars whose provenance we shall explain later, in Section 2.6. For each non-empty S ⊆ [d] and each i ∈ [d], set

C_{i}^{S} = ∏_{n∈S}(λ_{n} − λ_{i})^{2} and C_{i}^{∅} = 1.

Definition 2. Let B^{Λ} denote the semi-algebraic subset of W consisting of points w which satisfy the equations and inequalities

(16)  C_{i}^{S−R}w_{j}^{R}w_{i}^{S} = C_{j}^{S−R}w_{i}^{R}w_{j}^{S} ∀R ⊆ S ⊆ [d], i, j ∈ R
(17)  w_{i}^{S}w_{j}^{S} ≥ 0  ∀S ⊆ [d], i, j ∈ S.

We need some technical preparation in order to define the map π : B^{Λ} → \overline{D}^{Λ}. Here it will be useful to consider the collection L_{[d]} of subsets of [d], partially ordered by the inclusion relation ⊆; we make use of a correspondence between totally ordered sets, or chains, in L_{[d]} having maximum element [d], and ordered partitions of [d]. Let w ∈ B^{Λ}, S ⊆ [d], n ∈ S, and write P (S, n; w) for the statement

w_{n}^{S} ≠ 0 and ∀T ⊆ [d], w_{n}^{T} ≠ 0 ⇒ |T | ≤ |S|.

Lemma 3. If P (R, m; w) and P (S, n; w) then either R ⊆ S or S ⊆ R.

Proof. Set T = R ∪ S and choose i ∈ T such that w_{i}^{T} ≠ 0. (Such an i exists because w_{n}^{T} are homogeneous coordinates for the projective space W^{T}.) If i ∈ R, then C_{i}^{T −R}w_{m}^{R}w_{i}^{T} ≠ 0, so by equation (16), C_{m}^{T −R}w_{i}^{R}w_{m}^{T} ≠ 0, which implies w_{m}^{T} ≠ 0. Therefore, since P (R, m; w), |T | ≤ |R|, forcing T = R, or equivalently, S ⊆ R. Similarly, if i ∈ S, then P (S, n; w) and equation (16) force R ⊆ S.

It follows from Lemma 3 that for each n ∈ [d] there is a unique S ⊆ [d] such that P (S, n; w), so that we may define

φ_{w} : [d] → L_{[d]}

by setting

φ_{w}(n) = the unique S ⊆ [d] such that P (S, n; w).

Note that [d] itself is in the range of φ_{w}, since necessarily w_{i}^{[d]} ≠ 0, for some i, whence P ([d], i; w) automatically holds. Moreover, again by Lemma 3, the range {K_{1}, …, K_{r}} ⊆ L_{[d]} of φ_{w} is totally ordered; i.e., for an appropriate relabeling it is a chain of the form

(18)  [d] = K_{1} ⊃ ⋯ ⊃ K_{r} ≠ ∅,

for some r ≥ 1. We are now in a position to define the map π, but first we state another technical fact, for the sake of future reference.

Lemma 4. Let {K_{1}, …, K_{r}} ⊂ L_{[d]} be the range of φ_{w}, labeled so that (18) holds, and let (S_{1}, …, S_{r}) ∈ P_{[d]} be the corresponding ordered partition, defined by

(S_{1}, …, S_{r}) = (K_{1} − K_{2}, …, K_{r−1} − K_{r}, K_{r}).

Then for each n, 1 ≤ n ≤ r,

φ_{w}^{−1}(K_{n}) = S_{n}.

Proof. We claim that for each i ∈ [d], φ_{w}(i) is the smallest set K_{n} containing i, a fact which implies the lemma. To prove the claim, suppose i ∈ K_{m} ⊆ K_{n} and φ_{w}(i) = K_{n}, and choose j ∈ [d] such that φ_{w}(j) = K_{m}; necessarily j ∈ K_{m}. Then

C_{i}^{K_{n}−K_{m}}w_{j}^{K_{m}}w_{i}^{K_{n}} ≠ 0,

so by equation (16),

C_{j}^{K_{n}−K_{m}}w_{i}^{K_{m}}w_{j}^{K_{n}} ≠ 0,

forcing w_{j}^{K_{n}} ≠ 0. But this implies |K_{n}| ≤ |K_{m}|, since by assumption P (K_{m}, j; w) holds, forcing K_{n} = K_{m}. The claim follows.

We define π : B^{Λ} → \overline{D}^{Λ} as follows.

Definition 5. Let w ∈ B^{Λ}, let {K_{1}, …, K_{r}} denote the range of φ_{w}, indexed such that (18) holds, and let

(S_{1}, …, S_{r}) = (K_{1} − K_{2}, …, K_{r−1} − K_{r}, K_{r}) ∈ P_{[d]}

be the corresponding ordered partition. Set

π(w) = (w_{n}^{K_{1}})_{n∈S_{1}} ⊕ ⋯ ⊕ (w_{n}^{K_{r}})_{n∈S_{r}} ∈ W_{+}^{(S_{1},...,S_{r})}.

Note that the inequalities (17) in the definition of B^{Λ} guarantee that π(w) is in W_{+}^{(S_{1},...,S_{r})} and not just in W^{(S_{1},...,S_{r})}. Furthermore, because (S_{1}, …, S_{r}) determines the corresponding chain K_{1} ⊃ ⋯ ⊃ K_{r} via

K_{n} = S_{n} ∪ S_{n+1} ∪ … ∪ S_{r},

the restriction of π to π^{−1}(W_{+}^{(S_{1},...,S_{r})}) is a coordinate projection. Next we define a map ρ : \overline{D}^{Λ} → B^{Λ}, which will turn out to be the inverse of π.

Definition 6. Let w^{(S_{1},...,S_{r})} ∈ \overline{D}^{Λ}, and let \{K_{1}, …, K_{r}\} be the corresponding chain in L_{[d]}, defined by

K_{n} = S_{n} ∪ S_{n+1} ∪ ⋯ ∪ S_{r}

for each n, 1 ≤ n ≤ r. Set

ρ(w^{(S_{1},...,S_{r})}) = w̃,

where w̃ ∈ W is defined in terms of its components w̃^{S} as follows. Given S ⊆ [d], choose K_{i} ⊇ S to be the smallest member of the above chain that includes S, and set

(19)  w̃_{n}^{S} = \{ \begin{matrix}C_{n}^{K_{i}−S}w_{n}^{S_{i}} & if n ∈ S_{i} \\ 0 & if n ∉ S_{i} \end{matrix} .

To verify that w̃ = ρ(w^{(S_{1},...,S_{r})}) ∈ B^{Λ}, we check that equations (16) and inequalities (17) of Definition 2 are satisfied. Indeed w̃ satisfies the inequalities (17) by (19) and the definition of W_{+}^{(S_{1},...,S_{r})}. To see that w̃ satisfies equations (16), let R ⊆ S ⊆ [d] with i, j ∈ R. Let K_{m} ⊇ R be the smallest set in {K_{1}, …, K_{r}} that includes R, and let K_{n} ⊇ S be the smallest that includes S; thus K_{m} ⊆ K_{n}. Applying Definition 6, the left-hand side of (16) works out to be

C_{i}^{S−R}w̃_{j}^{R}w̃_{i}^{S} = \{ \begin{matrix}C_{i}^{S−R}(C_{j}^{K_{m}−R}w_{j}^{S_{m}})(C_{i}^{K_{n}−S}w_{i}^{S_{n}}) & if j ∈ S_{m} and i ∈ S_{n} \\ 0 & otherwise \end{matrix}
(20)  = \{ \begin{matrix}C_{j}^{K_{m}−R}C_{i}^{K_{n}−R}w_{j}^{S_{m}}w_{i}^{S_{n}} & if j ∈ S_{m} and i ∈ S_{n} \\ 0 & otherwise \end{matrix} ,

the latter equality since C_{i}^{K_{n}−S}C_{i}^{S−R} = C_{i}^{K_{n}−R}. The right-hand side of (16) is

C_{j}^{S−R}w̃_{i}^{R}w̃_{j}^{S} = \{ \begin{matrix}C_{j}^{S−R}(C_{i}^{K_{m}−R}w_{i}^{S_{m}})(C_{j}^{K_{n}−S}w_{j}^{S_{n}}) & if i ∈ S_{m} and j ∈ S_{n} \\ 0 & otherwise \end{matrix}
(21)  = \{ \begin{matrix}C_{j}^{K_{n}−R}C_{i}^{K_{m}−R}w_{i}^{S_{m}}w_{j}^{S_{n}} & if i ∈ S_{m} and j ∈ S_{n} \\ 0 & otherwise \end{matrix} ,

since C_{j}^{K_{n}−S}C_{j}^{S−R} = C_{j}^{K_{n}−R}. Now, if m ≠ n, then S_{n} ⊆ K_{n} − K_{m}, and therefore, since i, j ∈ R ⊆ K_{m}, neither i nor j belongs to S_{n} and consequently both (20) and (21) are 0. On the other hand, if m = n, then (20) and (21) are precisely the same. So equations (16) are satisfied in any case, confirming that ρ(w^{(S_{1},...,S_{r})}) ∈ B^{Λ}.

Proposition 7. The maps ρ and π are inverses, that is, ρ∘π = 1_{B^{Λ}} and π ∘ρ = 1\overline{D}^{Λ}.

Proof. (π ∘ρ = 1\overline{D}^{Λ}.) Let w^{(S_{1},...,S_{r})} ∈ \overline{D}^{Λ} and set w̃ = ρ(w^{(S_{1},...,S_{r})}); we need to check that π(w̃) = w^{(S_{1},...,S_{r})}. It follows directly from (19) that for n ∈ S_{i},

φw̃(n) = K_{i} = S_{i} ∪ S_{i+1} ∪ … ∪ S_{r}.

Then, by Definition 5,

π(w̃) = (w̃_{n}^{K_{1}})_{n∈S_{1}} ⊕ ⋯ ⊕ (w̃_{n}^{K_{r}})_{n∈S_{r}},

where, again by (19), w̃_{n}^{K_{i}} = C_{n}^{K_{i}−K_{i}}w_{n}^{S_{i}} = w_{n}^{S_{i}}, so that π(w̃) = w^{(S_{1},...,S_{r})}.

(ρ ∘ π = 1_{B^{Λ}}.) Let w̃ ∈ B^{Λ} and let w^{(S_{1},...,S_{r})} = π(w̃) be its image by π, so that w_{n}^{S_{j}} = w̃_{n}^{K_{j}}, where K_{j} = S_{j} ∪ S_{j+1} ∪ … ∪ S_{r}. In order to verify that ρ(w^{(S_{1},...,S_{r})}) = w̃, fix S ⊆ [d], and, following Definition 6, choose

K_{i} = S_{i} ∪ S_{i+1} ∪ … ∪ S_{r} ⊇ S

to be the smallest such set that includes S, so that S ∩ S_{i} ≠ ∅. Then

ρ(w^{(S_{1},...,S_{r})})_{n}^{S} = \{ \begin{matrix}C_{n}^{K_{i}−S}w_{n}^{S_{i}} & if n ∈ S_{i} \\ 0 & if n ∉ S_{i} \end{matrix}
(22)  = \{ \begin{matrix}C_{n}^{K_{i}−S}w̃_{n}^{K_{i}} & if n ∈ S_{i} \\ 0 & if n ∉ S_{i} \end{matrix} .

For comparison, fix m ∈ S ∩ S_{i}, and compute w̃_{n}^{S} using equation (16):

C_{m}^{K_{i}−S}w̃_{n}^{S}w̃_{m}^{K_{i}} = C_{n}^{K_{i}−S}w̃_{m}^{S}w̃_{n}^{K_{i}}
(23)  ⇒ w̃_{n}^{S} = (\frac{w̃_{m}^{S}}{C_{m}^{K_{i}−S}w̃_{m}^{K_{i}}} ) C_{n}^{K_{i}−S}w̃_{n}^{K_{i}}.

We will verify that the representations (22) and (23) are proportional, which implies that ρ(w^{(S_{1},...,S_{r})})^{S} = w̃^{S}, as desired. By Lemma 4, if n ∉ S_{i}, that is, if n ∈ S_{i+1} ∪ … ∪ S_{r}, then

φw̃(n) ∈ {K_{i+1}, …, K_{r}}

and consequently w̃_{n}^{K_{i}} = 0. On the other hand, if n ∈ S_{i}, then φw̃(n) = K_{i} and w̃_{n}^{K_{i}} ≠ 0; in particular, w̃_{m}^{K_{i}} ≠ 0. The coefficient w̃_{m}^{S}/(C_{m}^{K_{i}−S}w̃_{m}^{K_{i}}) in (23) is independent of n ∈ S, and non-zero since by definition w̃^{S} has at least one non-zero entry, therefore (22) and (23) are proportional.

2.4. Stable sequences. We focus our analysis of \overline{f} : \overline{D}^{Λ} → \overline{J}^{Λ} mainly on its values at sequences in W_{+}^{[d]}, the principal component of \overline{D}^{Λ}, that tend to the boundary of W_{+}^{[d]} in W^{[d]}. The blow-up (B^{Λ}, π) of W_{+}^{[d]} has a central place in this analysis; indeed, as mentioned earlier, we are working toward a proof that

\overline{f} ∘ π : B^{Λ} → \overline{J}^{Λ}

is a homeomorphism. We keep the notation ρ = π^{−1}, consistent with Definition 6 and Proposition 7. Let B_{∘}^{Λ} denote the piece of B^{Λ} corresponding to W_{+}^{[d]}, that is,

B_{∘}^{Λ} = ρ(W_{+}^{[d]}).

Note that B_{∘}^{Λ} is characterized as the collection of points w ∈ B^{Λ} for which each entry w_{n}^{S}, n ∈ S ⊆ [d], is non-zero. For w ∈ B_{∘}^{Λ} the range of φ_{w} is the singleton set {[d]}. The restriction of π to B_{∘}^{Λ} coincides with projection of w onto the coordinates w^{[d]}, and is a homeomorphism with respect to the natural topology of W_{+}^{[d]}.

Definition 8. Call a sequence w(n) ∈ W_{+}^{[d]}, n ∈ Z^{+}, stable if the corresponding sequence ρ(w(n)) ∈ B_{∘}^{Λ} is convergent in W (equivalently, in B^{Λ}).

By Definition 6, convergence of ρ(w(n)) in W amounts to the simultaneous convergence of the sequences

(C_{i}^{[d]−S}w(n)_{i})_{i∈S} in W^{S},

for each non-empty S ⊆ [d]. Since the constants C_{i}^{[d]−S} (i ∈ S) are strictly positive, this is equivalent to the simultaneous convergence of

(w(n)_{i})_{i∈S} in W^{S}.

Thus we have the following characterization. A sequence w(n) ∈ W_{+}^{[d]} is stable if and only if, for every i, j ∈ [d], there exists L_{ij} ∈ R^{+} ∪ {0, ∞} such that

\frac{w(n)_{i}}{w(n)_{j}} → L_{ij} as n → ∞.

The L_{ij} determine an ordered partition (S_{1}, …, S_{r}) ∈ P_{[d]}, where cells of the partition are defined by the equivalence relation

i ∼ j ⇔ 0 < L_{ij} < ∞,

and the ordering of the cells S_{m} < S_{n} is determined by

i ∈ S_{m}, j ∈ S_{n} ⇒ L_{ij} = ∞ (equivalently L_{ji} = 0).

We call (S_{1}, …, S_{r}) the limiting partition of the stable sequence w(n) ∈ W_{+}^{[d]}; it is also characterized by the fact that

π ( lim_{n→∞} ρ(w(n))) ∈ W_{+}^{(S_{1},...,S_{r})}.

Let us use the notation

⨁_{(S_{1},...,S_{r})}w^{S_{i}} = w^{S_{1}} ⊕ ⋯ ⊕ w^{S_{r}}

for w^{S_{1}} ⊕ ⋯ ⊕ w^{S_{r}} ∈ W^{(S_{1},...,S_{r})}. Given a stable sequence w(n) in W_{+}^{[d]} with limiting distribution (S_{1}, …, S_{r}), we calculate

π ( lim_{n→∞} ρ(w(n)))

as follows. As usual, for each i, 1 ≤ i ≤ r, set

K_{i} = S_{i} ∪ S_{i+1} ∪ … S_{r}.

By Definition 5, the restriction of π to ρ (W_{+}^{(S_{1},...,S_{r})}) coincides with a coordinate

projection on W, call it π^{(S_{1},...,S_{r})}. Then

π ( lim_{n→∞} ρ(w(n))) = π^{(S_{1},...,S_{r})} ( lim_{n→∞} ρ(w(n)))
= lim_{n→∞} π^{(S_{1},...,S_{r})}(ρ(w(n)))
= lim_{n→∞} ⨁_{(S_{1},...,S_{r})}(ρ(w(n))_{j}^{K_{i}})_{j∈S_{i}}

= lim_{n→∞} ⨁_{(S_{1},...,S_{r})}(C_{j}^{[d]−K_{i}}w(n)_{j})_{j∈S_{i}}

(24)  = ⨁_{(S_{1},...,S_{r})}lim_{n→∞} (C_{j}^{[d]−K_{i}}w(n)_{j})_{j∈S_{i}} .

Returning to distributional notation, write

dα_{i}(n) = ∑_{j∈S_{i}} w(n)_{j} δ(λ − λ_{j}),

so that supp dα_{i}(n) is indexed by S_{i}, and let

p_{dα_{i}}(λ) = ∏_{j∈S_{i}}(λ − λ_{j})

denote the characteristic polynomial of f(dα_{i}(n)), which does not depend on n. The assumption that w(n) is stable guarantees that each

d\overline{α}_{i} = lim_{n→∞} dα_{i}(n)

exists and has support indexed by S_{i}. Rewriting (24), we have

(25) π ( lim_{n→∞} ρ(dα_{1}(n) + … + dα_{r}(n))) = d\overline{α}_{1} ⊕ p_{dα_{1}}^{2} d\overline{α}_{2} ⊕ ⋯ ⊕ p_{dα_{1}+...+dα_{r−1}}^{2} d\overline{α}_{r}.

Now, the sequence

(26)  dα(n) = d\overline{α}_{1} + n^{−1} d\overline{α}_{2} + … + n^{−r+1} d\overline{α}_{r}

is stable, has limiting distribution (S_{1}, …, S_{r}), and ρ(dα(n)) converges to the image of (25) by ρ. Replacing n^{−1} in (26) with the continuous variable t, 0 < t < 1, yields the following.

Proposition 9. For every stable sequence w(n) in W_{+}^{[d]} there exists a corresponding moment curve in W_{+}^{[d]} of the form

dα(t) = dα_{1} + t dα_{2} + … + t^{r−1} dα_{r}, 0 < t < 1,

where (supp dα_{1}, …, supp dα_{r}) ∈ P_{Λ}, such that

π ( lim_{n→∞} ρ(w(n))) = π ( lim_{t→0^{+}} ρ(dα(t)))
= dα_{1} ⊕ p_{dα_{1}}^{2} dα_{2} ⊕ ⋯ ⊕ p_{dα_{1}+...+dα_{r−1}}^{2} dα_{r}.

Thus in order to study the way the pieces of \overline{D}^{Λ} are embedded in B^{Λ} by ρ, it is enough to study the behaviour of moment curves. In particular,

Proposition 10. B^{Λ} = cl B_{∘}^{Λ}.

Proof. B^{Λ} is closed, so clB_{∘}^{Λ} ⊆ B^{Λ}. To see that the reverse inclusion holds, let w ∈ B^{Λ} and write

dα_{1} ⊕ ⋯ ⊕ dα_{r} = π(w).

Then w is a limit point of B_{∘}^{Λ}, as we can see by choosing the appropriate moment curve:

w = lim_{t→0^{+}} ρ (dα_{1} + tp_{dα_{1}}^{−2} dα_{2} + … + t^{r−1}p_{dα_{1}+...+dα_{r−1}}^{−2}dα_{r}) .

Essentially the same argument as in the above proof, carried out within the lowerdimensional pieces W_{+}^{(S_{1},...,S_{r})} of \overline{D}^{Λ}, reveals that B^{Λ} has a natural “facial structure” identical with that of a special convex polyhedron known as a permutahedron. The details of this combinatorial analysis appear in Section 3.

2.5. Two technical lemmas. In this section we derive two technical lemmas concerning stable sequences in W_{+}^{[d]} by directly analyzing the maps

f : D → J , Ψ : D → MOP

of Definition 1.

To begin, we recall some necessary facts and set up notation. Given a matrix J, let χ(J) denote its characteristic polynomial, and let J_{i} denote the leading i × i submatrix. Note that for J = f(w), w ∈ W_{+}^{[d]}, the sequence (p_{0}, …, p_{d}) = Ψ(w) satisfies p_{i} = χ(J_{i}), 1 ≤ i ≤ d. Given w ∈ W_{+}^{[d]} and a non-empty set Q ⊂ [d], let w|_{Q} denote the restriction of w : [d] → R to Q. Recall that, with the notation we have established earlier,

f(w|_{Q}) = f (∑_{n∈Q} w_{n}δ(λ − λ_{n})) .

The following notion will be used only fleetingly in the present section; in Section 3, however, it will be used extensively. A refinement of an ordered partition (S_{1}, …, S_{r}) ∈ P_{[d]} is an ordered partition of the form

(R_{1}^{1}, …, R_{i_{1}}^{1}, R_{1}^{2}, …, R_{i_{2}}^{2}, …, R_{1}^{r}, …, R_{i_{r}}^{r}),

where, for each j, 1 ≤ j ≤ r, (R_{1}^{j}, …, R_{i_{j}}^{j}) is an ordered partition of S_{j}. We write

(R_{1}, …, R_{q}) ⪯ (S_{1}, …, S_{r})

to indicate that (R_{1}, …, R_{q}) is a refinement of (S_{1}, …, S_{r}); conversely, we say that (S_{1}, …, S_{r}) is a coarsening of (R_{1}, …, R_{q}).

We note a pair of bounds on the values of Ψ on W_{+}^{[d]}, in preparation for the coming lemmas. Let P, S ⊂ R denote the sets

P = {p_{i}^{2}(λ_{k}) | p_{i} = Ψ_{i}(w), w ∈ W_{+}^{[d]}, λ_{k} ∈ Λ, 0 ≤ i ≤ d} ,
S = {∑_{k∈Q} p_{i}^{2}(λ_{k}) | p_{i} = Ψ_{i}(w), w ∈ W_{+}^{[d]}, Q ⊆ [d], i < |Q|} .

Proposition 11. Let U = sup P and L = inf S. Then U < ∞ and L > 0.

Proof. Let S′ ⊂ R denote the set

S′ = \{∑_{k∈Q} p_{i}^{2}(λ_{k}) | p_{i} = χ(J_{i}), J ∈ \overline{J}^{Λ}, Q ⊆ [d], i < |Q|\} ,

and observe that S′ ⊇ S. Now, in S′, each ∑_{k∈Q} p_{i}^{2}(λ_{k}) > 0, since p_{i} has degree i and |Q| > i. Moreover, the map χ(J) is continuous in the entries of J, and the domain \overline{J}^{Λ} is compact, unlike W_{+}^{[d]}. Therefore

L′ = inf S′ > 0,

which implies positivity of L ≥ L′, since S ⊆ S′. That U < ∞ also follows from compactness of \overline{J}^{Λ}, by a similar argument.

Note that if (S_{1}, …, S_{r}) ∈ P_{[d]} is the limiting partition of a stable sequence w(n) ∈ W_{+}^{[d]}, then for any coarsening (Q, R) ∈ P_{[d]} of (S_{1}, …, S_{r}),

lim_{n→∞} \frac{w(n)_{j}}{w(n)_{i}} = 0 ∀ i ∈ Q, j ∈ R.

Of course, r ≥ 2 is necessary for such a coarsening to exist.

Lemma 12. Let w(n) be a stable sequence in W_{+}^{[d]}, with limiting partition (S_{1}, …, S_{r}), where r ≥ 2, and let (Q, R) ∈ P_{[d]} be a coarsening of (S_{1}, …, S_{r}). If f(w(n)|_{Q}) converges, then, for each N, 1 ≤ N ≤ 2|Q| − 1, the sequence f_{N}(w(n)) converges, and

(27)  lim_{n→∞} f_{N}(w(n)) = lim_{n→∞} f_{N}(w(n)|_{Q}).

Proof. We proceed by induction on N, in the range 1 ≤ N ≤ 2|Q| − 1. We first consider the case N = 1. By Definition 1,

f_{1}(w(n)) = \frac{A + B}{C + D}, f_{1}(w(n)|_{Q}) = \frac{A}{C},

where

\begin{matrix}A = ∑_{i∈Q} λ_{i}w(n)_{i}, & B = ∑_{i∈R} λ_{i}w(n)_{i}, \\ C = ∑_{i∈Q} w(n)_{i}, & D = ∑_{i∈R} w(n)_{i}. \end{matrix}

In order to show that

lim_{n→∞} f_{1}(w(n)) = lim_{n→∞} f_{1}(w(n)|_{Q}),

it suffices to show that

(28)  |\frac{A + B}{C + D} − \frac{A}{C}| = |\frac{B}{C + D} − \frac{A}{C} (\frac{D}{C + D})| → 0,

as n → ∞. Now, A/C = f_{1}(w(n)|_{Q}) converges in R by assumption; and we know that for every i ∈ Q, j ∈ R, lim_{n→∞} w(n)_{j}/w(n)_{i} = 0, which implies

lim_{n→∞} \frac{B}{C + D} = lim_{n→∞} \frac{D}{C + D} = 0,

and hence (28).

Next, suppose that (27) holds for every N in the range 1 ≤ N ≤ 2i − 3, where 2 ≤ i ≤ |Q|; we will prove that (27) then holds for N = 2i − 2 and N = 2i − 1 also. In the case N = 2i − 2, it is simpler to prove the equivalent statement to (27), that

(29)  lim_{n→∞} f_{2i−2}^{2}(w(n)) = lim_{n→∞} f_{2i−2}^{2}(w(n)|_{Q}).

Write

(p_{0}^{n}, …, p_{d}^{n}) = Ψ(w(n)), (q_{0}^{n}, …, q_{|Q|}^{n}) = Ψ(w(n)|_{Q}),

where here the superscript n in p_{i}^{n} and q_{i}^{n} is not an exponent, but just an index. By Definition 1,

f_{2i−2}^{2}(w(n)) = \frac{A + B}{C + D}, f_{2i−2}^{2}(w(n)|_{Q}) = \frac{A′}{C′} ,

where

\begin{matrix}A = ∑_{k∈Q}(p_{i−1}^{n}(λ_{k}))^{2}w(n)_{k}, & B = ∑_{k∈R}(p_{i−1}^{n}(λ_{k}))^{2}w(n)_{k}, \\ C = ∑_{k∈Q}(p_{i−2}^{n}(λ_{k}))^{2}w(n)_{k}, & D = ∑_{k∈R}(p_{i−2}^{n}(λ_{k}))^{2}w(n)_{k}, \\ A′ = ∑_{k∈Q}(q_{i−1}^{n}(λ_{k}))^{2}w(n)_{k}, & C′ = ∑_{k∈Q}(q_{i−2}^{n}(λ_{k}))^{2}w(n)_{k}. \end{matrix}

In order to prove (29), it suffices to show that the right-hand side of the inequality

(30)  |\frac{A + B}{C + D} − \frac{A′}{C′} | ≤ |\frac{A + B}{C + D} − \frac{A}{C}| + |\frac{A}{C} − \frac{A′}{C′} |

tends to 0 as n → ∞.

Since p_{i−1}^{n} = χ(J_{i−1}), where J = f(w(n)), and q_{i−1}^{n} = χ(J′_{i−1}), where J′ = f(w(n)|_{Q}), the induction hypothesis and continuity of χ imply that |A/A′| → 1 as n → ∞. If i = 2, then trivially p_{i−2}^{n} = q_{i−2}^{n}; if i > 2, the same reasoning as above shows that |C/C′| → 1 as n → ∞. Since A′/C′ converges by assumption, it follows that

lim_{n→∞} |\frac{A}{C} − \frac{A′}{C′} | = 0,

and hence that A/C converges. We now argue that the remaining term on the righthand side of (30),

(31)  |\frac{A + B}{C + D} − \frac{A}{C}| = |\frac{B}{C + D} − \frac{A}{C} (\frac{D}{C + D})| ,

tends to 0 as n → ∞. For each n, let w(n)_{min} = w(n)_{k(n)}, where the index k(n) ∈ Q renders |w(n)_{k(n)}| minimal over Q for the given n. Then, by Proposition 11,

B/w(n)_{min} ≤ U ∑_{k∈R} w(n)_{k}/w(n)_{min} → 0 as n → ∞,

D/w(n)_{min} ≤ U ∑_{k∈R} w(n)_{k}/w(n)_{min} → 0 as n → ∞,

C/w(n)_{min} ≥  L  > 0 independently of n.

It follows that (31) tends to 0 as n → ∞, proving (29). We omit the proof that

lim_{n→∞} f_{2i−1}(w(n)) = lim_{n→∞} f_{2i−1}(w(n)|_{Q}),

which goes along exactly the same lines as the proof of (29), with obvious minor modifications.

Lemma 13. Let w(n) be a stable sequence in W_{+}^{[d]}, with limiting partition (S_{1}, …, S_{r}), where r ≥ 2. Then

lim_{n→∞} f_{2|S_{1}|}(w(n)) = 0.

Proof. To simplify the notation, write N = |S_{1}|, and set Q = S_{1} and R = S_{2}∪…∪S_{r}. As before, let w(n)_{min} = w(n)_{k(n)}, where k(n) ∈ Q renders |w(n)_{min}| minimal over Q for the given n. The fact that S_{1} is a cell in the limiting partition of w(n) implies that

(32)  ∀k ∈ Q, the sequence w(n)_{k}/w(n)_{min} is bounded

(indeed it is convergent). Set p_{N}^{n} = Ψ_{N}(w(n)) and q_{N}^{n} = Ψ_{N}(w(n)|_{Q}), where the superscript n in p_{N}^{n} and q_{N}^{n} is an index and not an exponent, so that p_{N}^{n} = χ(J_{N}), where J = f(w(n)), and q_{N}^{n} = χ(J′), where J′ = f(w(n)|_{Q}). In fact q_{N}^{n} has constant value

q_{N}^{n}(λ) = ∏_{k∈Q}(λ − λ_{k}),

independent of n. The entries of J_{N}, J′ are, respectively,

(f_{1}(w(n)), …, f_{2N−1}(w(n))), (f_{1}(w(n)|_{Q}), …, f_{2N−1}(w(n)|_{Q})).

Therefore, by Lemma 12, lim_{n→∞} J_{N} = lim_{n→∞} J′, and by continuity of χ,

lim_{n→∞} p_{N}^{n}(λ) = lim_{n→∞} q_{N}^{n}(λ) = ∏_{k∈Q}(λ − λ_{k}).

Using (32), this implies

(33)  lim_{n→∞} ∑_{k∈Q}(p_{N}^{n}(λ_{k}))^{2}w(n)_{k}/w(n)_{min} = 0.

For every k ∈ R, w(n)_{k}/w(n)_{min} → 0, so, by Proposition 11,

(34)  ∑_{k∈R}(p_{N}^{n}(λ_{k}))^{2}w(n)_{k}/w(n)_{min} ≤ U ∑_{k∈R} w(n)_{k}/w_{min} → 0,

as n → ∞. On the other hand, since N − 1 < |Q|, we have, by Proposition 11,

(35)  ∑_{k∈Q}(p_{N−1}^{n}(λ_{k}))^{2}w(n)_{k}/w(n)_{min} ≥ L > 0,

independently of n, where p_{N−1}^{n} = Ψ_{N−1}(w(n)). By Definition 1,

f_{2N}^{2}(w(n)) = \frac{∑_{k∈Q}(p_{N}^{n}(λ_{k}))^{2}w(n)_{k} + ∑_{k∈R}(p_{N}^{n}(λ_{k}))^{2}w(n)_{k}}{∑_{k∈Q}(p_{N−1}^{n}(λ_{k}))^{2}w(n)_{k} + ∑_{k∈R}(p_{N−1}^{n}(λ_{k}))^{2}w(n)_{k}} .

It follows from (33), (34) and (35) that lim_{n→∞} f_{2N}^{2}(w(n)) = 0.

2.6. The flip transpose. In this section we explain the origin of the coefficients C_{i}^{S−R} appearing in the equations for B^{Λ} in Definition 2. The underlying technical fact is a formula involving the flip transpose.

The flip transpose of a d×d matrix M is defined to be the d×d matrix M^{F} having entries

M^{F} (i, j) = M(d + 1 − j, d + 1 − i).

In terms of our convention (1) for labeling the entries (a_{1}, …, a_{2d−1}) of a Jacobi matrix J, the entries of J^{F} are simply the reverse sequence (a_{2d−1}, …, a_{1}). The flip transpose of a matrix induces, in the obvious way, a corresponding operation on probability distributions in D, namely, define the flip transpose of dα ∈ D, written dα^{F}, to be the spectral distribution of

(f(dα))^{F} .

Note that flip transposition leaves the spectrum of a matrix unchanged, so that supp dα^{F} = supp dα. As an operation on distributions, therefore, flip transposition carries W_{+}^{[d]} into itself; we write w^{F} for the flip transpose of w ∈ W_{+}^{[d]}. It follows immediately from the definition that for each i, 1 ≤ i ≤ 2d − 1,

(36)  f_{i}(w) = f_{2d−i}(w^{F}).

Define constants \overline{C}_{i}^{S} in terms of the d-element set Λ = \{λ_{1}, …, λ_{d}\} as follows. Set

p(λ) = ∏_{n=1}^{d}(λ − λ_{n}), p′(λ) = \frac{d}{dλ}p(λ),

and for each non-empty S ⊆ [d], i ∈ [d], set

\overline{C}_{i}^{S} = ∏_{n∈S}(p′(λ_{i} − λ_{n}))^{2}.

Then, for i ∈ R ⊆ S ⊆ [d], we have the relation \overline{C}_{i}^{S}/\overline{C}_{i}^{R} = C_{i}^{S−R}.

The following result is a translation of [9, Proposition 3.3] into our current notation.

Proposition 14. For w ∈ W_{+}^{[d]}, w^{F} is given by the formula

w_{n}^{F} = \frac{1}{\overline{C}_{n}^{[d]}w_{n}} , ∀n ∈ [d].

This has an immediate implication for stable sequences.

Corollary 15. Let w(n) be a stable sequence in W_{+}^{[d]} with limiting partition (S_{1}, …, S_{r}). Then the sequence w(n)^{F} ∈ W_{+}^{[d]} is stable and has the reverse-ordered limiting partition (S_{r}, …, S_{1}).

Let Q ∪ R be a partition of [d], and let w ∈ W_{+}^{[d]}. Repeated application of Proposition 14 yields

(w^{F} |_{R})^{F} = ((\frac{1}{\overline{C}_{i}^{[d]}w_{i}} )_{i∈R})^{F}

= (\frac{\overline{C}_{i}^{[d]}w_{i}}{\overline{C}_{i}^{R}} )_{i∈R}
= (C_{i}^{[d]−R}w_{i})_{i∈R}
(37)  = (C_{i}^{Q})_{i∈R}.

The following technical result accounts for the coefficients that appear in the equations defining B^{Λ}.

Lemma 16. Let w(n) be a stable sequence in W_{+}^{[d]} with limiting partition (S_{1}, …, S_{r}), where r ≥ 2, and let (Q, R) ∈ P_{[d]} be a coarsening of (S_{1}, …, S_{r}). If f(w(n)^{F} |_{R}) converges, then for each i, 2|Q| + 1 ≤ i ≤ 2d − 1, f_{i}(w(n)) converges and

lim_{n→∞} f_{i}(w(n)) = lim_{n→∞} f_{i−2|Q|} ((w(n)^{F} |_{R})^{F} )
= lim_{n→∞} f_{i−2|Q|} ((C_{j}^{Q}w(n)_{j})_{j∈R}) .

Proof. By Corollary 15 w(n)^{F} is stable with limiting partition (S_{r}, …, S_{1}), of which (R, Q) is a coarsening. If f(w(n)^{F} |_{R}) converges then, by Lemma 12, for each i, 1 ≤ i ≤ 2|R| − 1, f_{i}(w(n)^{F}) converges, and

lim_{n→∞} f_{i}(w(n)^{F}) = lim_{n→∞} f_{i}(w(n)^{F} |_{R}).

Applying (36) to the left- and right-hand sides yields

lim_{n→∞} f_{j}(w(n)) = lim_{n→∞} f_{j−2|Q|}((w(n)^{F} |_{R})^{F}),

where j = 2d − i and 2|Q| + 1 ≤ j ≤ 2d − 1. The calculation (37) then gives the last expression in the conclusion of the lemma.

Lemma 17. Let w(n) be a stable sequence in W_{+}^{[d]} with limiting partition (S_{1}, …, S_{r}), where r ≥ 2. Then

lim_{n→∞} f_{2d−2|S_{r}|}(w(n)) = 0.

Proof. Applying Lemma 13 to the sequence w(n)^{F} yields

lim_{n→∞} f_{2|S_{r}|}(w(n)^{F}) = 0.

By (36) this is equivalent to the conclusion of the present lemma.

2.7. The main result. In this section we prove that

\overline{f} ∘ π : B^{Λ} → \overline{J}^{Λ}

is a homeomorphism.

The proof involves stable sequences in W_{+}^{Q}, where Q ranges over non-empty subsets of [d]. We use the characterization of stable sequences in terms of limits, to avoid dealing with semi-algebraic sets of the form B^{Γ} where Γ ⊂ Λ. Thus a sequence w(n) ∈ W_{+}^{Q} is stable if, for every i, j ∈ Q, there exists L_{i,j} ∈ R^{+} ∪ {0, ∞} such that

\frac{w(n)_{i}}{w(n)_{j}} → L_{ij} as n → ∞.

Note that if w(n) is a stable sequence in W_{+}^{[d]} then for Q ⊆ [d], the restriction w(n)|_{Q} is automatically a stable sequence in W_{+}^{Q}.

Proposition 18. Let w(n) be a stable sequence in W_{+}^{[d]} with limiting partition (S_{1}, …, S_{r}). Then f(w(n)) converges, and

(38)  lim_{n→∞} f(w(n)) = \overline{f} ( ⨁_{(S_{1},...,S_{r})}lim_{n→∞} (C_{i}^{S_{1}∪...∪S_{j−1}}w(n)_{i})_{i∈S_{j}} ) .

Proof. We argue by induction on N = |S|, where S ⊆ [d]. If |S| = 1 then the proposition, with W_{+}^{S} in place of W_{+}^{[d]}, holds trivially.

Suppose that 2 ≤ N ≤ d, and that for every non-empty Q ⊂ [d] of size |Q| < N, the proposition holds with W_{+}^{Q} in place of W_{+}^{[d]}. We will show that the proposition then holds for W_{+}^{S} whenever S ⊆ [d] and |S| = N. Thus let S ⊆ [d] have size |S| = N, and let w(n) be a stable sequence in W_{+}^{S} with limiting partition (S_{1}, …, S_{r}) ∈ P_{S}. If r = 1 then w(n) necessarily converges in W_{+}^{S}; since f is continuous on W_{+}^{S} (with respect to its natural topology), this implies

lim_{n→∞} f(w(n)) = f ( lim_{n→∞} w(n)) ,

which conforms to (38). Next consider the non-trivial case r ≥ 2. Set Q = S_{1} ∪ … ∪ S_{r−1} and R = S_{r}. Then w(n)|_{Q} is a stable sequence with limiting partition (S_{1}, …, S_{r−1}), and by the induction hypothesis

lim_{n→∞} f(w(n)|_{Q}) = \overline{f} ( ⨁_{(S_{1},...,S_{r−1})} lim_{n→∞} (C_{i}^{S_{1}∪...∪S_{j−1}}w(n)_{i})_{i∈S_{j}} ) .

In particular, f(w(n)|_{Q}) converges, so by Lemma 12 (with S in place of [d]), for every M in the range 1 ≤ M ≤ 2|Q| − 1, f_{M}(w(n)) converges, and

(39)  lim_{n→∞} f_{M}(w(n)) = lim_{n→∞} f_{M}(w(n)|_{Q}).

Corollary 15 implies that w(n)^{F} |_{R} converges in W_{+}^{R}, since R = S_{r} is a cell of the limiting partition of w(n). Therefore f(w(n)^{F} |_{R}) converges, and by Lemma 16, for M in the range 2|Q| + 1 ≤ M ≤ 2|S| − 1, f_{M}(w(n)) converges, and

lim_{n→∞} f_{M}(w(n)) = lim_{n→∞} f_{M−2|S|} ((C_{i}^{Q}w(n)_{i})_{i∈S_{r}})
(40)  = f_{M−2|S|} ( lim_{n→∞}(C_{i}^{Q}w(n)_{i})_{i∈S_{r}}) ,

the latter equality since f is continuous on W_{+}^{R}. The behaviour of f_{M}(w(n)) for the remaining index M = 2|S| − 2|S_{r}| is determined by Lemma 17:

(41)  lim_{n→∞} f_{2|S|−2|S_{r}|}(w(n)) = 0.

The statements (39), (40) and (41) collectively imply that lim f(w(n)) has the form

lim_{n→∞} f(w(n)) = \overline{f} ( ⨁_{(S_{1},...,S_{r−1})} lim_{n→∞} (C_{i}^{S_{1}∪...∪S_{j−1}}w(n)_{i})_{i∈S_{j}} ) ⊕

f ( lim_{n→∞} (C_{i}^{Q}w(n)_{i})_{i∈S_{r}})

= \overline{f} ( ⨁_{(S_{1},...,S_{r})}lim_{n→∞} (C_{i}^{S_{1}∪...∪S_{j−1}}w(n)_{i})_{i∈S_{j}} ) .

Thus the proposition holds for W_{+}^{S}, completing the induction.

Corollary 19. Let w̃(n) be a sequence in B_{∘}^{Λ} that converges in B^{Λ}. Then

(42)  lim_{n→∞} \overline{f} ∘ π(w̃(n)) = \overline{f} ∘ π ( lim_{n→∞} w̃(n)) .

Proof. Write w̃(n) = ρ(w(n)), where w(n) = π(w̃(n)) is by definition a stable sequence in W_{+}^{[d]}, and let (S_{1}, …, S_{r}) denote the limiting partition of w(n). Now, \overline{f} ∘ π(w̃(n)) = \overline{f}(w(n)), and, by Proposition 18, the left-hand side of (42) is

(43)  lim_{n→∞} \overline{f}(w(n)) = \overline{f} ( ⨁_{(S_{1},...,S_{r})}lim_{n→∞} (C_{i}^{S_{1}∪...∪S_{j−1}}w(n)_{i})_{i∈S_{j}} ) .

On the other hand, by the calculation (24),

π ( lim_{n→∞} w̃(n)) = ⨁_{(S_{1},...,S_{r})}lim_{n→∞} (C_{j}^{S_{1}∪...∪S_{j−1}}w(n)_{i})_{i∈S_{j}} ,

so the right-hand sides of (42) and (43) are equal.

It is a small step from the above corollary to our main result.

Theorem 20. The map \overline{f} ∘ π : B^{Λ} → \overline{J}^{Λ} is a homeomorphism.

Proof. For brevity write g = \overline{f} ∘ π. Note first that g is a bijection since each of its factors \overline{f} and π is. To see that g is continuous, let w(n) ∈ B^{Λ} be a convergent sequence. It follows from Corollary 19 and the fact that B^{Λ} = cl B_{∘}^{Λ} (Proposition 10) that there exists a convergent sequence w′(n) ∈ B_{∘}^{Λ} such that

(44)  lim_{n→∞} w′(n) = lim_{n→∞} w(n) and lim_{n→∞} ||g(w′(n)) − g(w(n))|| = 0.

By Corollary 19,

lim_{n→∞} g(w′(n)) = g ( lim_{n→∞} w′(n)) ,

which, by (44), implies

lim_{n→∞} g(w(n)) = g ( lim_{n→∞} w(n)) .

Thus g is a continuous bijection; since B^{Λ} is compact it follows that g is a homeomorphism.

2.8. The solution to Problem 1. With Theorem 20 we have a complete solution to Problem 1. Since the composition

B^{Λ} ⟶^{π} \overline{D}^{Λ} ⟶^{\overline{f}} \overline{J}^{Λ}

is a homeomorphism, the topology that \overline{J}^{Λ} induces on \overline{D}^{Λ} via \overline{f} is precisely the topology that B^{Λ} induces on \overline{D}^{Λ} via π. To put it succinctly, the blow-up (B^{Λ}, π) itself constitutes a solution to Problem 1. A sequence w(n) ∈ \overline{D}^{Λ} converges in the induced topology if and only if π^{−1}(w(n)) converges in B^{Λ}, and in this case the limiting value may be computed as

(45)  π ( lim_{n→∞} π^{−1}(w(n))) ,

which does not require evaluation of \overline{f}. The point is that π and ρ = π^{−1}, unlike \overline{f}, are easy to calculate by hand.

More explicitly, a sequence w(n) in the principal component W_{+}^{[d]} of \overline{D}^{Λ} is convergent if and only if it is stable. (The characterization of convergent sequences in the other, lower-dimensional pieces of \overline{D}^{Λ},

⨁_{(S_{1},...,S_{r})}w^{S_{i}}(n) ∈ W_{+}^{(S_{1},...,S_{r})},

is virtually the same: each w^{S_{i}}(n) must be stable in W_{+}^{S_{i}}.) Recall that the essence of the computation (45) is captured by the limiting values of moment curves in W_{+}^{[d]}, as in Proposition 9. In distributional notation, given dα_{1}, …, dα_{r} ∈ D such that

(supp dα_{1}, …, supp dα_{r}) ∈ P_{Λ},

the moment curve dα(t) = dα_{1} + t dα_{2} + ⋯ + t^{r−1} dα_{r} tends to the point

π ( lim_{t→0^{+}} π^{−1}(dα(t))) = \overline{f}^{−1} ( lim_{t→0^{+}} f(dα(t)))
= dα_{1} ⊕ p_{dα_{1}}^{2} dα_{2} ⊕ ⋯ ⊕ p_{dα_{1}+...+dα_{r−1}}^{2} dα_{r}.

The example discussed in Section 2.1 is a simple instance of this general limiting behaviour.

3. Isospectral sets of tridiagonal matrices

We turn now to a particular application of the material in Section 2: deducing the topology of the set of symmetric, tridiagonal matrices having prescribed spectrum Λ. This results in some rather interesting discrete geometry. As mentioned in the Introduction, the isospectral sets we consider have been studied before—our purpose is to provide a new approach.

We state precisely the problem of interest in Section 3.1. Then in Section 3.2 we analyze the combinatorial structure of the semialgebraic set B^{Λ}, constructed earlier in Section 2. We show that B^{Λ} has a natural “facial” structure, corresponding to the individual pieces of \overline{D}^{Λ}, and that the facial lattice of B^{Λ} is represented by the partial order (P_{Λ}, ⪯). The combinatorial structure of B^{Λ} allows one to very easily construct a polyhedral complex, which we label \overline{P}_{d}, over the manifold of symmetric, tridiagonal matrices that have spectrum Λ. We describe this construction in Sections 3.3 and 3.4. Finally in Section 3.5 we carry out some explicit computations. We explore the particular example of \overline{P}_{3}: topologically it is a two-holed torus, and its Petrie polygon uses every edge. Concerning the sequence of complexes \overline{P}_{d}, we prove the remarkable fact that hyperbolic tangent generates the Euler characteristics.

We follow the nomenclature for convex polytopes given in Brøndsted’s introductory text [2]. In particular we use the characterization of a proper face of a d-polytope P in R^{d} as the intersection of P with a supporting hyperplane in R^{d}.

3.1. Symmetric, tridiagonal matrices; Problem 2. Let T denote the set of finite-dimensional, real, symmetric, tridiagonal matrices. We consider the following problem.

Problem 2 Let Λ = {λ_{1}, …, λ_{d}} ⊂ R be a d-element set. Describe the topology of the isospectral set

T^{Λ} = {T ∈ T | spec T = Λ} .

The set \overline{J}^{Λ} ⊂ T^{Λ} consists of those matrices whose next-to-diagonal entries are non-negative, and so the parametrization

\overline{f} ∘ π : B^{Λ} → \overline{J}^{Λ}

established in Section 2 applies directly to Problem 2. Indeed let E denote the set of d-vectors of the form

ε = (ε_{1}, …, ε_{d}), where each ε_{j} ∈ {+1, −1}.

For each ε ∈ E let s_{ε} denote the operation on d×d matrices of conjugation by diag(ε), so that

s_{ε}(M) = diag(ε)M diag(ε).

Then each map of the form

s_{ε} ∘ \overline{f} ∘ π : B^{Λ} → T^{Λ}

is a homeomorphism from B^{Λ} onto a “patch” of T^{Λ}, and collectively the maps s_{ε}∘\overline{f} ∘π cover T^{Λ}. (Note that the s_{ε} are a way of encoding the modification of Definition 1 which would correspond to a particular choice of positive or negative square root for each off-diagonal component of f—as Definition 1 stands, only the positive square root is used.) The topology of T^{Λ} is thus captured by the complex (B^{Λ} × E)/ ∼, consisting of copies B^{Λ} × {ε} of B^{Λ}, glued together according to the relation

(w, ε) ∼ (w′, ε′) ⟺ s_{ε} ∘ \overline{f} ∘ π(w) = s_{ε′} ∘ \overline{f} ∘ π(w′).

This gluing map respects the inherent “facial” structure of B^{Λ}, which we describe in Section 3.2 below. In principle, the complex (B^{Λ} × E)/ ∼ is all we need in order to calculate the standard topological invariants of T^{Λ}. However, to make the combinatorial structure of (B^{Λ} × E)/ ∼ more transparent, we go a step further in Section 3.3 and replace B^{Λ} with a particular convex polytope, call a permutahedron, which is combinatorially equivalent to B^{Λ} but nevertheless a simpler object. The final result is a polyhedral complex over T^{Λ} which not only encodes the topology of T^{Λ}, but which is itself rather interesting.

3.2. The facial structure of B^{Λ}. For each ordered partition (S_{1}, …, S_{r}) ∈ P_{[d]}, set

B_{(S_{1},...,S_{r})}^{Λ} = cl (π^{−1} (W_{+}^{(S_{1},...,S_{r})})) .

We refer to B_{(S_{1},...,S_{r})}^{Λ} as a face of B^{Λ}, in analogy with the terminology for convex polytopes. We give partial justification for this later in the present section, by showing that, in the appropriate affine setting, each B_{(S_{1},...,S_{r})}^{Λ} is the intersection of B^{Λ} with the bounding hyperplane of a supporting half-space of B^{Λ}, exactly as for a convex polytope. But B^{Λ} is of course not a polytope; it’s faces are in general curved. In the next section we show that the “curved polytope” B^{Λ} can be flattened, that is, mapped to a bona fide convex polytope that has the same facial structure. Our main objective in this section is to ascertain the inclusion relation between faces of B^{Λ}, and, more precisely, to show that (P_{[d]}, ⪯) represents the facial lattice of B^{Λ}. This entails what is in essence a technically messier version of the proof of Proposition 10 (which states that B_{[d]}^{Λ} = B^{Λ}).

To begin, we note the following extension of Proposition 9.

Proposition 21. Let S ⊆ [d], (S_{1}, …, S_{r}) ∈ P_{S}, and w^{(S_{1},...,S_{r})} ∈ W_{+}^{(S_{1},...,S_{r})}. Then there exists a moment curve w(t) ∈ W_{+}^{S} such that

\overline{f}^{−1} ( lim_{t→0^{+}} f(w(t))) = w^{(S_{1},...,S_{r})}.

Proof. By Theorem 20 the topology that \overline{J}^{Λ} induces on \overline{D}^{Λ} via \overline{f} agrees with the topology induced on \overline{D}^{Λ} by B^{Λ} via π. In the case S = [d], Propositions 9 and 10 therefore imply the present proposition directly. But Λ, and in particular d = |Λ|, is arbitrary, so once the proposition holds for S = [d], it holds for all S ⊂ [d], since we may replace Λ with Λ′ = {λ_{n} ∈ Λ | n ∈ S}.

For each (S_{1}, …, S_{r}) ∈ P_{[d]}, let F_{(S_{1},...,S_{r})} ⊂ B^{Λ} denote the set

F_{(S_{1},...,S_{r})} = π^{−1} ( ⋃_{(R_{1},...,R_{q})⪯(S_{1},...,S_{r})} W_{+}^{(R_{1},...,R_{q})}) .

Lemma 22. For each (S_{1}, …, S_{r}) ∈ P_{[d]}, F_{(S_{1},...,S_{r})} ⊆ B_{(S_{1},...,S_{r})}^{Λ}.

Proof. Let w̃ ∈ F_{(S_{1},...,S_{r})}, and write w^{(R_{1},...,R_{q})} = π(w̃), so that (R_{1}, …, R_{q}) ⪯ (S_{1}, …, S_{r}) and hence has the form

(R_{1}, …, R_{q}) = (R_{1}^{1}, …, R_{i_{1}}^{1}, …, R_{1}^{r}, …, R_{i_{r}}^{r}),

where each (R_{1}^{j}, …, R_{i_{j}}^{j}) ∈ P_{S_{j}}. Using Proposition 21, for each S_{j}, let w^{S_{j}}(t) ∈ W_{+}^{S_{j}} be a moment curve such that

\overline{f}^{−1} ( lim_{t→0^{+}} f(w^{S_{j}}(t))) = w^{(R_{1}^{j},...,R_{i_{j}}^{j})},

where w^{(R_{1}^{j},...,R_{i_{j}}^{j})} denotes the appropriate component of w^{(R_{1},...,R_{q})}. Then ⨁_{(S_{1},...,S_{r})}w^{S_{j}}(t) is a moment curve in W_{+}^{(S_{1},...,S_{r})}, and

lim_{t→0^{+}} \overline{f} ( ⨁_{(S_{1},...,S_{r})}w^{S_{j}}(t)) = lim_{t→0^{+}} ⨁_{(S_{1},...,S_{r})}f(w^{S_{j}}(t))

= ⨁_{(S_{1},...,S_{r})} lim_{t→0^{+}} f(w^{S_{j}}(t))

= ⨁_{(S_{1},...,S_{r})}\overline{f}(w^{(R_{1}^{j},...,R_{i_{j}}^{j})})
= \overline{f}(w^{(R_{1},...,R_{q})}),

whereby

\overline{f}^{−1} ( lim_{t→0^{+}} \overline{f} ( ⨁_{(S_{1},...,S_{r})}w^{S_{j}}(t))) = w^{(R_{1},...,R_{q})}.

By Theorem 20, this implies

lim_{t→0^{+}} π^{−1} ( ⨁_{(S_{1},...,S_{r})}w^{S_{j}}(t)) = w̃,

so that w̃ ∈ B_{(S_{1},...,S_{r})}^{Λ} = cl (π^{−1} (W_{+}^{(S_{1},...,S_{r})})).

In Section 2 it was convenient to have B^{Λ} in projective space so that we could use homogeneous coordinates, and not have to worry about rescaling. For present considerations, it is better to embed B^{Λ} in affine space. To that end, for each nonempty S ⊆ [d], let

R^{S} = {w^{S} : S → R}

be the |S|-dimensional Euclidean space of real-valued sequences indexed over S, and set

E = ∏_{∅≠S⊆[d]} R^{S}.

Let A denote the affine subspace of E defined as

A = {w ∈ E | ∀S ⊆ [d], S ≠ ∅, ∑_{n∈S} w_{n}^{S} = 1} .

Now, the ambient space of B^{Λ}, W = ∏_{∅≠S⊆[d]} W^{S}, is a quotient space of E −{0}, and the inequalities (17) defining B^{Λ} guarantee that each w ∈ B^{Λ} has a unique normalized representor ŵ ∈ A. Hence we may regard B^{Λ} ⊂ A as sitting in affine space, without altering its topological structure; we do so for the remainder of the present section.

We now define a family of half-spaces H_{(S_{1},...,S_{r})}^{+} of A, along with their bounding hyperplanes H_{(S_{1},...,S_{r})}. It follows from the the explicit construction of ρ = π^{−1} given in Definition 6 that for w ∈ π^{−1} (W_{+}^{(S_{1},...,S_{r})}), the set

I = {(n, S) | n ∈ S ⊆ [d], w_{n}^{S} = 0}

does not depend on the particular point w. Rather,

I = I_{(S_{1},...,S_{r})}

is determined by the partition (S_{1}, …, S_{r}) ∈ P_{[d]}. Moreover,

(46)  I_{(S_{1},...,S_{r})} ⊆ I_{(R_{1},...,R_{q})} ⟺ (R_{1}, …, R_{q}) ⪯ (S_{1}, …, S_{r}).

Now, given (S_{1}, …, S_{r}) ∈ P_{[d]}, let

H_{(S_{1},...,S_{r})} ⊂ A

denote the hyperplane in A determined by the equation

∑_{(n,S)∈I_{(S_{1},...,Sr)}} w_{n}^{S} = 0,

and let H_{(S_{1},...,S_{r})}^{+} ⊂ A denote the corresponding half-space, determined by the inequality

∑_{(n,S)∈I_{(S_{1},...,Sr)}} w_{n}^{S} ≥ 0.

Lemma 23. For every (S_{1}, …, S_{r}) ∈ P_{[d]}, the half-space H_{(S_{1},...,S_{r})}^{+} includes B^{Λ}, and F_{(S_{1},...,S_{r})} = H_{(S_{1},...,S_{r})} ∩ B^{Λ}.

Proof. The inequalities (17) defining B^{Λ} and the defining equations of A imply that if w ∈ B^{Λ}, then its normalized representor ŵ ∈ A satisfies ŵ_{n}^{S} ≥ 0 for every n ∈ S ⊆ [d]. It follows that B^{Λ} ⊂ H_{(S_{1},...,S_{r})}^{+}.

Also, ŵ ∈ H_{(S_{1},...,S_{r})} if and only if for each (n, S) ∈ I_{(S_{1},...,S_{r})}, ŵ_{n}^{S} = 0. By (46) this condition is equivalent to the condition that

π(ŵ) ∈ W_{+}^{(R_{1},...,R_{q})},

for some (R_{1}, …, R_{q}) ⪯ (S_{1}, …, S_{r}), or in other words, ŵ ∈ F_{(S_{1},...,S_{r})}.

Combining Lemmas 22 and 23 yields the following characterization of the faces B_{(S_{1},...,S_{r})}^{Λ}.

Proposition 24. For every (S_{1}, …, S_{r}) ∈ P_{[d]}, B_{(S_{1},...,S_{r})}^{Λ} = F_{(S_{1},...,S_{r})}.

Proof. By definition, F_{(S_{1},...,S_{r})} ⊇ π^{−1} (W_{+}^{(S_{1},...,S_{r})}). Using Lemma 23, F_{(S_{1},...,S_{r})} = B^{Λ} ∩ H_{(S_{1},...,S_{r})} is closed, so

B_{(S_{1},...,S_{r})}^{Λ} = cl (π^{−1} (W_{+}^{(S_{1},...,S_{r})})) ⊆ F_{(S_{1},...,S_{r})}.

Lemma 22 gives the reverse inclusion.

Corollary 25. B_{(R_{1},...,R_{q})}^{Λ} ⊆ B_{(S_{1},...,S_{r})}^{Λ} if and only if (R_{1}, …, R_{q}) ⪯ (S_{1}, …, S_{r}).

Thus we have shown that (P_{[d]}, ⪯) represents the facial lattice of B^{Λ}. Note that the dimension of the face B_{(S_{1},...,S_{r})}^{Λ} is dim(W_{+}^{(S_{1},...,S_{r})}) = d−r. The least-dimensional faces, corresponding to ordered partitions of the form

({σ(1)}, …, {σ(d)}),

where σ is a permutation of [d], consist of a single point and have dimension 0. If two ordered partitions

(R_{1}, …, R_{q}) ⪯ (S_{1}, …, S_{r})

are adjacent with respect to ⪯, that is if r = q + 1, then evidently

dim (B_{(S_{1},...,S_{r})}^{Λ}) = dim (B_{(R_{1},...,R_{q})}^{Λ}) + 1,

a fact which we will use in the next section.

3.3. Permutahedra. Permutahedra are convex polytopes that have a very special structure. For instance, they are simple zonotopes that tile Euclidean space; see Ziegler [11, pp.17,18,200]. We give a slightly different description from that of Ziegler, and consequently our characterization of faces, Proposition 27, differs somewhat from his. But it is easy to reconcile the two descriptions, so we do not bother to prove Proposition 27.

We fix notation as follows. Let S_{[d]} denote the symmetric group, consisting of all permutations of [d] = {1, …, d}. For each non-empty subset R ⊆ [d], let S_{R} denote the subgroup of S_{[d]} consisting of those permutations which fix each element of [d]−R; let G denote the collection of subgroups of S_{[d]} given by

G = {S_{R_{1}} × ⋯ × S_{R_{q}} | ({1}, …, {d}) ⪯ (R_{1}, …, R_{q}) ∈ P_{[d]} } .

We say that a non-empty set R ⊆ [d] is an invariant set of a group H ⊆ S_{[d]} if every σ ∈ H fixes R setwise; if in addition no non-empty proper subset of R is invariant, we say R is a minimal invariant set of H. Note that for

G = S_{R_{1}} × ⋯ × S_{R_{q}} ∈ G,

the sets R_{1}, …, R_{q} are the minimal invariant subsets of G, and they have a unique ordering for which ({1}, …, {d}) ⪯ (R_{1}, …, R_{q}) ∈ P_{[d]}. The collection G will be useful in discussing the structure of the permutahedron, which we now define.

Definition 26. Let P_{d} denote the convex hull of the set

(47)  {(σ(1), …, σ(d)) ∈ R^{d} | σ ∈ S_{[d]} } .

The convex polytope P_{d} is called a permutahedron.

Given a set F ⊂ R^{d}, let F̂ denote its convex hull. We will generally identify elements of S_{[d]} with points in R^{d} as in (47); with this convention we have, for instance,

P_{d} = Ŝ_{[d]}.

The set of groups G provides a simple description of the faces of P_{d}, as follows. Let GS_{[d]} denote the set of right cosets of the form Gσ, where G ∈ G and σ ∈ S_{[d]}.

Proposition 27. The faces of P_{d} are precisely the sets F̂ where F ∈ GS_{[d]}.

The above proposition implies that

(GS_{[d]}, ⊆)

represents the facial lattice of P_{d}. Indeed this corresponds to the facial lattice of B^{Λ} via the following map.

Definition 28. We denote by φ the map

φ : GS_{[d]} → P_{[d]},

constructed as follows. Let H ∈ GS_{[d]}. Choose σ ∈ H arbitrarily; then Hσ^{−1} ∈ G. Let R_{1}, …, R_{q} ⊂ [d] be the minimal invariant sets of Hσ^{−1}, ordered such that

({1}, …, {d}) ⪯ (R_{1}, …, R_{q}).

Set

φ(H) = (σ^{−1}(R_{1}), …, σ^{−1}(R_{q})) ∈ P_{[d]}.

Note that if H ∈ GS_{[d]} corresponds to a vertex of P_{d}, that is, if H = {σ} is a singleton, then according to the above definition

φ(H) = ({σ^{−1}(1)}, …, {σ^{−1}(d)}) .

In other words, on the level of vertices, φ coincides essentially with the map σ ↦ σ^{−1}. More generally, let H ∈ GS_{[d]} and write (T_{1}, …, T_{r}) = φ(H). Then it is a straightforward to verify that

(48)  H = {σ ∈ S_{[d]} | ({1}, …, {d}) ⪯ (σ(T_{1}), …, σ(T_{r}))} ,

whence φ is one-to-one. And given any (T_{1}, …, T_{r}) ∈ P_{[d]}, the set H defined by (48) belongs to GS_{[d]}, and so φ is onto; that is, φ is a bijection. Indeed, P_{d} and B^{Λ} are combinatorially equivalent, in the following sense.

Proposition 29. The map φ : GS_{[d]} → P_{[d]} is a lattice isomorphism, so that

(GS_{[d]}, ⊆) ≅ (P_{[d]}, ⪯) .

Proof. Since φ is a bijection, we need only show that for every H, K ∈ GS_{[d]}, H ⊆ K if and only if φ(H) ⪯ φ(K). To that end, let H, K ∈ GS_{[d]} and write (R_{1}, …, R_{q}) = φ(H), (T_{1}, …, T_{r}) = φ(K). By (48) the condition H ⊆ K is evidently equivalent to the condition that for every σ ∈ S_{[d]},

({1}, …, {d}) ⪯ (σ(R_{1}), …, σ(R_{q})) ⇒ ({1}, …, {d}) ⪯ (σ(T_{1}), …, σ(T_{r})).

And the latter condition is easily shown to be equivalent to the relation

(R_{1}, …, R_{q}) ⪯ (T_{1}, …, T_{r}).

For an arbitrary convex polytope P, if two faces F ⊂ F′ are adjacent in the facial lattice of P, that is, if there is no face F′′ of P such that F ⊂ F′′ ⊂ F′, then dim(F)′ = dim(F) + 1. As pointed out in the previous section, the facial lattice of B^{Λ} also has this property; therefore the map φ automatically respects dimension:

dim(F̂) = dim(B_{φ(F)}^{Λ}),

for every F ∈ GS_{[d]}.

Any isomorphism ι between the facial lattices of two convex polytopes P and P′ has a topological realization, in the sense that there exists a homeomorphism h : P → P′ which preserves faces, and whose action on faces agrees with ι. By the same token, the map φ has a topological realization

h : P_{d} → B^{Λ}.

We sketch briefly one possible construction of such an h. Here it is useful to have a metric on B^{Λ}, so that we may speak of geodesics. As in the previous section, let us regard B^{Λ} as sitting in the affine space A, and consider the metric that B^{Λ} inherits from the ambient Euclidean space E = ∏_{∅≠S⊆[d]} R^{|S|}.

For each face B_{(S_{1},...,S_{r})}^{Λ} of B^{Λ}, consider the point w^{(S_{1},...,S_{r})} ∈ W_{+}^{(S_{1},...,S_{r})} having constant entries w_{n}^{S_{j}} = 1 for every j, n ∈ S_{j}. We refer to the normalized representor b_{(S_{1},...,S_{r})} ∈ A of π^{−1}(w^{(S_{1},...,S_{r})}) as the “barycentre” of B_{(S_{1},...,S_{r})}^{Λ}. The map h may be constructed recursively as follows.

\underline{Initial step} For each vertex σ ∈ P_{d}, set h(σ) = B_{φ(\{σ\})}^{Λ} (the latter consists of just a single point).

\underline{Continuing step} Suppose that h has been defined on the j-skeleton of P_{d}, that is, on the set of faces of P_{d} having dimension at most j, where 0 ≤ j ≤ d − 2. Given a (j + 1)-dimensional face F̂, extend h to F̂ as follows. Let h map the barycentre f_{0} of F̂ (the mean of F) to the barycentre b_{φ(F)} of B_{φ(F)}^{Λ}. And for each point f_{1} in the j-skeleton of F̂, let h map the segment \overline{f_{0}f_{1}} to the geodesic in B_{(S_{1},...,S_{r})}^{Λ} connecting b_{φ(F)} to h(f_{1}), at constant speed with respect to arclength.

The map h : P_{d} → B^{Λ} so constructed is a homeomorphism, and its inverse can be viewed as a “flattening” of B^{Λ}. The permutahedron P_{d} is homeomorphic to \overline{J}^{Λ} via the composite map

(49)  P_{d} ⟶^{h} B^{Λ} ⟶^{π} \overline{D}^{Λ} ⟶^{\overline{f}} \overline{J}^{Λ}.

This serves as the basis for a polyhedral complex, which we describe in the next section, on the set of d × d symmetric, tridiagonal matrices having spectrum Λ.

3.4. A polyhedral complex over T^{Λ}. Referring to the composite map (49), for p ∈ P_{d} write

J_{p} = \overline{f} ∘ π ∘ h(p).

Let E ⊂ R^{d} denote the 2^{d}-element set consisting of maps ε of the form

ε : [d] → {+1, −1}.

(In other words, E consists of the vertices of the twice-unit cube centred at the origin.) For each (p, ε) ∈ P_{d} × E, set

g(p, ε) = diag(ε) J_{p} diag(ε).

Since the map p ↦ J_{p} is a homeomorphism from P_{d} onto \overline{J}^{Λ}, the map

g : P_{d} × E → T^{Λ}

is easily seen to be a continuous surjection. Let ∼ denote the relation defined on P_{d} × E defined by

(p, ε) ∼ (p′, ε′) ⟺ g(p, ε) = g(p′, ε′).

And let [(p, ε)] denote the equivalence class of (p, ε) modulo ∼. The relation ∼ may be characterized purely in terms of P_{d} × E as follows.

Proposition 30. Let (p, ε), (p′, ε′) ∈ P_{d} × E. Let F ∈ GS_{[d]} represent the unique face F̂ of P_{d} whose relative interior contains p. Choose σ ∈ F, and write R_{1}, …, R_{q} for the minimal invariant sets of the group F σ^{−1} ∈ G, ordered such that

({1}, …, {d}) ⪯ (R_{1}, …, R_{q}).

Then (p, ε) ∼ (p′, ε′) if and only if p = p′ and ε|_{R_{j}} = ±ε′|_{R_{j}} for each R_{j}.

Proof. The matrix J_{p} may be obtained from g(p, ε) by replacing off-diagonal entries with their absolute values. Since p ↦ J_{p} is one-to-one, it follows that g(p, ε) determines p uniquely. Thus (p, ε) ∼ (p′, ε′) implies p = p′ and we need only characterize the relation (p, ε) ∼ (p, ε′).

The fact that p is in the relative interior of F̂ implies that h(p) is in the relative interior of B_{φ(F)}^{Λ}, or in other words, in π^{−1} (W_{+}^{φ(F)}). Therefore J_{p} ∈ \overline{f} (W_{+}^{φ(F)}), which, recalling that φ(F) = (σ^{−1}(R_{1}), …, σ^{−1}(R_{q})), implies

J_{p} = J_{1} ⊕ ⋯ ⊕ J_{q},

where each J_{i} is an |R_{i}| × |R_{i}| Jacobi matrix. With this decomposition, the condition (p, ε) ∼ (p, ε′) becomes

diag(ε) J_{1} ⊕ ⋯ ⊕ J_{q} diag(ε) = diag(ε′) J_{1} ⊕ ⋯ ⊕ J_{q} diag(ε′),

which is evidently equivalent to the condition that, for each R_{i}, ε|_{R_{i}} = ±ε′|_{R_{i}}.

We now define the polyhedral complex of interest.

Definition 31. Let \overline{P}_{d} denote the quotient (P_{d} × E)/ ∼, and define

g̃: \overline{P}_{d} → T^{Λ}

to be the map induced by g, so that g̃([(p, ε)]) = g(p, ε).

Faces of \overline{P}_{d} are sets of the form F̂ × \{ε\} where ε ∈ E and F̂ is a face of P_{d}. Proposition 30 implies that either the relative interiors of two faces F̂ × {ε} and F̂′ × {ε′} are disjoint, or the two faces are equal. And the latter can only happen if F = F′. In the case of a least-dimensional face, a vertex {σ} where σ ∈ S_{[d]}, we have \{σ\} × \{ε\} = \{σ\} × \{ε′\} in \overline{P}_{d} for every ε ∈ E. In other words, \overline{P}_{d} has the same vertices as P_{d}, one for each permutation σ ∈ S_{[d]}. At the other extreme, there are 2^{d−1} distinct faces of \overline{P}_{d} of the form P_{d} × \{ε\}; a given set P_{d} × \{ε\} gets identified in \overline{P}_{d} with the set P_{d} × \{ε′\} only when ε′ = ±ε.

The following result encapsulates the solution to Problem 2. To prove it, we need only verify that the map g̃ is a homeomorphism.

Theorem 32. \overline{P}_{d} is a polyhedral complex over T^{Λ}.

Proof. Since g : P_{d} × E → T^{Λ} is a continuous surjection, g̃ is a continuous bijection by construction. That g̃ is a homeomorphism then follows from compactness of \overline{P}_{d}.

Thus the topology of T^{Λ} is encoded by the polyhedral complex \overline{P}_{d}. Using Proposition 30, the calculation of topological invariants of \overline{P}_{d} is reasonably straightforward; we illustrate this in the next section.

3.5. Illustration of the results, Euler characteristics. In this section we apply the earlier results specifically to 3 × 3 matrices, and we calculate the Euler characteristic of T^{Λ} for an arbitrary d-element set Λ = {λ_{1}, …, λ_{d}} ⊂ R.

To begin, consider the permutahedron P_{d}, the basic unit of the complex \overline{P}_{d}, and let us count the number of faces having a fixed dimension n, where 0 ≤ n ≤ d − 1. A face F̂ of P_{d} has dimension n if and only if the ordered partition

(S_{1}, …, S_{r}) = φ(F)

has r = d − n cells. There are precisely

(50)  (d − n)!S(d, d − n)

such ordered partitions, where S(d, d − n) denotes the Stirling number of the second kind.

Recall that if F, F′ ∈ GS_{[d]} are distinct, then for any ε, ε′ ∈ E so are the faces F̂ × \{ε\}, F̂′ × \{ε\} of \overline{P}_{d}. On the other hand, for fixed F, Proposition 30 tells us precisely how many faces of \overline{P}_{d} there are of the form F̂ × \{ε\} (ε ∈ E). Namely, let N denote the number in question, and write

(σ^{−1}(R_{1}), …, σ^{−1}(R_{q})) = φ(F),

Figure 1. The complex \overline{P}_{3} with an individual facet depicted separately at left. The letters a-h and their negatives indicate the gluing rules for edges of the 16-gon. There are 12 distinct edges (including the four interior ones), 6 vertices and 4 faces.

where σ ∈ F and R_{1}, …, R_{q} are the minimal invariant subsets of F σ^{−1}. Then N is the number of equivalence classes of E modulo the relation

ε|_{R_{j}} = ±ε′|_{R_{j}} for every R_{j}.

That is,

(51)  N = 2^{d}/2^{q} = 2^{n},

where n = d − q is the dimension of F̂ × {ε}. Combining (50) and (51) yields the number of n-dimensional faces of \overline{P}_{d} and hence the following explicit form for the Euler characteristic.

Theorem 33. The Euler characteristic of \overline{P}_{d} is

χ(\overline{P}_{d}) = ∑_{n=0}^{d−1}(−2)^{n}(d − n)!S(d, d − n) = ∑_{q=1}^{d}(−2)^{d−q}q!S(d, q).

We show below that the above value of the Euler characteristic has a simple generating function. But first we discuss the particular complex \overline{P}_{3}. It consists of 2^{3−1} = 4 copies of the regular hexagon P_{3}, glued together according to the relation ∼ as depicted in Figure 1. By Theorem 33 the Euler characteristic is

χ (\overline{P}_{3}) = −2,

which, using Theorem 32 and the standard classification of 2-manifolds, implies:

Theorem 34. T^{Λ} is a two-holed torus whenever Λ is a set of 3 distinct real numbers.

From the point of view of discrete geometry, the polyhedral complexes \overline{P}_{d} seem to be of intrinsic interest, quite apart from their relationship to tridiagonal matrices. For instance, J. Bokowski has made the following observation. See [4, pp.24,25,223] for relevant definitions and comparison with the Platonic solids.

Proposition 35. The Petrie polygon of \overline{P}_{3} covers every edge.

This unusual property can be verified directly in Figure 1. Another remarkable property of the complexes \overline{P}_{d}—and also of the isospectral sets T^{Λ}—is that hyperbolic tangent generates the Euler characteristics.

Theorem 36.

tanh x = ∑_{d=1}^{∞} χ (\overline{P}_{d}) \frac{x^{d}}{d!} .

Proof. According to a theorem of Frobenius [3, p. 244], the so-called Eulerian polynomial of degree d has the representation

p_{d}(u) = u ∑_{r=1}^{d} r!S(d, r)(u − 1)^{d−r}.

It is known [3, p. 259] that

tan x = ∑_{d=1}^{∞} |p_{d}(−1)| \frac{x^{d}}{d!}

= ∑_{d=1}^{∞} i^{d+1}p_{d}(−1)\frac{x^{d}}{d!} ,

where i^{2} = −1. It follows from the relation

tanh x = −i tan(ix)

that

tanh x = ∑_{d=1}^{∞}(−1)^{d}p_{d}(−1)\frac{x^{d}}{d!}

= ∑_{d=1}^{∞} −p_{d}(−1)\frac{x^{d}}{d!} ,

the latter equality because tanh is odd. Comparing Theorem 33 to the Frobenius representation of p_{d} shows −p_{d}(−1) = χ(\overline{P}_{d}).

References

1. Richard Beals, David Sattinger, and Jacek Szmigielski, Peakons, strings and the finite Toda lattice, Communications on Pure and Applied Mathematics 54 (2001), 91–106.

2. Arne Brøndsted, An introduction to convex polytopes, Graduate Texts in Mathematics, vol. 90, Springer-Verlag, New York-Berlin, 1983.

3. Louis Comtet, Advanced combinatorics, revised and enlarged ed., D. Reidel, Dordrecht, Holland, 1974, Translated from the French by J. W. Nienhuys.

4. H. S. M. Coxeter, Regular polytopes, third ed., Dover, New York, 1973.

5. Carl de Boor and Gene H. Golub, The numerically stable reconstruction of a Jacobi matrix from spectral data, Linear Algebra and its Applications 21 (1978), 245–260.

6. P. Deift, L. C. Li, T. Nanda, and C. Tomei, The Toda flow on a generic orbit is integrable, Communications on Pure and Applied Mathematics 39 (1986), 183–232.

7. Hermann Flaschka and Luc Haine, Torus orbits in G/P, Pacific Journal of Mathematics 149 (1991), no. 2, 251–292.

8. Fritz Gesztesy and Barry Simon, M-functions and inverse spectral analysis for finite and semiinfinite Jacobi matrices, Journal d’Analyse Mathématique 73 (1997), 267–297.

9. Peter C. Gibson, Inverse spectral theory of finite Jacobi matrices, Transactions of the American Mathematical Society (2002), 1–47, To appear.

10. Carlos Tomei, The topology of isospectral manifolds of tridiagonal matrices, Duke Mathematical Journal 51 (1984), no. 4, 981–996.

11. Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer, Berlin, 1995.

Peter C. Gibson, Department of Mathematics, University of Washington, Seattle, WA 98195-4350, USA