\documentstyle{article}
\title{Theory of Equivalent Networks \\
                 and\\
        Some of its Applications}
\author{David V. Ingerman}
\date{1992}
\sloppy

\def\vs{\vskip1pc}
\def\hs{\hskip1cm}
\def\ss{\rule[-0.4cm]{0cm}{1cm}}
\begin{document}
\maketitle

\large
\vs\vs
\section{Introduction}

We consider the following network $\Omega$.  The nodes of $\Omega$
are the points in 3D space. The set of nodes is denoted by $\Omega_{n}$.
We define some subset $\Omega_{b}$ of $\Omega_{n}$ as {\it boundary} nodes, so
that cardinality of $\Omega_{b}$  N$_{b} = card\Omega_{b} \geq$ 2.
All other nodes of $\Omega_{n}$ are called {\it interior}.
The set of interior nodes is denoted by $\Omega_{i}$.
N$_{i} = card\Omega_{i} \geq$ 0. \vs
 
\hs $\Omega_{n} = \Omega_{b}\cup\Omega_{i}.$

\hs $\Omega_{b}\cap\Omega_{i} = \o.$

\hs N = $card\Omega_{n}$ = N$_{b}$ + N$_{i}.$ \vs 

For two different nodes {\it p} and {\it q} belonging to $\Omega_{n}$
the number $\gamma(pq)$
is called {\it conductance} of {\it pq}. The function $\gamma$, called
{\it conductivity}, is a non-negative real function. Two nodes {\it p}
and {\it q} are called {\it neighbors} if $\gamma(pq) > 0$. The set of all
neighbors of node {\it p} is called {\it N(p)}. If {\it p} and {\it q}
are neighbors {\it pq} is called an {\it edge} or a {\it conductor}. 

A {\it network of conductors} is a network with defined set of boundary 
nodes and conductivity function.  Below we will call a network of
conductors just a network.

For a node {\it p} belonging to $\Omega_{n}$ {\it u(p)} denotes the
{\it potential} at {\it p}.
A function {\it u}: $\Omega_{n} \rightarrow$ R gives the {\it current}
from node {\it p} to $q\in N(p)$ by {\it Ohm's Law}
$$I(pq) = \gamma(pq)(u(p) - u(q)).$$ 
For $q \notin N(p)$      
$$ I(pq) = I(qp) = 0. $$
For a boundary node {\it q}
$$I(q)=\sum_{p\in N(q)}I(qp)$$
is called a {\it boundary current}.

A function {\it u} is called $\gamma$-{\it harmonic function}, if for each 
interior node {\it p} 
  $$\sum_{q\in N(p)}I(pq) = 0.$$
According to {\it Kirchoff's Law},
if a function $\phi$ is defined at the boundary nodes, the network
$\Omega$ will acquire a unique $\gamma$-harmonic function {\it u} with
$u(p) = \phi (p)$ for all boundary nodes {\it p}.

For a network $\Omega$ with a conductivity function on it the linear map
$\Lambda$: $\phi \rightarrow I_{\phi}$ is defined by
$\Lambda\phi = I_{\phi}$, where $\phi$ is a vector of boundary potentials
 $I_{\phi}$ is the corresponding vector of boundary currents.
This map is called Dirichlet-to-Neumann map.
>From the maximum principle and Kirchoff's and Ohm's Laws
it can be proved that any 
$\Lambda$ has following properties (See [1])
\begin{itemize}
\item it is symmetric
\item all non-diagonal entries are non-positive
\item total of all entries in each row equals 0.
\end{itemize}

\section{Plane equivalent of a network}

{\bf Definition 2.1} The {\it Kirchoff matrix} of the network $\Omega$
is a square NxN matrix
$K(\Omega) = \{k_{ij}\}$ where \vs 
\hs $k_{ij} = -\gamma(p_{i}p_{j})\hs{\rm if}\hs i\neq j$

\noindent and

\hs $k_{ii} = \sum_{q\in N(p_{i})}\gamma(p_{i}q).$ \vs 
\noindent The matrix $K(\Omega)$ contains all information about
conductivity function of 
network $\Omega$. We denote the set of Kirchoff matrices by $\cal K$.
A matrix $M=\{m_{ij}\}$ belongs to $\cal K$ if
\vs
$\hs m_{ij} = {m_{ji}} \leq 0\hs{\rm if}\hs i\neq j,$

$\hs m_{ii} > 0,$

\hs $\sum_{j=1}^{N}m_{ij} = 0.$
\vs 
\noindent By this definition the set of Dirichlet-to-Neumann maps
belongs to $\cal K$.

If $\bar{\Omega}$ is a network with no interior nodes,
by Kirchoff's and Ohm's Laws
         $$K(\bar{\Omega})\phi = I_{\phi},$$
therefore,
         $$K(\bar{\Omega}) = \Lambda(\bar{\Omega}).$$
This proves the next statements.

{\bf Statement  2.2 } The set of Dirichlet-to-Neumann maps
{\it equals} $\cal K$.

{\bf Statement  2.3 } For any $\Lambda\in\cal K$ there exists unique 
network $\Omega$ with no interior nodes such that $\Lambda$
represents the Dirichlet-to-Neumann map for $\Omega$.
 
{\bf Statement  2.4 } The map from networks with no interior nodes to
Dirichlet-to-Neumann maps is 1 $\leftrightarrow$ 1.
 
{\bf Definition 2.5 } A {\it plane equivalent} of network $\Omega$ is a network
$\bar{\Omega}$ with no interior nodes which has the same 
Dirichlet-to-Neumann map as $\Omega$.
 
{\bf Theorem 2.6 } Any resistor network has unique plane equivalent. 

{\bf Definition 2.7 }
Two networks are {\it equivalent} if they have the same plane equivalent.

For a network $\Omega$ with a conductivity function on it the linear map
$\Phi$: $\phi\rightarrow u_{\phi}$ is defined by
$\Phi\phi = u_{\phi}$, where $\phi$ is a vector of boundary potentials
and $u_{\phi}$ is the corresponding vector of potentials on nodes
of $\Omega$. $\Phi$ is represented by an NxN$_{b}$ matrix.

We number nodes of a network $\Omega$ so that boundary nodes go first. That
is,

\hs $p_{i}\in\Omega_{b}\Leftrightarrow i\leq$ N$_{b}$

\noindent and

\hs $p_{i}\in\Omega_{i}\Leftrightarrow i>$ N$_{b}.$
\vs
\noindent We write K($\Omega$) and $\Phi(\Omega)$ in block form,
\vs
\begin{tabular}{l|c|cc|c|c|}
\cline{2-2}\cline{5-6}
\hs $\Phi(\Omega) =$ & {\it I} \ss      & and & $K(\Omega)$ = & $K'$ & $M^{T}$
\\ \cline{2-2}\cline{5-6}
                     & $\ss\Phi_{\Omega}$ & & & {\it M}  & $\Xi$
\\ \cline{2-2}\cline{5-6}
\end{tabular}
\vs
\noindent where {\it I} is the identity matrix.
Now using Kirchoff's and Ohm's Laws we obtain that
\vs
\begin{equation}
\begin{tabular}{l|c|c|c|c|c|c|}
                                        \cline{2-3}\cline{5-5}\cline{7-7}
\hs & $K'\ss $ & $M^{T}$ & &  {\it I}     & = & $\Lambda(\Omega)$
                                     \\ \cline{2-3}\cline{5-5}\cline{7-7}
\hs & {\it M}\ss    &   $\Xi$ & & $\Phi_{\Omega}$ &   & {\it 0}
                                     \\ \cline{2-3}\cline{5-5}\cline{7-7}
\end{tabular}
\end{equation}
\vs
\noindent where {\it 0} is a zero matrix. Since $\Xi$
is non-singular, we can obtain that
\begin{equation}
\Lambda(\Omega) = K(\bar{\Omega}) = K' - M^{T}\Xi^{-1}M.
\end{equation}
This equation expresses the Dirichlet-to-Neumann map of a network
in terms of blocks of this network's Kirchoff matrix.

\vs
\section{Blocks in Dirichlet-to-Neumann maps}

We consider a network $\Omega$ with Dirichlet-to-Neumann map $\Lambda$.
We write the Kirchoff matrix of $\Omega$ in block form,
\vs
\begin{tabular}{l|c|c|}
                                        \cline{2-3}
\hs\hs $K(\Omega)$ =   &   $K'\ss $   & $M^{T}$

                                     \\ \cline{2-3}

              & {\it M}  & $\Xi\ss $
                                     \\ \cline{2-3}
\end{tabular}
\vs
\noindent Let {\it A} be a {\it n} by {\it n} square submatrix
of $K'$ corresponding to rows $i_{1},...,i_{n}$ and columns
$j_{1},...,j_{n}$. Let {\it C} be the N$_{i}$x{\it n}
matrix formed by choosing columns $j_{1},...,j_{n}$ of block {\it M}.
Let {\it B} be the {\it n}xN$_{i}$ matrix
formed by choosing rows $i_{1},...,i_{n}$ of block $M^{T}$.
$\Lambda_{A}$ is the submatrix of $\Lambda$ corresponding
to rows $i_{1},...,i_{n}$ and columns $j_{1},...,j_{n}$.

By formula (2)
$$ \Lambda_{A} = A - B\Xi^{-1} C. $$
Now we have that
\vs
\begin{tabular}{l|c|c|c|c|c|c|c|c|}
                                        \cline{2-3}\cline{5-6}\cline{8-9}
\hs\hs & {\it A}\ss & {\it B} & &  {\it I} & {\it 0}  & = & $\Lambda_{A}$ & $ B$
                                     \\ \cline{2-3}\cline{5-6}\cline{8-9}
\hs\hs & {\it C}\ss &  $\Xi$ & & $-\Xi^{-1}C$ & {\it I} & & {\it 0} & $\Xi$ 
                                     \\ \cline{2-3}\cline{5-6}\cline{8-9}
\end{tabular}
\vs
\noindent If
\vs
\begin{tabular}{l|c|c|}
                                        \cline{2-3}
\hs\hs\hs {\it W} =   & {\it A}\ss & {\it B}
                                     \\ \cline{2-3}
              & {\it C}\ss  & $\Xi$
                                     \\ \cline{2-3}
\end{tabular}
\vs
\noindent we obtain that
\begin{equation}
|W| = |\Lambda_{A}||\Xi|. 
\end{equation}
Taking {\it A} to be an entry of $K'$ we can find any entry
of $\Lambda$ in terms of two determinants of blocks of $K(\Omega)$.
\vs
\begin{tabular}{l|c|c|c|c|c}
                                        \cline{3-4}
\hs\hs  $\lambda_{ij} =$    & & $k'_{ij}$\ss & $m^{T}_{i}$ & &$\slash |\Xi|. $
                                     \\ \cline{3-4}
            & & $m_{j}$\ss  & $\Xi$ &
                                     \\ \cline{3-4}
\end{tabular}
\vs

Since $\Xi$ is positive definite we have that
$$ sign|\Lambda_{A}| = sign|W|. $$


\section{Theorem about elimination of a subnetwork}

{\bf Definition 4.1 }
A network $\hat{\Omega}=\{\hat{\Omega}_{n},\hat{\Omega}_{b},\hat{\gamma}\}$
is a {\it subnetwork} of $\Omega=\{\Omega_{n},\Omega_{b},\gamma\}$ if \vs
\hs $\hat{\Omega}_{i}\subset\Omega_{i}.$

\hs $\hat{\Omega}_{b}=(\cup_{p\in\hat{\Omega}_{i}}N(p))\backslash\hat{\Omega}_{i}.$

\hs $p,q\in\hat{\Omega}_{n}\Rightarrow\hat{\gamma}(pq)=\gamma(pq).$
\vs
\noindent Any subnetwork is defined by its set of interior nodes. 
The Kirchoff matrix $\hat{K}$ of $\hat{\Omega}$
is a principal submatrix of {\it K}.

{\bf Definition 4.2 } {\it Elimination} of a subnetwork $\hat{\Omega}$ from
a network $\Omega$ is a transformation of $\Omega$ to $\Psi$ denoted by 
$\Omega \ominus \hat{\Omega}$ if \vs 
\hs $\Psi_{b} = \Omega_{b}$

\hs $\Psi_{i} = \Omega_{i}\backslash\hat{\Omega}_{i}.$

\hs $\gamma_{\Psi}(pq) = \gamma_{\Omega}(pq)\hs{\rm if}\hs p\notin\hat{\Omega}_{n}.$
 
\hs $\gamma_{\Psi}(pq) = \gamma_{\hat{\bar{\Omega}}}(pq)\hs{\rm if}\hs p,q\in\hat{\Omega}_{b}.$ \vs
\noindent where $\gamma_{\hat{\bar{\Omega}}}$ is the conductivity function on the
plane equivalent of $\hat{\Omega}$. In other words to eliminate some subnetwork
from a network is to replace this subnetwork with its plane equivalent.

We number the nodes so that the boundary nodes of $\Omega$ go first and interior nodes
of $\hat{\Omega}$ go last. That is,
\vs
\hs $p_{i}\in\Omega_{b}\Leftrightarrow i\leq card\Omega_{b}$

\noindent and

\hs $p_{i}\in\hat{\Omega}_{i}\Leftrightarrow i>card\Omega - card\hat{\Omega}_{i}$
\vs
\noindent Now we have that 
\vs
\begin{tabular}{l|c|c|c|}
                                        \cline{2-4}
              &  $K'\ss $   & $P^{T}$ & $U^{T}$ 
                                     \\ \cline{2-4}
\hs\hs $K(\Omega) =\ss $ & {\it P}  & {\it S}  & $R^{T}$
                                     \\ \cline{2-4}
              & {\it U}\ss  & {\it R} & {\it C}
                                     \\ \cline{2-4}
\end{tabular}
\vs

\noindent Taking into account that {\it C}
is non-singular and using Definition 4.2 and formula (2) we can obtain that  
if $\Psi = \Omega\ominus\hat{\Omega}$ then
\vs
\begin{tabular}{l|c|c|c}
                                        \cline{2-3}
$K(\Psi)$ = &  $K' - U^{T}C^{-1}U$ \ss    & $P^{T} - U^{T}C^{-1}R$ &
$ = \Lambda(\{\Psi_{n},\Psi_{n},\gamma_{\Psi}\})$
                                     \\ \cline{2-3}

                &  $P - R^{T}C^{-1}U$\ss  & $S - R^{T}C^{-1}R$ &
                                     \\ \cline{2-3}
\end{tabular}
\vs
\noindent We define linear maps $\Phi(\Omega)$ and $\Phi(\Psi)$ as it was done 
in Section 2. Solving equation (1) we obtain that
$$ \Phi_{\Psi} = -(S - R^{T}C^{-1}R)^{-1}(P - R^{T}C^{-1}U) $$
and 
\vs
\begin{tabular}{l|c|c|c|}
                                        \cline{2-2}
              &  $I\ss $    
                                     \\ \cline{2-2}\cline{4-4}
\hs $\Phi(\Omega) =\ss $ & $\Phi_{\Psi}$ &  =   & $\Phi(\Psi)$
                                     \\ \cline{2-2}\cline{4-4}
              & $-C^{-1}(T+R\Phi_{\Psi})$ \ss  &  & $-C^{-1}(T+R\Phi_{\Psi})$
                                     \\ \cline{2-2}\cline{4-4}
\end{tabular}
\vs
\noindent The non-singularity of $S - R^{T}C^{-1}R$ follows from (3). 
Now it is easy to show that 
$$ \Lambda(\Psi) = \Lambda(\Omega).$$
We proved the following theorem.

{\bf Theorem 4.4 } Suppose $\Psi=\Omega \ominus \hat{\Omega}$ where
$\hat{\Omega}$ is a subnetwork of $\Omega$. Then  $\Psi$ and $\Omega$ are
equivalent. That is  $\Lambda(\Psi)=\Lambda(\Omega)$.
The matrix $\Phi(\Psi)$ is an upper part of $\Phi(\Omega)$. Therefore,
$$ I_{\Psi}(pq) = I_{\Omega}(pq)\hs{\rm if}\hs p,q\notin\Psi_{N}.$$
In other words, elimination of a subnetwork does not affect 
potentials and currents outside of it.
\vs

\section{Recoverable networks}

We will say that we know the {\it shape} of a network if we know all neighbors
for each node of this network.

{\bf Definition 5.1} A network is {\it recoverable}
if there does not exist a network with the 
same shape, same plane equivalent (or Dirichlet-to-Neumann map),
and different conductivity function.

A network is {\it non-recoverable} if it is not recoverable.  

By Definition 5.1 two recoverable networks with the same shape have different 
plane equivalents.

{\bf Statement 5.2} All subnetworks of a recoverable network are recoverable.

{\it Elimination of node p} is an elimination of a subnetwork $\hat{\Omega}$
such that $\hat{\Omega}_{i} = p$.

Elimination of a subnetwork $\hat{\Omega}$ from $\Omega$ results in the 
same network as elimination of all interior nodes of $\hat{\Omega}$ in any
order. Elimination of some set {\it S} of interior nodes of $\Omega$ 
results in the same network as elimination of the subnetwork $\hat{\Omega}$
if $\hat{\Omega}_{i} = S$.

By Theorem 4.4 elimination of an interior node {\it p} of a network
$\Omega$ does not affect plane equivalent of any subnetwork $\hat{\Omega}$ of
$\Omega$ if $p\in\hat{\Omega}_{i}$. 

\vs

\section{Chain elimination}

We consider a network $\Omega = \{\Omega_{n}, \Omega_{b}, \gamma\}$
with $\Omega_{b}\neq\Omega_{n}$. 
We will eliminate interior nodes of $\Omega$ one by one.
The network obtained after $j^{th}$ elimination is called $\Omega^{j}$. 
Let
\vs 
\hs $E^{j} = \Omega_{n}\backslash\Omega^{j}_{n}.$
\vs
\noindent Let $\hat{\Omega}^{j}$ be the subnetwork of $\Omega$ with 
$\hat{\Omega}^{j}_{i} = E^{j}.$ Then
$$ \Omega^{j} = \Omega\ominus\hat{\Omega}^{j}.$$ 

\noindent By Theorem 4.4 
$$ \Lambda(\Omega) = \Lambda(\Omega^{j}). $$

Let $\Psi^{j} = \{\Omega_{n},\Psi^{j}_{b},\gamma\}$ where 
\vs
\hs $\Psi^{j}_{b} = \Omega_{n}\backslash E^{j}.$
\vs
\noindent $\Psi^{{\rm N}_{i}} = \Omega.$ By formula (2) we obtain that 
$$ K(\Omega\ominus\hat{\Omega}^{j}) = K(\Omega^{j}) = \Lambda(\Psi^{j}).$$
$$ K(\Omega) = \Lambda(\Psi^{0}). $$
\vs

\section{Specific comments}

Formula (2) gives a direct algorithm for finding
the Dirichlet-to-Neumann map
for any network with known conductivity function. For networks with
two boundary nodes this formula represents the generalized 
parallel and series laws of electrical circuit theory.

 

\end{document}
{\bf Theorem 4.3} Map between recoverable networks with fixed shape to
their plane 1 is 1$\leftrightarrow$1.

{\it Proof} Suppose it exists two different networks
with this shape and the same plane equivalent.
Then these networks are not recoverable. Because of Theorem 2.1 each
network has unique plane equivalent.

%\section{Blocks in Dirichlet-to-Neumann maps}

\end{document}




