I am trying to show that the 2 codes generated by reciprocal generators of the perfect Golay Code are equivalent and I don't know how to proceed. Raymond Hill's "A First Course in Coding Theory" just mentions it in a sentence with no explanation, so perhaps it is something very trivial that I cannot see.
The perfect Golay code is a [23,12,7]-cyclic code, and the factorisation of $x^{23}+1$ is
$$(x+1)\cdot(x^{11}+x^9+x^7+x^6+x^5+x+1)\cdot(x^{11}+x^{10}+x^6+x^5+x^4+x^2+1).$$
The 2 larger factors are reciprocal and will produce equivalent codes. But how can I prove that?
Best Answer
Well, let $g(x)=g_kx^k+\ldots+g_1x +g_0$ be the generator polynomial of a linear code. Then the reciprocal polynomial is $h(x)=g_0x^k+g_1x^{k-1} + \ldots + g_{k-1}x+g_k$.
The generator matrix $G$ for the code generated by $g(x)$ is
$\begin{pmatrix} g_k & g_{k-1} & \ldots & g_1 & g_0 & 0 & \ldots &\ldots & 0 \\ 0 & g_k & g_{k-1} & \ldots & g_1 & g_0 & 0 &\ldots & 0\\ \vdots\\ 0 & 0 &\ldots & 0 & g_k & g_{k-1} & \ldots & g_1 & g_0\\ \end{pmatrix}$
The generator matrix $H$ for the code generated by $h(x)$ is
$\begin{pmatrix} g_0 & g_1 & \ldots & g_{k-1} & g_k & 0 & \ldots &\ldots & 0 \\ 0 & g_0 & g_1 & \ldots & g_{k-1} & g_k & 0 &\ldots & 0\\ \vdots\\ 0 & 0 &\ldots & 0 & g_0 & g_1 & \ldots & g_{k-1} & g_k\\ \end{pmatrix}$
Now permute the rows of this matrix:
$\begin{pmatrix} 0 & 0 &\ldots & 0 & g_0 & g_1 & \ldots & g_{k-1} & g_k\\ \vdots\\ 0 & g_0 & g_1 & \ldots & g_{k-1} & g_k & 0 &\ldots & 0\\ g_0 & g_1 & \ldots & g_{k-1} & g_k & 0 & \ldots &\ldots & 0 \\ \end{pmatrix}$
This matrix generates the same code as $H$ since the rows generate the code and so row permutations don't change the code.
Now one can see that the first and last matrix contain the same columns up to a permutation such that the codes are (permutation-) equivalent, i.e., they are equal up to a column permutation.