Assuming
\begin{equation}
\beta \space \epsilon \space \mathbb{F}_{q} \backslash \{0\}
\end{equation}
with
\begin{equation}
\beta^n = 1 \space and \space \beta^i \ne 1 \space \forall i \space \epsilon \space \{1,…,n-1\}\\
\beta^0 \ne \beta^1 \ne \beta^2 … \ne \beta^{n-1}
\end{equation}
Given the parity check matrix of an [n,k] reed solomon code C
H:
\begin{pmatrix}
1 & 1 & 1 & … & 1 & 1\\
1 & \beta & \beta^2 & … & \beta^{n-2} & \beta^{n-1}\\
1 & \beta^2 & \beta^{4} & … & \beta^{2n-4} & \beta^{2n-2}\\
\vdots & & & \ddots\\
1 & \beta^{n-k-1} & \beta^{2n-2k-2} & … & \beta^{(n-k-1)\cdot(n-2)} & \beta^{(n-k-1)\cdot(n-1)}
\end{pmatrix}
How can I show, that
G:
\begin{pmatrix}
1 & \beta & \beta^2 & … & \beta^{n-2} & \beta^{n-1}\\
1 & \beta^2 & \beta^{4} & … & \beta^{2n-4} & \beta^{2n-2}\\
\vdots & & & \ddots\\
1 & \beta^{k-1} & \beta^{2k-2} & … & \beta^{(k-1)\cdot(n-2)} & \beta^{(k-1)\cdot(n-1)}
\end{pmatrix}
is the generator matrix of C?
I know that
\begin{equation}
G \cdot H^\intercal = 0
\end{equation}
and that the product of (assuming i is a row of the matrix)
\begin{equation}
G_i \cdot H_{i+1} = 0
\end{equation}
as they have the same elements.
How can I show this for the remaining multiplications?
I assume I have to show that all multiplications end in n unique elements, but do not know how.
Best Answer
The code that the OP is describing is a cyclic Reed-Solomon code whose generic codeword is the vector $[C_0, C_1, \ldots, C_{n-1}]$ corresponding to the codeword polynomial $\displaystyle C(x) = \sum_{i=0}^{n-1}C_ix^i$ (often also simply called the codeword instead of codeword polynomial by those steeped in cyclic code theory), and the parity check matrix that the OP provides is equivalent to the statement that $$C(\beta^i)=0 \text{ for } i = 0, 1, 2, \ldots, n-k-1. \tag{1}$$ Thus, every codeword $C(x)$ has $\beta^i, i = 0, 1, 2, \ldots, n-k-1$ among its roots or zeroes, and so every codeword $C(x)$ is a multiple of the generator polynomial of the code given by $$g(x) = \prod_{i=0}^{n-k-1}(x-\beta^i).$$
Now, with regard to the generator matrix of the cyclic Reed-Solomon code being described above, the form that the OP has written is a terrible one from the point of view of implementation as well as of understanding the theory, but no matter. Let's ask whether each row of the hypothesized $G$ is a codeword. If $\displaystyle C(x) = \sum_{i=0}^{n-1}(\beta^m)^ix^i$ is the alleged codeword corresponding to the $m$-th row of the hypothesized $G$ (note that $1 \leq m \leq k$), does it satisfy $(1)$? Well, for any $t, 0 \leq t \leq n-k-1$, \begin{align} C(\beta^t) &= \sum_{i=0}^{n-1}(\beta^m)^i(\beta^t)^i\\ &= \sum_{i=0}^{n-1}(\beta^{m+t})^i\\ &= \sum_{i=0}^{n-1}(\gamma)^i\\ &= \begin{cases} 0 & \text{if }~ t \neq n-m,\\ n & \text{if }~ t = n-m.\end{cases} \end{align} As $m$ ranges from $1$ to $k$, $n-m$ ranges from $n-1$ to $n-k$, and since $t$ is between $0$ and $n-k-1$, we see that $C(\beta^t) = 0$ for all $t, 0 \leq t \leq n-k-1$, and so $(1)$ holds: each row of the alleged $G$ is a codeword in the cyclic Reed-Solomon code. I will leave it to the OP to prove that the row space of $G$ has dimension $k$ so that $G$ is indeed a generator matrix of the $[n,k]$ cyclic Reed-Solomon code (i.e. that the rows of $G$ span the entire code, and not just a subcode.)