Definition 5. Let H be a Boolean hypothesis space family. Denote the n - m *matrices over the* input space X by X(n;m)*. For each* x 2 X(n;m)and H 2 H *, define* Hjx to be the set of (binary)
matrices,

$${\mathcal{H}}_{|\mathbf{x}}:={\left\{\left[\begin{array}{l l l}{h_{1}\left(x_{11}\right)}&{\ldots}&{h_{1}\left(x_{1m}\right)}\\ {\vdots}&{\ddots}&{\vdots}\\ {h_{n}\left(x_{n\,1}\right)}&{\ldots}&{h_{n}\left(x_{n m}\right)}\end{array}\right]}:\,h_{1},\ldots,h_{n}\,\in{\mathcal{H}}\right\}.$$

Define

$$\mathbb{H}_{|\mathbf{x}}:=\bigcup_{\mathcal{H}\in\mathbb{H}}{\mathcal{H}}_{|\mathbf{x}}.$$

Now for each n > 0; m > 0*, define* H (n; m) by

$$\Pi_{\mathbb{H}}\left(n,\,m\right):=\operatorname*{max}_{\mathbf{x}\in X^{\left(n\,,m\,\right)}}\left|\mathbb{H}|\mathbf{x}\right|.$$

_Note that $\Pi_{\pm}(n,m)\leq2^{nm}$. If $|\Pi|_{\bf x}|$,
 = 2nm *we say* H **shatters** the matrix x. For each n > 0 let

$$\mathbb{H}|\mathbf{x}|=2^{n m}$$
$$d_{\,\mp}(n\,):=\,\operatorname*{max}\{m:\,\Pi_{\,\mp}\left(n\,,\,m\right)\,=\,2^{n\,m}\}.$$

Define

$$\begin{array}{l}{{\overline{{{d}}}(\mathbb{H}):=\mathrm{VCdim}(\mathbb{H}^{1})\quad a n d}}\\ {{\underline{{{d}}}(\mathbb{H}):=\operatorname*{max}_{\mathcal{H}\in\mathbb{H}}\mathrm{VCdim}(\mathcal{H}).}}\end{array}$$

Lemma 10.

$$\overline{d}(\mathbb{H})\geq\underline{d}(\mathbb{H})$$ $$d_{\mathbb{H}}(n)\geq\max\left\{\left|\frac{\overline{d}(\mathbb{H})}{n}\right|,\underline{d}(\mathbb{H})\right\}\geq\frac{1}{2}\left(\left|\frac{\overline{d}(\mathbb{H})}{n}\right|+\underline{d}(\mathbb{H})\right)$$  nequality is trivial from the definitions. To get the second term 

Proof. The first inequality is trivial from the definitions. To get the second term in the maximum in the second inequality, choose an H 2 H with VCdim(H) = d(H ) and construct a matrix x 2 X(n;m) whose rows are of length d(H ) and are shattered by H. Then clearly H shatters x. For the first term in the maximum take a sequence x = (x1; : : : ; xd(H )

) shattered by H 1(the hypothesis space consisting of the union over all hypothesis spaces from H ), and distribute its elements equally among the rows of x (throw away any leftovers). The set of matrices

$$\left\{\left[\begin{array}{c c c}{{h\big(x_{11}\big)}}&{{\cdot\cdot\cdot}}&{{h\big(x_{1m}\big)}}\\ {{\vdots}}&{{\cdot\cdot\cdot}}&{{\vdots}}\\ {{h\big(x_{n1}\big)}}&{{\cdot\cdot\cdot}}&{{h\big(x_{n m}\big)}}\end{array}\right]:h\in\mathbb{H}^{1}\right\}.$$

$${\mathrm{where~}}m\,=\,\lfloor{\overline{{d}}}(\,\mathbb{H}\,)/n\rfloor$$

where m = bd(H )=n is a subset of H jx and has size 2nm. Lemma 11.

H (n; m)   em dH (n) ndH(n)

173