You can most easily prove this by working with an intermediate problem where $y_{i,j}=x_{i}x_{j}$ is a constraint. Then relax the integraility to bounds of 0 and 1 and show that the constraints relating $x$ and $y$ are a relaxation of $y_{i,j}=x_{i}x_{j}$.

How large are $m$ and $n$? thousands, millions, billions? How dense are the blocks $A_{1}$ and $A_{2}$?