exactly one row of ${{\cal M}}'$. Since ${{\cal M}}'$ has $q$ rows, it follows that there exists at least one row which share no linearly dependent entry with the first row of ${{\cal M}}$. The $\beta$ of such a row is the required $\beta$ for $M_2$.

The two matrices $M_1$ and $M_2$ are linearly independent. In fact, for each $i$, $1 \leq i \leq q+1$, the $i$-th columns of the two matrices are linearly independent. Hence, the linear span of $M_1$ and $M_2$ form a linear subspace of dimension two and for the each $i$, $1 \leq i \leq q+1$, the $i$-th columns of al matrices in the code are distinct.

Next, we consider all matrices which are candidates for the extension code. This set of candidates consists of all the $q^4$ distinct $2 \times (q+1)$ matrices over ${{\mathbb{F}}}_q$. If $v_1,v_2,\ldots , v_{q+1}$ are the $q+1$ consecutive columns of such a matrix, then for each $i$, $3 \leq i \leq q+1$, $v_i = \alpha^{i-3} v_1 + v_2$. This set of matrices is clearly a linear subspace which will be called the *extension space*. Since the entries of the first two column vectors can be chosen arbitrarily, it follows that there 