# Number of independent parity checks satisfied by a code

I have been studying quantum error correction codes and as background, I am currently studying the theory of classical linear codes. Despite many efforts, I am unable to understand the following excerpt:

Any given parity check u divides Hamming space exactly in half,into those vectors which satisfy u and those that do not.Therefore,the 2^k vectors of a linear subspace in 2^n Hamming space can satisfy at most n−k linearly independent parity checks.These parity checks together form the parity check matrix H, which is another way to define the linear subspace.

• Have you taken linear algebra? May 1 '20 at 7:52

Any given parity check $$u$$ divides Hamming space exactly in half, into those vectors which satisfy $$u$$ and those that do not.

Suppose your Hamming space is $$X = \{0,1\}^n$$. A non-zero parity check $$u$$ divides $$X$$ into two sets: $$X_0 = \{ x \in X \mid \langle x,u \rangle = 0 \}$$ and $$X_1 = \{ x \in X \mid \langle x,u \rangle = 1 \}$$. The two sets have equal size $$2^{n-1}$$.

Indeed, let $$v$$ be some non-zero vector such that $$\langle u,v \rangle = 1$$ (for example, $$v$$ could contain a single 1 entry, at some index in which $$u$$ also has a 1 entry). If $$x \in X_0$$ then $$x + v \in X_1$$, and conversely, if $$x \in X_1$$ then $$x + v \in X_0$$. Hence we can partition $$X$$ into pairs $$(x,x+v)$$ in which the first member is in $$X_0$$ and the second in $$X_1$$.

Here are two illustrating examples. If $$u = (1,\underbrace{0,\ldots,0}_{n-1\text{ copies}})$$ then $$X_0$$ consists of all vectors with 0 in the first coordinate, and $$X_1$$ consists of all vectors with 1 in the first coordinate. If $$u = (\underbrace{1,\ldots,1}_{n \text{ copies}})$$ then $$X_0$$ consists of all vectors with even parity, and $$X_1$$ consists of all vectors with odd parity.

Therefore, the $$2^k$$ vectors of a linear subspace in $$2^n$$ Hamming space can satisfy at most $$n−k$$ linearly independent parity checks. The statement here actually doesn't follow from the preceding statement. However, it is similar in spirit (and a generalization of the preceding statement). Earlier we have considered a single parity check $$u$$. We showed that if $$u$$ is non-zero, then the set $$\{x \in X \mid \langle x,u \rangle = 0\}$$ contains exactly half the space. If $$u = 0$$ then it consists of the entire space.

Now we are considering the common solutions of $$m$$ different vectors $$u_1,\ldots,u_m$$. The set $$C = \{x \in X \mid \langle x,u_1 \rangle = \cdots = \langle x,u_m \rangle = 0\}$$ contains at least $$2^{n-m}$$ vectors. If the vectors are linearly independent (this generalizes the condition $$u \neq 0$$), then $$C$$ contains exactly $$2^{n-m}$$ vectors. More generally, $$C$$ contains $$2^{n-d}$$ vectors, where $$d$$ is the dimension of the linear span of the vectors $$u_1,\ldots,u_m$$. I won't prove all these statements, but this is basic linear algebra.

If $$C$$ is a linear subspace containing $$2^k$$ vectors, and every element $$x \in C$$ satisfies $$\langle x,u_1 \rangle = \cdots = \langle x,u_m \rangle = 0$$, then the dimension of the span of $$u_1,\ldots,u_m$$ is at most $$n-k$$, per the discussion above. If we know that $$u_1,\ldots,u_m$$ are linearly independent, then the dimension of their span is $$m$$, and so $$m \leq n-k$$.

These parity checks together form the parity check matrix $$H$$, which is another way to define the linear subspace.

We can describe a linear code in two ways. One is using a generator matrix $$G$$: the linear code consists of all linear combinations of the rows. The other is using a parity check matrix $$H$$: the code consists of all vectors whose inner product with each row is 0. (Some books use rows, other columns.) Using our earlier notation, the rows of $$H$$ are just the vectors $$u_1,\ldots,u_m$$, where we insist that the vectors be linearly independent (the same holds for generator matrices).

Here is an example. Let $$n = 3$$, and consider the code whose generator matrix is $$\begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}$$ (We note that the same code has many generator matrices, and many parity check matrices.)

The code consists of all linear combinations of the rows: $$\begin{matrix} 0 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}$$ You can check that these are exactly the vectors with even parity. Hence a parity check matrix for this code (in this degenerate case, the unique parity check matrix) is $$\begin{bmatrix} 1 & 1 & 1 \end{bmatrix}$$ We can also treat this as a generator matrix of a code. The resulting code is known as the dual code (dual to the code for which this matrix functions as a parity check matrix).