Greedy Algorithm that does not produce a linear Code.

Question

In a section of study of LexiCode this problem comes . Any help and hint appreciated.

Find an ordering of $\mathbf{F}_{2}^5$ so that the greedy algorithm does not produce a linear code

[Edit: Apparently the greedy algorithm is to produce a code of a chosen minimum Hamming distance.]

Answer 1

The only way the question makes any kind of sense is to interpret it in a way that allows us to also decide on an acceptance criterion. Proffering the following:

• Let the first vector on the ordering be $10000$.
• Assume that we are greedily constructing a code with minimum Hamming distance two. Meaning that the next word on the list is rejected if and only if it as at Hamming distacne less than two from a previously accepted word.
• With these assumptions in place the greedy algorithm will never produce a linear code, because ___ (you fill in the blank, or peek at the spoiler)

The word $00000$ will be rejected, when its turn comes. The zero vector belongs to all vector spaces, so a set without it is not a linear subspace.

There are other ways of achieving non-linearity, but the spoilerized way is the most obvious one. For example the famous $(16,256,6)$ Nordstrom-Robinson could be generated as a result of a greedy algorithm. But it is not included in any linear code of minimum distance six, so if the greedy acceptance criterion of insisting on such a high minimum distance is used, the output will not be a linear code.

---

As all of the above depends on me having correctly guessed what the question really is about (I'm not entirely convinced that the OP understood it the same way), let me illustrate this with a minimal example. This time the greedy algorithm is used to get us a code of length three and minimum Hamming distance two. First consider the lexicographic ordering $$ \begin{array}{c} 000\\001\\010\\011\\100\\101\\110\\111 \end{array} $$ Here the greedy algorithm will first accept $000$, then reject $001$ and $010$ for being too close, accept $011$, then reject $100$ for being too close $000$, accept $101$, accept $110$ and finally reject $111$. Thus we got the code $\{000,011,101,110\}$.

On the other hand with the ordering $$ \begin{array}{c} 100\\001\\010\\011\\000\\101\\110\\111 \end{array} $$ we first accept $100$, then accept $001$ and $010$ for neither is too close to the preceding ones. Then $011$ is rejected for being too close to $001$ and $000$ for being too close to $100$. In the end we still accept $111$, and thus end up with the code $\{100,001,010,111\}$ which is not closed under addition, and not linear.