The following lemma will be the basis for the induction in our proof of Theorem 3.6.

- .
- The matrix
*H*contains a row of weight two or less; - .
- The matrix
*H*contains three identical columns of weight one; **.**- The matrix
*H*contains two identical columns of weight one, and furthermore the row of*H*which contains the nonzero entries of these two columns has weight three.

**Proof. **
Let *T*(*H*) be the Tanner graph of *H*.
We now construct another graph , called the *row-graph*
of *H*, whose vertex set
*y*_{1}, *y*_{2},..., *y*_{r-s} corresponds to
the rows of *H*.
The edge set of is derived from the columns of *H*
of weight 2, so that a column of weight *w* in *H*
contributes *w* - 1 edges to .
An example illustrating the construction of the row-graph for
a
6×8 cycle-free matrix is depicted in Figure 3.3.

Specifically, there is
an edge between *y*_{i} and *y*_{j} in iff *i* < *j* and
there exists a column
(*a*_{1}, *a*_{2},..., *a*_{r-s})^{t} in *H*,
such that
*a*_{i} = *a*_{j} = 1 while
*a*_{i+1} = *a*_{i+2} = ^{ ... } = *a*_{j-1} = 0.
Notice that each such edge (*y*_{i}, *y*_{j}) in corresponds to
a path of length two in *T*(*H*): namely
(*y*_{i}, *x*_{p}),(*x*_{p}, *y*_{j}),
where *p* denotes the position at which the column
(*a*_{1}, *a*_{2},..., *a*_{r-s})^{t} is to be found in *H*.
It follows that if there is a cycle in , then there
is a cycle in *T*(*H*). Since *T*(*H*) is cycle-free, then
so is . As such, necessarily contains at least two vertices
of degree 1, in view of (3.2).
Let *y*^{*} be one such vertex in , and let
*a*^{*} = (*a*_{1}, *a*_{2},..., *a*_{n-s}) be the corresponding
row of *H*. If
, then () is true.
If
and
deg *y*^{*} = 0, then
() is true.
If
and
deg *y*^{*} = 1, then (**) is true.
Finally, if
, then
() is true,
regardless of whether
deg ***y*^{*} = 0 or
deg *y*^{*} = 1.

width4pt depth2pt height6pt

Let
be an (*n*, *k*, *d* ) cycle-free binary linear code, and let
*H* be an
*r*×*n* cycle-free parity-check matrix for
,
where *r* = *n* - *k*. We say that *H* is in *s*-*canonical form*
if this matrix has the following structure:

where all the rows of

Lemma 3.7 trivially generalizes to matrices in *s*-canonical
form.

- .
- The matrix
*A*contains a row of weight two or less; - .
- The matrix
*A*contains three identical columns of weight one; **.**- The matrix
*A*contains two identical columns of weight one, and furthermore the row of*H*which contains the nonzero entries of these two columns has weight three.

**Proof. **
Evidently *T*(*A*) is
a subgraph of *T*(*H*), obtained by retaining only the first
*n* - *s* symbol vertices
*x*_{1}, *x*_{2},..., *x*_{n-s}, the first
*r* - *s* check vertices
*y*_{1}, *y*_{2},..., *y*_{r-s}, and all the
edges between these vertices. Since *T*(*H*) is
cycle-free by assumption, so is *T*(*A*). Thus, Lemma 3.7
applies to complete the proof.

width4pt depth2pt height6pt

We will say that an
*r*×*n* matrix *H* is in *reduced canonical form*,
if
*H* = *A*|_{s}*B* and either *s* = *r* or all the rows of *A* have
weight 3. It is a non-trivial fact that every cycle-free parity-check matrix can be put into such a form.

**Proof. **
Let *H* be an arbitrary cycle-free parity-check matrix for
.
We first put *H* in *s*-canonical form, for the highest possible *s*,
by means of row and column permutations. This is achieved by
considering all the rows of *H* of weight one, for which
the nonzero entry * is contained in a column of weight one,
and all the rows of *H* of weight two such that at least one of the two *'s is contained in a column of weight
one. Under an appropriate column permutation, these rows of *H*
will form the submatrix
[*B* | *I*_{s}] in (3.7).
If there are no such rows, then *s* = 0 and *H* = *A*.
Since row and column permutations preserve the cycle-free
property of *H*, this procedure produces a cycle-free
parity-check matrix
*H'* = *A*|_{s}*B* for
, which
is in canonical form, although not necessarily reduced.

Since
*H'* = *A*|_{s}*B* is full-rank by assumption, all the rows of *A*
have weight 1. The key observation is that certain elementary
operations on the rows of *H'* allow us to eliminate rows of
weight one and two in *A*, while still preserving the cycle-free
property.

Indeed, suppose that *A* has a row
(*a*_{1}, *a*_{2},..., *a*_{r-s}) of weight one,
with a single * in position *i*. Then we can add this row to all the
rows of *H'* that are nonzero at position *i*. This procedure is equivalent
to deleting all but one of the edges incident at the symbol vertex *x*_{i}
in *T*(*H'*), which certainly does not create new cycles.
Following this procedure, the single * in
(*a*_{1}, *a*_{2},..., *a*_{r-s})
is contained in a column of weight one. Hence we can transform the
resulting cycle-free parity-check matrix for
into the form
*A'*|_{s+1}*B'*, by means of row and column permutations, thereby
eliminating the row of weight one in *A*.

Now suppose that *A* has a row
(*a*_{1}, *a*_{2},..., *a*_{r-s}) of weight two,
with the two *'s in positions *i* and *j*, and let *y*^{*} be the corresponding
check vertex in *T*(*H'*). We again add this row to all the rows of *H'* that
are nonzero at position *i*. Let
(*b*_{1}, *b*_{2},..., *b*_{n}) be such a row,
and let *y'* denote the corresponding check vertex of *T*(*H'*). If
*b*_{j} = *b*_{i} = *, then *T*(*H'*) contains the
cycle
(*x*_{i}, *y*^{*}),(*y*^{*}, *x*_{j}),(*x*_{j}, *y'*),(*y'*, *x*_{i}).
Since *T*(*H'*) is cycle-free, we conclude that *b*_{i} = * while *b*_{j} = 0.
Hence, adding row
(*a*_{1}, *a*_{2},..., *a*_{n}) to
(*b*_{1}, *b*_{2},..., *b*_{n})
corresponds to deleting the edge (*y'*, *x*_{i}) in *T*(*H'*) while
introducing a new edge (*y'*, *x*_{j}), as illustrated in Figure 3.4.

However, this new edge cannot
close a cycle, since *T*(*H'*) is cycle-free and a path from *y'*
to *x*_{j} already exists in *T*(*H'*): indeed
(*y'*, *x*_{i}),(*x*_{i}, *y*^{*}),(*y*^{*}, *x*_{j})
is such a path.
Following all these elementary row operations, the * at position *i*
in
(*a*_{1}, *a*_{2},..., *a*_{n}) is contained in a column of weight one. Thus
we can again transform the resulting cycle-free parity-check matrix for
into the form
*A'*|_{s+1}*B'*,
thereby eliminating the row of weight two in *A*.

We iteratively repeat the process described in the foregoing two paragraphs,
until either *s* = *r* or all the rows of *A* have weight 3.
This procedure produces a cycle-free parity-check matrix for
that
is in reduced canonical form.

width4pt depth2pt height6pt

If the reduced canonical form in Lemma 3.9 is achieved in the extreme
case *s* = *r*, then it is easy to prove the claim of Theorem 3.6.

**Proof. **
If *B* contains a column of weight *w*, then clearly *d**w* + 1.
Since *B* is an
*r*×*k* matrix, there will always be at least
one column with maximum weight
, so that

As

width4pt depth2pt height6pt

http://people.bu.edu/trachten