CIRCULAR PLANAR GRAPHS AND RESISTOR NETWORKS

E. B. CURTIS , D. INGERMAN AND J. A. MORROW ^{∗}

Abstract. We consider circular planar graphs and circular planar resistor networks. Associated with each circular planar graph Γ there is a set π(Γ) = {(P; Q)} of pairs of sequences of boundary nodes which are connected through Γ. A graph Γ is called critical if removing any edge breaks at least one of the connections (P; Q) in π(Γ). We prove that two critical circular planar graphs are Y − Δ equivalent if and only if they have the same connections. If a conductivity γ is assigned to each edge in Γ, there is a linear from boundary voltages to boundary currents, called the network response. This linear map is represented by a matrix Λ_{γ}. We show that if (Γ, γ) is any circular planar resistor network whose underlying graph Γ is critical, then the values of all the conductors in Γ may be calculated from Λ_{γ}. Finally, we give an algebraic description of the set of network response matrices that can occur for circular planar resistor networks.

Key words. graph, connections, conductivity, resistor network, network response

AMS(MOS) subject classifications. 05C40, 05C50, 90B10, 94C15

1. Introduction. This article is a continuation of [5], [6] and [7], and was inspired by [1] and [2]. Some related results have been announced in [3].

A \underline{graph with boundary} is a triple Γ = (V, V_{B}, E), where (V, E) is a finite graph with V = the set of nodes, E = the set of edges, and V_{B} is a nonempty subset of V called the set of boundary nodes. Γ is allowed to have multiple edges (i.e., more than one edge between two nodes) or loops (i.e., an edge joining a node to itself).

A \underline{circular planar graph} is a graph with boundary which is embedded in a disc D in the plane so that the boundary nodes lie on the circle C which bounds D, and the rest of Γ is in the interior of D. The boundary nodes can be labelled v_{1}, …, v_{n} in the (clockwise) circular order around C. A pair of sequences of boundary nodes (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}) such that the sequence (p_{1}, …, p_{k}, q_{k}, …, q_{1}) is in circular order is called a \underline{circular pair}.

A circular pair (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}) of boundary nodes is said to be \underline{connected through} Γ if there are k disjoint paths α_{1}, …, α_{k} in Γ, such that α_{i} starts at p_{i}, ends at q_{i} and passes through no other boundary nodes. We say that α is a \underline{connection} from P to Q. The notion of a connection between a pair of sequences of boundary nodes appears in [1] and [2]. The definition of a well-connected critical graph was given in [1]. In this paper, we consider graphs which are not necessarily well-connected.

For each circular planar graph Γ, let π(Γ) be the set of all circular pairs (P; Q) of boundary nodes which are connected through Γ.

∗ Department of Mathematics, University of Washington

There are two ways to remove an edge from a graph:

(1) By deleting an edge.

(2) By contracting an edge to a single node. (An edge joining two boundary nodes is not allowed to be contracted to a single node).

We say that removing an edge \underline{breaks the connection} from P to Q if there is a connection from P to Q through Γ, but there is not a connection from P to Q after the edge is removed. A graph Γ is called \underline{critical} if the removal of any edge breaks some connection in π(Γ).

Theorem 1. Suppose Γ_{1} and Γ_{2} are two critical circular planar graphs. Then π(Γ_{1}) = π(Γ_{2}) if and only if Γ_{1} and Γ_{2} are Y − Δ equivalent.

A \underline{conductivity} on a graph Γ is a function γ which assigns to each edge e in E a positive real number γ(e). A \underline{resistor network} (Γ, γ) consists of a graph with boundary together with a conductivity function γ.

Suppose (Γ, γ) is a resistor network with n boundary nodes. There is a linear map from boundary functions to boundary functions, constructed as follows. To each function f = {f(v_{i})} defined at the boundary nodes, there is a unique extension of f to all the nodes of Γ which satisfies Kirchhoff’s current law at each interior node. This function then gives a current I where I(v_{i}) is the current into the network at boundary node v_{i}. The linear map which sends f to I is called the Dirichlet-to-Neumann map in [5], [6] and [7]. This map is represented by a n × n matrix, Λ_{γ} (= Λ(Γ, γ)), called the \underline{network response}.

Theorem 2. Suppose (Γ, γ) is a circular planar resistor network which is critical as a graph. Then the values of the conductors are uniquely determined by, and can be calculated from Λ_{γ}.

In this situation we say γ is \underline{recoverable} from Λ_{γ}.

\underline{Notation}: Suppose A = \{a_{s,t}\} is a matrix, P = (p_{1}, …, p_{k}) is an ordered subset of the rows, and Q = (q_{1}, …, q_{m}) is an ordered subset of the columns. Then A(P; Q) denotes the k × m matrix obtained by taking the entries of A which are in rows p_{1}, …, p_{k} and columns q_{1}, …, q_{m}. Specifically, for each 1 ≤ i ≤ k and 1 ≤ j ≤ m,

A(P; Q)_{i,j} = a_{p_{i},q_{j}}

A pair of sequences of indices (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}) is called a \underline{circular pair} if a cyclic permutation of (p_{1}, …, p_{k}, q_{k}, …, q_{1}) is in order. If (P; Q) is a circular pair of indices, A(P; Q) is called a \underline{circular minor} of A.

Definition 1.1. For each integer n ≥ 2, let Ω_{n} be the set of n × n symmetric matrices M for which the sum of the entries in each row is 0, and which satisfy the following condition.

If M(P; Q) is a k × k circular minor of M, then (−1)^{k} det M(P; Q) ≥ 0.

This condition says that if M ∈ Ω_{n}, and (P; Q) is a circular pair of indices, then the matrix −M(P; Q) is \underline{totally non-negative} as in [9]. This condition implies that if M ∈ Ω_{n}, each off-diagonal entry is non-positive and each diagonal entry is non-negative.

Theorem 3. Suppose M is in Ω_{n}. Then there is a circular planar graph with a conductivity γ so that M = Λ(Γ, γ).

Definition 1.2. Suppose Γ is a circular planar graph with n boundary nodes, and π = π(Γ) is the set of circular pairs (P; Q) which are connected through Γ. A subset Ω(π) of Ω_{n} is defined by the following condition. For each circular pair of indices (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}),

(a) If (P; Q) ∈ π, then (−1)^{k} det M(P; Q) > 0.

(b) If (P; Q) ∉ π, then det M(P; Q) = 0.

Let (Γ, γ) be a critical circular planar resistor network and π(Γ) = π. In §4, we show that the network response matrix Λ_{γ} is in Ω(π). In §12, we show that if M ∈ Ω(π), then there is a conductivity γ on Γ so that M = Λ_{γ}. More generally, we have the following.

Theorem 4. Suppose Γ is a critical circular planar graph with N edges and π = π(Γ). Then the map which sends γ to Λ_{γ} is a diffeomorphism of (R^{+})^{N} onto Ω(π).

Remark 1. Theorems 1, 2, 3, and 4 show that there is a close relationship between circular planar resistor networks and matrices. The set of network response matrices for all circular planar graphs with n boundary nodes is Ω_{n}, which is the disjoint union of the sets Ω(π). For each M ∈ Ω_{n}, let π = {(P; Q)} be the set of circular pairs (P; Q) of indices for which det M(P; Q) ≠ 0. Associated with this π, there is a circular planar graph Γ with π(Γ) = π, and there is a conductivity γ on Γ with Λ(Γ, γ) = M. The graph Γ may be chosen to be critical, and then Γ is unique to within Y −Δ equivalence. If a graph Γ is chosen in this Y − Δ equivalence class, then the conductivity γ on Γ which gives M = Λ(Γ, γ) is unique.

Remark 2. For each of the sets π, let N(π) be the number of edges in a critical graph with π(Γ) = π. Suppose Γ be a circular planar graph with N edges. Then Γ is critical if and only if N = N(π(Γ)). If Γ is not critical, then there is a critical graph Γ′, with π(Γ′) = π(Γ). The graph Γ′ may be obtained from Γ by removal (by deletion and/or contraction) of N − N(π(Γ)) edges. If γ is a conductivity on Γ, there is a conductivity γ′ on Γ′ so that Λ(Γ′, γ′) = Λ(Γ, γ).

Table of Contents §1. Introduction §2. Schur Complements §3. Resistor Networks §4. Connections and Determinants §5. Y − Δ Transformations §6. Medial Graphs §7. Standard Graphs §8. Recoverability §9. Adjoining Edges §10. Totally Non-negative Matrices §11. Removing Edges §12. Surjectivity §13. Equivalence

This paper is almost entirely self-contained. In addition to matrix algebra, the proofs make use of the medial graphs of Steinitz and Theorem 5.2 of [7]. In §2, Schur complements are used to prove a determinant identity, originally due to Dodgson, that is used extensively in §10. For (Λ, γ) a resistor network, the response matrix Λ_{γ} is constructed in §3. The important properties of Λ_{γ} are established in §4. §5 describes Y − Δ and Δ − Y transformations of planar graphs. The medial graph of a circular planar graph, is defined in §6. In §7, the methods of Steinitz are used to show that in each Y − Δ equivalence class of critical circular planar graphs there is a standard represenative. In §8, we define three ways to adjoin an edge to a graph and we describe the effects of each of these adjunctions on the response matrices. Theorem 2 was proven in [7] for the standard representative of a well-connected critical circular planar graph. §9 of the present paper makes use of [7] to prove Theorem 2 for an arbitrary critical graph. §10 uses Dodgson’s identity to prove some facts about the matrices M in Ω_{n}. In §11, we show that removing a boundary edge or boundary spike from a critical graph results in another critical graph. In §12, we prove Theorems 3 and 4. In §13, we prove Theorem 1.

2. The Schur Complement. Suppose M is a square matrix and D be a nonsingular square submatrix of M. For convenience, assume that D is the lower right hand corner of M, so that M has the block structure:

M = [ \begin{matrix}A & B \\ C & D \end{matrix} ]

The Schur complement of D in M is the matrix M/D = A − BD^{−1}C. The Schur complement satisfies the following determinantal identity:

det M = det(M/D) · det D

If E is a non-singular square submatrix of D, then

det M = det(M/D) · det(D/E) · det E

In this situation, the following quotient formula is due to Haynsworth ([4]).

M/D = (M/E)/(D/E)

Let A = {a_{i,j}} be a n × n matrix, and a_{h,k} is a non-zero entry. The 1 × 1 matrix with entry a_{h,k} is denoted [a_{h,k}]. For the Schur complement, A/[a_{h,k}], we have

det A = (−1)^{h+k}a_{h,k} · det(A/[a_{h,k}])

Suppose A is a n × n matrix, with n ≥ 2. If i and j are any two indices, A[i; j] will denote the (n − 1) × (n − 1) matrix obtained by \underline{deleting} row i and column j. Similarly, if (h, i) and (j, k) are indices, then A[h, i; j, k] will denote the (n − 2) × (n − 2) matrix obtained by \underline{deleting} rows h and i and columns j and k. We shall make extensive use of the following identity, due to Dodgson [8].

Lemma 2.1. For any indices [h, i; j, k] with 1 ≤ h < i ≤ n and 1 ≤ j < k ≤ n,

det A · det A[h, i; j, k] = det A[h; j] · det A[i; k] − det A[h; k] · det A[i; j]

Proof. By re-ordering the rows and columns, we may assume that the indices are (h, i) = (1, 2) and (j, k) = (1, 2). Let B = A[1, 2; 1, 2]. Then A has the form:

A = [ \begin{matrix}a & b & x \\ c & d & y \\ w & z & B \end{matrix} ]

where x and y are 1 × (n − 2) row vectors, w and z are (n − 2) × 1 column vectors. Temporarily assume that B is non-singular. For the Schur complement A/B we have:

A/B = [ \begin{matrix}a − xB^{−1}w & b − xB^{−1}z \\ c − yB^{−1}w & d − yB^{−1}z \end{matrix} ]

det(A/B) = (a − xB^{−1}y)(d − yB^{−1}z) − (b − xB^{−1}z)(c − yB^{−1}w)
= det(A[2; 2]/B) · det(A[1; 1]/B) − det(A[1; 2]/B) · det(A[2; 1]/B)

Using the determinantal identity for Schur complements, we have

det A · det B = det A[2; 2] · det A[1; 1] − det A[1; 2] · det A[2; 1]

This is a polynomial relation which holds for the n^{2} values of the entries of A whenever det B ≠ 0. Therefore it is an identity in the coefficients of A.

3. Resistor Networks. In this section we construct the response matrix Λ(Γ, γ) for a resistor network (Γ, γ). This is done first when Γ is connected as a graph; the response matrix for a general network is obtained by taking the direct sum of the response matrices of the connected components.

Suppose (Γ, γ) = (V, V_{B}, E, γ) is a connected resistor network, with d vertices numbered v_{1}, …, v_{d}. The Kirchhoff matrix K = K(Γ, γ) is the d × d matrix K constructed as follows.

(1) If i ≠ j then K_{i,j} = − ∑ γ(e), where the sum is taken over all edges e joining v_{i} to v_{j}. (If there is no edge joining v_{i} to v_{j}, then K_{i,j} = 0.)

(2) K_{i,i} = ∑ γ(e), where the sum is taken over all edges e with one endpoint at v_{i} and the other endpoint not v_{i}.

The Kirchhoff matrix has the following interpretation. If u is a voltage defined at the nodes of Γ, then c = Ku is the resulting current flow. In coordinates, if u = {u(v_{i})}, then c_{j} = ∑_{i} K_{i,j}u(v_{i}) is the current flowing into the network at node v_{j}.

If a function f is imposed at the boundary nodes, the function u which satisfies Kirchhoff’s current law c_{j} = 0 at each interior node v_{j}, and which agrees with f at the boundary nodes, is called the \underline{potential} due to f.

Suppose there are N edges numbered e_{1}, …, e_{N}. A d × N matrix Q is constructed as follows. If e is an edge joining v_{i} to v_{j} with i < j, then

Q_{i,k} = +\sqrt{γ(e)}
Q_{j,k} = −\sqrt{γ(ek)}
Q_{h,k} = 0, otherwise

A calculation shows that K = Q · Q^{T}. Thus K is positive semi-definite. Suppose x = (x_{1}, …, x_{d}). Then xKx^{T} = 0 if and only if xQ = 0. Let e = v_{i}v_{j} be an edge in Γ. Then xQ = 0 implies that

x_{i}\sqrt{γ(e)} − x_{j}\sqrt{γ(e)} = 0

Thus x_{i} = x_{j}. Since Γ is connected as a graph, xK^{T} x = 0 if and only if x_{i} = x_{j} for all vertices v_{i} and v_{j}.

Lemma 3.1. Suppose (Γ, γ) is a connected resistor network. Let P = (p_{1}, …, p_{k}) be a non-empty proper subset of the vertices. Then the matrix K(P; P) is positive definite.

Proof. Let A = K(P; P), and suppose y = (y_{1}, …, y_{k}) is a vector with yAy^{T} = 0. Let x = (x_{1}, …, x_{d}) be the vector with x_{p_{i}} = y_{i} for 1 ≤ i ≤ k, and and x_{j} = 0 if j is not in P. Then xKx^{T} = yAy^{T} = 0. Since P is a proper subset of V, at least one of the x_{i} is 0. Since Γ is connected, all the x_{i} must be 0. Hence the y_{i} are 0 also.

Suppose (Γ, γ) = (V, V_{B}, E, γ) is a connected resistor network. Let I = V − V_{B} be the set of interior nodes. By Lemma 3.1, if I is not empty, the matrix K(I, I) is nonsingular.

Theorem 3.2. Suppose (Γ, γ) is a connected resistor network. Then the network response matrix Λ_{γ} is the Schur complement

Λ_{γ} = K/K(I; I)

Proof. If I is the empty set, K/K(I; I) is defined to be to be K, and Λ_{γ} = K. Otherwise, I is nonempty. For convenience, assume the nodes are numbered so that V_{B} = {v_{1}, v_{2}, …, v_{n}}, and I = {v_{n+1}, v_{n+2}, …, v_{d}}. Let D = K(I; I). Then K has a block structure:

K = [ \begin{matrix}A & B \\ C & D \end{matrix} ]

Suppose that f = {f(v_{i}); i = 1, …, n} is a function imposed at the boundary nodes. Let g = {g(v_{i}); i = n + 1, …, d} be the resulting potential at the interior nodes. Kirchhoff’s current law says that the sum of the currents into each interior node is 0. Thus

[ \begin{matrix}A & B \\ C & D \end{matrix} ] [ \begin{matrix}f \\ g \end{matrix} ] = [ \begin{matrix}c \\ 0 \end{matrix} ]

This implies that (A − BD^{−1}C)f = c. Therefore the response matrix representing the Dirichlet-to-Neumann map is Λ_{γ} = A − BD^{−1}C.

If A = (a_{1}, …, a_{s}) and B = (b_{1}, …, b_{t}) are two sequences of nodes, A + B stands for the sequence (a_{1}, …, a_{s}, b_{1}, …, b_{t}).

Lemma 3.3. Suppose (Γ, γ) is a connected resistor network, and let Λ_{γ} be its response matrix. Let P and Q be two sequences of boundary nodes of Γ. Then the submatrix Λ_{γ}(P; Q) is obtained as the Schur complement

Λ_{γ}(P; Q) = K(P + I; Q + I)/K(I; I)

Proof. This follows from Theorem 3.2 and the definition of Schur complement.

Suppose Γ = (V, V_{B}, E) is a connected graph with n boundary nodes. Let p be one of the boundary nodes. Let Γ′ = (V′, V′_{B}, E′) be the graph with V′ = V, V′_{B} = V_{B} − p and E′ = E. That is Γ′ is the same as Γ, except that p is declared to be an interior node. If γ is a conductivity on Γ, we assign the same values to the conductors in Γ′. Let Λ′_{γ} denote the response matrix for Γ′. By Theorem 3.2,

Λ′_{γ} = K/K(I + p; I + p)

Suppose P = (p_{1}, …, p_{k}) and Q = (q_{1}, …, q_{k}) are two sequences of boundary nodes, and p is a boundary node not in P ∪ Q.

Lemma 3.4. In this situation,

(1) Λ′_{γ}(P; Q) = Λ_{γ}(P + p; Q + p)/Λ_{γ}(p; p)

(2) det Λ′_{γ}(P; Q) = det Λ_{γ}(P + p; Q + p)/ det Λ_{γ}(p; p)

Proof. The first follows from the Haynsworth quotient formula. The second follows from the determinantal identity for Schur complements.

4. Connections and Determinants. Suppose Γ = (V, V_{B}, E) is a connected graph with boundary. Γ is not assumed to be planar. Let I = V − V_{B} denote the set of interior nodes. If p and q are two boundary nodes, a \underline{path} from p to q through Γ is a sequence of edges p, r_{1}, r_{1}, r_{2}, …, r_{m}, q in Γ where the r_{j} are distinct interior nodes. Suppose P = (p_{1}, …, p_{k}) and Q = (q_{1}, …, q_{k}) are two disjoint sets of boundary nodes. A \underline{connection} from P to Q through Γ is a set α = (α_{1}, …, α_{k}) of disjoint paths through Γ, where for each 1 ≤ i ≤ k, α_{i} is a path from P_{i} to Q_{τ(i)}, and τ is an element of the permutation group S_{k}. Let C(P; Q) be the set of connections from P to Q. For each α = (α_{1}, …, α_{k}) in C(P; Q), let

τ_{α} be the permutation of (q_{1}, q_{2}, …, q_{k}) which results at the endpoints of the paths (α_{1}, α_{2}, …, α_{k});

E_{α} be the set of edges in α;

J_{α} be the set of interior nodes which are not the ends of any edge in α.

Lemma 4.1. Let (Γ, γ) be a connected resistor network. Let P = (p_{1}, p_{2}, …, p_{k}) and Q = (q_{1}, q_{2}, …, q_{k}) be two disjoint sequences of boundary nodes. Then

det Λ(P; Q) · det K(I, I) = (−1)^{k} ∑_{τ∈S_{k}} sgn(τ) \{ ∑ ; \begin{matrix}α ∈ C(P; Q) \\ τ_{α} = τ \end{matrix} ∏_{e∈E_{α}} γ(e) · det K(J_{α}; J_{α})\}

Proof. Let ν = k +k′, where k′ is the number of interior nodes in Γ. Let the interior nodes be numbered r_{i} for i = k + 1, …, k + k′. By taking the Schur complement with respect to K(I, I), we have

det Λ(P; Q) · det K(I, I) = det K(P + I; Q + I)

The ν × ν matrix K(P + I; Q + I) is denoted M = {m_{i,j}}. Then

det M = ∑_{σ∈S_{ν}} sgn(σ) ∏_{i=1}^{ν} m_{i,σ(i)}

Here S_{ν} denotes the symmetric group on ν symbols. For each 1 ≤ i ≤ k, let n_{i} be the first index j for which σ^{j}(i) ≤ k. For each 1 ≤ i ≤ k, and 0 ≤ j ≤ n_{i}, let a(i, j) = σ^{j}(i). Let τ be the permutation of 1, 2, …, k where τ(i) = a(i, n_{i}). Thus each σ ∈ S_{ν} gives a diagram of the following form:

1 = a(1, 0) ↦^{σ} a(1, 1) ↦^{σ} a(1, 2) ↦^{σ} … ↦^{σ} a(1, n_{1}) = τ(1)

2 = a(2, 0) ↦^{σ} a(2, 1) ↦^{σ} a(2, 2) ↦^{σ} … ↦^{σ} a(2, n_{2}) = τ(2)

…

k = a(k, 0) ↦^{σ} a(k, 1) ↦^{σ} a(k, 2) ↦^{σ} … ↦^{σ} a(k, n_{k}) = τ(k)

Let A be the subset of {1, 2, …, ν} consisting of the a(i, j) for 1 ≤ i ≤ k 0 ≤ j < n_{i}. Let t = ∑ n_{i}, which is the cardinality of A. Let B be the set {1, 2, …, ν} − A. Then σ may be expressed as a product σ = ϕ · μ, where ϕ is a permutation of A, and μ is a permutation of B. Let ϕ be expressed as a product of disjoint cycles ϕ = ϕ_{1} · ϕ_{2} · . . . · ϕ_{s}. Then sgn(σ) = (−1)^{t−s}sgn(μ). Then τ will also be expressed as a product of s cycles. τ = ψ_{1} · ψ_{2} ⋯ ψ_{s} and sgn(τ) = (−1)^{k−s}. Thus sgn(σ) = (−1)^{k+t}sgn(τ)sgn(μ).

The diagram above determines a set α = (α_{1}, …, α_{k}) of sequences of nodes in Γ, where α_{i} is the sequence a(i, 0), a(i, 1), …, a(i, n_{i}). For each 1 ≤ i ≤ k, a(i, 0) = p_{i} and a(i, n_{i}) = q_{τ(i)}. For each 1 ≤ i ≤ k, and 0 < j < n_{i}, a(i, j) is the interior node r_{a(i,j)}.

The product ∏_{i=1}^{ν} m_{i,σ(i)} can be non-zero only if α = (α_{1}, α_{2}, …, α_{k}) forms a connection

through Γ from P to Q. For each α ∈ C(P; Q), let S(α) be the set of σ ∈ S_{ν} for which the connection is α. As σ varies over S(α), μ varies over the permutations of J_{α}. Then

∑_{σ∈S(α)} sgn(σ) ∏_{i=1}^{ν} m_{i,σ(i)} = ∑_{σ∈S(α)}(−1)^{k+t}sgn(τ) ∏_{e∈E_{α}}(−γ(e)) · sgn(μ) · ∏_{i∈J_{α}} m_{i,μ(i)}

= (−1)^{k}sgn(τ) · ∏_{e∈E_{α}} γ(e) · det K(J_{α}; J_{α}).

For each τ ∈ S_{k}, take the sum over all α which induce this τ. Then take the sum over all τ ∈ S_{k}, and the proof is complete.

This answers a question raised by [2]. In particular, it follows from Lemma 4.1 that if det Λ(P; Q) = 0, then either

(1) There is no connection from P to Q;

or (2) There are (at least) two connections α and β from P to Q, with permutations τ_{α} and τ_{β} of opposite sign.

The following theorem is very important for our purposes. It first was proved for well-connected circular planar networks in [7], and for general circular planar networks in [1]. The proof we give here is based on Lemma 4.1.

Theorem 4.2. Suppose Γ is a circular planar resistor network and (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}) is a circular pair of sequences of boundary nodes.

(a) If (P; Q) are not connected through Γ, then det Λ(P; Q) = 0.

(b) If (P; Q) are connected through Γ, then (−1)^{k} det Λ(P; Q) > 0.

Proof. We first consider the case when Γ is connected as a graph. By Lemma 3.1, K(I, I) is positive definite, so det K(J, J) > 0 for all J ⊆ I. The sequence (p_{1}, …, p_{k}, q_{k}, …, q_{1}) is in circular order around the boundary of Γ. If there is a connection from P to Q, it must connect p_{i} to q_{i} for 1 ≤ i ≤ k. Thus each τ which appears in Lemma 4.1 is the identity permutation, so all the terms in the sum have the same sign. In the general case, Γ is a disjoint union of connected components Γ_{i}, and Λ(Γ, γ) is a direct sum of the Λ(Γ_{i}, γ_{i}) .

When we say that removal of an edge e from Γ breaks the connection from P to Q, we mean that P and Q are connected through Γ (possibly in many ways), and that P and Q are not connected through the graph Γ′ which is the graph Γ with e removed. By Theorem 4.2, this is equivalent to the two assertions that det Λ(P; Q) ≠ 0, and det Λ′(P; Q) = 0.

An edge e between a pair of adjacent boundary nodes is called a \underline{boundary edge}. If r is a boundary node which is joined by an edge to only one other node p which is an interior node, the edge rp is called a \underline{boundary spike}.

Corollary 4.3. Suppose Γ is a connected circular planar resistor network and e = pq is a boundary edge, such that deleting e breaks the connection between a circular pair (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}). Then pq is either p_{1}q_{1} or p_{k}q_{k}, and

det Λ(P; Q) = −γ(e) · det Λ(P − p; Q − q)

Proof. The edge pq must be either p_{1}q_{1} or p_{k}q_{k}. As the two cases are similar, WLOG assume the former. We consider det K(P + I; Q + I) as a linear function F (z) of the first column z of K(P + I; Q + I). Let ξ = γ(e). Then z = x + y, where

x = [ \begin{matrix}−ξ \\ 0 \end{matrix} ]  and  y = [ \begin{matrix}0 \\ a \end{matrix} ]

Then F (z) = F (x) + F (y). But F (y) = 0, since P and Q are not connected through Γ after p_{1}q_{1} is deleted. Thus

det K(P + I; Q + I) = −ξ det K(P − p_{1} + I; Q − q_{1} + I)

The result follows by taking the Schur complement with respect to K(I; I), and using Lemma 3.3.

Corollary 4.4. Suppose Γ is a connected circular planar resistor network and rp is boundary spike joining a boundary node r to an interior node p. Suppose that contracting rp breaks the connection between a circular pair (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}). Then r ∉ P ∪ Q, and

det Λ(P + r; Q + r) = γ(pr) · det Λ(P; Q)

Proof. It is clear that r ∉ P ∪ Q. Let ξ = γ(pr). Then K(P + r + I; Q + r + I) has a submatrix K(r, p; r, p) which has the form:

K(r, p; r, p) = [ \begin{matrix}ξ & −ξ \\ −ξ & w \end{matrix} ]

The remaining entries of K(P + r + I; Q + r + I) in the column corresponding to r are 0, and the remaining entries of K(P + r + I; Q + r + I) in the row corresponding to r are 0. Thus

det K(P + r + I; Q + r + I) = ξ det K(P + I; Q + I) − ξ^{2} det K(P + I − p; Q + I − p)

The assertion of the corollary follows upon dividing by K(I; I), interpreting each of the terms as the determinant of a Schur complement, and using Lemma 3.3.

5. Y - Δ Transformations. Suppose Γ = (V, V_{B}, E) is a circular planar graph, and s is a trivalent interior node with incident edges sp, sq and sr, as in Fig 1a.

[figure: p; q; r; Fig 1a; p; s; q; r; Fig 1b]

A \underline{Y − Δ transformation} removes the vertex s, the edges sp, sq, sr, and adds three new edges pq, qr, and rp as in Fig 1b. Similarly, if pqr is a triangle in Γ as in Fig 1b, then a Δ − Y transformation removes the edges pq, qr, and rp, inserts a new vertex s, and adds three new edges ps, qs, and rs, to arrive at Fig 1a. All other nodes are fixed during the transformation.

We say that two circular planar graphs Γ_{1} and Γ_{2} are \underline{Y − Δ equivalent} if Γ_{1} can be transformed to Γ_{2} by a sequence of Y − Δ or Δ − Y transformations.

Lemma 5.1. If Γ_{1} and Γ_{2} are two circular planar graphs which are Y −Δ equivalent, then π(Γ_{1}) = π(Γ_{2}).

Proof. Suppose Γ_{1} is transformed into Γ_{2} where the Y of Fig 1a is replaced by the triangle of Fig 1b. Let α and β be disjoint paths in Γ_{1} where α passes through p and β passes through edges rs and sq. The corresponding paths in Γ_{2} are α and β′, where β′ is the same as β except that the two edges rs and sq are replaced by the single edge rq.

Lemma 5.2. Suppose Γ_{1} and Γ_{2} are two circular planar graphs which are Y − Δ equivalent. Then Γ_{1} is critical if and only if Γ_{2} is critical.

Proof. Suppose Γ_{1} is transformed into Γ_{2} where the Y of Fig 1a is replaced by the triangle of Fig 1b. Assume that Γ_{1} is not critical. We need to consider three cases.

(1) Suppose e is an edge in Γ_{1} which is not ps, qs, or rs and e can be removed without breaking a connection in π(Γ_{1}). Then removal of the same edge in Γ_{2} breaks no connection in π(Γ_{2}).

(2) Suppose deletion of ps breaks no connection in π(Γ_{1}). Then deletion of pr breaks no connection in π(Γ_{2}).

(3) Suppose contraction of ps breaks no connection in π(Γ_{1}). Then deletion of rq breaks no connection in π(Γ_{2}).

Assume that Γ_{2} is not critical. Again there are three cases.

(4) Suppose e is an edge in Γ_{2} which is not pq, qr, or rp and e can be removed without breaking a connection in π(Γ_{2}). Then removal of the same edge in Γ_{1} breaks no connection in π(Γ_{1}).

(5) Suppose deletion of rq breaks no connection in π(Γ_{2}). Then contraction of ps breaks no connection in π(Γ_{1}).

(6) Suppose contraction of rq breaks no connection in π(Γ_{2}). Then contraction of rs breaks no connection in π(Γ_{1}).

Lemma 5.3. Suppose Γ_{1} and Γ_{2} are two circular planar graphs which are Y − Δ equivalent. If γ_{1} is a conductivity on Γ_{1} then there is a conductivity γ_{2} on Γ_{2}, with Λ(Γ_{1}, γ_{1}) = Λ(Γ_{2}, γ_{2}).

Proof. Suppose Γ_{1} is transformed into Γ_{2} where the Y of Fig 1a is replaced by the triangle of Fig 1b. Suppose γ_{1}(ps) = a, γ_{1}(qs) = b, γ_{1}(rs) = c. The corresponding conductivity γ_{2} on Γ_{2} is

γ_{2}(pq) = \frac{ab}{a + b + c}
γ_{2}(qr) = \frac{bc}{a + b + c}
γ_{2}(rp) = \frac{ac}{a + b + c}

and γ_{2}(e) = γ_{1}(e) for all other edges.

Suppose Γ_{1} is transformed into Γ_{2} where the triangle of Fig 1b is replaced by the Y of Fig 1a. Suppose γ_{1}(pq) = a, γ_{1}(qr) = b, γ_{1}(rp) = c. The corresponding conductivity γ_{2} on Γ_{2} is

γ_{2}(ps) = \frac{ab + ac + bc}{b}
γ_{2}(qs) = \frac{ab + ac + bc}{c}
γ_{2}(rs) = \frac{ab + ac + bc}{a}

and γ_{2}(e) = γ_{1}(e) for all other edges. If u is a function defined at the nodes of Γ_{1} which satisfies Kirchhoff’s current law, the same function (omitting the point s) satisfies Kirchhoff’s current law on Γ_{2}. Hence Λ(Γ_{1}, γ_{1}) = Λ(Γ_{2}, γ_{2}).

Lemma 5.4. Suppose Γ_{1} and Γ_{2} are two circular planar graphs which are Y − Δ equivalent. If γ_{1} is recoverable from Λ(Γ_{1}, γ_{1}), then γ_{2} is recoverable from Λ(Γ_{2}, γ_{2}).

Proof. This follows from Lemma 5.3.

6. Medial graphs. Suppose Γ = (V, V_{B}, E) is a circular planar graph with n boundary nodes. Γ is assumed to be embedded in in the plane so that the boundary nodes v_{1}, v_{2}, …, v_{n} occur in clockwise order around a circle C and the rest of Γ is in the interior of C. The construction of the medial graph M(Γ) is similar to that in [10] (p 239). The medial graph M(Γ) depends on the embedding. First, for each edge e of Γ, let m_{e} be its midpoint. Next, place 2n points t_{1}, t_{2}, … t_{2n} on C so that

t_{1} < v_{1} < t_{2} < t_{3} < v_{2} < … < t_{2n−1} < v_{n} < t_{2n} < t_{1}

in the clockwise circular order around C.

(1) The vertices of M(Γ) consist of the points m_{e} for e ∈ E, and the points t_{i} for i = 1, 2, …, 2n.

(2) The edges in M(Γ) are as follows. Two vertices m_{e} and m_{f} are joined by an edge whenever e and f have a common vertex and e and f are incident to the same face in Γ. There is also one edge for each point t_{j} as follows. The point t_{2i} is joined by an edge to m_{e} where e is the edge of the form e = v_{i}r which comes first after arc v_{i}t_{2i} in clockwise order around v_{i}. The point t_{2i−1} is joined by an edge to m_{f} where f is the edge of the form f = v_{i}s which comes first after arc v_{i}t_{2i−1} in counter-clockwise order around v_{i}.

The vertices of the form m_{e} of M(Γ) are 4-valent; the vertices of the form t_{i} are 1-valent. An edge uv of M(Γ) has a \underline{direct extension} vw if the edges uv and vw separate the other two edges incident to the vertex v. A path u_{0}u_{1} … u_{k} in M(Γ) is called a \underline{geodesic arc} if each edge u_{i−1}u_{i} has edge u_{i}u_{i+1} as a direct extension. A geodesic arc u_{0}u_{1} … u_{k} is called a \underline{geodesic} if either

(1) u_{0} and u_{k} are points on the circle C.

or (2) u_{k} = u_{0} and u_{k−1}u_{k} has u_{0}u_{1} as direct extension.

A subgraph L of M(Γ) is called a \underline{lens} provided that:

(1) L consists of a simple closed path path u_{0}u_{1} … u_{k}v_{0}v_{1} … v_{m}u_{0} and all the nodes and edges of M(Γ) in the bounded connected component of the complement of L in the plane.

(2) u_{0}u_{1} … u_{k}v_{0} and v_{0}v_{1} … v_{m}u_{0} are two geodesic arcs such that no inner edge of L is incident to u_{0} or v_{0}.

If each geodesic in M(Γ) begins and ends on C, has no self-intersection, and if M(Γ) has no lenses, we say that M(Γ) is \underline{lensless}.

A \underline{triangle} in M(Γ) is a triple \{f, g, h\} of geodesics which intersect to form a triangle with no other intersections within the configuration, as in Fig 2a.

[figure: f; h; g; Fig 2a; f; h; g; Fig 2b]

Suppose \{f, g, h\} form a triangle as in Fig 2a. A \underline{motion} of \{f, g, h\} consists of replacing this configuration with that of Fig 2b.

Lemma 6.1. Two circular planar graphs are Y − Δ equivalent if and only if their medial graphs are equivalent under motions.

Proof. Each Y − Δ transformation of Γ corresponds to a motion on M(Γ). Conversely, a motion on M(Γ) corresponds to a Y − Δ transformation of Γ.

We shall make extensive use of the following Lemma. Our proof is an adaptation of a proof of Steinitz to our situation; see [10] and [11].

Lemma 6.2. Suppose Γ is a circular planar graph, for which M(Γ) is lensless. Suppose g and h intersect at p. Suppose g intersects C at q and h intersects C at r. Assume F = {f_{1}, …, f_{m}} is a set of geodesics with the property that for each 1 ≤ i ≤ m, f_{i} intersects g between p and q if and only if f_{i} intersects h between p and r. Then a finite sequence of motions will remove all members of F from the sector qpr.

Proof. For each i = 1, …, m, let v_{i} be the point of intersection (if there is one) of f_{i} with g between p and q. For each f_{i} which intersects another of the f_{j} within sector qpr, let D_{i} be the first point of intersection on f_{i} after v_{i} in sector qpr. Let D = {D_{i}} be the set of points obtained in this way. If D is empty, let f_{i} be the geodesic in F such that v_{i} is closest to p, and {g, h, f_{i}} form a triangle. A motion will remove f_{i} from sector qpr. Otherwise, D is nonempty. Each point D_{i} ∈ D is the point of intersection of two of the geodesics, say f_{i} and f_{j}. Let D be a point in D for which the number of regions within the configuration formed by f_{i} and f_{j} and g is a minimum. This minimum must be one, or there would be another geodesic which intersects f_{i} between v_{i} and D or which intersects f_{j} between v_{j} and D. Then {g, f_{i}, f_{j}} form a triangle. A motion will reduce the number of regions within sector qpr. After a finite number of motions, no f_{i} crosses into the sector.

Lemma 6.3. Suppose Γ is a circular planar graph, for which M(Γ) has a lens. Then Γ is Y − Δ equivalent to a graph Γ′ which has either a pair of edges in series, or a pair of edges in parallel.

Proof. Suppose g and h are two geodesics which intersect at p_{1} and p_{2} to form a lens L. WLOG assume that L is a lens with the fewest number of regions inside L. Each geodesic f which intersects g between p_{1} and p_{2} also intersects h between p_{1} and p_{2}, or there would be a lens with fewer regions than L. An argument similar to that of 6.2 shows that all of these f may be removed from L. Thus Γ is Y − Δ equivalent to a graph Γ′ for which M(Γ′) has an empty lens. This empty lens corresponds either to a pair of edges in series (if there is a vertex of Γ′ within L), or to a pair of edges in parallel (if there is no vertex of Γ′ within L).

Lemma 6.4. If Γ is a critical circular planar graph, then M(Γ) is lensless.

Proof. If there were a lens, a closed geodesic or a geodesic with a self-intersection in M(Γ), then Γ would be Y − Δ equivalent to a graph Γ′ with a pair of edges in series or in parallel, or with an interior pendant or an interior loop. In each case an edge could be removed from Γ′ without breaking any connection, so Γ′ would not be critical, and hence also Γ would not be critical.

In §13, we show that if M(Γ) is lensless, then Γ is critical.

7. Standard Graphs. Suppose Γ is a circular planar graph with n boundary nodes which is embedded in the plane so that the boundary nodes v_{1}, …, v_{n} occur in clockwise order on a circle C and the rest of Γ is in the interior of C. Assume the medial graph M(Γ) is lensless. Then M(Γ) has n geodesics each of which intersects C twice. The n geodesics intersect C in 2n distinct points. These 2n points are labelled t_{1}, …, t_{2n}, so that

t_{1} < v_{1} < t_{2} < t_{3} < v_{2} < … < t_{2n−1} < v_{n} < t_{2n} < t_{1}

in the circular order around C. The geodesics are labelled as follows. Let g_{1} be the geodesic which begins at t_{1}. The remaining geodesics are labelled g_{2}, g_{3}, …, g_{n} so that if i < j, then the first point of intersection of g_{i} with C occurs before the first point of intersection of g_{j} with C in the clockwise order starting from t_{1}. For each i = 1, 2, …, 2n, let z_{i} be the number associated with the geodesic which intersects C at t_{i}. In this way we obtain a sequence z = z_{1}, z_{2}, …, z_{2n}, called the z-sequence for M(Γ). Each of the numbers from 1 to n occurs in z exactly twice. If i < j, and if the occurrences of i and j appear in z in the order

… i … j … i … j …

we say that i and j \underline{interlace} in z; otherwise, we say that i and j do not interlace in z.

Suppose z = z_{1}, z_{2}, …, z_{2n} is a sequence which contains each of the the numbers 1, 2, …, n twice. Assume that if i < j, the first occurrence of i comes before the first occurrence of j. Associated with this sequence, there is a standard arrangement A(z), of n pseudolines {g_{i}} in the disc, constructed as follows. Place 2n points in clockwise order around the circle C and label them x_{1}, …, x_{n} and y_{1}, …, y_{n} as follows. The points labelled x_{i} and y_{i} are to be placed at positions corresponding to the two occurrences of i in the sequence z_{1}, …, z_{2n}, with x_{i} < y_{i}. We join each x_{i} to y_{i} by a geodesic g_{i}. If i and j interlace in z, then g_{i} will be made to intersect g_{j}; the point of intersection is denoted x(i, j), with the convention that x(j, i) denotes the same point as x(i, j).

First, join x_{1} to y_{1} by a pseudoline g_{1}. After g_{1}, …, g_{m−1} have been placed within C, the pseudoline g_{m} joining x_{m} to y_{m} is placed as follows. For each i ≤ m − 1, if m interlaces i in z, place a point x(i, m) on g_{i} closer to y_{i} than any previously placed point on g_{i}. Now let g_{m} join x_{m} to y_{m} passing through the points x(i, m) which have just been placed. The points y_{i} which are between x_{m} and y_{m} occur in the same order on C as the points x(i, m) occur on g_{m}.

When all the pseudolines g_{1}, …, g_{n} are in place, the arrangement A(z) has sequence z. The intersection points x(i, j) occur as follows. For each i ≤ m − 1, the points x(i, j) which are on g_{i} appear between x_{i} and y_{i} so that:

(1) If i < j < k, then x(i, j) appears before x(i, k).
(2) If j < i < k, then x(i, j) appears before x(i, k).

(3) If j < k < i, then x(i, j) and x(i, k) appear on g_{i} in the same order as y_{j} and y_{k} appear in z.

Let {x_{1}, …, x_{n}} ∪ {y_{1}, …, y_{n}} = {t_{1}, …, t_{2n}} where t_{1} < … < t_{2n} in the clockwise order around the circle C. Place n boundary points v_{1}, …, v_{n} on C so that the points

t_{1} < v_{1} < t_{2} < t_{3} < v_{2} < … < t_{2n−1} < v_{n} < t_{2n}

are in clockwise circular order on C. Next color the regions formed by M(Γ(z)) inside C in two colors, black and white, with each v_{i} in a black region. To obtain the standard graph Γ(z), for which M(Γ(z)) = A(z), we must assume that each of the black regions contains at most one of the vertices v_{i}. After a vertex has been placed in each black region, they are joined by edges, with one edge passing through each of the points x(i, j).

Lemma 7.1. Let Γ be a connected circular planar graph with n boundary nodes. Assume M(Γ) is lensless. Let z = z_{1}, z_{2}, … z_{2n} be the z-sequence associated with Γ, and let Γ(z) be the standard graph constructed above. Then Γ is Y − Δ equivalent to Γ(z).

Proof. We make motions in M(Γ) to transform it to A(z). Geodesic g_{i} intersects the outer circle C at two points x_{i} and y_{i}, with x_{i} < y_{i}. The points x_{1}, x_{2}, …, x_{n} and y_{1}, y_{2} …, y_{n} occur in the order of z around C. If i and j interlace in z, the geodesic g_{j} intersects g_{i}. Let x(i, j) = x(j, i) be the point of intersection of g_{i} with g_{j}, and let S(i, j) be the sector formed by x_{i}, x(i, j) and x_{j}. The location of the points x(i, j) is changed by the motions of M(Γ).

Let k be the first index for which g_{k} intersects a previous geodesic. Then g_{k} must intersect g_{k−1}. Consider the geodesics from the set {g_{k+1}, g_{k+2}, … g_{n}} which intersect g_{k} between x(k − 1, k) and x_{k}. Any such geodesic also intersects g_{k−1} between x(k − 1, k) and x_{k−1}. Lemma 6.2 implies that finite sequence of motions will remove g_{k+1}, …, g_{n} from the sector S(k − 1, k). This process is repeated to remove all intersections of g_{k+1}, …, g_{n} from the sectors S(i, k) for i = k − 2, …, 1.

We perform a similar process at steps k + 1, …, n − 1. After step (m − 1), the geodesics are in position so that if i < j < m, the geodesics g_{m}, g_{m+1}, g_{k+1}, … g_{n} have no intersections within any of the sectors S(i, j). Note that for each 1 ≤ i < m, if g_{m} intersects g_{i}, then for all j < m the point of intersection x(i, m) is between x(i, j) and y_{i} on g_{i}. Also the set of points

{x_{m}, x(m, 1), … x(m, m − 1), y_{m}}

occur in the following order along g_{m}: if j < m and k < m, with j ≠ k , then x(m, j) and x(m, k) appear in the same order along g_{m} as y_{j} and y_{k} appear in z.

For step(m), Lemma 6.2 implies that we can remove geodesics g_{m+1}, …, g_{n} from the sectors S(j, m) for 1 ≤ j < m. These geodesics are removed from the sectors S(j, m) in the same order in which the x(m, j) appear on g_{m}.

Continue until m = n − 1, when all intersections are as in A(z).

Theorem 7.2. Suppose Γ_{1} and Γ_{2} are two connected circular planar graphs, each with n boundary nodes. Assume the medial graphs M(Γ_{1}) and M(Γ_{2}) are lensless. Then Γ_{1} and Γ_{2} are Y − Δ equivalent if and only if M(Γ_{1}) and M(Γ_{2}) and have the same z-sequence.

Proof. A Y − Δ transformation does not change the z-sequence. Conversely, if M(Γ_{1}) and M(Γ_{2}) and have the same z-sequence, then Γ_{1} and Γ_{2} are each be Y − Δ equivalent to the same standard graph Γ(z).

When the sequence z is 1, …, n, 1, … n, the standard standard arrangement A(z) is denoted A_{n} and the standard graph Γ(z) is denoted Σ_{n}. In A_{n}, every pseudoline g_{i} intersects every other pseudoline, and there are \frac{1}{2}n(n − 1) points of intersection x(i, j). For each 1 ≤ i ≤ n, the points

x_{i}, x(i, 1), x(i, 2), … x(i, i − 1), x(i, i + 1), … x(i, n), y_{i}

occur in order along g_{i}.

The standard graph Σ_{n} has \frac{1}{2}n(n − 1) edges. The graphs Σ_{6} and Σ_{7} are shown in Fig 3.

[figure: v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; Σ_{6}; v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; v_{7}; Σ_{7}; Fig 3]

As in [1], a circular planar graph is called \underline{well-connected} if every circular pair (P; Q) is connected through Γ.

Proposition 7.3. For each integer n ≥ 3, the graph Σ_{n} is critical and wellconnected.

Proof. The proof is left to the reader.

Corollary 7.4. Let n = 4m + 3, and let C(m, 4m + 3) be the circular graph of [7]. Suppose that Γ is a circular planar graph with n boundary nodes, Assume that M(Γ) is lensless and has z-sequence 1, …, n, 1, …, n. Then Γ is Y − Δ equivalent to C(m, 4m + 3). In particular, Σ_{n} and C(m, 4m + 3) are Y − Δ equivalent.

Proof. The medial graph M(C(m, 4m + 3)) is lensless. The z-sequence is 1, …, n, 1, …, n. By Lemma 7.2, Γ and C(m, 4m + 3) are Y − Δ equivalent.

8. Adjoining edges. Let (Γ, γ) be a circular planar resistor network with n boundary nodes v_{1}, … v_{n}. We will describe three ways to adjoin an edge to Γ, and the effect of each on the matrix Λ(Γ, γ). In this section, Λ(Γ) stands for Λ(Γ, γ), with the conductivity γ implicit from the context.

(1) Let p and q be two adjacent boundary nodes. For convenience of notation, we make a cyclic re-labelling of the boundary nodes, so that p = v_{1} and q = v_{2}. We add an edge pq so that the new graph is still be a circular planar graph with n boundary nodes. We call this process \underline{adjoining a boundary edge}. If a boundary edge pq is adjoined to Γ, with γ(pq) = ξ, the resulting resistor network is denoted T_{ξ}(Γ).

Suppose M = {m_{i,j}} is an n × n matrix, and ξ is a real number. We define a new matrix T_{ξ}(M) as follows.

T_{ξ}(M)_{1,1} = m_{1,1} + ξ
T_{ξ}(M)_{2,2} = m_{2,2} + ξ
T_{ξ}(M)_{1,2} = m_{1,2} − ξ
T_{ξ}(M)_{2,1} = m_{2,1} − ξ
T_{ξ}(M)_{i,j} = m_{i,j} otherwise

Clearly, T_{−ξ} ∘ T_{ξ} = identity. From the definition of the Kirchhoff matrix, we have

K(T_{ξ}(Γ)) = T_{ξ}(K(Γ))

From Theorem 3.2, it follows that

Λ(T_{ξ}(Γ)) = T_{ξ}(Λ(Γ))
Λ(Γ) = T_{−ξ}(Λ(T_{ξ}(Γ))

Suppose given (Γ, γ) and ξ. Then Λ(Γ) uniquely determines Λ(T_{ξ}(Γ)). Also, Λ(T_{ξ}(Γ)) uniquely determines Λ(Γ).

(2) Let p be a boundary node. By a cyclic re-labelling of the boundary nodes, assume that p = v_{1}. We place a new vertex v_{0} on the boundary circle C, between v_{n} and v_{1}, and adjoin a new edge v_{0}v_{1} to Γ. The new graph is a circular planar graph with n+1 boundary nodes. We call this process \underline{adjoining a boundary spike} \underline{without interiorizing}. If a boundary spike v_{0}v_{1} is adjoined to Γ, without interiorizing the vertex v_{1}, and with γ(v_{0}v_{1}) = ξ, the resulting resistor network is denoted P_{ξ}(Γ).

Suppose M = {m_{i,j}} is an n × n matrix, written in block form:

M = [ \begin{matrix}m_{1,1} & a \\ b & C \end{matrix} ]

If ξ a real number, let P_{ξ}(M) be the (n + 1) × (n + 1) matrix, with indices 0 ≤ i ≤ n and 0 ≤ j ≤ n,

P_{ξ}(M) = [ \begin{matrix}ξ & −ξ & 0 \\ −ξ & m_{1,1} + ξ & a \\ 0 & b & C \end{matrix} ]

Then by Theorem 3.2,

Λ(P_{ξ}(Γ) = P_{ξ}(Λ(Γ))

Suppose given (Γ, γ) and ξ. Then Λ(Γ) uniquely determines Λ(P_{ξ}(Γ)). Also, Λ(P_{ξ}(Γ)) uniquely determines Λ(Γ).

(3) Let p be a boundary node. By a cyclic re-labelling of the boundary nodes, assume that p = v_{1}. We adjoin a boundary spike rv_{1} to Γ, then declare v_{1} to be an interior node, and renumber so that r is the first boundary node. The new graph is a circular planar graph with n boundary nodes. We call this process \underline{adjoining a boundary spike}. If a boundary spike rv_{1} is adjoined to Γ, with γ(rv_{1}) = ξ, the resulting resistor network is denoted S_{ξ}(Γ).

Suppose M = {m_{i,j}} is an n × n matrix, written in block form:

M = [ \begin{matrix}m_{1,1} & a \\ b & C \end{matrix} ]

For any real number ξ, the (n + 1) × (n + 1) matrix P_{ξ}(M) has been defined in (2). The indexing is 0 ≤ i ≤ n and 0 ≤ j ≤ n. If the (1, 1) entry δ = m_{1,1} + ξ is not 0, we take the Schur complement of P_{ξ}(M) with respect to this entry, to obtain

S_{ξ}(M) = P_{ξ}/[m_{1,1} + ξ] = [ \begin{matrix}ξ − \frac{ξ^{2}}{δ} & \frac{aξ}{δ} \\ \frac{bξ}{δ} & C − \frac{ba}{δ} \end{matrix} ]

A calculation shows that S_{−ξ} ∘ S_{ξ} = identity. From the definition of the Kirchhoff matrix in §3,

K(S_{ξ}(Γ)) = K(P_{ξ}(Γ))

Thus Λ(S_{ξ}(Γ)) is the Schur complement of P_{ξ}(K(Γ)) with respect to the block corresponding to I ∪ {v_{1}}. From Theorem 3.2 and Lemma 3.4, it follows that

Λ(S_{ξ}(Γ)) = S_{ξ}(Λ(Γ))
Λ(Γ) = S_{−ξ}(Λ(S_{ξ}(Γ))

Suppose given (Γ, γ) and the positive real number ξ. Then Λ(Γ) uniquely determines Λ(S_{ξ}(Γ). Also Λ(S_{ξ}(Γ)) uniquely determines Λ(Γ).

Remark 8.1 We have adjoined the boundary edge at v_{1}v_{2} for convenience of notation. The construction T_{ξ}(Γ) may be made at any pair of boundary nodes p and q which are adjacent in the circular order. The construction T_{ξ}(M) may be made at any pair of indices of which are adjacent in the circular order. Similarly the constructions P_{ξ}(Γ) or S_{ξ}(Γ) may be made at any boundary node, and P_{ξ}(M) or S_{ξ}(M) may be made at any index. In each case, the location of the nodes (or indices) where the construction is to be made will be clear from the context.

9. Recovering Conductivities.

Lemma 9.1. Suppose Γ is a circular planar graph with n boundary nodes for which the medial graph M(Γ) is lensless. Assume that the z-sequence for the medial graph M(Γ) is not the sequence 1, 2, …, n, 1, 2, …, n. Then either

(1) There is a boundary node where a boundary spike may be adjoined to Γ, so that after the adjunction, the resulting graph Γ′ is lensless.

or (2) There is a pair of consecutive boundary nodes where a boundary edge may be adjoined, so that after the adjunction, the resulting graph Γ′ is lensless.

Proof. Let t be a number in the sequence such that two repetitions of t are closest in the circular order around C. By a cyclic relabelling, we may assume that t = 1, so that the z-sequence for M(Γ) is

z = 1, 2 …, m, 1, z_{m+2}, …, z_{2n}

with m < n. Let h be the first index for which z_{h} is not in the set {1, 2, …, m}. Then z_{h−1} and z_{h} are a pair of numbers which do not interlace in z (see §7). The corresponding geodesics in M(Γ) do not cross. We now make the single alteration in M(Γ) so that these two geodesics do cross, and the new z-sequence is

1, 2 …, m, 1, z_{m+2}, …, z_{h}, z_{h−1}, …, z_{2n}

The new medial graph is lensless. This change in the medial graph corresponds to adjoining either a boundary edge or a boundary spike to Γ.

Lemma 9.2. Suppose Γ is a circular planar graph with n boundary nodes for which the medial graph M(Γ) is lensless. There is a sequence of circular planar graphs Γ = Γ_{0}, Γ_{1}, Γ_{2}, …, Γ_{k}, where each Γ_{i+1} is obtained from Γ_{i} by adjoining a boundary edge or a boundary spike, and where Γ_{k} is Y − Δ equivalent to the standard graph Σ_{n}.

Proof. We adjoin boundary edges or boundary spikes until the z-sequence for the medial graph M(Γ_{k}) is 1, 2, …, n, 1, 2, …, n. By Corollary 7.4, Γ_{k} is Y − Δ equivalent to Σ_{n}.

Proof. of Theorem 2. By taking connected components, we need only consider the case when Γ is connected. First let (Γ, γ) be a resistor network whose underlying graph is the graph C(m, 4m + 3) of [7]. In Theorem 5.2 of [7] we showed that for this graph, the conductivity γ may be recovered from Λ_{γ}. By Corollary 5.4, any resistor network whose underlying graph is Y − Δ equivalent to C(m, 4m + 3) is also recoverable. In particular, any conductivity on Σ_{4m+3} is recoverable.

Next suppose (Γ, γ) is any connected critical circular planar resistor network with n boundary nodes. If n is not of the form 4m + 3, first adjoin 1, 2, or 3 boundary spikes without interiorizing as in §8, to obtain a resistor network which does have 4m + 3 boundary nodes. Combining this with Lemma 9.2, we obtain a sequence of circular planar resistor networks Γ = Γ_{0}, Γ_{1}, Γ_{2}, …, Γ_{k}, where Γ_{k} is a graph with 4m + 3 boundary nodes, which is Y − Δ equivalent to Σ_{4m+3}. Each Γ_{i+1} is obtained from Γ_{i} by adjoining a boundary edge, or adjoining a boundary spike (with or without interiorizing). The resistor network Γ_{k} is recoverable, and hence each of the resistor networks Γ_{i} for k ≥ i ≥ 0 is also recoverable. In particular, the resistor network Γ = Γ_{0} is recoverable.

10. Totally Non-negative Matrices. We continue the notations of §1 and §2. Specifically, let A = {a_{i,j}} be a matrix. If P = (p_{1}, …, p_{k}) is an ordered subset of the rows, and Q = (q_{1}, …, q_{m}) is an ordered subset of the columns, then A(P; Q) is the k × m sub-matrix of A with

A(P; Q)_{i,j} = a_{p_{i},q_{j}}

A[P; Q] is the matrix obtained by \underline{deleting} the rows for which the index is in P, and \underline{deleting} the columns for which the index is in Q. The empty set is ϕ. Thus A[ϕ; 1] refers to the matrix A with the first column deleted.

Following [9], a rectangular matrix A is called \underline{totally non-negative} (abbreviation: TNN) if every square minor has determinant ≥ 0. The following facts about TNN matrices will be needed in §11 and §12.

Lemma 10.1. Suppose A = {a_{i,j}} is an m × m matrix which is TNN and nonsingular. Then any principal minor is non-singular.

Proof. Induction on m. For m = 1, there is nothing to prove. Let m > 1. The entry a_{1,1} must be > 0, else either the first row or the first column of A would be entirely 0, contradicting the assumption that A is non-singular. By the determinantal formula for Schur complements, the Schur complement A/[a_{1,1}] is non-singular and TNN. Similarly a_{m,m} > 0, A/[a_{m,m}] is non-singular and TNN. By the inductive assumption, every principal minor of A/[a_{1,1}] is non-singular. Let A(P; P) be a principal minor of A, where P = (p_{1}, …, p_{k}) is an ordered subset of the index set (1, 2, …, m). If 1 ∈ P, A(P; P)/[a_{1,1}] is a principal minor of A/[a_{1,1}] and hence is non-singular. Thus det A(P; P) ≠ 0, so A(P; P) is non-singular. Similarly if m ∈ P, A(P; P) is nonsingular. Otherwise, P contains neither 1 nor m, and k ≤ m−2. Let Q = (1, p_{1}, …, p_{m}). The k + 1 × k + 1 matrix A(Q; Q) is TNN and non-singular. A(P; P) is a principal minor of A(Q; Q), so is non-singular by induction.

Lemma 10.2. Suppose that A = {a_{i,j}} is an m × m matrix, and suppose that a_{s,1} < 0 for some index s with 1 ≤ s ≤ m. Assume also that

(i) A[ϕ; 1] is TNN.
(ii) A(s + 1, …, m; 1, …, m) is TNN.
(iii) A(1, …, s − 1; 2, …, m, 1) is TNN.

Then (1) (−1)^{s} det A ≥ 0.

(2) If it is further assumed that det A[s; 1] > 0, then (−1)^{s} det A > 0.

Proof. Induction on m. The assertion of (1) for m = 2 is immediate. For m > 2, first consider the case s = 1, with a_{1,1} < 0. If all the cofactors of the entries in the first column are 0, then det A = 0. If the only non-zero cofactor of an entry in the first column is A[1; 1], then

det A = a_{1,1} · det A[1; 1] < 0

Otherwise, suppose det A[t; 1] > 0 with t > 1. A[1, t; 1, 2] is a principal minor of A[t; 1] which is assumed to be TNN, so det A[1, t; 1, 2] > 0 by Lemma 10.1. Dodgson’s identity (Lemma 2.1) gives

(1) det A · det A[1, t; 1, 2] = det A[1; 1] · det A[t; 2] − det A[1; 2] · det A[t; 1]

det A[1; 2] and det A[t; 1] are non-negative by assumption (ii). By the inductive assumption det A[t; 2] ≤ 0. Hence det A ≤ 0.

The case s = m is similar, by considering the matrix A(1, …, m; 2, …, m, 1). The only negative entry is in the last column. Assumption (iii) is used in place of (ii).

This leaves the case when 1 < s < m. If the only non-zero cofactor of an entry in the first column is A[s; 1], then

det A = (−1)^{s+1} · a_{s,1} · det A[s; 1]

If another cofactor is non-zero, WLOG, assume det A[t; 1] > 0 with 1 < s < t ≤ m. Then A[1, t; 1, 2] is a principal minor of A[t; 1], so det A[1, t; 1, 2] > 0 by Lemma 10.1. Dodgson’s identity (Lemma 2.1) gives

det A · det A[1, t; 1, 2] = det A[1; 1] · det A[t; 2] − det A[1; 2] · det A[t; 1]

The factors det A[1; 1] and det A[t; 1] are non-negative. By the inductive assumption, (−1)^{s} det A[t; 2] ≥ 0 and (−1)^{s−1} det A[1; 2] ≥ 0. In every case, (−1)^{s} det A ≥ 0.

The proof of (2) is also by induction on m. For m = 2, the assertion is immediate. Let m > 2. If the only non-zero cofactor of an entry in the first column is A[s; 1], then

(−1)^{s} det A = −a_{s,1} · det A[s; 1] > 0

If more than one cofactor is non-zero, WLOG, assume det A[s; 1] > 0 and det A[t; 1] > 0 with 1 < s < t ≤ m. Then det A[1, s; 1, 2] > 0 and det A[1, t; 1, 2] > 0 by Lemma 10.1. By the inductive assumption, (−1)^{s−1} det A[1; 2] > 0, and equation (1) shows that (−1)^{s} det A > 0.

Lemma 10.3. Suppose A is a k + 1 × k matrix which is TNN. Suppose that for some pair of integers s and t with 1 ≤ s < t ≤ k + 1,

(i) det A[s; ϕ] = 0
(ii) det A[t; ϕ] ≠ 0

Then the rank of A(s + 1, …, k + 1; 1, …, k) is ≤ k − s.

Proof. For each i = 1, …, k + 1, let R_{i} be the i-th row of A, considered as a vector in R^{k}. Assumption (ii) implies that {R_{1}, …, R̂_{t}, … R_{k+1}} form a basis for R^{k}. Hence,

R_{t} = ∑_{i≠t} x_{i}R_{i}

In this sum, x_{s} = 0, else {R_{1}, …, R̂_{s}, … R_{k+1}} would also be a basis for R^{k}, contradicting assumption (i). Then

det A[1; ϕ] = (−1)^{t} · x_{1} · det A[t; ϕ] ≥ 0

Hence (−1)^{t}x_{1} ≥ 0, because det A[t; ϕ] > 0. A[s, t; s] is a principal minor of A[t; ϕ], so det A[s, t; s] > 0 by Lemma 10.1. Then

det A[1, s; s] = (−1)^{t−1} · x_{1} · det A[s, t; s] ≥ 0

Hence (−1)^{t−1}x_{1} ≥ 0, Thus x_{1} = 0. Similarly, x_{2} = 0, …, x_{s−1} = 0. Thus

R_{t} = ∑ ; \begin{matrix}i > s \\ i ≠ t \end{matrix} x_{i}R_{i}

This implies rank A(s + 1, …, k + 1; 1, …, k) ≤ k − s.

\underline{Notation}. Let P = (p_{1}, p_{2}, …, p_{k}) be a sequence of distinct indices. If p ∈ P, then P − p denotes the sequence obtained by deleting the index p from P. If p ∉ P, then p + P denotes the sequence (p, p_{1}, ⋯, p_{k}). Also μ(P; Q) stands for det M(P; Q), and μ′(P; Q) stands for det M′(P; Q).

Recall the definition of the set Ω_{n} from §1. With our conventions, this means that if M ∈ Ω_{n} and (P; Q) is a circular pair of indices, then the matrix −M(P; Q) is TNN.

Lemma 10.4. Let M ∈ Ω_{n} and suppose that m_{h,h} is a non-zero diagonal entry. Then the Schur complement M′ = M/[m_{h,h}] is in Ω_{n−1}.

Proof. If (1, …, n) is the indexing set for M, it is convenient to regard the deleted set (1, …, ĥ, …, n) as the indexing set for M′. Let (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}) be a circular pair of indices for M′. Then h ∉ P ∪ Q. By interchanging P and Q if necessary, and by a cyclic re-labelling of the indices, we may assume that 1 ≤ h < q_{k} in the circular order. Let B = (b_{1}, …, b_{k+1}), be the set P ∪ h with the circular ordering, where b_{s} = h with 1 ≤ s ≤ k + 1. Thus 1 ≤ b_{1} < … b_{k+1} < q_{k} < … q_{1} ≤ n. The matrix

A = −M(B; b_{s} + Q)

satisfies the conditions of Lemma 10.2. Hence (−1)^{s} det A ≥ 0, so

(−1)^{s+1+k}μ(B; b_{s} + Q) ≥ 0

Taking the Schur complement with respect to the entry m_{h,h}, which is in the (s, 1) position of M(B; b_{s} + Q), we find that (−1)^{k}μ′(P; Q) ≥ 0.

Remark 10.5. If (−1)^{k}μ(P; Q) > 0, then part (2) of Lemma 10.2 shows that (−1)^{s+1+k}μ(B; b_{s} + Q) > 0. Therefore (−1)^{k}μ′(P; Q) > 0.

Lemma 10.6. Suppose M ∈ Ω_{n}. Let B = (b_{1}, …, b_{k+1}), and and Q = (q_{1}, … q_{k}) be two sequences of indices, with with 1 ≤ b_{1} < … < b_{k} < b_{k+1} < q_{k} < … < q_{1} ≤ n. Suppose for some pair of indices (s, t) with 1 ≤ s < t ≤ k + 1, that μ(B − b_{s}; Q) = 0 and μ(B − b_{t}; Q) ≠ 0. Let B_{0} = (b_{s+1}, …, b_{k+1}), and Let Q_{0} = (q_{s+1}, …, q_{k}). Then μ(B_{0} − b_{t}; Q_{0}) ≠ 0, and

μ(B; b_{s} + Q) = (−1)^{s} \frac{μ(B − b_{t}; Q) · μ(B_{0}; b_{s} + Q_{0})}{μ(B_{0} − b_{t}; Q_{0})}

Proof. For 0 ≤ r ≤ s, let

B_{r} = (b_{1}, …, b_{r}, b_{s+1}, …, b_{k+1})
Q_{r} = (q_{1}, …, q_{r}, q_{s+1}, …, q_{k}).

Then μ(B_{r} − b_{t}; Q_{r}) ≠ 0 because M(B_{r} − b_{t}; Q_{r}) is a principal minor of M(B − b_{t}; Q). Dodgson’s identity (Lemma 2.1) gives

μ(B_{r+1}; b_{s} + Q_{r+1}) · μ(B − b_{t}; Q_{r}) =

μ(B_{r}; Q_{r+1}) · μ(B − b_{t}; b_{s} + Q_{r}) − μ(B_{r+1} − b_{t}; Q_{r}) · μ(B_{r}; b_{s} + Q_{r})

μ(B_{r}; Q_{r+1}) = 0 by Lemma 10.3, so the first term on the RHS is 0, and

\frac{μ(B_{r+1}; b_{s} + Q_{r+1})}{μ(B_{r+1} − b_{t}; Q_{r+1})} = −\frac{μ(B_{r}; b_{s} + Q_{r})}{μ(B_{r} − b_{t}; Q_{r})}

Repeated use of this identity gives the result.

Lemma 10.7. Suppose M ∈ Ω_{n}, p and q are adjacent indices, and ξ > 0. Let T_{ξ}(M) be the matrix constructed in §8 (see also Remark 8.1). Then T_{ξ}(M) ∈ Ω_{n}.

Proof. The circular determinants in M′ = T_{ξ}(M) are equal to the circular determinants in M except for the ones which correspond to circular pairs (P; Q) = (p_{1}, …, p_{k}; q_{1}, … q_{k}) where p = p_{k} and q = q_{k}, or p = p_{1} and q = q_{1}. Each of these determinants has the form

μ′(P; Q) = det [ \begin{matrix}C & a \\ b & d − ξ \end{matrix} ]

= det [ \begin{matrix}C & a \\ b & d \end{matrix} ] − ξ det(C)
= μ′(P; Q) − ξμ(P − p; Q − q)

Hence

(−1)^{k}μ′(P; Q) = (−1)^{k}μ(P; Q) − ξ(−1)^{k−1}μ(P − p; Q − q) ≥ 0 (2)

Remark 10.8. If either (−1)^{k}μ(P; Q) > 0 or (−1)^{k−1}μ(P − p; Q − q) > 0, then (−1)^{k}μ′(P; Q) > 0; otherwise μ′(P; Q) = 0. Thus the signs of the circular determinants in M′ are determined by the signs of the circular determinants in M.

Lemma 10.9. Suppose M ∈ Ω_{n}, and ξ > 0. Let P_{ξ}(M) be the matrix constructed in §8. Then P_{ξ}(M) ∈ Ω_{n+1}.

Proof. Let M′ = P_{ξ}(M), and let (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}) be a circular pair of indices from the set (0, 1, …, n).

(1) If 0 ∉ P ∪ Q, then μ′(P; Q) = μ(P; Q).
(2) If 0 ∈ P and 1 ∉ Q, then μ′(P; Q) = 0.

(3) If 0 ∈ P and 1 ∈ Q, then 0 = p_{k}, 1 = q_{k}, and μ′(P; Q) = −ξμ(P − p_{k}; Q − q_{k}).

(4) The situation is similar if 0 ∈ Q.

Lemma 10.10. Suppose M ∈ Ω_{n}, and ξ > 0. Let S_{ξ}(M) be the matrix constructed in §8. Then S_{ξ}(M) ∈ Ω_{n}.

Proof. Let (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}) be a circular pair of indices. Let p be the index where the adjunction is made (see Remark 8.1). By interchanging P and Q if necessary, and by a circular re-labelling of the indices, we may assume that 1 ≤ p < q_{k} in the circular order. Let M′ = S_{ξ}(M).

(1) If p ∈ P, then the formula for S_{ξ}(M), shows that

μ′(P; Q) = (\frac{ξ}{ξ + m_{p,p}} ) μ(P; Q)

(2) Suppose that p ∉ P and (−1)^{k}μ(P; Q) > 0. Then (−1)^{k}S_{ξ}(M)(P; Q) > 0, by Remark 10.5.

(3) Suppose that p ∉ P, μ(P; Q) = 0, and μ(P − p_{j} + p; Q) = 0, for all 1 ≤ j ≤ k. Then the proof of Lemma 10.2 shows that μ′(P; Q) = 0.

(4) Finally, suppose that p ∉ P, that μ(P; Q) = 0, and that μ(P − p_{j} + p; Q) ≠ 0 for some j with 1 ≤ j ≤ k. Let B = (b_{1}, …, b_{k+1}) be the set P ∪ p with the circular ordering. That is, p = b_{s} for some s, and p_{j} = b_{t} for some t, and WLOG, may assume s < t. P_{ξ}(M)(B, b_{s} + Q) and M(B, b_{s} + Q) differ only at the (s, 1) position, and the cofactor of that entry is μ(P; Q), assumed to be 0. Therefore,

det P_{ξ}(M)(B; b_{s} + Q) = μ(B; b_{s} + Q)

Recall that S_{ξ}(M) is the Schur complement of P_{ξ}(M) with respect to the entry m_{p,p} +ξ, which is in the (s, 1) position of P_{ξ}(M)(B; b_{s} + Q). Then

(−1)^{s+1}(m_{p,p} + ξ) · μ′(P : Q) = det P_{ξ}(M)(B; b_{s} + Q)
= μ(B; b_{s} + Q)
= (−1)^{s} \frac{μ(B − b_{t}; Q) · μ(B_{0}; b_{s} + Q_{0})}{μ(B_{0} − b_{t}; Q_{0})}

The last equality uses Lemma 10.6. Thus (−1)^{k}M′(P; Q) ≥ 0 and if μ(B_{0}; b_{s} +Q_{0}) ≠ 0, then (−1)^{k}M′(P; Q) > 0.

Remark 10.11. (1) and (2) show that if (−1)^{k}μ(P; Q) > 0, then (−1)^{k}μ′(P; Q) > 0. Together with (3) and (4), this shows that the signs of the circular determinants in M′ are determined by the signs of the circular determinants in M.

Lemma 10.12. Let Γ be a circular planar graph with n boundary nodes.

(1) Suppose a boundary edge pq is adjoined to Γ, as in §8. Let Γ′ = T_{ξ}(Γ) and π′ = π(Γ′). If M ∈ Ω(π), then T_{ξ}(M) ∈ Ω(π′).

(2) Suppose a boundary spike rp is adjoined to Γ at node p, without interiorizing as in §8. Let Γ′ = P_{ξ}(Γ) and π′ = π(Γ′). If M ∈ Ω(π), then P_{ξ}(M) ∈ Ω(π′).

(3) Suppose p is a boundary node of Γ, and a boundary spike rp is adjoined with p then declared interior, as in §8. Let Γ′ = S_{ξ}(Γ) and π′ = π(Γ′). If M ∈ Ω(π), then S_{ξ}(M) ∈ Ω(π′).

Proof. The three processes are similar, so for definiteness, suppose that the operation is S_{ξ}. Let γ be an arbitrary conductivity on Γ. By §8, statement (1) is true if M = Λ(Γ, γ). Next, suppose M is any matrix in Ω(π), and let M′ = S_{ξ}(M). By Remark 10.11, the signs of the circular determinants in M′ are determined by the signs of the circular determinants in M. Hence they have the same signs as the circular determinants in S_{ξ}(Λ(Γ, γ)). Since S_{ξ}(Λ(Γ, γ)) ∈ Ω(π′), we have M′ ∈ Ω(π′) also.

11. Removing edges. Suppose that Γ is a circular planar graph with n boundary nodes. Recall from §1, that there are two ways to remove an edge from Γ called deletion and contraction. In either case the new graph will be a circular planar graph with n boundary nodes.

Lemma 11.1. Suppose Γ is a critical circular planar graph and pq is a boundary edge. Let Γ_{1} be the graph obtained after deletion of pq. Then Γ_{1} is also critical.

Proof. Let e ≠ pq be an edge in Γ. Since Γ is critical, removal of e will break some connection in Γ. If this connection also exists in Γ_{1}, then removal of e from Γ_{1} breaks this connection in Γ_{1}. Suppose that removal of e from Γ breaks a connection (P; Q) that is not present in Γ_{1}. This connection must use the edge pq, so (P; Q) has the form (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}), where p_{k} = p and q_{k} = q. Thus removal of e breaks the connection of (P′; Q′) = (p_{1}, …, p_{k−1}; q_{1}, …, q_{k−1}) in Γ_{1}.

Lemma 11.2. Suppose Γ is a critical circular planar graph with a boundary spike rp where r is a boundary node of Γ. Let Γ_{1} be the graph obtained after contracting rp to p. Then Γ_{1} is also critical.

Proof. Let e be an edge in Γ with e ≠ pr. Let Γ′ be the graph with e removed, either by deletion or contraction. Similarly, let Γ′_{1} be the graph Γ_{1} with e removed. Let γ be a conductivity on Γ, and by restriction γ gives a conductivity on Γ_{1}, Γ′ and Γ′_{1}. Let (P; Q) be a pair of sequences of boundary nodes. Then λ(P; Q), λ′(P; Q), λ_{1}(P; Q) and λ′_{1}(P; Q) will denote the subdeterminants of Λ(Γ), Λ(Γ′), Λ(Γ_{1}) and Λ(Γ′_{1}) respectively.

Suppose that removal of e breaks a connection in Γ that persists in Γ_{1}. Then removal of e from Γ_{1} breaks the same connection in Γ_{1}.

Suppose removal of e from Γ breaks a connection (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}) in Γ which does not persist in Γ_{1}. Then r ∉ P ∪ Q. WLOG, assume that q_{1} < p < q_{k} in the circular order around Γ_{1}. Let B = (b_{1}, …, b_{k+1}) be the set P ∪ p with the circular ordering around the boundary of Γ_{1}, and suppose p = b_{s}. The assumptions that λ(P; Q) ≠ 0 and λ_{1}(P; Q) = 0 imply that each connection from Q to P through Γ must use p = b_{s}. Such a connection either connects q_{s−1} to b_{s−1} through b_{s} or connects q_{s} to b_{s+1} through b_{s}. WLOG, assume the latter. Let B_{0} = (b_{s+1}, …, b_{k+1}), and Q_{0} = (q_{s+1}, …, q_{k}). Hence λ_{1}(B − b_{s+1}; Q) ≠ 0 and λ_{1}(B_{0}; b_{s} + Q_{0}) ≠ 0. Both (B − b_{s+1}; Q) and (B_{0}; b_{s} + Q_{0}) are circular pairs. Suppose removal of e from Γ_{1} does not break either connection. Then λ′_{1}(B − b_{s+1}; Q) ≠ 0 and λ′_{1}(B_{0}; b_{s} + Q_{0}) ≠ 0. We have assumed λ_{1}(P; Q) = 0; that is λ_{1}(B − b_{s}; Q) = 0. Hence λ′_{1}(B − b_{s}; Q) = 0. By Lemma 10.6, with t = s + 1,

λ′_{1}(p + P; p + Q) = (−1)^{s−1}λ′_{1}(B; b_{s} + Q)
= −\frac{λ′_{1}(B − b_{s+1}; Q)λ′_{1}(B_{0}; b_{s} + Q_{0})}{λ′_{1}(B_{0} − b_{s+1}; Q_{0})}
≠ 0

Let ξ = γ(pr). Then Λ′ is the Schur complement of P_{ξ}(Λ′_{1}) with respect to the entry Λ′_{1}(p, p) + ξ. Part (4) of the proof of Lemma 10.10 shows that λ′(P; Q) ≠ 0. This would contradict the assumption that removal of e from Γ breaks the connection (P; Q).

Lemma 11.3. Suppose Γ is a non-trivial circular planar graph for which M(Γ) is lensless. Then Γ has either a boundary edge or a boundary spike.

Proof. Refer to §7 for the notation. Let t be a number in the z-sequence for M(Γ) such that there are no repetitions of any other number between two occurrences of t. WLOG, assume that t = 1, so that a portion of the z-sequence is

1, 2 …, m, 1, z_{m+2}, …

Let h be the portion of the outer circle C for Γ which lies between x_{1} and y_{1}. Then h contains the points x_{2}, … x_{m}. Consider h, g_{1} and the family {g_{2}, … g_{m}}. The proof of Lemma 6.2 shows that there is a triangle T formed by h and two of the geodesics from the set {g_{1}, … g_{m}}. The triangle T in M(Γ) corresponds in Γ either to a boundary spike (if there is a vertex of Γ inside T), or to a boundary to boundary edge (if there is no vertex of Γ inside T).

Lemmas 11.3, 11.1 and 11.2, together with Corollaries 4.3 and 4.4 show that there is an algorithm for calculating the conductivity of any critical circular planar graph.

12. Surjectivity.

Theorem 12.1. Suppose Γ is a critical circular planar graph with n boundary nodes and π = π(Γ). Let M be any matrix in Ω(π). Then there is a conductivity γ on Γ with Λ(Γ, γ) = M.

Proof. of Theorem 12.1. We first consider the case where n = 4m + 3 and the z-sequence for the medial graph M(Γ) is 1, …, n, 1, …, n. Corollary 7.4 shows that Γ is Y − Δ equivalent to the graph C(m, n) of [7]. By Theorem 6.2 of [7] there is a conductivity γ′ on C(m, n) with Λ(C(m, n), γ′) = M. By Lemma 5.3, there is a conductivity γ on Γ with Λ(Γ, γ) = M.

Next suppose (Γ, γ) is any connected critical circular planar resistor network with n boundary nodes. If n is not of the form 4m + 3, first adjoin 1, 2, or 3 boundary spikes without interiorizing as in §8, to obtain a resistor network which does have 4m + 3 boundary nodes. Combining this with Lemma 9.2, we obtain a sequence of circular planar resistor networks Γ = Γ_{0}, Γ_{1}, Γ_{2}, …, Γ_{k}, where Γ_{k} is a graph with 4m + 3 boundary nodes, and which is Y − Δ equivalent to Σ_{4m+3}. Each Γ_{i+1} is obtained from Γ_{i} by one of the operations T , P or S. For each i = 0, 1, …, k, let π_{i} = π(Γ_{i}). Given a matrix M in Ω(π), there is an analogous sequence of matrices M = M_{0}, M_{1}, …, M_{k}, where each matrix M_{i+1} is obtained from M_{i} by one of the operations M_{i+1} = T_{ξ}(M_{i}), M_{i+1} = P_{ξ}(M_{i}) or M_{i+1} = S_{ξ}(M_{i}).

Let σ_{n} denote the set of connections in a well-connected circular planar graph with n boundary nodes. By Lemma 5.1 and Proposition 7.3, π(Σ_{n}) = σ_{n}. By Lemma 10.12, M_{k} ∈ Ω(σ_{n}). Using the first part of the proof, there is a conductivity γ_{k} on Γ_{k} so that Λ(Γ_{k}, γ_{k}) = M_{k}. The graph Γ_{k} is obtained from Γ_{k−1} by one of the operations T , P or S. The processes are similar, so for definiteness, suppose that the operation is S_{ξ} and M_{k} = S_{ξ}(M_{k−1}).

In going from Γ_{k} to Γ_{k−1}, removal of the spike breaks a connection in Γ_{k}. By Lemma 4.4, the value of this spike can be calculated as the ratio of two non-zero subdeterminants of Λ(Γ_{k}) = M_{k}. Moreover, the computed value is the same as the value ξ that was used to construct M_{k} from M_{k−1}. By §11, removal of the spike with conductivity ξ from Γ_{k} results in a critical graph Γ_{k−1}, with Λ(Γ_{k−1}) = M_{k−1}. Continuing the argument on Γ_{k−1}, …, Γ_{0} = Γ, we find that Λ(Γ) = M.

Proof. of Theorem 4. As in the proof of Theorem 12.1, there is a sequence of the operations T , P, and S which, when applied to the graph Γ, give a graph Γ_{k} which is Y − Δ equivalent to the graph C(m, 4m + 3) of [7]. Let U be the composite of these operations, and let U be the composite of the corresponding operations T, P and S applied to the matrix Λ(Γ, γ). With an ordering of the N edges in Γ, the conductivity γ is represented by a point in (R^{+})^{N}. Similarly, with an ordering of the N_{k} edges in Γ_{k}, the conductivity γ_{k} is represented by a point in (R^{+})^{N_{k}}. Let π = π(Γ) and π_{k} = π(Γ_{k}). With these conventions, there is a commutative diagram:

[figure: Ω(π); Ω(π_{k}); (R^{+})^{N}; (R^{+})^{N_{k}}; Λ; Λ_{k}; U; U; Fig 4]

By Theorem 12.1, the map Λ is surjective. By Theorems 4.2 and 5.2 of [7], the map Λ_{k} is a diffeomorphism. For the differentials, we have

dΛ_{k} ∘ dU = dU ∘ dΛ

Since dλ_{k} and dU are 1-1, dΛ is 1-1. By Theorem 2, Λ is 1-1. U^{−1} is the inverse of U which is well-defined and continuous on its image in (R^{+})^{N_{k}}. Then

Λ^{−1} = U^{−1} ∘ Λ_{k}^{−1} ∘ U

Thus Λ^{−1} is continuous. It follows that Λ is a diffeomorphism of (R^{+})^{N} onto Ω(π).

Lemma 12.2. Suppose M ∈ Ω_{n}, with at least one circular determinant equal to 0. Let ϵ > 0 be given. Then there is a matrix M′ ∈ Ω_{n}, with ∥M′ − M∥_{∞} < ϵ, and

(1) μ′(P; Q) ≠ 0 whenever μ(P; Q) ≠ 0

(2) For at least one circular pair (P; Q), μ(P; Q) = 0 and μ′(P; Q) ≠ 0.

Proof. As in §10, μ(P; Q) stands for det M(P; Q) and μ′(P; Q) stands for det M′(P; Q). Let (P; Q) = (p_{1}, …, p_{k}; q_{1}, …, q_{k}) be a circular pair of indices for which the minor M(P; Q) has determinant 0, has minimum order k, and for which q_{k} −p_{k} is a minimum.

(1) If q_{k} − p_{k} = 1, let M′ = T_{ξ}(M), where the chosen indices are p_{k} and q_{k}. By Remark 10.8, μ′(P; Q) ≠ 0. Also by Remark 10.8, μ′(R; S) ≠ 0 whenever (R; S) is a circular pair for which μ(R; S) ≠ 0. If ξ is sufficiently small, then ∥M′ − M∥_{∞} < ϵ.

(2) If q_{k} − p_{k} > 1, let p = p_{k} + 1 and M′ = S_{ξ}(M) where the chosen index is p. By Remark 10.11, μ′(R; S) ≠ 0 whenever (R; S) is a circular pair for which μ(R; S) ≠ 0. Dodgson’s identity (Lemma 2.1) gives

μ(P + p; Q + p) · μ(P − p_{k}; Q − q_{k}) = μ(P − p_{k} + p; Q − q_{k} + p) · μ(P; Q) − μ(P − p_{k} + p; Q) · μ(P; Q − q_{k} + p)

Using the assumption μ(P; Q) = 0, we have

μ(P + p; Q + p) = −\frac{μ(P − p_{k} + p; Q) · μ(P; Q − q_{k} + p)}{μ(P − p_{k}; Q − q_{k})} (3)

Each of the factors on the RHS of (3) is non-zero because of the assumption of the minimality of (P; Q). Therefore μ′(P; Q) ≠ 0. If ξ is taken sufficiently large, then ∥M′ − M∥_{∞} < ϵ.

Proof. of Theorem 3. Recall from §7 the graph Σ_{n} = (V, V_{B}, E), with n boundary nodes, and let σ = π(Σ_{n}). Since Σ_{n} is well-connected, Ω(σ) is the subset of Ω_{n}, consisting of those M which satisfy (−1)^{k} det M(P; Q) > 0 for each k × k circular subdeterminant of M.

Lemma 12.2 implies that Ω_{n} is the closure of Ω(σ) in the space of n × n matrices. Thus for any M ∈ Ω_{n}, there is a sequence of matrices M_{i} ∈ Ω(σ) which converge to M. Theorem 4 shows that for each integer i, there is a conductivity γ_{i} on Σ_{n} with M_{i} = Λ(Σ_{n}, γ_{i}). By taking a subsequence if necessary, we may assume for each edge e ∈ E that lim_{i→∞} γ_{i}(e) is either 0, a finite non-zero value or ∞.

Let E_{0} be the subset of E for which lim_{i→∞} γ_{i}(e) = 0.

Let E_{1} be the subset of E for which lim_{i→∞} γ_{i}(e) = γ(e) is a finite non-zero value.

Let E_{∞} be the subset of E for which lim_{i→∞} γ_{i}(e) = ∞.

Let Γ = (W, V_{B}, E_{1}) be the graph obtained from Σ_{n} = (V, V_{B}, E) by deleting the edges of E_{0} and contracting each edge of E_{∞} to a point. The vertex set W for Γ is the set of equivalence classes of vertices in V, where p ∼ q if pq ∈ E_{∞}. Note that distinct boundary nodes of V_{B} cannot belong to the same equivalence class, because the M_{i} are bounded. Thus we may consider V_{B} as a subset of W. Each edge e ∈ E_{1} joins a pair of points of W, so the edgeset of Γ is E_{1}. The restrictions of γ_{i} and γ to E_{1} give conductivities on Γ. We shall show that M = Λ(Γ, γ).

Suppose f is a function defined on the set of boundary nodes V_{B} of Γ. Let

Q(f) = inf ∑_{e∈E_{1}} γ(e)(Δw(e))^{2}

where Δw(pq) = w(p) − w(q), and the infimum is taken over all functions w defined on the nodes of Γ which agree with f on V_{B}. This infimum is attained when w = u is the potential function on the resistor network (Γ, γ), with boundary values f. Similarly, for each integer i, let

Q_{i}(f) = inf ∑_{e∈E_{1}} γ_{i}(e)(Δw(e))^{2}

This infimum is attained when w = u_{i} is the potential function on (Γ, γ_{i}) with boundary values f. Then lim_{i→∞} u_{i} = u, because the γ_{i} and γ are conductivities (non-zero, and finite) on Γ, with lim_{i→∞} γ_{i} = γ. Therefore Q(f) = lim_{i→∞} Q_{i}(f)

For each integer i, let

S_{i}(f) = inf ∑_{e∈E} γ_{i}(e)(Δw(e))^{2}

where the infimum is taken over all functions w defined on the nodes of Σ_{n} which agree with f on V_{B}. This infimum is attained when w = w_{i} is the potential function on the resistor network (Σ_{n}, γ_{i}), with boundary values f. The maximum principle implies that | w_{i}(p) | ≤ max | f(p) |. By taking a subsequence if necessary, we may assume that for each node p, w_{i}(p) converges to a finite value w(p). The assumption that the M_{i} converge to M guarantees that for each function f, the S_{i}(f) are bounded. Thus for each edge e = pq ∈ E_{∞}, we have w(p) = w(q). Let

R_{i}(f) = ∑_{e∈E_{1}} γ_{i}(e)(Δw_{i}(e))^{2}

and

R(f) = lim_{i→∞} R_{i}(f) = ∑_{e∈E_{1}} γ(e)(Δw(e))^{2}

Let F be the set of functions v = {v(p)} defined for all nodes of Σ_{n}, which which agree with f on V_{B}, and for which v(p) = v(q) whenever pq ∈ E_{∞}. Let

P_{i}(f) = inf_{v∈F} ∑_{e∈E} γ_{i}(e)(Δv(e))^{2}

We have

P_{i}(f) ≥ S_{i}(f) ≥ R_{i}(f)

and

Q_{i}(f) + ∑_{e∈E_{0}} γ_{i}(e)(Δu_{i}(e))^{2} ≥ P_{i}(f) ≥ Q_{i}(f)

The maximum principle implies that the | u_{i}(p) | are bounded by max | f(p) |. For each edge e ∈ E_{0}, we have lim_{i→∞} γ_{i}(e) = 0 , so

Q(f) = lim_{i→∞} Q_{i}(f) = lim_{i→∞} P_{i}(f) ≥ lim_{i→∞} R_{i}(f) = R(f)

But R(f) ≥ Q(f), so R(f) = Q(f). Thus

lim_{i→∞} S_{i}(f) = Q(f) = lim_{i→∞} < f, M_{i}(f) > = < f, M(f) >

13. Equivalence.

Lemma 13.1. Suppose that Γ is a circular planar graph. Then Γ is critical if and only if the medial graph M(Γ) is lensless.

Proof. Lemma 6.4, shows that if Γ is critical, then M(Γ) is lensless. Conversely, suppose M(Γ) is lensless. Let z = z_{1}z_{2} ⋯ z_{2n} be the z-sequence for M(Γ) as in §8. If z = 1, …, n, 1, …, n, then Γ is Y −Δ equivalent to the graph Σ_{n} of §8, which is critical and well-connected. Suppose that z is not the sequence 1, …, n, 1, …, n. By Lemma 9.2, there is a sequence of graphs Γ_{0}, Γ_{1}, …, Γ_{k}, where Γ_{0} = Γ, each Γ_{i+1} is obtained from Γ_{i} by adjoining a boundary edge or a boundary spike, and Γ_{k} is Y − Δ equivalent to the standard graph Σ_{n}. By Lemmas 5.2 and 7.3, Γ_{k} is critical. By Lemmas 11.1 and 11.2, each of the graphs Γ_{k−1}, Γ_{k−2}, …, Γ_{0} is critical; in particular, Γ = Γ_{0} is critical.

Lemma 13.2. A circular planar graph Γ is recoverable if and only if it is critical.

Proof. By Theorem 2, if Γ is critical, then Γ is recoverable. Suppose that Γ is not critical. By Lemma 13.1, M(Γ) has a lens. By 6.3, Γ is Y − Δ equivalent to a graph Γ′ with two edges in parallel or two edges in series. Γ′ cannot be recoverable, so by Lemma 5.4, Γ is not recoverable either.

Proof. of Theorem 1. Suppose that Γ_{1} and Γ_{2} are two critical circular planar graphs with π(Γ_{1}) = π(Γ_{2}). Let conductivities be put on both Γ_{1} and Γ_{2}. By Lemma 9.2, and Lemma 13.1, there is a sequence of critical graphs Γ_{1} = F_{0}, F_{1}, …, F_{k}, each F_{i+1} is obtained from F_{i} by adjoining a boundary edge or a boundary spike, and F_{k} is Y − Δ equivalent to Σ_{n}. We perform the same operations on Γ_{2} to produce a sequence Γ_{2} = H_{0}, H_{1}, …, H_{k}. For each i, let π_{i} = π(F_{i}). We apply the results of §8 and §12 to conclude that Λ(H_{1}) ∈ Ω(π_{1}). Hence π(H_{1}) = π(F_{1}). Continuing, we see that π(H_{i}) = π(F_{i}) for i = 1, 2, …, k. Each F_{i+1} has more connections than F_{i}, so each H_{i+1} has more connections than H_{i}. By Corollaries 4.3 and 4.4, the edge adjoined to H_{i} is recoverable. Working back from H_{k} to H_{0} which is critical and hence recoverable, we find that each H_{k} is recoverable, and hence critical.

Suppose the z-sequence for H_{k} were not 1, …, n, 1, …, n. Then a boundary edge or boundary spike could be adjoined to H_{k} to give another graph H_{k+1} with more connections than H_{k}. But π(H_{k}) = π(F_{k}) which is the maximal set of connections for circular planar graphs with n boundary nodes, so the z-sequence for M(H_{k}) is 1, … n, 1, … n.

The process of going from F_{k} to F_{0} = Γ_{1} by removing edges is the same as going from H_{k} to H_{0} = Γ_{2}. Each step of this process preserves equality of the z-sequences of the medial graphs M(F_{i}) and M(H_{i}). Thus M(Γ_{1}) and M(Γ_{2}) have the same z-sequence, and by Lemma 7.2 are Y − Δ equivalent.

REFERENCES

[1] Y. Colin de Verdiere, Reseaux Electriques Planaires, Publ. de l’Institut Fourier, no. 225, (1992), pp = 1–20.

[2] Y. Colin de Verdiere, Reseaux Electriques Planaires I, preprint, (1993), pp = 1–20.

[3] Y. Colin de Verdiere, I. Gitler, D. Vertigan, Planar Electric Networks II, preprint, (1994).

[4] D. Crabtree and E. Haynsworth, An identity for the Schur complement of a matrix, Proc. Amer. Math Soc. 22 (1969), pp 364-366.

[5] E. B. Curtis and J. A. Morrow, Determining the resistors in a network, SIAM J. of Applied Math., 50 (1990), pp. 918–930.

[6] E. B. Curtis and J. A. Morrow, The Dirichlet to Neumann map for a resistor network, SIAM J. of Applied Math, 51 (1991), pp. 1011–1029.

[7] E. B. Curtis, E. Mooers and J. A. Morrow, Finding the conductors in circular networks from boundary measurements, Math. Modelling and Numerical Analysis, vol 28, no. 7 (1994) pp. 781-813.

[8] C. L. Dodgson, Condensation of determinants, Royal Society of London, Proceedings, 15 (1866), pp150-155.

[9] F. R. Gantmacher, Matrix Theory , Chelsea, (1959).

[10] B. Grunbaum, Convex Polytopes, Interscience, (1967).

[11] E. Steinitz and H. Rademacher, Vorlesungen uber die Theorie der Polyhedra, Berlin, (1914).