Prove that this family of sets has a SDR .

Question

Definition. SDR = System of distinct representatives. Given a finite family of sets $X=\{S_1,…,S_n\}$, a system of distinct representatives, or SDR, for the sets in $X$ is a set of distinct elements $x_1$, ... ,$x_n$ with $x_i$ belongs to $S_i$ for $1≤i≤n$

Hall's Theorem.

Incident Matrix of family of sets $A=\{S_1,…,S_n\}$ with $S_i \subseteq \{1,…,n\}$ for $1≤i≤n$ is $[a_{ij}]$ such that $a_{ij}= \begin{cases} 1 & j\in S_i\\ 0 & o.w. \end{cases}$

Given a finite family of sets $X=\{S_1,…,S_n\}$ with $S_i \subseteq \{1,…,n\}$ for $1≤i≤n$ , Prove that if incident matrix of $X$ is invertible then $X$ has a SDR.

probably hall's theorem is useful.

Answer 1

HINT: $X$ is invertible if and only if $\det X\ne 0$. The Leibniz formula for the determinant says that

$$\det X=\sum_{\sigma\in S_n}\operatorname{sgn}(\sigma)\prod_{i=1}^na_{i,\sigma(i)}\;,$$

where $S_n$ is the set of all permutations of $\{1,2,\ldots,n\}$. If $\det X\ne 0$, then clearly there is at least one $\sigma_0\in S_n$ such that

$$\prod_{i=1}^na_{i,\sigma_0(i)}\ne 0\;.$$

Since each entry $a_{i,j}$ in $X$ is either $0$ or $1$, this tells you something about the entries $a_{i,\sigma_0(i)}$. Now use $\sigma_0$ to get an SDR. (You don’t need Hall’s theorem.)