Building matrices with prescribed size and number of invertible submatrices. (January 2020)

• Record Type: Journal Article
• Authors: Fan, Edward S.T.; Wong, Tony W.H.
• Is Part Of: European journal of combinatorics. Volume 83(2020)
• Publication Date: 2020-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2019.103016
• Languages: English
• ISSNs: 0195-6698

Abstract

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 .