Generator Matrix

Let be a Linear Code.
A generator matrix for is a matrix whose rows are a basis for

Lemma

Every linear code is equivalent to a linear code with Generator Matrix of form

Proof

We can perform row operations:

• swap 2 rows
• add one row to another
  (because rows are just basis vectors, this corresponds to permuting the basis or taking linear combinations of basis vectors to find new bases)
  By Gaussian elimination and some permutations we get , the generator matrix in row form:

Then with more row operations we can finish and get
with a matrix