On the rank of Z_2-matrices with free entries on the diagonal

Abstract

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)\le k$ (whose complexity may depend on $k$). We also give a polynomial in $n$ algorithm computing a number $m$ such that $m/2\le R(M)\le m$. These results have applications to graph drawings on non-orientable surfaces.

10 pages, 1 figure