Families of subsets whose characteristic vectors are spanning sets

Question

Let $X$ be a finite set and $\mathbb CX$ be a vector space with basis $X$. If $Y\subseteq X$ is a subset, then by the characteristic vector of $Y$ I mean $\sum_{y\in Y}y$.

My question is:

1. Is there a standard name in the literature for a family of subsets of $X$ whose characteristic vectors span $\mathbb CX$?

2. Are there any decent combinatorial characterizations of families of subsets satisfying 1.?

Answer 1

Ad 2. Without loss of generality let $X$ be the finite ordinal $n$. Then $\mathbb{C}X\cong\mathbb{C}^n$. Now,

• because of your definition of characteristic vectors,

• because the supports of the characteristic vectors correspond to the sets in the family,

• because you asked the question in the context of vector spaces,

• because every generating set of a vector space contains a basis¹,

it follows that your question is at least as difficult as:

Are there any decent combinatorial characterizations of nonsingular zero-one matrices?²

While of course the term 'decent' is not mathematically defined, all hope of what most people would call a 'decent' characterization was lost by 1967, at the latest, with the publication of:

János Komlós: On the determinant of (0,1)-matrices. Studia Scientiarum Mathematicarum Hungarica 2 (1967) 7-21

which seems to have been the first proof that

Almost all finite square zero-one matrices are nonsingular (in characteristic zero). $\hspace{3em}$ (1)

By interpreting the zero-one-vectors as subsets of the set $X$, you can read Komlós' article as an answer why most families of subsets of $X$ are generating-sets of $\mathbb{C}X$, if only the number of sets in the family is at least $n=\mathrm{dim}_{\mathbb{C}}\ \mathbb{C}X$, and hence such generating sets cannot be characterized.

In that sense, Komlós' 1967 article is some sort of negative answer to your question no 2.

If later work of Komlós, and in several later publications of Bourgain, Tao, Vu and Wood, theorem (1) was quantified by giving upper bounds for the probability that a randomly chosen such matrix is singular. Detailing these difficult results (wich roughly speaking show that singular zero-one matrices are exponentially rare w.r.t. dimension $n$) would seem excessive for an answer to your question; what matters here is that

Any characterization of the kind you were asking for would have to account for the fact that if you select the "family of at least $\lvert X\rvert$ subsets of $X$" randomly, then asymptotically almost surely you'll obtain one such "spanning set".

In an intuitive sense, this is dashes all hopes of a decent structural characterization in the traditional sense.

That said, it is impossible to predict what the future will bring, and of course there are ideas like rough structure and classification, which might be more adequate to such a question than the traditional structure theorems of algebra, which decompose a structure into simpler structures of a deterministic specified kind.

One could also perhaps hope to define some kind of 'distance' $\mathrm{d}$ of the "family" from the 'diagonal family' $\{ \{i\}\colon i\in X \}$, which arguably is the simplest generating set, and then try to prove quantitative results to the effect of 'there are roughly $h(d)$ generating families $\mathcal{F}$ of distance $\mathrm{d}(\mathcal{F})=d$', or even dream of structural results.

Ad 1. While non-existence is difficult to prove, I am reasonably confident to state that no attested technical term exists. Of course, trivially, every family of sets of the kind you require must be an edge cover of the ground set $X$, in the sense of hypergraph theory, but this obvious necessary condition is far from a characterization. There are some vaguely related terms, like 'sparsity patters' of nonsingular matrices, or 'sign patterns' of nonsingular matrices.

${}$___________________________________________________________

¹ This is of course not true for modules.

² As usual, 'nonsingular zero-one matrix' without further qualifications means 'zero-one matrix which is nonsingular in characteristic zero', i.e., 'zero-one matrix whose determinant is not zero when computed in the ring $\mathbb{Z}$.