$\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 paper of mine.