Building matrices with prescribed size and number of invertible submatrices. (January 2020) - Fan, Edward S.T.; Wong, Tony W.H.
Abstract: Given an ordered triple of positive integers ( n, r, b ), where 1 ≤ b ≤ n r, does there exist a matrix of size r × n with exactly b invertible submatrices of size r × 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 ≤ 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 .