\documentstyle[12pt]{article}
% Make Declarations

  \title{Recoverable and Unrecoverable Resistor Networks}

  \author{David D. Muresan}
  \date{August 17, 1993}
  \begin{document}

  \maketitle


 {\Large\bf 1. Introduction}

        In this paper we will attempt to answer some questions about
the recoverability of a general electrical network.  We will also take
a look at a few specific examples and some network operations.  It is important to mention that we will be working only with connected networks.\\
\\

{\bf Definition}.

An electrical network $\Omega$=($\Omega_0,\Omega_1$) consists of nodes ($\Omega_0$) and edges ($\Omega_1$=\{$\sigma_{ij}$\}, where $\sigma_{ij}$ connects $p_i$ and $p_j$ in $\Omega_0$ by a single conductor).  Edges are the conductors and nodes are ends of
 edges.  There are two kinds of nodes: a) boundary ($\partial\Omega_0$) and b) interior (int$\Omega_0$).  Let N($p_i$) = \{$p_j \mid \sigma_{ij} \in \Omega_1$ \} be the set of neighbors of $p_i$.  Potential $\Phi$ is applied on $\partial\Omega_0$ and this
 gives rise to a potential u on the interior nodes such that Kirkoff's Law is satisfied:\\

 $\sum_{p_{j} \epsilon N(p_{i})}$ $\gamma (p_{i} p_{j})(u(p_{i})-u(p_{j}))$ =  0 for all $p_i\epsilon$ int$\Omega_0$.

\vspace*{.3in}
Hence a given boundary function $\Phi$ uniquely determines the current into each boundary node.  If $\Phi$ is the vector of this boundary potentials and I is the vector of boundary currents, then there is a linear relationship I = $\Lambda\Phi$.  $\Lambda
$ is called the Dirichlet - Neumann map.\\
\vspace*{.3in}

{\Large\bf 2. The Question of Recovability}\\

Before going any further it is important to discuss some terminology.  At this point the reader is incouraged to take a look at David Ingerman's paper where all the terms are discussed in greater detail.\\

{\Large Kirkoff Matrix:}\\
Let $E$ be any electrical network that contains $n$ total nodes ($k$ boundary nodes and $m$ interior nodes).  With this electrical network we can associate an $n\ by\ n$ matrix, called the Kirkoff Matrix, which contains all the information about how the n
etwork is constructed.  The matrix is formed as follows:

1.  Enumerate the nodes starting with the boundary and ending with the interior.

2.  On the diagonal entries ($a_{ii}$) enter the sum of all the conductances meeting at node $i$.

3.  For the entry $a_{ij}$ put the negative value of the conductance that directly connects node $i$ and node $j$.\\
Example:\\
\begin{center}
\input{fig6}
\end{center}
\vspace{.4in}


{\Large Lambda Matrix:}\\
The Kirkoff Matrix can be broken down into four submatrices as shown in figure 1.\\
\begin{center}
\input{fig1}
\end{center} 
  Where $K'$ is a $k\ by\ k$ submatrix\\
\begin{center}
\bf Figure 1.
\end{center}
 From here the Dirichlet-Neumann map $\Lambda$ is found to be
 \begin{math}      
     \Lambda = K' - {B^T}{A^{-1}}B.
  \end{math}\\

Lambda is $k\ by\ k$ symmetric matrix where the sum of any row or column is zero.  And the only possible independent entries are the upper $k(k-1)/2$ diagonal ones.\\

By definition a network is recoverable {\em if and only if there does not exist a network with the same shape and same $\Lambda$ matrix for two different sets of conductivities.}\\

  Our aim now is to try to see if there exists a away to tell if a network is recoverable by looking at the $\Lambda$ matrix.  We note the upper diagonal entries of $\Lambda$ by $-x_1, ..., -x_n$ from left to right and from top to bottom as shown in fig. 
2.\\   

\begin{center}
\input {fig2}

\end{center}

\begin{center}
{\bf Figure 2.}
\end{center}

The entries $x_i$ are functions of the set of conductivities ($\gamma_j$) in the network. We will let $T( \gamma ) = ( x_1(\gamma), ...,x_n(\gamma) )$.  Now we can restate the recovability of a network as follows:\\
\vspace{.5in}

{\bf Definition 2.1}

{\em A network is recoverable if and only if T:$R^{N+}$--$>$$R^{M+}$ is globally 1-1. (Where $N$ = the number of conductors and $M$ = $k(k-1)/2)$.}\\


>From this definition it is clear that if $N$ $>$ $M$, $T$ is not 1-1 and the network is therefore unrecoverable.\\

{\bf Proposition 2.2} {\em  Let A be a recoverable network, and $A^*$ be the network formed by connecting two boundary nodes, not previously connected, by a known conductor.  Then $A^*$ is recoverable.}\\

Proof:\\
    If $A$ is recoverable then $T_A$ is 1-1.  By connecting two boundary nodes by a known resistor the $K'$ matrix will have some constants in the place of some zero's.  Therefore \\


\begin{math}
\vspace{.2in}
T_{A} = \left\{ 
\begin{array}{ccc}
               x_1 & = & {f_{1}(\gamma_{1} , ...,\gamma_{N})}\\
                . & = & .\\
                . & = & .\\
                . & = & .\\
               x_M & = & {f_{M}(\gamma_{1} , ...,\gamma_{N})}
\end{array}
\right. \Rightarrow T_{A^{*}} = \left\{
\begin{array}{ccc}
               x_1 & = & {f_{1}(\gamma_1, ...,\gamma_N) - c_1}\\
                . & = & . \\
                . & = & .\\
                . & = & .\\
               x_M & = & {f_{M}(\gamma_1, ...,\gamma_N) - c_M}
\end{array}
\right.\\
where \ c_1, ..., c_M\ are\ known.
\end{math}

Now, $T_{A^{*}}$(a) = $T_{A^{*}}$(b) implies $T_{A}(a) = T_{A}(b)$ which implies a = b.  Thus $T_{A^{*}}$ is 1-1 and $A^*$ is recoverable.\\

\vspace{.2in}
{\large  Minimal Networks} (networks which have $N = M$.)\\

>From now on we will look at networks which have as many conductors as there are upper diagonal entries in the $\Lambda$ matrix, namely $k(k-1)/2$.

Let $J(\gamma)$ denote the determinant of the derivative matrix of $T$ at $\gamma$. \\


 $J(\gamma)$ = det {\Large [($\frac{\partial x_i}{\partial \gamma_j}$)].}\\

 Then it is clear that if $J(\gamma)$ = 0 in an open region the network is unrecoverable, and if $J(\gamma)$ $\ne$ 0 the network is locally recoverable.\\

{\bf Fact 2.3} {\em Each entry of the transformation T is of the form\\


{\Large $\frac{Homogeneous\ Polynomial\ of\ degree\ (m+1)}{Homogeneous\ Polynomial\ of\ degree\ m}$,}} where $m$ = the number of interior nodes.\\

And this is why:  

 First we want to show that since $A$ is an  $m\ by\ m$ matrix, the determinant of $A$ is a homogeneous polynomial of degree $m$.  It is clear that Det($A$) is a polynomial.  To verify that it is a homogeneous polynomial we must show 

Det($A(t \lambda)$) = $t^m$ Det($A(\lambda)$).

Since $A$ is an $m\ by\ m$ matrix with entries which are homogeneous polynomials of degree 1, if we replace each $\lambda$ by $t \lambda$ we get each entry in $A$ multiplied by $t$.  This forces the new determinant to equal $t^m$Det($A$).\\
By definition we have:\\ 

 $A^{-1}$ = $\frac{Adj(A)}{Det(A)}$, where Adj($A$) is the transpose of the matrix of cofactors of $A$.\\

Let Adj($A$) = ($\alpha_{ij}$), with
 $\alpha_{ij}$ = $(-1)^{j+i}$Det($M_{ji}$), where $M_{ji}$ is a minor matrix of $A$, and therefore, by an argument similar to the one just given, it has a determinant which is a homogeneous polynomial of degree $(m-1)$.  So $A^{-1}$ has entries of the for
m:\\
       
{\Large $\frac{Homogeneous\ Polynomial\ of\ degree\ (m-1)}{Homogeneous\ Polynomial\ of\ degree\ m}$}\\

Next, recall that $\Lambda$ = $K' - {B^T}{A^{-1}}B$, where the entries in the matrix $K', B\ and\ B^T$ are homogeneous polynomials of degree 1.  Since homogeneous polynomial of degree 1 times homogeneous polynomial of degree $(m-1)$ is a homogeneous polyn
omial of degree $m$, the desired result follows.\\

Knowing this fact it is now obvious that for any Lambda transformation $T$, we have $T(\kappa p)$ = $\kappa$ $T(p)$, where $\kappa$ is a constant.\\


We made the following conjecture:

If $T$ has $J(\gamma)$ $\ne$ 0 everywhere (where $T$ is given by the $\Lambda$ matrix) then $T$ is globally 1-1.\\

{\Large\bf 3. More Specific Networks}\\

{\bf Definition 3.1} {\em If a boundary node is the end of exactly one conductor, and if the other end of the conductor is an interior node then the conductor is called a spike.}\\

{\bf Proposition 3.2} {\em In any connected network with at least three boundary nodes, if we have two spikes with one interior node (as in fig.3), we can always recover them.}
 
\begin{center}
\input {fig3}

{\bf Figure 3}
\end{center}

Let $S$ be the subnetwork formed by eliminating $\lambda_1$ and $\lambda_2$ from the network of figure 3.\\

In order to prove this proposition we prove the following lemma:\\

{\bf Lemma 3.3} {\em With the notation of proposition 3.1 there exists a unique potential u such that u(1) = 1, u(2) = 2, and u has zero current in all edges of the subnetwork $S$}.\\


Proof: At node 4 we want the current comming from the subnetwork to be zero.  Since node 4 is an interior node it must satisfy Kirkoff's Law:\\
       
$\gamma_1(u_4 - 1) + \gamma_2(u_4) = 0$.\\
>From here we uniquely determine 

$u_4 = \frac{\gamma_1}{\gamma_1 + \gamma_2}$\\

Now if we let the potential be $u_4$ at all the boundary nodes of the subnetwork we have no current in the subnetwork, and thus $u_4$ is the unique solution to the problem.\\

Now let's prove Proposition 3.2:\\
    Apply potential 1 at node 1, potential 0 at node 2 and have 0 current at all the other boundary points, including node 3.  This will uniquely determine $u_4 = u_3$, and will make the current from node 1 to node 4 ($I_{14}$) to equal the current from n
ode 4 to node 2 ($I_{42}$).  We can measure this current $I$ = $I_{14}$ = $I_{42}$ and then solve for $\gamma_1$ and $\gamma_2$.\\

$\gamma_1 = \frac{I}{1-u_3}$\\

$\gamma_2 = \frac{I}{u_3}$\\

{\bf Proposition 3.4}  {\em If two recoverable networks A and B are joined together by one node (interior to interior or boundary to boundary), the network so formed is recoverable.}\\

\vspace*{.5in}
\begin{center}
\vspace{.2in}
\input{fig4}

{\bf Figure 4}
\end{center}



Proof:\\
Before attacking the problem we introduce some notation.\\
Let $\Lambda^C = ({\lambda_{ij}}^C)$ be the Lambda matrix of the network $C$, and let $\Lambda^A = ({\lambda_{ij}}^A)$ be the Lambda matrix of the network $A$.\\ 

   To prove the proposition all we have to show is that we can find $\Lambda^A$ and $\Lambda^B$ from $\Lambda^C$.  Then by the assumption that $A$ and $B$ are recoverable, we can find the resistors of $A$ and $B$ from $\Lambda^A$, and $\Lambda^B$ respecti
vely.  We break the problem in two case.  One, when we consider $x$ a boundary node, and two, when we consider $x$ an interior node.\\

First, suppose that node $x$, at which $A$ and $B$ are joined, is a boundary node.  Order the nodes in $\partial C$ starting with nodes in $\partial A$ and ending with nodes in $\partial B$, making sure that $x$ is the last node in $\partial A$, and first
 in $\partial B$.  In constructing $\Lambda^C$ we apply potentials of 1, one node at a time, and 0 at the other nodes.  Notice that as long as the potential at node $x$ and the potential on $\partial B$ is 0, the only non zero contribution to the $\Lambda
^C$ matrix is from $A$ ( because the current on $\partial B$ is 0).  In other words,\\

 ${\lambda_{ij}}^C$ = ${\lambda_{ij}}^A$, for i,j $<$ $x$.\\

Now, when the potential at $x$ is 1, and 0 everywhere else we have\\

${\lambda_{ix}}^C$ = ${\lambda_{ix}}^A$, for i $<$ $x$.\\  

So we found the entries above the diagonal, in the $\Lambda^A$ matrix. But by symmetry of $\Lambda^A$, and the fact that the sum af any row or column in $\Lambda^A$ is zero, this is all we really need to determine $\Lambda^A$.  Similarly we find $\Lambda^
B$.\\  

Next, consider the case when $x$ is an interior node.\\
To prove the proposition in this case we must introduce the following lemma;\\

{\bf Lemma 3.5}  {\em With the notation of figure 4 let $j \in \partial A$.  Then there exists a unique potential $u$ on $C$ such that $u(j)$ = 1, $u(i)$ = 0 for $i \in \partial A, i \neq j$, and with no current on $\partial B$.}\\

Proof:\\
  Consider network $A$.  There is a unique potential $w$ on $A$ such that $w(j)$ = 1 and $w$ = 0 at all other nodes of $\partial A$.  We now define a potential $u$ on $C$ so that,\\

$u(q)$ = $w(q)$ if $q$ $\in$ $A$

$u(q)$ = $w(x)$ if $q$ $\in$ $B$.\\

Then $u$ restricted to $B$ defines a potential which has 0 current on all edges of $B$.  This proves existence.

To prove uniqueness, suppose that there exist two potentials $u_1$ and $u_2$ that are solutions to our problem. We have to show that if $v$ = $u_1$ - $u_2$, then $v$=0.  Or equivalently we have to show that if we let the potential on $\partial A$ be zero,
 and require that the current at each node of $\partial B$ be zero, the potential at every node is 0.\\

Take the network $B'$ to be the subnetwork $B$ where we now consider node $x$ to be a boundary point ($\partial B'$ = $\partial B \cup \{x\}$).  If $I_q$ is the current at boundary node $q$ then,\\

$\sum_{q \in \partial B'} {I_q}$ = 0.\\

However the sum of $I_q$ on $\partial B$=$\partial B' \setminus \{x\}$ is required to be zero,\\

$\sum_{p \in \partial B' \setminus \{x\}} {I_q}$ = 0.\\

This implies that $I_x$ is zero.
Now going back to network $C$, we know that the net current at $x$ is 0 ($x$ is an interior node of C).  Moreover, from the above argument, we also know that no current, from subnetwork $B$, comes or leaves node $x$.  This implies that in subnetwork $A$, 
Kirkoff's Law must be satisfied.\\

Since $v$=0 on $\partial A$, we have that $v$=0 on all of $A$.  In particular $v(x)$=0.  If we now return to $B'$, $v$ on $B'$ has 0 current at each node of $\partial B'$, which implies that $v$ is constant.  But since $v(x)$ = 0, we have that $v$ is zero
 on $B$.  This finishes the proof of lemma 3.5.\\

We now finish the proof of 3.4 in the case that $x$ is an interior node.  
Let $j \in \partial A$, and let $u$ be the potential of lemma 3.5.  We now want to compute $u(x)$, which satisfies the following system of equations,\\

${\lambda_{ij}}^C + u(x)(\sum_{k \in \partial B} {\lambda_{ik}}^C) = 0$ for $i \in \partial B$.\\

By the above lemma, this system of equations uniquely determines $u(x)$.  Then,\\

${\lambda_{ij}}^A = {\lambda_{ij}}^C + u(x)(\sum_{k \in \partial B} {\lambda_{ik}}^C)$, for i,j $\in \partial A$. \\

This shows how to find $\Lambda^A$ from $\Lambda^C$.  Similarly we can find $\Lambda^B$.\\

{\bf Proposition 3.6} {\em Any network that satisfies the following two conditions is recoverable.

a) Be a tree in which the boundary nodes are exactly the ends of the tree.

b) Every interior node is connected to at least three other nodes.}\\
 
Proof:\\
We prove the proposition by giving an explicit algorithm for finding any conductor in the tree network.
The proof is broken down in two cases.  One, when the conductor has both ends interior nodes (see figure 5).  And two, when the conductor has one end a boundary node, and the other end, an interior node (see figure 6).\\

Case 1 (two interior nodes).\\
Before giving the proof we need to explain figure 5 a little bit.  Letters $A$, $B$, $C$, $D$ stand for subnetworks of the initial network.  These subnetworks might have more boundary nodes, but all we care is that each subnetwork has at least one boundar
y node.\\

\begin{center}
\input{fig5} 

{\bf Figure 5}
\end{center}

Again as in the previous problems we introduce the following lemma,\\

{\bf Lemma 3.7} {\em With the notation of figure 5, there exists a unique potential u on the network such that:

1. u(i) = 1 for i $\in \partial A$

2. u(i) = 0 for i $\in \partial D$

3. u is with no current on $\partial B\ and\ \partial C$.}\\

Proof:\\
The proof is very similar to the one in lemma 3.5, and we don't present it here.\\

We now continue our proof of proposition 3.6.
Let $u$ be the potential of lemma 3.7.  Then potential at node 2 equals potential at node 5, and potential at node 4 equals potential at node 6.  All the current will flow from subnetwork $A$ to subnetwork $B$ through $\gamma_x$, and $u(2) = u(5)$ and $u(
4) = u(6)$.  This implies that:\\

$\gamma_x = \frac {I}{u(2) - u(4)}$, where $I$ is the sum of all the currents from the boundary nodes of subnetwork $A$.\\

Case 2 (one interior node and one boundary node)\\
If we look at figure 6, as in figure 5, letters $A$ and $B$ stand for subnetworks of the initial network.  Numbers 1, 2, 3 denote boundary nodes, and 4 is an interior node.
\begin{center}
\input{fig7}
{\bf Figure 6}
\end{center}
As in the first case it can be shown that with the notation of figure 6
 there exists a unique potential $u$ on the network such that $u(1)$ = 1, $u(i)$ = 0 for $i$ $\in \partial A$, and $u$ has 0 current on $\partial B$.  Moreover, this potential $u$ has no current on any edge of $B$.  In recovering $\gamma_y$, apply this po
tential $u$ on the network.  Then potential at node 3 equals potential at node 4 and all the current flows from node 1 to subnetwork $A$.  Now:\\

$\gamma_y = \frac{I}{1 - u_4}$, where $I$ is the current at node 1.




  \end{document}
%----fig1.tex----
\begin{math}
K =  \left(
\begin{array}{cc}
K' & B^T\\
 B & A
\end{array}
\right)
\end{math}

%----------fig2.tex------
\begin{math}
\Lambda = \left(
\begin{array}{cccc}
 * & -x_1 = \lambda_{12} & -x_2 = \lambda_{13} & \rightarrow \\
 \ast & *  & ... & ...\\
 \ast & *  & *  & -x_{\frac{(k-1)k}{2}} = \lambda_{(k-1),k}\\
 \ast & *  & * & * 
\end{array}
\right)
\end{math}
%----fig3.tex--------

\begin{picture}(300,200)
{\thicklines
\put (150,150){\line(1,1){42}}
\put (190,190){$\bullet$}
\put (190,200){2}
\put (180,170){$\gamma_2$}


\put (150,150){\line(-1,1){42}}
\put (105,190){$\bullet$}
\put (105,200){1}
\put (110,170){$\gamma_1$}

\put (131,141){$u_4 = u_3$}
\put (145,157){4}
\put (150,150){\line(1,0){100}}
\put (150,150){\line(-1,0){100}}

\put (50,150){\line(0,-1){50}}
\put (250,150){\line(0,-1){50}}

\put (50,100){\line(1,0){200}}
%\put (150,100){\line(0,-1){42}}
\put (147,98){$\bullet$}
\put (147,89){3}
}


%------------------------

%----------fig4.tex---------

\begin{picture}(300,110)
\thicklines
\put (105,90){\Large $C=A+B$}

\put (150,50){\line(-2,1){75}}
\put (150,50){\line(-2,-1){75}}
\put (210,90){\line(0,-1){82}}
\put (210,49){\line(1,0){25}}


\put (150,50){\line(2,1){75}}
\put (150,50){\line(2,-1){75}}
\put (90,90){\line(0,-1){82}}
\put (90,49){\line(-1,0){25}}

\put (147,47){$\bullet$}
\put (145,33){$x$}

\put (100,44){\Large $A$}
\put (180,44){\Large $B$}


\end{picture}

%----------fig5.tex----------------

\begin{picture}(200,200)
\thicklines
\put(0,175){\framebox(25,25){A}}
\put(175,175){\framebox(25,25){B}}

\put(25,187){\line(1,0){25}}
\put(49,184){$\bullet$}
\put(55,185){1}

\put(175,187){\line(-1,0){25}}
\put(149,184){$\bullet$}
\put(143,185){2}
\put(123,185){(0)}

\put(0,0){\framebox(25,25){C}}
\put(175,0){\framebox(25,25){D}}

\put(25,12){\line(1,0){25}}
\put(49,9){$\bullet$}
\put(55,10){4 (0)}

\put(175,12){\line(-1,0){25}}
\put(149,9){$\bullet$}
\put(143,10){3}

%-----------------------------------

\put(25,175){\line(2,-1){75}}
\put(175,175){\line(-2,-1){75}}
\put(97,135){$\bullet$}

\put(96,147){5}

\put(25,25){\line(2,1){75}}
\put(175,25){\line(-2,1){75}}
\put(97,59){$\bullet$}

\put(96,47){6}

\put(100,139){\line(0,-1){78}}
\put(105,100){$\gamma_x$}
\end{picture}


%--------fig6.tex--------

\begin{picture}(400,200)
\thicklines

\put(100,150){\line(0,-1){60}}
\put(97,150){$\bullet$}
\put(105,120){$\gamma_1 $}
\put(97,158){1}

\put(100,90){\line(1,-1){60}}
\put(37,27){$\bullet$}
\put(20,50){$\gamma_2 $}
\put(27,27){2}

\put(100,90){\line(-1,-1){60}}
\put(158,27){$\bullet$}
\put(146,50){$\gamma_3 $}
\put(173,27){3}
\put(99,70){4}



\put(200,100){
\begin{math}
K = \left(
\begin{array}{cccc}
          \gamma_1 & 0 & 0 & -\gamma_1\\
           0  & \gamma_2 & 0 & -\gamma_2\\
           0  & 0 & \gamma_3 & -\gamma_3\\
        -\gamma_1 & -\gamma_2 & -\gamma_3 & \gamma_1+\gamma_2+\gamma_3         

\end{array}
\right)
\end{math}}

\end{picture}






%-------fig7.tex--------------------


\begin{picture}(200,200)
\thicklines

\put(0,0){\framebox(25,25){$B$}}
\put(175,0){\framebox(25,25){$A$}}

\put(25,12){\line(1,0){25}}
\put(49,9){$\bullet$}
\put(55,10){3 (0)}

\put(175,12){\line(-1,0){25}}
\put(149,9){$\bullet$}
\put(143,10){2}



\put(97,135){$\bullet$}

\put(96,147){1}

\put(25,25){\line(2,1){75}}
\put(175,25){\line(-2,1){75}}
%\put(97,59){$\bullet$}

\put(96,47){4}

\put(100,139){\line(0,-1){78}}
\put(105,100){$\gamma_y$}
\end{picture}

























