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.
Basic algebraic concepts, the notion of an equivalence relation. Other prerequisites vary from example to example.
Example 1: Jordan normal form
Two matrices and are similar if there is an invertible matrix such that A slightly strange result is that every 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 is similar to and the result is true for , then the result is true for . Indeed, is similar to , which is similar to , which is similar to
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 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.