Representation (mathematics)
Encyclopedia
In mathematics
, representation is a very general relationship that expresses similarities between objects. Roughly speaking, a collection Y of mathematical objects may be said to represent another collection X of objects, provided that the properties and relationships existing among the representing objects yi conform in some consistent way to those existing among the corresponding represented objects xi. Somewhat more formally, for a set Π of properties and relations
, a Π-representation of some structure X is a structure Y that is the image of X under an isomorphism
that preserves Π. The label representation is sometimes also applied to the isomorphism itself.
called representation theory
, which studies the representing of elements of algebraic structures by linear transformations of vector spaces.
is the exploration of isomorphisms between graphs
and other structures.
A key class of such problems stems from the fact that, like adjacency in undirected graphs, intersection of sets
(or, more precisely, non-disjointness) is a symmetric relation
.
This gives rise to the study of intersection graph
s for innumerable families of sets.
One foundational result here, due to Paul Erdős
and colleagues, is that every n-vertex
graph may be represented in terms of intersection among subsets of a set of size no more than n2/4.
Representing a graph by such algebraic structures as its adjacency matrix
and Laplacian matrix
gives rise to the field of spectral graph theory
.
is the fact that every partially ordered set
is isomorphic to a collection of sets ordered by the containment
(or inclusion) relation ⊆.
Among the posets that arise as the containment order
s for natural classes of objects are the Boolean lattices and the orders of dimension n
.
Many partial orders arise from (and thus can be represented by) collections of geometric
objects.
Among them are the n-ball orders.
The 1-ball orders are the interval-containment orders,
and the 2-ball orders are the so-called circle orders,
the posets representable in terms of containment among disks in the plane.
A particularly nice result in this field is the characterization of the planar graph
s as those graphs
whose vertex-edge incidence relations are circle orders.
There are also geometric representations that are not based on containment.
Indeed, one of the best studied classes among these are the interval order
s,
which represent the partial order in terms of what might be called disjoint precedence of intervals on the real line
:
each element x of the poset is represented by an interval [x1, x2] such that
for any y and z in the poset, y is below z if and only if y2 < z1.
Since each of those structures may be thought of, intuitively, as a meaning of the image Y—one of the things that Y is trying to tell us—this phenomenon is called polysemy,
a term borrowed from linguistics
.
Examples include:
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, representation is a very general relationship that expresses similarities between objects. Roughly speaking, a collection Y of mathematical objects may be said to represent another collection X of objects, provided that the properties and relationships existing among the representing objects yi conform in some consistent way to those existing among the corresponding represented objects xi. Somewhat more formally, for a set Π of properties and relations
Relation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
, a Π-representation of some structure X is a structure Y that is the image of X under an isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
that preserves Π. The label representation is sometimes also applied to the isomorphism itself.
Representation theory
Perhaps the most well-developed example of this general notion is the subfield of abstract algebraAbstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
called representation theory
Representation theory
Representation theory is a branch of mathematics that studies abstract algebraic structures by representing their elements as linear transformations of vector spaces, and studiesmodules over these abstract algebraic structures...
, which studies the representing of elements of algebraic structures by linear transformations of vector spaces.
Other examples
Although the term representation theory is well established in the algebraic sense discussed above, there are many other uses of the term representation throughout mathematics.Graph theory
An active area of graph theoryGraph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
is the exploration of isomorphisms between graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
and other structures.
A key class of such problems stems from the fact that, like adjacency in undirected graphs, intersection of sets
(or, more precisely, non-disjointness) is a symmetric relation
Symmetric relation
In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...
.
This gives rise to the study of intersection graph
Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
s for innumerable families of sets.
One foundational result here, due to Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and colleagues, is that every n-vertex
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
graph may be represented in terms of intersection among subsets of a set of size no more than n2/4.
Representing a graph by such algebraic structures as its adjacency matrix
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
and Laplacian matrix
Laplacian matrix
In the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be...
gives rise to the field of spectral graph theory
Spectral graph theory
In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix....
.
Order theory
Dual to the observation above that every graph is an intersection graphis the fact that every partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
is isomorphic to a collection of sets ordered by the containment
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
(or inclusion) relation ⊆.
Among the posets that arise as the containment order
Containment order
In the mathematical field of order theory, a containment order is the partial order that arises as the subset-containment relation on some collection of objects. In a simple way, every poset P = is a containment order...
s for natural classes of objects are the Boolean lattices and the orders of dimension n
Order dimension
In mathematics, the dimension of a partially ordered set is the smallest number of total orders the intersection of which gives rise to the partial order....
.
Many partial orders arise from (and thus can be represented by) collections of geometric
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
objects.
Among them are the n-ball orders.
The 1-ball orders are the interval-containment orders,
and the 2-ball orders are the so-called circle orders,
the posets representable in terms of containment among disks in the plane.
A particularly nice result in this field is the characterization of the planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s as those graphs
whose vertex-edge incidence relations are circle orders.
There are also geometric representations that are not based on containment.
Indeed, one of the best studied classes among these are the interval order
Interval order
In mathematics, especially order theory,the interval order for a collection of intervals on the real lineis the partial order corresponding to their left-to-right precedence relation—one interval, I1, being considered less than another, I2, if I1 is completely to the left of I2.More formally, a...
s,
which represent the partial order in terms of what might be called disjoint precedence of intervals on the real line
Real line
In mathematics, the real line, or real number line is the line whose points are the real numbers. That is, the real line is the set of all real numbers, viewed as a geometric space, namely the Euclidean space of dimension one...
:
each element x of the poset is represented by an interval [x1, x2] such that
for any y and z in the poset, y is below z if and only if y2 < z1.
Polysemy
Under certain circumstances, a single function f:X → Y is at once an isomorphism from several mathematical structures on X.Since each of those structures may be thought of, intuitively, as a meaning of the image Y—one of the things that Y is trying to tell us—this phenomenon is called polysemy,
a term borrowed from linguistics
Polysemy
Polysemy is the capacity for a sign or signs to have multiple meanings , i.e., a large semantic field.Charles Fillmore and Beryl Atkins’ definition stipulates three elements: the various senses of a polysemous word have a central origin, the links between these senses form a network, and ...
.
Examples include:
- intersection polysemy—pairs of graphs G1 and G2 on a common vertex set V that can be simultaneously represented by a single collection of sets Sv such that any distinct vertices u and w in V...
-
- are adjacent in G1 if and only if their corresponding sets intersect ( Su ∩ Sw ≠ Ø ), and
- are adjacent in G2 if and only if the complements do ( SuC ∩ SwC ≠ Ø ).
- competition polysemy—motivated by the study of ecologicalEcologyEcology is the scientific study of the relations that living organisms have with respect to each other and their natural environment. Variables of interest to ecologists include the composition, distribution, amount , number, and changing states of organisms within and among ecosystems...
food webFood webA food web depicts feeding connections in an ecological community. Ecologists can broadly lump all life forms into one of two categories called trophic levels: 1) the autotrophs, and 2) the heterotrophs...
s, in which pairs of species may have prey in common or have predators in common. A pair of graphs G1 and G2 on one vertex set is competition polysemic if and only if there exists a single directed graphDirected graphA directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
D on the same vertex set such that any distinct vertices u and v...
-
- are adjacent in G1 if and only if there is a vertex w such that both uw and vw are arcs in D, and
- are adjacent in G2 if and only if there is a vertex w such that both wu and wv are arcs in D.
- interval polysemy—pairs of posets P1 and P2 on a common ground set that can be simultaneously represented by a single collection of real intervals that is an interval-order representation of P1 and an interval-containment representation of P2.