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 dimension reduction construction.
Let and be finite vertex and edge sets, with endpoint maps and real conductances . Write . Here is the natural logarithm on positive arguments, with . The incidence matrix is the matrix given by (1): (1)✦ The conductance-weighted incidence matrix is obtained from by multiplying row by , as in (2), where is the diagonal conductance matrix: (2)✦
The Gram Projection
For a real matrix , let be its Gram matrix, and choose an orthonormal eigenvector matrix for , with corresponding eigenvalues . The Gram eigenbasis coordinates are the matrix in (3): (3)✦ The Gram projection , or orthogonal range projection, is the matrix given by (4), taking the reciprocal to be zero at zero: (4) For an edge matrix , its entrywise absolute value is the matrix with entries .
The Claim
Theorem 1. Suppose that every conductance is positive, every vertex is an endpoint of at least one edge, and each pair of distinct vertices is joined by an edge. Let be the conductance-weighted incidence matrix in (2) and put as in (4). For every , the quadratic localization bound is (5)✦ and the electrical localization bound is (6)✦
In the paper, the result reads: if is a connected loopless graph on vertices, is an oriented edge-by-vertex incidence matrix, has , and is the Euclidean orthogonal projection onto , then .
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 , its Gram matrix is Hermitian.✦