# A Borg–Levinson theorem for trees

B.M Brown, R Weikard

## Abstract

We prove that the Dirichelet-to-Neumann map for a Schrödinger operator on a finite simply connected tree determines uniquely the potential on that tree.

## 1. Introduction

Recently there has been much interest in the inverse spectral problem for the one dimensional Sturm–Liouville problemwhere l may be either finite or infinite. More precisely the problem is to recover q from spectral data. Borg (1946) and Levinson (1949) showed when q was real that it is uniquely determined by the associated Titchmarsh–Weyl function. Local versions of this theorem have recently been proved by Simon (1999), Gesztesy & Simon (2000) and Bennewitz (2001), the latter theorem being the result of an elegant and short proof. In the case of complex q, Brown et al. (2002) have shown, using a method modelled on the approach in Bennewitz (2001), that the local Borg theorem is still true. In the case of real q mention must also be made of the famous result of Gel'fand & Levitan (1951) who showed that q could be determined by the spectral function which in the case of a finite interval can itself be determined by two sets of eigenvalues.

The study of the Sturm–Liouville problem on an interval has been extended to its consideration on trees. This has been motivated by quantum models in both physics and chemistry see for instance (Exner et al. 1988; Gerasimenko 1988; Gerasimenko & Pavlov 1988; Bulla & Trenkler 1990). In the case of real coefficients the self-adjoint extensions of symmetric operators on trees have been studied by Carlson in Carlson (1998) and their self-adjoint extensions characterized. Treelike domains have been used to model the scattering problem for partial differential equations (Melnikov & Pavlov 2001), while in a series of papers (Evans & Saitō 2000; Evans et al. 2001) the authors study PDE problems on domains with fractal boundaries and reduce the study of these problems to ones on trees. Further, a recent result of Carlson (1997) has shown that on an infinite homogeneous tree the spectrum of the free Laplacian consists of bands and gaps and possibly eigenvalues. Sobolev & Solomyak (2002) have studied the effect of introducing a real perturbation of the zero potential on such an infinite homogeneous tree when the coupling constant tends to infinity. A further impetus has been given to these studies by the requirements in micro electronics fabrication problems, in particular the construction of quantum switches and other nano-computational devices (see Mikhailova et al. 2002; Mikhaylova & Pavlov 2002; Pavlov 2002) where scattering problems on trees have been studied. In a recent paper, Pivovarchik (2000) considers the inverse spectral problem of the recovery of the coefficients of the Sturm–Liouville problem on a domain consisting of three intervals together with appropriate interface and boundary conditions. He shows that given the spectrum of the problem on the tree together with the Dirichlet problems on each edge, the coefficients of the Sturm–Liouville problem may be recovered. For further references the reader may consult the January 2004 issue of Waves in Random Media where a special section on quantum graphs appeared.

The approach in Borg (1946) and Levinson (1949) is to show that the Titchmarsh–Weyl m-function determines uniquely the function q in the case of a one-dimensional Schrödinger equation. Nachman et al. (1988) have shown an analogous result in the case of a multi-dimensional Schrödinger equation on a bounded domain using the Dirichlet-to-Neumann map instead of the m-function. Curtis & Morrow (1990, 1991) have a similar result for the (combinatorial) problem of a resistor network. We will show here that this is the right idea also for treelike domains following the approach in Bennewitz (2001) and Brown et al. (2002).

More precisely, in this paper we shall study the inverse spectral problem for the Sturm–Liouville problemon each branch of a finite tree where the qj are complex-valued and integrable and where continuity and Kirchhoff type conditions for the solutions and their derivatives are imposed at the internal branch points. We shall follow the approach in Brown et al. (2002) adapted to the tree domain with the m-function being replaced by the Dirichlet-to-Neumann map. The main result of this paper is the following theorem (cf. §§2 and 3 for precise definitions).

Let q be a complex-valued integrable potential supported on a simply connected finite tree. Then the associated (generalized) Dirichlet-to-Neumann map uniquely determines the potential almost everywhere on the tree.

Section 2 contains basic definitions and a formulation of the Sturm–Liouville problem on a tree through interface conditions between the branches. Section 3 defines the Dirichlet-to-Neumann map while §4 discusses the structure of the Green's function for this problem. The Weyl solution is introduced in §5 and its asymptotics are obtained. Section 6 shows how the Dirichlet-to-Neumann map may be used to recover the coefficients of boundary edges while an induction argument in §7 shows how the remaining coefficients are also determined by the map. An appendix contains the asymptotics of the basic solutions on an interval.

## 2. Preliminaries

### (a) Trees

For j=1,…,r let ϵj be homeomorphisms defined on [0,1]. The Hausdorff spaceis called a directed finite tree if it is simply connected and if ϵj(t)=ϵk(s) happens only if j=k or if t,s∈{0,1}. The points ϵ1(0), ϵ1(1),…,ϵr(0), ϵr(1) are called vertices. The set of all vertices is denoted by V. It contains precisely r+1 elements. The images of the functions ϵj are called edges. The structure of the tree is described uniquely by specifying the vertices connected by each edge, i.e. by the setA vertex is called a boundary vertex if it belongs to only one edge. Such an edge will be called a boundary edge. A vertex which belongs to several edges is called an internal vertex. An edge both of whose endpoints are internal vertices is called an internal edge. Without loss of generality we assume that the boundary edges are labelled 1,…,n0 when n0 denotes the number of boundary vertices. We will also assume that the boundary vertices are given by vj=ϵj(0), j=1,…,n0.

### (b) The interface conditions

An integrable function y on T may be represented as y=(y1,…,yr)T, where yj(t)=y(ϵj(t)).

If q is an integrable function on T we are interested in problems associated with the differential expression L given by . We impose the following requirements on y.

1. For each j the functions yj and are absolutely continuous on [0,1].

2. For each j the function is in L2([0,1]).

3. y is continuous on T.

4. For each internal vertex vk the Kirchhoff condition

holds.

Conditions (iii) and (iv) are called interface conditions.

If νk edges meet at vertex vk then these are precisely νk conditions. Therefore, every internal edge gives rise to two conditions and every boundary edge gives rise to one condition. Altogether there are therefore 2r −n0 interface conditions.

To represent the interface conditions we introduce next the following operators which map C1([0,1])n to (any n):The interface conditions are then given as y=0, where is a (2rn0r matrix whose entries are zeros or ±E0,…,±D1. Note that the first n0 columns of correspond to boundary edges. Therefore, these columns will not involve E0 or D0.

For example, for the tree given by ((v1, v4), (v2, v4), (v3, v4)) we have r=3, n0=3 andFor the tree given by ((v1, v3), (v2, v4), (v3, v4)) we have r=3, n0=2 andDenote by cj(λ, .) and sj(λ, .) the solutions of satisfying initial conditions and . Note that cj(., x) and sj(., x) are entire functions of growth order 1/2 at most. Now any solution of can be written aswhen aj and bj denote appropriate constants. The column (a1,…,ar, b1,…,br)T will be denoted by ξ.

We introduce the following matricesand the block matricesandThen we have

## 3. The generalized Dirichlet-to-Neumann map

We will show below that for all but countably many values of λ there will be a unique solution of Ly=λy satisfying the Dirichlet boundary conditions yj(0)=fj for j=1,…,n0. One may then compute the values . The relationship between the fj and the gj is linear and is called the Dirichlet-to-Neumann map. Instead of Dirichlet and Neumann data we will consider general linear boundary conditions described by n0 pairs and n0 pairs which satisfy the relationship(3.1)for j=1,…,n0. More precisely, given the unique solution of Ly=λy satisfying the non-homogeneous boundary conditions (which exists for all but countably many values of λ) we compute the values and call the corresponding linear map the generalized Dirichlet-to-Neumann map which we will denote by Λ. The goal of this section is to compute it.

The boundary conditions are described by the equation y=f, where is the n0×r matrix (boundary operator)and where . We also define the matricesas well asandFinally, letandThe 2r×2r matrix M is of central importance. Its determinant det M is an entire function of λ whose zeros are the eigenvalues of the boundary value problem determined by the αj and . Hence there are at most countably many eigenvalues which cannot have a finite accumulation point. Note that =Pf, wherewhen ξ is the vector of coefficient of the basis functions cj and sj as described in §2b.

Now we haveHence the generalized Dirichlet-to-Neumann map is

## 4. Green's function

We want to obtain a solution of the non-homogeneous system of equations Ly=h, where hL2(T) and where y is subject to the homogeneous boundary conditions y=0 as well as the interface conditions y=0.

Let h(t) denote the column (h(ϵ1(t)),…,h(ϵr(t)))T. DefinewhereandThen the general solution of Ly=h may then be represented asSince y=0 is equivalent to +K=0 we obtainBefore we proceed we need to determine the vector K. To this end we write =0+1, where 0 involves the operators E0 and D0 only while 1 involves the operators E1 and D1 only. Then we have 0K=0. Suppressing the λ-dependence for a while we see thatand, since Therefore,where M0=0(C, S).

Let H be the Heaviside function, i.e. H(t) equals zero or one depending on whether t is negative or positive. ThenThe Green's function Γ is now the term in brackets in the integrand on the right-hand side of this equation. Since we haveNext let 1≤kn0. ThenSince the only entry in column k of 0 is situated in row k we obtain that the kth and (k+r)th columns of M0(λ) equal and −αkek, respectively.1 HenceIf we compute the determinant of M by expanding with respect to row k (which contains at most two non-zero entries) we obtainwhere mrk,j(M) denotes the minor of M obtained by deleting row k and column j. The minors may be expressed by the corresponding entries of M−1. Therefore,Since we also havewe obtainHencewhereandNote θk(., t) and ϕk(., t) are entire functions of growth order 1/2 at most.

## 5. Weyl solutions

Fix k∈{1,…,n0}. Let ψ(k, λ, .) be the solution of the problem Ly=λy, y=0, y=ek . We call this solution the Weyl solution for the boundary vertex k. The Weyl solutions are uniquely determined for any λ which is not an eigenvalue of the boundary value problem determined by the αj and . Recall that these are the roots of the determinant of M and hence the poles of Λ.

Fix k, j∈{1,…,n0}. The Weyl solution for the boundary vertex k satisfies

Note that for appropriate values of aj and bj. Hence, using equation (3.1)and ▪

In the following lemma and its proof we will use different conventions on labelling and orienting boundary vertices and boundary edges of trees as before. We will designate one of the boundary vertices as the root of the tree and denote it by v0. All other boundary vertices will then be called branch tips. The edge attached to the root, denoted by ϵ0, will be called the stem. Nothing will be assumed about the orientation of boundary edges. Note that every vertex v is connected to another vertex v′ by a unique sequence of edges. The number of these edges will be called the distance between v and v′ and will be denoted by d(v, v′). The numberis called the height of the tree with respect to the root v0. (The height of a tree depends on which boundary vertex is designated as root.)

We denote the outward normal derivative of a differentiable function at one of the end points by and , i.e. we defineFinally, we will call a ray in the complex plane admissible if it emanates from zero and lies otherwise in the open upper half plane.

Suppose T is a tree with root v0 and ψ(λ, .) satisfies the differential equation Ly=λy and the interface conditions y=0. Also assume that ψ(λ, .) is zero at the branch tips but not identically zero on T. Then, as tends to infinity along an admissible ray,(5.1)where ψ0(λ, t)=ψ(λ, ϵ0(t)) and p∈{0,1} is such that ϵ0(p)=v0.

The proof is by induction on the height of the tree. Assume that the height of T with respect to v0 is one (i.e. T is an interval). If v0=ϵ0(1) then ψ0(λ, t)=b0s0(λ, t) for some non-zero b0 and, using lemma A 1,If v0=ϵ0(0) then where . Using again lemma A 1 we findNext assume that equation (5.1) is true for every tree whose height is at most n and that T has height n+1 with respect to v0. In addition to the stem itself there are k subtrees attached to the internal endpoint v1 of the stem. We designate v1 to be the root of each of these subtrees and we assign labels 1,…,k to their stems. We also assume that v1=ϵj(1) for j=1,…, and v1=ϵj(0) for j=+1,…,k.

First, assume again v0=ϵ0(1). Then , where a0=ψ(λ, v1) and whereEmploying the induction hypothesis we obtain and thus, using lemma A 1,If, however, v0=ϵ0(0) then , where and where, using the induction hypothesis,Solving for a0 and b0 and a final application of lemma A 1 gives ▪

The preceding lemma has the following immediate corollary for a Weyl solution if t=0. For t∈(0,1) one simply has to apply the lemma to the tree whose stem is ϵk([t,1]) rather than ϵk([0,1]).

If k∈{1,…,n0} and t∈[0,1) thenas tends to infinity along an admissible ray.

If k∈{1,…,n0} and t∈[0,1) then the diagonal Green's function Γk,k(λ, t, t) tends to zero as tends to infinity along an admissible ray.

By lemma 5.1 we have and that the Wronskian of ψk(k, λ, .) and ϕk(λ, .) equals the Wronskian of θk(k, λ, .) and ϕk(λ, .) and hence 1. Therefore, as tends to infinity,using lemma A 1 for the first term and corollary 5.3 for the second. ▪

## 6. The potential on the boundary edges

The (generalized) Dirichlet-to-Neumann map determines uniquely the potential almost everywhere on the boundary edges.

Fix k∈{1,…,n0} and t∈[0,1). Suppose q and are two potentials on T giving rise to the same (generalized) Dirichlet-to-Neumann map. Associated with are the functions , , and just like θ, ϕ, ψ and Λ are associated with q. From lemma A 1 we know that tends to one as λ tends to infinity. This fact and theorem 5.4 yieldas tends to infinity along an admissible ray. Recall that and, by assumption, . Therefore we find thatAs noted earlier all of the four terms appearing here on the right-hand side are entire functions of growth order 1/2 when viewed as functions of λ. Thus g is an entire function of growth order 1/2, which tends to zero along the positive and the negative imaginary axis (for instance). The Phragmén–Lindelöf theorem implies that g is bounded in , so it is constant by Liouville's theorem and in fact identically equal to zero, i.e.Since t∈[0,1) was arbitrary this equation holds for all t∈[0,1) and for all . Differentiating both sides with respect to t gives . Differentiating once more gives . Differentiating a third time gives finallyalmost everywhere on [0,1]. ▪

## 7. Pruning the tree

Let T be a tree with n0 boundary edges, q a potential on T and Λ the associated Dirichlet-to-Neumann map. Let v* be a vertex such that all but one of the edges attached to v* are boundary edges. Assume the number of these boundary edges is r* and that the labels of their boundary vertices are n0r*+1,…,n0. Let T* be the tree with the boundary edges just mentioned removed so that its boundary vertices are , and v*. Then the Dirichlet-to-Neumann map Λ* for T* is uniquely determined by Λ and the restriction of the potential q to the boundary edges attached to v*.

We have to compute the values Λ*f* for an arbitrary vector . We will do this for any value of λ which is not an eigenvalue for the Dirichlet problem for T nor an eigenvalue for the Dirichlet problem for T*. It is clearly sufficient to consider only these λ as we are missing at most countably many. Note that we may assume that the functions c(λ, .) and s(λ, .), and hence the function are known for all and all since we know the potentials on the corresponding edges.

Next we want to show that there is a such that . Assume that ψ(n0, λ, v*)=0. Since λ is not an eigenvalue for T* we have that is the zero function. Hence there must be a such that is not identically equal to zero. For this k we have, using lemma 5.1,i.e. sk(λ, 1)=0 and thus ck(λ, 1)≠0. HenceNow definefor some number γ yet to be determined. Then Χ(λ, .) has Dirichlet data given by the vectorand has Dirichlet data given by the vector f* provided that , i.e. ifSince ψk(k, λ, 1)≠0 we may (and will) choose γ such that this condition is satisfied. ThereforeMoreover, by the Kirchhoff conditions,where the right-hand side involves only known quantities. ▪

We are now in a position to prove theorem 1.1.

Proof of theorem 1.1. Let Λ be the generalized Dirichlet-to-Neumann map given. Then the Dirichlet-to-Neumann map ΛD–N itself is given byHence we may assume without loss of generality that the given map is the Dirichlet-to-Neumann map. Theorem 6.1 gives q on the boundary edges. If we can show the existence of an internal vertex with the properties of the vertex v* in theorem 7.1 we may use that theorem to show that the Dirichlet-to-Neumann map is now given on the tree where certain edges are removed. Induction then completes the proof.

To show the existence of v* recall the concepts introduced before lemma 5.2 and designate any boundary vertex as the root of the tree. Suppose that the tree has height h with respect to the root. Then any vertex whose distance from the root is h−1 (we may, of course, assume that h>1) has the properties of v*, i.e. all but one of the edges attached to it are boundary edges. ▪

## Acknowledgments

We are indebted to the referees for many useful comments which led to a greatly improved presentation and the abolition of a number of mistakes.

## Appendix A Asymptotics of basic solutions

Let qL1([0,1]). Suppose that u(λ, .) solves the equationy″+qy=λy. Defineand . Then, for all x∈[0,1] and all complex λ≠0,

Without loss of generality we choose the root of λ in the open upper half plane or the positive real axis. Let and defineReplacing u by u0+(uu0) in the variation of constants formulaone finds(A1)Let , move the first term on the right of (A 1) to the left, and multiply with |q(t)|exp(−ϕ(t)). This will produce total derivatives on either side so that integration from 0 to x yieldsUsing this estimate in (A 1) gives the desired estimate on uu0. The statement on follows from this and the derivative of the variation of constants formula. ▪

We remark that this proof is fairly standard and that it is included here for the convenience of the reader.

## Footnotes

• This material is based upon work supported by the National Science Foundation under grant no. DMS-0304280.

• We denote the vector whose entries are zero save for a 1 at position k by ek.