Rank-one PSD updates
Toolkit note: what can be said about eigenvalues when $A$ is replaced by $A+uu^{\mathsf T}$. This is directly relevant because adding a triangle produces exactly this update on $L_1^{\uparrow}$.
Loewner monotonicity
If $A\succeq 0$, then $A+uu^{\mathsf T}\succeq A$. In particular, every Rayleigh quotient can only increase: $$\langle (A+uu^{\mathsf T})x,x\rangle=\langle Ax,x\rangle + \langle u,x\rangle^2\ \ge\ \langle Ax,x\rangle.$$
If $A\preceq C$, then $\lambda_i(A)\le \lambda_i(C)$ for all $i$ (ordered with multiplicity). Hence each eigenvalue (counting multiplicity) is nondecreasing under PSD updates.
Rank-one interlacing
For $C=A+uu^{\mathsf T}$, eigenvalues interlace: $$\lambda_1(A)\le \lambda_1(C)\le \lambda_2(A)\le \cdots \le \lambda_n(A)\le \lambda_n(C).$$ This is a sharp structural statement (not just “everything increases”).
Kernel-aware quantities
The quantity $\lambda_{\min}^+(A)$ depends on $(\ker A)^\perp$. When the kernel changes under update, interpreting “improvement” requires distinguishing:
- kernel shrinkage: a previously-harmonic direction becomes constrained (a zero eigenvalue becomes positive),
- positive-floor lift: the smallest positive eigenvalue itself moves upward.
If $A\preceq C$ and $\ker(C)\subseteq \ker(A)$, then $\lambda_{\min}^+(C)\ge \lambda_{\min}^+(A)$. The hypothesis is the point: without it, “smallest positive” is not monotone in general.
See kernel-bookkeeping for discussion.
Triangle addition link
In our setting, $L_1^{\uparrow}(T\cup\{\tau\})=L_1^{\uparrow}(T)+b_\tau b_\tau^{\mathsf T}$. Thus you can apply all of the above with $u=b_\tau$.