\documentclass{amsart}
\title{Relation between Vertex and Edge Conductivities}
\author{Daniel Rim}
\date{July, 2003}

% Check if we are compiling under latex or pdflatex, and include the
% appropriate graphics package
\ifx\pdftexversion\undefined
  \usepackage[dvips]{graphicx}
\else
  \usepackage[pdftex]{graphicx}
\fi

\usepackage{amsmath}
\usepackage{amssymb}

% Define the theorem environments
\usepackage{amsthm}
\newtheorem{theorem}{Theorem}[section] % numbered like the section
\newtheorem{lemma}[theorem]{Lemma} % numbered like the theorems
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition} % styled differently... not italicized
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}

% Let \sign show roman-style characters in math mode
\newcommand{\sign}{\mathop{\mathrm{sign}}}

%\raggedbottom % Makes the bottom margin more flexible (helpful for pictures)
\begin{document}

\begin{abstract}
 
Vertex conductivities and Edge conductivities could be defined differently on one graph. This paper investigates the relationship between these two kinds of conductivities. The possibility of using this relationship in recovery is discussed.
\end{abstract}

\maketitle

\section{Introduction}
Vertex conductivities is a function defined on vertices and can be used to define the current flow out of a vertex. For given edge there is a different conductivity corresponding to the direction of the edge. The Kirchhoff matrix $K$ is defined so that \(K\cdot u = I(u)\), where I is the current flow and u is the potential at each vertex. This paper defines the Kirhhoff matrix K as the following,

\begin{displaymath}
K_{ij} = \begin{cases}
  0                     & j \neq i,\  j \not\in \mathcal{N}(i) \\
  -\gamma_j              & j \neq i,\  j     \in \mathcal{N}(i) \\
  \sum_{n\neq i}K_{in} & j =    i 
 \end{cases}
\end{displaymath}

where $\mathcal{N}(i)$ represents the neighboring nodes. 
We find the response matrix $\Lambda$ as in the case of edge conductivities, by taking Schur Complement of the Kirhhoff matrix. 

We define the current into the node p to be the current flowing out of the node,

\begin{equation}
I_{p}(u)=\sum_{q \in \mathcal{N}(p)}(u_{p}-u_{q})\gamma(q)
\end{equation}

The inverse problem is that given the response matrix $\Lambda$, we are to recover the vertex conductivities of the network.

In the vertex conductivity networks Kirhhoff law is defined as following, 

\begin{equation}
I_{p}(u)=\sum_{q \in \mathcal{N}(p)}(u_{p}-u_{q})\gamma(q)=0 
\end{equation}

for the interior node p. This is not physically equivalent to Kirhoff's law for the edge conductivity networks, and we will see that this discrepancy makes trouble in finding out the relationship between the vertex and edge response matrices. 

The first idea that came up was that we could draw a medial graph of a edge conductivity network and assign the vertex conductivities with the edge conductivities at the "interior vertices" of the medial graphs. For example, for the circular planar network given in figure(1) has its medial graph as an associated vertex conductivity network.

\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{medial_vert.eps}
\caption{Assigning vertex conductivities using edge graph \label{some_label}}
\end{center}
\end{figure}



 

If one could find some kind of relationship between the response matrix of those two graphs and if there is a equation that gives correct answers to circular planar but does not work on any other network, than that equation can be used as a test for circular planarity. However, the task seems to be extremely complicated if not impossible. 

\section{Algebraic Relation between Vertex and Edge Conductivities}
Another way to approach this is to consider the same network and think of it as consisting of both edge conductivity and vertex conductivity networks. The task would be to find the edge conductivities given vertex conductivities or vice versa. We consider the case in which the vertex conductivities $\gamma(p)$, $\gamma(q)$ and the conductivity $\gamma_{pq}$ of edge connecting those two vertex is the following.

\begin{equation}
\gamma(p)+\gamma(q)=\gamma(pq)
\end{equation}


With the potential difference between two nodes p and q, and the conductivities at node p and q, we can find the net current that flows from p to q by calculating the current flowing in one way and the current flowing in the other way. current flowing into p and q are going to be 
\begin{equation*}
\begin{split}
i(p)=\gamma(q)(u(p)-u(q))\\
i(q)=\gamma(p)(u(q)-u(p))
\end{split}
\end{equation*}

So the net current flowing from p to q is going to be 

\begin{equation*}
\begin{split}
i_{net}=i(p)-i(q)=\gamma(q)(u(p)-u(q))-\gamma(p)(u(q)-u(p))\\
=(\gamma(p)+\gamma(q))(u(p)-u(q))
\end{split}
\end{equation*}

In this equation we can see that this is equivalent to a edge network with conductivity $\gamma(p)+\gamma(q)$. It is also equivalent to a network with parralel connection that has conductivities $\gamma(p)$ and $\gamma(q)$. If we consider the network physically, in the case where u(p)$<$u(q), there is no way the current is going to flow from p to q. In the directed graph, the two currents flowing in opposite direction on the same network always have opposite signs. 

If (2) is true, then sometimes we can set up a system of linear equations and solve it to get vertex conductivities from edge conductivities. However there are many cases when the same edge conductivities give infinitely many vertex conductivities and sometimes there is no vertex conductivities that would give the edge conductivities at all. 

For example, for the following network, given the edge conductivities,

\begin{figure}
\begin{center}
\includegraphics[height=7cm]{edge_vertex1.eps}
\caption{Finding the corresponding edge conductivities from vertex conductivities \label{still_another_label}}
\end{center}
\end{figure}

we can set up following equations. 

\begin{equation*}
\begin{split}
e+f=a\\
f+g=b\\
g+h=c\\
f+h=d\\
\end{split}
\end{equation*}

In this case we can find the exact values for e,f,g,h. 
\begin{equation*}
\begin{split}
e=-\frac{1}{2}d+\frac{1}{2}c-\frac{1}{2}b+a\\
f=\frac{1}{2}d-\frac{1}{2}c+\frac{1}{2}b\\
g=-\frac{1}{2}d+\frac{1}{2}c+\frac{1}{2}b\\
h=\frac{1}{2}d+\frac{1}{2}c-\frac{1}{2}b 
\end{split}
\end{equation*}

However, even though the relationship between the edge and vertex conductivites is one-to-one, it is not recoverable in the edge case, whereas it is recoverable in the vertex case as shown in [1]. The reason could be that we have more information in the vertex response matrix than the edge response matrix, since in the edge response matrix all the information we need is on the upper triangular part of the matrix, whereas in vertex response matrix we need the whole matrix to recover the network. But we can sense the bleak situation where we glimpse the fact that even though the conductivies might have one-to-one relationship, even the response matrix might have one to one relationship, and still it is possible that we are able to recover in one case, but not the other, or might be able to recover in both cases, or, of course, not be able to recover in both cases. In other words, it might be possible that the recoverability relation between those two might just be arbitrary.


There are cases when we don't have enough equations or even if we do those equations would not give the explicit answers. Take, for example, a Y network. 

\begin{figure}
\begin{center}
\includegraphics[height=7cm]{Y.eps}
\caption{vertex conductivity in Y-network \label{some_other_label}}
\end{center}
\end{figure}

Here, we don't have enough equation to solve for e,h,f,g. 
\begin{equation*}
\begin{split}
e+h=a\\
h+f=b\\
h+g=c\\
\end{split}
\end{equation*}
Usually we just need one more piece of information to make it possible to figure out the vertex conductivities. Suppose we could somehow measure any one of e,h,f,g. Then we could certainly solve for the rest of the vertex conductivities. Note that we cannot use Y-$\Delta$ transformation to figure out in this case because we have no information as to how do the vertex conductivities vary in this transformation. There has been an attempt to find some kind of equivalent network for vertex conductivity in [3], but it seems that the attempt was unsuccessful. 

Conclusion is that even after we establish the relationship between vertex and edge conductivities it is not easy to move back and forth, mainly because in many cases those relationship is not one-to-one, and even if it is, we still do not have concrete relationship between the response matrices. There are cases when we end up with more equations than we need, and in that case the equation won't have answers unless we can toss out enough equations that we don't need by their linear dependence.

Consider the next case where both vertex and edge conductivities are recoverable. 

\begin{figure}
\begin{center}
\includegraphics[height=7cm]{lattice.eps}
\caption{vertex and edge conductivity in lattice\label{whatevers}}
\end{center}
\end{figure}

In this case we have enough equations. And yet it is not possible to find the corresponding vertex conductivites given the edge conductivities. 

\begin{equation*}
\begin{split}
\gamma(1)+\gamma(2)=a\\
\gamma(2)+\gamma(6)=b\\
\gamma(3)+\gamma(4)=c\\
\gamma(4)+\gamma(5)=d\\
\gamma(5)+\gamma(6)=e\\
\gamma(5)+\gamma(9)=g\\
\gamma(4)+\gamma(8)=f\\
\gamma(7)+\gamma(8)=h\\
\gamma(8)+\gamma(9)=i\\
\gamma(9)+\gamma(10)=j\\
\gamma(8)+\gamma(11)=k\\
\gamma(9)+\gamma(12)=l\\
\end{split}
\end{equation*}

It turns out when written in the matrix form A$\gamma$=e, one of the rows in A becomes 0 after carrying out the Gaussian Elimination, and thus det(A)=0.

In this case, however, if one can provide more information, then one might be able to make the transition between edge conductivity and vertex conductivity case. Say if we know one of the vertex conductivities. Then we can find the rest if we know the edge conductivities. 
Consider a case where $\gamma(7)$ is given along with all the edge conductivities. Then $\gamma(8)$=h-$\gamma(7)$, $\gamma(4)$=f-h+$\gamma(7)$, $\gamma(9)$=i-h+$\gamma(7)$, and $\gamma(5)$=d-f+h-$\gamma(7)$. Notice that g=$\gamma(9)$+$\gamma(5)$=d-f+i has to be satisfied for this network to have a solution. 

There is another similar case. Consider the following top hat graph. 

\begin{figure}
\begin{center}
\includegraphics[height=4cm]{hat.eps}
\caption{vertex conductivity in hat-network\label{label2}} 
\end{center}
\end{figure}


\begin{equation*}
\begin{split}
\gamma(1)+\gamma(2)=a\\
\gamma(1)+\gamma(4)=b\\
\gamma(3)+\gamma(4)=d\\
\gamma(4)+\gamma(5)=e\\
\gamma(5)+\gamma(6)=f\\
\gamma(5)+\gamma(2)=c\\
\end{split}
\end{equation*}

The null space for the matrix of this system is generated by [1 1 -1 -1 -1]${^T}$. The dimension of this null space is 1.

Given $\gamma(3)$ along with all the edge conductivities, $\gamma(4)$=f-$\gamma(3)$, $\gamma(5)$=e-f+$\gamma(3)$, $\gamma(1)$=d-f+$\gamma(3)$,and $\gamma(2)$=c-d+f-$\gamma(3)$. Again we need the condition that $\gamma(2)$+$\gamma(5)$=e+c-d=b in order for this network to have infinitely many solutions. Note that if we do have this condition, we would have one to one relation of vertex and edge conductivities if we have one more piece of information, such as one of the vertex conductivities, or one more edge conductivity as in figure (6). Thus we might be able to construct networks that have bijective relation between vertex and edge conductivities from the networks that has no such relation.  In the revised top hat case the relation is going to be like this.

\begin{equation}
\begin{split}
\gamma(1)=\frac{1}{2}f-\frac{1}{2}c-\frac{1}{2}g+a\\
\gamma(2)=-\frac{1}{2}f+\frac{1}{2}c+\frac{1}{2}g\\
\gamma(3)=\frac{1}{2}f+\frac{1}{2}c-\frac{1}{2}g-e+d\\
\gamma(4)=-\frac{1}{2}f-\frac{1}{2}c+\frac{1}{2}g+e\\
\gamma(5)=\frac{1}{2}f+\frac{1}{2}c-\frac{1}{2}g\\
\gamma(6)=\frac{1}{2}f+\frac{1}{2}c-\frac{1}{2}g
\end{split}
\end{equation}

Note that we did not need the edge conductivity b to solve this one to one relation. In other words, as long as we have the relationship e+c-d=b, the edge b is not needed to solve this system, and the vertex conductivities of revised top hat is going to equal the network without the edge conductivity b as in figure (7). We could construct a similar equivalent network in the lattice case as well. We could do this in any network with where there is no bijective correspondense. The number of the edges we need to add is going to vary according to the dimension of the null space. In fact, it is going to correspond to the dimension of the null space. \footnote{We need not restrict ourselves into removing b, we could've removed e, c, or d instead.} 
Also, we can see that all vertex conductivities of figure(6) depend on the value of g, which is the edge conductivity that was newly added. In other words, if we change the value of g, then the vertex conductivities will change just as well. This seems to show that vertex conductivities are not intrinsic, but induced by the corresponding edge conductivities. 
In adding another edge conductivity, we made a recoverable edge graph(the top hat graph is recoverable in the edge case) into a non-recoverable graph. But if we assume that we know the value of the newly added edge conductivity(namely g in this case) it might be possible to have enough information to recover the graph.
Figure(2) and Y-graph has similar relationship. If we add one more edge conductivity to the Y-graph, then we have a one-to-one relation between vertex and edge conductivities. However, figure(2) graph is not recoverable, but Y-graph is recoverable in the edge case. So provided we know the edge conductivity that we add to the Y-graph, it would be possible to find the corresponding vertex conductivities. 
Vertex conductivities change when corresponding edge conductivities are changed, so if we are to modify networks, we have to keep track of added edge conductivities. Adding another edge conductivity may not be useful because the additional information is not given.

\begin{figure}
\begin{center}
\includegraphics[width=7cm]{top_hat_revised.eps}
\caption{Revised Top Hat graph\label{label2}} 
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[width=14cm]{vertex_equi1.eps}
\caption{Two networks with equal vertex conductivity\label{label3}} 
\end{center}
\end{figure}

In this way we might be able to find some networks that would have the same vertex conductivities provided that the edge conductivities satisfy a certain kind of condition.


It seems that given the vertex conductivities, it might be easy to find the corresponding edge conductivities. We can just add the two vertex conductivities to get the edge conductivity in between. However, when it comes to the problem of recoverability, we need the relationship between the response matrix of the vertex case and the edge case, and even if we have the relationship between the response matrices, that might not help in figuring out the recoverabilty relationship.

\section{Relationship between the Kirchhoff Matrices} 

So far I made a conjecture on the relationship between Kirchhoff matrix of the edge and vertex case, which is 

\begin{equation}
K_{edge}=K_{vertex}+(K_{vertex})^T+D
\end{equation}

where D is a diagonal matrix.\footnote{Jaime Lust's paper on directed graphs uses $K_{vert}$ and its transpose in a similar way in order to define Dirichlet norm for directed networks. Lust put $u^TKu+u^TDu$ as Dirichlet norm where D is a diagonal matrix.}
 It would be neat if D wasn't included in the equation, and I made a mistake of leaving it out at first. But since $K_{vertex}$ only has its row sums to 0, D has to be included to fix the diagonal entries. If the second $K_{vertex}$'s column sums were add up to be 0, then we can do away with D. 

D turns out to be

\begin{equation}
D_{ii}=\sum_{n\neq i}K_{ni}-\sum_{n\neq i}K_{in} 
\end{equation}


This equation seems to work because

\begin{displaymath}
(K_{edge})_{ij} = \begin{cases}
  0                     & j \neq i,\  j \not\in \mathcal{N}(i) \\
  -\gamma_{ij}=-\gamma(i)-\gamma(j)              & j \neq i,\  j     \in \mathcal{N}(i) \\
  \sum_{n\neq i}K_{in} & j =    i 
 \end{cases}
\end{displaymath}

whereas the Kirchhoff matrix in the vertex case is

\begin{displaymath}
(K_{vertex})_{ij} = \begin{cases}
  0                     & j \neq i,\  j \not\in \mathcal{N}(i) \\
  -\gamma(i)             & j \neq i,\  j     \in \mathcal{N}(i) \\
  \sum_{n\neq i}K_{in} & j =    i 
 \end{cases}
\end{displaymath}

and its transpose would be
\begin{displaymath} 
(K_{vertex})_{ij}^T = \begin{cases}
  0                     & i \neq j,\  i \not\in \mathcal{N}(j) \\
  -\gamma(j)             & i \neq j,\  i     \in \mathcal{N}(j) \\
  \sum_{n\neq j}K_{in} & i =    j
 \end{cases}
\end{displaymath}


\section{Reponse Matrices}
The relationship between the response matrix of the two conductivities is not easy to show because taking Schur Complement is a complicated task. The response matrix $\Lambda_{vertex}$ for vertex conductivities provides information about the currents flowing through the directed edges that point outward from the boundary nodes, whereas  the response matrix $\Lambda_{edge}$ gives information about the net current flowing out of the boundary nodes. So if there were information about currents flowing through the edge directed into the boundary nodes (say $\Lambda_{vertex}'$) then the following relationship comes about.

\begin{equation}
\begin{split}
\Lambda_{edge}f=\Lambda_{vertex}f-\Lambda_{vertex}'f
\end{split}
\end{equation}

whereas f is the voltage at the boundary nodes.

\begin{equation}
\Lambda_{vertex}-\Lambda_{vertex}'=\Lambda_{edge}
\end{equation}

In a vertex case $\lambda_{ij}$ gives the current flowing out of the boundary node i when the potential at node j is 1 and 0 elsewhere on the boundary. $\lambda'_{ij}$ would give the current flowing into the boundary node i when the potential at node j is 1 and 0 elsewhere. The conjecture is that

\begin{equation}
\begin{split}
\Lambda_{vertex}=K_{vertex}(I,I)\\
\Lambda_{vertex}'=K_{vertex}'(I,I)
\end{split}
\end{equation}

where $K_{vertex}(I,I)$ represents taking the Schur Complement of $K_{vertex}$. However, this seems unlikely to be true.

$K_{vertex}'$ is $K_{vertex}^T$ with its diagonal entries fixed. This would mean that a vertex conductivity network consists of two different edge conductivity networks that is directed in the same way. \footnote{I've tried to confirm the relation between the response matrices out in matlab, but it did not seem to work. I tried the first example in figure(2). It turns out that 
\begin{equation}
\Lambda_{edge}= \begin{pmatrix} 
e+f-\frac{(e+f)^{2}}{e+3f+g+h} & -\frac{(e+f)(g+f)}{e+3f+g+h} & -\frac{(e+f)(h+f)}{e+3f+g+h} \\ 
-\frac{(e+f)(g+f)}{e+3f+g+h} & 2g+f+h-\frac{(g+f)^{2}}{e+3f+g+h} &-h-g-\frac{(g+f)(h+f)}{e+3f+g+h}\\
-\frac{(e+f)(h+f)}{e+3f+g+h} & -h-g-\frac{(g+f)(h+f)}{e+3f+g+h} &2h+g+f-\frac{(h+f)^{2}}{e+3f+g+h} 
\end{pmatrix}
\end{equation}
and 
\begin{equation}
\Lambda_{vertex}= \begin{pmatrix}
f-\frac{fe}{e+g+h} & -\frac{fg}{e+g+h} & -\frac{fh}{e+g+h}\\
-\frac{fe}{e+g+h} & f+h-\frac{fg}{e+g+h} & -h-\frac{fh}{e+g+h}\\
-\frac{fe}{e+g+h} & -g-\frac{fg}{e+g+h} & f+g-\frac{fh}{e+g+h}
\end{pmatrix}
\end{equation} It's hard to see that $\Lambda_{edge}$=$\Lambda_{vertex}$-$\Lambda_{vertex}'$  holds because of the different factors in the denominators. $\Lambda_{vertex}$', turns out to be,
\begin{equation}
\Lambda_{vertex}'=
\begin{pmatrix}
\frac{ef}{e+g+h}-f & \frac{hf}{e+g+h}& \frac{gf}{e+g+h}\\
\frac{ef}{e+g+h} & \frac{hf}{e+g+h}-f & \frac{gf}{e+g+h}\\
\frac{ef}{e+g+h} & h+\frac{hf}{e+g+h} & \frac{gf}{e+g+h-f-h}
\end{pmatrix}
\end{equation} Note that $\Lambda_{vertex}'$ is -$\Lambda_{vertex}$ with h and g switched. We can make a conjecture that $\Lambda_{vertex}'$ is going to be negative of $\Lambda_{vertex}$ with the connected boundary vertices switched. Problem arises, of course, when more than 2 vertices are connected. The main problem, however, is that $\Lambda_{edge}$ does not equal $\Lambda_{vertex}$-$\Lambda_{vertex}'$. This problem comes from the fact that we have defined Kirhoff's law differently for the edge and vertex conductivity network.}

Given $\Lambda_{edge}$, there might be some way to construct two different corresponding $\Lambda_{vertex}$, and if those two vertex conductivites are recoverable, and yet give different corresponding edge conductivities, then the edge conductivity network would not be recoverable. However, it is still difficult to construct $\Lambda_{vertex}$ from $\Lambda_{edge}$, and even if we could construct two different $\Lambda_{vertex}$, it might be the case that a lot of those would give the same edge conductivities, thereby rendering the method useless. The reason for this is that if you consider the top hat graph, there are infinitely many vertex conductivities that would give the same edge conductivities, and it seems reasonable to assume that infinitely many vertex response matrices would give the same edge response matrix. Another difficulty is that vertex conductivity network is much harder to recover than the edge case and of course, the conductivities would have to have one to one relationship.

There might be a case when there is one-to-one relationship for the conductivities, and yet the response matrices might not have such relationship. It would be interesting to see if this case exists.

We could try to go the other way. Given $\Lambda_{vertex}$, we might be able to find a way to construct corresponding $\Lambda_{edge}$, and then recover that and work your way back to the vertex conductivites. Again the difficulty is that we do not know if the conductivity relation is 1 to 1, and even if it is, it does not tell us much about the recoverability of the vertex network.

\section{Further Problem} 
If this problem is going to be further pursued, then it would be interesting to see in what cases the vertex and edge conductivities relation is going to be bijective, and if it is bijective, we could look for conditions that would answer the questions of recoverability of the edge or vertex conductivities. Also, we would have to fully construct the relationship between the two response matrices. Because of physically different way of defining Kirhoff's law, it seems that one would have to construct a completely different definition of Kirhoff matrix, or the current. 

There might be certain kind of operations that would lead to a neat relationship between vertex and edge case. Even though this will not be a complete inverse problem, we would need to provide ourselves with some of the information we need to make the transition and that transition might lead us somewhere, as in the case of Y-graph with one edge conductivity added.

Another problem that may concern us is that even though we cannot find the exact relationship between $\Lambda_{vertex}$ and $\Lambda_{edge}$, we might be able to find some kind of relationship between the edge conductivity network and the vertex conductivity network as the network grows larger and larger. So far the only relationship we have is that 
\begin{equation}
|K_{edge}-K_{vertex}|=K_{vertex}^T+D
\end{equation}
whereas D is a diagonal matrix. But if we could find some kind of limiting relation that would make the vertex conductivity to approach edge conductivities, then we might be able to find something useful when we're studying a sequences of networks that are converging to continuous case.


\begin{thebibliography}{99}
\bibitem{paper}
Blunk, Mark, and Sam Coskey. Vertex Conductivity Networks.\\
\bibitem{paper}
Oberlin, Richard. Discrete inverse problem for Schroedinger and Resister networks.\\
\bibitem{paper}
Lust, Jamie. Directed Graphs
\end{thebibliography}
\end{document}