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.


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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.