Consider a $m\times n$ grid of one-Ohm resistors. What is the effective resistance of any given edge? I understand how to do the case $m=2$ inductively using the series and parallel laws, but I get stuck in breaking apart the grid for $m,n>2$ to allow for the application of those rules. There seem to be good considerations of the infinite grid (such as this physics.SE answer), but I am specifically interested in a finite grid. Is there a way to truncate the some infinite series arising in the infinite grid case to give the answer for the finite case?
-
$\begingroup$ By 'any given edge' do you mean "between any two given points"? (That is: If I inject a 1-amp current at one point it and it all comes out at another, what is the voltage difference?) This has been considered in the literature previously, e.g., www2.ece.rochester.edu/users/friedman/papers/… $\endgroup$– SemiclassicalCommented Jun 1, 2023 at 13:57
-
$\begingroup$ I will also note the following Wikipedia entry: en.wikipedia.org/wiki/Resistance_distance. (Whether this is useful computationally is another matter...) $\endgroup$– SemiclassicalCommented Jun 1, 2023 at 14:02
-
$\begingroup$ Sure, that would be sufficient, but what I am most interested in is the effective resistance of just the edges (so adjacent vertices, the ones connected by the resistors themselves). Of course if there was a formula for any pair of vertices on the grid, I would gladly just specialize to the edge case, but it's possible that there is some exploitable symmetry for the case of the edges themselves. I will take a look at this paper, thank you for linking it. $\endgroup$– zjsCommented Jun 1, 2023 at 14:02
-
$\begingroup$ @Semiclassical yes unfortunately the wikipedia page doesn't seem to have the tools to handle this kind of graph. $\endgroup$– zjsCommented Jun 1, 2023 at 14:08
1 Answer
While I can't provide an analytical answer, I can show how to compute these distances using Mathematica. The Wikipedia page for resistance distance supplies the following definition:
On a graph $G$, the resistance distance $\Omega_{i,j}$ between two vertices $v_i$ and $v_j$ is $$\Omega_{i,j}:=\Gamma_{i,i}+\Gamma_{j,j}-\Gamma_{i,j}-\Gamma_{j,i},\text{ where } \Gamma = \left(L + \frac{1}{|V|}\Phi\right)^+,$$ with $^+$ denoting the Moore–Penrose inverse, $L$ the Laplacian matrix of $G$, $|V|$ is the number of vertices in $G$, and $\Phi$ is the $|V|\times |V|$ matrix containing all $1$s.
(I will not attempt to prove the equivalence of this definition to the physical one, but I've checked its efficacy for a few different cycle graphs.) While this doesn't itself lead to a simpler closed-form expression for resistance in a grid graph, this is sufficient to calculate the matrix $\Omega$ in Mathematica:
{m,n}={5,6};v=m*n;
g=GridGraph[{m,n}];
G=Transpose[Inverse[N[KirchhoffMatrix[g]+1/v]]]; (* aka the Gamma matrix *)
Clear[R];R[i_,j_]:=R[i,j]=G[[i,i]]+G[[j,j]]-G[[i,j]]-G[[j,i]]; (* aka the Omega matrix*)
(Note that Mathematica refers to the graph Laplacian as the Kirchoff matrix, and that scalar addition acts element-wise on matrices.) As an example, suppose we want one vertex to be the top-right corner of a 5-by-6 grid. Taking into account index conventions that I don't entirely follow, this requires $m=5,n=6,i=26$. So we take the 6th row of $\Omega$ (the R-array in the code) and reshape to get a 5-by-6 array:
ArrayReshape[Array[R,{v,v}][[26]],{n,m}] //Transpose //MatrixForm
0.698639 0.794557 1.04434 1.31814 1.68018 0.
0.563464 0.893328 1.15266 1.43951 0.659125 0.766115
0.961786 1.15983 1.4069 1.07386 1.02159 1.11488
1.25945 1.48398 1.40347 1.273 1.30368 1.42064
1.64818 1.78479 1.56339 1.55515 1.67139 1.96114
Thus the effective resistances for the edges at the upper-right corner are 1.66018 and 0.766115 respectively. This can be graphed using the ArrayPlot
command (or MatrixPlot
depending on your taste):
ArrayReshape[Array[R,{v,v}][[26]],{n,m}] //Transpose //ArrayPlot
Note that the resistance rises monotonically as one moves away from the source vertex, as it should if resistance is a valid distance.
One additional caveat: while the above code is tidy and generalizes to other graphs, that doesn't mean it's at all optimized. In particular it doesn't scale well with the number of vertices: a 50-by-50 graph takes about 1.3 seconds in Mathematica (via Wolfram Cloud), while a 56-by-56 graph takes about twice as long. Moreover, the matrix $L+\Phi/|V|$ appears to be ill-conditioned for large grids and so Inverse
ceases to be effective. So the above implementation is likely only satisfactory if the graph is not especially large.
-
$\begingroup$ Thanks. One comment on speed: Mathematica's
Inverse
method is seemingly much faster thanPseudoInverse
, and since the graph here will always be connected,Inverse
is adequate since adding the $\Phi$ term makes the eigenvalue of the trivial eigenspace be nonzero, thus making the matrix to be (pseud)inverted actually properly invertible. $\endgroup$– zjsCommented Jun 1, 2023 at 15:49 -
$\begingroup$ @zjs After some testing, I entirely agree. (This was partly occluded initially due my initial code accidentally forcing Mathematica to compute the inverse symbolically rather than numerically. The code runs much faster now.) $\endgroup$ Commented Jun 1, 2023 at 16:10