4.3: Partial SDRs
- Page ID
- 7161
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)In this section, sdr means partial sdr.
If there is no complete sdr, we naturally want to know how many of the \(n\) sets can be represented, that is, what is the largest value of \(m\) so that some \(m\) of the sets have a complete sdr. Since there is no complete sdr, there are sets \(A_{i_1},A_{i_2},\ldots,A_{i_k}\) such that \(|\bigcup_{j=1}^k A_{i_j}|=l< k\). Clearly at most \(l\) of these \(k\) sets have a complete sdr, so no sdr for \(A_1,A_2,\ldots,A_n\) can be larger than \(n-k+l\). Thus, \(m\) can be no larger than the minimum value, over all \(k\) and all collections of sets \(A_{i_1},A_{i_2},\ldots,A_{i_k}\), of \(n-k+|\bigcup_{j=1}^k A_{i_j}|\). Note that if \(|\bigcup_{j=1}^k A_{i_j}|>k\), \(n-k+|\bigcup_{j=1}^k A_{i_j}|>n\), which tells us nothing. If \(k=0\), \(n-k+|\bigcup_{j=1}^k A_{i_j}|=n\) (because empty unions are empty), so we are guaranteed that the minimum is never greater than \(n\). In fact the minimum value of the expression is exactly the size of a largest sdr.
The maximum size of an sdr for the sets \(A_1,A_2,\ldots,A_n\) is the minimum value, for \(0\le k\le n\) and sets \(A_{i_1},A_{i_2},\ldots,A_{i_k}\), of \(n-k+|\bigcup_{j=1}^k A_{i_j}|\).
- Proof
-
Since no sdr can be larger than this minimum value, it suffices to show that we can find an sdr whose size is this minimum. The proof is by induction on \(n\); the case \(n=1\) is easy.
Suppose first that the minimum value is \(n\), so that for all \(k\) and all collections of sets \(A_{i_1},A_{i_2},\ldots,A_{i_k}\), \[n-k+|\bigcup_{j=1}^k A_{i_j}|\ge n.\nonumber\] Then rearranging we see that
\[|\bigcup_{j=1}^k A_{i_j}|\ge k,\nonumber\]
so by Hall's Theorem (4.2.1), there is an sdr of size \(n\).
Note that the minimum value of \(n-k+|\bigcup_{j=1}^k A_{i_j}|\) occurs when \(|\bigcup_{j=1}^k A_{i_j}|-k\) is a minimum, that is \[\min(n-k+|\bigcup_{j=1}^k A_{i_j}|)= n+\min(|\bigcup_{j=1}^k A_{i_j}|-k).\nonumber\] Suppose now that the minimum \(m\) is less than \(n\), and that \(m=n-k+|\bigcup_{j=1}^k A_{i_j}|\), with \(0< k< n\). Let \(B_j=A_{i_j}\); since \(k< n\), the induction hypothesis applies to the sets \(B_1,\ldots,B_k\). Since each set \(B_j\) is \(A_{i_j}\), \(|\bigcup_{j=1}^l B_{h_j}|-l\ge |\bigcup_{j=1}^k A_{i_j}|-k\), for all \(l\) and \(B_{h_1},\ldots,B_{h_l}\). Thus, the minimum value of \(|\bigcup_{j=1}^l B_{i_j}|-l\), over all \(l\) and \(B_{h_1},\ldots,B_{h_l}\), is \(|\bigcup_{j=1}^k B_{j}|-k=|\bigcup_{j=1}^k A_{i_j}|-k\), so by the induction hypothesis, the sets \(A_{i_1},A_{i_2},\ldots,A_{i_k}\) have an sdr of size \(k-k+|\bigcup_{j=1}^k A_{i_j}|=|\bigcup_{j=1}^k A_{i_j}|=m-n+k\), \(\{x_1,\ldots,x_{m-n+k}\}\).
Now consider the \(n-k\) sets consisting of those original sets not in \(A_{i_1},A_{i_2},\ldots,A_{i_k}\), that is, \(\{A_i\mid i\notin\{i_1,\ldots,i_k\}\}\). Let \(C_i=A_i\backslash \bigcup_{j=1}^k A_{i_j}\) for \(i\) not in \(i_1,i_2,\ldots,i_k\). Consider some sets \(C_{g_1},C_{g_2},\ldots,C_{g_l}\). If \(|\bigcup_{j=1}^l C_{g_j}|< l\) then \(|\bigcup_{j=1}^l C_{g_j}|-l< 0\) and \[\eqalign{ n-k+|\bigcup_{j=1}^k A_{i_j}| &> n-k-l+|\bigcup_{j=1}^l C_{g_j}|+|\bigcup_{j=1}^k A_{i_j}|\cr &\ge n-(k+l)+|C_{g_1}\cup\cdots\cup C_{g_l}\cup A_{i_1}\cup\cdots \cup A_{i_k}|\cr &= n-(k+l)+|A_{g_1}\cup\cdots\cup A_{g_l}\cup A_{i_1}\cup\cdots \cup A_{i_k}|,\cr }\nonumber\] contradicting the fact that \(n-k+|\bigcup_{j=1}^k A_{i_j}|\) is a minimum. Thus by Hall's Theorem (4.2.1), the sets \(C_{g_1},C_{g_2},\ldots,C_{g_{n-k}}\) have a complete sdr \(\{y_1,\ldots,y_{n-k}\}\). By the definition of the sets \(C_i\), \(\{x_1,\ldots,x_{m-n+k}\}\cap\{y_1,\ldots,y_{n-k}\}=\emptyset\), so \(\{x_1,\ldots,x_{m-n+k}\}\cup \{y_1,\ldots,y_{n-k}\}\) is an sdr of size \(m-n+k+n-k=m\) as desired.
Finally, suppose that the minimum value of \(n-k+|\bigcup_{j=1}^k A_{i_j}|\) occurs only when \(k=n\), so we want an sdr of size \[ n-n+|\bigcup_{j=1}^n A_{j}|=|\bigcup_{j=1}^n A_{j}|.\nonumber\] Then \[\eqalign{ n-(n-1)+|\bigcup_{j=1}^{n-1} A_{j}|&>|\bigcup_{j=1}^n A_{j}|\cr 1+|\bigcup_{j=1}^{n-1} A_{j}|&>|\bigcup_{j=1}^n A_{j}|\cr |\bigcup_{j=1}^{n-1} A_{j}|&\ge|\bigcup_{j=1}^n A_{j}|.\cr }\nonumber\] Since \(|\bigcup_{j=1}^{n-1} A_{j}|\le|\bigcup_{j=1}^n A_{j}|\), \(|\bigcup_{j=1}^{n-1} A_{j}|=|\bigcup_{j=1}^n A_{j}|\). By the induction hypothesis, the theorem applies to the sets \(A_1,A_2,\ldots,A_{n-1}\). If the minimum of \((n-1)-l+|\bigcup_{j=1}^l A_{i_j}|\) occurs when \(l=n-1\), then there is an sdr of size \((n-1)-(n-1)+|\bigcup_{j=1}^{n-1} A_{j}| =|\bigcup_{j=1}^{n-1} A_{j}| =|\bigcup_{j=1}^{n} A_{j}|\), as desired.
If the minimum occurs when \(l< n-1\) and not when \(l=n-1\), then \[\eqalign{ (n-1)-l+|\bigcup_{j=1}^{l} A_{i_j}|< |\bigcup_{j=1}^{n-1} A_{j}|\cr n-l+|\bigcup_{j=1}^{l} A_{i_j}|< |\bigcup_{j=1}^{n-1} A_{j}|+1\cr }\nonumber\] and by assumption \[ n-l+|\bigcup_{j=1}^{l} A_{i_j}|>|\bigcup_{j=1}^{n} A_{j}|.\nonumber\] Thus \[\eqalign{ |\bigcup_{j=1}^{n} A_{j}|&< n-l+|\bigcup_{j=1}^{l} A_{i_j}|\cr &< |\bigcup_{j=1}^{n-1} A_{j}|+1\cr &=|\bigcup_{j=1}^{n} A_{j}|+1.\cr }\nonumber\] This means that there is an integer strictly between two consecutive integers, a contradiction. This completes the proof.
While this theorem provides a method to calculate the size of a maximum sdr, the method is hardly efficient: it requires looking at all possible collections of the sets. It also does not provide a way to find an actual sdr, that is, the actual representatives. We will fix these problems in the last two sections of this chapter.