# Greedy Algorithm that does not produce a linear Code.

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.]

-
I don't know what you mean by "the greedy algorithm" in this context. – Gerry Myerson Dec 6 '13 at 4:38
What I mean of greedy algorithm , is to construct a code in which first we have only 0 ( as a vector) , and later add another ( with some kind of condition till the code will be completed. for example in the construction of lexicode we use greedy algorithm . – henry Dec 6 '13 at 4:48
The greedy algorithm is to always pick the first answer you can, and never change it later if you find it was wrong. I'm guessing you have been asked to construct a code with some properties (what are they?). In this case, the greedy algorithm would be to choose the codewords one by one, choosing for each one the earliest (in some list) that does not spoil the properties of the code. I cannot give a better answer without knowing the properties of the code that the question as asked for. – apt1002 Dec 6 '13 at 4:49
"with some kind of condition" "until the code is completed" If you don't have a more precise understanding than that of what the greedy algorithm is, I don't think it will be possible to answer your question. – Gerry Myerson Dec 6 '13 at 4:49
Thanks @GerryMyerson for your kind advice. I gave the definition of greedy algorithm based on lexicode ( first time I see greedy algorithm ).and Yes in construction lexicdoe we use greedy algorithm and we have condition to add the next vector to zero vector and we will not stop until the code is complete ( Repeat the algorithm until there are not more vectors in the lexicographic list to look at this is what the book say ). – henry Dec 6 '13 at 5:19

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.

-
Not so fast. If the next word on the list would be $01000$ it would not be rejected. After all, it is at a Hamming distance two from the (so far) only included word $10000$. So it is possible that the resulting code has words beginning with a $0$ Try again! Write the 32 words in some order, and follow the greedy algorithm. Observe the code you end up with. Can you tell at a glance that it is not linera? – Jyrki Lahtonen Dec 6 '13 at 16:11