Anchored graph-harmonic extensions are unique and obey a maximum principle

If $U=\mathrm{\varnothing }$, then $B=V$ and the affine set of extensions contains only $f=y_B$. It is therefore the unique minimizer; the maximum and minimum assertions over $U$ are vacuous, and the one-hot boundary rows are in ${\mathrm{\Delta }}_C$.

Suppose $U\mathrm{\ne }\mathrm{\varnothing }$ and put $M=L_{UU}$. For nonzero $v\in {\mathbb{R}}^U$, extend $v$ by zero on $B$ to $\tilde{v}\in {\mathbb{R}}^V$. By [F3], $v^{T}Mv={\tilde{v}}^{T}L\tilde{v}=\frac{1}{2}{\sum }_{i,j}{w}_{ij}({\tilde{v}}_i-{\tilde{v}}_j{)}^2$. If this sum were zero, every positive-weight edge would have equal endpoint values, so $\tilde{v}$ would be constant on each support component. Every component meeting $U$ meets $B$, where $\tilde{v}=0$, forcing $v=0$, a contradiction. Thus $M$ is positive definite; it is symmetric as a principal block of the symmetric matrix $L$.

By [F5], $M$ has a Cholesky factorization $M=R{R}^T$ with positive diagonal. By [F6] and [F7], solving $Rv=-L_{UB}{y}_B$ and then $R^{T}z=v$ gives a unique vector $z=-M^{-1}{L}_{UB}{y}_B$ in finitely many scalar operations.

Let $f_B=y_B$ and $f_U=z$. For any $h\in {\mathbb{R}}^U$, block expansion and $Mz+L_{UB}{y}_B=0$ give $E(f+h)-E(f)=h^T(Mz+L_{UB}{y}_B)+\frac{1}{2}{h}^{T}Mh=\frac{1}{2}{h}^{T}Mh$. This is positive for $h\mathrm{\ne }0$ by step 1.2, so $f$ is the unique minimizer and has the stated block formula.

The equation solved in step 2.1 gives $(Lf{)}_u=0$ for every $u\in U$. If $d_u=0$, then $u$ is an isolated support component contained in $U$, contradicting anchoring; hence $d_u>0$ and $f_u={\sum }_j{w}_{uj}{f}_j\mathrm{/}{d}_u$, a weighted average of neighboring values.

Let $m={\max }_{i\in V}{f}_i$. If $m>{\max }_{b\in B}{y}_b$, then no maximizing vertex lies in $B$, so choose a maximizing vertex $u_0\in U$. At $u_0$, the weighted-average equation in step 3.2 and $f_j\le m$ force $f_j=m$ for each neighbor with positive weight. Choose a shortest finite path in its support component to $B$; every interior vertex lies in $U$, so applying the same argument successively forces the boundary value at the end of the path to equal $m$, a contradiction. Therefore ${\max }_{i\in V}{f}_i\le {\max }_{b\in B}{y}_b$.

Apply step 4.1 to $-f$, whose boundary values are $-y_B$ and whose unlabeled coordinates satisfy the same weighted-average equations. This yields ${\min }_{b\in B}{y}_b\le f_u$ for every $u\in U$, completing the maximum-principle bounds.

For one-hot boundary data, let $f^{(c)}$ be the minimizer for coordinate $c$ and put $g={\sum }_{c=1}^C{f}^{(c)}$. By step 2.1 each coordinate satisfies $(L{f}^{(c)}{)}_u=0$, and by steps 4.1 and 5.1 each $f_u^{(c)}$ is between 0 and 1. Linearity gives $(Lg{)}_u=0$ on $U$, while the one-hot boundary data give $g{\mathrm{\mid }}_B=1$. The constant-one function also has these properties because every row sum of $L=D-W$ is zero. The difference $h=g-\mathbf{1}$ therefore has $h{\mathrm{\mid }}_B=0$ and $L_{UU}{h}_U=0$; positive definiteness from step 1.2 forces $h_U=0$. Thus $g$ is identically 1, so every unlabeled row lies in ${\mathrm{\Delta }}_C$.