# Question about block erasure codes

I have a question about linear block erasure codes that are described in this paper. I briefly describe the idea behind the linear erasure codes and then I ask my question.

Given a set $d=\langle x_i \in GF(2^q)|i=1,\cdots,k\rangle$ of data packets, the general idea of (systematic) erasure codes is to generate $n-k$ extra packets $e=\langle y_j \in GF(2^q)|j=1,\cdots,n-k\rangle$, such that given any $k$ packets out of the set $\{x_1,\cdots,x_k,y_1,\cdots,y_{n-k}\}$ one is able to decode the original set $d$.

To generate the extra packets, we consider an $(n-k) \times n$ generator matrix $G'$ and compute $e=G'd$.

The paper claims that if the rows of the generator matrix are selected from a Vandermonde matrix:

$$V=\begin{bmatrix} 1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{k-1}\\ 1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{k-1}\\ 1 & \alpha_3 & \alpha_3^2 & \dots & \alpha_3^{k-1}\\ \vdots & \vdots & \vdots & \ddots &\vdots \\ 1 & \alpha_m & \alpha_m^2 & \dots & \alpha_m^{k-1} \end{bmatrix}$$ where $\alpha_i \in GF(2^q)$ then the computed vector $e$ has the desired property.

Now my question: Assume $n-k=2$, i.e., any loss of 2 packets can be recovered. Let, $$G'=\begin{bmatrix} 1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{k-1}\\ 1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{k-1} \end{bmatrix}$$

By definition of the erasure codes, the submatrix consisting of any two columns of the matrix $G'$ must have rank 2. But we know that for $\alpha_1, \alpha_2 \in GF(2^q)$ and $\alpha_1 \neq \alpha_2$, we may have $\alpha_1^s = \alpha_2^s$ for some $s$. It means that the matrix

$$\begin{bmatrix} 1 & \alpha_1^s \\ 1 & \alpha_2^s \end{bmatrix}$$ has rank 1 rather than 2. So, it means that if packets $x_1$ and $x_{s+1}$ are lost, they cannot be recovered using the set $e$. Generally, the fact that an $m\times m$ Vandermonde matrix is non-singular, does not mean that any submatrix of it has full rank, does it?

Did I misunderstood the concept or is it the fault of the paper?

• A matrix being nonsingular does not imply that all its submatricies are nonsingular. Here is a simple counterexample: consider a $4\times 4$ identity matrix; it is nonsingular. However, if we consider the $2\times 2$ matrix in the upper right corner, that consists of all 0's, and so is obviously singular. I'm not certain how that pertains to block erasure codes (I do cryptography, not coding theory), however that at least is one statement you made which is not true. – poncho May 30 '14 at 22:41
• That's right. My question is that some losses of size $n-k$ (=2 in my example) are not recoverable because the rank of some of the subsets of size $n-k$ of the columns of the $G'$ matrix is not $n-k$. – Helium May 30 '14 at 22:52