Let $a_1,\dots,a_n$ be pairwise distinct elements of $\mathbb{F}_q$ and $k ≤ n$. I have to show that
-
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.
-
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:
- $C$ is MDS
- All $(n-k)\times(n-k)$ full size minors of $H$ are invertible
- 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.