DISCRETE AND CONTINUOUS DIRICHLET-TO-NEUMANN MAPS IN THE LAYERED CASE

DAVID V INGERMAN

Abstract. Every sufficiently regular non-negative function γ (conductivity) on the closed unit disk \overline{𝔻} induces the Dirichlet-to-Neumann map Λ_{γ} on functions on ∂𝔻. The main forward problem is to give a characterization of the maps Λ_{γ}. The main inverse problem is to find out when Λ_{γ} uniquely determines γ. In this paper we consider the case of conductivities that are constant on circles centered at the origin, and a discrete analog of this, so called, layered case. We characterize the set of the layered Dirichlet-to-Neumann maps in terms of their kernels and spectra. We also give sharp conditions on γ for the uniqueness in the inverse problems. The characterization in terms of the spectra shows that continuous Dirichlet-to-Neumann maps can be viewed as limits of the discrete Dirichlet-to-Neumann maps. The characterization in terms of the kernels supports the conjecture in [8] that the alternating property essentially characterizes continuous Dirichlet-to-Neumann maps. The chracterizations above give a new interpretation of connections between positive measures, positive definite functions and analytic functions that map the right half plane to itself in the Bochner and Herglotz theorems.

1. Introduction

We first give a short outline of the paper. Precise definitions and theorems are in the next section.

Every sufficiently smooth positive function γ on the closed unit disk \overline{𝔻} induces the Dirichlet-to-Neumann map Λ_{γ} from functions on the boundary of the disk ∂𝔻 to functions on ∂𝔻. There are two main problems connected with the maps Λ_{γ}:

• The forward problem is to give a characterization of the Dirichlet-to-Neumann maps. (A necessary condition is known: it was shown in [8] and [4] that if γ ∈ C^{2}(\overline{𝔻}) then Λ_{γ} has, so called alternating property, which can be thought of as a generalized Hopf’s lemma property.)

• the inverse problem, so called the impedance tomography problem, is to recover γ from Λ_{γ}. (A sufficient condition for uniqueness is known: It was recently proved in [13] that Λ_{γ} uniquely determines γ for γ ∈ W^{2,p}(\overline{𝔻}) ⊂ C^{3}(\overline{𝔻}), p > 1.)

Great progress in understanding of the discrete analogs (Dirichlet-to-Neumann maps on graphs) of these problems, was made in [3] and [2]: it was shown

Supported by an Alfred P. Sloan Research Fellowship.

that the discrete analog of the alternating property essentially characterizes the discrete Dirichlet-to-Neumann maps. Also the discrete inverse problem was completely solved. The success in understanding the discrete problems gives one of the main motivations of this paper: to show a strong connection between properties of the continuous and discrete Dirichlet-to-Neumann maps.

In this paper we consider the case of conductivities that are constant on circles centered at the origin. We also consider a discrete analog of this, so called, layered case. We obtain a clear picture of the sets of both discrete and continuous Dirichlet-to-Neumann maps in this case. We characterize them in terms of their kernels and spectra.

The characterization in terms of the spectra shows that continuous Dirichletto-Neumann maps can be viewed as limits of the discrete Dirichlet-to-Neumann maps.

The characterization in terms of the kernels supports the conjecture in [8] that the alternating property essentially characterizes continuous Dirichletto-Neumann maps.

We also give sharp conditions on γ for the uniqueness in the continuous inverse problem. For the discrete case, we give a new algorithm, based on the Pick-Nevalinna Interpolation theorem, for the recovery of γ.

The characterizations above give a physical interpretation of the connection between positive measures, positive definite functions and analytic functions from the right half-plane to itself: these objects describe, respectively, spectral measures, kernels and spectra of Dirichlet-to-Neumann maps in the layered case.

2. Background and Main Results

2.1. Basic definitions. We first give the definition of Dirichlet-to-Neumann maps as it is usually done, see [17] for details. For the layered case, which we will consider, the restrictions on γ will be weakened, and the domain of Λ_{γ} will be shrunk.

Let γ ∈ C^{1,1}(\overline{𝔻}). A function u ∈ H^{1}(𝔻) is called \underline{γ-harmonic} function or \underline{potential} if

div(γ∇u) = 0 in 𝔻. (2.1)

A potential in 𝔻 satisfies this equation if there are no sources or sinks of current in 𝔻.

For each f ∈ H^{1/2}(∂𝔻) there exists a unique γ-harmonic function u such that u|_{∂𝔻} = f. The Dirichlet-to-Neumann corresponding to γ maps the boundary values of a γ-harmonic function (Dirichlet data) to the current

flux γ \frac{∂u}{∂r}|_{r=1} at the boundary (Neumann data). In symbols

Λ_{γ} = γ \frac{∂u}{∂r}|_{r=1},

where u is γ-harmonic and u|_{∂𝔻} = f. The operator Λ_{γ} : H^{1/2}(∂𝔻) → H^{−1/2}(∂𝔻) is a self-adjoint pseudodifferential operator of order 1.

A discrete analog of the disk 𝔻 is a \underline{circular planar} graph. It is a finite graph Γ = (V, E, ∂Γ) imbedded into \overline{𝔻}, where the set V is the set of nodes of the graph, the set E is the set of edges of Γ, and ∂Γ = V ∩ ∂𝔻 is the non-empty set of \underline{boundary} nodes of Γ. The set V − ∂Γ is the set of \underline{interior} nodes of Γ. A conductivity γ is a positive function on the edges of Γ.

A function u on the nodes of Γ is γ-harmonic if at every interior node p it satisfies Kirchhoff’s law, that is: the total current I_{u}(p) out of p is zero:

I_{u}(p) = ∑_{pq∈E} γ(pq)(u(p) − u(q)) = 0. (2.2)

This tells that the value of u at p is the weighted average of the values of u at the neighbors of p (neighbors are the nodes q of the graph for which pq ∈ E). It follows that γ-harmonic functions satisfy the maximum and the minimum principles. From now on we will only consider the graphs in which every interior node is topologically connected to at least one boundary node. On such graphs (and only on them) each γ-harmonic function u is uniquely determined by its values u|_{∂Γ} on the boundary of Γ. The discrete Dirichletto-Neumann map Λ_{γ} is the linear map that sends the boundary values f of a γ-harmonic function u to the corresponding total current out of nodes at the boundary I_{u}|_{∂Γ}. Or algebraically,

Λ_{γ}f(p) = I_{u}(p) = ∑_{pq∈E} γ(pq)(u(p) − u(q)), p ∈ ∂Γ, (2.3)

where u is γ-harmonic and u|_{∂Γ} = f.

2.2. Alternating property. One of the main motivations of this paper is to show a strong connection between properties of discrete and continuous Dirichlet-to-Neumann maps. An important step in this direction has been made in [8], [3] and [4], where it was shown that both discrete and continuous Dirichlet-to-Neumann maps have the \underline{alternating property}.

Theorem 2.1 (see [8] and [4]). Let Λ_{γ} be a Dirichlet-to-Neumann map for γ ∈ C^{2}(\overline{𝔻}). Then Λ_{γ} has the alternating property. That is:

Let A and B be a pair of disjoint intervals on ∂𝔻 and f ∈ C^{∞}(∂𝔻), such that suppf ⊂ A. Then for any m distinct points b_{1}, b_{2}, …, b_{m} ∈ B, numbered \underline{clockwise}, such that

(−1)^{i}Λf(b_{i}) > 0

there exists m distinct points a_{1}, a_{2}, …, a_{m} ∈ A numbered \underline{counterclockwise}, such that

(−1)^{i}f(a_{i}) < 0.

b_{1} b_{2} b_{3} b_{4} a_{2} a_{4} a_{3} a_{1}

This picture shows the main idea of the proof: the pattern of the directions of the current flux Λ_{γ}f on B together with the maximum and minimum principles garantee the existence of non-intersecting curves from b’s on which potential alternates in sign. Since suppf ⊂ A these curves have to terminate at A. See [8] for a detailed proof.

The same argument can be applied to the discrete case. In fact the discrete version of the alternating property, which we define next, essentially characterizes the discrete Dirichlet-to-Neumann maps.

We identify the space of real functions on ∂Γ with ℝ^{n}, where n is the number of points in ∂Γ.

Theorem 2.2 ([3]). A self-adjoint linear map Λ : ℝ^{n} → ℝ^{n} is a Dirichletto-Neumann map of a circular planar graph if and only if Λ1 = 0 and Λ has the discrete alternating property, that is:

Let A, B be a pair of disjoint intervals on ∂𝔻 and f a function on ∂Γ with suppf ⊂ A. Then for any m points (2m ≤ n) b_{1}, b_{2}, …, b_{m} ∈ B ∩ ∂Γ, numbered clockwise and such that

(−1)^{i}Λf(b_{i}) > 0

there exist m distinct points a_{1}, a_{2}, …, a_{m} ∈ A∩∂Γ, numbered counterclockwise such that

(−1)^{i}f(a_{i}) < 0.

2.3. Right sign property. The following algebraic description of the alternating property turned out to be very useful. To state it we consider the \underline{kernel} of Λ_{γ}.

For a discrete Dirichlet-to-Neumann map Λ_{γ} its kernel is the matrix that represents the linear operator Λ_{γ}.

The kernel of a continuous Dirichlet-to-Neumann map is the distribution K(ϕ, θ) on ∂𝔻 × ∂𝔻 such that

Λ_{γ}f(ϕ) = ∫_{0}^{2π} K(ϕ, θ)f(θ)dθ. (2.4)

The existence of K is garanteed by the fact that Λ_{γ} is a pseudodifferential operator. In fact for γ ∈ C^{2}(\overline{𝔻}) K is a continuous function off the diagonal of ∂𝔻 × ∂𝔻, and the singularity at the diagonal is of order 2. (see [8]) The following theorem shows the equivalence of the alternating property of an operator Λ and the algebraic property of the kernel of Λ.

Theorem 2.3 ([3]). A symmetric matrix Λ is the kernel of a linear operator Λ : ℝ^{n} → ℝ^{n} that has the alternating property if and only if the kernel of Λ has the discrete \underline{right sign} property. That is:

for any two disjoint intervals A, B ⊂ ∂𝔻 and any 2m (2m ≤ n) distinct points a_{1}, a_{2}, …, a_{m} ∈ A ∩ ∂Γ, b_{1}, b_{2}, …, b_{m} ∈ B ∩ ∂Γ, (as before a’s are numbered counterclockwise and b’s are numbered clockwise)

det{−Λ(b_{i}, a_{j})}_{i,j=1}^{m} ≥ 0.

A continuous analog of this theorem was recently proved in [8].

Theorem 2.4. Let K be a distribution on ∂𝔻 × ∂𝔻 such that K is continuous off the diagonal and has a singularity of order 2 on the diagonal. Then the operator

Λf = ∫ Kf

has the alternating property if and only if K has the continuous \underline{right sign} property. That is:

for any two disjoint intervals A, B ⊂ ∂𝔻 and any 2m distinct points a_{1}, a_{2}, …, a_{m} ∈ A, b_{1}, b_{2}, …, b_{m} ∈ B, (a’s and b’s are numbered as above)

det{−K(a_{i}, b_{j})}_{i,j=1}^{m} > 0.

2.4. The layered case and the admittance function. In this paper we consider the case of conductivities that are constant on circles centered at the origin.

We now introduce a discrete analog of the continuous layered situation. The \underline{discrete disks} are connected circular planar graphs D(n, l) and D^{∗}(n, l) of the following shapes:

D^{∗}(11, 4) D(11, 6) D(11, 5) D(11, 5) D^{∗}(11, 5)

where n is the number of radial lines and l is the number of \underline{layers}. The layers of the graphs D(n, l) and D^{∗}(n, l) are minimal subsets of edges invariant

under rotations of the graph by the angle \frac{2π}{n}. Each layer consists of n edges. We assume that the conductivity γ is constant on layers. Therefore, the layered conductivity is determined by l positive numbers.

We first describe the effect that the assumed form of γ has on Λ_{γ}. In both discrete and continuous situations the γ-harmonic functions are still γ-harmonic after rotations and reflections with respect to the origin. Therefore, the discrete and continuous Dirichlet-to-Neumann maps, corresponding to the layered conductivities γ, commute with rotations and the reflections of functions on the boundaries. For the continuous case it immediately follows that Dirichlet-to-Neumann maps commute with the Laplacian on the

boundary of the disk \frac{d^{2}}{dθ^{2}}. With a little more effort one gets that Λ_{γ}1 = 0 and

Λ_{γ}e^{±ikθ} = R(k)e^{±ikθ}, k ∈ ℕ. (2.5)

We call the function R the \underline{admittance} function. Its values at positive integers uniquely determine Λ_{γ}. This reduction of layered Dirichlet-to-Neumann maps to one-dimensional objects gives us a way to interpret the notion of γ-harmonic functions when γ is a positive measure. (see Section 3.1 and 3.2) The corresponding Λ_{γ}’s will map trigonometric polynomials to trigonometric polynomials.

We now will make sense of the admittance function for the discrete Dirichlet-to-Neumann maps. The discrete version of the Laplacian on the boundary of a discrete disk D(n, l) or D^{∗}(n, l) is given by the n × n matrix of the form

[\frac{d^{2}}{dθ^{2}} ] = − ( \begin{matrix}2 & −1 & 0 & 0 & … & 0 & 0 & −1 \\ −1 & 2 & −1 & 0 & … & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & … & −1 & 2 & −1 \\ −1 & 0 & 0 & 0 & … & 0 & −1 & 2 \end{matrix} ) .

It makes the calculations cleaner if we assume that n is odd. Throughout this section we let n = 2m + 1, m ∈ N. We define

∂_{n} = \{\frac{2πj}{n}, j = −m, …, 0, …, m\} (2.6)

Direct calculation shows that [\frac{d^{2}}{dθ^{2}} ] is diagonal in the orthogonal basis

e^{ikθ}|_{∂_{n}}, k = −m, …, 0, …, m

with the eigenvalues

−|e^{i \frac{2πk}{n}} − 1|^{2}, k = −m, …, 0, …, m

We define

ω_{k}^{(n)} = ω_{−k}^{(n)} = |e^{i \frac{2πk}{n}} − 1|, k = −m, …, 0, …, m. (2.7)

Note that

lim_{n→∞} \frac{n}{2π}ω_{k}^{(n)} = |k|.

The discrete Λ_{γ} commute with [\frac{d^{2}}{dθ^{2}} ] and we get that the eigenvectors of the discrete Dirichlet-to-Neumann maps are the restrictions of the eigenfunctions of the continuous Dirichlet-to-Neumann maps to the boundaries of the discrete disks. In symbols:

Λ_{γ}e^{±ikθ}|_{∂_{n}} = R(ω_{k}^{(n)})e^{±ikθ}|_{∂_{n}}, k = 1, …, m. (2.8)

2.5. Characterization of admittance functions. Now, to see how ”close” the discrete and continuous Dirichlet-to-Neumann maps are we need to describe their possible eigenvalues. We will give the descriptions by characterizing the discrete and continuous admittance functions.

The discrete admittance functions will turn out to be of the form of the Stieltjes’ continued fractions:

R(λ) = \frac{1}{\frac{1}{γ_{l}} + \frac{1}{γ_{l−1}λ^{2} + ⋯ + \frac{1}{\frac{1}{γ_{3}} + \frac{1}{γ_{2}λ^{2} + \frac{1}{\frac{1}{γ_{1}}}}}}} (2.9)

B where γ_{i}’s are the conductivities on the layers of the discrete disks. This explicit formula will allow us to show a one-to-one correspondence between the admittance functions of discrete disks with l layers and the Blaschke products of degree l. (This correspondence together with the Pick-Nevanlinna interpolation theorem is a key to the discrete inverse problem, see Section 4.3).

It follows from (2.9) that

β(λ) = \frac{R(λ)}{λ} (2.10)

has a natural extension to an analytic function from the right half-plane ℂ^{+} to itself. We define

𝔅 = {β : ℂ^{+} → ℂ^{+} : β is analytic, β(λ) > 0 for λ > 0}.

Applying the Pick-Nevanlinna Interpolation theorem, (see [12],[16]), we will prove

Theorem 2.5. A linear map Λ : ℝ^{n} → ℝ^{n} is the Dirichlet-to-Neumann map of a discrete disk if and only if Λ is diagonal in the orthogonal basis

e^{ikθ}|_{∂_{n}}, k = −m, …, 0, …, m,

Λ1 = 0 and there is a function β in 𝔅 such that

Λe^{±ikθ}|_{∂_{n}} = ω_{k}^{(n)}β(ω_{k}^{(n)})e^{±ikθ}|_{∂_{n}}, k = 1, …, m.

In other words the set of the Dirichlet-to-Neumann maps is equal to

\{\sqrt{−[\frac{d^{2}}{dθ^{2}} ]}β(\sqrt{−[\frac{d^{2}}{dθ^{2}} ]}) : β ∈ 𝔅\}. (2.11)

It turns out that a continuous analog of this theorem is true. (Our proof heavily uses the characterization of spectral measures of inhomogenuous strings done by Krein and Kac [9], see also [5].)

Theorem 2.6. A linear map Λ : ∂𝔻 → ∂𝔻 is the Dirichlet-to-Neumann map of the unit disk with a layered conductivity if and only if Λ is diagonal in the orthogonal basis

e^{ikθ}, k ∈ ℤ,

Λ1 = 0 and there is a function β in 𝔅 such that

Λe^{±ikθ} = kβ(k)e^{±ikθ}, k ∈ ℕ.

In other words the set of the Dirichlet-to-Neumann maps is equal to

\{\sqrt{−\frac{d^{2}}{dθ^{2}}} β(\sqrt{−\frac{d^{2}}{dθ^{2}}} ) : β ∈ 𝔅\}. (2.12)

2.6. The ”γ ↔ \frac{1}{γ} ” duality. We note, without a proof, that the following identity is true, (see [9] or [5])

Λ_{γ}Λ_{\frac{1}{γ}} = Λ_{\frac{1}{γ}} Λ_{γ} = −\frac{d^{2}}{dθ^{2}} .

Definition 2.7. Two disks D_{γ}(n, l) and D∗_{\frac{1}{γ}} (n, l) with conductivities on

layers respectively \{δ_{1}, ξ_{1}, δ_{2}, ξ_{2}, δ_{3}, … \} and \{\frac{1}{δ_{1}} , \frac{1}{ξ_{1}} , \frac{1}{δ_{2}} , \frac{1}{ξ_{2}} , \frac{1}{δ_{3}} , … \} are called \underline{dual}.

We will show that

Λ(D∗_{\frac{1}{γ}})Λ(D_{γ}) = Λ(D_{γ})Λ(D∗_{\frac{1}{γ}}) = −[\frac{d^{2}}{dθ^{2}} ].

Remark We find the following result amusing. It was motivated by a question of G. Uhlmann. In fact, this question together with the article [16] have stimulated this paper. If γ is identically 1 on \overline{𝔻} then the corresponding Dirichlet-to-Neumann map as an operator is the positive square root of the minus Laplacian on ∂𝔻. In symbols:

Λ_{1} = \sqrt{−\frac{d^{2}}{dθ^{2}}}.

The question: Is

\sqrt{−[\frac{d^{2}}{dθ^{2}}]}

the Dirichlet-to-Neumann map of a circular planar graph? The answer is yes. It is an easy corollary of the Theorem 2.5.

2.7. Approximation of continuous Dirichlet-to-Neumann maps by discrete ones. Remark We note that from the results in [8] it follows that the discrete disks give all possible Dirichlet-to-Neumann maps of circular planar graphs. In particular, the discrete disks with layered conductivity give all possible Dirichlet-to-Neumann maps Λ of circular planar graphs with the eigenvectors e^{±ikθ}|_{∂_{n}}. Therefore, for the purposes of the approximations of continuous Dirichlet-to-Neumann maps of the disk with layered conductivity by the discrete ones, one loses nothing essential considering only the discrete disks with layered conductivity and not all circular planar graphs.

The Pick-Nevalinna Interpolation theorem (see [12]) lets us formulate the following ”continuous is the limit of discrete” theorem.

Theorem 2.8. In the layered case, the eigenvectors of discrete Dirichletto-Neumann maps are restrictions of the eigenfunctions of the continuous Dirichlet-to-Neumann maps.

Let λ_{1}, λ_{2}, …, λ_{k} be the first (corresponding to e^{iθ}, e^{2iθ}, …, e^{ikθ}) eigenvalues of a continuous Dirichlet-to-Neumann map. Then there exist a sequence of discrete disks {D_{n}} with the first eigenvalues λ_{1}^{n}, λ_{2}^{n}, …, λ_{k}^{n} such that

λ_{j} = lim_{n→∞} λ_{j}^{n}, 1 ≤ j ≤ k.

Conversely, let {D_{n}} be a sequence of discrete disks, such that the limits above exist. Then there exists a continuous Dirichlet-to-Neumann map with the first k eigenvalues being equal to the limits.

2.8. Characterization of kernels. Positive definite functions. We will now show the existence and characterize the kernels of the Dirichlet-to-Neumann maps in the layered case. We show the existence by an explicit calculation of the kernel of Λ_{γ} in terms of the corresponding admittance function R(λ). Recall that the layered Dirichlet-to-Neumann maps commute with rotations and reflections (with respect to the origin) of functions. It follows that the kernel of Λ_{γ} has to be of the convolution type:

K(ϕ, θ) = h(ϕ − θ)

where h is a distribution on ℝ such that

h(s) = h(s + 2π) = h(2π − s), s ∈ ℝ

and

∫_{0}^{2π} h(s) cos λsds = R(λ), λ > 0.

To proceed we need the following representation of analytic functions from the right half-plane to the right half-plane.

Theorem 2.9 (Herglotz). A function β is in 𝔅 if and only if for some c, C ≥ 0

β(λ) = Cλ + \frac{c}{λ} + ∫_{0}^{∞} \frac{λ(1 + t^{2})dσ(t)}{λ^{2} + t^{2}}

where σ is a positive measure of bounded variation on (0, ∞).

A straightforward calculation gives us

Lemma 2.10. A distribution K on ∂𝔻 × ∂𝔻 is the kernel of a layered Dirichlet-to-Neumann map Λ_{γ} if and only if

K(ϕ, θ) = h(ϕ − θ)

where h is a distribution on ℝ such that h(s) = h(s+2π) = h(2π −s), s ∈ ℝ,

∫_{0}^{2π} h(s)ds = 0,

and for s ∈ [0, 2π)

h(s) = cδ(0) − Cδ′′(0) + ∫_{0}^{∞} t\frac{e^{−st} + e^{(s−2π)t}}{1 − e^{−2πt}} (1 + t^{2})dσ(t), (2.13)

where c, C ≥ 0 and σ is a positive measure of bounded variation on (0, ∞).

Corollary 2.11. The kernel of a layered Dirichlet-to-Neumann map is C^{∞} off the diagonal.

We will now explain a connection of the characterization in lemma 2.10 with the alternating property.

Definition 2.12. A continuous function f on a possibly infinite interval (a, b) is \underline{positive definite} if

det{f(x_{i} + y_{j})}_{1}^{m} ≥ 0

for all m ∈ ℕ, x_{i} + y_{j} ∈ (a, b).

It follows that f is positive definite on (0, 2π) if and only if the kernel K(ϕ, θ) = f(ϕ − θ) satisfies the right sign property. We are now one step from restating the characterization of the kernels in terms of their right sign property. We need the following classical characterization of the positive definite functions. (see [10])

Theorem 2.13 (Bochner). A continuous function f is positive definite on a possibly infinite interval (a, b) if and only if there exists a positive σ-finite measure ν on ℝ such that

f(x) = ∫_{−∞}^{+∞} e^{xt}dν(t).

We now state one of the main resuls of this paper.

Theorem 2.14. A distribution K on ∂𝔻 × ∂𝔻 is the kernel of a layered Dirichlet-to-Neumann map Λ_{γ} if and only if

K(ϕ, θ) = h(ϕ − θ)

where h is a distribution on ℝ such that h(s) = h(s+2π) = h(2π −s), s ∈ ℝ,

∫_{0}^{2π} h(s)ds = 0, ∫_{0}^{2π} h(s)(cos s − 1)ds < ∞

and h is positive definite on (0, 2π).

2.9. The inverse problems. The continuous inverse problem will be reduced to an inverse Sturm-Liouville problem studied by Krein, (see [9]). We obtain the following result.

Theorem 2.15. If γ(r) is a measurable function on [0, 1] such that for all ϵ > 0

∫_{ϵ}^{1}(γ + \frac{1}{γ})dr < ∞

then γ is uniquely determined by Λ_{γ} a.e.. If for some ϵ > 0 the integral is infinite, then no information about γ on [0, ϵ) can be obtained from Λ_{γ}.

Our main result on the discrete inverse problem can be roughly stated as

Theorem 2.16. A layered conductivity on D(2m + 1, l) or D^{∗}(2m + 1, l) can be recovered from the corresponding Dirichlet-to-Neumann map if and only if l ≤ m.

(See Section 4.3 for a refined version.) Theorem 2.16 follows from the general theory in [3] and [4]. In this paper the proof of the uniqueness and the conductivity recovery algorithm are much simpler due to the assumed form of the conductivity.

Our algorithm shows an intimate connection between the discrete inverse problem and the Pick-Nevalinna interpolation problem.

2.10. The case of a half plane. One often considers the Dirichlet-to-Neumann maps of the lower half plane with a conductivity that is constant on horizontal lines. For that layered case the following results hold.

Theorem 2.17. The set of Dirichlet-to-Neumann maps of the half planes with layered conductivity is equal to

\{\sqrt{−\frac{d^{2}}{dx^{2}}} β(\sqrt{−\frac{d^{2}}{dx^{2}}} ) : β ∈ 𝔅\}.

Theorem 2.18. A distribution K on ℝ × ℝ is the kernel of the Dirichletto-Neumann map Λ_{γ} of the half plane with a layered conductivity if and only if

K(ϕ, θ) = h(ϕ − θ)

where h is a distribution on ℝ such that h(s) = h(−s),

∫_{0}^{∞} h(s)ds = 0, ∫_{0}^{∞} h(s)(cos s − 1)ds < ∞

and h is positive definite on (0, ∞).

3. Continuous problem

Our assumption that γ depends only on r makes it possible to reduce our subject of study to a 1-dimensional one.

3.1. Reduction to a 1-dimensional problem.

Lemma 3.1. The solution to the Dirichlet problem on 𝔻 with the boundary data e^{ikθ}, k ∈ ℤ is of the form

u_{k}(r, θ) = a_{k}(r)e^{ikθ}

Proof. Suppose u is γ-harmonic and u|_{∂𝔻} = e^{ikθ}. Since the conductivity is constant on circles, for all ϵ > 0

v(r, θ) = u(r, θ + ϵ) − u(r, θ)

is also γ-harmonic and v|_{∂𝔻} = e^{ikθ}(e^{ikϵ} − 1). Hence, by the uniqueness of the solution of the Dirichlet problem,

u_{k}(r, θ)(e^{ikϵ} − 1) = u_{k}(r, θ + ϵ) − u_{k}(r, θ)

⇒ u_{k}(r, θ)e^{ikϵ} = u_{k}(r, θ + ϵ)
⇒ u_{k}(r, θ) = a_{k}(r)e^{ikθ}.

Corollary 3.2. Λ_{γ} and \frac{d^{2}}{dθ^{2}} have the same eigenfunctions

e^{ikθ}, k ∈ ℤ.

We have that for k ∈ ℕ

\begin{cases}a_{k}(0) = 0, \\ a_{k}(1) = 1. \end{cases}

Writing (2.1) in polar coordinates gives

\frac{d}{dr}γ(r)r \frac{d}{dr}a_{k}(r) − k^{2} \frac{γ(r)}{r}a_{k}(r) = 0. (3.1)

The eigenvalue of Λ_{γ} corresponding to e^{ikθ} and e^{−ikθ} is

R(k) = γ \frac{da_{k}}{dr}(1).

We make the change of variable

x = ∫_{r}^{1} \frac{dt}{tγ(t)}.

Let x_{∞} = ∫_{0}^{1} \frac{dt}{tγ(t)} ≤ ∞. We have

\frac{d^{2}}{dx^{2}}a_{k}(x) = k^{2}γ^{2}(x)a_{k}(x), x ∈ (0, x_{∞}), (3.2)

\begin{cases}a_{k}(0) = 1, \\ a_{k}(x_{∞}) = 0, \end{cases}

and

R(k) = −\frac{da_{k}}{dx}(0).

The investigations by Krein and Kac, outlined in the next section, show that the admittance function R is well-defined even if γ^{2} in (3.2) is replaced by a positive measure. This fact allows us to extend the map γ → Λ_{γ} to conductivities given by positive measures. (See [14] for a similar extension made by geophysicists).

We will view from now on Λ_{γ}’s as linear operators from trigonometric polynomials to trigonometric polynomials, given by

\begin{cases}Λ_{γ}1 = 0, \\ Λ_{γ}e^{±ikθ} = R(k)e^{±ikθ}, k ∈ ℕ. \end{cases}

3.2. Small Vibrations of Strings. We will give now, without proofs, an outline of some results of Krein and Kac, see also [5].

Definition 3.3. A \underline{string} is a pair lm, where l is the lenght of the string (0 < l ≤ ∞) and

m = m(x), x ∈ [0, l]

is a non-decreasing function with

0 ≤ m(x) < ∞ for 0 ≤ x < l

The value of m at z represents the mass of the interval [0, x].

We note that this definition is slightly different from the one in [9] and [5], instead of considering different ways of attaching the right end of the string we allow a weightless interval at that end. If the right end l of the string is fixed, and a pulsating force

F = A sin \sqrt{ζ}t, ζ ∉ ℝ

is applied to the left end in the direction perpendicular to the x-axis, the forced oscillation of the left end satisfies the law

y = Ω(ζ)A sin \sqrt{ζ}t.

The function Ω is called the \underline{coefficient of dynamic compliance} of the string.

The amplitude function of the oscillation satisfies the following integral equation

ψ(x, ζ) = ψ(0, ζ) + ψ′_{−}(0, ζ)x − ζ ∫_{0}^{x}(x − s)ψ(s, ζ)dm(s). (3.3)

If m has the density ρ(x) = dm/dx this equation has an equivalent differential form

\frac{1}{ρ(x)} \frac{d^{2}}{dx^{2}} ψ(x, ζ) = −ζψ(x, ζ). (3.4)

The integral form makes the general characterizations below possible.

Let ϕ(x, ζ) and θ(x, ζ) be the solutions of (3.3) with the boundary conditions

\begin{cases}ϕ̃(0, ζ) = 1 \\ \frac{dϕ̃}{dx}(0, ζ) = 0 \end{cases} and \begin{cases}θ̃(0, ζ) = 0 \\ \frac{dθ̃}{dx}(0, ζ) = 1. \end{cases}

For every x ∈ [0, x_{∞}) the functions ϕ(x, ζ) and θ(x, ζ) are entire functions of ζ. The coefficient of dynamic compliance is determined by these fundamental solutions

Ω(ζ) = lim_{x→l} \frac{θ(x, ζ)}{ϕ(x, ζ)}.

Note that

ψ(x, ζ) = ϕ(x, ζ) − \frac{1}{Ω(ζ)}θ(x, ζ)

is the solution of (3.3) with

\begin{cases}ψ(0, ζ) = 1, \\ ψ(l, ζ) = 0. \end{cases}

The following fundamental theorem is proved in [9], see also [5].

Theorem 3.4. For every function of the form

Ω(ζ) = C − \frac{c}{ζ} + ∫_{0}^{∞} \frac{(1 + t^{2})dσ(t)}{t^{2} − ζ}, ζ ∈ ℂ − [0, +∞),

where σ is a positive measure of bounded variation on (0, ∞) there exists a unique string for which Ω serves as the coefficient of dynamic compliance. And for every string its coefficient of dynamic compliance is of this form.

The measure σ is essentially the spectral measure of the operator \frac{1}{ρ(x)} \frac{d^{2}}{x^{2}} . In particular for any x, y ∈ [0, x_{∞})

∫_{0}^{∞} ϕ(x, ζ)ϕ(y, ζ)(1 + ζ^{2})dσ(ζ) = δ(x − y).

Corollary 3.5. The formula

β(ζ) = ζΩ(−ζ^{2})

gives a one-to-one correspondence between coefficients of dynamic compliance of strings and analytic functions

β : ℂ^{+} → ℂ^{+}

with β(ζ) > 0 for ζ > 0.

Proof. Herglotz’s theorem in Introduction.

3.3. Corollaries of the results of Krein and Kac. The definition of the Dirichlet-to-Neumann maps in section 3.1 and corollary 3.5 immediately imply Theorem 2.6.

We will now show that the uniqueness in Theorem 3.4 implies Theorem 2.15.

For a conductivity γ satisfying the hypothesis of Theorem 2.15 we put in correspondence the string lm with

l = ∫_{0}^{1} \frac{dr}{rγ(r)} ≤ ∞,

and

ρ(∫_{r}^{1} \frac{dt}{tγ(t)}) = γ^{2}(r).

The admittance function corresponding to γ and the coefficient of dynamic compliance of the string are connected by

R(λ) = \frac{1}{Ω(−λ^{2})}. (3.5)

By Corollary 3.5 we have that

\frac{R(λ)}{λ} : ℂ^{+} → ℂ^{+}

is analytic in ℂ^{+} and, therefore, is determined by its values at integers (see [15]). Therefore, the Dirichlet-to-Neumann map Λ_{γ} determines the coefficient of dynamic compliance Ω(λ) of the correspondent string. Theorem 3.4 garantees a unique corresponding string with density ρ. The conductivity can be found then by

γ(e^{− ∫_{0}^{x} \sqrt{ρ(t)}dt}) = \sqrt{ρ(x)}. (3.6)

3.4. Characterization of kernels. Positive definite functions. We will now explore the role of positive definite functions.

Lemma 3.6. Let

f(s) = − ∫_{0}^{∞} t\frac{e^{−st} + e^{(s−2π)t}}{1 − e^{−2πt}} (1 + t^{2})dσ(t), s ∈ (0, π), (3.7)

where σ is a positive measure of bounded variation on (0, ∞), then

∫_{0}^{π} f(s)(cos λs − 1)ds = ∫_{0}^{∞} \frac{λ^{2}(1 + t^{2})dσ(t)}{λ^{2} + t^{2}}

for λ ∈ ℂ^{+}.

Proof. Tonelli’s theorem.

We are now in a position to prove Theorem 2.14.

Proof. The fact that the kernel of a layered Dirichlet-to-Neumann map has the properties of the Theorem 2.14 follows directly from the Herglotz’s theorem and the lemma 3.6. We now show the other direction.

By the Bochner’s theorem in Section 2, if −h is positive definite on (0, 2π), there exists a σ-finite measure ν on ℝ such that

h(s) = − ∫_{−∞}^{+∞} e^{−st}dν(t), s ∈ (0, 2π).

Since

h(s) = h(2π − s),

there exists a σ-finite measure τ on (0, ∞) such that

h(s) = −\frac{1}{2} ∫_{−∞}^{+∞} e^{−st} + e^{−(2π−s)t}dν(t) = − ∫_{0}^{∞} e^{−st} + e^{−(2π−s)t}dτ(t).

Since

∫_{0}^{π} f(s)(cos s − 1)ds < ∞,

by lemma 3.6 with λ = 1 and dτ(t) = \frac{t(1+t^{2})}{1−e^{−2πt}} dσ(t)

∫_{0}^{∞} \frac{1 − e^{−2πt}}{t(1 + t^{2})} dτ(t) < ∞.

⇒ f(s) = − ∫_{0}^{∞} t\frac{e^{−st} + e^{(s−2π)t}}{1 − e^{−2πt}} (1 + t^{2})dσ(t), s ∈ (0, π)

for a positive measure of bounded total variation σ. Invoking of lemma 3.6 and Theorem 3.4 finishes the proof.

The arguments above can be easily transformed to give theorems 2.17 and 2.18 for the half-plane. Lemma 3.6 should be replaced by

Lemma 3.7. Let

g(s) = − ∫_{0}^{∞} te^{−st}(1 + t^{2})dσ(t), s ∈ (0, ∞), (3.8)

where σ is a positive measure of bounded variation on [0, ∞), then

∫_{0}^{∞} g(s)(cos λs − 1)ds = ∫_{0}^{∞} \frac{λ^{2}(1 + t^{2})dσ(t)}{λ^{2} + t^{2}}

for λ ≥ 0.

4. Discrete problem

We will proceed in a manner similar to the continuous case.

4.1. Reduction to a 1-dimensional problem.

Lemma 4.1. The solution to the Dirichlet problem on D_{n} with the boundary data e^{ikθ}|_{∂_{n}} is of the form

u_{k}(r, θ) = a_{k}(r)e^{ikθ}

Proof. Suppose u is γ-harmonic and u|_{∂_{n}} = e^{ikθ}. Since the conductivity is constant on layers

v(r, θ) = u(r, θ + \frac{2π}{n}) − u(r, θ)

is also γ-harmonic and v|_{∂_{n}} = e^{ikθ}(e^{i \frac{2πk}{n}} − 1). Hence, by the uniqueness of the solution of the Dirichlet problem,

u_{k}(r, θ)(e^{i \frac{2πk}{n}} − 1) = u_{k}(r, θ + \frac{2π}{n}) − u_{k}(r, θ)

⇒ u_{k}(r, θ)e^{i \frac{2π}{n}} = u_{k}(r, θ + \frac{2π}{n})

⇒ u_{k}(r, θ) = a_{k}(r)e^{ikθ}.

Corollary 4.2. Λ_{γ} and [\frac{d^{2}}{dθ^{2}} ] have the same eigenvectors.

We will now derive an explicit formula for the eigenvalues of Λ_{γ} in terms of γ. We will do it in a way that emphasizes the relevance of the Sturm-Liouville and beads-on-a-string inverse problems ([7]) to discrete impedance tomography. Let us first consider the case of D(n, l) with an odd l. Let \{δ_{1}, ξ_{1}, δ_{2}, ξ_{2}, …, δ_{\frac{l+1}{2}} \} denote the conductivities on layers of D(n, l) starting from the origin. For k ≠ 0

\begin{cases}a_{k}(0) = 0, \\ a_{k}(1) = 1, \\ δ_{j}(a_{k}(r_{j}) − a_{k}(r_{j−1})) + δ_{j+1}(a_{k}(r_{j}) − a_{k}(r_{j+1})) + ξ_{j}a_{k}(ω_{k}^{(n)})^{2} = 0. \end{cases}

Let P (λ, r_{j}) be the unique solution of the following problem:

\begin{cases}P (λ, 0) = 0, \\ P (λ, r_{1}) = 1, \\ δ_{j}(P (λ, r_{j}) − P (λ, r_{j−1})) + δ_{j+1}(P (λ, r_{j}) − P (λ, r_{j+1})) + λ^{2}ξ_{j}P (λ, r_{j}) = 0. \end{cases}

Let

Q(λ, r_{j}) = δ_{j}(P (λ, r_{j}) − P (λ, r_{j−1})).

Then

λ_{k}^{(n)} = \frac{Q(ω_{k}^{(n)}, 1)}{P (ω_{k}^{(n)}, 1)}.

We have also

\begin{cases}P (λ, r_{j}) = P (λ, r_{j−1}) + \frac{1}{δ_{j}}Q(λ, r_{j}), \\ Q(λ, r_{j}) = Q(λ, r_{j−1}) + ξ_{j−1}λ^{2}P (λ, r_{j−1}). \end{cases} (4.1)

Therefore,

\frac{Q(λ, r_{j})}{P (λ, r_{j})} = \frac{Q(λ, r_{j})}{P (λ, r_{j−1}) + \frac{1}{δ_{j}}Q(λ, r_{j})}

= \frac{1}{\frac{1}{δ_{j}} + \frac{P (λ, r_{j−1})}{Q(λ, r_{j})}} = \frac{1}{\frac{1}{δ_{j}} + \frac{P (λ, r_{j−1})}{Q(λ, r_{j−1}) + ξλ^{2}P (λ, r_{j−1})}}

= \frac{1}{\frac{1}{δ_{j}} + \frac{1}{ξ_{j−1}λ^{2} + \frac{Q(λ, r_{j−1})}{P (λ, r_{j−1})}}}. (4.2)

Let

R(λ) = \frac{1}{\frac{1}{δ_{\frac{l+1}{2}}} + \frac{1}{ξ_{\frac{l−1}{2}} λ^{2} + ⋯ + \frac{1}{\frac{1}{δ_{3}} + \frac{1}{ξ_{2}λ^{2} + \frac{1}{\frac{1}{δ_{2}} + \frac{1}{ξ_{1}λ^{2} + δ_{1}}}}}}} (4.3)

Then the eigenvalues λ_{k}^{(n)} of Λ_{γ} are

λ_{k}^{(n)} = R(ω_{k}^{(n)}).

To get the similar formula for other disks one should make corresponding δ_{1}

or \frac{1}{δ_{\frac{l+1}{2}}} or both zero.

4.2. Characterizations of the Dirichlet-to-Neumann maps. We consider the function

β(λ) = \frac{1}{λ}R(λ) = \frac{1}{\frac{1}{δ_{\frac{l+1}{2}}} λ + \frac{1}{ξ_{\frac{l−1}{2}} λ + ⋯ + \frac{1}{\frac{1}{δ_{3}}λ + \frac{1}{ξ_{2}λ + \frac{1}{\frac{1}{δ_{2}}λ + \frac{1}{ξ_{1}λ + \frac{1}{\frac{1}{δ_{1}}λ}}}}}}}. (4.4)

The function β has the following properties:

1. β is rational,

2. β(λ) : ℂ^{+} → ℂ^{+},

3. β(λ) > 0 for λ > 0,

4. β(−λ̄) = −β̄(λ). It turns out that these four properties characterize the continued fractions of the form (4.4), see [11].

Corollary 4.3. The set of the discrete Dirichlet-to-Neumann maps belongs to

\{\sqrt{−[\frac{d^{2}}{dθ^{2}} ]}β(\sqrt{−[\frac{d^{2}}{dθ^{2}} ]}) : β ∈ 𝔅\}.

Let

τ(z) = \frac{1 − z}{1 + z} : ℂ^{+} ⟶^{1−1} 𝔻 (4.5)

The characterization in [11] can be restated as

Theorem 4.4. Let

B : 𝔻 → 𝔻

be a real Blaschke product. Then

τ ∘ B ∘ τ : ℂ^{+} → ℂ^{+} (4.6)

can be written in unique way as a continued fraction of the form (4.4) with positive δ_{k}, ξ_{k}. The number of coefficients in this continued fraction is equal to the number of terms in the product. Conversely, every continued fraction of the form (4.4) with positive δ_{k}, ξ_{k} can be written in the form (4.6) for some real Blaschke product B.

The following theorem is a consequence of the Pick-Nevanlinna interpolation algorithm. (see [6], see also [12] and [16]).

Theorem 4.5. Consider

{z_{i}}, {w_{i}} ⊂ ℝ^{+}, i = 1, …, m

There exists an analytic function

F : ℂ^{+} → ℂ^{+}
F (z_{i}) = w_{i}, i = 1, …, m

if and only if the matrix

W = (\frac{w_{i} + w_{j}}{z_{i} + z_{j}} )_{i,j=1}^{m}

is positive semidefinite, if and only if there exists a real Blaschke product B such that

τ ∘ B ∘ τ(z_{i}) = w_{i}, i = 1, …, m,

which may not be equal to F, e.g. F ≡ 1.

If W is singular, the Blaschke product is unique, and the number of terms in it is equal to the size of the largest non-singular principal minor of W.

If W is not singular there are exactly two desired Blaschke products with the number of terms m, and an infinite family of the Blaschke products with the number of terms > m.

Corollary 4.6. The set of the discrete Dirichlet-to-Neumann maps contains

\{\sqrt{−[\frac{d^{2}}{dθ^{2}} ]}β(\sqrt{−[\frac{d^{2}}{dθ^{2}} ]}) : β ∈ 𝔅\}.

This finishes the proof of the Theorem 2.5.

4.3. Solution of the discrete inverse problem. Let Λ be an n × n, n = 2m + 1 discrete layered Dirichlet-to-Neumann map with the non-zero eigenvalues

λ_{k}^{(n)}, k = 1, 2, …, m.

Consider

W = (\frac{λ_{i}^{(n)}/ω_{i}^{(n)} + λ_{j}^{(n)}/ω_{j}^{(n)}}{ω_{i}^{(n)} + ω_{j}^{(n)}} )_{i,j=1}^{m} .

If W is singular, there is unique discrete disk D = D(n, l) or D^{∗}(n, l) with unique radially symmetric conductivity γ on it, such that

Λ(D_{γ}) = Λ.

Theorems (3.3) and (3.4) give an explicit construction of D_{γ}(n, l). Also, it follows that l is equal to the size of the largest non-singular principal minor of W, in particular l < m.

If W is non-singular, there are unique conductivities γ, γ′ on the disks D(n, m), D^{∗}(n, m), with

Λ(D_{γ}(n, m)) = Λ(D_{γ′}^{∗}(n, m)) = Λ,

And for every D = D(n, l) or D^{∗}(n, l) with l > m there are infinitely many condutivities γ with

Λ(D_{γ}) = Λ.

References

[1] N. I. Akhiezer and I. M. Glazman, Theory of Linear Operators in Hilbert Space, New York, 1961-63.

[2] Yves Colin de Verdiere, Reseaux Electriques Planaires, Prepublication de l’Institut Fourier.

[3] E. Curtis, D. Ingerman, J. Morrow, Circular planar graphs and resistor networks, submitted.

[4] E. Curtis, E. Mooers, J. Morrow, Finding conductors in circular networks from boundary measurments, Math. Modelling and Numerical Mathematical Modelling and Numerical Analysis 28 (1994), 781-813.

[5] H. Dym and H. P. McKean, Gaussian Processes, Function Theory, and the Inverse Spectral Problem, Academic Press, 1976.

[6] J. B. Garnett, Bounded Analytic Functions, Academic Press, Inc., 1981.

[7] F. R. Gantmakher and M. G. Krein, Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems, Moscow, 1950.

[8] D. Ingerman and J. Morrow, On a Characterization of the kernel of the Dirichletto-Neumann map for a planar region, submitted.

[9] I. S. Kac, M. G. Krein, On the spectral function of the string, AMS Translations, S.2, Vol 103, 1974, 19-102.

[10] S. Karlin, Total Positivity, Stanford University Press, 1968.

[11] N. Levinson, R. M. Redheffer, Complex Variables, Holden-Day, Inc., 1970.

[12] D. Marshall, An Elementary Proof of the Pick-Nevalinna Interpolation Theorem, Michigan Math. J. 21 (1974), 219-233.

[13] A. I. Nachman ,Global Uniqueness for a Two-Dimentional Inverse Boundary Value Problema, Annals of Mathematics(2), 143 (1996), no. 1, 71-96.

[14] R. Parker, The Inverse Problem of Electromagnetic Induction: Existence and Construction of Solutions Based on Incomplete Data, J. of Geophysical Research, Vol. 85, No. B8, August 10, (1980), 4421-4428.

[15] Rudin, Complex and Real Analysis, McGraw-Hill Book Company, 1987.

[16] J. Sylvester, A Convergent Layer Stripping algorithm for the Radially Symmetric Impedance Tomography Problem, Commun. in Partial Differential Equations, 17(11&12), (1992), 1955-1994.

[17] J. Sylvester, G. Uhlmann, Inverse Boundary Value Problems at the Boundary - Continuous Dependence, Comm. Pure Appl. Math. XLI, (1988), 197-219.

E-mail address: ingerman@math.washington.edu

Department of Mathematics, University of Washington