Independent-copy symmetrization matrix

PDF p. 33: Proof of Proposition 6.3

Let $n\in \mathbb{N}$ with $n\ge 1$, $p\in [0,1]$, and let $A$ be the adjacency matrix of $G(n,p)$ on the labelled vertices $[n]=\{1,\dots ,n\}$. Let $A^{\mathrm{\prime }}$ be an independent copy of $A$: it has the same matrix distribution as $A$ and is independent of $A$ as a random element. Define the independent-copy symmetrization matrix by $W=A-A^{\mathrm{\prime }}$.

The matrix $W$ is symmetric with zero diagonal. Its entries $W_{x,y}$ for $1\le x<y\le n$ are mutually independent and identically distributed: each takes the values $1$ and $-1$ with probability $p(1-p)$ each, and $0$ with probability $p^2+(1-p{)}^2$. Mutual independence means that every joint assignment to a finite subfamily has probability equal to the product of its individual probabilities. When there are no entries above the diagonal, this independence assertion is vacuous.

Erdős–Rényi random graph and high probability

Adjacency, degrees, graph Laplacian, and spectral notation

Independent random elements

Finite Bernoulli difference laws and parity of moments

Given: $n\in \mathbb{N}$ with $n\ge 1$, $p\in [0,1]$, an adjacency matrix $A$ of $G(n,p)$ and an independent copy $A^{\mathrm{\prime }}$.

Goal: Verify that $W$ is well defined and has the stated symmetry and entry laws.

1.1 Both matrices are indexed by the same labelled vertex set, so their entrywise difference is a well-defined real matrix. By [F1] both are symmetric with zero diagonal, hence so is $W$. [given, F1, algebra]

1.2 For any assignment of values to edge indicators from each matrix, [F2] factors its probability into the probability of the assignment for $A$ and that for $A^{\mathrm{\prime }}$. The same law for $A^{\mathrm{\prime }}$ and [F1] factor each of those two probabilities over its distinct edges. Thus all coordinates in the two edge families are mutually independent Bernoulli$(p)$ variables on their original common probability space. [given, F1, F2]

2.1 Let $E$ be the finite set of unordered pairs of distinct vertices in $[n]$, and let $S$ be the finite set of all assignments $(b_e,b_e^{\mathrm{\prime }}{)}_{e\in E}$ with $b_e,b_e^{\mathrm{\prime }}\in \{0,1\}$. Write $Z=((A_e,A_e^{\mathrm{\prime }}){)}_{e\in E}$ for the joint edge vector. For $z\in S$, put $w(z)=\mathbb{P}(Z=z)$. These events are measurable because each is a finite intersection of edge-coordinate events; they partition the original sample space. By [F4], the weights are nonnegative and sum to one. Hence $(S,w)$ is a finite probability space by [F5]. For each $T\subseteq S$, the event $Z\in T$ is the disjoint union of the events $Z=z$ for $z\in T$, so $\mathbb{P}(Z\in T)={\sum }_{z\in T}w(z)$. Consequently every joint coordinate-assignment probability on $(S,w)$ equals its original probability. By step 1.2, the coordinate pairs on $(S,w)$ satisfy all the independence and Bernoulli hypotheses of [F3]. [given, F1, F3, F4, F5, step 1.2, construct]

3.1 Apply [F3] on $(S,w)$ to the coordinate differences $b_e-b_e^{\mathrm{\prime }}$. This gives their common law and mutual independence. Every joint assignment of differences is a subset of $S$, so the probability equality in step 2.1 transfers all these assertions to the original differences $A_e-A_e^{\mathrm{\prime }}$, precisely the entries $W_{x,y}$ for $x<y$. This includes $p=0$ and $p=1$ without dividing by any probability. If $n=1$, $E$ is empty and $S$ consists of the single empty assignment of weight one; there are no upper-diagonal entries and independence is vacuous. Together with step 1.1 this establishes every asserted property. [F3, step 1.1, step 2.1] ∎

The construction and entry law are attributed to Expander graphs are globally synchronizing, proof of Proposition 6.3, PDF p. 33. The argument above uses the independent suppliers stated in its facts.