Tricki
a repository of mathematical know-how

Prove the result for a representative of each equivalence class

Quick description

Sometimes one can prove a result for every element of a set with an equivalence relation on it by proving the result for a representative of each equivalence class and proving that if the result is true for some element then it is true for all elements that are equivalent to that element.

Prerequisites

Basic algebraic concepts, the notion of an equivalence relation. Other prerequisites vary from example to example.

Example 1: Jordan normal form

Two n\times n matrices A and B are similar if there is an invertible matrix P such that PAP^{-1}=B. A slightly strange result is that every n\times n matrix is similar to its transpose. It is strange because it is hard to interpret as a statement about linear maps. Given that it is true, it is also surprisingly hard to prove.

However, we can get a handle on the problem by observing that if A is similar to B and the result is true for A, then the result is true for B. Indeed, B is similar to A, which is similar to A^T, which is similar to B^T.

The relationship of similarity is an equivalence relation, so once we have made this observation, all we have to do is prove the result for one element of each equivalence class. A good idea under such circumstances is to try to find the "nicest" or "simplest" representative of each equivalence class.

This job is done for us by the Jordan normal form theorem, which says, as its name suggests, that every matrix is similar to a matrix in Jordan normal form. It is straightforward to prove the result for a Jordan block – take P to be the matrix that reverses the order of the basis elements (that is, the matrix with 1s on the "wrong" diagonal and zeros everywhere else) – and from that one can get the result for an arbitrary matrix in Jordan normal form. Therefore the result is proved.

Note iconContributions wanted This article could use additional contributions. This article could do with some more examples.