Show that the matrix is a generator matrix of a MDS code

abstract-algebracoding-theorydiscrete mathematicsfinite-fieldsmatrices

Let $a_1,\dots,a_n$ be pairwise distinct elements of $\mathbb{F}_q$ and $k ≤ n$. I have to show that

  1. the matrix $\begin{bmatrix}1&\dots&1&0\\a_1&\dots&a_n&0\\a_1^2&\dots&a_n^2&0\\\vdots&&\vdots&0\\a_1^{k-1}&\dots&a_n^{k-1}&1\end{bmatrix}$ is a generator matrix of an $[n+1,k,n−k+2]$ MDS code.

  2. if q is a power of 2, then the matrix $\begin{bmatrix}1&\dots&1&0&0\\a_1&\dots&a_q&1&0\\a_1^2&\dots&a_q^2&0&1\end{bmatrix}$ is a generator matrix of an $[q + 2, 3, q]$ MDS code.

I don't even know where to start, the things we covered in the lecture are not so many, but what I thought could be useful, but don't know how to apply are:

Theorem: Let $C$ be an $[n,k]$ code with generator matrix $G$ and parity check matrix $H$. The following are equivalent:

  1. $C$ is MDS
  2. All $(n-k)\times(n-k)$ full size minors of $H$ are invertible
  3. All $k\times k$ full size minors og G are invertible

Maybe I could use this theorem, part (3), but I'm not sure how to show that all the minors og G are invertible.

Should I maybe, from definition of MDS, show that the distance is indeed $d(C)=n-k+2$, and then conclude that the code is MDS? But aren't the elements arbitrary?

Should I maybe look for a parity check matrix $H$ and do something?

Please any hint is appreciated.

Best Answer

Hint

Use characterization (3) of your theorem and remember the formula for the determinant of a Vandermonde matrix!

Hint (2)

Come up with different cases for the $k\times k$ minor, depending on the number of the involved "special" columns (the 1 or 2 rightmost columns of the generator matrix). Then, you can either directly apply Vandermonde or you have to do some transformation first.

For the second case of the $[q+2,3]$ MDS code, there are cases without Vandermonde. But here, the minors are of fixed size $3\times 3$, so just approach those cases by a direct computation of the determinant.

Related Question