A certain class of incidence matrices

Abstract

1. Let S be a set consisting of K elements, and call any subset of S containing precisely m elements an m-set [2]. We wish to study incidence matrices obtained in the following manner: Let K > mrn_ n >0, we label the rows of the matrix by all the m-sets of S and the columns by all the n-sets of S; take the (i, j) element as 1 if the m-set corresponding to the ith row contains the n-set corresponding to the jth column, and zero otherwise. This note studies the question of which collections of m-sets give rise to a linearly dependent set of row vectors, and likewise what combinations of n-sets give rise to a linearly dependent set of column vectors. To do this, we characterize the row null spaces and the column null spaces of the above matrices in an inductive manner. Then using this characterization, we prove that the above matrices must have maximal rank. A corollary then gives a necessary condition for the existence of a tactical configuration [I].