  


The (minimum) rank of typical foolingset matrices
Mozhgan Pourmoradnasseri(mozhganut.ee) Abstract: A foolingset matrix is a square matrix with nonzero diagonal, but at least one in every pair of diagonally opposite entries is 0. Dietzfelbinger et al. '96 proved that the rank of such a matrix is at least $\sqrt n$, for a matrix of order $n$. We ask for the typical minimum rank of a foolingset matrix: For a foolingset zerononzero pattern chosen at random, is the minimum rank of a matrix with that zerononzero pattern over a field $\FF$ closer to its lower bound $\sqrt{n}$ or to its upper bound $n$? We study random patterns with a given density $p$, and prove an $\Omega(n)$ bound for the cases when (a) $p$ tends to $0$ quickly enough; (b) $p$ tends to $0$ slowly, and $\abs{\FF}=O(1)$; (c) $p\in\lt]0,1\rt]$ is a constant. We leave open the case when $p\to 0$ slowly and $\FF$ is a large (e.g., $\FF=\GF(2^n)$, $\FF=\RR$). Keywords: Category 1: Combinatorial Optimization (Polyhedra ) Category 2: Combinatorial Optimization (Graphs and Matroids ) Citation: Download: [PDF] Entry Submitted: 01/02/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  