0. Contents
- Notations
- Ohm’s Law
- Problem 1
- Problem 2
- Problem 3 & Verify
- Application in Complex Circuit using Python
- Related Theorems - Thompson’s Principle & Rayleigh’s Monotonicity
1. Notations
Between a and b
- \( v \): Voltage (= \( p_a - p_b \))
- \( w \): Current
- \( r \): Resistance
- \( p \): Potential
- \( c \): Net Current
2. Ohm’s Law
\[ v = rw \quad \text{(Ohm’s Law)} \]
Let’s express Ohm’s Law everywhere.
- Current \( w \in \mathbb{R}^m \) → Net Current \( \delta w \in \mathbb{R}^n \)
- Potential \( p \in \mathbb{R}^n \) → Voltage \( \delta^T p \in \mathbb{R}^m \)
Define \( \delta \) as the Incidence Matrix:
\[ (\delta)_{v,e} = \begin{cases} -1 & \text{if } v = v_i \\ +1 & \text{if } v = v_j \\ 0 & \text{otherwise} \end{cases} \]
where \( e = (v_i, v_j) \) and \( i < j \).
Assume all resistances are 1:
\[ v = rw = w \]
Then,
\[ \delta^T p = w \]
3. Problem 1
Q. Given net current, find the potential.
\[ c = \delta w = \delta \delta^T p = Lp \]
We must solve:
\[ Lp = c \]
Observation:
\[ Lx \perp \mathbf{1} \]
Therefore, if
\[ c^T \mathbf{1} = 0 \]
(i.e., total net current is zero), then the system is solvable.
Example
Inject 1 unit of current at \( S \), extract 1 unit at \( T \):
\[ c = \begin{bmatrix} 0 \\ \vdots \\ 1 \\ \vdots \\ -1 \\ \vdots \\ 0 \end{bmatrix} \]
Since \( c^T \mathbf{1} = 0 \),
\[ Lp = c \]
\[ p = L^+ c \]
where \( L^+ \) is the Moore–Penrose pseudoinverse.
4. Problem 2
Q. Compute the effective resistance between two vertices.
Set \( c \), solve \( Lp = c \).
\[ \text{Effective Resistance} = \frac{\text{Potential Difference}}{\text{Current}} = \frac{p_S - p_T}{1} \]
5. Problem 3
Q. What if edges have different resistances?
Let
\[ R = \begin{bmatrix} r_1 & & 0 \\ & \ddots & \\ 0 & & r_m \end{bmatrix} \]
\[ \delta^T p = Rw \quad \Longleftrightarrow \quad w = R^{-1} \delta^T p \]
Define:
\[ L_r = \delta R^{-1} \delta^T \]
Then:
\[ c = \delta w = \delta R^{-1} \delta^T p = L_r p \]
Solve:
\[ L_r p = c \]
Verification Example
Given circuit:
- Edge (1,2) = 2Ω
- Edge (2,3) = 3Ω
Inject 1 unit at 1, extract 1 at 3.
Solving \( L_r p = c \) via Gaussian elimination gives:
\[ p = \begin{bmatrix} t+5 \\ t+3 \\ t \end{bmatrix} \]
Thus,
\[ R_{1,3} = 5\Omega \]
6. Application in Complex Circuit using Python
Cube Graph
- Vertex: 8
- Edge: 12
- Resistance: All 1Ω
Core Functions
def transpose(A):
return [[A[i][j] for i in range(len(A))] for j in range(len(A[0]))]
def matmul(A, B):
if isinstance(B[0], (int, float)):
B = [[x] for x in B]
AB = [[0 for _ in range(len(B[0]))] for _ in range(len(A))]
for i in range(len(A)):
for j in range(len(B[0])):
for k in range(len(B)):
AB[i][j] += A[i][k] * B[k][j]
return AB
def solve_least_squares(A, b):
AT = transpose(A)
ATA = matmul(AT, A)
ATb = matmul(AT, b)
n = len(ATA)
Ab = [ATA[i] + ATb[i] for i in range(n)]
for i in range(n):
factor = Ab[i][i]
for j in range(i, n+1):
Ab[i][j] /= factor
for k in range(n):
if k == i:
continue
factor = Ab[k][i]
for j in range(i, n+1):
Ab[k][j] -= factor * Ab[i][j]
x = [[Ab[i][-1]] for i in range(n)]
return x
Cube Construction
nodes = [v for v in range(0,8)]
edges = [(0,1),(0,3),(0,4),(1,2),(1,7),
(2,3),(2,6),(3,5),(4,5),(4,7),
(5,6),(6,7)]
n = len(nodes)
m = len(edges)
D = [[0 for _ in range(m)] for _ in range(n)]
for j,(u,v) in enumerate(edges):
if u < v:
D[u][j] = -1
D[v][j] = 1
else:
D[v][j] = -1
D[u][j] = 1
L = matmul(D, transpose(D))
c = [0 for _ in range(n)]
c[0] = 1
c[1] = -1
p = solve_least_squares(L, c)
print("Potential is :", p)
a, b = map(int, input("Input Two Vertices: ").split())
print(f"Resistance Between {a} and {b} is : {abs(p[a][0] - p[b][0])}")
Example Output:
Potential is :
[[0.26], [-0.32], [-0.11], [0.05],
[0.05], [0.01], [-0.07], [-0.11]]
Input Two Vertices: 0 1
Resistance Between 0 and 1 is : 0.58 = 7/12 (verified)
7. Related Theorems
Thompson’s Principle
Let \( w \) be any unit flow from \( s \) to \( t \).
\[ \mathcal{E}(w) \ge R_{s,t} \]
The electrical flow minimizes energy.
Rayleigh’s Monotonicity
If resistances increase on edges, effective resistance cannot decrease.
References
- Lorenzo Orecchia (2015). Lecture 7: Effective Resistance.
- Daniel A. Spielman (2010). Effective Resistance.
- Daniel A. Spielman (2010). Harmonic Functions on Graphs, Three Ways.
- Don Sheehy Lectures (2020). GTAC 12.1: Laplacians and Electricity.
- Don Sheehy Lectures (2020). GTAC 12.3: Matrix Invariants.
- Don Sheehy Lectures (2020). GTAC 13.1: Solving Sub-Laplacian Systems.
- Wolfram MathWorld (n.d.). Dodecahedral Graph.