Building matrices with prescribed size and number of invertible submatrices

Edward S. T. Fan; Tony W. H. Wong

doi:10.1016/j.ejc.2019.103016

paper

Building matrices with prescribed size and number of invertible submatrices

arXiv:1402.6048 · doi:10.1016/j.ejc.2019.103016

Abstract

Given an ordered triple of positive integers $(n, r, b)$ , where $1 \leq b \leq (r n)$ , does there exist a matrix of size $r \times n$ with exactly $b$ invertible submatrices of size $r \times r$ ? Such a matrix is called an $(n, r, b)$ -matrix. This question is a stronger version of an open problem in matroid theory raised by Dominic Welsh. In this paper, we prove that an $(n, r, b)$ -matrix exists when the corank satisfies $n - r \leq 3$ , unless $(n, r, b) = (6, 3, 11)$ . Furthermore, we show that an $(n, r, b)$ -matrix exists when the rank $r$ is large relative to the corank $n - r$ .