Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 210 / 4 / a / Solution

Write $s_i=1$ on $S$ and $s_i=-1$ on $S^c$, and put $v=s/\sqrt{n}$ and $w=1/\sqrt{n}$. Because the two groups have equal size, $v,w$ are orthonormal. Let $a=1/2-t/(2\sqrt{n})$ and $b=t/(2\sqrt{n})$. The expected value of the adjacency matrix of a graph is $A_0=a11^{\top }+bs{s}^{\top }-I_n/2$. ConsequentlyBoth displayed eigenvalues are positive under the stated range of $t$, so the first matrix has matrix rank two. The other $n-2$ eigenvalues are zero. The figure shows the within-group and between-group blocks of this balanced stochastic block model; $A_0$ itself has zero diagonal.