Paper
Part IILinear Block Codes

Matrices and Elimination over Finite Fields

November 15, 202654 min readbeginner

A binary matrix turns parity checks into XOR gates. The chapter row-reduces matrices by hand, proves the rank theorem, solves linear systems, inverts square matrices and puts a generator matrix into systematic form.

The previous chapter, Vector Spaces over Finite Fields, measured a code by its dimension and found that a subspace of dimension kk over GF(q)\mathrm{GF}(q) holds qkq^k words. It left open how to compute any of this. Given four words of length 7, are they independent? Which words pass three parity checks at once, and how many of them are there? Each question is about a matrix, a rectangular table of field elements, and each is answered by one procedure, elimination.

Elimination adds one row of a matrix to another until the matrix is as simple as it can be made. Over GF(2)\mathrm{GF}(2) adding a row is XOR, the operation parity checks already use. The simplified matrix shows the rank, the number of independent rows, and from it the null space, the solutions of any linear system, the inverse when there is one, and the systematic form in which a code's message bits appear unchanged in its codewords.

Every number in the chapter is recomputed by ch16_matrices_and_elimination_over_finite_fields.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch16_charts.py in the same folder. The GNU Octave twin ch16_matrices_and_elimination_over_finite_fields.m prints the same lines, as The Octave Route explains.

01.A Matrix Is a Table of Bits

Three parity checks on a 4-bit word x=x1x2x3x4x = x_1 x_2 x_3 x_4 make a concrete start. The first check reads bits 1, 2 and 4, the second reads bits 1, 3 and 4, and the third reads bits 2, 3 and 4. Writing a 1 under each bit a check reads and a 0 under each bit it skips turns the three checks into the rows 11011101, 10111011 and 01110111. Stacked one above the other, the rows form a table with three rows and four columns.

A=[110110110111]A = \begin{bmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{bmatrix}

The matrix AA above is 3×43 \times 4, and its entry a23a_{23} is 1 because the second check reads bit 3. Each row of a matrix is a word of length nn and each column is a word of length mm, so both are vectors in the sense of Vector Spaces over Finite Fields. The span of the rows is the row space of the matrix, and the span of the columns is its column space. Words are written as strings, such as x=1011x = 1011, and a word that multiplies a matrix from the right stands as a column.

02.Matrix Times Vector as Parity Sums

Take x=1011x = 1011. The first check XORs bits 1, 2 and 4, which gives 1⊕0⊕1=01 \oplus 0 \oplus 1 = 0. The second XORs bits 1, 3 and 4, which gives 1⊕1⊕1=11 \oplus 1 \oplus 1 = 1, and the third XORs bits 2, 3 and 4, which gives 0⊕1⊕1=00 \oplus 1 \oplus 1 = 0. The three results, read top to bottom, form the word 010010. Each result is the dot product of Vector Spaces over Finite Fields, taken between a row of AA and xx. The same pattern defines the product of any matrix and any word.

A second reading of the same product looks at columns instead of rows. The word x=1011x = 1011 has 1s in positions 1, 3 and 4, and the columns of AA in those positions are 110110, 011011 and 111111, read top to bottom. Their XOR is 110⊕011⊕111=010110 \oplus 011 \oplus 111 = 010, the same answer as before.

Proof. Entry ii of the combination on the right is x1ai1+⋯+xnainx_1 a_{i1} + \cdots + x_n a_{in}, since entry ii of the column cjc_j is aija_{ij}. Multiplication in a field is commutative, so this sum equals ai1x1+⋯+ainxna_{i1} x_1 + \cdots + a_{in} x_n, which is yiy_i by the definition. Every combination of the columns has the form on the right for some coefficients xjx_j, which proves the claim about the column space. For linearity, entry ii of A(x+x′)A (x + x') is ∑jaij(xj+xj′)\sum_j a_{ij} (x_j + x'_j), and the distributive law splits it into ∑jaijxj+∑jaijxj′\sum_j a_{ij} x_j + \sum_j a_{ij} x'_j. The same law gives ∑jaij(cxj)=c∑jaijxj\sum_j a_{ij} (c x_j) = c \sum_j a_{ij} x_j. ■\blacksquare

Figure 1 builds the row reading in hardware. A row of weight ww, meaning a row with ww ones, XORs ww bits, and a chain of two-input XOR gates does that with w−1w - 1 gates. Each row of AA has weight 3, so the three parity sums cost 2+2+2=62 + 2 + 2 = 6 gates. The second and third checks share the pair x3⊕x4x_3 \oplus x_4, so a network that computes t=x3⊕x4t = x_3 \oplus x_4 once and then forms x1⊕tx_1 \oplus t and x2⊕tx_2 \oplus t needs only 5 gates, and a check of all 16 inputs confirms that it agrees with AxA x.

The product A x for the 3-by-4 matrix A with rows 1101, 1011 and 0111, built from two-input XOR gates. Each output adds the inputs in the columns where its row of A holds a 1: y1 is x1 + x2 + x4, y2 is x1 + x3 + x4 and y3 is x2 + x3 + x4, each from two gates, six in all. With x = 1011 the outputs are 0, 1 and 0. x1 1 x2 0 x3 1 x4 1 output row of A y1 = 0 1101 y2 = 1 1011 y3 = 0 0111 With x = 1011 the three parity sums are 0, 1 and 0, so A x = 010, from six gates.
Figure 1. The product of the 3-by-4 matrix A and the word x = 1011 built from gates. Each row of A becomes a chain of two XOR gates fed by the bits that the row selects, and the three outputs give A x = 010 from six gates.

A parity-check matrix HH lists the checks that a code imposes, one per row, and a received word rr passes them all exactly when Hr=0H r = 0. Hamming's codes of 1950 were defined by parity checks of this kind [1], and the gates of Figure 1 are what a hardware decoder builds to compute HrH r.

03.Multiplying Two Matrices

Two matrices can be multiplied when the first has as many columns as the second has rows. The product applies the first matrix to each column of the second.

Take the binary matrices

E=[1101],F=[1011].E = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}, \qquad F = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}.

Row 1 of EE is 1111, so row 1 of EFEF is the XOR of both rows of FF, which is 10⊕11=0110 \oplus 11 = 01. Row 2 of EE is 0101, so row 2 of EFEF is row 2 of FF, which is 1111. In the other order, row 1 of FEFE is row 1 of EE, which is 1111, and row 2 is 11⊕01=1011 \oplus 01 = 10. So EF≠FEEF \neq FE, and the order of a product matters. How a longer product is grouped does not.

Proof. Entry (i,j)(i, j) of (AB)C(AB)C is ∑s(AB)iscsj=∑s∑rairbrscsj\sum_{s} (AB)_{is} c_{sj} = \sum_{s} \sum_{r} a_{ir} b_{rs} c_{sj}, a sum over all pairs (r,s)(r, s). Entry (i,j)(i, j) of A(BC)A(BC) is ∑rair(BC)rj=∑r∑sairbrscsj\sum_{r} a_{ir} (BC)_{rj} = \sum_{r} \sum_{s} a_{ir} b_{rs} c_{sj}, a sum of the same terms. The distributive law is what expands each product of a sum into these sums of products, and since addition in a field can be reordered and multiplication can be regrouped, the two finite sums are equal. In IAI A, entry (i,j)(i, j) is ∑rδirarj\sum_r \delta_{ir} a_{rj}, where δir\delta_{ir} is 1 when r=ir = i and 0 otherwise, so only the term with r=ir = i survives and the entry is aija_{ij}. The case AIA I is the same with rows and columns exchanged. ■\blacksquare

A message multiplies a matrix from the left. A generator matrix GG of size k×nk \times n turns a message mm of length kk, written as a row, into the codeword mGm G, which by the definition is the XOR of the rows of GG that mm selects. Take the 4×74 \times 7 binary matrix

G=[0110111111000111010101100101].G = \begin{bmatrix} 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 1 \end{bmatrix}.

The message 10111011 selects rows 1, 3 and 4, and its codeword is 0110111⊕1101010⊕1100101=01110000110111 \oplus 1101010 \oplus 1100101 = 0111000. The codewords of GG are the combinations of its rows, so the code is the row space of GG, while the code of a parity-check matrix is its null space.

04.Three Row Operations

Elimination changes a matrix one row at a time, and only in three ways.

Over GF(2)\mathrm{GF}(2) the only nonzero scalar is 1, so scaling does nothing and every row addition has c=1c = 1. Binary elimination therefore uses swaps and the additions Ri←Ri+RjR_i \leftarrow R_i + R_j, each an XOR of one row into another. Applied to AA, the addition R2←R2+R1R_2 \leftarrow R_2 + R_1 replaces the second row 10111011 by 1011⊕1101=01101011 \oplus 1101 = 0110.

Each of the three can be undone. Repeating a swap restores the rows. Scaling by cc is undone by scaling by c−1c^{-1}, which exists because cc is a nonzero element of a field. Adding cRjc R_j to RiR_i is undone by adding −cRj-c R_j, and over GF(2)\mathrm{GF}(2), where −1=1-1 = 1, by adding RjR_j a second time, since 0110⊕1101=10110110 \oplus 1101 = 1011 brings back the original row.

Each row operation is also a matrix product. Applying R2←R2+R1R_2 \leftarrow R_2 + R_1 to the 3×33 \times 3 identity gives

E21=[100110001],E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix},

and multiplying AA on the left by E21E_{21} keeps rows 1 and 3 of AA and replaces row 2 by the XOR of rows 1 and 2, exactly as the operation does.

Proof. Row ii of EAE A is the combination of the rows of AA whose coefficients are the entries of row ii of EE. A row of EE that ρ\rho did not touch is the identity row eie_i, with 1 in position ii and 0 elsewhere, and it selects row ii of AA unchanged. A swap makes rows ii and jj of EE equal to eje_j and eie_i, a scaling makes row ii equal to c eic\,e_i, and a row addition makes it ei+c eje_i + c\,e_j, which select RjR_j and RiR_i, then cRic R_i, then Ri+cRjR_i + c R_j. In each case EA=ρ(A)E A = \rho(A). Applying this with A=EA = E gives E′E=ρ′(E)=ρ′(ρ(I))=IE' E = \rho'(E) = \rho'(\rho(I)) = I, since ρ′\rho' undoes ρ\rho, and exchanging the roles of ρ\rho and ρ′\rho' gives EE′=IE E' = I. ■\blacksquare

A sequence of row operations is therefore left multiplication by a product Et⋯E2E1E_t \cdots E_2 E_1 of elementary matrices, and by associativity that product is invertible, with inverse E1−1E2−1⋯Et−1E_1^{-1} E_2^{-1} \cdots E_t^{-1}.

Proof. Write B=EAB = E A with EE invertible. If Ax=0A x = 0 then Bx=E(Ax)=0B x = E (A x) = 0, and if Bx=0B x = 0 then Ax=E−1(Bx)=0A x = E^{-1} (B x) = 0, using associativity both times. Each row of BB is a combination of the rows of AA, so the row space of BB lies inside the row space of AA. The same holds with A=E−1BA = E^{-1} B and the roles exchanged, so the two row spaces are equal. ■\blacksquare

05.Elimination to Reduced Row Echelon Form

Elimination works through the columns from left to right. In each column it looks for a row with a nonzero entry among the rows not yet used, moves that row into place, and clears every other entry in the column. Figure 2 shows the run on AA.

Column 1 of AA has a 1 in row 1, so row 1 becomes the first pivot row. Row 2 also has a 1 in column 1, and R2←R2+R1R_2 \leftarrow R_2 + R_1 clears it, giving the rows 11011101, 01100110 and 01110111. Column 2 has a 1 in row 2, the next unused row, so row 2 becomes the second pivot row. Rows 1 and 3 have 1s in column 2, and R1←R1+R2R_1 \leftarrow R_1 + R_2 and R3←R3+R2R_3 \leftarrow R_3 + R_2 clear them, giving 10111011, 01100110 and 00010001. Column 3 has a 0 in row 3, the only unused row, so it gets no pivot and is called free. Column 4 has a 1 in row 3, and R1←R1+R3R_1 \leftarrow R_1 + R_3 clears the 1 above it.

[110110110111]⟶[110101100111]⟶[101101100001]⟶[101001100001]\begin{bmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{bmatrix} \longrightarrow \begin{bmatrix} 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \end{bmatrix} \longrightarrow \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \longrightarrow \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}

Four row additions turned AA into a matrix whose pivots, the leading 1s of the rows, sit in columns 1, 2 and 4, with each pivot alone in its column.

Gauss-Jordan elimination of the 3-by-4 matrix A, one pivot column at a time A 1 2 3 4 1 1 0 1 1 0 1 1 0 1 1 1 column 1 cleared 1 2 3 4 1 1 0 1 0 1 1 0 0 1 1 1 add R1 to R2 column 2 cleared 1 2 3 4 1 0 1 1 0 1 1 0 0 0 0 1 add R2 to R1 add R2 to R3 column 4 cleared 1 2 3 4 1 0 1 0 0 1 1 0 0 0 0 1 add R3 to R1 pivot, a leading 1 alone in its column free column, no pivot
Figure 2. Elimination of A, one column at a time. Each stage clears the column of a new pivot, shown in green, by adding the pivot row to every other row with a 1 there. Column 3 gets no pivot and stays free. Data: computed by ch16_charts.py in the companion repository.

This form of elimination, often called Gauss-Jordan elimination, keeps a counter rr for the next pivot row, starting at 1, and treats each column jj from left to right. If every entry of column jj in rows rr and below is zero, the column is free and the counter stays. Otherwise a row at or below rr with a nonzero entry in column jj is swapped into row rr and scaled so that the entry becomes 1, a suitable multiple of it is added to every other row to clear column jj, and rr increases by one.

Proof. Every step is a row operation, and the procedure ends after the last column. The claim, by induction on jj, is that after column jj the first jj columns are in reduced row echelon form and rows rr and below are zero in them. For j=0j = 0 there are no columns yet, so the claim holds with nothing to check. If column jj is free, its entries in rows rr and below are already zero. Otherwise the swap and the scaling touch only rows rr and below, which are zero in columns 1 to j−1j - 1, so those columns do not change and the new pivot row is zero in them. Adding multiples of it to other rows then leaves those columns alone while clearing column jj. The new pivot sits below and to the right of every earlier one, and rows r+1r + 1 and below are now zero in the first jj columns. The case j=nj = n is the theorem. Each pivot uses its own row and its own column, so there are at most min⁡(m,n)\min(m, n) of them. ■\blacksquare

Figure 3 shows the shape that results, a staircase of pivots with zeros below it.

The shape of a matrix in reduced row echelon form, four rows by eight columns, with pivots in columns 1, 2, 4 and 7. A green staircase separates the zeros below and to the left of the pivots from the rest. Each pivot is a 1 with zeros above and below it in its column, and the free columns 3, 5, 6 and 8 may hold any values above the staircase. Four pivots give rank 4 and four free columns give nullity 4. 1 2 3 4 5 6 7 8 R1 1 0 * 0 * * 0 * R2 0 1 * 0 * * 0 * R3 0 0 0 1 * * 0 * R4 0 0 0 0 0 0 1 * 4 pivots, so rank 4 4 free columns, so nullity 4 rank + nullity = 8, the number of columns pivot, a leading 1 * any value, in a free column zeros below the staircase
Figure 3. The shape of a matrix in reduced row echelon form. Each pivot is a 1 alone in its column, the pivots step down and to the right, and the free columns, marked in orange, hold whatever entries elimination left above the staircase.

The method is far older than its name. The Nine Chapters on the Mathematical Art, a Chinese text about two thousand years old, solves linear systems by cross-multiplying and subtracting columns of coefficients on a counting board [2]. Grcar traces how the method came to carry Gauss's name [3].

06.Rank

Run elimination on a second matrix, the 3×63 \times 6 binary matrix

B=[011011101100110111].B = \begin{bmatrix} 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 \end{bmatrix}.

Column 1 has a 0 in row 1, so the swap R1↔R2R_1 \leftrightarrow R_2 brings a 1 to the top. Row 3 has a 1 in column 1, and R3←R3+R1R_3 \leftarrow R_3 + R_1 gives 110111⊕101100=011011110111 \oplus 101100 = 011011, so the rows are now 101100101100, 011011011011 and 011011011011. Column 2 has a 1 in row 2, row 1 already has a 0 there, and R3←R3+R2R_3 \leftarrow R_3 + R_2 turns row 3 into 000000000000. No row remains for a third pivot, and the result is

[101100011011000000].\begin{bmatrix} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}.

Three rows went in and two pivots came out. Row 3 of BB is the XOR of rows 1 and 2, as 011011⊕101100=110111011011 \oplus 101100 = 110111 confirms, so it carried nothing that the other two did not, and elimination exposed that by turning it into zeros.

Proof. Suppose a combination ∑iλiρi\sum_i \lambda_i \rho_i of the nonzero rows ρi\rho_i of RR is zero. The pivot of row ii lies in a column where every other row of RR holds 0, so the entry of the combination in that column is λi⋅1=λi\lambda_i \cdot 1 = \lambda_i. That entry is 0, so every λi\lambda_i is 0 and the rows are independent. The row space of RR equals the row space of AA by the lemma on row operations, and zero rows add nothing to a span, so the nonzero rows span the row space of AA. An independent spanning set is a basis, and its size is the dimension. ■\blacksquare

The rank of AA is 3 and the rank of BB is 2. A matrix with mm rows has rank mm exactly when its rows are independent, because only then does the row space have dimension mm. For a generator matrix this test decides whether a message can be recovered from its codeword. If the rows of GG are dependent, some nonzero λ\lambda has λG=0\lambda G = 0, and then mG=(m+λ)Gm G = (m + \lambda) G for every message mm, so two different messages share each codeword.

07.The Null Space by Back Substitution

The null space of BB is the set of words xx of length 6 with Bx=0B x = 0. By the lemma on row operations it is also the null space of the reduced form, whose two nonzero rows give two equations.

x1+x3+x4=0,x2+x3+x5+x6=0x_1 + x_3 + x_4 = 0, \qquad x_2 + x_3 + x_5 + x_6 = 0

Each equation holds exactly one pivot variable, x1x_1 in the first and x2x_2 in the second. The free variables x3x_3, x4x_4, x5x_5 and x6x_6 can take any values, and then the pivot variables are forced. Over GF(2)\mathrm{GF}(2), where −1=1-1 = 1, the equations give x1=x3+x4x_1 = x_3 + x_4 and x2=x3+x5+x6x_2 = x_3 + x_5 + x_6. Solving each pivot equation for its pivot variable in this way is called back substitution.

Setting one free variable to 1 and the others to 0 gives one word for each free column. With x3=1x_3 = 1 the equations force x1=1x_1 = 1 and x2=1x_2 = 1, which gives 111000111000. The other three free variables give 100100100100, 010010010010 and 010001010001. A search over all 64 words of length 6 finds exactly 16 words in the null space, which is the number of combinations of these four words.

Proof. Row ii of RR has 1 in its pivot column pp and 0 in the other pivot columns. Applied to vfv_f it gives 1⋅(−rif)+rif⋅1=01 \cdot (-r_{if}) + r_{if} \cdot 1 = 0, because vfv_f is zero in every other free position. So each vfv_f lies in the null space of RR, which is the null space of AA. In a combination ∑fλfvf\sum_f \lambda_f v_f the entry in position ff is λf\lambda_f alone, so a zero combination has every λf=0\lambda_f = 0 and the words are independent. To show that they span, take any xx with Ax=0A x = 0. The word z=x−∑fxfvfz = x - \sum_f x_f v_f lies in the null space and is zero in every free position, so row ii of RR applied to zz reads off its pivot entry zpz_p, which must be 0. So z=0z = 0 and x=∑fxfvfx = \sum_f x_f v_f. ■\blacksquare

Counting the basis gives the central result of the chapter.

Proof. The reduced form has rank⁡(A)\operatorname{rank}(A) pivot columns, and the other n−rank⁡(A)n - \operatorname{rank}(A) columns are free. The theorem on back substitution gives a basis of the null space with one word per free column, so the nullity is n−rank⁡(A)n - \operatorname{rank}(A). A space of dimension dd over GF(q)\mathrm{GF}(q) holds qdq^d words, as Vector Spaces over Finite Fields showed. ■\blacksquare

Table 1 applies it to five of the binary matrices that the chapter reduces. For BB it gives 2+4=62 + 4 = 6 and a null space of 24=162^4 = 16 words, the count found by trying all 64.

Table 1. Rank, nullity and null-space size of the binary matrices reduced in the chapter, with M from Inverting a Square Matrix and C from the worked example A system with two free variables

MatrixSizeRankNullityWords in the null space
AA3×43 \times 4312
BB3×63 \times 62416
GG4×74 \times 7438
MM3×33 \times 3301
CC3×53 \times 5324

Source: reproduced by ch16_matrices_and_elimination_over_finite_fields.py.

For codes the theorem counts codewords. A parity-check matrix HH of size (n−k)×n(n - k) \times n with independent rows has rank n−kn - k, so its null space, the code, has dimension n−(n−k)=kn - (n - k) = k and holds 2k2^k codewords.

08.Solving a Linear System

A linear system asks for every xx with Ax=bA x = b for a given word bb. Elimination solves it by working on the augmented matrix [ A∣b ]\left[\,A \mid b\,\right], which attaches bb as an extra column. Row operations on the augmented matrix act on both sides of every equation at once.

For Bx=100B x = 100, the operations that reduced BB act on the attached column too. The swap moves its bits to 010010, the addition R3←R3+R1R_3 \leftarrow R_3 + R_1 leaves the last bit of row 3 at 0, and R3←R3+R2R_3 \leftarrow R_3 + R_2 makes it 1. Row 3 now reads 000000∣1000000 \mid 1, which says 0=10 = 1. No word satisfies that equation, so the system has no solution. For Bx=110B x = 110 the same steps give

[101100101101110000000].\left[\begin{array}{cccccc|c} 1 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right].

Setting the free variables to 0 gives x1=1x_1 = 1 and x2=1x_2 = 1, so xp=110000x_p = 110000 is one solution. Adding any word vv of the null space to xpx_p gives another, since B(xp+v)=Bxp+Bv=110+000B (x_p + v) = B x_p + B v = 110 + 000. The 16 null-space words give 16 solutions, and a search over all 64 words finds no others.

Proof. The row operations are left multiplication by an invertible EE, and Ax=bA x = b holds exactly when EAx=EbE A x = E b, so the reduced augmented matrix has the same solutions. If its last column holds a pivot, that pivot's row reads 0=10 = 1 and there is no solution. Otherwise setting every free variable to 0 and each pivot variable to the last entry of its row gives a solution. If Axp=bA x_p = b and Av=0A v = 0, then A(xp+v)=bA (x_p + v) = b by linearity, and if Ax=bA x = b then A(x−xp)=0A (x - x_p) = 0, so every solution lies in xp+N(A)x_p + N(A). The map v↦xp+vv \mapsto x_p + v is one to one, so the solution set has as many elements as N(A)N(A), which is q n−rank⁡(A)q^{\,n - \operatorname{rank}(A)} by the rank theorem. ■\blacksquare

The solution sets are cosets in the sense of Groups and Cosets, translates of the subgroup N(A)N(A). Figure 4 draws them for AA, whose reduced form has a pivot in every row and so leaves no row that could read 0=10 = 1. Every right side is reachable, and each of the eight has exactly 24−3=22^{4 - 3} = 2 solutions, which differ by 11101110, the one nonzero word of N(A)N(A). For BB, each reachable right side has 16 solutions, so only 64/16=464 / 16 = 4 of the 8 right sides are reachable.

The two solutions of A x = b for each of the eight right sides b b = 000 0000 1110 b = 001 0111 1001 b = 010 0101 1011 b = 011 0010 1100 b = 100 0011 1101 b = 101 0100 1010 b = 110 0110 1000 b = 111 0001 1111 b = 000, whose two solutions are the null space of A any other b, whose solutions are the null space shifted by one solution In every box the two solutions differ by 1110, the one nonzero word of the null space.
Figure 4. The solutions of A x = b for all eight right sides b. Each solution set is a coset of the null space {0000, 1110}, shown in green, so the sixteen words of length 4 split into eight pairs. Data: computed by ch16_charts.py in the companion repository.

For a parity-check matrix HH the same picture is the syndrome decoder of Groups and Cosets. The received words rr with syndrome Hr=sH r = s form one coset of the code, and the code itself is the coset of the zero syndrome.

09.Inverting a Square Matrix

Take the 3×33 \times 3 binary matrix MM with rows 110110, 011011 and 111111. Solving Mx=bM x = b for one right side at a time would repeat the same row operations for each bb, so elimination works on the three columns of the identity at once, through the augmented matrix [ M∣I ]\left[\,M \mid I\,\right]. R3←R3+R1R_3 \leftarrow R_3 + R_1 clears column 1, R1←R1+R2R_1 \leftarrow R_1 + R_2 clears column 2, and R1←R1+R3R_1 \leftarrow R_1 + R_3 and R2←R2+R3R_2 \leftarrow R_2 + R_3 clear column 3. Figure 5 follows the six columns through these steps.

[110100011010111001]⟶[100011010111001101]\left[\begin{array}{ccc|ccc} 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \end{array}\right] \longrightarrow \left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 \end{array}\right]

The left half became II, and the right half holds the rows 011011, 111111 and 101101. Multiplying confirms that this is the inverse. Row 1 of MM is 110110, so row 1 of MM−1M M^{-1} is 011⊕111=100011 \oplus 111 = 100, and the other two rows give 010010 and 001001 the same way.

Inverting the 3-by-3 matrix M by row-reducing the augmented matrix [M | I] [M | I] at the start 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 M I column 1 cleared 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 add R1 to R3 column 2 cleared 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 0 1 add R2 to R1 column 3 cleared 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 0 1 I inverse of M add R3 to R1 add R3 to R2 pivot the inverse of M, read off the right half at the end
Figure 5. Inversion by elimination. The row operations that turn M into the identity turn the identity beside it into the inverse of M, boxed in cyan. Data: computed by ch16_charts.py in the companion repository.

Proof. Let EE be the product of the elementary matrices used, so that EA=RE A = R is the reduced form. A square matrix in reduced row echelon form with nn pivots has a pivot in every row and every column, stepping down the diagonal, and each pivot is alone in its column, so R=IR = I exactly when the rank is nn. If R=IR = I then EA=IE A = I. Since EE is invertible, A=E−1EA=E−1A = E^{-1} E A = E^{-1}, and therefore AE=E−1E=IA E = E^{-1} E = I as well, so EE is the inverse of AA. The same operations applied to [ A∣I ]\left[\,A \mid I\,\right] give [ EA∣EI ]=[ I∣A−1 ]\left[\,E A \mid E I\,\right] = \left[\,I \mid A^{-1}\,\right]. If instead the rank is below nn, the rank theorem gives a nullity of at least 1, so some v≠0v \neq 0 has Av=0A v = 0. An inverse would give v=A−1Av=0v = A^{-1} A v = 0, a contradiction, so AA has no inverse. ■\blacksquare

The matrix MM passes this test, and the matrix UU with rows 110110, 011011 and 101101 fails it. Its third row is the XOR of the first two, its reduced form has rows 101101, 011011 and 000000, and its rank is 2. Where an inverse exists it solves every system at once. The solution of Mx=110M x = 110 is M−1⋅110M^{-1} \cdot 110, the XOR of columns 1 and 2 of M−1M^{-1}, which is 011⊕110=101011 \oplus 110 = 101, and indeed M⋅101=110M \cdot 101 = 110.

10.How Many Square Matrices Are Invertible

Of the 16 binary 2×22 \times 2 matrices, 6 are invertible. The first row can be any of the 3 nonzero words 0101, 1010 and 1111, and the second row any of the 2 nonzero words that differ from the first. Choosing rows one at a time in the same way counts the invertible matrices of every size.

Proof. By the theorem on inversion, AA is invertible exactly when its rank is nn, and by the lemma on pivot rows the rank is the dimension of the row space, which is nn exactly when the nn rows are independent. Count independent rows in order. Once rows 1 to ii are chosen and independent, their span has dimension ii and holds qiq^i words, and row i+1i + 1 keeps the rows independent exactly when it lies outside that span, which leaves qn−qiq^n - q^i choices. For i=0i = 0 the span is {0}\{0\} and the first row is any nonzero word. Multiplying the numbers of choices for i=0,1,…,n−1i = 0, 1, \ldots, n - 1 gives the product. This is the theorem on counting ordered independent lists from Vector Spaces over Finite Fields, applied to the nn rows. ■\blacksquare

For q=2q = 2 the formula gives 3⋅2=63 \cdot 2 = 6 for n=2n = 2, then 7⋅6⋅4=1687 \cdot 6 \cdot 4 = 168 and 15⋅14⋅12⋅8=2016015 \cdot 14 \cdot 12 \cdot 8 = 20160. Table 2 lists the counts up to n=7n = 7 beside the totals 2n22^{n^2}, and for n≤4n \le 4 the script also finds them by testing every matrix.

Table 2. The number of invertible binary n-by-n matrices, the number of all binary n-by-n matrices, and the fraction that is invertible

nnInvertibleAll, 2n22^{n^2}Fraction invertible
1120.500000
26160.375000
31685120.328125
420,16065,5360.307617
59,999,36033,554,4320.298004
620,158,709,76068,719,476,7360.293348
7163,849,992,929,280562,949,953,421,3120.291056

Source: reproduced by ch16_matrices_and_elimination_over_finite_fields.py.

Dividing each factor 2n−2i2^n - 2^i by 2n2^n turns the fraction into a product whose factors approach 1.

Nn(2)2n2=∏j=1n(1−2−j)=12⋅34⋅78⋯(1−2−n)\frac{N_n(2)}{2^{n^2}} = \prod_{j=1}^{n} \left(1 - 2^{-j}\right) = \frac{1}{2} \cdot \frac{3}{4} \cdot \frac{7}{8} \cdots \left(1 - 2^{-n}\right)
(6)

Figure 6 plots the fraction, which is the binary line of the basis chart in Vector Spaces over Finite Fields, since the rows of an invertible matrix form a basis. It falls fast at first and then levels off, reaching 0.289070 at n=10n = 10, against a limit of 0.288788 as nn grows.

The fraction of n-by-n binary matrices that are invertible, falling toward 0.2888 matrix size n fraction invertible 1 2 3 4 5 6 7 8 9 10 0.20 0.30 0.40 0.50 0.500 0.375 0.328 0.308 0.298 0.293 0.291 0.290 0.289 0.289 fraction invertible at size n the limit, 0.288788 the bound 1/4
Figure 6. The fraction of binary n-by-n matrices that are invertible. It drops from one half and settles near 0.2888, never reaching the bound of one quarter. Data: computed by ch16_charts.py in the companion repository.

Proof. For numbers a1,…,ata_1, \ldots, a_t between 0 and 1, write Pt=∏j≤t(1−aj)P_t = \prod_{j \le t} (1 - a_j) and St=∑j≤tajS_t = \sum_{j \le t} a_j. Then Pt≥1−StP_t \ge 1 - S_t by induction on tt, because multiplying the bound by 1−at+1≥01 - a_{t+1} \ge 0 gives Pt+1≥(1−St)(1−at+1)=1−St+1+at+1St≥1−St+1P_{t+1} \ge (1 - S_t)(1 - a_{t+1}) = 1 - S_{t+1} + a_{t+1} S_t \ge 1 - S_{t+1}. Applied to the factors from j=2j = 2 to nn, it gives ∏j=2n(1−2−j)≥1−(2−2+⋯+2−n)=12+2−n\prod_{j=2}^{n} (1 - 2^{-j}) \ge 1 - (2^{-2} + \cdots + 2^{-n}) = \tfrac12 + 2^{-n}. The factor for j=1j = 1 is 12\tfrac12, so the fraction is at least 14+2−n−1\tfrac14 + 2^{-n-1}, which exceeds 14\tfrac14. ■\blacksquare

The matrices that are not invertible spread over the lower ranks. Of the 512 binary 3×33 \times 3 matrices, 1 has rank 0, 49 have rank 1, 294 have rank 2 and 168 have rank 3. A random binary square matrix of size 2 or more is singular more often than not, so kk random rows for a generator matrix can fail to have rank kk, and elimination is the check that rules this out.

11.Systematic Form

Run elimination on the generator matrix GG from Multiplying Two Matrices. Column 1 has a 0 in row 1, so R1↔R2R_1 \leftrightarrow R_2 brings up the row 11100011110001, and R3←R3+R1R_3 \leftarrow R_3 + R_1 and R4←R4+R1R_4 \leftarrow R_4 + R_1 clear the rest of the column. R1←R1+R2R_1 \leftarrow R_1 + R_2 clears column 2, then R2←R2+R3R_2 \leftarrow R_2 + R_3 and R4←R4+R3R_4 \leftarrow R_4 + R_3 clear column 3, and R2←R2+R4R_2 \leftarrow R_2 + R_4 and R3←R3+R4R_3 \leftarrow R_3 + R_4 clear column 4. The result is

S=[1000110010001100101000001111]=[ I4∣P ],P=[110011100111].S = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} = \left[\, I_4 \mid P \,\right], \qquad P = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{bmatrix}.

Row operations keep the row space, so SS generates the same 16 codewords as GG. What changes is the encoder. A message mm now becomes mS=(m,mP)m S = (m, m P), the message itself followed by n−kn - k parity bits. The message 10111011 selects rows 1, 3 and 4 of PP, and 110⊕100⊕111=101110 \oplus 100 \oplus 111 = 101, so its codeword is 10111011011101. Figure 7 draws this encoding.

The systematic generator matrix S = [I | P] reached from G by row operations alone, with the 4-by-4 identity on the left and the 4-by-3 block P on the right. The message m = 1011 keeps rows 1, 3 and 4 and drops row 2, and their sum is the codeword 1011101: its first four bits repeat the message and its last three are the parity bits m P = 101. 1 2 3 4 5 6 7 m 1 1 0 0 0 1 1 0 kept 0 0 1 0 0 0 1 1 dropped 1 0 0 1 0 1 0 0 kept 1 0 0 0 1 1 1 1 kept I, the identity P m S = 1 0 1 1 1 0 1 the message, copied parity, m P
Figure 7. Encoding with the systematic form S = [I | P]. The message 1011 selects rows 1, 3 and 4, the identity block copies it into the first four positions, and the block P supplies the three parity bits 101.

Under GG itself the same message gave 01110000111000, a different codeword of the same code. A systematic generator lets a receiver read the message straight off a corrected codeword. Lin and Costello place the message last instead, with a generator [ P∣Ik ]\left[\,P \mid I_k\,\right] [4].

Proof. Multiplying on the left by a k×kk \times k matrix EE acts on each block separately, so EG=[ EL∣EG′ ]E G = \left[\,E L \mid E G'\,\right]. If LL is invertible, the theorem on inversion reduces LL to IkI_k by row operations whose product is E=L−1E = L^{-1}, and these give [ Ik∣L−1G′ ]\left[\,I_k \mid L^{-1} G'\,\right]. Conversely, suppose row operations with product EE give EG=[ Ik∣P ]E G = \left[\,I_k \mid P\,\right]. Then EL=IkE L = I_k, and since EE is invertible, L=E−1EL=E−1L = E^{-1} E L = E^{-1}, which is invertible. So E=L−1E = L^{-1}, and the right block is P=EG′=L−1G′P = E G' = L^{-1} G'. ■\blacksquare

For GG the leading block is invertible, so no column has to move. The matrix AA fails the test. Its first three columns 110110, 101101 and 011011 add to zero, so its leading 3×33 \times 3 block is singular, and its reduced form 10101010, 01100110, 00010001 has its pivots in columns 1, 2 and 4. Taking the columns in the order 1, 2, 4, 3 gives the matrix [ I3∣P ]\left[\,I_3 \mid P\,\right] with rows 10011001, 01010101 and 00100010.

A column swap is not a row operation. It gives an equivalent code, a code whose words are those of the original with the positions permuted in one fixed way, here positions 3 and 4 exchanged, so it has the same length, size and weights. Moving the kk pivot columns of any generator of rank kk to the front in the same way yields [ Ik∣P ]\left[\,I_k \mid P\,\right], so every linear code is equivalent to one with a systematic generator. The kk pivot columns are an information set in the sense of Vector Spaces over Finite Fields, positions on which the codewords show every message exactly once.

12.Elimination Modulo Five

Over GF(2)\mathrm{GF}(2) every nonzero pivot is already 1. Over a larger field a pivot must be scaled to 1, which means multiplying its row by the inverse of the pivot. In GF(5)\mathrm{GF}(5) the inverses of 1, 2, 3 and 4 are 1, 3, 2 and 4, since 2⋅3=62 \cdot 3 = 6 and 4⋅4=164 \cdot 4 = 16 both leave remainder 1 on division by 5. Solve the system

[213131412]x=[302]\begin{bmatrix} 2 & 1 & 3 \\ 1 & 3 & 1 \\ 4 & 1 & 2 \end{bmatrix} x = \begin{bmatrix} 3 \\ 0 \\ 2 \end{bmatrix}

over GF(5)\mathrm{GF}(5), working on the augmented rows 213∣3213 \mid 3, 131∣0131 \mid 0 and 412∣2412 \mid 2.

The pivot of column 1 is 2, so R1←3R1R_1 \leftarrow 3 R_1 makes it 1 and turns row 1 into 134∣4134 \mid 4. Then R2←R2−R1R_2 \leftarrow R_2 - R_1 gives 002∣1002 \mid 1 and R3←R3−4R1R_3 \leftarrow R_3 - 4 R_1 gives 041∣1041 \mid 1, with every entry reduced modulo 5. Column 2 has a 0 in row 2, so R2↔R3R_2 \leftrightarrow R_3 brings up 041∣1041 \mid 1, and R2←4R2R_2 \leftarrow 4 R_2 makes its pivot 1, giving 014∣4014 \mid 4. Then R1←R1−3R2R_1 \leftarrow R_1 - 3 R_2 gives 102∣2102 \mid 2. The pivot of column 3 is 2, so R3←3R3R_3 \leftarrow 3 R_3 gives 001∣3001 \mid 3, and R1←R1−2R3R_1 \leftarrow R_1 - 2 R_3 and R2←R2−4R3R_2 \leftarrow R_2 - 4 R_3 clear the column.

[100101020013]\left[\begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 3 \end{array}\right]

The solution is x=(1,2,3)x = (1, 2, 3), and substituting checks it. Row 1 gives 2+2+9=13≡32 + 2 + 9 = 13 \equiv 3, row 2 gives 1+6+3=10≡01 + 6 + 3 = 10 \equiv 0, and row 3 gives 4+2+6=12≡24 + 2 + 6 = 12 \equiv 2. A search over all 125 words finds no other, as the theorem on solutions predicts at rank 3.

13.Elimination in Hardware

A binary row addition XORs one row into another bit by bit, and the bits do not interact. Figure 8 builds R2←R2+R1R_2 \leftarrow R_2 + R_1, the first step of eliminating AA, from four XOR gates side by side, which turn 10111011 into 01100110 in the time of one gate.

A row addition in hardware: row 2 of A, 1011, is replaced by row 2 plus row 1, 1011 + 1101. Bit j of each row feeds the j-th of four XOR gates, and the four gate outputs, 0110, are written back as the new row 2. The gates work in parallel, so the whole row costs one gate delay. 1 1 0 bit 1 1 0 1 bit 2 0 1 1 bit 3 1 1 0 bit 4 row 1 row 2 new row 2 The four gates work side by side, so one row addition costs one gate delay.
Figure 8. The row addition that starts the elimination of A, built from four XOR gates, one per bit. The gates do not depend on one another, so the whole addition takes the time of one gate.

Counting the gates comes down to counting additions. The elimination of AA used 4 row additions of 4 bits each, which is 16 bit XORs, and the elimination of GG used 7 additions of 7 bits, which is 49.

Proof. The theorem on elimination gives at most min⁡(m,n)\min(m, n) pivots, and over GF(2)\mathrm{GF}(2) the scaling step never occurs. Clearing the column of one pivot adds the pivot row to each other row that holds a 1 in that column, which is at most m−1m - 1 rows. So there are at most min⁡(m,n)(m−1)\min(m, n)(m - 1) additions, and each XORs nn pairs of bits. ■\blacksquare

For a 4×74 \times 7 matrix the bound is 4⋅3⋅7=844 \cdot 3 \cdot 7 = 84, against the 49 that the reduction of GG above used. For 3×43 \times 4 matrices it allows 6 additions, and under the rule that always takes the first row with a 1, a run over all 4,096 binary 3×43 \times 4 matrices finds 15 that use all 6. A swap uses no XOR gate. A circuit that must eliminate any matrix adds multiplexers to choose which row moves up and one AND gate per bit, so that a row's bit in the pivot column decides whether it receives the addition.

14.Looking Ahead

One procedure answered every question of the chapter, from rank and null space to solutions, inverses and systematic form, and over GF(2)\mathrm{GF}(2) every step was an XOR of one row into another.

The next chapter, Linear Codes, turns these tools into the definition of a code. A linear code is the row space of a generator matrix and the null space of a parity-check matrix, the rank theorem fixes how many codewords it holds, and the systematic form [ Ik∣P ]\left[\,I_k \mid P\,\right] leads to a parity-check matrix built from the same block PP.

15.Worked Examples

16.Exercises

References

  1. [1]Hamming, Richard W. (1950). “Error Detecting and Error Correcting Codes.” Bell System Technical Journal, 29(2), pp. 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x
  2. [2]Shen, Kangshen and Crossley, John N. and Lun, Anthony W.-C. (1999). “The Nine Chapters on the Mathematical Art: Companion and Commentary.” Oxford University Press. doi:10.1093/oso/9780198539360.001.0001
  3. [3]Grcar, Joseph F. (2011). “How Ordinary Elimination Became Gaussian Elimination.” Historia Mathematica, 38(2), pp. 163–218. doi:10.1016/j.hm.2010.06.003
  4. [4]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes