Cory Patrick

2022-06-24

Show that the matrix is a generator matrix of a MDS code
Let ${a}_{1},\dots ,{a}_{n}$ be pairwise distinct elements of ${\mathbb{F}}_{q}$ and $k\le n$. I have to show that
1. The matrix $\left[\begin{array}{cccc}1& \dots & 1& 0\\ {a}_{1}& \dots & {a}_{n}& 0\\ {a}_{1}^{2}& \dots & {a}_{n}^{2}& 0\\ ⋮& & ⋮& 0\\ {a}_{1}^{k-1}& \dots & {a}_{n}^{k-1}& 1\end{array}\right]$ is a generator matrix of an $\left[n+1,k,n-k+2\right]$ MDS code.
2. if q is a power of 2, then the matrix $\left[\begin{array}{ccccc}1& \dots & 1& 0& 0\\ {a}_{1}& \dots & {a}_{q}& 1& 0\\ {a}_{1}^{2}& \dots & {a}_{q}^{2}& 0& 1\end{array}\right]$ is a generator matrix of an $\left[q+2,3,q\right]$ 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 $\left(n-k\right)×\left(n-k\right)$ full size minors of H are invertible
3. All $k×k$ full size minors og G are invertibleMaybe 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\left(C\right)=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?

Jovan Wong

Expert

Step 1
Use characterization (3) of your theorem and remember the formula for the determinant of a Vandermonde matrix!
Step 2
Come up with different cases for the $k×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 $\left[q+2,3\right]$ MDS code, there are cases without Vandermonde. But here, the minors are of fixed size $3×3$, so just approach those cases by a direct computation of the determinant.

Do you have a similar question?