Congruence relation - Citizendia

See congruence (geometry) for the term as used in elementary geometry. In Geometry, two sets of points are called congruent if one can be transformed into the other by an Isometry, i

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). Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Abstract algebra is the subject area of Mathematics that studies Algebraic structures such as groups, rings, fields, modules In Mathematics, an equivalence relation is a Binary relation between two elements of a set which groups them together as being "equivalent"

1 Modular arithmetic
2 Linear algebra
3 Universal algebra
4 Congruences of groups, and normal subgroups and ideals
- 4.1 Ideals of rings and the general case of kernels
5 See also
6 References

Modular arithmetic

The prototypical example is modular arithmetic: for n a positive integer, two integers a and b are called congruent modulo n if a − b is divisible by n (or an equivalent condition is that they give the same remainder when divided by n). In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French

For example, 5 and 11 are congruent modulo 3:

$11 \equiv 5 \pmod 3$

because 11 − 5 gives 6, which is divisible by 3. Or, equally, both numbers give the same remainder when divided by 3:

$11 = 3\times 3 + 2$

$5 = 1\times 3 + 2$

If a₁ ≡ b₁ (mod n) and a₂ ≡ b₂ (mod n) then a₁ + a₂ ≡ b₁ + b₂ (mod n) and a₁a₂ ≡ b₁b₂ (mod n) This turns the congruence (mod n) into an equivalence on the ring of all integers. In Mathematics, a ring is an Algebraic structure which generalizes the algebraic properties of the Integers though the rational, real The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French

Linear algebra

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

$P^\top A P = B.$

A symmetric matrix has real eigenvalues. In Mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries) which may be Numbers or more generally In Mathematics, two matrices A and B over a field are called congruent if there exists an Invertible matrix P In Linear algebra, an n -by- n (square matrix A is called invertible or non-singular if there exists an n -by- In Mathematics, given a Linear transformation, an of that linear transformation is a nonzero vector which when that transformation is applied to it changes 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 have the same inertia. In Linear algebra, Sylvester's law of inertia is a Theorem describing a canonical representative for a real symmetric matrix under Congruence 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 ^Tcongruency (A and B are ^Tcongruent if there is an invertible matrix P such that P^TAP = 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. Universal algebra (sometimes called general algebra) is the field of Mathematics that studies Algebraic structures themselves not examples ("models" In Mathematics, one can often define a direct product of objectsalready known giving a new one In Mathematics, an equivalence relation is a Binary relation between two elements of a set which groups them together as being "equivalent" In Algebra (mathematics, the word "algebra" usually means a Vector space or module equipped with an additional bilinear operation

The kernel of a homomorphism is always a congruence. In the various branches of Mathematics that fall under the heading of Abstract algebra, the kernel of a Homomorphism measures the degree to which the homomorphism In Abstract algebra, a homomorphism is a structure-preserving map between two Algebraic structures (such as groups rings or Vector Indeed, every congruence arises as a kernel. 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. In Mathematics, given a set X and an Equivalence relation ~ on X, the equivalence class of an element a in X In Mathematics a quotient ring, also known as factor ring or residue class ring, is a construction in Ring theory, quite similar to the The function that maps every element of A to its equivalence class is a homomorphism, and the kernel of this homomorphism is ~.

The lattice Con A of all congruence relations on an algebra A is algebraic. In the mathematical area of Order theory, the compact or finite elements of a Partially ordered set are those elements that cannot be subsumed

Congruences of groups, and normal subgroups and ideals

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 (reflexivity);
Given any elements a and b of G, if a ~ b, then b ~ a (symmetry);
Given any elements a, b, and c of G, if a ~ b and b ~ c, then a ~ c (transitivity);
Given any elements a, a' , b, and b' of G, if a ~ a' and b ~ b' , then a * b ~ a' * b' . In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In Mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a Binary operation on that In Mathematics, a binary relation (or a dyadic or 2-place relation) is an arbitrary association of elements within a set or with elements of In Predicate logic, universal quantification is an attempt to formalize the notion that something (a Logical predicate) is true for everything, or every In Set theory, a Binary relation can have among other properties reflexivity or irreflexivity. The material conditional, also known as the material implication or truth functional conditional, expresses a property of certain Conditionals in Logic In Mathematics, a Binary relation R over a set X is symmetric if it holds for all a and b in X that In Logic and/or Mathematics, logical conjunction or and is a two-place Logical operation that results in a value of true if both of In Mathematics, a Binary relation R over a set X is transitive if whenever an element a is related to an element b
Given any elements a and a' of G, if a ~ a' , then a⁻¹ ~ a' ⁻¹ (this can actually be proven from the other four, so is strictly redundant);

Conditions 1, 2, and 3 say that ~ is an equivalence relation. In Mathematics, an equivalence relation is a Binary relation between two elements of a set which groups them together as being "equivalent"

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. In Mathematics, more specifically in Abstract algebra, a normal subgroup is a special kind of Subgroup. Specifically, a ~ b if and only if b⁻¹ * 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.

Ideals of rings and the general case of kernels

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. In Mathematics, a ring is an Algebraic structure which generalizes the algebraic properties of the Integers though the rational, real In Ring theory, a branch of Abstract algebra, an ideal is a special Subset of a ring. In Abstract algebra, the concept of a module over a ring is a generalization of the notion of Vector space, where instead of requiring the scalars In Abstract algebra, the concept of a module over a ring is a generalization of the notion of Vector space, where instead of requiring the scalars

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. In Abstract algebra, a branch of Mathematics, a monoid is an Algebraic structure with a single Associative Binary operation

References

Horn and Johnson, Matrix Analysis, Cambridge University Press, 1985. The word modulo (Latin with respect to a modulus of ___ is the Latin Ablative of Modulus which itself means "a small measure ISBN 0-521-38632-2. (Section 4. 5 discusses congruency of matrices. )

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents