Mathematics 392 – Seminar in Coding Theory Selected Solutions – Discussion 2 February 18, 2002

C) The general formula relating the dimensions of C, D, E is

dim(E) = k + ℓ = dim(C) + dim(D).

To prove this, let γ = {u_{1}, …, u_{k}} be a basis for C and δ = {v_{1}, …, v_{ℓ}} be a basis for D. Then we claim that the set

β = {(u_{1}|u_{1}), …, (u_{k}|u_{k}), (0|v_{1}), …, (0|v_{ℓ})}

is a basis for E. Since |β| = k + ℓ, this will prove our claim.

To show that β is a basis for E, we must show that β spans E and that β is linearly independent.

To see that β spans E, note that a general vector in E has the form (u|u + v) = (u|u) + (0|v), where u ∈ C and v ∈ D. Since γ is a basis for C, there exist scalars c_{i} ∈ K such that u = c_{1}u_{1} + ⋯ + c_{k}u_{k}. Hence (u|u) = c_{1}(u_{1}|u_{1}) + ⋯ + c_{k}(u_{k}|u_{k}). Similarly, since δ is a basis for D, there exist scalars d_{j} ∈ K such that v = d_{1}v_{1} + ⋯ + d_{ℓ}v_{ℓ}. Hence (0|v) = d_{1}(0|v_{1}) + ⋯ + d_{ℓ}(0|v_{ℓ}). Putting all this together, we have

(u|u + v) = (u|u) + (0|v) = c_{1}(u_{1}|u_{1}) + ⋯ + c_{k}(u_{k}|u_{k}) + d_{1}(0|v_{1}) + ⋯ + d_{ℓ}(0|v_{ℓ})

This shows that (u|u + v) is in the span of β.

To see that β is linearly independent, consider a linear combination of vectors in β that adds up to the zero word of length 2n:

(1)  c_{1}(u_{1}|u_{1}) + ⋯ + c_{k}(u_{k}|u_{k}) + d_{1}(0|v_{1}) + ⋯ + d_{ℓ}(0|v_{ℓ}) = (0|0).

We can also write this as

(2)  (c_{1}u_{1} + ⋯ + c_{k}u_{k}|(c_{1}u_{1} + ⋯ + c_{k}u_{k}) + (d_{1}v_{1} + ⋯ + d_{ℓ}v_{ℓ})) = (0|0).

Looking at the first half of the word, we see that c_{1}u_{1} + ⋯ + c_{k}u_{k} = 0. Since γ is a basis for C, the vectors u_{i} are linearly independent. Hence c_{1} = ⋯ = c_{k} = 0. Substituting this into (2), we have

(0|d_{1}v_{1} + ⋯ + d_{ℓ}v_{ℓ}) = (0|0).

Since δ is a basis for D, the vectors v_{j} are linearly independent, so d_{1} = d_{2} = ⋯ = d_{ℓ} = 0. Hence β is linearly independent as well, since all the coefficients in the linear combination in (1) must be zero.

D) The minimum distance of E is 2d. To prove this, note that if the word (u|u + v) is not zero, then u ≠ 0, or u = 0 but v ≠ 0. If the vector u ∈ C is not zero, it has weight at least d by hypothesis. Say wt(u) = d + r, where r ≥ 0. Similarly, if v ≠ 0, then by hypothesis wt(v) ≥ 2d. In the word (u|u + v), the first half has d + r 1’s, while the second half has at least 2d−(d+r) 1’s. (There would be exactly this many if all the 1’s in u canceled 1’s in v. Note also that the inequality is still true if 2d − (d + r) < 0.) Hence the total weight is at least d + r + 2d − (d + r) = 2d. On the other hand if u = 0, then (0|v) has weight ≥ 2d by hypothesis (and some words achieve this minimum). This shows that every nonzero word in E has weight at least 2d, and some words have weight exactly 2d. Since E is linear this shows the claim about the minimum distance.

E) The general statement along these lines is that if H is a parity check matrix for C and H has the property that every set of d − 1 rows of H is linearly independent, but some set of d rows of H is linearly dependent, then the minimum distance of C is d.

Proof: By the definition of a parity check matrix, uH = 0 if and only if u ∈ C. Let u = (u_{1}, …, u_{n}) ∈ K^{n} be any vector, and let H_{1}, …, H_{n} be the rows of H. Then the matrix product uH is the same as the linear combination u_{1}H_{1} +⋯+u_{n}H_{n} of the rows of H. If every set of d − 1 rows is linearly independent, but some set of rows of H is linearly dependent, then we have some linear combination

u_{i_{1}}H_{i_{1}} + ⋯ + u_{i_{d}}H_{i_{d}} = 0,

where not all u_{i_{j}} = 0. Moreover, all the u_{i_{j}} must equal 1, or else we would have a linear dependence on < d rows of H. By the above, the word u with 1’s in positions i_{1}, …, i_{d} and zeros elsewhere satisfies uH = 0. Hence u is a codeword of weight d, and there are no codewords of smaller weight. Since C is linear, the minimum distance is d.