Let C be the code of length n of solutions to a matrix equa

Let C be the code (of length n ) of solutions to a matrix equation Ax = 0 . Define a relation on the set of words of length n by u v mod C if u + v C . Prove that this is an equivalence relation, and that for any word w , the equivalence class of w is the coset C + w .

Solution

A relation from X to X is called a relation in X.

If R is in X and: xRx x X R is refelexive

xRy yRx R is symmetric

xRy & yRz xRz R is transitive

An equivalence relation is a relation in X that has all three properties.

The smallest such relation (in X) is equality and the largest is X × X.

A partition of X is a disjoint set C of non-empty subsets of X whose union is X.

If R is an equivalence relation in X, and x X, then the set of all those elements y X for which xRy is the equivalence class of X with respect to R. If R is equality, then every element is an equivalence class.

If R is X × X, then X itself is the only equivalence class. We denote it x/R and X/R for the set of all equivalence classes.

Given a partition C of X, we write (x X/C y) as a new relation induced by C. If R is an equivalence relation in X, then the set of equivalence classes is a partition of X that induces R.

If C is a partition of X, then the induced relation is an equivalence relation whose set of equivalence classes is exactly C