= Solution
Write $s_i=1$ on $S$ and $s_i=-1$ on $S^c$, and put $v=s/\sqrt n$ and $w=\mathbf1/\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=a\mathbf1\mathbf1^\top+bss^\top-I_n/2$. Consequently
$$
\boxed{A_0+I_n/2=(n/2-t\sqrt n/2)ww^\top+(t\sqrt n/2)vv^\top,\qquad M_0=(t\sqrt n/2)vv^\top.}
$$
Both 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.
\Image[/past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2016/iii/paper-210-block-expectation.png]
{title=Expected adjacency blocks and the positive rank-one community signal}
Back to article page
