\magnification=\magstep1
\centerline{Mathematics 392 -- Seminar in Coding Theory}
\centerline{Selected Solutions -- Discussion 2}
\centerline{\it February 18, 2002}
\bigskip
\noindent
C)  The general formula relating the dimensions of $C,D,E$ is 
$$\dim(E) = k + \ell = \dim(C) + \dim(D).$$
To prove this, let $\gamma = \{u_1,\ldots, u_k\}$ be a basis for 
$C$ and $\delta = \{v_1,\ldots, v_\ell\}$ be a basis for $D$.  Then we claim
that the set
$$\beta = \{(u_1|u_1),\ldots,(u_k|u_k),(0|v_1),\ldots,(0|v_\ell)\}$$
is a basis for $E$.  Since $|\beta| = k + \ell$, this will prove our
claim.  

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

To see that $\beta$ spans $E$, note that a general vector in $E$ has the 
form $(u|u+v) = (u|u) + (0|v)$, where $u \in C$ and $v\in D$.  Since 
$\gamma$ is a basis for $C$, there exist scalars $c_i \in K$ such 
that $u = c_1u_1 + \cdots + c_k u_k$.  
Hence $(u|u) = c_1(u_1|u_1) + \cdots + c_k (u_k|u_k)$.  Similarly,
since $\delta$ is a basis for $D$, there exist scalars $d_j \in K$ 
such that 
$v = d_1v_1 + \cdots + d_\ell v_\ell$.  Hence
$(0|v) = d_1(0|v_1) + \cdots + d_\ell (0|v_\ell)$.  Putting all this together,
we have 
$$(u|u+v) = (u|u) + (0|v) =  c_1(u_1|u_1) + \cdots + c_k (u_k|u_k) + d_1(0|v_1) + \cdots + d_\ell (0|v_\ell)$$
This shows that $(u|u+v)$ is in the span of $\beta$.  

To see that $\beta$ is linearly independent, consider a linear combination
of vectors in $\beta$ that adds up to the zero word of length $2n$:
$$ c_1(u_1|u_1) + \cdots + c_k (u_k|u_k) + d_1(0|v_1) + \cdots + d_\ell (0|v_\ell)
=(0|0).\leqno(1)$$
We can also write this as 
$$(c_1u_1 + \cdots + c_k u_k|(c_1u_1 + \cdots + c_k u_k)+(d_1v_1 + \cdots + d_\ell v_\ell)) = (0|0).
\leqno(2)$$
Looking at the first half of the word, we see that
$c_1u_1 + \cdots + c_k u_k = 0$.  Since $\gamma$ is a basis for $C$, 
the vectors $u_i$ are linearly independent.  Hence $c_1 = \cdots = c_k = 0$.  
Substituting this into (2), we have
$$(0|d_1v_1 + \cdots + d_\ell v_\ell) = (0|0).$$
Since $\delta$ is a basis for $D$, the vectors $v_j$ are linearly independent,
so $d_1 = d_2 = \cdots = d_\ell= 0$.  Hence $\beta$ is linearly independent
as well, since all the coefficients in the linear combination in (1)
must be zero.
\bigskip
\noindent
D) The minimum distance of $E$ is $2d$.  To prove this, note that  
if the word $(u|u+v)$ is not zero, then $u \ne 0$, or $u = 0$ but 
$v \ne 0$.   If the vector $u \in C$ is not zero, it has 
weight at least $d$ by hypothesis.  Say $wt(u) = d + r$, where $r \ge 0$.
Similarly, if $v\ne 0$, then by hypothesis $wt(v) \ge 2d$.  In the 
word $(u|u+v)$, the first half has $d + r$ 1's, while the second half
has {\it 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 $\ge 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.
\bigskip
\noindent
E)  The general statement along these lines is that if $H$ is a 
parity check matrix for $C$ and $H$ has the property that 
{\it 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$.
\bigskip
\noindent
{\it Proof:}  By the definition of a parity check matrix,
$uH = 0$ if and only if $u \in C$.  
Let $u = (u_1,\ldots,u_n) \in K^n$ be any vector, 
and let $H_1,\ldots, H_n$ be the rows of $H$.  Then the matrix
product $uH$ is the same as the linear combination 
$u_1H_1 + \cdots + u_nH_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} + \cdots + 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,\ldots, 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$.
\bye



