# Design and Analysis of Systematic Batched Network Codes
## Appendix A Proofs Regarding Recoverability of Message Packets
As \(\mathbf{X}\) and \(S\) are independent given \(\mathbf{H}^{u+}\) and \(\mathbf{Y}^{u+}\), we obtain  
\[P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+},s) =\frac{P(\mathbf{x},s|\mathbf{y}^{+},\mathbf{h}^{+})}{P(s|\mathbf{ y}^{+},\mathbf{h}^{+})}\] \[=\frac{P(s|\mathbf{y}^{+},\mathbf{h}^{+})P(\mathbf{x}|\mathbf{y}^ {+},\mathbf{h}^{+})}{P(s|\mathbf{y}^{+},\mathbf{h}^{+})}\] \[=P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+}).\qed\]  
Proof of Proposition 5.: For convenience, we omit the subscripts of \(\mathbf{H}^{u}\), \(\Phi^{u}\) and \(\mathbf{E}^{u}\). Assume that \(\mathbf{H}\in\mathbb{F}_{q}^{M\times N_{u}}\) is fixed with \(\text{rank}(\mathbf{H})\ =\ r\) and \(\mathbf{e}_{i}\in\text{Col}(\mathbf{H})\). Since \(\text{rank}(\mathbf{H})\ =\ r\), and \(\mathbf{e}_{i}\in\text{Col}(\mathbf{H})\), we can extend \(\{\mathbf{e}_{i}\}\) to a basis of \(\text{Col}(\mathbf{H})\), denoted by \(\mathbf{W}\). Then, there exists a full row rank matrix \(\mathbf{C}\in\mathbb{F}_{q}^{r\times N_{u}}\) such that \(\mathbf{H}=\mathbf{W}\mathbf{C}\) and \(\mathbf{H}^{u+}=\mathbf{W}\mathbf{C}\Phi\mathbf{E}\). Let \(\Phi^{*}=\Phi\mathbf{E}\); then, \(\Phi^{*}\) is an \(N_{u}\times N_{u+}\) uniformly random matrix. Notice that \(\mathbf{C}\) is full row rank, and \(\mathbf{C}\) can be written as \(\mathbf{C}=\mathbf{K}\mathbf{C}^{\prime}\), where \(\mathbf{C}^{\prime}\) is an invertible matrix with the first \(r\) rows being \(\mathbf{C}\) and \(\mathbf{K}\) is made up of the first \(r\) rows of an identity matrix. Since \(\mathbf{C}^{\prime}\Phi^{*}\) is still an \(N_{u}\times N_{u+}\) uniformly random matrix, we have that \(\mathbf{C}\Phi^{*}\) is an \(r\times N_{u+}\) uniformly random matrix. In the following, we let \(\mathbf{M}=\mathbf{C}\Phi^{*}\) and we have \(\mathbf{e}_{i}\in\text{Col}(\mathbf{H}^{u+})\) if and only if \(\mathbf{e}_{1}\in\text{Col}(\mathbf{M})\). Let \(\mathbf{m}^{T}\) be the first row of \(\mathbf{M}\) and \(\tilde{\mathbf{M}}\) be the submatrix of \(\mathbf{M}\) with the first row removed. Then, \(\mathbf{e}_{1}\in\text{Col}(\mathbf{M})\) is equivalent to \(\exists\mathbf{x}\) s.t. \(\tilde{\mathbf{M}}\mathbf{x}=\mathbf{0},\mathbf{m}^{T}\mathbf{x}\
eq 0\); in other words, \(\mathbf{m}\
ot\perp\text{Null}(\tilde{\mathbf{M}})\). When \(\tilde{\mathbf{M}}\) has rank \(k\), the null space of \(\tilde{\mathbf{M}}\) has dimension \(N_{u+}-k\). The probability \(\mathbf{m}\
ot\perp\text{Null}(\tilde{\mathbf{M}})\) is \(1-\frac{k}{q^{N_{u+}}}\). Therefore, the probability \(\mathbf{e}_{1}\in\text{Col}(\mathbf{M})\) is:  
\[P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+},\phi) =\frac{P(\mathbf{x})P(\mathbf{h}^{+},\phi)}{P(\mathbf{y}^{+}, \mathbf{h}^{+},\phi)}\]0 \[P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+},\phi) =\frac{P(\mathbf{x})P(\mathbf{h}^{+},\phi)}{P(\mathbf{y}^{+}, \mathbf{h}^{+},\phi)}\]1  
Observe that  
\[P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+},\phi) =\frac{P(\mathbf{x})P(\mathbf{h}^{+},\phi)}{P(\mathbf{y}^{+}, \mathbf{h}^{+},\phi)}\]2 \[P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+},\phi) =\frac{P(\mathbf{x})P(\mathbf{h}^{+},\phi)}{P(\mathbf{y}^{+}, \mathbf{h}^{+},\phi)}\]3 \[P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+},\phi) =\frac{P(\mathbf{x})P(\mathbf{h}^{+},\phi)}{P(\mathbf{y}^{+}, \mathbf{h}^{+},\phi)}\]4 \[P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+},\phi) =\frac{P(\mathbf{x})P(\mathbf{h}^{+},\phi)}{P(\mathbf{y}^{+}, \mathbf{h}^{+},\phi)}\]5  
Since \(\sum_{i=0}^{N_{u_{+}}-1}(1-q^{-r+1+i})\to 1\) as \(q\to\infty\), \(\Pr(\mathbf{e}_{1}\in\text{Col}(\mathbf{M}))\to 0\), as \(q\to\infty\).