Proof of the main result

We are now in a position to proceed with
the proof of Theorem 3.6.
Part of this proof involves tedious calculations which are
needed to establish the tight bound, and we delegate these
to the Appendix B.
The proof is by induction on the length *n* of the code.
Thus we first transform (3.6) into the form:

that is more conducive to induction on

As the induction basis, we may consider codes of length *n* = 2,
for which the bound of Theorem 3.6 holds trivially. As the
induction hypothesis, we assume that the minimum distance
of every cycle-free linear code of length *n'* < *n* satisfies
the bound of Theorem 3.6.

The induction step is established as follows. Let
be an (*n*, *k*, *d* ) cycle-free binary linear code. We may
assume that
2*k**n* - 1, since for *k* = 1 the
bound of (3.9) reduces to *d**n*, while if *k* = *n*
then *d* = 1 and (3.9) obviously holds with equality.

By Lemma 3.9, there exists an
*r*×*n* cycle-free
parity-check matrix
*H* = *A*|_{s}*B* for
,
which is in reduced canonical form. If *s* = *r*
then the induction step follows immediately from Lemma 3.10.
Otherwise, Lemma 3.8 implies that either
() or (**) is true. Observe that case () of Lemma 3.8 does not
occur, since by the definition of a reduced canonical form,
the matrix ***A* does not have rows of weight 2.
Furthermore, both
() and (**) imply that
***A* contains at least two identical columns
of weight one. Let *i* and *j* denote the positions
at which these two columns are found in *A*. Further,
let *w*_{i} and *w*_{j} denote the weight of the corresponding
columns of *B* and we denote
*w* = *w*_{i} + *w*_{j} + 2.

It follows from the canonical form structure of
*H* = *A*|_{s}*B*
that the *i*-th bit, respectively *j*-th bit, of
is repeated *w*_{i} times, respectively *w*_{j} times,
in the last *n*-*s* positions.
Further observe that the sum of the *i*-th and the *j*-th columns
of *H* together with the corresponding *w*_{i} + *w*_{j} columns of
the identity matrix produces the all-zero *r*-tuple.
Hence there is a codeword of weight
*w* = *w*_{i} + *w*_{j} + 2
in
and *d**w*.

We now shorten
at positions *i* and *j* to obtain
an
(*n'*, *k'*, *d'*) code
. That is, we consider the
subcode of
consisting of all the codewords that
are zero on positions *i* and *j*
and define
to be the code obtained by puncturing out the
*w*_{i} + *w*_{j} + 2 zero positions in this subcode.
Notice that shortening
at positions *i* and *j*
is equivalent to deleting
*w*_{i} + *w*_{j} + 2 columns of *H*
and *w*_{i} + *w*_{j} rows of *H*, as illustrated in Figure 3.5.
It is easy to see that the parameters of the resulting code
satisfy

Furthermore, since

It follows that
is a cycle-free code of length *n'* < *n*,
and we can invoke the induction hypothesis.
We distinguish between two cases.

**Case1.**-
*n'*+ 1 0 mod (*k'*+ 1)In this case, the induction hypothesis implies that . Taking into account the relations (3.10) between the parameters of and , we obtain

where the third inequality follows from the fact that*d**w*. It is shown in Appendix B that the relation between*n*,*k*, and*d*in (3.11) implies (3.9). **Case2.**-
*n'*+ 1 0 mod (*k'*+ 1)We again apply the induction hypothesis. Notice that in this case, the upper bound of Theorem 3.6 may be re-written as

where (

*n'*+ 1)/(*k'*+ 1) is a positive integer. Suppose that*d**d'*is an even integer. Then, since the right-hand side of (3.12) is an odd integer, we have

where the second inequality in (3.13) follows from (3.10) along with the fact that

*d**w*. It is shown in Appendix B that (3.13) implies (3.9).Now suppose that

*d*is odd. In this case, the bound of (3.12) does not suffice to establish (3.9), and we need to use the additional structure present in statements () and (**) of Lemma 3.8. Suppose that () is true, and the matrix***A*contains three identical columns of weight one, at positions ,,. Let*w*_{},*w*_{},*w*_{}denote the weight of the corresponding columns of*B*. Notice that at least one of*w*_{}+*w*_{},*w*_{}+*w*_{},*w*_{}+*w*_{}is an even integer. Hence we can choose the two positions*i*and*j*in Figure 3.5 from the three positions ,,, in such a way that*w*=*w*_{i}+*w*_{j}+ 2 is even. Since*d**w*and*d*is odd, it follows that*d**w*- 1. In conjunction with (3.12), we thus obtain

It is shown in Appendix B that if

*d*is odd, then (3.14) implies (3.9). Now suppose that (**) is true, and the matrix***H*contains a row of weight three, with the three * at positions*h*,*i*,*j*. Then after deleting*w*_{i}+*w*_{j}+ 2 columns of*H*and*w*_{i}+*w*_{j}rows of*H*as illustrated in Figure 3.5, we are left with a row of weight one, with the single * at position*h*. This means that the*h*-th position in is entirely zero; this position can be punctured-out without decreasing the dimension or the minimum distance. We thus obtain an (*n*^{*},*k*^{*},*d*^{*}) code , with*n*^{*}=*n'*- 1,*k*^{*}=*k'*, and*d*^{*}=*d'*. Applying the induction hypothesis to , we get

where the second inequality follows from the fact that if

*n'*+ 1 0 mod (*k'*+ 1) then*n*^{*}+ 1 0 mod (*k*^{*}+ 1). The right-hand side of (3.15) is the same as relation (3.11), which was already considered in Case1.