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

Autor:	Kogan, Eugene
Rok vydání:	2021
Předmět:	Mathematics - Combinatorics Computer Science - Data Structures and Algorithms 15B33 (Primary) 68R01 (Secondary) F.2.2 G.2.0
Druh dokumentu:	Working Paper
Popis:	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. Comment: 10 pages, 1 figure
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2104.10668 Zobrazit plný text záznamu View this record from Arxiv