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 k over GF(q) holds qk 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) 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.
Three parity checks on a 4-bit word x=x1x2x3x4 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 1101, 1011 and 0111. Stacked one above the other, the rows form a table with three rows and four columns.
A=110101011111
The matrix A above is 3×4, and its entry a23 is 1 because the second check reads bit 3. Each row of a matrix is a word of length n and each column is a word of length m, 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=1011, and a word that multiplies a matrix from the right stands as a column.
Take x=1011. The first check XORs bits 1, 2 and 4, which gives 1⊕0⊕1=0. The second XORs bits 1, 3 and 4, which gives 1⊕1⊕1=1, and the third XORs bits 2, 3 and 4, which gives 0⊕1⊕1=0. The three results, read top to bottom, form the word 010. Each result is the dot product of Vector Spaces over Finite Fields, taken between a row of A and x. 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=1011 has 1s in positions 1, 3 and 4, and the columns of A in those positions are 110, 011 and 111, read top to bottom. Their XOR is 110⊕011⊕111=010, the same answer as before.
Proof. Entry i of the combination on the right is x1ai1+⋯+xnain, since entry i of the column cj is aij. Multiplication in a field is commutative, so this sum equals ai1x1+⋯+ainxn, which is yi by the definition. Every combination of the columns has the form on the right for some coefficients xj, which proves the claim about the column space. For linearity, entry i of A(x+x′) is ∑jaij(xj+xj′), and the distributive law splits it into ∑jaijxj+∑jaijxj′. The same law gives ∑jaij(cxj)=c∑jaijxj. ■
Figure 1 builds the row reading in hardware. A row of weight w, meaning a row with w ones, XORs w bits, and a chain of two-input XOR gates does that with w−1 gates. Each row of A has weight 3, so the three parity sums cost 2+2+2=6 gates. The second and third checks share the pair x3⊕x4, so a network that computes t=x3⊕x4 once and then forms x1⊕t and x2⊕t needs only 5 gates, and a check of all 16 inputs confirms that it agrees with Ax.
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 H lists the checks that a code imposes, one per row, and a received word r passes them all exactly when Hr=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 Hr.
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=[1011],F=[1101].
Row 1 of E is 11, so row 1 of EF is the XOR of both rows of F, which is 10⊕11=01. Row 2 of E is 01, so row 2 of EF is row 2 of F, which is 11. In the other order, row 1 of FE is row 1 of E, which is 11, and row 2 is 11⊕01=10. So EF=FE, and the order of a product matters. How a longer product is grouped does not.
Proof. Entry (i,j) of (AB)C is ∑s(AB)iscsj=∑s∑rairbrscsj, a sum over all pairs (r,s). Entry (i,j) of A(BC) is ∑rair(BC)rj=∑r∑sairbrscsj, 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 IA, entry (i,j) is ∑rδirarj, where δir is 1 when r=i and 0 otherwise, so only the term with r=i survives and the entry is aij. The case AI is the same with rows and columns exchanged. ■
A message multiplies a matrix from the left. A generator matrix G of size k×n turns a message m of length k, written as a row, into the codeword mG, which by the definition is the XOR of the rows of G that m selects. Take the 4×7 binary matrix
G=0111111111000010100110101101.
The message 1011 selects rows 1, 3 and 4, and its codeword is 0110111⊕1101010⊕1100101=0111000. The codewords of G are the combinations of its rows, so the code is the row space of G, while the code of a parity-check matrix is its null space.
Elimination changes a matrix one row at a time, and only in three ways.
Over GF(2) the only nonzero scalar is 1, so scaling does nothing and every row addition has c=1. Binary elimination therefore uses swaps and the additions Ri←Ri+Rj, each an XOR of one row into another. Applied to A, the addition R2←R2+R1 replaces the second row 1011 by 1011⊕1101=0110.
Each of the three can be undone. Repeating a swap restores the rows. Scaling by c is undone by scaling by c−1, which exists because c is a nonzero element of a field. Adding cRj to Ri is undone by adding −cRj, and over GF(2), where −1=1, by adding Rj a second time, since 0110⊕1101=1011 brings back the original row.
Each row operation is also a matrix product. Applying R2←R2+R1 to the 3×3 identity gives
E21=110010001,
and multiplying A on the left by E21 keeps rows 1 and 3 of A and replaces row 2 by the XOR of rows 1 and 2, exactly as the operation does.
Proof. Row i of EA is the combination of the rows of A whose coefficients are the entries of row i of E. A row of E that ρ did not touch is the identity row ei, with 1 in position i and 0 elsewhere, and it selects row i of A unchanged. A swap makes rows i and j of E equal to ej and ei, a scaling makes row i equal to cei, and a row addition makes it ei+cej, which select Rj and Ri, then cRi, then Ri+cRj. In each case EA=ρ(A). Applying this with A=E gives E′E=ρ′(E)=ρ′(ρ(I))=I, since ρ′ undoes ρ, and exchanging the roles of ρ and ρ′ gives EE′=I. ■
A sequence of row operations is therefore left multiplication by a product Et⋯E2E1 of elementary matrices, and by associativity that product is invertible, with inverse E1−1E2−1⋯Et−1.
Proof. Write B=EA with E invertible. If Ax=0 then Bx=E(Ax)=0, and if Bx=0 then Ax=E−1(Bx)=0, using associativity both times. Each row of B is a combination of the rows of A, so the row space of B lies inside the row space of A. The same holds with A=E−1B and the roles exchanged, so the two row spaces are equal. ■
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 A.
Column 1 of A 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+R1 clears it, giving the rows 1101, 0110 and 0111. 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+R2 and R3←R3+R2 clear them, giving 1011, 0110 and 0001. 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+R3 clears the 1 above it.
Four row additions turned A 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.
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 r for the next pivot row, starting at 1, and treats each column j from left to right. If every entry of column j in rows r and below is zero, the column is free and the counter stays. Otherwise a row at or below r with a nonzero entry in column j is swapped into row r and scaled so that the entry becomes 1, a suitable multiple of it is added to every other row to clear column j, and r increases by one.
Proof. Every step is a row operation, and the procedure ends after the last column. The claim, by induction on j, is that after column j the first j columns are in reduced row echelon form and rows r and below are zero in them. For j=0 there are no columns yet, so the claim holds with nothing to check. If column j is free, its entries in rows r and below are already zero. Otherwise the swap and the scaling touch only rows r and below, which are zero in columns 1 to j−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 j. The new pivot sits below and to the right of every earlier one, and rows r+1 and below are now zero in the first j columns. The case j=n is the theorem. Each pivot uses its own row and its own column, so there are at most min(m,n) of them. ■
Figure 3 shows the shape that results, a staircase of pivots with zeros below it.
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].
Run elimination on a second matrix, the 3×6 binary matrix
B=011101110011101101.
Column 1 has a 0 in row 1, so the swap R1↔R2 brings a 1 to the top. Row 3 has a 1 in column 1, and R3←R3+R1 gives 110111⊕101100=011011, so the rows are now 101100, 011011 and 011011. Column 2 has a 1 in row 2, row 1 already has a 0 there, and R3←R3+R2 turns row 3 into 000000. No row remains for a third pivot, and the result is
100010110100010010.
Three rows went in and two pivots came out. Row 3 of B is the XOR of rows 1 and 2, as 011011⊕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 of the nonzero rows ρi of R is zero. The pivot of row i lies in a column where every other row of R holds 0, so the entry of the combination in that column is λi⋅1=λi. That entry is 0, so every λi is 0 and the rows are independent. The row space of R equals the row space of A by the lemma on row operations, and zero rows add nothing to a span, so the nonzero rows span the row space of A. An independent spanning set is a basis, and its size is the dimension. ■
The rank of A is 3 and the rank of B is 2. A matrix with m rows has rank m exactly when its rows are independent, because only then does the row space have dimension m. For a generator matrix this test decides whether a message can be recovered from its codeword. If the rows of G are dependent, some nonzero λ has λG=0, and then mG=(m+λ)G for every message m, so two different messages share each codeword.
The null space of B is the set of words x of length 6 with Bx=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=0
Each equation holds exactly one pivot variable, x1 in the first and x2 in the second. The free variables x3, x4, x5 and x6 can take any values, and then the pivot variables are forced. Over GF(2), where −1=1, the equations give x1=x3+x4 and x2=x3+x5+x6. 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=1 the equations force x1=1 and x2=1, which gives 111000. The other three free variables give 100100, 010010 and 010001. 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 i of R has 1 in its pivot column p and 0 in the other pivot columns. Applied to vf it gives 1⋅(−rif)+rif⋅1=0, because vf is zero in every other free position. So each vf lies in the null space of R, which is the null space of A. In a combination ∑fλfvf the entry in position f is λf alone, so a zero combination has every λf=0 and the words are independent. To show that they span, take any x with Ax=0. The word z=x−∑fxfvf lies in the null space and is zero in every free position, so row i of R applied to z reads off its pivot entry zp, which must be 0. So z=0 and x=∑fxfvf. ■
Counting the basis gives the central result of the chapter.
Proof. The reduced form has rank(A) pivot columns, and the other n−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). A space of dimension d over GF(q) holds qd words, as Vector Spaces over Finite Fields showed. ■
Table 1 applies it to five of the binary matrices that the chapter reduces. For B it gives 2+4=6 and a null space of 24=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
Matrix
Size
Rank
Nullity
Words in the null space
A
3×4
3
1
2
B
3×6
2
4
16
G
4×7
4
3
8
M
3×3
3
0
1
C
3×5
3
2
4
Source: reproduced by ch16_matrices_and_elimination_over_finite_fields.py.
For codes the theorem counts codewords. A parity-check matrix H of size (n−k)×n with independent rows has rank n−k, so its null space, the code, has dimension n−(n−k)=k and holds 2k codewords.
A linear system asks for every x with Ax=b for a given word b. Elimination solves it by working on the augmented matrix [A∣b], which attaches b as an extra column. Row operations on the augmented matrix act on both sides of every equation at once.
For Bx=100, the operations that reduced B act on the attached column too. The swap moves its bits to 010, the addition R3←R3+R1 leaves the last bit of row 3 at 0, and R3←R3+R2 makes it 1. Row 3 now reads 000000∣1, which says 0=1. No word satisfies that equation, so the system has no solution. For Bx=110 the same steps give
100010110100010010110.
Setting the free variables to 0 gives x1=1 and x2=1, so xp=110000 is one solution. Adding any word v of the null space to xp gives another, since B(xp+v)=Bxp+Bv=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 E, and Ax=b holds exactly when EAx=Eb, so the reduced augmented matrix has the same solutions. If its last column holds a pivot, that pivot's row reads 0=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=b and Av=0, then A(xp+v)=b by linearity, and if Ax=b then A(x−xp)=0, so every solution lies in xp+N(A). The map v↦xp+v is one to one, so the solution set has as many elements as N(A), which is qn−rank(A) by the rank theorem. ■
The solution sets are cosets in the sense of Groups and Cosets, translates of the subgroup N(A). Figure 4 draws them for A, whose reduced form has a pivot in every row and so leaves no row that could read 0=1. Every right side is reachable, and each of the eight has exactly 24−3=2 solutions, which differ by 1110, the one nonzero word of N(A). For B, each reachable right side has 16 solutions, so only 64/16=4 of the 8 right sides are reachable.
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 H the same picture is the syndrome decoder of Groups and Cosets. The received words r with syndrome Hr=s form one coset of the code, and the code itself is the coset of the zero syndrome.
Take the 3×3 binary matrix M with rows 110, 011 and 111. Solving Mx=b for one right side at a time would repeat the same row operations for each b, so elimination works on the three columns of the identity at once, through the augmented matrix [M∣I]. R3←R3+R1 clears column 1, R1←R1+R2 clears column 2, and R1←R1+R3 and R2←R2+R3 clear column 3. Figure 5 follows the six columns through these steps.
The left half became I, and the right half holds the rows 011, 111 and 101. Multiplying confirms that this is the inverse. Row 1 of M is 110, so row 1 of MM−1 is 011⊕111=100, and the other two rows give 010 and 001 the same way.
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 E be the product of the elementary matrices used, so that EA=R is the reduced form. A square matrix in reduced row echelon form with n pivots has a pivot in every row and every column, stepping down the diagonal, and each pivot is alone in its column, so R=I exactly when the rank is n. If R=I then EA=I. Since E is invertible, A=E−1EA=E−1, and therefore AE=E−1E=I as well, so E is the inverse of A. The same operations applied to [A∣I] give [EA∣EI]=[I∣A−1]. If instead the rank is below n, the rank theorem gives a nullity of at least 1, so some v=0 has Av=0. An inverse would give v=A−1Av=0, a contradiction, so A has no inverse. ■
The matrix M passes this test, and the matrix U with rows 110, 011 and 101 fails it. Its third row is the XOR of the first two, its reduced form has rows 101, 011 and 000, and its rank is 2. Where an inverse exists it solves every system at once. The solution of Mx=110 is M−1⋅110, the XOR of columns 1 and 2 of M−1, which is 011⊕110=101, and indeed M⋅101=110.
Of the 16 binary 2×2 matrices, 6 are invertible. The first row can be any of the 3 nonzero words 01, 10 and 11, 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, A is invertible exactly when its rank is n, and by the lemma on pivot rows the rank is the dimension of the row space, which is n exactly when the n rows are independent. Count independent rows in order. Once rows 1 to i are chosen and independent, their span has dimension i and holds qi words, and row i+1 keeps the rows independent exactly when it lies outside that span, which leaves qn−qi choices. For i=0 the span is {0} and the first row is any nonzero word. Multiplying the numbers of choices for i=0,1,…,n−1 gives the product. This is the theorem on counting ordered independent lists from Vector Spaces over Finite Fields, applied to the n rows. ■
For q=2 the formula gives 3⋅2=6 for n=2, then 7⋅6⋅4=168 and 15⋅14⋅12⋅8=20160. Table 2 lists the counts up to n=7 beside the totals 2n2, and for n≤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
n
Invertible
All, 2n2
Fraction invertible
1
1
2
0.500000
2
6
16
0.375000
3
168
512
0.328125
4
20,160
65,536
0.307617
5
9,999,360
33,554,432
0.298004
6
20,158,709,760
68,719,476,736
0.293348
7
163,849,992,929,280
562,949,953,421,312
0.291056
Source: reproduced by ch16_matrices_and_elimination_over_finite_fields.py.
Dividing each factor 2n−2i by 2n turns the fraction into a product whose factors approach 1.
2n2Nn(2)=j=1∏n(1−2−j)=21⋅43⋅87⋯(1−2−n)
(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=10, against a limit of 0.288788 as n grows.
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,…,at between 0 and 1, write Pt=∏j≤t(1−aj) and St=∑j≤taj. Then Pt≥1−St by induction on t, because multiplying the bound by 1−at+1≥0 gives Pt+1≥(1−St)(1−at+1)=1−St+1+at+1St≥1−St+1. Applied to the factors from j=2 to n, it gives ∏j=2n(1−2−j)≥1−(2−2+⋯+2−n)=21+2−n. The factor for j=1 is 21, so the fraction is at least 41+2−n−1, which exceeds 41. ■
The matrices that are not invertible spread over the lower ranks. Of the 512 binary 3×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 k random rows for a generator matrix can fail to have rank k, and elimination is the check that rules this out.
Run elimination on the generator matrix G from Multiplying Two Matrices. Column 1 has a 0 in row 1, so R1↔R2 brings up the row 1110001, and R3←R3+R1 and R4←R4+R1 clear the rest of the column. R1←R1+R2 clears column 2, then R2←R2+R3 and R4←R4+R3 clear column 3, and R2←R2+R4 and R3←R3+R4 clear column 4. The result is
Row operations keep the row space, so S generates the same 16 codewords as G. What changes is the encoder. A message m now becomes mS=(m,mP), the message itself followed by n−k parity bits. The message 1011 selects rows 1, 3 and 4 of P, and 110⊕100⊕111=101, so its codeword is 1011101. Figure 7 draws this encoding.
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 G itself the same message gave 0111000, 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][4].
Proof. Multiplying on the left by a k×k matrix E acts on each block separately, so EG=[EL∣EG′]. If L is invertible, the theorem on inversion reduces L to Ik by row operations whose product is E=L−1, and these give [Ik∣L−1G′]. Conversely, suppose row operations with product E give EG=[Ik∣P]. Then EL=Ik, and since E is invertible, L=E−1EL=E−1, which is invertible. So E=L−1, and the right block is P=EG′=L−1G′. ■
For G the leading block is invertible, so no column has to move. The matrix A fails the test. Its first three columns 110, 101 and 011 add to zero, so its leading 3×3 block is singular, and its reduced form 1010, 0110, 0001 has its pivots in columns 1, 2 and 4. Taking the columns in the order 1, 2, 4, 3 gives the matrix [I3∣P] with rows 1001, 0101 and 0010.
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 k pivot columns of any generator of rank k to the front in the same way yields [Ik∣P], so every linear code is equivalent to one with a systematic generator. The k 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.
Over 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) the inverses of 1, 2, 3 and 4 are 1, 3, 2 and 4, since 2⋅3=6 and 4⋅4=16 both leave remainder 1 on division by 5. Solve the system
214131312x=302
over GF(5), working on the augmented rows 213∣3, 131∣0 and 412∣2.
The pivot of column 1 is 2, so R1←3R1 makes it 1 and turns row 1 into 134∣4. Then R2←R2−R1 gives 002∣1 and R3←R3−4R1 gives 041∣1, with every entry reduced modulo 5. Column 2 has a 0 in row 2, so R2↔R3 brings up 041∣1, and R2←4R2 makes its pivot 1, giving 014∣4. Then R1←R1−3R2 gives 102∣2. The pivot of column 3 is 2, so R3←3R3 gives 001∣3, and R1←R1−2R3 and R2←R2−4R3 clear the column.
100010001123
The solution is x=(1,2,3), and substituting checks it. Row 1 gives 2+2+9=13≡3, row 2 gives 1+6+3=10≡0, and row 3 gives 4+2+6=12≡2. A search over all 125 words finds no other, as the theorem on solutions predicts at rank 3.
A binary row addition XORs one row into another bit by bit, and the bits do not interact. Figure 8 builds R2←R2+R1, the first step of eliminating A, from four XOR gates side by side, which turn 1011 into 0110 in the time of one gate.
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 A used 4 row additions of 4 bits each, which is 16 bit XORs, and the elimination of G used 7 additions of 7 bits, which is 49.
Proof. The theorem on elimination gives at most min(m,n) pivots, and over 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−1 rows. So there are at most min(m,n)(m−1) additions, and each XORs n pairs of bits. ■
For a 4×7 matrix the bound is 4⋅3⋅7=84, against the 49 that the reduction of G above used. For 3×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×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.
One procedure answered every question of the chapter, from rank and null space to solutions, inverses and systematic form, and over 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] leads to a parity-check matrix built from the same block P.
[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]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]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]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.