
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 which 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.
The canonical form of a
positive integer
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...
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
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each 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
In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating mathematical expressions ...
, 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). 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
In mathematics, differential forms provide a unified approach to define integrands over curves, surfaces, solids, and higher-dimensional manifolds. The modern notion of differential forms was pioneered by Élie Cartan. It has many applications, ...
that is defined in a natural (canonical) way.
Definition
Given a set ''S'' of objects with an
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each 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'', ''s''
1, ''s''
2 ∈ ''S'':
#''c''(''s'') = ''c''(''c''(''s'')) (
idempotence),
#''s''
1 ''R'' ''s''
2 if and only if ''c''(''s''
1) = ''c''(''s''
2) (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 ''x''
2 + ''x'' + 30 than ''x'' + 30 + ''x''
2, although the two forms define the same polynomial. By contrast, the existence of
Jordan canonical form for a matrix is a deep theorem.
History
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
Logan may refer to:
Places
* Mount Logan (disambiguation)
Australia
* Logan (Queensland electoral district), an electoral district in the Queensland Legislative Assembly
* Logan, Victoria, small locality near St. Arnaud
* Logan City, local gover ...
. 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
Sylvester or Silvester is a name derived from the Latin adjective ''silvestris'' meaning "wooded" or "wild", which derives from the noun ''silva'' meaning "woodland". Classical Latin spells this with ''i''. In Classical Latin, ''y'' represented a ...
writes:
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:
Examples
Note: in this section, "
up to Two Mathematical object, mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R''
* if ''a'' and ''b'' are related by ''R'', that is,
* if ''aRb'' holds, that is,
* if the equivalence classes of ''a'' and ''b'' wi ...
" 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
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.
Number theory
*
Canonical representation of a positive integer
*Canonical form of a
continued fraction
Linear algebra
Algebra
Geometry
In
analytic geometry
In classical mathematics, analytic geometry, also known as coordinate geometry or Cartesian geometry, is the study of geometry using a coordinate system. This contrasts with synthetic geometry.
Analytic geometry is used in physics and engineerin ...
:
*The equation of a line: ''Ax'' + ''By'' = ''C'', with ''A
2'' + ''B''
2 = 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 mathematics, a linear equation is an equation that may be put in the form
a_1x_1+\ldots+a_nx_n+b=0, where x_1,\ldots,x_n are the variables (or unknowns), and b,a_1,\ldots,a_n are the coefficients, which are often real numbers. The coefficien ...
in
point-slope and
slope-intercept form.
Convex polyhedra
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
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.
Integrable systems
Every differentiable
manifold
In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a n ...
has a
cotangent bundle
In mathematics, especially differential geometry, the cotangent bundle of a smooth manifold is the vector bundle of all the cotangent spaces at every point in the manifold. It may be described also as the dual bundle to the tangent bundle. This may ...
. That bundle can always be endowed with a certain
differential form
In mathematics, differential forms provide a unified approach to define integrands over curves, surfaces, solids, and higher-dimensional manifolds. The modern notion of differential forms was pioneered by Élie Cartan. It has many applications, ...
, called the
canonical one-form. This form gives the cotangent bundle the structure of a
symplectic manifold
In differential geometry, a subject of mathematics, a symplectic manifold is a smooth manifold, M , equipped with a closed nondegenerate differential 2-form \omega , called the symplectic form. The study of symplectic manifolds is called sympl ...
, 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
The study of
dynamical systems
In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a p ...
overlaps with that of
integrable systems; there one has the idea of a
normal form (dynamical systems).
Three dimensional geometry
In the study of manifolds in three dimensions, one has the
first fundamental form, the
second fundamental form and the
third fundamental form
In differential geometry, the third fundamental form is a surface metric denoted by \mathrm. Unlike the second fundamental form, it is independent of the surface normal.
Definition
Let be the shape operator and be a smooth surface. Also, let ...
.
Functional analysis
Classical logic
*
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 form
Set theory
*
Cantor normal form of an
ordinal number
In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets.
A finite set can be enumerated by successively labeling each element with the least n ...
Game theory
*
Normal form game
Proof theory
*
Normal form (natural deduction)
Rewriting systems
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
*A lambda term is in
beta normal form if no beta reduction is possible;
lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation ...
is a particular case of an abstract rewriting system. In the untyped lambda calculus, for example, the term
doesn't have a normal form. In the typed lambda calculus, every well-formed term can be rewritten to its normal form.
Graph theory
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
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
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
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
A relational database is a (most commonly digital) database based on the relational model of data, as proposed by E. F. Codd in 1970. A system used to maintain relational databases is a relational database management system (RDBMS). Many relatio ...
to minimize
redundancy and dependency.
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
Software development is the process of conceiving, specifying, designing, programming, documenting, testing, and bug fixing involved in creating and maintaining applications, frameworks, or other software components. Software development invol ...
. Competent
content management system
A content management system (CMS) is computer software used to manage the creation and modification of digital content (content management).''Managing Enterprise Content: A Unified Content Strategy''. Ann Rockley, Pamela Kostur, Steve Manning. New ...
s provide logical ways of obtaining it, such as
transclusion.
See also
*
Canonicalization
*
Canonical basis
*
Canonical class
*
Normalization (disambiguation)
Normalization or normalisation refers to a process that makes something more normal or regular. Most commonly it refers to:
* Normalization (sociology) or social normalization, the process through which ideas and behaviors that may fall outside o ...
*
Standardization
Standardization or standardisation is the process of implementing and developing technical standards based on the consensus of different parties that include firms, users, interest groups, standards organizations and governments. Standardization ...
Notes
References
*.
*{{citation , last=Hansen , first=Vagn Lundsgaard , title = Functional Analysis: Entering Hilbert Space , date=2006 , publisher=World Scientific Publishing , isbn=981-256-563-9.
Algebra
Concepts in logic
Mathematical terminology
Formalism (deductive)