TABLE OF CONTENTS Since a linear code is a vector space, all its elements can be described in terms of a basis. In this section, we discuss three algorithms that yield either a basis for a given linear code or its dual. We first recall some facts from linear algebra.
Let A be a matrix over F q; an elementary row operation performed on A is any one of the following three operations:
interchanging two rows,
multiplying a row by a nonzero scalar,
replacing a row by its sum with the scalar multiple of another row.
Two matrices are row equivalent if one can be obtained from the other by a sequence of elementary row operations.
The following are well known facts from linear algebra:
Any matrix M over F q can be put in row echelon form ( REF) or reduced row echelon form ( RREF) by a sequence of elementary row operations. In other words, a matrix is row equivalent to a matrix in REF or in RREF.
For a given matrix, its RREF is unique, but it may have different REFs. (Recall that the difference between the RREF and the REF is that the leading nonzero entry of a row in the RREF is equal to 1 and it is the only nonzero entry in its column.)
We are now ready to describe the three...
