fbpx
Wikipedia

Canonical form

In mathematics and computer science, a canonical, normal, or standard form of a mathematical object is a standard way of presenting that object as a mathematical 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 a unique representation for every object, while a normal form simply specifies its form, without the requirement of uniqueness.[1]

Algorithmic anagram test using multisets as canonical forms: The strings "madam curie" and "radium came" are given as C arrays. Each one is converted into a canonical form by sorting. Since both sorted strings literally agree, the original strings were anagrams of each other.

The canonical form of a positive integer in decimal representation is a finite sequence of digits that does not begin with zero. More generally, for a class of objects on which an equivalence 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 in computer 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 (with canonicalization 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 a differential form that is defined in a natural (canonical) way.

Definition Edit

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:SS such that for all s, s1, s2S:

  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 x2 + x + 30 than x + 30 + x2, although the two forms define the same polynomial. By contrast, the existence of Jordan canonical form for a matrix is a deep theorem.

History Edit

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.[3] The German term kanonische Form is attested in a 1846 paper by Eisenstein,[4] later the same year Richelot uses the term Normalform in a paper,[5] and in 1851 Sylvester writes:[6]

"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"),[7] Hermite ("forme canonique"),[8] Borchardt ("forme canonique"),[9] and Cayley ("canonical form").[10]

In 1865, the Dictionary 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."

Examples Edit

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.

Large number notation Edit

Standard form is used by many mathematicians and scientists to write extremely large numbers in a more concise and understandable way, the most prominent of which being the scientific notation.[11]

Number theory Edit

Linear algebra Edit

Objects A is equivalent to B if: Normal form Notes
Normal matrices over the complex numbers   for some unitary matrix U Diagonal matrices (up to reordering) This is the Spectral theorem
Matrices over the complex numbers   for some unitary matrices U and V Diagonal matrices with real positive entries (in descending order) Singular value decomposition
Matrices over an algebraically closed field   for some invertible matrix P Jordan normal form (up to reordering of blocks)
Matrices over an algebraically closed field   for some invertible matrix P Weyr canonical form (up to reordering of blocks)
Matrices over a field   for some invertible matrix P Frobenius normal form
Matrices over a principal ideal domain   for some invertible matrices P and Q Smith normal form The equivalence is the same as allowing invertible elementary row and column transformations
Matrices over the integers   for some unimodular matrix U Hermite normal form
Matrices over the integers modulo n Howell normal form
Finite-dimensional vector spaces over a field K A and B are isomorphic as vector spaces  , n a non-negative integer

Algebra Edit

Objects A is equivalent to B if: Normal form
Finitely generated R-modules with R a principal ideal domain A and B are isomorphic as R-modules Primary decomposition (up to reordering) or invariant factor decomposition

Geometry Edit

In analytic geometry:

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

By contrast, there are alternative forms for writing equations. For example, the equation of a line may be written as a linear equation in point-slope and slope-intercept form.

Convex polyhedra can be put into canonical form such that:

  • All faces are flat,
  • All edges are tangent to the unit sphere, and
  • The centroid of the polyhedron is at the origin.[12]

Integrable systems Edit

Every differentiable manifold has a cotangent bundle. That bundle can always be endowed with a certain differential form, called the canonical one-form. This form gives the cotangent bundle the structure of a symplectic manifold, and allows vector fields on the manifold to be integrated by means of the Euler-Lagrange equations, or by means of Hamiltonian mechanics. Such systems of integrable differential equations are called integrable systems.

Dynamical systems Edit

The study of dynamical systems overlaps with that of integrable systems; there one has the idea of a normal form (dynamical systems).

Three dimensional geometry Edit

In the study of manifolds in three dimensions, one has the first fundamental form, the second fundamental form and the third fundamental form.

Functional analysis Edit

Objects A is equivalent to B if: Normal form
Hilbert spaces If A and B are both Hilbert spaces of infinite dimension, then A and B are isometrically isomorphic.   sequence spaces (up to exchanging the index set I with another index set of the same cardinality)
Commutative C*-algebras with unit A and B are isomorphic as C*-algebras The algebra   of continuous functions on a compact Hausdorff space, up to homeomorphism of the base space.

Classical logic Edit

Set theory Edit

Game theory Edit

Proof theory Edit

Rewriting systems Edit

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 an abstract 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.

Lambda calculus Edit

  • A lambda term is in beta normal form if no beta reduction is possible; lambda calculus is a particular case of an abstract rewriting system. In the untyped lambda calculus, for example, the term   does not have a normal form. In the typed lambda calculus, every well-formed term can be rewritten to its normal form.

Graph theory Edit

In graph theory, a branch of mathematics, graph canonization is the problem of finding a canonical form of a given graph G. A canonical form is a labeled graph Canon(G) that is isomorphic to G, such that every graph that is isomorphic to G has the same canonical form as G. Thus, from a solution to the graph canonization problem, one could also solve the problem of graph isomorphism: to test whether two graphs G and H are isomorphic, compute their canonical forms Canon(G) and Canon(H), and test whether these two canonical forms are identical.

Computing Edit

In computing, the reduction of data to any kind of canonical form is commonly called data normalization.

For instance, database normalization is the process of organizing the fields and tables of a relational database to minimize redundancy and dependency.[13]

In the field of software security, a common vulnerability is unchecked malicious input (see Code injection). The mitigation for this problem is proper input 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 common character set.

Other forms of data, typically associated with signal processing (including audio and imaging) or machine learning, can be normalized in order to provide a limited range of values.

In content management, the concept of a single source of truth (SSOT) is applicable, just as it is in database normalization generally and in software development. Competent content management systems provide logical ways of obtaining it, such as transclusion.

See also Edit

Notes Edit

  1. ^ In some occasions, the term "canonical" and "normal" can also be used interchangeably, as in Jordan canonical form and Jordan normal form (see Jordan normal form on MathWorks).
  2. ^ The term 'canonization' is sometimes incorrectly used for this.
  3. ^ "Letter from James Logan to William Jones, Correspondence of Scientific Men of the Seventeenth Century". University Press. 1841.
  4. ^ "Journal für die reine und angewandte Mathematik 1846". de Gruyter.
  5. ^ Journal für die reine und angewandte Mathematik 1846. de Gruyter.
  6. ^ "The Cambridge and Dublin mathematical journal 1851". Macmillan.
  7. ^ Hesse, Otto (1865). "Vorlesungen aus der analytischen Geometrie der geraden Linie, des Punktes und des Kreises in der Ebene" (in German). Teubner.
  8. ^ "The Cambridge and Dublin mathematical journal 1854". 1854.
  9. ^ "Journal für die reine und angewandte Mathematik, 1854". de Gruyter.
  10. ^ Cayley, Arthur (1889). "The Collected Mathematical Papers". University.
  11. ^ "Big Numbers and Scientific Notation". Teaching Quantitative Literacy. Retrieved 2019-11-20.
  12. ^ Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, pp. 117–118, ISBN 0-387-94365-X
  13. ^ "Description of the database normalization basics". support.microsoft.com. Retrieved 2019-11-20.

References Edit

  • Shilov, Georgi E. (1977), Silverman, Richard A. (ed.), Linear Algebra, Dover, ISBN 0-486-63518-X.
  • Hansen, Vagn Lundsgaard (2006), Functional Analysis: Entering Hilbert Space, World Scientific Publishing, ISBN 981-256-563-9.

canonical, form, canonical, form, linguistics, lemma, morphology, canonical, form, catholic, matrimonial, marriage, catholic, church, this, article, needs, additional, citations, verification, please, help, improve, this, article, adding, citations, reliable, . For canonical form in linguistics see Lemma morphology For canonical form in Catholic matrimonial law see Marriage in the Catholic Church Canonical form This article needs additional citations for verification Please help improve this article by adding 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 template message In mathematics and computer science a canonical normal or standard form of a mathematical object is a standard way of presenting that object as a mathematical 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 a unique representation for every object while a normal form simply specifies its form without the requirement of uniqueness 1 Algorithmic anagram test using multisets as canonical forms The strings madam curie and radium came are given as C arrays Each one is converted into a canonical form by sorting Since both sorted strings literally agree the original strings were anagrams of each other The canonical form of a positive integer in decimal representation is a finite sequence of digits that does not begin with zero More generally for a class of objects on which an equivalence relation is defined a canonical form consists in the choice of a specific object in each class For example Jordan normal form is a canonical form for matrix similarity The row echelon form is a canonical form when one considers as equivalent a matrix and its left product by an invertible matrix In computer science and more specifically in computer 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 with canonicalization 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 a differential form that is defined in a natural canonical way Contents 1 Definition 2 History 3 Examples 3 1 Large number notation 3 2 Number theory 3 3 Linear algebra 3 4 Algebra 3 5 Geometry 3 6 Integrable systems 3 7 Dynamical systems 3 8 Three dimensional geometry 3 9 Functional analysis 3 10 Classical logic 3 11 Set theory 3 12 Game theory 3 13 Proof theory 3 14 Rewriting systems 3 15 Lambda calculus 3 16 Graph theory 3 17 Computing 4 See also 5 Notes 6 ReferencesDefinition EditGiven 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 c s c c s idempotence s1 R s2 if and only if c s1 c s2 decisiveness and 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 x2 x 30 than x 30 x2 although the two forms define the same polynomial By contrast the existence of Jordan canonical form for a matrix is a deep theorem History EditAccording to OED and LSJ the term canonical stems from the Ancient Greek word kanonikos kanonikos regular according to rule from kanṓn kᾰnwn 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 3 The German term kanonische Form is attested in a 1846 paper by Eisenstein 4 later the same year Richelot uses the term Normalform in a paper 5 and in 1851 Sylvester writes 6 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 7 Hermite forme canonique 8 Borchardt forme canonique 9 and Cayley canonical form 10 In 1865 the Dictionary 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 Examples EditNote 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 Large number notation Edit Standard form is used by many mathematicians and scientists to write extremely large numbers in a more concise and understandable way the most prominent of which being the scientific notation 11 Number theory Edit Canonical representation of a positive integer Canonical form of a continued fractionLinear algebra Edit Objects A is equivalent to B if Normal form NotesNormal matrices over the complex numbers A U B U displaystyle A U BU nbsp for some unitary matrix U Diagonal matrices up to reordering This is the Spectral theoremMatrices over the complex numbers A U B V displaystyle A UBV nbsp for some unitary matrices U and V Diagonal matrices with real positive entries in descending order Singular value decompositionMatrices over an algebraically closed field A P 1 B P displaystyle A P 1 BP nbsp for some invertible matrix P Jordan normal form up to reordering of blocks Matrices over an algebraically closed field A P 1 B P displaystyle A P 1 BP nbsp for some invertible matrix P Weyr canonical form up to reordering of blocks Matrices over a field A P 1 B P displaystyle A P 1 BP nbsp for some invertible matrix P Frobenius normal formMatrices over a principal ideal domain A P 1 B Q displaystyle A P 1 BQ nbsp for some invertible matrices P and Q Smith normal form The equivalence is the same as allowing invertible elementary row and column transformationsMatrices over the integers A U B displaystyle A UB nbsp for some unimodular matrix U Hermite normal formMatrices over the integers modulo n Howell normal formFinite dimensional vector spaces over a field K A and B are isomorphic as vector spaces K n displaystyle K n nbsp n a non negative integerAlgebra Edit Objects A is equivalent to B if Normal formFinitely generated R modules with R a principal ideal domain A and B are isomorphic as R modules Primary decomposition up to reordering or invariant factor decompositionGeometry Edit In analytic geometry The equation of a line Ax By C with A2 B2 1 and C 0 The equation of a circle x h 2 y k 2 r 2 displaystyle x h 2 y k 2 r 2 nbsp By contrast there are alternative forms for writing equations For example the equation of a line may be written as a linear equation in point slope and slope intercept form Convex polyhedra can be put into canonical form such that All faces are flat All edges are tangent to the unit sphere and The centroid of the polyhedron is at the origin 12 Integrable systems Edit Every differentiable manifold has a cotangent bundle That bundle can always be endowed with a certain differential form called the canonical one form This form gives the cotangent bundle the structure of a symplectic manifold and allows vector fields on the manifold to be integrated by means of the Euler Lagrange equations or by means of Hamiltonian mechanics Such systems of integrable differential equations are called integrable systems Dynamical systems Edit The study of dynamical systems overlaps with that of integrable systems there one has the idea of a normal form dynamical systems Three dimensional geometry Edit In the study of manifolds in three dimensions one has the first fundamental form the second fundamental form and the third fundamental form Functional analysis Edit Objects A is equivalent to B if Normal formHilbert spaces If A and B are both Hilbert spaces of infinite dimension then A and B are isometrically isomorphic ℓ 2 I displaystyle ell 2 I nbsp sequence spaces up to exchanging the index set I with another index set of the same cardinality Commutative C algebras with unit A and B are isomorphic as C algebras The algebra C X displaystyle C X nbsp of continuous functions on a compact Hausdorff space up to homeomorphism of the base space Classical logic Edit Main article Canonical form Boolean algebra Negation normal form Conjunctive normal form Disjunctive normal form Algebraic normal form Prenex normal form Skolem normal form Blake canonical form also known as the complete sum of prime implicants the complete sum or the disjunctive prime formSet theory Edit Cantor normal form of an ordinal numberGame theory Edit Normal form gameProof theory Edit Normal form natural deduction Rewriting systems Edit Main article Normal form abstract rewriting 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 an abstract 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 Lambda calculus Edit A lambda term is in beta normal form if no beta reduction is possible lambda calculus is a particular case of an abstract rewriting system In the untyped lambda calculus for example the term l x x x l x x x displaystyle lambda x xx lambda x xx nbsp does not have a normal form In the typed lambda calculus every well formed term can be rewritten to its normal form Graph theory Edit Main article Graph canonization In graph theory a branch of mathematics graph canonization is the problem of finding a canonical form of a given graph G A canonical form is a labeled graph Canon G that is isomorphic to G such that every graph that is isomorphic to G has the same canonical form as G Thus from a solution to the graph canonization problem one could also solve the problem of graph isomorphism to test whether two graphs G and H are isomorphic compute their canonical forms Canon G and Canon H and test whether these two canonical forms are identical Computing Edit In computing the reduction of data to any kind of canonical form is commonly called data normalization For instance database normalization is the process of organizing the fields and tables of a relational database to minimize redundancy and dependency 13 In the field of software security a common vulnerability is unchecked malicious input see Code injection The mitigation for this problem is proper input 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 common character set Other forms of data typically associated with signal processing including audio and imaging or machine learning can be normalized in order to provide a limited range of values In content management the concept of a single source of truth SSOT is applicable just as it is in database normalization generally and in software development Competent content management systems provide logical ways of obtaining it such as transclusion See also EditCanonicalization Canonical basis Canonical class Normalization disambiguation StandardizationNotes Edit In some occasions the term canonical and normal can also be used interchangeably as in Jordan canonical form and Jordan normal form see Jordan normal form on MathWorks The term canonization is sometimes incorrectly used for this Letter from James Logan to William Jones Correspondence of Scientific Men of the Seventeenth Century University Press 1841 Journal fur die reine und angewandte Mathematik 1846 de Gruyter Journal fur die reine und angewandte Mathematik 1846 de Gruyter The Cambridge and Dublin mathematical journal 1851 Macmillan Hesse Otto 1865 Vorlesungen aus der analytischen Geometrie der geraden Linie des Punktes und des Kreises in der Ebene in German Teubner The Cambridge and Dublin mathematical journal 1854 1854 Journal fur die reine und angewandte Mathematik 1854 de Gruyter Cayley Arthur 1889 The Collected Mathematical Papers University Big Numbers and Scientific Notation Teaching Quantitative Literacy Retrieved 2019 11 20 Ziegler Gunter M 1995 Lectures on Polytopes Graduate Texts in Mathematics vol 152 Springer Verlag pp 117 118 ISBN 0 387 94365 X Description of the database normalization basics support microsoft com Retrieved 2019 11 20 References EditShilov Georgi E 1977 Silverman Richard A ed Linear Algebra Dover ISBN 0 486 63518 X Hansen Vagn Lundsgaard 2006 Functional Analysis Entering Hilbert Space World Scientific Publishing ISBN 981 256 563 9 Retrieved from https en wikipedia org w index php title Canonical form amp oldid 1169557995, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.