$\DeclareMathOperator{\rk}{rk}$It is possible to construct a matrix with $\rk(A)\leq 2\sqrt{n}$. Introduce two matrices $B$ and $C$, whose rows and columns of our matrix will be indexed by elements of $\{1,2,\dotsc,r\}^2$, and whose entries are defined by
$$
B_{(x,y),(x',y')}=\begin{cases}1&\text{if }x=x',\\0&\text{otherwise},\end{cases}
$$
and
$$
B_{(x,y),(x',y')}=\begin{cases}-1&\text{if }y<y',\\0&\text{otherwise},\end{cases}
$$
where $(x,y),(x',y')\in \{1,2,\dotsc,n\}^2$.

We have $\rk(B)\leq r$ and $\rk(C)\leq r$, and $A:=B+C$ is an $r^2$-by-$r^2$ matrix satisfying the requisite condition.

This is a minor modification of the constructions that I used in a <a href="http://arxiv.org/abs/1508.00145">paper of mine</a>.