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?
