Positive graph-diffusion semigroup and Euler maps

If $I=\mathrm{\varnothing }$, all free-state assertions are vacuous, so assume $I\mathrm{\ne }\mathrm{\varnothing }$. Put $Q=-L{M}^{-1}$. For distinct free vertices $i,j$, $Q_{ij}=-L_{ij}\mathrm{/}{m}_j\ge 0$ by [F1]. If $D=\mathrm{\varnothing }$, [F1] says that $\mathbf{1}$ is constant on every positive-conductance component, so $L\mathbf{1}=0$; symmetry gives ${\mathbf{1}}^{\mathsf{T}}L=0$. Thus $Q$ has zero column sums and is a finite column generator by [F2]. If $p_0\ge 0$ is nonzero, let $s={\mathbf{1}}^{\mathsf{T}}{p}_0>0$ and $\pi =p_0\mathrm{/}s$. By [F2], $e^{tQ}\pi$ is a probability vector, so it is entrywise nonnegative; multiplying by $s$ proves $e^{tQ}{p}_0\ge 0$. If $p_0=0$, its image is zero.

If $D\mathrm{\ne }\mathrm{\varnothing }$, then $Q$ has nonnegative off-diagonal entries and diagonal entries $Q_{ii}=-L_{ii}\mathrm{/}{m}_i$. Put $\lambda ={\max }_{i\in I}{L}_{ii}\mathrm{/}{m}_i\ge 0$. If $\lambda =0$, then $L_{ii}={\sum }_{e\text{ incident to }i}{c}_e=0$ for every free vertex. Since each $c_e\ge 0$, every conductance incident to a free vertex is zero; hence each free row of $L_D$ vanishes, $Q=0$, and its exponential is the identity. If $\lambda >0$, every entry of $Q+\lambda I$ is nonnegative. For $t\ge 0$, each term of the matrix series $e^{t(Q+\lambda I)}={\sum }_{k\ge 0}{t}^k(Q+\lambda I{)}^k\mathrm{/}k!$ is entrywise nonnegative. By [F3], since $-\lambda tI$ commutes with $t(Q+\lambda I)$, $e^{tQ}=e^{-\lambda tI}{e}^{t(Q+\lambda I)}=e^{-\lambda t}{e}^{t(Q+\lambda I)}$ is entrywise nonnegative.

The diagonal entries of $E_F(\tau )$ are $1-\tau L_{ii}\mathrm{/}{m}_i$, and its off-diagonal entries are $-\tau L_{ij}\mathrm{/}{m}_i\ge 0$ by [F1]. Thus all entries are nonnegative exactly when each diagonal is nonnegative, which is exactly $\tau \le m_i\mathrm{/}{L}_{ii}$ for every $i$ with $L_{ii}>0$. If a diagonal is negative, applying the step matrix to the corresponding coordinate vector produces a negative coordinate, so the condition is sharp.

The mass state $p=Mu$ satisfies $p^{\mathrm{\prime }}=Qp$ for the homogeneous network equation. Its solution is $p(t)=e^{tQ}p(0)$. Since $M$ and $M^{-1}$ are entrywise positive diagonal matrices, $u(t)=M^{-1}{e}^{tQ}Mu(0)=e^{-t{M}^{-1}L}u(0),$ where the second equality follows term by term from the matrix exponential series applied to the similarity $M^{-1}QM=-M^{-1}L$. Steps 1.1–1.2 therefore prove positivity of $S_D(t)$ for both boundary cases.

Let $y\ge 0$ and solve $(M+\tau L)x=My$. The matrix is symmetric positive definite because for nonzero $x$, $x^{\mathsf{T}}(M+\tau L)x\ge {\sum }_i{m}_i{x}_i^2>0$ by [F1]; hence the solve exists uniquely. If $x_k<0$ is a minimum coordinate, extend $x$ by zero on $D$. The edge formula for $(Lx{)}_k$ is a sum of terms $c_e(x_k-{\bar{x}}_{\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}(e)})$, each nonpositive because every free neighbor has value at least $x_k$ and every Dirichlet value is zero. Therefore $((M+\tau L)x{)}_k=m_k{x}_k+\tau (Lx{)}_k<0$, contradicting $(My{)}_k=m_k{y}_k\ge 0$. Thus $x\ge 0$ and backward Euler is positivity preserving.