A worked theorem–proof page

This page is deliberately complete: a concrete statement and a full proof. The content is standard linear algebra, but written in the language of triangle selection.

Setup

Fix a base graph $G=(V,E)$ with an orientation of edges. Let $C^1=\mathbb{R}^{E}$. For a triangle set $T$, let $\delta_1(T):C^1\to C^2$ be the edge–triangle coboundary and define $$L_1^{\uparrow}(T)=\delta_1(T)^{\mathsf T}\delta_1(T).$$

Proposition (triangle addition is a rank-one PSD update)

completely explicit

Let $\tau$ be an oriented triangle. Let $b_\tau\in C^1$ be the signed incidence vector of the boundary of $\tau$ in the oriented edge basis (entries in $\{0,\pm 1\}$). Then $$L_1^{\uparrow}(T\cup\{\tau\}) \;=\; L_1^{\uparrow}(T) \;+\; b_\tau b_\tau^{\mathsf T}.$$ In particular, $L_1^{\uparrow}(T\cup\{\tau\})\succeq L_1^{\uparrow}(T)$.

Proof

Write $\delta_1(T)$ as a matrix whose rows are indexed by oriented triangles in $T$ and whose columns are indexed by oriented edges in $E$. For each oriented triangle $\sigma\in T$, the row of $\delta_1(T)$ is precisely the signed incidence vector $b_\sigma^{\mathsf T}\in \mathbb{R}^{E}$.

When we add the oriented triangle $\tau$, the new coboundary matrix $\delta_1(T\cup\{\tau\})$ is obtained by appending one additional row, namely $b_\tau^{\mathsf T}$. Thus, as block matrices, $$ \delta_1(T\cup\{\tau\}) = \begin{bmatrix} \delta_1(T)\\ b_\tau^{\mathsf T} \end{bmatrix}. $$

Compute the upper Laplacian: \begin{align*} L_1^{\uparrow}(T\cup\{\tau\}) &=\delta_1(T\cup\{\tau\})^{\mathsf T}\delta_1(T\cup\{\tau\})\\ &= \begin{bmatrix} \delta_1(T)^{\mathsf T} & b_\tau \end{bmatrix} \begin{bmatrix} \delta_1(T)\\ b_\tau^{\mathsf T} \end{bmatrix}\\ &=\delta_1(T)^{\mathsf T}\delta_1(T)\;+\; b_\tau b_\tau^{\mathsf T}\\ &=L_1^{\uparrow}(T)+b_\tau b_\tau^{\mathsf T}. \end{align*} Since $b_\tau b_\tau^{\mathsf T}$ is an outer product, it is positive semidefinite, giving the Loewner monotonicity. This completes the proof.

Immediate corollaries

Corollary (Rayleigh quotients increase)

one line

For every $x\in C^1$, $$\langle L_1^{\uparrow}(T\cup\{\tau\})x,x\rangle=\langle L_1^{\uparrow}(T)x,x\rangle+\langle b_\tau,x\rangle^2\ \ge\ \langle L_1^{\uparrow}(T)x,x\rangle.$$

Corollary (eigenvalue monotonicity)

Weyl

All ordered eigenvalues of $L_1^{\uparrow}$ (counting multiplicity) are nondecreasing as triangles are added. This is immediate from $L_1^{\uparrow}(T\cup\{\tau\})\succeq L_1^{\uparrow}(T)$.

Where things become subtle: comparing $\lambda_{\min}^+(\cdot)$ for operators whose kernels change with $T$. The rank-one update is the right starting point, but kernel bookkeeping matters.