# Design and Analysis of Systematic Batched Network Codes
## Appendix A Proofs Regarding Recoverability of Message Packets  
**Proof of Proposition 1. ** For the sufficiency, if \(\mathbf{e}_{i}\) is a column of \(\mathbf{L}\), then \(\mathbf{e}_{i}\in\mathrm{Col}(\mathbf{L})=\mathrm{Col}(\mathbf{H}^{u})\). Now, we prove the necessity. If \(\mathbf{e}_{i}\in\mathrm{Col}(\mathbf{H}^{u})\), then \(\mathbf{e}_{i}\in\mathrm{Col}(\mathbf{L})\). Let \(r=\mathrm{rank}(\mathbf{H}^{u})\). By the property of reduced column echelon form, all the zero columns are on the right of the non-zero columns in \(\mathbf{L}\), and hence the first \(r\) columns are all the non-zero columns of \(\mathbf{L}\). Then, we can write \(\mathbf{e}_{i}=\sum_{j=1}^{r}c_{j}\mathbf{l}_{j}\), where \(c_{j}\) is a constant and \(\mathbf{l}_{j}\) is the \(j\)th non-zero column of \(\mathbf{L}\). For \(j=1,\ldots,r\), denote by \(i_{j}\) the row index of the leading 1 of \(\mathbf{l}_{j}\), which must exist due to the property of reduced column echelon form. Further, as the \((i_{j},j)\) entry is the only non-zero entry on the \(i_{j}\)th row of \(\mathbf{L}\), \(c_{j}=0\) for \(j\) such that \(i_{j}\
eq i\). If there exists no \(j\) such that \(i_{j}=i\), then \(\mathbf{e}_{i}=\mathbf{0}\), a contradiction. Therefore, there must a unique \(j^{*}\) such that \(i_{j^{*}}=i\), and hence \(\mathbf{e}_{i}=\mathbf{l}_{j^{*}}\). **Proof of Proposition 3. ** Denote by \(\mathbf{x}\), \(\mathbf{y}^{+}\), \(\mathbf{h}^{+}\) and \(\phi\) the instances of \(\mathbf{X}\), \(\mathbf{Y}^{u+}\), \(\mathbf{H}^{u+}\) and \(\Phi^{u}\), respectively. As \(P(\mathbf{x},\phi|\mathbf{y}^{+},\mathbf{h}^{+})=P(\phi|\mathbf{y}^{+}, \mathbf{h}^{+})P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+},\phi)\); to prove this claim, it is sufficient to show that  
\[P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+},\phi)=P(\mathbf{x}|\mathbf{y}^{+}, \mathbf{h}^{+}) \tag{1}\]  
for all instances \(\mathbf{x}\), \(\mathbf{y}^{+}\), \(\mathbf{h}^{+}\) and \(\phi\). If \(\mathbf{y}^{+}\
eq\mathbf{x}\mathbf{h}^{+}\), (1) holds as both sides are 0. Suppose that \(\mathbf{y}^{+}=\mathbf{x}\mathbf{h}^{+}\). As \(\mathbf{X},\mathbf{H}^{u},\Phi^{u}\) and \(\mathbf{E}^{u}\) are independent and \(\mathbf{H}^{u+}=\mathbf{H}^{u}\Phi^{u}\mathbf{E}^{u}\), we obtain  
\[P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+},\phi) =\frac{P(\mathbf{x})P(\mathbf{h}^{+},\phi)}{P(\mathbf{y}^{+}, \mathbf{h}^{+},\phi)}\] \[=\frac{P(\mathbf{x})P(\mathbf{h}^{+},\phi)}{\sum_{\mathbf{x}^{ \prime}:\mathbf{x}^{\prime}\mathbf{h}^{+}=\mathbf{y}^{+}}p(\mathbf{x}^{\prime })P(\mathbf{h}^{+},\phi)}\] \[=\frac{P(\mathbf{x})}{\sum_{\mathbf{x}^{\prime}:\mathbf{x}^{ \prime}\mathbf{h}^{+}=\mathbf{y}^{+}}p(\mathbf{x}^{\prime})}.\]  
Similarly,  
\[P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+}) =\frac{P(\mathbf{x})P(\mathbf{h}^{+})}{P(\mathbf{y}^{+},\mathbf{ h}^{+})}\] \[=\frac{P(\mathbf{x})P(\mathbf{h}^{+})}{\sum_{\mathbf{x}^{\prime }:\mathbf{x}^{\prime}\mathbf{h}^{+}=\mathbf{y}^{+}}p(\mathbf{x}^{\prime})P( \mathbf{h}^{+})}\] \[=\frac{P(\mathbf{x})}{\sum_{\mathbf{x}^{\prime}:\mathbf{x}^{ \prime}\mathbf{h}^{+}=\mathbf{y}^{+}}p(\mathbf{x}^{\prime})}.\]  
Therefore, (A1) holds when \(\mathbf{y}^{+}=\mathbf{x}\mathbf{h}^{+}\). The proof is completed. Proof of Proposition 4.: Denote by \(\mathbf{x}\), \(\mathbf{y}^{+}\), \(\mathbf{h}^{+}\) and \(s\) the instances of \(\mathbf{X}\), \(\mathbf{Y}^{u+}\), \(\mathbf{H}^{u+}\) and \(S\), respectively. It is sufficient to show that \(P(\mathbf{x}|\mathbf{y}^{+},\mathbf{h}^{+},s)=P(\mathbf{x}|\mathbf{y}^{+}, \mathbf{h}^{+})\) for all instances \(\mathbf{x},s,\mathbf{y}^{+},\mathbf{h}^{+}\). If \(\mathbf{y}^{+}\
eq\mathbf{x}\mathbf{h}^{+}\), the equality holds as both sides are \(0\). Suppose that \(\mathbf{y}^{+}=\mathbf{x}\mathbf{h}^{+}\).