  For an $n \times n$ matrix $M$ with entries in $\mathbb{Z}_2$ denote by
$R(M)$ the minimal rank of all the matrices obtained by changing some numbers
on the main diagonal of $M$. We prove that for each non-negative integer $k$
there is a polynomial in $n$ algorithm deciding whether $R(M) \leq k$ (whose
complexity may depend on $k$). We also give a polynomial in $n$ algorithm
computing a number $m$ such that $m/2 \leq R(M) \leq m$. These results have
applications to graph drawings on non-orientable surfaces.
