 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Canonical form" – news ·newspapers ·books ·scholar ·JSTOR(December 2007) (Learn how and when to remove this message) |
Inmathematics andcomputer science, acanonical,normal, orstandardform of amathematical object is a standard way of presenting that object as amathematical expression. Often, it is one which provides the simplest representation of an object and allows it to be identified in a unique way. The distinction between "canonical" and "normal" forms varies from subfield to subfield. In most fields, a canonical form specifies aunique representation for every object, while a normal form simply specifies its form, without the requirement of uniqueness.[1]
The canonical form of apositive integer indecimal representation is a finite sequence of digits that does not begin with zero. More generally, for a class of objects on which anequivalence relation is defined, a canonical form consists in the choice of a specific object in each class. For example:
In computer science, and more specifically incomputer algebra, when representing mathematical objects in a computer, there are usually many different ways to represent the same object. In this context, a canonical form is a representation such that every object has a unique representation (withcanonicalization being the process through which a representation is put into its canonical form).[2] Thus, the equality of two objects can easily be tested by testing the equality of their canonical forms.
Despite this advantage, canonical forms frequently depend on arbitrary choices (like ordering the variables), which introduce difficulties for testing the equality of two objects resulting on independent computations. Therefore, in computer algebra,normal form is a weaker notion: A normal form is a representation such that zero is uniquely represented. This allows testing for equality by putting the difference of two objects in normal form.
Canonical form can also mean adifferential form that is defined in a natural (canonical) way.
Given a setS of objects with anequivalence relationR on S, a canonical form is given by designating some objects ofS 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 inS 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 aclassification 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 relationR on a setS is a mappingc:S→S such that for alls,s1,s2 ∈S:
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 objects inS to its canonical forms*? Canonical forms are generally used to make operating with equivalence classes more effective. For example, inmodular 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 writex2 +x + 30 thanx + 30 +x2, although the two forms define the same polynomial. By contrast, the existence ofJordan canonical form for a matrix is a deep theorem.
According toOED andLSJ, the termcanonical stems from theAncient Greek wordkanonikós (κανονικός, "regular, according to rule") fromkanṓn (κᾰνών, "rod, rule"). The sense ofnorm,standard, orarchetype has been used in many disciplines. Mathematical usage is attested in a 1738 letter fromLogan.[3] The German termkanonische Form is attested in a 1846 paper byEisenstein,[4] later the same yearRichelot uses the termNormalform in a paper,[5] and in 1851Sylvester writes:[6]
"I now proceed to [...] the mode of reducing Algebraical Functions to their simplest and most symmetrical, or as my admirable friendM. Hermite well proposes to call them, theirCanonical forms."
In the same period, usage is attested byHesse ("Normalform"),[7]Hermite ("forme canonique"),[8]Borchardt ("forme canonique"),[9] andCayley ("canonical form").[10]
In 1865, theDictionary of Science, Literature and Art defines canonical form as:
"In Mathematics, denotes a form, usually the simplest or most symmetrical, to which, without loss of generality, all functions of the same class can be reduced."
Note: in this section, "up to" some equivalence relation E means that the canonical form is not unique in general, but that if one object has two different canonical forms, they are E-equivalent.
Standard form is used by many mathematicians and scientists to write extremelylarge numbers in a more concise and understandable way, the most prominent of which being thescientific notation.[11]
| Objects | A is equivalent toB if: | Normal form | Notes |
|---|---|---|---|
| Normal matrices over thecomplex numbers | for someunitary matrixU | Diagonal matrices (up to reordering) | This is theSpectral theorem |
| Matrices over the complex numbers | for some unitary matricesU andV | Diagonal matrices with real non-negative entries (in descending order) | Singular value decomposition |
| Matrices over analgebraically closed field | for someinvertible matrixP | Jordan normal form (up to reordering of blocks) | |
| Matrices over an algebraically closed field | for some invertible matrixP | Weyr canonical form (up to reordering of blocks) | |
| Matrices over a field | for some invertible matrixP | Frobenius normal form | |
| Matrices over aprincipal ideal domain | for some invertible matricesP andQ | Smith normal form | The equivalence is the same as allowing invertible elementary row and column transformations |
| Matrices over the integers | for someunimodular matrixU | Hermite normal form | |
| Matrices over theintegers modulo n | Howell normal form | ||
| Finite-dimensionalvector spaces over a fieldK | A andB are isomorphic as vector spaces | ,n a non-negative integer |
| Objects | A is equivalent toB if: | Normal form |
|---|---|---|
| Finitely generatedR-modules withR aprincipal ideal domain | A andB are isomorphic asR-modules | Primary decomposition (up to reordering) or invariant factor decomposition |
By contrast, there are alternative forms for writing equations. For example, the equation of a line may be written as alinear equation inpoint-slope andslope-intercept form.
Convex polyhedra can be put intocanonical form such that:
Every differentiablemanifold has acotangent bundle. That bundle can always be endowed with a certaindifferential form, called thecanonical one-form. This form gives the cotangent bundle the structure of asymplectic manifold, and allows vector fields on the manifold to be integrated by means of theEuler-Lagrange equations, or by means ofHamiltonian mechanics. Such systems of integrabledifferential equations are calledintegrable systems.
The study ofdynamical systems overlaps with that ofintegrable systems; there one has the idea of anormal form (dynamical systems).
In the study of manifolds in three dimensions, one has thefirst fundamental form, thesecond fundamental form and thethird fundamental form.
| Objects | A is equivalent toB if: | Normal form |
|---|---|---|
| Hilbert spaces | IfA andB are both Hilbert spaces of infinite dimension, thenA andB are isometrically isomorphic. | sequence spaces (up to exchanging the index setI with another index set of the samecardinality) |
| CommutativeC*-algebras with unit | A andB are isomorphic as C*-algebras | The algebra of continuous functions on acompactHausdorff space, up tohomeomorphism of the base space. |
The symbolic manipulation of a formula from one form to another is called a "rewriting" of that formula. One can study the abstract properties of rewriting generic formulas, by studying the collection of rules by which formulas can be validly manipulated. These are the "rewriting rules"—an integral part of anabstract rewriting system. A common question is whether it is possible to bring some generic expression to a single, common form, the normal form. If different sequences of rewrites still result in the same form, then that form can be termed a normal form, with the rewrite being called a confluent. It is not always possible to obtain a normal form.
Ingraph theory, a branch of mathematics, graph canonization is the problem of finding a canonical form of a given graphG. A canonical form is alabeled graph Canon(G) that isisomorphic toG, such that every graph that is isomorphic toG has the same canonical form asG. Thus, from a solution to the graph canonization problem, one could also solve the problem ofgraph isomorphism: to test whether two graphsG andH are isomorphic, compute their canonical forms Canon(G) and Canon(H), and test whether these two canonical forms are identical.
Incomputing, the reduction of data to any kind of canonical form is commonly calleddata normalization.
For instance,database normalization is the process of organizing thefields andtables of arelational database to minimizeredundancy and dependency.[13]
In the field ofsoftware security, a commonvulnerability is unchecked malicious input (seeCode injection). The mitigation for this problem is properinput validation. Before input validation is performed, the input is usually normalized by eliminating encoding (e.g.,HTML encoding) and reducing the input data to a single commoncharacter set.
Other forms of data, typically associated withsignal processing (includingaudio andimaging) ormachine learning, can be normalized in order to provide a limited range of values.
Incontent management, the concept of asingle source of truth (SSOT) is applicable, just as it is indatabase normalization generally and insoftware development. Competentcontent management systems provide logical ways of obtaining it, such astransclusion.