\documentclass{article}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{fullpage}

\title{Connections and Determinants}
\author{Mark Blunk\\Sam Coskey}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem} [thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor} [thm]{Corollary}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{conj}[thm]{Conjecture}
\newcommand{\sign}{\mathop{\mathrm{sign}}}


\begin{document}
\maketitle
\begin{abstract}
 The relationship between connections and determinants in conductivity
 networks is discussed.  We paraphrase Lemma 3.12, by Curtis and
 Morrow \cite{C-M}, infamous in smaller circles as ``the page 50
 proof.''
\end{abstract}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A conductivity network $G$ is given by a graph $\Gamma$, and some
arrangement of conductivities.  The vertices of the graph are made up
of boundary ($\mathcal{B}$) and interior ($\mathcal{I}$) nodes, and
are ordered with the boundary nodes listed first.  The graph may be
directed; in special cases, the conductivities will be assigned to
bidirectional edges \cite{C-M} or vertices \cite{O}.

Vectors of potentials $u$ and currents $I$ are defined over the
vertices of $\Gamma$.  The Kirchhoff matrix $K$ is defined so that
\(K\cdot u=I\).  The information in this matrix is equivalent to $G$.

The response matrix $\Lambda$ is defined so that \(\Lambda\cdot
u|_{\mathcal{B}} = I(u)|_{\mathcal{B}}\).  $\Lambda$ is thus the Schur
complement of \(K(\mathcal{I};\mathcal{I})\) in $K$, that is \(\Lambda =
K/K(\mathcal{I};\mathcal{I})\).  For now, we will assume that
\(K(\mathcal{I};\mathcal{I})\) is invertible; we will later impose
certain hypotheses to guarantee that this is true.

We take the definition of connection from \cite{C-M}.  Given two
disjoint sets of $k$ boundary nodes, $P$ and $R$, a connection from
$P$ to $R$ is a set of vertex disjoint paths through $\Gamma$ from the
vertices of $P$ to the vertices of $R$ through the interior nodes
$\mathcal{I}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Connections and permutations}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{defn}
 Let $S_m$ represent the permutation group on $m$ symbols.
\end{defn}

Suppose $P$ and $R$ are given as above. Let \(M =
K(P+\mathcal{I};R+\mathcal{I})\).  Then 
\begin{equation}
 \det M =
  \sum_{\sigma\in S_n}\sign(\sigma)\prod_{i=1}^n M(i;\sigma(i))
\end{equation}
In the above formula, a permuation $\sigma$ of $n$ elements may be
interpreted as a possible connection from $P$ to $R$.  The path can be
constructed as follows.  Suppose that all of the nodes in $P$ are
numbered \(1,2,\ldots,k\), the nodes of $R$ are also numbered
\(1,2,\ldots,k\), and that the interior nodes denoted $\mathcal{I}$
are numbered \(k+1,\ldots,n\).

Begin with the ordered set \(T_0 = (1,\ldots,k)\), the nodes of $P$.
This is the beginning of the path.  The first step in the path, the
set $T_1$, is obtained by permuting each element of the set by
$\sigma$.  In this new set, mark each element that is less than or
equal to $k$.  To obtain the second step in the path, $T_2$, let
$\sigma$ act on each unmarked element of $T_1$, keeping the marked
elements unchanged.  Continue this process, until every element of the
newest set is marked.  This set is the last step.

Suppose the last step of the path is $T_m$.  These are the elements of
$R$.  In all of the ordered sets $T_0$ up to $T_m$, no element greater
than $k$ is repeated.  Thus, each $\sigma$ represents a single
vertex-disjoint connection from $P$ to $R$.  However, $\sigma$ is only
an actual connection through a network if every vertex $i$ in
\(P\cup\mathcal{I}\) is connected by a directed edge to the vertex
$\sigma(i)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Determinental Expansion}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

It is clear that their is a relationship between connections through a
network and the determinant of the Kirchhoff matrix for that network.
It is natural to seek a representation of paths within corresponding
determinants.

\begin{defn}
 Suppose $S$ is a set. Then \(\pi(\mathcal{S})\) is the set of all
 orderings of $\mathcal{S}$.
\end{defn}

\begin{defn}
 Suppose $A$ is a matrix, and \(I = (i_1,i_2,\ldots,i_m)\) and \(J =
 (j_1,j_2,\ldots,j_n)\) are subsets of the rows and columns of $A$,
 respectively.

\begin{itemize}
 \item Let \(D[I,J]\) represent the determinant of an \(m \times m\)
 sub-matrix of $A$ obtained by deleting the entries of $A$ in rows
 \(i_1,\ldots,i_m\) and in columns \(j_1,\ldots,j_n\).

 \item Let \(D(I,J)\) represent the determinant of an \(m \times m\)
 sub-matrix of $A$ obtained by including only the entries of $A$ in
 rows \((i_1,\ldots,i_m)\) and in columns \((j_1,\ldots,j_m)\), in
 listed order.  Of course, this definition and the previous only make
 sense when $m=n$.

 \item Let \(a_{p\mapsto I\mapsto q} = a_{ps_1}a_{s_1s_2}\cdots
 a_{s_mq}\), where $-a_{ij}$ is the entry in the $i^{\rm th}$ row and
 $j^{\rm th}$ column of $A$, for $i \neq j$.

 \item Let the symbol $I+J$ denote the concatenation
 $(i_1,\ldots,i_m,j_1,\ldots,j_n)$.
\end{itemize}
\end{defn}

We now proceed to describe an expansion of the determinant of a
general matrix.  When the matrix is interpreted as a subdeterminant
of a Kirchhoff matrix, the terms of the expansion may be interpreted
as boundary to boundary connections.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{One-expansion}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We first examine the case that we wish to examine a one-connection, a
single path.  The sets $P$ and $R$ would thus have one element each.
The following lemma is stated very generally, but the matrix $A$ is
of the form of, and will later be interpreted as, the submatrix
\(K(P+\mathcal{I};R+\mathcal{I})\).

\begin{lem}
Let $A$ be an \(n\times n\) matrix, with negative entries everywhere
except on the second through $n^{\rm th}$ diagonals.
\begin{displaymath}
 A = \begin{bmatrix}
 -a_{11} \hfill\vline & -a_{12} & -a_{13} &        & -a_{1n} \\ \hline
 -a_{21} \hfill\vline & +a_{22} & -a_{23} & \cdots & -a_{2n} \\
 -a_{31} \hfill\vline & -a_{32} & +a_{33} &        & -a_{3n} \\
         \hfill\vline & \vdots  &         & \ddots & \vdots  \\
 -a_{n1} \hfill\vline & -a_{n2} & -a_{n3} & \cdots & +a_{nn}
\end{bmatrix}
\end{displaymath}
Let the ordered set \(\mathcal{B}=(1)\), and the ordered set
\(\mathcal{I}=(2,\ldots,n)\).  Suppose that $J$ be a subset of
$\mathcal{I}$.  Suppose that \(\sigma\in\pi(J)\). Then the determinant
of $A$ may be written as follows.
\begin{equation} 
\det A \quad = \quad -\sum_{\sigma} 
               a_{1\mapsto \sigma \mapsto 1}\cdot D[1,J;1,J]
\label{eq:1expansion}
\end{equation}
\label{connections:one}
\end{lem}

\begin{proof}
First, note that the expression (\ref{eq:1expansion}) may be expanded
as follows.
\begin{eqnarray*}
 \det A \quad= \quad -a_{11}\cdot D[1;1]
            & - & \sum_{j\neq1}(a_{1j}a_{j1})\cdot D[1,j;1,j]   \\
            & - & \sum_{\substack{j_1,j_2\neq1 \\ j_1\neq j_2}} 
                               (a_{1j_1}a_{j_1j_2}a_{j_21})
                                 \cdot D[1,j_1,j_2;1,j_1,j_2]   \\[3pt]
            & - & \cdots                                        \\[3pt]
            & - & \sum_{\substack{j_i\neq1 \\ j_i\neq j_k}}
                               (a_{1j_1}a_{j_1j_2}\cdots a_{j_n1})\cdot 1
\end{eqnarray*}

We proceed by induction on $n$.  First, note that when $n=1$, $J$ is
null, so the determinant of $A$ is equal to its lone element.  Hence
(\ref{eq:1expansion}) would correctly give \(-a_{11}\cdot 1\) for $\det
A$.

Now, suppose that given a matrix of the form $A$, but of size
\((n-1)\times (n-1)\), its determinant may be computed using the above
expansion.  We will show that the determinant of $A$ can be computed
using the above expansion.

The cofactor expansion of the determinant gives us the following expression.
\begin{displaymath}
 \det A = 
 - a_{11}\cdot D[1;1] + a_{12}\cdot D[1;2] 
 - a_{13}\cdot D[1,3] + a_{14}\cdot D[1;4]
 - + \cdots           + (-1)^{n}a_{1n}\cdot D[1;n]
\end{displaymath}
In each subdeterminant in the above expansion (except the first),
perform $i-2$ row interchanges so that the $i^{\rm th}$ row is now the
top row of the subdeterminant.  These row interchanges result in
multiplying each term by $(-1)^{i-2}$, thus changing the sign of each
odd term.
\begin{eqnarray*}
 = -a_{11}\cdot D[1;1] 
                    & + & a_{12}\cdot D(2,3,4,5,\ldots,n;1,3,4,5,\ldots,n)  \\
                    & + & a_{13}\cdot D(3,2,4,5,\ldots,n;1,2,4,5,\ldots,n)  \\
                    & + & a_{14}\cdot D(4,2,3,5,\ldots,n;1,2,3,5,\ldots,n)  \\
                    & + & \cdots                                            \\
                    & + & a_{1n}\cdot D(n,2,3,4,\ldots,n-1;1,2,3,4,\ldots,n-1)
\end{eqnarray*}
Each determinant in the above expression is now of the form of $A$,
but of size \((n-1)\times(n-1)\).  Thus, by the inductive assumpsion, we
may rewrite each of them using (\ref{eq:1expansion}).
\begin{eqnarray*}
 = -a_{11}\cdot D[1;1]
  &   \mbox{} - a_{12} \Big\{a_{21}\cdot D[1,2;1,2]
  &   \mbox{} + \sum_{j\neq1,2}(a_{2j}a_{j1})\cdot D[1,2,j;1,2,j]      \\
  & & \mbox{} + \cdots                                                 \\
  & & \mbox{} + \sum_{\substack{j_i\neq1,2 \\ j_i \neq j_k}}
                     (a_{2j_1}\cdots a_{j_{n-2}1})\cdot 1\Big\}        \\[3pt]
  &   \mbox{} - a_{13} \Big\{a_{31}\cdot D[1,3;1,3]
  &   \mbox{} + \sum_{j\neq1,3}(a_{3j}a_{j1})\cdot D[1,3,j;1,3,j]      \\
  & & \mbox{} + \cdots                                                 \\
  & & \mbox{} + \sum_{\substack{j_i\neq1,3 \\ j_i \neq j_k}}
                     (a_{3j_1}\cdots a_{j_{n-2}1})\cdot 1\Big\}        \\[3pt]
  &   \mbox{} - \cdots \hspace{1.1in} &                                \\
  &   \mbox{} - a_{1n} \Big\{a_{n1}\cdot D[1,n;1,n]
  &   \mbox{} + \sum_{j\neq1,n}(a_{nj}a_{j1})\cdot D[1,n,j;1,n,j]      \\
  & & \mbox{} + \cdots                                                 \\
  & & \mbox{} + \sum_{\substack{j_i\neq1,n \\ j_i \neq j_k}}
                     (a_{nj_1}\cdots a_{j_{n-2}1})\cdot 1\Big\}
\end{eqnarray*}
Each expansion in brackets contains the same number of terms.
Defactoring (carrying through) the multipliers in front of each group
(the $a_{1i}$ terms), and combining the corresponding terms (those of
equal length) from each group, gives the result.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Two-expansion}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We now consider the case that $P$ and $R$ each have two elements.  The
proof will proceed along similar lines.

\begin{lem}
Let $A$ be an \(n\times n\) matrix, with negative entries everywhere
except on the third through $n^{\rm th}$ diagonals.
\begin{displaymath}
 A = \begin{bmatrix}
 -a_{11} & -a_{12} \hfill\vline & -a_{13} &        & -a_{1n} \\
 -a_{21} & -a_{22} \hfill\vline & -a_{23} & \cdots & -a_{2n} \\ \hline
 -a_{31} & -a_{32} \hfill\vline & +a_{33} &        & -a_{3n} \\
         & \vdots  \hfill\vline &         & \ddots & \vdots  \\
 -a_{n1} & -a_{n2} \hfill\vline & -a_{n3} & \cdots & +a_{nn}
\end{bmatrix}
\end{displaymath}
Let the ordered set \(\mathcal{B}=(1,2)\), and the ordered set
\(\mathcal{I}=(3,\ldots,n)\).  Suppose that $J$ is a subset of
$\mathcal{I}$.  Suppose that the sets \(\{J_1,J_2\}\) partition $J$
into two subsets.  Further suppose that \(\sigma_1\in\pi(J_1)\) and that
\(\sigma_2\in\pi(J_2)\). Then the determinant of $A$ may be written as
follows.
\begin{equation}
 \det A \quad = \quad \sum_{\sigma_1,\sigma_2}
                           ( a_{1\mapsto \sigma_1 \mapsto 1}  \cdot
                             a_{2\mapsto \sigma_2 \mapsto 2}
                           - a_{1\mapsto \sigma_1 \mapsto 2}  \cdot
                             a_{2\mapsto \sigma_2 \mapsto 1}) \cdot
                             D[1,2,J;1,2,J]
\label{eq:2expansion}
\end{equation}
\end{lem}

\begin{proof}
First, note that the equation (\ref{eq:2expansion}) may be expanded into the
following.
\begin{displaymath}
\begin{array}{llll}
\det A & =  & \lefteqn{(a_{11}a_{22} - a_{12}a_{21})\cdot D[1,2;1,2]}   \\[3pt]
 & \mbox{}+ & \sum_{j_1 \in \mathcal{I}} 
 &                    ( a_{11}a_{2j_1}a_{j_12} - a_{12}a_{2j_1}a_{j_11} \\
 & & &                  a_{1j_1}a_{j_11}a_{22} - a_{1j_1}a_{j_12}a_{21} )
                 \cdot D[1,2,j_1;1,2,j_1]                               \\[3pt]
 & \mbox{}+ & \sum_{\substack{j_1,j_2 \in \mathcal{I} \\ j_1 \neq j_2}} 
 &              ( a_{11}a_{2j_1}a_{j_1j_2}a_{j_22}
                - a_{12}a_{2j_1}a_{j_1j_2}a_{j_21}                      \\
 & & &   \mbox{}+ a_{1j_1}a_{j_11}a_{2j_2}a_{j_22}
                - a_{1j_1}a_{j_12}a_{2j_2}a_{j_21}                      \\
 & & &   \mbox{}+ a_{1j_1}a_{j_1j_2}a_{j_21}a_{22}
                - a_{1j_1}a_{j_1j_2}a_{j_22}a_{21} )
            \cdot D[1,2,j_1,j_2;1,2,j_1,j_2]                            \\[3pt]
 & \mbox{}+ & \cdots &                                                  \\[3pt]
 & \mbox{}+ & \sum_{\substack {j_i \in \mathcal{I} \\ j_i \neq j_k}} 
 &              ( a_{11}a_{2j_1}a_{j_1j_2} \cdots a_{j_{n-2}2}
                - a_{12}a_{2j_1}a_{j_1j_2} \cdots a_{j_{n-2}1}          \\
 & & &  \mbox{} + a_{1j_1}a_{j_11}a_{2j_2} \cdots a_{j_{n-2}2}
                - a_{1j_1}a_{j_12}a_{2j_2} \cdots a_{j_{n-2}1}          \\
 & & &   \mbox{}+ \cdots                                                \\
 & & &   \mbox{}+ a_{1j_1}a_{j_1j_2} \cdots a_{j_{n-2}1}a_{22} 
                - a_{1j_1}a_{j_1j_2} \cdots a_{j_{n-2}1}a_{22}  )\cdot 1
\end{array}
\end{displaymath}

We proceed by induction on $n$.  When $n=2$, $J_1$ and $J_2$ are null.
Hence, (\ref{eq:2expansion}) reduces to \((a_{11}a_{22} -
a_{12}a_{21})\cdot1\), which is the determinant of $A$.  When $n=3$,
(\ref{eq:2expansion}) reduces to
\begin{displaymath}
 \det A  =  (a_{11}a_{22} - a_{12}a_{21})\cdot a_{33}
         +  (  a_{13}a_{31}a_{22} - a_{13}a_{32}a_{21}
             + a_{11}a_{23}a_{32} - a_{12}a_{23}a_{31} )\cdot 1
\end{displaymath}
which is equivalent to determinant of $A$.  Now suppose that given a
matrix of the form $A$, but of size \((n-2)\times(n-2)\), its
determinant may be computed using the above expansion.  We will show
that the Laplace expansion of the determinant of $A$ can be
manipulated to derive (\ref{eq:2expansion}).

Taking the Laplace expansion of the determinant of $A$ along the first
two rows gives the following expression.
\begin{displaymath}
 \begin{array}{rl}
\det A  = & \Big\{(a_{11}a_{22} - a_{12}a_{21})
                \cdot D(3,4,5,6,\ldots,n;3,4,5,6,\ldots,n)         \\
   & \mbox{} - (a_{11}a_{23} - a_{13}a_{21})
                \cdot D(3,4,5,6,\ldots,n;2,4,5,6,\ldots,n)         \\
   & \mbox{} + (a_{11}a_{24} - a_{14}a_{21})
                \cdot D(3,4,5,6,\ldots,n;2,3,5,6,\ldots,n)         \\
   & \mbox{} - (a_{11}a_{25} - a_{15}a_{21})
                \cdot D(3,4,5,6,\ldots,n;2,3,4,6,\ldots,n)         \\
   & \mbox{}+ - \cdots                                             \\
   & \mbox{}+ (-1)^{n+4}(a_{11}a_{2n}-a_{1n}a_{21})
                \cdot D(3,4,5,6,\ldots,n;2,3,4,\ldots,n-1)  \Big\} \\
 + & \Big\{   (a_{12}a_{23} - a_{13}a_{22})
                \cdot D(3,4,5,6,\ldots,n;1,4,5,6,\ldots,n)         \\
   & \mbox{}- (a_{12}a_{24} - a_{14}a_{22})
                \cdot D(3,4,5,6,\ldots,n;1,3,5,6,\ldots,n)         \\
   & \mbox{}+ (a_{12}a_{25} - a_{15}a_{22})
                \cdot D(3,4,5,6,\ldots,n;1,3,4,6,\ldots,n)         \\
   & \mbox{}- + \cdots                                             \\
   & \mbox{}+ (-1)^{n+5}(a_{12}a_{2n}-a_{1n}a_{22})
                \cdot D(3,4,5,6\ldots,n;1,3,4,5,\ldots,n-1) \Big\} \\
 + & \Big\{(a_{13}a_{24} - a_{14}a_{23})
                \cdot D(3,4,5,6,\ldots,n;1,2,5,6,\ldots,n)         \\
   & \mbox{}- (a_{13}a_{25} - a_{15}a_{23})
                \cdot D(3,4,5,6,\ldots,n;1,2,4,6,\ldots,n)         \\
   & \mbox{}+ - \cdots                                             \\
   & \mbox{}+ (-1)^{n+6}(a_{13}a_{2n}-a_{1n}a_{23})
                \cdot D(3,4,5,6,\ldots,n;1,2,4,5\ldots,n-1) \Big\} \\
% + & \Big\{(a_{14}a_{25} - a_{15}a_{24})
%               \cdot D(3,4,5,6,\ldots,n;1,2,3,6,\ldots,n)          \\
%   & \mbox{}- + \cdots                                             \\
%   & \mbox{}+(-1)^{n+7}(a_{14}a_{2n}-a_{1n}a_{24})
%               \cdot D(3,4,5,6,\ldots,n;1,2,3,5,\ldots,n-1) \Big\} \\
 + & \cdots                                                        \\
 + & (a_{1(n-1)}a_{2n} - a_{1n}a_{2(n-1)})
               \cdot D(3,4,5,6,\ldots,n;1,2,3,4,\ldots,n-2)
 \end{array}
\end{displaymath}
For every \((n-2)\times(n-2)\) subdeterminant, let $j_1,j_2$ be the
indices of the first and second columns deleted by the Laplace
expansion.  Now perform the following row interchanges.  If \(j_1
\not\in \mathcal{I}\) and \(j_2 \in\mathcal{I}\), perform $j_2 - 3$
row interchanges so that row $j_2$ is now the first row in the
subdeterminant. If \(j_1,j_2 \in \mathcal{I}\), perform $j_1 - 3$ row
intechanges so that row $j_1$ is now in the first row, and perform
$j_2 - 4$ row interchanges so that row $j_2$ is now in the second row
of the subdeterminant.  No row changes are peformed on the
subdeterminant where columns $1$ and $2$ have been deleted.  The
result of these row interchanges is to negate every subdeterminant
where row $1$ is deleted, and to change the sign of every other term
to positive.  Continuing from above,
\begin{displaymath}
 \begin{array}{ll}
 = & \Big\{\ \ (a_{11}a_{22}-a_{12}a_{21})
               \cdot D(3,4,5,6,\ldots,n;3,4,5,6\ldots,n)               \\
   & \mbox{} - (a_{11}a_{23}-a_{13}a_{21})
               \cdot D(3,4,5,6,\ldots,n;2,4,5,6\ldots,n)               \\
   & \mbox{} - (a_{11}a_{24}-a_{14}a_{21})
               \cdot D(4,3,5,6,\ldots,n;2,3,5,6,\ldots,n)              \\
   & \mbox{} - (a_{11}a_{25}-a_{15}a_{21})
               \cdot D(5,3,4,6,\ldots,n;2,3,4,6,\ldots,n)              \\
   & \mbox{} - \cdots                                                  \\
   & \mbox{} - (a_{11}a_{2n}-a_{1n}a_{21})
               \cdot D(n,3,4,5,\ldots,n-1;2,3,4,5\ldots,n-1)    \Big\} \\
 + & \Big\{\ \ (a_{12}a_{23}-a_{13}a_{22})
               \cdot D(3,4,5,6,\ldots,n;1,4,5,6\ldots,n)               \\
   & \mbox{} + (a_{12}a_{24}-a_{14}a_{22})
               \cdot D(4,3,5,6,\ldots,n;1,3,5,6\ldots,n)               \\
   & \mbox{} + (a_{12}a_{25}-a_{15}a_{22})
               \cdot D(5,3,4,6\ldots,n;1,3,4,6,\ldots,n)               \\
   & \mbox{} + \cdots                                                  \\
   & \mbox{} + (a_{12}a_{2n}-a_{1n}a_{22})
               \cdot D(n,3,4,5,\ldots,n-1;1,3,4,5,\ldots,n-1)   \Big\} \\
 + & \Big\{\ \ (a_{13}a_{24}-a_{14}a_{23})
               \cdot D(3,4,5,6,\ldots,n;1,2,5,6,\ldots,n)              \\
   & \mbox{} + (a_{13}a_{25}-a_{15}a_{23})
               \cdot D(3,5,4,6,\ldots,n;1,2,4,6,\ldots,n)              \\
   & \mbox{} + \cdots                                                  \\
   & \mbox{} + (a_{13}a_{2n}-a_{1n}a_{23})
               \cdot D(3,n,4,5,\ldots,n-1;1,2,4,5,\ldots,n-1)   \Big\} \\
% + & \Big\{\ \ (a_{14}a_{25}-a_{15}a_{24})
%              \cdot D(4,5,3,6,\ldots,n;1,2,3,6,\ldots,n)              \\
%   & \mbox{} + \cdots                                                 \\
%   & \mbox{} + (a_{14}a_{2n}-a_{1n}a_{24})
%              \cdot D(4,n,3,5,\ldots,n-1;1,2,3,5,\ldots,n-1)   \Big\} \\
 + & \cdots                                                            \\
 + & (a_{1(n-1)}a_{2n}-a_{1n}a_{2(n-1)})
               \cdot D(n-1,n,3,4,\ldots,n-2;1,2,3,4,\ldots,n-2)        
 \end{array}
\end{displaymath}
More simply, this can be stated
\begin{displaymath}
\begin{array}{ll}
 = \lefteqn{(a_{11}a_{22} - a_{12}a_{21})\cdot D[1,2;1,2]}                  \\
 - & \sum_{j_1 \in \mathcal{I}}(a_{11}a_{2j_1}- a_{1j_1}a_{22})
    \cdot D(j_1,\mathcal{I}\backslash\{j_1\};2,\mathcal{I}\backslash\{j_1\})\\
 + & \sum_{j_1 \in \mathcal{I}}(a_{12}a_{2j_1} - a_{1j_1}a_{21})
    \cdot D(j_1,\mathcal{I}\backslash\{j_1\};1,\mathcal{I}\backslash\{j_1\})\\
 + & \sum_{j_1,j_2 \in \mathcal{I}}(a_{1j_1}a_{2j_2} - a_{1j_2}a_{2j_1})
     \cdot D(j_1,j_2,\mathcal{I}\backslash\{j_1,j_2\};
               1,  2,\mathcal{I}\backslash\{j_1,j_2\})                       
 \end{array}
\end{displaymath}
By the inductive assumption, the subdeterminant of size \((n-2)\times
(n-2)\) in the third sum can be expressed by (\ref{eq:2expansion}).
The subdeterminants of size \((n-2)\times (n-2)\) in the first two sums
contain only one negative diagonal entry, so they refer to a one
connection, and can be expressed by (\ref{eq:1expansion}).  Hence the
subdeterminants in all three sums can be expanded by the assumption to
produce the following expression.
\begin{displaymath}
 \begin{array}{llll}
\lefteqn{(a_{11}a_{22} - a_{12}a_{21})\cdot D[1,2;1,2]}                 \\[3pt]
 - & \sum_{j_1 \in \mathcal{I}} (a_{11}a_{2j_1} - a_{1j_1}a_{21})
   &  \lefteqn{\Big\{ -a_{j_12}\cdot D[1,2,j_1;1,2,j_1]} &              \\
   & & - & \sum_{j_1,j_2 \in \mathcal{I}\backslash\{j_1\}}
                 (a_{j_1j_2}a_{j_22}) 
           \cdot D[1,2,j_1,j_2;1,2,j_1,j_2]                             \\
   & & - & \cdots                                                       \\
   & & - & \sum_{j_i \in \mathcal{I}\backslash\{j_1\}}
                 (a_{j_1j_2}\cdots a_{j_{n-3}j_{n-2}}a_{j_{n-2}2})
           \cdot 1 \Big\}                                               \\
 + & \sum_{j_1 \in \mathcal{I}} (a_{12}a_{2j_1} - a_{1j_1}a_{22})
   & \lefteqn{\Big\{ -a_{j_11}\cdot D[1,2,j_1;1,2,j_1]}              &  \\
   & & - & \sum_{j_2 \in \mathcal{I}\backslash\{j_1\}}
                ( a_{j_1j_2}a_{j_21}) \cdot D[1,2,j_1,j_2;1,2,j_1,j_2]  \\
   & & - & \cdots                                                       \\
   & & - & \sum_{j_i \in \mathcal{I}\backslash\{j_1\}}
                ( a_{j_1j_2}\cdots a_{j_{n-3}j_{n-2}}a_{j_{n-2}1})
                    \cdot 1 \Big\}                                      \\
 + & \sum_{j_1,j_2 \in \mathcal{I}} (a_{1j_1}a_{2j_2} - a_{1j_2}a_{2j_1})
   & \lefteqn{\Big\{(a_{j_11}a_{j_22} - a_{j_12}a_{j_21}) 
                    \cdot D[1,2,j_1,j_2;1,2,j_1,j_2]}                &  \\
   & & + & \sum_{j_3 \in \mathcal{I}\backslash \{j_1,j_2\}}
                 (  a_{j_11}a_{j_2j_3}a_{j_32} - a_{j_12}a_{j_2j_3}a_{j_31}\\
   & &   & \mbox{}+ a_{j_1j_3}a_{j_31}a_{j_22} - a_{j_1j_3}a_{j_32}a_{j_21} )
                    \cdot D[1,2,j_1,j_2,j_3;1,2,j_1,j_2,j_3]            \\
   & & + & \cdots                                                       \\
   & & + & \sum_{j_i \in \mathcal{I}\backslash\{j_1,j_2\}}                   
            ( a_{j_11}a_{j_2j_3}a_{j_3j_4}
                    \cdots a_{j_{n-3}j_{n-2}}a_{j_{n-2}2}               \\
   & & & \mbox{} - a_{j_12}a_{j_2j_3}a_{j_3j_4}
                    \cdots a_{j_{n-3}j_{n-2}}a_{j_{n-2}1}               \\
   & & & \mbox{} + a_{j_1j_3}a_{j_31}a_{j_2j_4}
                    \cdots a_{j_{n-3}j_{n-2}}a_{j_{n-2}2}               \\
   & & & \mbox{} - a_{j_1j_3}a_{j_32}a_{j_2j_4}
                    \cdots a_{j_{n-3}j_{n-2}}a_{j_{n-2}1}               \\
   & & & \mbox{} + - \cdots                                             \\
   & & & \mbox{} + a_{j_1j_3}a_{j_3j_4}
                    \cdots a_{j_{n-3}j_{n-2}}a_{j_{n-2}1}a_{j_22}       \\
   & & & \mbox{} - a_{j_1j_3}a_{j_3j_4}
                    \cdots a_{j_{n-3}j_{n-2}}a_{j_{n-2}2}a_{j_21} )
            \cdot1\Big\}
 \end{array}
\end{displaymath}
As was the case with the one connection, defactoring the multipliers
of each expression in curly braces gives the result.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{$k$-expansion}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Next, we will generalize the above expansions to represent a connection
of any size.  But first, some junk about permutations.

\begin{defn}
 Let \(\left(\substack{I \\ J}\right) =
 \left(\substack{i_1,i_2,\ldots,i_m \\ j_1,j_2,\ldots,j_m}\right)\) be
 the mapping from the elements of $I$ to the elements of $J$ in their
 listed order.  Suppose $p$ is the number of interchanges required to
 sort the elements \((j_1,j_2,\ldots,j_m)\) into increasing order.
 Then let \(\sign\left(\substack{I \\ J}\right) = (-1)^p\).  Let the
 binary infix operator $\circ$ act on two mappings, and represent the
 new mapping obtained by composing the two argument mappings.
\end{defn}

\begin{lem}
Suppose that $S$ is an ordered set of integers, that $I$ and $J$
partition $S$, and that $I$ and $J$ are sorted in increasing order.
Then \(\sign\left(\substack{S \\ I+J}\right)=(-1)^{\sum I -
\sum_1^{|I|}i}\).  Simplifying the sum, and changing its sign (which
does not affect its value in modulus $2$) gives us the expression
\(\sign\left(\substack{S \\ I+J}\right)=(-1)^{\sum I + \frac 1 2
|I|(|I|+1)}\).
\label{lem:rearrange}
\end{lem}

\begin{proof}[Proof outline]
This concept is perhaps best explained with an example.  Suppose that
\(S=(1,\ldots,10)\), and that \(I=(3,4,9)\).  $I+J$ is therefore
\((3,4,9,1,2,5,6,7,8,10)\).  To sort this set, the third element
requires $9-3$ interchanges to bring it to the $9^{\rm th}$ spot from
the $3^{\rm rd}$ position.  Similarly, the second element must be
interchanged $4-2$ times, and the first element must be interchanged
$3-1$ times.  Summing together all of the interchanges gives
\begin{displaymath}
 (3-1) + (4-2) + (9-3) = \sum I - \sum_1^3 i
\end{displaymath}
The result is hopefully an intuitive consequence of understanding this
example.
\end{proof}

\begin{lem} \emph{(The Curtis-Morrow expansion)}
Let $A$ be an \(n\times n\) matrix, with negative entries everywhere
except on the $(k+1)^{\rm st}$ through $n^{\rm th}$ diagonals.
\begin{displaymath}
 A = \begin{bmatrix}
-a_{11} &        & -a_{1k} \hfill\vline &              &        & -a_{1n}   \\
        & \ddots &         \hfill\vline &              &        &           \\
-a_{k1} &        & -a_{kk} \hfill\vline &              &        &   \\ \hline
        &        &         \hfill\vline & +a_{k+1,k+1} &        & -a_{k+1,n}\\
        &        &         \hfill\vline &              & \ddots &           \\
-a_{n1} &        &         \hfill\vline & -a_{n,k+1}   &        & +a_{nn}
     \end{bmatrix}
\end{displaymath}
Let the ordered set \(\mathcal{B} = (1,\ldots,k)\), and the ordered
set \(\mathcal{I}=(k+1,\ldots,n)\).  Suppose that $J$ is a subset of
$\mathcal{I}$.  Suppose that \(\{J_1,J_2,\ldots,J_k\}\) partition $J$
into $k$ subsets.  Suppose that $\sigma$ is a set of $k$ elements such
that \(\sigma_i\in\pi(J_i)\), for \(1\leq i\leq k\). Then the
determinant of $A$ may be written as follows.
\begin{equation}
\det A = (-1)^k\sum_{\tau\in S_k}\sign(\tau)
               \sum_\sigma   \left\{
              \left(\prod_{i=1}^k a_{i\mapsto \sigma_i \mapsto \tau(i)}\right)
              \cdot D[\mathcal{B}\cup J;\mathcal{B}\cup J]
              \right\} = (P \Rightarrow R)
 \label{eq:Kexpansion}
\end{equation}
Further, the above expression is to be interpreted as a connection
from \(P=\mathcal{B}\) to \(R=\mathcal{B}\) through the interior nodes
$\mathcal{I}$, and is denoted \((P\Rightarrow R)\).  A direct
connection that does not go through any interior nodes is denoted
\((P\rightarrow R)\).
\label{lem:Kexpansion}
\end{lem}

\begin{proof}
We proceed by induction on $k$, the size of the upper-left (purely
negative) quadrant of $A$, and on $n$, the dimension of the matrix.
Notice that (\ref{eq:Kexpansion}) holds for $k=1$ by Lemma
\ref{connections:one}.  Also notice that when $n=k$, the expansion
(\ref{eq:Kexpansion}) is merely the definition of the determinant of a
matrix of size \(k\times k\) with all negative entries.

Now suppose inductively that for any matrix of the form of $A$, with
dimension at most \((n-1)\times(n-1)\), and upper left-hand corner of
size at most $k\times k$, that its determinant can be expressed by
(\ref{eq:Kexpansion}) for any size connection less than $k$.  We will
show that the Laplace expansion on the first $k$ rows of $A$ is
equivalent to the expansion (\ref{eq:Kexpansion}).

Taking the Laplace expansion of the determinant of $A$ along the first
$k$ rows gives the following expression.
\begin{displaymath}
 \det A=\sum_{|Q|=k} (-1)^{\sum P + \sum Q}\ D(P;Q)\ D[P;Q]
\end{displaymath}
In each term of the above sum, some of the elements of $Q$ will be in
the set $\mathcal{B}$, and the rest will be in the set $\mathcal{I}$.
Let $Q_B$ consist of the elements of $Q$ that are elements of
$\mathcal{B}$, and $Q_I$ consist of the elements of $Q$ that are
elements of $\mathcal{I}$.

Now perform row interchanges on $D[P;Q]$ (except for when $Q=R$) until
it is of the form \(D(Q_I+(\mathcal{I}\backslash Q_I);\
(R+\mathcal{I})\backslash Q)\).  This will take \(\sum Q_I -
\sum_1^{|Q_I|}(k+i)\) row interchanges.  The new subdeterminant is now
of the form of $A$, but of size $n-k$.  Also, notice that $D(P;Q)$ is
of the form of $A$, with $n=k$.  Thus, by the inductive assumption, we
have
\begin{eqnarray*}
 \det A & = & \sum_{|Q|=k} (-1)^{\sum P + \sum Q}\cdot (P\rightarrow Q)
              \cdot (-1)^{\sum Q_I - \sum_1^{|Q_I|}(k+i)}
              \ (Q_I\Rightarrow R\backslash Q_B)               \\
        & = & \sum_{|Q|=k} (-1)^{\sum Q_B + \frac 1 2 (k+|Q_I|)(k+|Q_I|+1)}
              \cdot (P\rightarrow Q)
              \cdot (Q_I\Rightarrow R\backslash Q_B)
\end{eqnarray*}
In the above expression \(|Q_I|+|Q_B|=k\), so we may perform the
following rearrangement.
\begin{eqnarray*}
 \lefteqn{  \frac 1 2 (k+|Q_I|)(k+|Q_I|+1) 
        =   \frac 1 2 (2k-|Q_B|)(2k-|Q_B|+1)}                  \\
 &      = & 2(k^2-kQ_B)+ \frac 1 2 (|Q_B|^2 + |Q_B| + 2|Q_I|)  \\
 & \equiv & \frac 1 2 (|Q_B|^2 + |Q_B| + 2|Q_I|)
        =   \frac 1 2 |Q_B|(|Q_B|+1) + |Q_I| \pmod 2 
\end{eqnarray*}
Accordingly, substitution of the sign exponent gives us
\begin{displaymath}
 \det A = \sum_{|Q|=k} (-1)^{\sum Q_B + \frac 1 2 |Q_B|(|Q_B|+1) + |Q_I|}
          \cdot (P\rightarrow Q)
          \cdot (Q_I\Rightarrow R\backslash Q_B)
\end{displaymath}
By Lemma \ref{lem:rearrange}, the expression \(\sum Q_B + \frac 1 2
|Q_B|(|Q_B|+1)\) can be represented as the sign of a mapping, giving
us
\begin{equation}
 \det A = \sum_{|Q|=k} (-1)^{|Q_I|}
          \sign\left(\substack{Q \\ Q_B+(R\backslash Q_B)}\right)
          \cdot (P\rightarrow Q)
          \cdot (Q_I\Rightarrow R\backslash Q_B)
\label{eq:laplace}
\end{equation}
In the above equation, the \((P\rightarrow Q)\) is the determinant of a
\(k\times k\) matrix.  Using (\ref{eq:Kexpansion}), with $\sigma$ and
$J$ null, we can see that this determinant is the sum of products
representing every possible direct connection from the elements of $P$
to the elements of $R$.  Similarly, the \((Q_I\Rightarrow R\backslash
Q_B)\) is the sum of products representing every possible connection
from the elements of $Q_I$ to the elements of $R$ that are not already
reached in the first path (through leftover interior nodes).  The
product \((P\rightarrow Q)\cdot (Q_I\Rightarrow R\backslash Q_B)\) is
thus the sum of every path from $P$ to $Q$ appended onto every path
from $Q_I$ to \(R\backslash Q_B\) through interior; this sum will
include every connection from $P$ to $R$ through $Q$.  Summing over
every possible $Q$ then gives every possible connection from $P$ to
$R$ through the interior of the graph.

It is hopefully clear that the expression (\ref{eq:laplace}) contains
exactly the same terms as the expansion (\ref{eq:Kexpansion}).  We
will now show that corresponding terms have the same sign.

Fix a permutation $\alpha$ on the elements of $Q$, and a
permutation $\delta$ on the elements of \(R\backslash Q_B\).  The
$\alpha$ and $\delta$ determine a permutation $\tau$ of the elements
of $R$ as follows.
\begin{displaymath}
 \left(\substack{P \\ \tau(R)}\right)
      = \left(\substack{P \\ \alpha(Q)                 }\right)
  \circ \left(\substack{Q \\Q_B+\delta(R\backslash Q_B)}\right)
\end{displaymath}
Together, $\alpha$, $\delta$, and $Q$ map one-to-one onto the terms of
(\ref{eq:Kexpansion}).  Now, take a term from (\ref{eq:Kexpansion}),
with sign \((-1)^k\sign(\tau)\).  The corresponding term in
(\ref{eq:laplace}) has sign
\begin{eqnarray*}
\lefteqn{(-1)^{|Q_I|}\sign\left(\substack{Q\\Q_B+(R\backslash Q_B)}\right)
\cdot (-1)^{k}    \sign\left(\substack{P  \\\alpha(Q)}\right)
\cdot (-1)^{|Q_I|}\sign\left(\substack{Q_I\\\delta(R\backslash Q_B)}\right)} \\
& = & (-1)^{k}    \sign\left(\substack{Q  \\Q_B+(R\backslash Q_B)}\right)
\cdot \sign\left(\substack{P \\ \alpha(Q)}\right)
\cdot \sign\left(\substack{Q_B+\quad Q_I\quad \\
                           Q_B+\delta(R\backslash Q_B)}\right)
      \sign\left(\substack{Q_B+\quad Q_I\quad \\
                           Q_B+(R\backslash Q_B)}\right)                     \\
& = & (-1)^{k}\sign\left(\substack{P \\ \alpha(Q)}\right)
 \cdot\sign\left(\substack{Q \\Q_B+\delta(R\backslash Q_B)}\right)           \\
& = & (-1)^{k}\sign(\tau)
\end{eqnarray*}
This concludes the proof of Lemma \ref{lem:Kexpansion}.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Connections Revisited}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section, we apply Lemma \ref{lem:Kexpansion} in order to
establish a relationship between the determinant of a response matrix
and connections through its network.  What follows is a summary of
Theorem 3.13 of \cite{C-M}.

\begin{lem}
Suppose that $G$ is a directed network with $n$ interior nodes, and
that $K$ is the Kirchhoff matrix for this network.  Suppose further
that there is a directed path through $G$ from every interior node to
the boundary.

Let \(A=K(\mathcal{I};\mathcal{I})\).  Thus, $A$ is of the form
\begin{equation}
 A = \begin{bmatrix}
  \sigma_1+\epsilon_1 & -a_{12} & -a_{13} &        & -a_{1n} \\
  -a_{21} & \sigma_2+\epsilon_2 & -a_{23} & \cdots & -a_{2n} \\
  -a_{31} & -a_{32} & \sigma_3+\epsilon_3 &        & -a_{3n} \\
          & \vdots  &                     & \ddots & \vdots  \\
  -a_{n1} & -a_{n2} & -a_{n3}             & \cdots & \sigma_n+\epsilon_n
     \end{bmatrix}
\label{eq:pd1}
\end{equation}
where for \(1\leq i\leq n\), \(\epsilon_i\geq 0\) and \(\sigma_i =
\sum_{j \neq i} a_{ij}\).  Then \(\det A > 0\). Furthermore, every
principal subdeterminant of $A$ is also greater than zero.
\label{lem:pos}
\end{lem}

\begin{proof}
We begin by constructing a new network, $\tilde G$, with the same
interior nodes as $G$, but only one boundary node (with index zero).
Let \(\mathcal{B}=(0)\), and \(\mathcal{I}=(1,2,\ldots,n)\).  For
\(1\leq i\leq n\), let $\epsilon_i$ be the row-sum of the $i^{\rm th}$
row of $A$. Then for every interior node $i$, we let $\epsilon_i$ be the
conductivity from $i$ to the boundary node.  Hence, there is a
directed path from every interior node in $\tilde G$ to the boundary
node.

The Kirchhoff matrix $\tilde K$ of $\tilde G$ is thus of the form
\begin{equation}
 \tilde K = \begin{bmatrix}
  0         \hfill\vline  & 0       &       0 &      0  &       &   0 \\ \hline
 -\epsilon_1\hfill\vline  & \sigma_1+\epsilon_1
                          & -a_{12} & -a_{13} &         & -a_{1n}     \\
 -\epsilon_2\hfill\vline  & -a_{21} & \sigma_2+\epsilon_2
                          & -a_{23} & \cdots  & -a_{2n}               \\
 -\epsilon_3\hfill\vline  & -a_{31} & -a_{32} & \sigma_3+\epsilon_3
                                              &         & -a_{3n}     \\
            \hfill\vline  &         & \vdots  &
                                    & \ddots  & \vdots                \\
 -\epsilon_n\hfill\vline  & -a_{n1} & -a_{n2} & -a_{n3}
                                    & \cdots  & \sigma_n+\epsilon_n
     \end{bmatrix}
\label{pd2}
\end{equation}
Notice that this matrix has the property that its row-sums are zero.
We now will now prove by induction on $n$ that the submatrix \(\det
\tilde K(1,\ldots,n;1,\ldots,n) = \det A > 0\).

When $n=1$, $K$ is of the form 
\begin{displaymath}
 \tilde K = \begin{bmatrix} 0 & 0 \\ -\epsilon_1 & \epsilon_1 \end{bmatrix}
\end{displaymath}
where \(A = [\epsilon_1]\), and \(\epsilon_1 > 0\), since there must
be a directed edge from the interior node to the boundary node.
Hence, \(\det A > 0\).  Now, assume that for when a matrix of size
\((n-1)\times(n-1)\) is of the form (\ref{eq:pd1}), then its
determinant is greater than zero.

Now, consider a matrix of the form (\ref{eq:pd1}) where there are $n$
interior nodes.  Perform Gaussian elimination on the entry \(\sigma_n
+ \epsilon_n\) of the augmented matrix $\tilde K$.  This produces a
new matrix, $\tilde K'$.
\begin{displaymath}
 \tilde K' = \begin{bmatrix}
  0         \hfill\vline  & 0       &       0   &    0  &       &   0 \\ \hline
 -\epsilon_1'\hfill\vline & \sigma_1'+\epsilon_1' 
                          & -a_{12}' & -a_{13}'         &       & 0   \\
 -\epsilon_2'\hfill\vline & -a_{21}' & \sigma_2'+\epsilon_2'  
                          & -a_{23}' & \cdots   & 0                   \\
 -\epsilon_3'\hfill\vline & -a_{31}' & -a_{32}' & \sigma_3'+\epsilon_3'
                                                &               & 0   \\
             \hfill\vline &          & \vdots   &
                                     & \ddots   & \vdots              \\
 -\epsilon_n \hfill\vline & -a_{n1}  & -a_{n2}  & -a_{n3}
                                     & \cdots   & \sigma_n+\epsilon_n
     \end{bmatrix}
\end{displaymath}
In this matrix, \(-a_{ij}' = -a_{ij} -
\frac{a_{in}a_{nj}}{\sigma_n+\epsilon_n} \leq -a_{ij}\).  Hence, if
\(a_{ij}\) is nonzero, then $a_{ij}'$ is also nonzero.  Similarly, if
$a_{in}$ and $a_{nj}$ are nonzero, then $a_{ij}'$ is nonzero.  Thus,
the elimination of node $n$ in this manner does not eliminate any
paths in the graph.  Therefore, the submatrix consisting of the rows
and columns \((1,2,\ldots,n-1)\) of $\tilde K'$ is a matrix of the
form (\ref{eq:pd1}) and hence, by our inductive assumption, its
determinant is greater than zero.  The cofactor expansion of $A$ along
the last column yields
\begin{displaymath}
 \det A = \det \tilde K(\mathcal{I};\mathcal{I})
        = (\sigma_n + \epsilon_n)
          \cdot \det \tilde K'(1,2,\ldots,n-1;1,2,\ldots,n-1)
\end{displaymath}
Both terms in the final product are greater than zero, so \(\det A > 0\)

We now verify that the principal minors of $A$ satisfy the same
hypothesis as $A$.  Let \(J \subseteq \mathcal{I}\), and $A(J;J)$ be a
principal minor of $A$.  Let $\tilde G_J$ be the network constructed
from the interior nodes $J$, and one boundary node (with index zero).
We will show that if there was a directed path from \(j_i \in J\) to
the boundary of $\tilde G$ through $\mathcal{I}$, then there is a
directed path from $j_i$ to the boundary of $\tilde G_J$ through $J$.
We rewrite each diagonal entry of $A(J;J)$
\(\sigma_{j_i}+\epsilon_{j_i} = \hat\sigma_{j_i}+\hat\epsilon_{j_i}\),
where $\hat\sigma_{j_i}$ is the sum of the off-diagonal terms of the
$j_i^{\rm th}$ row of $A(J;J)$.

Given a node $j_i$, Let $s$ be a step in the path from $j_i$ to the
boundary of $\tilde G$ through $\mathcal{I}$.  If $s$ goes from an
element of $J$ to the boundary of $\tilde G$, this step also goes to
the boundary of $\tilde G_J$ .  If $s$ is from a node in $J$ to another
node in $J$, then this portion of the path will also be unaffected.
If $s$ is from a node in $J$ through an interior node that is not in
$J$, then \(\hat\epsilon_{j_i} > \epsilon_{j_i}\).  Thus, node $j_i$ is
now connected directly to the boundary.

Thus, every node \(j_i \in J\) has a directed path to the bounday
through $J$, and hence $A(J;J)$ is of the same form as $A$.
\end{proof}

\begin{thm}
Let $G$ be a directed conductivity network with a circular planar
graph.  Suppose that \(P = (p_1,\ldots,p_k)\) and \(Q =
(q_1,\ldots,q_k)\) are disjoint subsets of the boundary of $G$.  Also,
suppose that the sequence of boundary nodes
\((p_1,\ldots,p_k,q_k,\ldots,q_1)\) is in circular order.  Finally,
suppose that for every interior node, there is a directed path to the
boundary.  Then \((-1)^{k}\det\Lambda(P;R) > 0\) if and only if there
is a directed connection from $P$ to $R$ through $G$.
\end{thm}

\begin{proof}
For any square matrix $M$ of the form
\begin{displaymath}
 M = \begin{pmatrix} M_1 & M_2 \\ M_3 & M_4  \end{pmatrix}
\end{displaymath}
where $M_4$ is a non-singular principal submatrix of $M$.  Then 
\begin{displaymath}
 \det M = \det(M/M_4)\cdot \det M_4
\end{displaymath}
Setting \(M = K(P\cup\mathcal{I};R\cup\mathcal{I})\), and \(M_4 =
K(\mathcal{I};\mathcal{I})\), we have
\begin{displaymath}
   \det K(P\cup\mathcal{I};R\cup\mathcal{I})
 = \det \Lambda(P;R) \cdot \det K(\mathcal{I};\mathcal{I})
\end{displaymath}
By Lemma \ref{lem:pos} \(\det K(J;J) > 0\) for \(J \subseteq
\mathcal{I}\).  Therefore, if we compute the determinant of
\(K(P\cup\mathcal{I};R\cup\mathcal{I})\) by (\ref{eq:Kexpansion}),
every weight determinant of the form \(D[\mathcal{B}\cup
J;\mathcal{B}\cup J]\) in that expression will be greater than zero.
In addition, when $G$ is restricted to be circular planar, every
nonzero term in the expression (\ref{eq:Kexpansion}) will have the
sign $(-1)^k$.  Furthermore, \(\det
K(P\cup\mathcal{I};R\cup\mathcal{I}) = 0\) if and only if there is no
connection from $P$ to $R$ through $G$.  Hence, \((-1)^{k}\det
\Lambda(P;R) > 0\) if and only if there is a connection from $P$ to
$R$.
\end{proof}

\begin{thebibliography}{10}
 \bibitem{C-M} Curtis, Edward B., and James A. Morrow.
 \emph{Inverse Problems for Electrical Networks}.

 \bibitem{O} Oberlin, Richard.  
 \emph{Discrete inverse problems for Schr\"odinger and Resistor networks}.

 \bibitem{B-C} Blunk, Mark, and Sam Coskey.
 \emph{Vertex Conductivity Networks}.
\end{thebibliography}
\end{document}









