SUFFICIENT CONDITIONS FOR AN ELECTRICAL NETWORK TO BE N-TO-ONE

BENJAMIN R. HAYES

Abstract. In this paper, we discuss the inverse problem for electrical networks, and give sufficient conditions for an electrical network to have an n-to-one correspondence for some positive integer n. We also discuss some of the problems that have come up so far in constructing an n-to-one correspondence and show how to avoid these problems.

1. Definitions

Convention. By a graph, we shall always mean a graph with no loops, but which may have multiple edges.

Definition 1. A graph with boundary is a graph G = (V, E) with a set of vertices designated boundary nodes, the rest are called interior nodes. The set of boundary nodes will be denoted ∂V and the interior nodes will be denoted intV.

Definition 2. An electrical network Γ = (G, γ) is a graph G = (V, E) with boundary and a function γ: E → ℝ^{+} called the conductivity function. For any edge e ∈ E the conductance of the edge e is γ(e).

Definition 3. A linear fractional transformation is function from ℝ to ℝ which is a ratio of two linear functions.

Notation. If x = (x_{1}, x_{2}, x_{3}, …, x_{n}) ∈ ℝ^{n} and y = (y_{1}, y_{2}, …, y_{m}) ∈ ℝ^{m} we will use (x, y) for (x_{1}, x_{2}, …, x_{n}, y_{1}, y_{2}, …, y_{m}).

2. Introduction

The purpose of this paper is to explore the correspondence between the Kirchhoff matrix for an electrical network and its response matrix. For some graphs this correspondence is neither one-to-one nor infinite to one. We give sufficient conditions for a network to have an n-to-one correspondence for a natural number n.

2.1. The Forward Problem and The Inverse Problem. We now discuss the forward problem for electrical networks, and introduce the inverse problem. A more detailed discussion is given in [2].

Suppose Γ = (G, γ) is an electrical network, with n vertices, 1, 2, ..., n (we often use numbers to denote vertices) we shall use γ_{i,j} for the sum of the conductances over all edges from vertex i to j. If i and j are not adjacent we say γ_{i,j} = 0.

Date: June 17, 2009.

Definition 4. Suppose Γ = (G, γ) is an electrical network with n vertices. The Kirchhoff matrix K is an m × m matrix defined as follows.

(1) K_{i,j} = −γ_{i,j}, if i ≠ j

(2) K_{i,i} = ∑_{i≠j} γ_{i,j}

Suppose we are given a function u defined on the vertices of G, after labeling the vertices we may regard u as a vector in the obvious way. The physical interpretation of K is that (Ku)_{i} is the resulting current into the network due to u out of node i. Suppose now we are given an electrical network Γ = (G, γ) with G = (V, E) and a function ϕ: ∂V → ℝ^{+}. The forward problem is to find a function u: V → ℝ^{+} such that u = ϕ on ∂V and (Ku)_{i} = 0 for all i ∈ intV. As discussed in [2] the forward problem has a unique solution for every electrical network with a boundary node in each connected component. Let Γ = (G, γ) be an electrical network and K its Kirchhoff matrix. Let A, B, C be sub-matrices corresponding to boundary to boundary connections, boundary to interior connections, and interior to interior connections, respectively. Then K has the following block structure

K = [\begin{matrix}A & B \\ B^{T} & C \end{matrix}] .

As proved in [2], the matrix C is always invertible and the solution to the forward problem is (A−BC^{−1}B^{T})u. We will use Λ_{γ} to denote A−BC^{−1}B^{T} and call it the network response. If G has no boundary vertices, then Λ_{γ} = K. The ij-th entry of Λ_{γ} will be denoted λ_{i,j}. The inverse problem is to recover K from Λ_{γ}, specifically we wish to see if the map sending γ to Λ_{γ} is one to one. For some networks, this correspondence is neither one-to-one nor infinite-to-one but is instead n-to-one for some n ∈ ℕ with n bigger than 1. The first example discovered was in [3]. We now discuss the amalgamation and the star-K transformation, which will help us understand the possibility of an n-to-one correspondence.

2.2. Graph Amalgamation. We will often need to construct a graph by gluing it from smaller pieces, we usually do this by labeling vertices on each smaller piece and then gluing together vertices which have the same labels. We now define precisely what we mean by such a gluing process.

Definition 5. Let G_{1} = (V_{1}, E_{1}), G_{2} = (V_{2}, E_{2}), …, G_{n} = (V_{n}, E_{n}) be graphs whose vertex sets are disjoint, Let

V = ⋃_{i=1}^{n} V_{i}.

Suppose L is a set,whose elements we shall call labels, such that |L| ≤ |V | and that ϕ: V → L is a surjective function satisfying ϕ(v) ≠ ϕ(w) if v is adjacent to w. We shall call ϕ a labeling function (or a labeling function on G_{1}, G_{2}, …, G_{n}). We define a new graph G as follows, the vertex set is {ϕ^{−1}(a): a ∈ L}. For each a, b ∈ V let B_{a,b} be the set of all edges between v and w for all nodes v ∈ ϕ−1(a), w ∈ ϕ^{−1}(b). We then declare that for each a, b ∈ L there should be |B_{a,b}| edges between ϕ^{−1}(a) and ϕ^{−1}(b) in G. We call G a the connected direct sum of the G_{i} with respect to ϕ and write

G = (∑_{i=1}^{n} G_{i})_{ϕ} ,

Suppose G is a graph with boundary and a ∈ L. If |ϕ^{−1}(a)| = 1 then we declare |ϕ^{−1}(a)| to be a boundary node if and only if the unique element in |ϕ^{−1}(a)| is. If |ϕ^{−1}(a)| > 1 we shall have to declare whether |ϕ^{−1}(a)| is a boundary node or not.

Definition 6. Suppose Γ_{1} = (G_{1}, γ_{1}), Γ_{2} = (G_{2}, γ_{2}), …, Γ_{n} = (G_{n}, γ_{n}), with G_{i} = (V_{i}, E_{i}) for all i ∈ 1, 2, …, n, and V_{i} ∩ V_{j} = if i ≠ j. For each i and for each edge e ∈ E_{i} we shall use γ(e) for γ_{i}(e). Let L be a set such that |L| ≤ | ⋃_{i=1}^{n} V_{i}|, and let ϕ be a labeling function on G_{1}, G_{2}, …, G_{n}. Let G be the connected direct sum of the G_{i} with respect to ϕ. We define a new conductivity function γ̃ as follows.

For each pair of vertices ϕ^{−1}(v), ϕ^{−1}(w) in G let B_{v,w} be the set of all edges between ϕ^{−1}(v) and ϕ^{−1}(w) in G, and let A_{v,w} be the set of all edges between elements of ϕ^{−1}(v), ϕ^{−1}(w). By definition there exists a bijection f : B_{v,w} → A_{v,w}. For each e ∈ B_{v,w} we now define γ̃(e) = γ(f(e)).We call Γ = (G, γ̃) the connected direct sum of the Γ_{i} with respect to ϕ and write

Γ = (∑_{i=1}^{n} Γ_{i})_{ϕ} .

We will sometimes drop any explicit reference to the labeling function if it is clear from the context. We thus sometimes speak of the connected direct sum of G_{i} and write G = ∑_{i=1}^{n} G_{i}, th similar conventions for networks. Whenever we talk about gluing graphs, or networks, together by labeling vertices we will mean in the sense of the preceding. This topic is discussed more in [1] and [8], there this process is called ”amalgamation.”

2.3. The Star-K Transformation. The star-K transformation allows us to regard the response matrix of an electrical network as an electrical network itself. The reader is encouraged to go to [9] for more details.

1 2 3 4 5 1 2 3 4

Figure 1. The four-star S_{4} transformed into the complete graph on 4 vertices, K_{4}.

Given n ∈ ℕ the n-star, denoted S_{n}, is a graph with one central vertex, which is adjacent to n other vertices, none of which are adjacent to each other. To regard S_{n} as an electrical network the central vertex is interior, every other vertex is a boundary vertex. The complete graph on n vertices, denoted K_{n} is a graph with n vertices which are all adjacent to each other. For K_{n} to be an electrical network we have all of its vertices be boundary vertices. The star-K transformation is a way to take a graph which is ”composed” of star graphs, and replace them with complete graphs.

Suppose we start with S_{n} and a conductivity function γ on S_{n} , we then replace S_{n} with K_{n} and define a new conductivity function μ on K_{n} by μ_{i,j} = −λ_{i,j}. In general we cannot reverse the operation, but in [9] it is proved we can under a simple condition, called the quadrilateral condition. Let μ_{i,j} = −λ_{i,j}, then K_{n} comes from S_{n} if and only if for any four distinct vertices i, j, k, l

(1)  μ_{i,j}μ_{k,l} = μ_{i,k}μ_{j,l}.

That is, the products of conductances on opposite sides of a quadrilateral in a complete graph which came from a star graph are equal.

c  e a b  f d 1 2 3 4

Figure 2. The quadrilateral condition is that ab = cd = ef.

Suppose the quadrilateral condition is satisfied and let {1, 2, …, n} be the boundary vertices of S_{n} and denote the interior vertex by n + 1. Then

(2)  γ_{i,n+1} = (∑_{i≠j} μ_{i,j}) + \frac{μ_{i,j}μ_{i,k}}{μ_{j,k}}

this is well defined by the quadrilateral condition. (See [9]). It is also proved in [9] that if we know the original graph we can calculate the conductances on the new graph by

(3)  μ_{i,j} = \frac{γ_{i,n+1}γ_{j,n+1}}{∑_{k=1}^{n} γ_{k,n+1}}

We also describe the inversion, which is another graph we can apply the star-K transformation to. The inversion is drawn below on the left and its star-K transformed graph is drawn on the right.

1 4 2 5 3 α_{1} α_{2} 1 4 2 5 3

Using the quadrilateral rule, we deduce that α_{2} = \frac{μ_{3,4}α_{1}}{μ_{1,2}} .

Suppose we have networks Γ_{1} = (G_{1}, γ_{1}), Γ_{2} = (G_{2}, γ_{2}), …, Γ_{n} = (G_{n}, γ_{n}) where each G_{i} is a star or an inversion for i ∈ {1, 2, 3 …, n} and let V = ⋃_{i=1}^{n} V_{i}. For each i, let Γ̂_{i} = (Ĝ_{i}, γ̂_{i}) be the star-K transformed network and let ϕ be a labeling function on G_{1}, G_{2}, …, G_{n}, such that |ϕ^{−1}(ϕ(a))| = 1 for all interior nodes a (i.e. we are not gluing interior nodes together). We can apply the star-K transformation to Γ = (∑_{i=1}^{n} Γ_{i})_{ϕ}, as follows. For each i, let Ĝ_{i} = (V̂_{i}, Ê_{i}) and let V̂ = ⋃_{i=1}^{n} V̂_{i}. We may regard V̂_{i} as a subset of the vertex set for G_{i} ,we then restrict the domain of ϕ to V̂, we also restrict the codomain of ϕ, if necessary, to obtain a surjective function ϕ̂. We then set Γ̂ = (∑_{i=1}^{n} Γ̂_{i})ϕ̂ .Then Γ̂ is the star-K transformed network. Let

γ̂ be the conductivity function for Γ̂ and letΛ be the response matrix for Γ. Under these conditions it is still true that γ̂_{i,j} = −Λ_{i,j}, by construction the quadrilateral rule holds for each K.

A graph G with boundary which can be constructed by gluing stars and inversions together as above, will be called star-based, and the collection {G_{i}} will be called a star-basis for G.

Note that in general this transformation leads to multiple edges. Suppose we do not know the original Kirchhoff matrix, and that for two nodes i, j there are n edges between i and j we then pick n variables α_{1}, α_{2}, …, α_{n} and place one on each edge in the transformed graph and call them partial conductances. We are then required to solve for the α_{1} requiring that ∑_{i=1}^{n} α_{i} = μ_{i,j}, and that they are all positive. If we do know the original Kirchhoff matrix, then for any edge e between i and j we can calculate the partial conductance on e by γ̂(e).

Example 1. Triangle − in − Triangle Graph

1 2 3 4 5 6 7 8 9 α_{4} α_{1} α_{2} α_{3}  1 2 3 4 5 6

Using the quadrilateral rule, α_{2} = (μ_{1,2}μ_{5,6})/(α_{1}). Using the double edge α_{3} = μ_{2,6} − (μ_{1,2}μ_{5,6})/(α_{1}). Continuing, we see that the α_{4} must be

\frac{μ_{1,4}μ_{3,5}}{μ_{2,3} − \frac{μ_{3,6}μ_{2,4}}{μ_{2,6} − \frac{μ_{1,2}μ_{5,6}}{α_{1}}}}.

Therefore

(4)  μ_{1,5} = α_{1} + \frac{μ_{1,4}μ_{3,5}}{μ_{2,3} − \frac{μ_{3,6}μ_{2,4}}{μ_{2,6} − \frac{μ_{1,2}μ_{5,6}}{α_{1}}}}.

If we clear denominators in (4) the continued fraction can be written as a linear fractional transformation. We then clear denominators again to see that α_{1} satisfies a quadratic polynomial, this can lead to a two-to-one correspondence for appropriate values of conductances. Note that this polynomial is only determined by our choice of starting with α_{1}. If instead we start α_{4} and determined α_{1} by going clockwise around the graph our equation would be

(5)  μ_{1,5} = α_{4} + \frac{μ_{1,6}μ_{2,5}}{μ_{2,6} − \frac{μ_{3,6}μ_{2,4}}{μ_{3,4} − \frac{μ_{1,4}μ_{3,5}}{α_{1}}}}

If we do the same process with (5) as we did with (4) we will in general have a different quadratic equation.

There are other examples of n-gon in n-gon networks which have the same behavior, see [5].

In order to be valid partial conductances, it is necessary and sufficient for each partial conductance to be positive and to satisfy (1). Condition (1) has already been discussed. To see that it is sufficient that each partial conductance be positive we use (2); for necessity (3).

Suppose Γ = (G, γ) is an electrical network constructed by gluing stars together as described above, let N be the number of edges in G and let M be the number of edges in its star-K transformed graph, not counting multiple edges. We may regard the conductivity function γ as an element of ℝ^{N} and the response matrix as an element of ℝ^{M}.

Fix a response matrix Λ = (λ_{i,j}) for Γ. Suppose β and α are partial conductances, and that for some linear fractional transformation l_{i}, we have β = l_{i}(α). We thus have a function g_{β}: (ℝ^{+})^{N+1} → ℝ , continuous in a neighborhood of (α, Λ), so that β = g_{β}(α, Λ). Each of the entries in the response matrix may be written as rational functions of the conductances in the original graph. Thus for each partial conductance β we can find a function f_{β} : ℝ^{N+1} → ℝ continuous in a neighborhood (α, γ), so that β = f_{β}(α, γ).

3. Polynomial Relations and Multiple Solutions

As seen above, sometimes we can use the quadrilateral conditions and partial conductances to write an entry in the response matrix μ_{i,j} as a function of a partial conductance α. We wish to discuss this situation in general, so we must come up with a class of graphs we can apply this analysis to. We first define the notion of a multiplexer. Intuitively, a multiplexer is what allows us to write some partial conductances in a graph as a function of others.

Definition 7. Given a graph with boundary G, a multiplexer is a partitioning of all the subsets of size two of ∂V into two sets U and K, where U is called the unknown set and K is called the known set. We require that

(1) For any function f: U → ℝ^{+}, if there exists a response matrix Λ_{1} such that (Λ_{1})_{i,j} = −f({i, j}) for all {i, j} ∈ U then there also exists a response matrix Λ_{2} ≠ Λ_{1} with (Λ_{2})_{i,j} = −f({i, j}) for all {i, j} ∈ U.

(2) For all {i, j} ∈ K, and for any negative real number λ there is at most one response matrix Λ on G such that (Λ)_{i,j} = λ.

If |U| = n we call this multiplexer an n-plexer.

Note that by (2) the graph is recoverable. Intuitively, (1) says that if we only know entries corresponding to pairs in the unknown set we cannot recover all the conductivities on the graph, while (2) says that if we known any entry corresponding to a pair in the known set we can recover all the conductivities in the graph. Multiplexers are described in more detail in [4].

We are now able to describe general conditions where we can generalize the analysis of the triangle-in-triangle graph.

Definition 8. Let G be a star-based graph and let G_{i} be a star-basis for G, and for each i let P_{i} be a multiplexer for G_{i}. Let Ĝ be the the star-K transformed graph of G an suppose there exist two nodes a, b in Ĝ which have n edges e_{1}, e_{2}, …, e_{n} between them which satisfy the following properties.

(1) For any positive real number β there is at most one conductivity function γ on G such that γ̂(e_{1}) = β.

(2) For each j ∈ {2, 3, …, n} there exists a sequence

e_{1} = e_{j,0}, e_{j,1}, …, e_{j,m_{j}} = e_{j}

of edges which satisfying the following. Let e_{j,k} = {a_{k}, b_{k}} and e_{j,k+1} = {a_{k+1}, b_{k+1}}. Either {a_{k+1}, b_{k+1}} = {a_{k}, b_{k}} and e_{i,k}, e_{i,k+1} are the only edges between a_{k} and b_{k}, or {a_{k}, b_{k}} is an element in the known set of one of the multiplexers P_{l} and a_{k+1} ≠ a_{k}, b_{k+1} ≠ b_{k}, and a_{k}, b_{k} are vertices in G_{l}.

By (1) knowing a valid partial conductance on e_{1} allows us to recover all the conductivities in G. By (2) for each k + 1 ∈ {1, 2, …, m_{j}} there exist a unique linear fractional transformation l_{j,k+1} such that for any valid partial conductance α on e_{j,k} a valid partial conductance on e_{j,k+1} is given by l_{j,k+1}(α). Let

l_{j} = l_{j,m_{j}} ∘ l_{j,m_{j}−1} ∘ ⋯ ∘ l_{j,1}.

By the preceding, if α is a partial conductance on e_{1} we conclude that μ_{a,b} satisfies

μ_{a,b} = α + l_{1}(α) + l_{2}(α) + … + l_{n}(α),

for i = 1, …, n, moreover if we know a root of this equation we can recover all the conductivities in the graph. Clearing denominators and subtracting we see that α must satisfy what is, in general, a polynomial p of degree n. We call p the conductance polynomial of the original electrical network with respect to the edge e_{1}.

Note that the conductance polynomial depends on our choice of starting edge, (this was noted in Example 1). However, if the choice of edge is irrelevant we may abuse terminology and call p the conductance polynomial.

The reader should see how the steps involved in this definition work in the example of the triangle-in-triangle graph, or indeed, any of the n-gon in n-gon graphs.

The reader may be worried that a valid partial conductance α may correspond to a point where this denominator vanishes, but this cannot happen. Each l_{i} may be written as a composition of linear fractional transformations l_{i} = S_{1} ∘S_{2} ⋯∘S_{n}. Since α is a valid partial conductance implies that (S_{i} ∘ S_{i+1} ⋯ ∘ S_{n})(α) > 0 and finite for all i. For any two linear fractional transformations S_{1}(x) = \frac{a_{1}x+b_{1}}{c_{1}x+d1} and S_{2}(x) = \frac{a_{2}x+b_{2}}{c_{2}x+d2},

(S_{1} ∘ S_{2})(x) = \frac{a_{1}(\frac{a_{2}x+b_{2}}{c_{2}x+d_{2}} ) + b_{1}}{c_{1}(\frac{a_{2}x+b_{2}}{c_{2}x+d_{2}} ) + d_{1}} .

If the denominator is not 0, then

(S_{1} ∘ S_{2})(x) = \frac{(a_{1}a_{2} + c_{2}b_{1})x + b_{2}a_{1} + d_{2}b_{1}}{(a_{2}c_{1}1 + d_{1}c_{2})x + b2c_{1} + d_{1}d_{2}} .

If this expression is finite the new denominator cannot be 0. In our case we know all the intermediate linear fractional transformations are positive and finite so the denominator of l_{i} has to be nonzero for a valid partial conductance. Thus we can clear denominators and conclude that a valid partial conductance must satisfy the conductance polynomial.

This polynomial can have more than one root, of course, when this happens we may have more than one choice for the partial conductance α. Each of these choices will determine a sequence of partial conductances, either by the quadrilateral rule, or by the use of a multiple edge. If all the partial conductances obtained this way are positive, then we have a correspondence which is not one-to-one, but is still finite-to-one. We must assume that in every star we cannot determine α from the other entries in Λ, because if we know α we could determine the other entries and the correspondence would be one-to-one. This is why we need to use a multiplexer at every stage.

We now give sufficient conditions for all the partial conductances obtained from every root of a conductance polynomial p to be positive. Our idea will be to find values of conductances so that the polynomial p has a root of multiplicity n; we will show that for coefficients ”nearby” our original polynomial there are conductances which give an n-to-one correspondence. To make this precise associate to every real polynomial p(x) = a_{n}x^{n} +a_{n−1}x^{n−1} +…+a_{0} its vector of coefficients v_{p} = (a_{0}, a_{1}, …, a_{n}), we can then make the notion of ”nearness” precise by using standard Euclidean distance. Recall that for any ε ∈ ℝ^{+} and x ∈ ℝ^{n+1} we use B_{ε}(x) for the ball of radius epsilon around x, i.e. B_{ε}(x) = {y ∈ ℝ^{n+1} : |x−y| < ε}.

Theorem 1. Let p be a polynomial of degree n with real coefficients, and suppose p has a root of multiplicity n. For any positive real number ε there exists v_{q} ∈ B_{ε}(v_{p}) so that q is a real polynomial with n distinct real roots, furthermore the roots of q can be made arbitrarily close to the roots of p by making ε small enough.

Proof. Let ε be a given positive real number. By hypotheses p may be written as p(x) = a_{n}(x − a)^{n} for some a ∈ ℝ. For any y ∈ ℝ^{n} with y = (y_{1}, y_{2}, …, y_{n}) let p_{y}(x) = a_{n}(x − (a + y_{1}))(x − (a + y_{2})) ⋯ (x − (a + y_{n})). Let σ_{i} be the polynomial

σ_{i}(x_{1}, x_{2}, …, x_{n}) = ∑_{j_{1}<j_{2}<...<j_{i}} x_{j_{1}}x_{j_{2}} ⋯ x_{j_{i}},

and σ_{0} = 1.

The i-th coefficient of p is (−1)^{n−i}a_{n}σ_{n−i}(a, a, …, a) and the i-th coefficient of p_{y} is (−1)^{n−i}a_{n}σ_{n−i}(a − y_{1}, a − y_{2}, …, a − y_{n}). Since σ_{n−i} is continuous it follows that

(−1)^{n−i}a_{n}σ_{n−i}(a − y_{1}, a − y_{2}, …, a − y_{n}) → (−1)^{n−i}a_{n}σ_{n−i}(a, a, …, a)

as y → 0. Therefore v_{p_{y}} → v_{p} as y → 0. So we can find a δ such that y ∈ B_{δ}(0) implies that v_{p_{y}} ∈ B_{ε}(v_{p}). Choosing η ∈ B_{δ}(0) with distinct coordinates it follows that q = p_{η} has the desired properties. That the roots of q can be made close to the roots of p follows. □

We now recall some terminology from mutltivariable calculus which we will need in our next result.

Definition 9. Suppose U is an open subset of ℝ^{n} and V is an open subset of ℝ^{m} and let T: U → V. Suppose all the first partial derivatives of T exist. For any vector x ∈ ℝ^{n}, we use x_{i} for the i-th coordinate of x, and T_{j} for the function defined by T_{j}(x) = (T (x))_{j}. The differential of T, denoted, dT is a n × m variable matrix defined by

(dT)_{ij} = \frac{∂T_{j}}{∂x_{i}} .

Define [dT (x)]_{i,j} = \frac{∂T_{j}}{∂x_{i}} (x).

The coefficients of our associated polynomial may be written as a rational function of entries in the response matrix. We also know that entries in the response matrix may be written as rational functions of the conductivities in our network. Composing we have a map which sends conductances on the network to coefficients of the polynomial, for which we can calculate the differential. We use this fact in then next result.

Theorem 2. Suppose we have an electrical network Γ = (G, γ),which satisfies the conditions of Definition 8 and suppose its conductance polynomial has degree n. Let N be the number of edges in G. We may then regard γ ∈ ℝ^{N}. Suppose we have a vector of conductivities γ for which the conductance polynomial p has a root r of multiplicity n. Let T: (ℝ^{+})^{N} → ℝ^{n} be the map which sends conductances on G to coefficients of the polynomial, assume that dT (γ) has rank n+1. Then there exists a response matrix Λ which corresponds to n distinct Kirchhoff matrices.

Proof. Since dT has rank n + 1 there are n + 1 columns which are linearly independent, let e_{1}, e_{2}, …, e_{n}, e_{n+1} be the edges which correspond to these n + 1 columns. We fix the other conductivities on Γ and let the conductivities on e_{1}, e_{2}, …, e_{n} vary. This gives a new map T′ which is locally invertible at γ′ = (γ(e_{1}), γ(e_{2}), …, γ(e_{n}), γ(e_{n+1}). By the Inverse Function Theorem, we may select an open subset U of (ℝ^{+})^{n+1} containing γ′ which maps homeomorphically onto an open subset V of ℝ^{n+1} containing v_{p}. By Theorem 1 we may select a sequence {v_{m}} so that the polynomial p_{v_{m}} corresponding to v_{m} has n distinct positive real roots, and v_{m} → v_{p} as m → ∞. Since V is open we may choose v_{m} ∈ V for all m.

Let {r_{1,m}, {r_{2,m}}, …, {r_{n,m}} be the sequences of distinct roots of the polynomial p_{v_{m}}. Theorem 1 implies that r_{i,m} → r as m → ∞.

Since T′ is invertible, for each m we can find γ_{m} so that T′(γ_{m}) = v_{m}. Thus γ_{m} = T^{′−1}(v_{m}), and since v_{m} → v_{p} as m → ∞ we conclude that γ_{m} → γ′ as m → ∞, since T^{′−1} is continuous. One of the partial conductances in the transformed network must satisfy the original polynomial p, since p has only one root the root of this polynomial must be a partial conductance on the network. As described in section 2.3 for each β we can find a function f_{β}: ℝ^{n+2} → ℝ, continuous in a neighborhood of (r, γ′), so that β = f_{β}(r, γ′). Since f_{β}(r, γ′) > 0, we can find an open set W ⊆ (ℝ^{+})^{n+2} containing (r, γ′) so that (x, y_{1}, y_{2}, …, y_{n+1}) ∈ W implies that f_{β}(x, y_{1}, y_{2}, …, y_{n+1}) > 0 .

Since γ_{m} → γ′ as m → ∞, and r_{i,m} → r as m → ∞, we conclude that for each i there is a large enough N_{i} so that m ≥ N_{i} implies that each partial conductance which is a function of r_{i,m} is positive. Picking m larger than all the N_{i} we conclude r_{1,m}, r_{2,m}, …, r_{n,m} correspond to all positive partial conductances. Since all the roots are distinct we have constructed n different positive Kirchhoff matrices which correspond to the same response matrix.

□

We close this section with some conditions that guarantee a polynomial with exactly one root, recall that if p is a polynomial of degree n and if p has a root of multiplicity n, then p′|p; thus we may hope for conditions that guarantee a root of multiplicity n by using the division algorithm.

Theorem 3. Let n ∈ ℕ and let p(x) = a_{n}x^{n} + a_{n−1}x^{n−1} + a_{n−2}x^{n−2} + … a_{1}x + a_{0} be a polynomial of degree n whose leading term is not zero. Then p has a root of multiplicity n if and only if for all i ∈ {0, 1, …, n − 2} it is true that

(6)  n(n − i)a_{i}a_{n} − (i + 1)a_{n−1}a_{i+1} = 0.

Proof. First suppose that p has a root of multiplicity n, so p′|p. By the division algorithm,

p = (\frac{1}{n}x + \frac{a_{n−1}}{n^{2}a_{n}} ) p′ + ∑_{i=0}^{n−2} (\frac{n − i}{n}a_{i} − \frac{(i + 1)(a_{n−1}a_{i+1})}{n^{2}a_{n}}) x^{i}.

Therefore (\frac{n−i}{n}a_{i} − \frac{(i+1)(a_{n−1}a_{i+1})}{n^{2}a_{n}}) = 0 for all i ≤ n − 2 so equation (6) holds. Conversely, suppose equation (6) holds. Then since a_{n} ≠ 0, we know

(7)  a_{i} = \frac{(i + 1)a_{n−1}a_{i+1}}{n(n − i)a_{n}} ,

Let p̃(x) = a_{n}(x + \frac{a_{n−1}}{na_{n}})^{n}, and denote its i-th coefficent by ã_{i}, we claim that p = p̃. We have that ã_{i} is

(8)  \binom{n}{i}a_{n} \frac{a_{n−1}^{n−i}}{a_{n}^{n−i}n^{n−i}} = \frac{\binom{n}{i}a_{n−1}^{n−i}}{a_{n}^{n−(i+1)}n^{n−i}} .

By (7) we see a_{n−2} = \frac{(n−1)a_{n−1}^{2}}{2na_{n}} = \frac{\binom{n}{n−2}a_{n−1}^{2}}{n^{2}a_{n}} which agrees with { \atop a_{n−2}}. Assuming that a_{i+1} = ã_{i+1}, equations (7) and (8) imply that

a_{i} = \frac{(i + 1)a_{n−1}a_{i+1}}{n(n − i)a_{n}} = \frac{(i + 1)a_{n−1}}{n(n − i)a_{n}} (\frac{\binom{n}{i+1}a_{n−1}}{a_{n}^{n−(i−2)}n^{n−i−1}} ) = \frac{\binom{n}{i+1}(i + 1)a_{n−1}^{n−i}}{n^{n−i}(n − i)a_{n}^{n−(i+1)}} .

It is easy to see that \frac{\binom{n}{i+1}(i+1)}{(n−i)} = \binom{n}{i} so a_{i} = ã_{i}. The claim holds by induction. □

4. Linear Fractional Transformations and How to Control Signs of The Derivative

The method above was developed because the author had hoped to use it to show that a certain network was three-to-one. This turned out to be false. Recall from Section 2.3 that by repeated application of the Star-K transformation we end up with an equation

(9)  μ_{i,j} = α + l_{1}(α) + l_{2}(α) + … + l_{n}(α),

for some linear fractional transformations l_{1}, l_{2}, …, l_{n}, and some μ_{i,j} which is the negative of an entry in the response matrix. Chad Klumb discovered (see [7]) that all the solutions to this equation must lie in an interval where the right hand side of (9) is continuous. So if each l_{i} has a positive derivative it cannot have n distinct roots in any interval where the right hand side of (9) is continuous. We now show how to control this behavior. For any 2 × 2 matrix

A = [\begin{matrix}a & b \\ c & d \end{matrix}]

associate the linear fractional transformation S_{A}(x) = \frac{ax+b}{cx+d}. It follows from Section 3 that S_{A}∘S_{B} = S_{AB}. So we have a homomorphism from the group of 2×2 invertible real matrices to the group of real linear fractional transformations. Also

S′_{A}(x) = \frac{a(cx + d) − c(ax + b)}{(cx + d)^{2}} = \frac{det A}{(cx + d)^{2}} .

Therefore sign(S′_{A}) = sign(det A). The continued fractions we have can be written as compositions of linear fractional transformations. Using the homomorphism we see that sign[(S_{A_{1}} ∘ S_{A_{2}} ⋯ ∘ S_{A_{n}})′] = sign(det A_{1} det A_{2} ⋯ det A_{n}). This allows us to calculate the signs of the derivatives of our linear fractional transformations without actually computing the composition. We simply account for the sign at each stage. Suppose we express a partial conduction x in a fourstar as a function of the partial on an opposite edge l(x). This will take the form l(x) = C/x for some positive constant C, and has a negative derivative.

\begin{matrix}x \\ l(x) \\ 1 \\ 2 \\ 3 \\ 4 \end{matrix}

Expressing one conductance as a function of another across a double edge is a

transformation of the form l(x) = C−x and has a negative derivative.x l(x) 1 2

Writing one partial conductance as function of another across an inversion can be written as l(x) = Cx for some postive constant C, (in our figure below l(x) = \frac{μ_{1,3}x}{μ_{3,4}})

and thus has a positive derivative. l(x) x 1 4 2 5 3

These are the basic transformations we use so we can keep track of the signs of the derivative easily. For instance, the linear fractional transformations l_{1}, l_{2} in the graph below (note that nodes numbered the same should be identified) always have positive derivatives, this was the graph that the author worked on; which is not three-to-one.

\begin{matrix}x \\ l_{1}(x) \\ l_{2}(x) \\ 1 \\ 2 \\ 3 \\ 4 \\ 12 \\ 6 \\ 5 \\ 11 \\ 16 \\ 9 \\ 10 \\ 14 \\ 1 \\ 2 \\ 1 \\ 2 \\ 13 \\ 7 \\ 8 \\ 15 \end{matrix}

One simply counts the four-stars and double edges in pairs to see that we end up with all positive derivatives. In fact if we start with any multiplexer for which we can write all partial conductances in the unknown set as a linear function of one partial conductance in the known set, and then attach four-stars, the same reasoning applies and shows that we always get positive derivatives. So we know why we need the inversions that Ilya used in [6], replacing a four-star with an inversion switches the sign of the derivatives and allows negative derivatives, this shows us why Ilya’s graph without inversion is not three-to-one. For each integer n ≥ 3 we can now give examples of graphs G_{n} that have the possibility of being n-to-one and avoid these problems with the derivatives. For simplicity we indicate boundary nodes with solid dots, and interior nodes with open circles. We start with an n + 1-star in the middle, its boundary nodes numbered 1, 2, …, n + 1 the interior node to be numbered later. let X_{i} be the graph drawn in figure 3. For each i − 1 ∈ {2, … (n − 1)/2} let X_{i} be the graph drawn in figure 4, the other nodes to be numbered later. For all i − 1 ∈ {(n − 1)/2, (n − 1)/2 + 1, …, n} let X_{i} be the graph drawn in figure 5.

For each of these graphs we number the nodes as in figure 3,4,5. Let N be the number of remaining unnumbered boundary nodes and M the number of interior nodes. Label the rest of the boundary nodes n + 4, n + 5, …, n + 3 + N and the interior nodes n + 4 + N, …, n + 3 + N + M. We then set

G_{n} = ∑_{i=1}^{n} X_{i}.

1 2 Figure 3.

1i n+2 n+3

Figure 4. Two four-stars glued together.

1i n+2 n+3

Figure 5. Two four-stars with an inversion.

If n is even we do the same but instead have one more graph which has an inversion.

We need at least two four-stars on every wing except one to prevent an edge in series. Note that we use a complete bipartite graph for the multiplexer, that is because it is the only n-plexer known to exist for all n , as discussed in [4]. It is not hard to see that once we fix a partial conductance x on one of the {n + 2, n + 3} edges all the partial conductances on the {n + 2, n + 3} can be written as l_{i}(x) for some linear fractional transformation l_{i}. It is not hard to verify that in the case of odd n half the l_{i} is have positive derivatives, and the other half have negative derivatives. For n even there is one more negative derivative. It may be the case that this is not the best choice for the signs of the derivatives. This can be easily changed by either deleting one of the inversions or by replacing one of the four-stars with an inversion.

5. Future Research

One obvious direction for research is to try and find methods for deciding whether or not the graphs described above are n-to-one. Another is to investigate the behavior of the map T which sends conductances on the original graph to coefficients of its associated polynomial. In order to prove Theorem 2 we needed the assumption that dT had full rank. This assumption may be already satisfied, there does not seem to be enough dependence of the equations on each other for the rank of dT to not be full. One could also make refine Theorem 1 and find out which way to move the coefficients to guarantee n distinct real roots. This may make the rank hypothesis of Theorem 2 superfluous, because it is not necessary to move the coefficients in an arbitrary direction just in the right direction.

If one can associate a polynomial p to an electrical network Γ which has the properties that a root of p can be used to determine all the partial conductances in Γ̂ and that the other partial conductances depend continuously on such a root, then one can make an obvious generalization of Theorem 2. Therefore one further direction for research would be to try and define the conductance polynomial in further generality.

The idea for Theorem 2 came from Ernie Esser, and from our technique to try to prove our graph was three-to-one. We put random conductivities on most of the edges of our original graph but set some others to be variable. We then try to solve equations to prove that it had values for which the polynomial had a root of multiplicity three. In doing this we are studying a polynomial whose coefficients vary, but in a continuous manner. One possibility for future research is to try to understand more about how the roots of a polynomial vary when the coefficients vary continuously. What can one say about the behavior of the roots in this situation? All the author is aware of is the result of Theorem 1 and that if the leading term never vanishes the roots vary continuously. This last fact can be seen by using Rouche’s Theorem from Complex Analysis.

Theorems 2 and 1 has obvious generalizations, one is that if you have a polynomial with all real roots, and no assumption on the multiplicities, there are polynomials which have distinct roots, and whose coefficients are nearby the original polynomial. One simply applies Theorem 1 and uses the fact that coefficients of products of polynomials depend continuously on the original coefficients. One can generalize Theorem 2 to say that if you have conductances for which all the roots of the associated polynomial (whether they are distinct or not) correspond to positive Kirchhoff matrices, and if dT has full rank; then there are conductances nearby which correspond to n-distinct positive Kirchhoff matrices. The proof is the same as before.

6. Acknowledgments

The author would like to thank Professor Morrow for the opportunity to work in the REU program, Ernie Esser for the idea to look at points where the polynomials has one root, and Tom Boothby for help with computing.

References

[1] Ryan K. Card and Brandon I. Muranaka, Using Network Amalgamation and Seperation to Solve the Inverse Problem, University Of Washington, 2000.

[2] Edward B.Curtis, and James A. Morrow, Inverse Problems for Electrical Networks, Singapore, World Scientific Publishing, 2000.

[3] Ernie Esser, On Solving the Inverse Problem for Annular Networks, University of Washington, 2000.

[4] Andrew Fanoe, and Tracy Zhang, Structures of Multiplexers on Stars, University of Washington, 2007.

[5] Jennifer French, and Shen Pan, 2^{n} To 1 Graphs, University of Washington, 2004.

[6] Ilya Grigorev, Three 3-To-1 Graphs With Positive Conductivities, University of Chicago, 2006.

[7] Chad Klumb, ???,University of Washington, 2008.

[8] Brian Lehmann, Recoverability of Spliced Networks, University of Washington, 2002.

[9] Jeffrey T. Russell, Star and K Solve the Inverse Problem, Stanford University, 2003.

Department of Mathematics, University of Washington, Seattle,WA 98105

   E-mail address: hayes benjamin@hotmail.com

A five-plexer_{23} 2 5 1 6 3 4 x 24 1 2 7 8 l_{1}(x)  (+) 27 1 4 7 8 28 13 14 l_{2}(x) (−) 29 1 5 7 8 30 15 16 17  ^{18} 34 l_{3}(x) (+)  7 1 8 6 32 33 21 19 21 21 l_{4}(x)  (−) 7 1 8 3_{26}_{35} 31 11_{12} 9 10

Figure 6. A potentially five-to-one graph, nodes numbered the same should be considered identical. Indicated are the signs of the derivatives of the partial conductances on the (7, 8) edge.

6-plexer 26 7 2 5 1 6 3 4 x 35 1 2 8 9 l_{1}(x)  (+) 36 1 4 8 9 37 14 15 l_{2}(x) (−) 38 1 5 8 9_{40} 16_{17}_{18}  ^{19}_{39} l_{3}(x) (+)  8 1 9 6 27 28 20 21 l_{4}(x)  (−) 8 1 9 3_{33}_{32} 34_{12}_{13} 11_{10} l_{5}(x) (−)  9 1 8 7 29_{30}_{31}_{23} 24_{25} 22

Figure 7. A possibly six-to-one graph

7-plexer 45 7 2 5 1 6 3 4 5 8 x 32 1 2 10 9 l_{1}(x)  (+) 37 1 4 9 10 36 15 16 l_{2}(x) (−) 38 1 8 9 10_{40} 17_{18}_{19}  ^{20}_{39} l_{3}(x) (+)  9 1 10 6 43 44 23 24 l_{4}(x)  (+) 9 1 10 3_{34}_{33} 35_{13}_{14} 11_{12} l_{5}(x) (−)  10 1 9 5 31_{30}_{29}_{25}_{27}_{28} 26 l_{6}(x) (−) 10 1 9 7 42 21 22 41

Figure 8. A potentially seven-to-one graph.