A simple improvement bound under rank-one update

Complete proof of a basic inequality. Useful as a “first certificate” in greedy triangle addition.

Statement

Proposition

rank-one update bound

Let $A\succeq 0$ be symmetric and set $C=A+uu^{\mathsf T}$. For any unit vector $x$, $$\langle Cx,x\rangle-\langle Ax,x\rangle = \langle u,x\rangle^2 \le \|u\|^2.$$ Consequently, for any subspace $S$, $$\max_{\substack{x\in S\\\|x\|=1}}\langle Cx,x\rangle \le \max_{\substack{x\in S\\\|x\|=1}}\langle Ax,x\rangle + \|u\|^2.$$

Proof

The first identity is direct: $$\langle Cx,x\rangle=\langle Ax,x\rangle+\langle uu^{\mathsf T}x,x\rangle=\langle Ax,x\rangle+\langle u,x\rangle^2.$$ By Cauchy–Schwarz, $|\langle u,x\rangle|\le \|u\|\cdot \|x\|=\|u\|$, hence $\langle u,x\rangle^2\le \|u\|^2$. Taking maxima over $x\in S$ yields the second inequality.

Triangle addition interpretation

With $u=b_\tau$, the update $L_1^{\uparrow}(T\cup\{\tau\})=L_1^{\uparrow}(T)+b_\tau b_\tau^{\mathsf T}$ satisfies $$\langle L_1^{\uparrow}(T\cup\{\tau\})x,x\rangle - \langle L_1^{\uparrow}(T)x,x\rangle = \langle b_\tau,x\rangle^2 \le \|b_\tau\|^2.$$ Since $\|b_\tau\|^2=3$ for an unweighted triangle (three $\pm 1$ entries), this gives a crude but universal scale.