Canonical form

Given a set S of objects with an equivalence relation R on S, a canonical form is given by designating some objects of S to be "in canonical form", such that every object under consideration is equivalent to exactly one object in canonical form. In other words, the canonical forms in S represent the equivalence classes, once and only once. To test whether two objects are equivalent, it then suffices to test equality on their canonical forms. A canonical form thus provides a classification theorem and more, in that it not only classifies every class, but also gives a distinguished (canonical) representative for each object in the class.

Formally, a canonicalization with respect to an equivalence relation R on a set S is a mapping c:S→S such that for all s, s1, s2 ∈ S:

1. c(s) = c(c(s))   (idempotence),
2. s1 R s2 if and only if c(s1) = c(s2)   (decisiveness), and
3. s R c(s)   (representativeness).

Property 3 is redundant; it follows by applying 2 to 1.

In practical terms, it is often advantageous to be able to recognize the canonical forms. There is also a practical, algorithmic question to consider: how to pass from a given object s in S to its canonical form s*? Canonical forms are generally used to make operating with equivalence classes more effective. For example, in modular arithmetic, the canonical form for a residue class is usually taken as the least non-negative integer in it. Operations on classes are carried out by combining these representatives, and then reducing the result to its least non-negative residue. The uniqueness requirement is sometimes relaxed, allowing the forms to be unique up to some finer equivalence relation, such as allowing for reordering of terms (if there is no natural ordering on terms).

A canonical form may simply be a convention, or a deep theorem. For example, polynomials are conventionally written with the terms in descending powers: it is more usual to write x + x + 30 than x + 30 + x, although the two forms define the same polynomial. By contrast, the existence of Jordan canonical form for a matrix is a deep theorem.

According to OED and LSJ, the term canonical stems from the Ancient Greek word kanonikós (κανονικός, "regular, according to rule") from kanṓn (κᾰνών, "rod, rule"). The sense of norm, standard, or archetype has been used in many disciplines. Mathematical usage is attested in a 1738 letter from Logan. The German term kanonische Form is attested in a 1846 paper by Eisenstein, later the same year Richelot uses the term Normalform in a paper, and in 1851 Sylvester writes:

"I now proceed to [...] the mode of reducing Algebraical Functions to their simplest and most symmetrical, or as my admirable friend M. Hermite well proposes to call them, their Canonical forms."

In the same period, usage is attested by Hesse ("Normalform"), Hermite ("forme canonique"), Borchardt ("forme canonique"), and Cayley ("canonical form").

In 1865, the Dictionary of Science, Literature and Art defines canonical form as:

In analytic geometry:

• The equation of a line: Ax + By = C, with A + B = 1 and C ≥ 0
• The equation of a circle: