OctoInformBeta

OpenAI preprint, September 2026 · §4. A projection with controlled row sums

Lemma 4.1: Quadratic and squared norm estimates under positive conductances and direct-edge incidence assumptions

Absolute projection bounds on complete graphs.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Electrical localization concerns the effect of taking entrywise absolute values in a projection on edge coordinates. The weighted incidence matrices arise in the LpL_p dimension reduction construction.

Let VV and EE be finite vertex and edge sets, with endpoint maps src,dst:E→V\mathrm{src},\mathrm{dst}:E\to V and real conductances cec_e. Write n=|V|n=|V|. Here log\log is the natural logarithm on positive arguments, with log⁡0=0\log 0=0. The incidence matrix B∈ℝE×VB\in\mathbb R^{E\times V} is the matrix given by (1): Bei=𝟏{src(e)=i}−𝟏{dst(e)=i}.B_{ei}=\mathbf 1_{\{\mathrm{src}(e)=i\}} -\mathbf 1_{\{\mathrm{dst}(e)=i\}}.(1)✦ The conductance-weighted incidence matrix A∈ℝE×VA\in\mathbb R^{E\times V} is obtained from BB by multiplying row ee by ce\sqrt{c_e}, as in (2), where CC is the diagonal conductance matrix: C=diag⁡(ce),A=C1/2B.C=\operatorname{diag}(c_e),\qquad A=C^{1/2}B.(2)✦

The Gram Projection

For a real matrix A∈ℝE×VA\in\mathbb R^{E\times V}, let M=A𝖳AM=A^{\mathsf T}A be its Gram matrix, and choose an orthonormal eigenvector matrix UU for MM, with corresponding eigenvalues λk\lambda_k. The Gram eigenbasis coordinates Z∈ℝE×VZ\in\mathbb R^{E\times V} are the matrix in (3): Z=AU.Z=AU.(3)✦ The Gram projection Q(A)∈ℝE×EQ(A)\in\mathbb R^{E\times E}, or orthogonal range projection, is the matrix given by (4), taking the reciprocal to be zero at zero: Q(A)=Zdiag⁡(ρ(λk))Z𝖳,ρ(t)={t−1,t≠0,0,t=0.Q(A)=Z\operatorname{diag}\bigl(\rho(\lambda_k)\bigr)Z^{\mathsf T}, \qquad \rho(t)= \begin{cases} t^{-1},&t\ne0,\\ 0,&t=0. \end{cases}(4) For an edge matrix QQ, its entrywise absolute value |Q||Q| is the matrix with entries |Q|ef=|Qef||Q|_{ef}=|Q_{ef}|.

The Claim

Theorem 1. Suppose that every conductance cec_e is positive, every vertex is an endpoint of at least one edge, and each pair of distinct vertices is joined by an edge. Let AA be the conductance-weighted incidence matrix in (2) and put Q=Q(A)Q=Q(A) as in (4). For every x∈ℝEx\in\mathbb R^E, the quadratic localization bound is |∑e∈E∑f∈Exexf|Qef||≤2log⁡n∑e∈Exe2,\left|\sum_{e\in E}\sum_{f\in E}x_e x_f\,|Q_{ef}|\right| \le 2\log n\sum_{e\in E}x_e^2,(5)✦ and the electrical localization bound is ∑e∈E(∑f∈E|Qef|xf)2≤(2log⁡n)2∑e∈Exe2.\sum_{e\in E}\left(\sum_{f\in E}|Q_{ef}|x_f\right)^2 \le (2\log n)^2\sum_{e\in E}x_e^2.(6)✦

In the paper, the result reads: if 𝒢\mathcal G is a connected loopless graph on n≥2n\ge2 vertices, BB is an oriented edge-by-vertex incidence matrix, C=diag⁡(ce)C=\operatorname{diag}(c_e) has ce>0c_e>0, and QQ is the Euclidean orthogonal projection onto im⁡(C1/2B)\operatorname{im}(C^{1/2}B), then ∥|Q|∥ℓ2→ℓ2≤2log⁡n\|\,|Q|\,\|_{\ell_2\to\ell_2}\le2\log n.

What Is Checked

The bounds (5) and (6) are stated for the Gram projection (4) of the conductance-weighted incidence matrix (2), with positive conductances and the endpoint and direct-edge hypotheses of the theorem. For every real matrix AA, its Gram matrix A𝖳AA^{\mathsf T}A is Hermitian.✦