# Congruence relation

### From Exampleproblems

*See congruence (geometry) for the term as used in elementary geometry.*

In mathematics and especially in abstract algebra, a **congruence relation** or simply **congruence** is an equivalence relation that is compatible with some algebraic operation(s).

## Contents |

## Modular arithmetic

The prototypical example is modular arithmetic: for *n* a positive natural number, two integers *a* and *b* are called **congruent modulo n** if

*a*−

*b*is divisible by

*n*.

If and , then and . This turns the equivalence (mod *n*) into a congruence on the ring of all integers.

## Linear algebra

Two real matrices *A* and *B* are called congruent if there is an invertible real matrix *P* such that

A symmetric matrix has real eigenvalues. The *inertia* of a symmetric matrix is a triple consisting of the number of positive eigenvalues, the number of zero eigenvalues, and the number of negative eigenvalues. *Sylvester's law of inertia* states that two symmetric real matrices are congruent if and only if they the same inertia. So, congruence transformations may change the eigenvalues of a matrix but they cannot change the signs of the eigenvalues.

For complex matrices, we have to distinguish between ^{T}congruency (*A* and *B* are ^{T}congruent if there is an invertible matrix *P* such that *P*^{T}*AP* = *B*) and *congruency (*A* and *B* are *congruent if there is an invertible matrix *P* such that *P***AP* = *B*).

## Universal algebra

The idea is generalized in universal algebra:
A congruence relation on an algebra *A* is a subset of the direct product *A* × *A* that is both an equivalence relation on *A* and a subalgebra of *A* × *A*.

Congruences typically arise as kernels of homomorphisms, and in fact every congruence is the kernel of *some* homomorphism:
For a given congruence ~ on *A*, the set *A*/~ of equivalence classes can be given the structure of an algebra in a natural fashion, the quotient algebra.
Furthermore, the function that maps every element of *A* to its equivalence class is a homomorphism, and the kernel of this homomorphism is ~.

## Group theory

In the particular case of groups, congruence relations can be described in elementary terms as follows:
If *G* is a group (with identity element *e*) and ~ is a binary relation on *G*, then ~ is a congruence whenever:

- Given any element
*a*of*G*,*a*~*a*; - Given any elements
*a*and*b*of*G*, if*a*~*b*, then*b*~*a*; - Given any elements
*a*,*b*, and*c*of*G*, if*a*~*b*and*b*~*c*, then*a*~*c*; *e*~*e*;- Given any elements
*a*and*a*' of*G*, if*a*~*a*', then*a*^{−1}~*a*'^{−1}; - Given any elements
*a*,*a*',*b*, and*b*' of*G*, if*a*~*a*' and*b*~*b*', then*a***b*~*a*' **b*'.

(However, we can actually shorten the list of requirements to just numbers 1, 2, 3, and 6.)

Notice that such a congruence ~ is determined entirely by the set {*a* ∈ *G* : *a* ~ *e*} of those elements of *G* that are congruent to the identity element, and this set is a normal subgroup.
Specifically, *a* ~ *b* iff *b*^{−1} * *a* ~ *e*.
So instead of talking about congruences on groups, people usually speak in terms of normal subgroups of them; in fact, every congruence corresponds uniquely to some normal subgroup of *G*.
This is what makes it possible to speak of kernels in group theory as subgroups, while in more general universal algebra, kernels are congruences.

## Ring theory

A similar trick allows one to speak of kernels in ring theory as ideals instead of congruence relations, and in module theory as submodules instead of congruence relations.

## General case of kernels

The most general situation where this trick is possible is in ideal-supporting algebras. But this cannot be done with, for example, monoids, so the study of congruence relations plays a more central role in monoid theory.

## See also

## References

- Horn and Johnson,
*Matrix Analysis,*Cambridge University Press, 1985. ISBN 0-521-38632-2. (Section 4.5 discusses congruency of matrices.)de:Kongruenzrelation

es:congruencia fr:Congruence io:Kongruo pl:Kongruencja ru:Сравнение по модулю sl:Kongruenca zh:同馀