Mathematics 392 – Seminar in Coding Theory Selected Solutions – Problem Set 2

B) The main point to address here is why the minimum weight of a nonzero word in a linear code is the same as the minimum distance. Here is one argument: Let’s write w = min_{x≠0} wt(x) for the minimum weight of a nonzero codeword in C. Let x_{0}, y_{0} ∈ C with d = d(x_{0}, y_{0}). Then we have

d = d(x_{0}, y_{0}) = wt(x_{0} + y_{0}) ≥ w

because x_{0} + y_{0} ≠ 0 is a word in C. Hence d ≥ w. On the other hand, if wt(z_{0}) = w, then

w = wt(z_{0}) = d(z_{0}, 0) ≥ d.

Since d ≥ w and w ≥ d, we must have d = w.

F) We must analyze the number of ways to choose the vectors in a basis {v_{1}, v_{2}, …, v_{k}} in C. Choosing the vectors v_{i} in turn, v_{1} can be any nonzero vector, so there are 2^{k} − 1 = 2^{k} − 2^{0} choices for v_{1}. Once v_{1} is chosen, then to get a linearly independent set, v_{2} can be any vector other than 0, v_{1}. Similarly, once the first i − 1 vectors are chosen, to get a linearly independent set, v_{i} can be any vector not in the span of v_{1}, …, v_{i−1}. There are 2^{i−1} such vectors, so 2^{k} − 2^{i−1} choices for v_{i}, given v_{1}, …, v_{i−1}. We multiply these to get the total number of ways to choose the vectors in a basis:

(2^{k} − 2^{0})(2^{k} − 2^{1}) ⋯ (2^{k} − 2^{k−1}) = ∏_{i=0}^{k−1}(2^{k} − 2^{i})

But now each basis is a set (unordered). In choosing our vectors, we will have selected a given set of k basis vectors in every possible ordering, so we will have found each basis a total of k! different times. The total number of distinct bases is

\frac{1}{k!} ∏_{i=0}^{k−1}(2^{k} − 2^{i})

which is what we had to show.