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:

$$\le \left\{\vphantom{ \begin{array}{l@{\hspace{6ex}}l} \displaystyle ... ...if\hspace{3.5ex} $n+1 \equiv 0$\ ~mod~ $(k+1)$}\\ [2.0ex] \end{array} }\right. \begin{array}{l@{\hspace{6ex}}l} \displaystyle {2 \left\lfloor{n ... ...text{\rm if\hspace{3.5ex} $n+1 \equiv 0$\ ~mod~ $(k+1)$}\\ [2.0ex] \end{array}$$ (9)

that is more conducive to induction on n. It can be easily seen with simple algebraic manipulation that equations (3.6) and (3.9) are equivalent.

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 $\ensuremath{\mathbb{C}}$ be an (n, k, d ) cycle-free binary linear code. We may assume that 2$\le$k$\le$n - 1, since for k = 1 the bound of (3.9) reduces to d$\le$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|_sB for $\ensuremath{\mathbb{C}}$, 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 ($\Diamond$) or ($\star$) is true. Observe that case ($\bullet$) 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 $\le$2. Furthermore, both ($\Diamond$) and ($\star$) 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|_sB that the i-th bit, respectively j-th bit, of $\ensuremath{\mathbb{C}}$ 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 $\ensuremath{\mathbb{C}}$ and d$\le$w.

We now shorten $\ensuremath{\mathbb{C}}$ at positions i and j to obtain an (n', k', d') code $\ensuremath{\mathbb{C}}'$. That is, we consider the subcode of $\ensuremath{\mathbb{C}}$ consisting of all the codewords that are zero on positions i and j and define $\ensuremath{\mathbb{C}}'$ to be the code obtained by puncturing out the w_i + w_j + 2 zero positions in this subcode. Notice that shortening $\ensuremath{\mathbb{C}}$ 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 $\ensuremath{\mathbb{C}}'$ satisfy

$$\ge \ge$$ (9)

Furthermore, since H is cycle-free by assumption, the parity-check matrix for $\ensuremath{\mathbb{C}}'$ which results by deleting rows and columns of H is also cycle-free.

Figure: Deleting rows and columns of H = A|_sB to shorten a cycle-free code.

It follows that $\ensuremath{\mathbb{C}}'$ is a cycle-free code of length n' < n, and we can invoke the induction hypothesis. We distinguish between two cases.

Case1.

n' + 1 $\not\equiv$ 0  mod  (k' + 1)

In this case, the induction hypothesis implies that $d' \le 2 \mbox{\ensuremath{\lfloor {n'/(k'\!+\!1)} \rfloor}}$. Taking into account the relations (3.10) between the parameters of $\ensuremath{\mathbb{C}}$ and $\ensuremath{\mathbb{C}}'$, we obtain

$$\le \left\lfloor\vphantom{{n' \over k'+1}}\right. {n' \over k'+1} \left.\vphantom{{n' \over k'+1}}\right\rfloor \le \left\lfloor\vphantom{{n - w \over k-1}}\right. {n - w \over k-1} \left.\vphantom{{n - w \over k-1}}\right\rfloor \le \left\lfloor\vphantom{{n - d \over k-1}}\right. {n - d \over k-1} \left.\vphantom{{n - d \over k-1}}\right\rfloor$$ (9)

where the third inequality follows from the fact that d$\le$w. It is shown in Appendix B that the relation between n, k, and d in (3.11) implies (3.9).

Case2.

n' + 1 $\equiv$ 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

$$\le {2 \left\lfloor{n' \over k'+1}\right\rfloor + 1} {n'+1 \over k'+1}$$ (9)

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

$$\le {n'+1 \over k'+1} \le {n-d+1 \over k-1}$$ (9)

where the second inequality in (3.13) follows from (3.10) along with the fact that d$\le$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 ($\Diamond$) and ($\star$) of Lemma 3.8. Suppose that  ($\Diamond$) is true, and the matrix A contains three identical columns of weight one, at positions $\alpha$,$\beta$,$\gamma$. Let w_$\alpha$, w_$\beta$, w_$\gamma$ denote the weight of the corresponding columns of B. Notice that at least one of w_$\alpha$ + w_$\beta$, w_$\alpha$ + w_$\gamma$, w_$\beta$ + w_$\gamma$ is an even integer. Hence we can choose the two positions i and j in Figure 3.5 from the three positions $\alpha$,$\beta$,$\gamma$, in such a way that w = w_i + w_j + 2 is even. Since d$\le$w and d is odd, it follows that d$\le$w - 1. In conjunction with (3.12), we thus obtain

$$\le {n'+1 \over k'+1} \le {n-w+1 \over k-1} \le {n - d \over k-1}$$ (9)

It is shown in Appendix B that if d is odd, then (3.14) implies (3.9). Now suppose that ($\star$) 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 $\ensuremath{\mathbb{C}}'$ 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 $\ensuremath{\mathbb{C}}^*$, with n^* = n' - 1, k^* = k', and d^* = d'. Applying the induction hypothesis to $\ensuremath{\mathbb{C}}^*$, we get

$$\le \le \left\lfloor\vphantom{{n^* \over k^*+1}}\right. {n^* \over k^*+1} \left.\vphantom{{n^* \over k^*+1}}\right\rfloor \le \left\lfloor\vphantom{{n - w -1 \over k-1}}\right. {n - w -1 \over k-1} \left.\vphantom{{n - w -1 \over k-1}}\right\rfloor \le \left\lfloor\vphantom{{n - d \over k-1}}\right. {n - d \over k-1} \left.\vphantom{{n - d \over k-1}}\right\rfloor$$ (9)

where the second inequality follows from the fact that if n' + 1 $\equiv$ 0 mod (k' + 1) then n^* + 1 $\not\equiv$ 0 mod (k^* + 1). The right-hand side of (3.15) is the same as relation (3.11), which was already considered in Case1.

It remains to consider the case where $\ensuremath{\mathbb{C}}' = \{{\bf0}\}$, namely k' = 0. But in this case k$\le$2 in view of (3.10), and the upper bound of Theorem 3.6 follows directly from the Griesmer bound [42, p.547]. Since we have now exhausted all the possibilities, this establishes the induction step and completes the proof of Theorem 3.6.