Graph automorphism

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.
Formally, an automorphism of a graph "G" = ("V","E") is a permutation σ of the vertex set "V", such that the pair of vertices ("u","v") form an edge if and only if the pair (σ("u"),σ("v")) also form an edge. That is, it is a graph isomorphism from "G" to itself. Automorphisms may be defined in this way both for directed graphs and for undirected graphs.
The composition of two automorphisms is another automorphism, and the set of automorphisms of a given graph, under the composition operation, forms a group, the automorphism group of the graph. In the opposite direction, by Frucht's theorem, all groups can be represented as the automorphism group of a connected graph – indeed, of a cubic graph.
Computational complexity.
Constructing the automorphism group is at least as difficult (in terms of its computational complexity) as solving the graph isomorphism problem, determining whether two given graphs correspond vertex-for-vertex and edge-for-edge. For, "G" and "H" are isomorphic if and only if the disconnected graph formed by the disjoint union of graphs "G" and "H" has an automorphism that swaps the two components. In fact, just counting the automorphisms is polynomial-time equivalent to graph isomorphism.
The graph automorphism problem is the problem of testing whether a graph has a nontrivial automorphism. It belongs to the class NP of computational complexity. Similar to the graph isomorphism problem, it is unknown whether it has a polynomial time algorithm or it is NP-complete.
There is a polynomial time algorithm for solving the graph automorphism problem for graphs where vertex degrees are bounded by a constant.
The graph automorphism problem is polynomial-time many-one reducible to the graph isomorphism problem, but the converse reduction is unknown. By contrast, hardness is known when the automorphisms are constrained in a certain fashion; for instance, determining the existence of a fixed-point-free automorphism (an automorphism that fixes no vertex) is NP-complete, and the problem of counting such automorphisms is ♯P-complete.
Algorithms, software and applications.
While no "worst-case" polynomial-time algorithms are known for the general Graph Automorphism problem, finding the automorphism group (and printing out an irredundant set of generators) for many large graphs arising in applications is rather easy. Several open-source software tools are available for this task, including NAUTY, BLISS and SAUCY. SAUCY and BLISS are particularly efficient for sparse graphs, e.g., SAUCY processes some graphs with millions of vertices in mere seconds. However, BLISS and NAUTY can also produce Canonical Labeling, whereas SAUCY is currently optimized for solving Graph Automorphism. An important observation is that for a graph on "n" vertices, the automorphism group can be specified by no more than "n-1" generators, and the above software packages are guaranteed to satisfy this bound as a side-effect of their algorithms (minimal sets of generators are harder to find and are not particularly useful in practice). It also appears that the total support (i.e., the number of vertices moved) of all generators is limited by a linear function of "n", which is important in runtime analysis of these algorithms. However, this has not been established for a fact, as of March 2012.
Practical applications of Graph Automorphism include graph drawing and other visualization tasks, solving structured instances of Boolean Satisfiability arising in the context of Formal verification and Logistics. Molecular symmetry can predict or explain chemical properties.
Symmetry display.
Several graph drawing researchers have investigated algorithms for drawing graphs in such a way that the automorphisms of the graph become visible as symmetries of the drawing. This may be done either by using a method that is not designed around symmetries, but that automatically generates symmetric drawings when possible, or by explicitly identifying symmetries and using them to guide vertex placement in the drawing. It is not always possible to display all symmetries of the graph simultaneously, so it may be necessary to choose which symmetries to display and which to leave unvisualized.
Graph families defined by their automorphisms.
Several families of graphs are defined by having certain types of automorphisms:
Inclusion relationships between these families are indicated by the following table:


Associative bialgebroid

In mathematics, if formula_1 is an associative algebra over some ground field "k", then a left associative formula_1-bialgebroid is another associative "k"-algebra formula_3 together with the following additional maps:
an algebra map formula_4 called the source map,
an algebra map formula_5 called the target map, so that the elements of the images of formula_6 and formula_7 commute in formula_3, therefore inducing an formula_1-bimodule structure on formula_3 via the rule formula_11 for formula_12; an formula_1-bimodule morphism formula_14 which is required to be a counital coassociative comultiplication on formula_3 in the monoidal category of formula_1-bimodules with monoidal product formula_17. The corresponding counit formula_18 is required to be a left character (equivalently, the map formula_19 must be a left action extending the multiplication formula_20 along formula_21). Furthermore, a compatibility between the comultiplication formula_22 and multiplications on formula_3 and on formula_24 is required. For a noncommutative formula_1, the tensor square formula_26 is not an algebra, hence asking for a bialgebra-like compatibility that formula_14 is a morphism of "k"-algebras does not make sense. Instead, one requires that formula_26 has a "k"-subspace formula_29 which contains the image of formula_22 and has a well-defined multiplication induced from its preimage under the projection from the usual tensor square algebra formula_24. Then one requires that the corestriction formula_32 is a homomorphism of unital algebras. If it is a homomorphism for one such formula_29, one can make a canonical choice for formula_29, namely the so called Takeuchi's product formula_35, which always inherits an associative multiplication via the projection from formula_24. Thus, it is sufficient to check if the image of formula_22 is contained in the Takeuchi's product rather than to look for other formula_29. As shown by Brzeziński and Militaru, the notion of a bialgebroid is equivalent to the notion of formula_39-algebra introduced by Takeuchi earlier, in 1977.
Associative bialgebroid is a generalization of a notion of "k"-bialgebra where a commutative ground ring "k" is replaced by a possibly noncommutative "k"-algebra formula_1. Hopf algebroids are associative bialgebroids with an additional antipode map which is an antiautomorphism of formula_3 satisfying additional axioms.
The term bialgebroid for this notion has been first proposed by J-H. Lu. The modifier associative is often dropped from the name, and retained mainly only when we want to distinguish it from the notion of a Lie bialgebroid, often also referred just as a bialgebroid. Associative bialgebroids come in two chiral versions, left and right. A dual notion is the notion of a bicoalgebroid.
There is a generalization, an internal bialgebroid which abstracts the structure of an associative bialgebroid to the setup where the category of vector spaces is replaced by an abstract symmetric monoidal category admitting coequalizers commuting with the tensor product.


Fixed-point subring

In algebra, the fixed-point subring formula_1 of an automorphism "f" of a ring "R" is the subring of the fixed points of "f":
More generally, if "G" is a group acting on "R", then the subring of "R":
is called the fixed subring or, more traditionally, the ring of invariants. In Galois theory, when "R" is a field and "G" is a group of field automorphisms, the fixed ring is a subfield called the fixed field of the automorphism group; see Fundamental theorem of Galois theory.
Along with a module of covariants, the ring of invariants is a central object of study in invariant theory. Geometrically, the rings of invariants are the coordinate rings of (affine or projective) GIT quotients and they play fundamental roles in the constructions in geometric invariant theory.
Example: Let formula_4 be a polynomial ring in "n" variables. The symmetric group "S""n" acts on "R" by permuting the variables. Then the ring of invariants "R""G" is the ring of symmetric polynomials. If a reductive algebraic group "G" acts on "R", then the fundamental theorem of invariant theory describes the generators of "R""G".
Hilbert's fourteenth problem asks whether the ring of invariants is finitely generated or not (the answer is affirmative if "G" is a reductive algebraic group by Nagata's theorem.) The finite generation is easily seen for a finite group "G" acting on a finitely generated algebra "R": since "R" is integral over "R""G", the Artin–Tate lemma implies "R""G" is a finitely generated algebra. The answer is negative for some unipotent groups.
Let "G" be a finite group. Let "S" be the symmetric algebra of a finite-dimensional "G"-module. Then "G" is a reflection group if and only if formula_5 is a free module (of finite rank) over "S""G" (Chevalley's theorem).
In differential geometry, if "G" is a Lie group and formula_6 its Lie algebra, then each principal "G"-bundle on a manifold "M" determines a graded algebra homomorphism (called the Chern–Weil homomorphism)
where formula_8 is the ring of polynomial functions on formula_9 and "G" acts on formula_8 by adjoint representation.


Normal scheme

In algebraic geometry, an algebraic variety or scheme "X" is normal if it is normal at every point, meaning that the local ring at the point is an integrally closed domain. An affine variety "X" (understood to be irreducible) is normal if and only if the ring "O"("X") of regular functions on "X" is an integrally closed domain. A variety "X" over a field is normal if and only if every finite birational morphism from any variety "Y" to "X" is an isomorphism.
Normal varieties were introduced by .
Geometric and algebraic interpretations of normality.
A morphism of varieties is finite if the inverse image of every point is finite and the morphism is proper. A morphism of varieties
is birational if it restricts to an isomorphism between dense open subsets. So, for example, the cuspidal cubic curve "X" in the affine plane "A"2 defined by "x"2 = "y"3 is not normal, because there is a finite birational morphism "A"1 → "X"
(namely, "t" maps to ("t"3, "t"2)) which is not an isomorphism. By contrast, the affine line "A"1 is normal: it cannot be simplified any further by finite birational morphisms.
A normal complex variety "X" has the property, when viewed as a stratified space using the classical topology, that every link is connected. Equivalently, every complex point "x" has arbitrarily small neighborhoods "U" such that "U" minus
the singular set of "X" is connected. For example, it follows that the nodal cubic curve "X" in the figure, defined by "x"2 = "y"2("y" + 1), is not normal. This also follows from the definition of normality, since there is a finite birational morphism from "A"1 to "X" which is not an isomorphism; it sends two points of "A"1 to the same point in "X".
More generally, a scheme "X" is normal if each of its local rings
is an integrally closed domain. That is, each of these rings is an integral domain "R", and every ring "S" with "R" ⊆ "S" ⊆ Frac("R") such that "S" is finitely generated as an "R"-module is equal to "R". (Here Frac("R") denotes the field of fractions of "R".) This is a direct translation, in terms of local rings, of the geometric condition that every finite birational morphism to "X" is an isomorphism.
An older notion is that a subvariety "X" of projective space is linearly normal if the linear system giving the embedding is complete. Equivalently, "X" ⊆ Pn is not the linear projection of an embedding "X" ⊆ Pn+1 (unless "X" is contained
in a hyperplane Pn). This is the meaning of "normal" in the phrases rational normal curve and rational normal scroll.
Every regular scheme is normal. Conversely, showed that every normal variety is regular outside a subset of codimension at least 2, and a similar result is true for schemes. So, for example, every normal curve is regular.
The normalization.
Any reduced scheme "X" has a unique normalization: a normal scheme "Y" with an integral birational morphism "Y" → "X". (For "X" a variety over a field, the morphism "Y" → "X" is finite, which is stronger than "integral".) The normalization of a scheme of dimension 1 is regular, and the normalization of a scheme of dimension 2 has only isolated singularities. Normalization is not usually used for resolution of singularities for schemes of higher dimension.
To define the normalization, first suppose that "X" is an irreducible reduced scheme "X". Every affine open subset of "X" has the form Spec "R" with "R" an integral domain. Write "X" as a union of affine open subsets Spec "A"i. Let "B"i be the integral closure of "A"i in its fraction field. Then the normalization of "X" is defined by gluing together the affine schemes
Spec "B"i.
Examples.
If the initial scheme is not irreducible, the normalization is defined to be the disjoint union of the normalizations of the irreducible components.
Normalization of a cusp.
Consider the affine curveformula_1with the cusp singularity at the origin. Its normalization can be given by the mapformula_2induced from the algebra mapformula_3
Normalization of axes in affine plane.
For example,formula_4is not an irreducible scheme since it has two components. Its normalization is given by the scheme morphismformula_5induced from the two quotient mapsformula_6
formula_7
Normalization of reducible projective variety.
Similarly, for homogeneous irreducible polynomials formula_8 in a UFD, the normalization offormula_9is given by the morphismformula_10


Real form (Lie theory)

In mathematics, the notion of a real form relates objects defined over the field of real and complex numbers. A real Lie algebra "g"0 is called a real form of a complex Lie algebra "g" if "g" is the complexification of "g"0:
The notion of a real form can also be defined for complex Lie groups. Real forms of complex semisimple Lie groups and Lie algebras have been completely classified by Élie Cartan.
Real forms for Lie groups and algebraic groups.
Using the Lie correspondence between Lie groups and Lie algebras, the notion of a real form can be defined for Lie groups. In the case of linear algebraic groups, the notions of complexification and real form have a natural description in the language of algebraic geometry.
Classification.
Just as complex semisimple Lie algebras are classified by Dynkin diagrams, the real forms of a semisimple Lie algebra are classified by Satake diagrams, which are obtained from the Dynkin diagram of the complex form by labeling some vertices black (filled), and connecting some other vertices in pairs by arrows, according to certain rules.
It is a basic fact in the structure theory of complex semisimple Lie algebras that every such algebra has two special real forms: one is the compact real form and corresponds to a compact Lie group under the Lie correspondence (its Satake diagram has all vertices blackened), and the other is the split real form and corresponds to a Lie group that is as far as possible from being compact (its Satake diagram has no vertices blackened and no arrows). In the case of the complex special linear group "SL"("n",C), the compact real form is the special unitary group "SU"("n") and the split real form is the real special linear group "SL"("n",R). The classification of real forms of semisimple Lie algebras was accomplished by Élie Cartan in the context of Riemannian symmetric spaces. In general, there may be more than two real forms.
Suppose that "g"0 is a semisimple Lie algebra over the field of real numbers. By Cartan's criterion, the Killing form is nondegenerate, and can be diagonalized in a suitable basis with the diagonal entries +1 or −1. By Sylvester's law of inertia, the number of positive entries, or the positive index of inertia, is an invariant of the bilinear form, i.e. it does not depend on the choice of the diagonalizing basis. This is a number between 0 and the dimension of "g" which is an important invariant of the real Lie algebra, called its index.
Split real form.
A real form "g"0 of a finite-dimensional complex semisimple Lie algebra "g" is said to be split, or normal, if in each Cartan decomposition "g"0 = "k"0 ⊕ "p"0, the space "p"0 contains a maximal abelian subalgebra of "g"0, i.e. its Cartan subalgebra. Élie Cartan proved that every complex semisimple Lie algebra "g" has a split real form, which is unique up to isomorphism. It has maximal index among all real forms.
The split form corresponds to the Satake diagram with no vertices blackened and no arrows.
Compact real form.
A real Lie algebra "g"0 is called compact if the Killing form is negative definite, i.e. the index of "g"0 is zero. In this case "g"0 = "k"0 is a compact Lie algebra. It is known that under the Lie correspondence, compact Lie algebras correspond to compact Lie groups.
The compact form corresponds to the Satake diagram with all vertices blackened.
Construction of the compact real form.
In general, the construction of the compact real form uses structure theory of semisimple Lie algebras. For classical Lie algebras there is a more explicit construction.
Let "g"0 be a real Lie algebra of matrices over R that is closed under the transpose map,
Then "g"0 decomposes into the direct sum of its skew-symmetric part "k"0 and its symmetric part "p"0, this is the Cartan decomposition:
The complexification "g" of "g"0 decomposes into the direct sum of "g"0 and "ig"0. The real vector space of matrices
is a subspace of the complex Lie algebra "g" that is closed under the commutators and consists of skew-hermitian matrices. It follows that "u"0 is a real Lie subalgebra of "g", that its Killing form is negative definite (making it a compact Lie algebra), and that the complexification of "u"0 is "g". Therefore, "u"0 is a compact form of "g".


Representation of a Lie group

In mathematics and theoretical physics, a representation of a Lie group is a linear action of a Lie group on a vector space. Equivalently, a representation is a smooth homomorphism of the group into the group of invertible operators on the vector space. Representations play an important role in the study of continuous symmetry. A great deal is known about such representations, a basic tool in their study being the use of the corresponding 'infinitesimal' representations of Lie algebras.
Finite-dimensional representations.
Representations.
A complex representation of a group is an action by a group on a finite-dimensional vector space over the field formula_1. A representation of the Lie group "G", acting on an "n"-dimensional vector space "V" over formula_1 is then a smooth group homomorphism
where formula_4 is the general linear group of all invertible linear transformations of formula_5 under their composition. Since all "n"-dimensional spaces are isomorphic, the group formula_4 can be identified with the group of the invertible, complex generally Smoothness of the map formula_7 can be regarded as a technicality, in that any continuous homomorphism will automatically be smooth.
We can alternatively describe a representation of a Lie group formula_8 as a "linear action" of formula_8 on a vector space formula_5. Notationally, we would then write formula_11 in place of formula_12 for the way a group element formula_13 acts on the vector formula_14.
A typical example in which representations arise in physics would be the study of a linear partial differential equation having symmetry group formula_8. Although the individual solutions of the equation may not be invariant under the action of formula_8, the "space" formula_5 of all solutions is invariant under the action of formula_8. Thus, formula_5 constitutes a representation of formula_8. See the example of SO(3), discussed below.
Basic definitions.
If the homomorphism formula_7 is injective (i.e., a monomorphism), the representation is said to be faithful.
If a basis for the complex vector space "V" is chosen, the representation can be expressed as a homomorphism into general linear group formula_22. This is known as a "matrix representation". Two representations of "G" on vector spaces "V", "W" are "equivalent" if they have the same matrix representations with respect to some choices of bases
for "V" and "W".
Given a representation formula_3, we say that a subspace "W" of "V" is an invariant subspace if formula_24 for all formula_13 and formula_26. The representation is said to be irreducible if the only invariant subspaces of "V" are the zero space and "V" itself. For certain types of Lie groups, namely compact and semisimple groups, every finite-dimensional representation decomposes as a direct sum of irreducible representations, a property known as complete reducibility. For such groups, a typical goal of representation theory is to classify all finite-dimensional irreducible representations of the given group, up to isomorphism. (See the Classification section below.)
A unitary representation on a finite-dimensional inner product space is defined in the same way, except that formula_7 is required to map into the group of unitary operators. If "G" is a compact Lie group, every finite-dimensional representation is equivalent to a unitary one.
Lie algebra representations.
Each representation of a Lie group "G" gives rise to a representation of its Lie algebra; this correspondence is discussed in detail in subsequent sections. See representation of Lie algebras for the Lie algebra theory.
An example: The rotation group SO(3).
In quantum mechanics, the time-independent Schrödinger equation, formula_28 plays an important role. In the three-dimensional case, if formula_29 has rotational symmetry, then the space formula_30 of solutions to formula_28 will be invariant under the action of SO(3). Thus, formula_30 will—for each fixed value of formula_33—constitute a representation of SO(3), which is typically finite dimensional. In trying to solve formula_28, it helps to know what all possible finite-dimensional representations of SO(3) look like. The representation theory of SO(3) plays a key role, for example, in the mathematical analysis of the hydrogen atom.
Every standard textbook on quantum mechanics contains an analysis which essentially classifies finite-dimensional irreducible representations of SO(3), by means of its Lie algebra. (The commutation relations among the angular momentum operators are just the relations for the Lie algebra formula_35 of SO(3).) One subtlety of this analysis is that the representations of the group and the Lie algebra are not in one-to-one correspondence, a point that is critical in understanding the distinction between integer spin and half-integer spin.
Ordinary representations.
The rotation group SO(3) is a compact Lie group and thus every finite-dimensional representation of SO(3) decomposes as a direct sum of irreducible representations. The group SO(3) has one irreducible representation in each odd dimension. For each non-negative integer formula_36, the irreducible representation of dimension formula_37 can be realized as the space formula_38 of homogeneous harmonic polynomials on formula_39 of degree formula_36. Here, SO(3) acts on formula_38 in the usual way that rotations act on functions on formula_39:
The restriction to the unit sphere formula_44 of the elements of formula_38 are the spherical harmonics of degree formula_36.
If, say, formula_47, then all polynomials that are homogeneous of degree one are harmonic, and we obtain a three-dimensional space formula_48 spanned by the linear polynomials formula_49, formula_50, and formula_51. If formula_52, the space formula_53 is spanned by the polynomials formula_54, formula_55, formula_56, formula_57, and formula_58.
As noted above, the finite-dimensional representations of SO(3) arise naturally when studying the time-independent Schrödinger equation for a radial potential, such as the hydrogen atom, as a reflection of the rotational symmetry of the problem. (See the role played by the spherical harmonics in the mathematical analysis of hydrogen.)
Projective representations.
If we look at the Lie algebra formula_35 of SO(3), this Lie algebra is isomorphic to the Lie algebra formula_60 of SU(2). By the representation theory of formula_60, there is then one irreducible representation of formula_35 in "every" dimension. The even-dimensional representations, however, do not correspond to representations of the "group" SO(3). These so-called "fractional spin" representations do, however, correspond to "projective" representations of SO(3). These representations arise in the quantum mechanics of particles with fractional spin, such as an electron.
Operations on representations.
In this section, we describe three basic operations on representations. See also the corresponding constructions for representations of a Lie algebra.
Direct sums.
If we have two representations of a group formula_8, formula_64 and formula_65, then the direct sum would have formula_66 as the underlying vector space, with the action of the group given by
for all formula_68 formula_69, and formula_13.
Certain types of Lie groups—notably, compact Lie groups—have the property that "every" finite-dimensional representation is isomorphic to a direct sum of irreducible representations. In such cases, the classification of representations reduces to the classification of irreducible representations. See Weyl's theorem on complete reducibility.
Tensor products of representations.
If we have two representations of a group formula_8, formula_64 and formula_65, then the tensor product of the representations would have the tensor product vector space formula_74 as the underlying vector space, with the action of formula_8 uniquely determined by the assumption that
for all formula_77 and formula_69. That is to say, formula_79.
The Lie algebra representation formula_80 associated to the tensor product representation formula_7 is given by the formula:
The tensor product of two irreducible representations is usually not irreducible; a basic problem in representation theory is then to decompose tensor products of irreducible representations as a direct sum of irreducible subspaces. This problem goes under the name of "addition of angular momentum" or "Clebsch–Gordan theory" in the physics literature.
Dual representations.
Let formula_8 be a Lie group and formula_84 be a representation of G. Let formula_85 be the dual space, that is, the space of linear functionals on formula_5. Then we can define a representation formula_87 by the formula
where for any operator formula_89, the transpose operator formula_90 is defined as the "composition with formula_91" operator:
(If we work in a basis, then formula_93 is just the usual matrix transpose of formula_91.) The inverse in the definition of formula_95 is needed to ensure that formula_95 is actually a representation of formula_8, in light of the identity formula_98.
The dual of an irreducible representation is always irreducible, but may or may not be isomorphic to the original representation. In the case of the group SU(3), for example, the irreducible representations are labeled by a pair formula_99 of non-negative integers. The dual of the representation associated to formula_99 is the representation associated to formula_101.
Lie group versus Lie algebra representations.
Overview.
In many cases, it is convenient to study representations of a Lie group by studying representations of the associated Lie algebra. In general, however, not every representation of the Lie algebra comes from a representation of the group. This fact is, for example, lying behind the distinction between integer spin and half-integer spin in quantum mechanics. On the other hand, if "G" is a simply connected group, then a theorem says that we do, in fact, get a one-to-one correspondence between the group and Lie algebra representations.
Let be a Lie group with Lie algebra formula_102, and assume that a representation formula_80 of formula_102 is at hand. The Lie correspondence may be employed for obtaining group representations of the connected component of the . Roughly speaking, this is effected by taking the matrix exponential of the matrices of the Lie algebra representation. A subtlety arises if is not simply connected. This may result in projective representations or, in physics parlance, multi-valued representations of . These are actually representations of the universal covering group of .
These results will be explained more fully below.
The Lie correspondence gives results only for the connected component of the groups, and thus the other components of the full group are treated separately by giving representatives for matrices representing these components, one for each component. These form (representatives of) the zeroth homotopy group of . For example, in the case of the four-component Lorentz group, representatives of space inversion and time reversal must be put in by hand. Further illustrations will be drawn from the representation theory of the Lorentz group below.
The exponential mapping.
If formula_8 is a Lie group with Lie algebra formula_102, then we have the exponential map from formula_102 to formula_8, written as
If formula_8 is a matrix Lie group, the expression formula_111 can be computed by the usual power series for the exponential. In any Lie group, there exist neighborhoods formula_112 of the identity in formula_8 and formula_5 of the origin in formula_102 with the property that every formula_116 in formula_112 can be written uniquely as formula_118 with formula_119. That is, the exponential map has a "local" inverse. In most groups, this is only local; that is, the exponential map is typically neither one-to-one nor onto.
Lie algebra representations from group representations.
It is always possible to pass from a representation of a Lie group to a representation of its Lie algebra formula_120 If is a group representation for some vector space , then its pushforward (differential) at the identity, or Lie map, formula_121 is a Lie algebra representation. It is explicitly computed using
A basic property relating formula_7 and formula_80 involves the exponential map:
The question we wish to investigate is whether every representation of formula_102 arises in this way from representations of the group formula_8. As we shall see, this is the case when formula_8 is simply connected.
Group representations from Lie algebra representations.
The main result of this section is the following:
From this we easily deduce the following:
A projective representation is one in which each formula_143 is defined only up to multiplication by a constant. In quantum physics, it is natural to allow projective representations in addition to ordinary ones, because states are really defined only up to a constant. (That is to say, if formula_144 is a vector in the quantum Hilbert space, then formula_145 represents the same physical state for any constant formula_146.) Every "finite-dimensional" projective representation of a connected Lie group formula_8 comes from an ordinary representation of the universal cover formula_138 of formula_8. Conversely, as we will discuss below, every irreducible ordinary representation of formula_138 descends to a projective representation of formula_8. In the physics literature, projective representations are often described as multi-valued representations (i.e., each formula_152 does not have a single value but a whole family of values). This phenomenon is important to the study of fractional spin in quantum mechanics.
We now outline the proof of the main results above. Suppose formula_153 is a representation of formula_102 on a vector space . If there is going to be an associated Lie group representation formula_7, it must satisfy the exponential relation of the previous subsection. Now, in light of the local invertibility of the exponential, we can "define" a map formula_7 from a neighborhood formula_112 of the identity in formula_8 by this relation:
A key question is then this: Is this locally defined map a "local homomorphism"? (This question would apply even in the special case where the exponential mapping is globally one-to-one and onto; in that case, formula_7 would be a globally defined map, but it is not obvious why formula_7 would be a homomorphism.) The answer to this question is yes: formula_7 is a local homomorphism, and this can be established using the Baker–Campbell–Hausdorff formula.
If formula_8 is connected, then every element of formula_8 is at least a "product" of exponentials of elements of formula_102. Thus, we can tentatively define formula_7 globally as follows.
Note, however, that the representation of a given group element as a product of exponentials is very far from unique, so it is very far from clear that formula_7 is actually well defined.
To address the question of whether formula_7 is well defined, we connect each group element formula_13 to the identity using a continuous path. It is then possible to define formula_7 along the path, and to show that the value of formula_152 is unchanged under continuous deformation of the path with endpoints fixed. If formula_8 is simply connected, any path starting at the identity and ending at formula_116 can be continuously deformed into any other such path, showing that formula_152 is fully independent of the choice of path. Given that the initial definition of formula_7 near the identity was a local homomorphism, it is not difficult to show that the globally defined map is also a homomorphism satisfying .
If formula_8 is not simply connected, we may apply the above procedure to the universal cover formula_138 of formula_8. Let formula_179 be the covering map. If it should happen that the kernel of formula_180 contains the kernel of formula_181, then formula_7 descends to a representation of the original group formula_8. Even if this is not the case, note that the kernel of formula_181 is a discrete normal subgroup of formula_138, which is therefore in the center of formula_138. Thus, if formula_80 is irreducible, Schur's lemma implies that the kernel of formula_181 will act by scalar multiples of the identity. Thus, formula_7 descends to a "projective" representation of formula_8, that is, one that is defined only modulo scalar multiples of the identity.
A pictorial view of how the universal covering group contains "all" such homotopy classes, and a technical definition of it (as a set and as a group) is given in geometric view.
For example, when this is specialized to the doubly connected , the universal covering group is formula_191, and whether its corresponding representation is faithful decides whether is projective.
Classification in the compact case.
If "G" is a connected compact Lie group, its finite-dimensional representations can be decomposed as direct sums of irreducible representations. The irreducibles are classified by a "theorem of the highest weight." We give a brief description of this theory here; for more details, see the articles on representation theory of a connected compact Lie group and the parallel theory classifying representations of semisimple Lie algebras.
Let "T" be a maximal torus in "G". By Schur's lemma, the irreducible representations of "T" are one dimensional. These representations can be classified easily and are labeled by certain "analytically integral elements" or "weights." If formula_192 is an irreducible representation of "G", the restriction of formula_192 to "T" will usually not be irreducible, but it will decompose as a direct sum of irreducible representations of "T", labeled by the associated weights. (The same weight can occur more than once.) For a fixed formula_192, one can identify one of the weights as "highest" and the representations are then classified by this highest weight.
An important aspect of the representation theory is the associated theory of characters. Here, for a representation formula_192 of "G", the character is the function
given by
Two representations with the same character turn out to be isomorphic. Furthermore, the Weyl character formula gives a remarkable formula for the character of a representation in terms of its highest weight. Not only does this formula gives a lot of useful information about the representation, but it plays a crucial role in the proof of the theorem of the highest weight.
Unitary representations on Hilbert spaces.
Let "V" be a complex Hilbert space, which may be infinite dimensional, and let formula_198 denote the group of unitary operators on "V". A unitary representation of a Lie group "G" on "V" is a group homomorphism formula_199 with the property that for each fixed formula_14, the map
is a continuous map of "G" into "V".
Finite-dimensional unitary representations.
If the Hilbert space "V" is finite-dimensional, there is an associated representation formula_80 of the Lie algebra formula_102 of formula_8. If formula_8 is connected, then the representation formula_7 of formula_8 is unitary if and only if formula_208 is skew-self-adjoint for each formula_209.
If formula_8 is compact, then every representation formula_7 of formula_8 on a finite-dimensional vector space "V" is "unitarizable," meaning that it is possible to choose an inner product on "V" so that each formula_213 is unitary.
Infinite-dimensional unitary representations.
If the Hilbert space "V" is allowed to be infinite dimensional, the study of unitary representations involves a number of interesting features that are not present in the finite dimensional case. For example, the construction of an appropriate representation of the Lie algebra formula_102 becomes technically challenging. One setting in which the Lie algebra representation is well understood is that of semisimple (or reductive) Lie groups, where the associated Lie algebra representation forms a (g,K)-module.
Examples of unitary representations arise in quantum mechanics and quantum field theory, but also in Fourier analysis as shown in the following example. Let formula_215, and let the complex Hilbert space "V" be formula_216. We define the representation formula_217 by
Here are some important examples in which unitary representations of a Lie group have been analyzed.
Projective representations.
In quantum physics, one is often interested in "projective" unitary representations of a Lie group formula_8. The reason for this interest is that states of a quantum system are represented by vectors in a Hilbert space formula_220—but with the understanding that two states differing by a constant are actually the same physical state. The symmetries of the Hilbert space are then described by unitary operators, but a unitary operator that is a multiple of the identity does not change the physical state of the system. Thus, we are interested not in ordinary unitary representations—that is, homomorphisms of formula_8 into the unitary group formula_222—but rather in projective unitary representations—that is, homomorphisms of formula_8 into the projective unitary group
To put it differently, for a projective representation, we construct a family of unitary operators formula_225, where it is understood that changing formula_226 by a constant of absolute value 1 is counted as "the same" operator. The operators formula_226 are then required to satisfy the homomorphism property "up to a constant":
We have already discussed the irreducible projective unitary representations of the rotation group SO(3) above; considering projective representations allows for fractional spin in addition to integer spin.
 states that for certain types of Lie groups formula_8, irreducible projective unitary representations of formula_8 are in one-to-one correspondence with ordinary unitary representations of the universal cover of formula_8. Important examples where Bargmann's theorem applies are SO(3) (as just mentioned) and the Poincaré group. The latter case is important to Wigner's classification of the projective representations of the Poincaré group, with applications to quantum field theory.
One example where Bargmann's theorem does "not" apply is the group formula_232. The set of translations in position and momentum on formula_233 form a projective unitary representation of formula_232 but they do not come from an ordinary representation of the universal cover of formula_232—which is just formula_232 itself. In this case, to get an ordinary representation, one has to pass to the Heisenberg group, which is a one-dimensional central extension of formula_232. (See the discussion .)
The commutative case.
If formula_8 is a commutative Lie group, then every irreducible unitary representation of formula_8 on complex vector spaces is one dimensional. (This claim follows from Schur's lemma and holds even if the representations are not assumed ahead of time to be finite dimensional.) Thus, the irreducible unitary representations of formula_8 are simply continuous homomorphisms of formula_8 into the unit circle group, U(1). For example, if formula_215, the irreducible unitary representations have the form
for some real number formula_244.
See also Pontryagin duality for this case.


Lie-admissible algebra

In algebra, a Lie-admissible algebra, introduced by , is a (possibly non-associative) algebra that becomes a Lie algebra under the bracket ["a","b"] = "ab–ba". Examples include associative algebras, Lie algebras, and Okubo algebras.


Orthogonal polynomials on the unit circle

In mathematics, orthogonal polynomials on the unit circle are families of polynomials that are orthogonal with respect to integration over the unit circle in the complex plane, for some probability measure on the unit circle. They were introduced by .
Definition.
Suppose that formula_1 is a probability measure on the unit circle in the complex plane, whose support is not finite. The orthogonal polynomials associated to formula_1 are the polynomials formula_3 with leading term formula_4 that are orthogonal with respect to the measure formula_1.
The Szegő recurrence.
Szegő's recurrence states that
where
is the polynomial with its coefficients reversed and complex conjugated, and where the Verblunsky coefficients formula_9 are complex numbers with absolute values less than 1.
Verblunsky's theorem.
Verblunsky's theorem states that any sequence of complex numbers in the open unit disk is the sequence of Verblunsky coefficients for a unique probability measure on the unit circle with infinite support.
Geronimus's theorem.
Geronimus's theorem states that the Verblunsky coefficients of the measure μ are the Schur parameters of the function formula_10 defined by the equations
Baxter's theorem.
Baxter's theorem states that the Verblunsky coefficients form an absolutely convergent series if and only if the moments of formula_1 form an absolutely convergent series and the weight function formula_13 is strictly positive everywhere.
Szegő's theorem.
Szegő's theorem states that
where formula_15 is the absolutely continuous part of the measure formula_1.
Rakhmanov's theorem.
Rakhmanov's theorem states that if the absolutely continuous part formula_13 of the measure formula_1 is positive almost everywhere then the Verblunsky coefficients formula_9 tend to 0.
Examples.
The Rogers–Szegő polynomials are an example of orthogonal polynomials on the unit circle.


Giovanni Frattini

Giovanni Frattini (8 January 1852 – 21 July 1925) was an Italian mathematician, noted for his contributions to group theory.
Biography.
Frattini entered the University of Rome in 1869, where he studied mathematics with Giuseppe Battaglini, Eugenio Beltrami, and Luigi Cremona, obtaining his Laurea in 1875.
In 1885 he published a paper where he defined a certain subgroup of a finite group. This subgroup, now known as the Frattini subgroup, is the subgroup formula_1 generated by all the non-generators of the group formula_2. He showed that formula_1 is nilpotent and, in so doing, developed a method of proof known today as Frattini's argument.


P-core


Anabelian geometry

Anabelian geometry is a theory in number theory, which describes the way in which the algebraic fundamental group "G" of a certain arithmetic variety "V", or some related geometric object, can help to restore "V". The first results for number fields and their absolute Galois groups were obtained by Jürgen Neukirch, Masatoshi Gündüz Ikeda, Kenkichi Iwasawa, and Kôji Uchida (Neukirch–Uchida theorem) prior to conjectures made about hyperbolic curves over number fields by Alexander Grothendieck. As introduced in "Esquisse d'un Programme" the latter were about how topological homomorphisms between two arithmetic fundamental groups of two hyperbolic curves over number fields correspond to maps between the curves. These Grothendieck conjectures were partially solved by Hiroaki Nakamura and , while complete proofs were given by Shinichi Mochizuki.
More recently, Mochizuki introduced and developed a so called mono-anabelian geometry which restores, for a certain class of hyperbolic curves over number fields or some other fields, the curve from its algebraic fundamental group. Key results of mono-anabelian geometry were published in Mochizuki's "Topics in Absolute Anabelian Geometry."
Anabelian geometry can be viewed as one of generalizations of class field theory. Unlike two other generalizations — abelian higher class field theory and representation theoretic Langlands program — anabelian geometry is highly non-linear and non-abelian.
Formulation of a conjecture of Grothendieck on curves.
The "anabelian question" has been formulated as
A concrete example is the case of curves, which may be affine as well as projective. Suppose given a hyperbolic curve "C", i.e., the complement of "n" points in a projective algebraic curve of genus "g", taken to be smooth and irreducible, defined over a field "K" that is finitely generated (over its prime field), such that
Grothendieck conjectured that the algebraic fundamental group "G" of "C", a profinite group, determines "C" itself (i.e., the isomorphism class of "G" determines that of "C"). This was proved by Mochizuki. An example is for the case of formula_2 (the projective line) and formula_3, when the isomorphism class of "C" is determined by the cross-ratio in "K" of the four points removed (almost, there being an order to the four points in a cross-ratio, but not in the points removed). There are also results for the case of "K" a local field.


Free Lie algebra

In mathematics, a free Lie algebra over a field "K" is a Lie algebra generated by a set "X", without any imposed relations other than the defining relations of alternating "K"-bilinearity and the Jacobi identity.
Definition.
The definition of the free Lie algebra generated by a set "X" is as follows:
Given a set "X", one can show that there exists a unique free Lie algebra formula_6 generated by "X".
In the language of category theory, the functor sending a set "X" to the Lie algebra generated by "X" is the free functor from the category of sets to the category of Lie algebras. That is, it is left adjoint to the forgetful functor.
The free Lie algebra on a set "X" is naturally graded. The 0-graded component of the free Lie algebra is just the free vector space on that set.
One can alternatively define a free Lie algebra on a vector space "V" as left adjoint to the forgetful functor from Lie algebras over a field "K" to vector spaces over the field "K" – forgetting the Lie algebra structure, but remembering the vector space structure.
Universal enveloping algebra.
The universal enveloping algebra of a free Lie algebra on a set "X" is the free associative algebra generated by "X". By the Poincaré–Birkhoff–Witt theorem it is the "same size" as the symmetric algebra of the free Lie algebra (meaning that if both sides are graded by giving elements of "X" degree 1 then they are isomorphic as graded vector spaces). This can be used to describe the dimension of the piece of the free Lie algebra of any given degree.
Ernst Witt showed that the number of basic commutators of degree "k" in the free Lie algebra on an "m"-element set is given by the necklace polynomial:
where formula_8 is the Möbius function.
The graded dual of the universal enveloping algebra of a free Lie algebra on a finite set is the shuffle algebra. This essentially follows because universal enveloping algebras have the structure of a Hopf algebra, and the shuffle product describes the action of comultiplication in this algebra. See tensor algebra for a detailed exposition of the inter-relation between the shuffle product and comultiplication.
Hall sets.
An explicit basis of the free Lie algebra can be given in terms of a Hall set, which is a particular kind of subset inside the free magma on "X". Elements of the free magma are binary trees, with their leaves labelled by elements of "X". Hall sets were introduced by based on work of Philip Hall on groups. Subsequently, Wilhelm Magnus showed that they arise as the graded Lie algebra associated with the filtration on a free group given by the lower central series. This correspondence was motivated by commutator identities in group theory due to Philip Hall and Witt.
Lyndon basis.
The Lyndon words are a special case of the Hall words, and so in particular there is a basis of the free Lie algebra corresponding to Lyndon words. This is called the Lyndon basis, named after Roger Lyndon. (This is also called the Chen–Fox–Lyndon basis or the Lyndon–Shirshov basis, and is essentially the same as the Shirshov basis.)
There is a bijection γ from the Lyndon words in an ordered alphabet to a basis of the free Lie algebra on this alphabet defined as follows:
Shirshov–Witt theorem.
 and showed that any Lie subalgebra of a free Lie algebra is itself a free Lie algebra.
Applications.
Serre's theorem on a semisimple Lie algebra uses a free Lie algebra to construct a semisimple algebra out of generators and relations.
The Milnor invariants of a link group are related to the free Lie algebra on the components of the link, as discussed in that article.
See also Lie operad for the use of a free Lie algebra in the construction of the operad.


Span (category theory)

In category theory, a span, roof or correspondence is a generalization of the notion of relation between two objects of a category. When the category has all pullbacks (and satisfies a small number of other conditions), spans can be considered as morphisms in a category of fractions.
Formal definition.
A span is a diagram of type formula_1 i.e., a diagram of the form formula_2.
That is, let Λ be the category (-1 ← 0 → +1). Then a span in a category "C" is a functor "S" : Λ → "C". This means that a span consists of three objects "X", "Y" and "Z" of "C" and morphisms "f" : "X" → "Y" and "g" : "X" → "Z": it is two maps with common "domain".
The colimit of a span is a pushout.
Cospans.
A cospan "K" in a category C is a functor K : Λop → C; equivalently, a "contravariant" functor from Λ to C. That is, a diagram of type formula_8 i.e., a diagram of the form formula_9.
Thus it consists of three objects "X", "Y" and "Z" of C and morphisms "f" : "Y" → "X" and "g" : "Z" → "X": it is two maps with common "codomain."
The limit of a cospan is a pullback.
An example of a cospan is a cobordism "W" between two manifolds "M" and "N", where the two maps are the inclusions into "W". Note that while cobordisms are cospans, the category of cobordisms is not a "cospan category": it is not the category of all cospans in "the category of manifolds with inclusions on the boundary", but rather a subcategory thereof, as the requirement that "M" and "N" form a partition of the boundary of "W" is a global constraint.
The category nCob of finite-dimensional cobordisms is a dagger compact category. More generally, the category Span("C") of spans on any category "C" with finite limits is also dagger compact.


Nonnegative matrix

In mathematics, a nonnegative matrix, written
is a matrix in which all the elements are equal to or greater than zero, that is,
A positive matrix is a matrix in which all the elements are strictly greater than zero. The set of positive matrices is a subset of all non-negative matrices. While such matrices are commonly found, the term is only occasionally used due to the possible confusion with positive-definite matrices, which are different. A matrix which is both non-negative and is positive semidefinite is called a doubly non-negative matrix.
A rectangular non-negative matrix can be approximated by a decomposition with two other non-negative matrices via non-negative matrix factorization.
Eigenvalues and eigenvectors of square positive matrices are described by the Perron–Frobenius theorem.
Inversion.
The inverse of any non-singular M-matrix is a non-negative matrix. If the non-singular M-matrix is also symmetric then it is called a Stieltjes matrix.
The inverse of a non-negative matrix is usually not non-negative. The exception is the non-negative monomial matrices: a non-negative matrix has non-negative inverse if and only if it is a (non-negative) monomial matrix. Note that thus the inverse of a positive matrix is not positive or even non-negative, as positive matrices are not monomial, for dimension .
Specializations.
There are a number of groups of matrices that form specializations of non-negative matrices, e.g. stochastic matrix; doubly stochastic matrix; symmetric non-negative matrix.


Wheel theory

A wheel is a type of algebra (in the sense of universal algebra) where division is always defined. In particular, division by zero is meaningful. The real numbers can be extended to a wheel, as can any commutative ring.
The term "wheel" is inspired by the topological picture formula_1 of the projective line together with an extra point formula_2.
Definition.
A wheel is an algebraic structure formula_3, in which
and satisfying the following properties:
Algebra of wheels.
Wheels replace the usual division as a binary operation with multiplication, with a unary operation applied to one argument formula_24 similar (but not identical) to the multiplicative inverse formula_25, such that formula_26 becomes shorthand for formula_27, but neither formula_28 nor formula_29 in general, and modifies the rules of algebra such that
If there is an element formula_35 such that formula_36, then we may define negation by formula_37 and formula_38.
Other identities that may be derived are
And, for formula_34 with formula_43 and formula_44, we get the usual
If negation can be defined as above then the subset formula_47 is a commutative ring, and every commutative ring is such a subset of a wheel. If formula_34 is an invertible element of the commutative ring then formula_49. Thus, whenever formula_25 makes sense, it is equal to formula_24, but the latter is always defined, even when formula_52.
Examples.
Wheel of fractions.
Let formula_53 be a commutative ring, and let formula_54 be a multiplicative submonoid of formula_53. Define the congruence relation formula_56 on formula_57 via
Define the "wheel of fractions" of formula_53 with respect to formula_54 as the quotient formula_63 (and denoting the equivalence class containing formula_64 as formula_65) with the operations
Projective line and Riemann sphere.
The special case of the above starting with a field produces a projective line extended to a wheel by adjoining an element formula_71, where formula_72. The projective line is itself an extension of the original field by an element formula_73, where formula_74 for any element formula_75 in the field. However, formula_76 is still undefined on the projective line, but is defined in its extension to a wheel.
Starting with the real numbers, the corresponding projective "line" is geometrically a circle, and then the extra point formula_76 gives the shape that is the source of the term "wheel". Or starting with the complex numbers instead, the corresponding projective "line" is a sphere (the Riemann sphere), and then the extra point gives a 3-dimensional version of a wheel.


Stephen Schanuel

Stephen H. Schanuel (1933—2014) was an American mathematician working in the fields of abstract algebra and category theory, number theory, and measure theory.
Life.
While he was a graduate student at University of Chicago, he discovered Schanuel's lemma, an essential lemma in homological algebra. Schanuel received his Ph.D. in mathematics from Columbia University in 1963, under the supervision of Serge Lang.
Work.
Shortly thereafter he stated a conjecture in the field of transcendental number theory, which remains an important open problem to this day. Schanuel was a professor emeritus of mathematics at University at Buffalo.


Arason invariant

In mathematics, the Arason invariant is a cohomological invariant associated to a quadratic form of even rank and trivial discriminant and Clifford invariant over a field "k" of characteristic not 2, taking values in H3("k",Z/2Z). It was introduced by .
The Rost invariant is a generalization of the Arason invariant to other algebraic groups.
Definition.
Suppose that "W"("k") is the Witt ring of quadratic forms over a field "k" and "I" is the ideal of forms of even dimension. The Arason invariant is a group homomorphism from "I"3 to the Galois cohomology group H3("k",Z/2Z). It is determined by the property that on the 8-dimensional diagonal form with entries 1, –"a", –"b", "ab", -"c", "ac", "bc", -"abc" (the 3-fold Pfister form«"a","b","c"») it is given by the cup product of the classes of "a", "b", "c" in H1("k",Z/2Z) = "k"*/"k"*2. The Arason invariant vanishes on "I"4, and it follows from the Milnor conjecture proved by Voevodsky that it is an isomorphism from "I"3/"I"4 to H3("k",Z/2Z).


Transposition cipher

In cryptography, a transposition cipher is a method of encryption by which the positions held by units of plaintext (which are commonly characters or groups of characters) are shifted according to a regular system, so that the ciphertext constitutes a permutation of the plaintext. That is, the order of the units is changed (the plaintext is reordered). Mathematically a bijective function is used on the characters' positions to encrypt and an inverse function to decrypt.
Following are some implementations.
Rail Fence cipher.
The Rail Fence cipher is a form of transposition cipher that gets its name from the way in which it is encoded. In the rail fence cipher, the plaintext is written downwards and diagonally on successive "rails" of an imaginary fence, then moving up when we get to the bottom. The message is then read off in rows. For example, using three "rails" and a message of 'WE ARE DISCOVERED FLEE AT ONCE', the cipherer writes out:
 W . . . E . . . C . . . R . . . L . . . T . . . E
 . E . R . D . S . O . E . E . F . E . A . O . C .
 . . A . . . I . . . V . . . D . . . E . . . N . .
Then reads off:
 WECRL TEERD SOEEF EAOCA IVDEN
Scytale.
The rail fence cipher follows a pattern similar to that of the scytale, a mechanical system of producing a transposition cipher used by the ancient Greeks. The system consisted of a cylinder and a ribbon that was wrapped around the cylinder. The message to be encrypted was written on the coiled ribbon. The letters of the original message would be rearranged when the ribbon was uncoiled from the cylinder. However, the message was easily decrypted when the ribbon was recoiled on a cylinder of the same diameter as the encrypting cylinder. Using the same example as before, if the cylinder has a radius such that only three letters can fit around its circumference, the cipherer writes out:
 W . . E . . A . . R . . E . . D . . I . . S . . C
 . O . . V . . E . . R . . E . . D . . F . . L . .
 . . E . . E . . A . . T . . O . . N . . C . . E .
In this example, the cylinder is running horizontally and the ribbon is wrapped around vertically. Hence, the cipherer then reads off:
 WOEEV EAEAR RTEEO DDNIF CSLEC
Route cipher.
In a route cipher, the plaintext is first written out in a grid of given dimensions, then read off in a pattern given in the key. For example, using the same plaintext that we used for rail fence:
 W R I O R F E O E
 E E S V E L A N J
 A D C E D E T C X
The key might specify "spiral inwards, clockwise, starting from the top right". That would give a cipher text of:
 EJXCTEDEC DAEWRIORF EONALEVSE
Route ciphers have many more keys than a rail fence. In fact, for messages of reasonable length, the number of possible keys is potentially too great to be enumerated even by modern machinery. However, not all keys are equally good. Badly chosen routes will leave excessive chunks of plaintext, or text simply reversed, and this will give cryptanalysts a clue as to the routes.
A variation of the route cipher was the Union Route Cipher, used by Union forces during the American Civil War. This worked much like an ordinary route cipher, but transposed whole words instead of individual letters. Because this would leave certain highly sensitive words exposed, such words would first be concealed by code. The cipher clerk may also add entire null words, which were often chosen to make the ciphertext humorous.
Columnar transposition.
In a columnar transposition, the message is written out in rows of a fixed length, and then read out again column by column, and the columns are chosen in some scrambled order. Both the width of the rows and the permutation of the columns are usually defined by a keyword. For example, the keyword ZEBRAS is of length 6 (so the rows are of length 6), and the permutation is defined by the alphabetical order of the letters in the keyword. In this case, the order would be "6 3 2 4 1 5".
In a regular columnar transposition cipher, any spare spaces are filled with nulls; in an irregular columnar transposition cipher, the spaces are left blank. Finally, the message is read off in columns, in the order specified by the keyword. For example, suppose we use the keyword ZEBRAS and the message WE ARE DISCOVERED. FLEE AT ONCE. In a regular columnar transposition, we write this into the grid as follows:
 6 3 2 4 1 5
 W E A R E D
 I S C O V E
 R E D F L E
 E A T O N C
 E Q K J E U
providing five nulls (QKJEU), these letters can be randomly selected as they just fill out the incomplete columns and are not part of the message. The ciphertext is then read off as:
 EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE
In the irregular case, the columns are not completed by nulls:
 6 3 2 4 1 5
 W E A R E D
 I S C O V E
 R E D F L E
 E A T O N C
 E
This results in the following ciphertext:
 EVLNA CDTES EAROF ODEEC WIREE
To decipher it, the recipient has to work out the column lengths by dividing the message length by the key length. Then he can write the message out in columns again, then re-order the columns by reforming the key word.
In a variation, the message is blocked into segments that are the key length long and to each segment the same permutation (given by the key) is applied. This is equivalent to a columnar transposition where the read-out is by rows instead of columns.
Columnar transposition continued to be used for serious purposes as a component of more complex ciphers at least into the 1950s.
Double transposition.
A single columnar transposition could be attacked by guessing possible column lengths, writing the message out in its columns (but in the wrong order, as the key is not yet known), and then looking for possible anagrams. Thus to make it stronger, a double transposition was often used. This is simply a columnar transposition applied twice. The same key can be used for both transpositions, or two different keys can be used.
As an example, we can take the result of the irregular columnar transposition in the previous section, and perform a second encryption with a different keyword, STRIPE, which gives the permutation "564231":
 5 6 4 2 3 1
 E V L N A C
 D T E S E A
 R O F O D E
 E C W I R E
 E
As before, this is read off columnwise to give the ciphertext:
 CAEEN SOIAE DRLEF WEDRE EVTOC
If multiple messages of exactly the same length are encrypted using the same keys, they can be anagrammed simultaneously. This can lead to both recovery of the messages, and to recovery of the keys (so that every other message sent with those keys can be read).
During World War I, the German military used a double columnar transposition cipher, changing the keys infrequently. The system was regularly solved by the French, naming it Übchi, who were typically able to quickly find the keys once they'd intercepted a number of messages of the same length, which generally took only a few days. However, the French success became widely known and, after a publication in "Le Matin", the Germans changed to a new system on 18 November 1914.
During World War II, the double transposition cipher was used by Dutch Resistance groups, the French Maquis and the British Special Operations Executive (SOE), which was in charge of managing underground activities in Europe. It was also used by agents of the American Office of Strategic Services and as an emergency cipher for the German Army and Navy.
Until the invention of the VIC cipher, double transposition was generally regarded as the most complicated cipher that an agent could operate reliably under difficult field conditions.
Cryptanalysis.
The double transposition cipher can be treated as a single transposition with a key as long as the product of the lengths of the two keys.
In late 2013, a double transposition challenge, regarded by its author as undecipherable, was solved by George Lasry using a divide-and-conquer approach where each transposition was attacked individually.
Myszkowski transposition.
A variant form of columnar transposition, proposed by Émile Victor Théodore Myszkowski in 1902, requires a keyword with recurrent letters. In usual practice, subsequent occurrences of a keyword letter are treated as if the next letter in alphabetical order, "e.g.," the keyword TOMATO yields a numeric keystring of "532164."
In Myszkowski transposition, recurrent keyword letters are numbered identically, TOMATO yielding a keystring of "432143."
 4 3 2 1 4 3
 W E A R E D
 I S C O V E
 R E D F L E
 E A T O N C
 E
Plaintext columns with unique numbers are transcribed downward;
those with recurring numbers are transcribed left to right:
 ROFOA CDTED SEEEA CWEIV RLENE
Disrupted transposition.
A disrupted transposition cipher further complicates the transposition pattern with irregular filling of the rows of the matrix, i.e. with some spaces intentionally left blank (or blackend out like in the Rasterschlüssel 44), or filled later with either another part of the plaintext or random letters. One possible algorithm is to start a new row whenever the plaintext reaches a password character. Another simple option would be to use a password that places blanks according to its number sequence. E.g. "SECRET" would be decoded to a sequence of "5,2,1,4,3,6" and cross out the 5th field of the matrix, then count again and cross out the second field, etc. The following example would be a matrix set up for columnar transposition with the columnar key "CRYPTO" and filled with crossed out fields according to the disruption key "SECRET" (marked with astersik), whereafter the message "we are discovered, flee at once" is placed in the leftover spaces. The resulting ciphertext (the columns read according to the transposition key) is "WCEEO ERET RIVFC EODN SELE ADA".
 C R Y P T O
 1 4 6 3 5 2
 W E A R * E
 * * D I S *
 C O * V E R
 E D * F L E
 E * A * * T
 O N * C E *
Grilles.
Another form of transposition cipher uses "grilles", or physical masks with cut-outs. This can produce a highly irregular transposition over the period specified by the size of the grille, but requires the correspondents to keep a physical key secret. Grilles were first proposed in 1550, and were still in military use for the first few months of World War One.
Detection and cryptanalysis.
Since transposition does not affect the frequency of individual symbols, simple transposition can be easily detected by the cryptanalyst by doing a frequency count. If the ciphertext exhibits a frequency distribution very similar to plaintext, it is most likely a transposition. This can then often be attacked by anagramming—sliding pieces of ciphertext around, then looking for sections that look like anagrams of English words, and solving the anagrams. Once such anagrams have been found, they reveal information about the transposition pattern, and can consequently be extended.
Simpler transpositions also often suffer from the property that keys very close to the correct key will reveal long sections of legible plaintext interspersed by gibberish. Consequently, such ciphers may be vulnerable to optimum seeking algorithms such as genetic algorithms.
A detailed description of the cryptanalysis of a German transposition cipher
can be found in chapter 7 of Herbert Yardley's "The American Black Chamber."
A cipher used by the Zodiac Killer, called "Z-340", organized into triangular sections with substitution of 63 different symbols for the letters and diagonal "knight move" transposition, remained unsolved for over 51 years, until an international team of private citizens cracked it on December 5, 2020 using specialized software.
Combinations.
Transposition is often combined with other techniques such as evaluation methods. For example, a simple substitution cipher combined with a columnar transposition avoids the weakness of both. Replacing high frequency ciphertext symbols with high frequency plaintext letters does not reveal chunks of plaintext because of the transposition. Anagramming the transposition does not work because of the substitution. The technique is particularly powerful if combined with fractionation (see below). A disadvantage is that such ciphers are considerably more laborious and error prone than simpler ciphers.
Fractionation.
Transposition is particularly effective when employed with fractionation – that is, a preliminary stage that divides each plaintext symbol into several ciphertext symbols. For example, the plaintext alphabet could be written out in a grid, and every letter in the message replaced by its co-ordinates (see Polybius square and Straddling checkerboard).
Another method of fractionation is to simply convert the message to Morse code, with a symbol for spaces as well as dots and dashes.
When such a fractionated message is transposed, the components of individual letters become widely separated in the message, thus achieving Claude E. Shannon's diffusion. Examples of ciphers that combine fractionation and transposition include the bifid cipher, the trifid cipher, the ADFGVX cipher and the VIC cipher.
Another choice would be to replace each letter with its binary representation, transpose that, and then convert the new binary string into the corresponding ASCII characters. Looping the scrambling process on the binary string multiple times before changing it into ASCII characters would likely make it harder to break. Many modern block ciphers use more complex forms of transposition related to this simple idea.


Gottlieb polynomials

In mathematics, Gottlieb polynomials are a family of discrete orthogonal polynomials introduced by . They are given by


Parabolic Lie algebra

In algebra, a parabolic Lie algebra formula_1 is a subalgebra of a semisimple Lie algebra formula_2 satisfying one of the following two conditions:
These conditions are equivalent over an algebraically closed field of characteristic zero, such as the complex numbers. If the field formula_8 is not algebraically closed, then the first condition is replaced by the assumption that
where formula_11 is the algebraic closure of formula_8.


Sextic function


Vector operator

A vector operator is a differential operator used in vector calculus. Vector operators are defined in terms of del, and include the gradient, divergence, and curl:
The Laplacian is
Vector operators must always come right before the scalar field or vector field on which they operate, in order to produce a result. E.g.
yields the gradient of "f", but
is just another vector operator, which is not operating on anything.
A vector operator can operate on another vector operator, to produce a compound vector operator, as seen above in the case of the Laplacian.


Weierstrass transform

In mathematics, the Weierstrass transform of a function , named after Karl Weierstrass, is a "smoothed" version of obtained by averaging the values of , weighted with a Gaussian centered at "x".
Specifically, it is the function defined by
the convolution of with the Gaussian function
The factor 1/√(4π) is chosen so that the Gaussian will have a total integral of 1, with the consequence that constant functions are not changed by the Weierstrass transform.
Instead of one also writes . Note that need not exist for every real number , when the defining integral fails to converge.
The Weierstrass transform is intimately related to the heat equation (or, equivalently, the diffusion equation with constant diffusion coefficient). If the function describes the initial temperature at each point of an infinitely long rod that has constant thermal conductivity equal to 1, then the temperature distribution of the rod "t" = 1 time units later will be given by the function "F". By using values of "t" different from 1, we can define the generalized Weierstrass transform of .
The generalized Weierstrass transform provides a means to approximate a given integrable function arbitrarily well with analytic functions.
Names.
Weierstrass used this transform in his original proof of the Weierstrass approximation theorem. It is also known as the Gauss transform or Gauss–Weierstrass transform after Carl Friedrich Gauss and as the Hille transform after Einar Carl Hille who studied it extensively. The generalization "Wt" mentioned below is known in signal analysis as a Gaussian filter and in image processing (when implemented on R2) as a Gaussian blur.
Transforms of some important functions.
As mentioned above, every constant function is its own Weierstrass transform. The Weierstrass transform of any polynomial is a polynomial of the same degree, and in fact same leading coefficient (the asymptotic growth is unchanged). Indeed, if denotes the (physicist's) Hermite polynomial of degree "n", then the Weierstrass transform of (/2) is simply . This can be shown by exploiting the fact that the generating function for the Hermite polynomials is closely related to the Gaussian kernel used in the definition of the Weierstrass transform.
The Weierstrass transform of the function "e""ax" (where "a" is an arbitrary constant) is "e""a"2 "e""ax". The function "e""ax" is thus an eigenfunction of the Weierstrass transform. (This is, in fact, more generally true for "all" convolution transforms.)
Setting "a"="bi" where "i" is the imaginary unit, and applying Euler's identity, one sees that the Weierstrass transform of the function cos("bx") is "e"−"b"2 cos("bx") and the Weierstrass transform of the function sin("bx") is "e"−"b"2 sin("bx").
The Weierstrass transform of the function "e""ax"2 is
In particular, by choosing "a" negative, it is evident that the Weierstrass transform of a Gaussian function is again a Gaussian function, but a "wider" one.
General properties.
The Weierstrass transform assigns to each function "f" a new function "F"; this assignment is linear. It is also translation-invariant, meaning that the transform of the function "f"("x" + "a") is "F"("x" + "a"). Both of these facts are more generally true for any integral transform defined via convolution.
If the transform "F"("x") exists for the real numbers "x" = "a" and "x" = "b", then it also exists for all real values in between and forms an analytic function there; moreover, "F"("x") will exist for all complex values of "x" with "a" ≤ Re("x") ≤ "b" and forms a holomorphic function on that strip of the complex plane. This is the formal statement of the "smoothness" of "F" mentioned above.
If "f" is integrable over the whole real axis (i.e. "f" ∈ L1(R)), then so is its Weierstrass transform "F", and if furthermore "f"("x") ≥ 0 for all "x", then also "F"("x") ≥ 0 for all "x" and the integrals of "f" and "F" are equal. This expresses the physical fact that the total thermal energy or heat is conserved by the heat equation, or that the total amount of diffusing material is conserved by the diffusion equation.
Using the above, one can show that for 0 < "p" ≤ ∞ and "f" ∈ Lp(R), we have "F" ∈ Lp(R) and ||"F"||"p" ≤ ||"f"||p. The Weierstrass transform consequently yields a bounded operator W : Lp(R) → Lp(R).
If "f" is sufficiently smooth, then the Weierstrass transform of the "k"-th derivative of "f" is equal to the "k"-th derivative of the Weierstrass transform of "f".
There is a formula relating the Weierstrass transform "W" and the two-sided Laplace transform "L". If we define
then
Low-pass filter.
We have seen above that the Weierstrass transform of cos("bx") is "e"−"b"2 cos("bx"), and analogously for sin("bx"). In terms of signal analysis, this suggests that if the signal "f" contains the frequency "b" (i.e. contains a summand which is a combination of sin("bx") and cos("bx")), then the transformed signal "F" will contain the same frequency, but with an amplitude multiplied by the factor "e"−"b"2. This has the consequence that higher frequencies are reduced more than lower ones, and the Weierstrass transform thus acts as a low-pass filter. This can also be shown with the continuous Fourier transform, as follows. The Fourier transform analyzes a signal in terms of its frequencies, transforms convolutions into products, and transforms Gaussians into Gaussians. The Weierstrass transform is convolution with a Gaussian and is therefore "multiplication" of the Fourier transformed signal with a Gaussian, followed by application of the inverse Fourier transform. This multiplication with a Gaussian in frequency space blends out high frequencies, which is another way of describing the "smoothing" property of the Weierstrass transform.
The inverse transform.
The following formula, closely related to the Laplace transform of a Gaussian function, and a real analogue to the Hubbard–Stratonovich transformation, is relatively easy to establish:
Now replace "u" with the formal differentiation operator "D" = "d"/"dx" and utilize the Lagrange shift operator
(a consequence of the Taylor series formula and the definition of the exponential function), to obtain
to thus obtain the following formal expression for the Weierstrass transform "W",
where the operator on the right is to be understood as acting on the function "f"("x") as
The above formal derivation glosses over details of convergence, and the formula "W" = "e""D"2 is thus not universally valid; there are several functions "f" which have a well-defined Weierstrass transform, but for which "e""D"2"f"("x") cannot be meaningfully defined.
Nevertheless, the rule is still quite useful and can, for example, be used to derive the Weierstrass transforms of polynomials, exponential and trigonometric functions mentioned above.
The formal inverse of the Weierstrass transform is thus given by
Again, this formula is not universally valid but can serve as a guide. It can be shown to be correct for certain classes of functions if the right-hand side operator is properly defined.
One may, alternatively, attempt to invert the Weierstrass transform in a slightly different way: given the analytic function
apply "W"−1 to obtain
once more using a fundamental property of the (physicists') Hermite polynomials .
Again, this formula for "f"("x") is at best formal, since one didn't check whether the final series converges. But if, for instance, "f" ∈ L2(R), then knowledge of all the derivatives of "F" at "x" = 0 suffices to yield the coefficients "an"; and to thus reconstruct as a series of Hermite polynomials.
A third method of inverting the Weierstrass transform exploits its connection to the Laplace transform mentioned above, and the well-known inversion formula for the Laplace transform. The result is stated below for distributions.
Generalizations.
We can use convolution with the Gaussian kernel formula_13 (with some "t" > 0) instead of
formula_14, thus defining an operator , the generalized Weierstrass transform.
For small values of is very close to , but smooth. The larger , the more this operator averages out and changes . Physically, corresponds to following the heat (or diffusion) equation for time units, and this is additive,
corresponding to "diffusing for time units, then time units, is equivalent to diffusing for time units". One can extend this to "t" = 0 by setting to be the identity operator (i.e. convolution with the Dirac delta function), and these then form a one-parameter semigroup of operators.
The kernel formula_13 used for the generalized Weierstrass transform is sometimes called the Gauss–Weierstrass kernel, and is Green's function for the diffusion equation formula_17 on R.
 can be computed from : given a function , define a new function ; then , a consequence of the substitution rule.
The Weierstrass transform can also be defined for certain classes of distributions or "generalized functions". For example, the Weierstrass transform of the Dirac delta is the Gaussian formula_18.
In this context, rigorous inversion formulas can be proved, e.g.,
where "x"0 is any fixed real number for which exists, the integral extends over the vertical line in the complex plane with real part "x"0, and the limit is to be taken in the sense of distributions.
Furthermore, the Weierstrass transform can be defined for real- (or complex-) valued functions (or distributions) defined on R"n". We use the same convolution formula as above but interpret the integral as extending over all of R"n" and the expression as the square of the Euclidean length of the vector "x" − "y"; the factor in front of the integral has to be adjusted so that the Gaussian will have a total integral of 1.
More generally, the Weierstrass transform can be defined on any Riemannian manifold: the heat equation can be formulated there (using the manifold's Laplace–Beltrami operator), and the Weierstrass transform is then given by following the solution of the heat equation for one time unit, starting with the initial "temperature distribution" "f".
Related transforms.
If one considers convolution with the kernel instead of with a Gaussian, one obtains the Poisson transform which smoothes and averages a given function in a manner similar to the Weierstrass transform.


Boole polynomials

In mathematics, the Boole polynomials "s""n"("x") are polynomials given by the generating function


Gain group


Tridiagonal matrix algorithm

In numerical linear algebra, the tridiagonal matrix algorithm, also known as the Thomas algorithm (named after Llewellyn Thomas), is a simplified form of Gaussian elimination that can be used to solve tridiagonal systems of equations. A tridiagonal system for "n" unknowns may be written as
where formula_2 and formula_3.
For such systems, the solution can be obtained in formula_5 operations instead of formula_6 required by Gaussian elimination. A first sweep eliminates the formula_7's, and then an (abbreviated) backward substitution produces the solution. Examples of such matrices commonly arise from the discretization of 1D Poisson equation and natural cubic spline interpolation.
Thomas' algorithm is not stable in general, but is so in several special cases, such as when the matrix is diagonally dominant (either by rows or columns) or symmetric positive definite; for a more precise characterization of stability of Thomas' algorithm, see Higham Theorem 9.12. If stability is required in the general case, Gaussian elimination with partial pivoting (GEPP) is recommended instead.
Method.
The forward sweep consists of the computation of new coefficients as follows, denoting the new coefficients with primes:
and
The solution is then obtained by back substitution:
The method above does not modify the original coefficient vectors, but must also keep track of the new coefficients. If the coefficient vectors may be modified, then an algorithm with less bookkeeping is:
followed by the back substitution
The implementation in a VBA subroutine without preserving the coefficient vectors is shown below
Sub TriDiagonal_Matrix_Algorithm(N%, A#(), B#(), C#(), D#(), X#())
 Dim i%, W#
 For i = 2 To N
 W = A(i) / B(i - 1)
 B(i) = B(i) - W * C(i - 1)
 D(i) = D(i) - W * D(i - 1)
 Next i
 X(N) = D(N) / B(N)
 For i = N - 1 To 1 Step -1
 X(i) = (D(i) - C(i) * X(i + 1)) / B(i)
 Next i
End Sub
Derivation.
The derivation of the tridiagonal matrix algorithm is a special case of Gaussian elimination.
Suppose that the unknowns are formula_15, and that the equations to be solved are:
Consider modifying the second (formula_17) equation with the first equation as follows:
which would give:
Note that formula_20 has been eliminated from the second equation. Using a similar tactic with the modified second equation on the third equation yields:
This time formula_22 was eliminated. If this procedure is repeated until the formula_23 row; the (modified) formula_23 equation will involve only one unknown, formula_25. This may be solved for and then used to solve the formula_26 equation, and so on until all of the unknowns are solved for.
Clearly, the coefficients on the modified equations get more and more complicated if stated explicitly. By examining the procedure, the modified coefficients (notated with tildes) may instead be defined recursively:
To further hasten the solution process, formula_34 may be divided out (if there's no division by zero risk), the newer modified coefficients, each notated with a prime, will be:
This gives the following system with the same unknowns and coefficients defined in terms of the original ones above:
The last equation involves only one unknown. Solving it in turn reduces the next last equation to one unknown, so that this backward substitution can be used to find all of the unknowns:
Variants.
In some situations, particularly those involving periodic boundary conditions, a slightly perturbed form of the tridiagonal system may need to be solved:
In this case, we can make use of the Sherman-Morrison formula to avoid the additional operations of Gaussian elimination and still use the Thomas algorithm. The method requires solving a modified non-cyclic version of the system for both the input and a sparse corrective vector, and then combining the solutions. This can be done efficiently if both solutions are computed at once, as the forward portion of the pure tridiagonal matrix algorithm can be shared.
In other situations, the system of equations may be block tridiagonal (see block matrix), with smaller submatrices arranged as the individual elements in the above matrix system (e.g., the 2D Poisson problem). Simplified forms of Gaussian elimination have been developed for these situations.
The textbook "Numerical Mathematics" by Quarteroni, Sacco and Saleri, lists a modified version of the algorithm which avoids some of the divisions (using instead multiplications), which is beneficial on some computer architectures.
Parallel tridiagonal solvers have been published for many vector and parallel architectures, including GPUs
For an extensive treatment of parallel tridiagonal and block tridiagonal solvers see


Difference algebra

Difference algebra is a branch of mathematics concerned with the study of difference (or functional) equations from the algebraic point of view. Difference algebra is analogous to differential algebra but concerned with difference equations rather than differential equations. As an independent subject it was initiated by Joseph Ritt and his student Richard Cohn.
Difference rings, difference fields and difference algebras.
A "difference ring" is a commutative ring formula_1 together with a ring endomorphism formula_2. Often it is assumed that formula_3 is injective. When formula_4 is a field one speaks of a "difference field". A classical example of a difference field is the field formula_5 of rational functions with the difference operator formula_3 given by formula_7. The role of difference rings in difference algebra is similar to the role of commutative rings in commutative algebra and algebraic geometry. A morphism of difference rings is a morphism of rings that commutes with formula_3. A "difference algebra" over a difference field formula_9 is a difference ring formula_4 with a formula_9-algebra structure such that formula_12 is a morphism of difference rings, i.e. formula_2 extends formula_14. A difference algebra that is a field is called a "difference field extension".
Algebraic difference equations.
The difference polynomial ring formula_15 over a difference field formula_9 in the (difference) variables formula_17 is the polynomial ring over formula_9 in the infinitely many variables formula_19. It becomes a difference algebra over formula_9 by extending formula_3 from formula_9 to formula_23 as suggested by the naming of the variables.
By a "system of algebraic difference" equations over formula_9 one means any subset formula_25 of formula_23. If formula_4 is a difference algebra over formula_9 the solutions of formula_25 in formula_4 are
Classically one is mainly interested in solutions in difference field extensions of formula_9. For example, if formula_5 and formula_4 is the field of meromorphic functions on formula_35 with difference operator formula_3 given by formula_7, then the fact that the gamma function formula_38 satisfies the functional equation formula_39 can be restated abstractly as formula_40.
Difference varieties.
Intuitively, a "difference variety" over a difference field formula_9 is the set of solutions of a system of algebraic difference equations over formula_9. This definition has to be made more precise by specifying where one is looking for the solutions. Usually one is looking for solutions in the so-called universal family of difference field extensions of formula_9. Alternatively, one may define a difference variety as a functor from the category of difference field extensions of formula_9 to the category of sets, which is of the form formula_45 for some formula_46.
There is a one-to-one correspondence between the difference varieties defined by algebraic difference equations in the variables formula_17 and certain ideals in formula_23, namely the perfect difference ideals of formula_23. One of the basic theorems in difference algebra asserts that every ascending chain of perfect difference ideals in formula_23 is finite. This result can be seen as a difference analog of Hilbert's basis theorem.
Applications.
Difference algebra is related to many other mathematical areas, such as discrete dynamical systems, combinatorics, number theory, or model theory. While some real life problems, such as population dynamics, can be modeled by algebraic difference equations, difference algebra also has applications in pure mathematics. For example, there is a proof of the Manin–Mumford conjecture using methods of difference algebra. The model theory of difference fields has been studied.


Quasi-abelian category

In mathematics, specifically in category theory, a quasi-abelian category is a pre-abelian category in which the pushout of a kernel along arbitrary morphisms is again a kernel and, dually, the pullback of a cokernel along arbitrary morphisms is again a cokernel.
Definition.
Let formula_1 be a pre-abelian category. A morphism formula_2 is a kernel (a cokernel) if there exists a morphism formula_3 such that formula_2 is a kernel (cokernel) of formula_3. The category formula_1 is quasi-abelian if for every kernel formula_7 and every morphism formula_8 in the pushout diagram
the morphism formula_9 is again a kernel and, dually, for every cokernel formula_10 and every morphism formula_11 in the pullback diagram
the morphism formula_12 is again a cokernel.
Equivalently, a quasi-abelian category is a pre-abelian category in which the system of all kernel-cokernel pairs forms an exact structure.
Given a pre-abelian category, those kernels, which are stable under arbitrary pushouts, are sometimes called the semi-stable kernels. Dually, cokernels, which are stable under arbitrary pullbacks, are called semi-stable cokernels.
Properties.
Let formula_2 be a morphism in a quasi-abelian category. Then the induced morphism formula_14 is always a bimorphism, i.e., a monomorphism and an epimorphism. A quasi-abelian category is therefore always semi-abelian.
Examples.
Every "abelian category" is quasi-abelian. Typical non-abelian examples arise in functional analysis.
History.
The concept of quasi-abelian category was developed in the 1960s. The history is involved. This is in particular due to Raikov's conjecture, which stated that the notion of a semi-abelian category is equivalent to that of a quasi-abelian category. Around 2005 it turned out that the conjecture is false.
Left and right quasi-abelian categories.
By dividing the two conditions in the definition, one can define left quasi-abelian categories by requiring that cokernels are stable under pullbacks and right quasi-abelian categories by requiring that kernels stable under pushouts.


Crout matrix decomposition

In linear algebra, the Crout matrix decomposition is an LU decomposition which decomposes a matrix into a lower triangular matrix (L), an upper triangular matrix (U) and, although not always needed, a permutation matrix (P). It was developed by Prescott Durand Crout.
The Crout matrix decomposition algorithm differs slightly from the Doolittle method. Doolittle's method returns a unit lower triangular matrix and an upper triangular matrix, while the Crout method returns a lower triangular matrix and a unit upper triangular matrix.
So, if a matrix decomposition of a matrix A is such that:
being L a unit lower triangular matrix, D a diagonal matrix and U a unit upper triangular matrix, then Doolittle's method produces
and Crout's method produces
Implementations.
C implementation:
void crout(double const **A, double **L, double **U, int n) {
 int i, j, k;
 double sum = 0;
 for (i = 0; i < n; i++) {
 U[i][i] = 1;
 for (j = 0; j < n; j++) {
 for (i = j; i < n; i++) {
 sum = 0;
 for (k = 0; k < j; k++) {
 sum = sum + L[i][k] * U[k][j];
 L[i][j] = A[i][j] - sum;
 for (i = j; i < n; i++) {
 sum = 0;
 for(k = 0; k < j; k++) {
 sum = sum + L[j][k] * U[k][i];
 if (L[j][j] == 0) {
 printf("det(L) close to 0!\n Can't divide by 0...\n");
 exit(EXIT_FAILURE);
 U[j][i] = (A[j][i] - sum) / L[j][j];
Octave/Matlab implementation:
 function [L, U] = LUdecompCrout(A)
 [R, C] = size(A);
 for i = 1:R
 L(i, 1) = A(i, 1);
 U(i, i) = 1;
 end
 for j = 2:R
 U(1, j) = A(1, j) / L(1, 1);
 end
 for i = 2:R
 for j = 2:i
 L(i, j) = A(i, j) - L(i, 1:j - 1) * U(1:j - 1, j);
 end
 for j = i + 1:R
 U(i, j) = (A(i, j) - L(i, 1:i - 1) * U(1:i - 1, j)) / L(i, i);
 end
 end
 end


FinOrd


Biquadratic field

In mathematics, a biquadratic field is a number field "K" of a particular kind, which is a Galois extension of the rational number field Q with Galois group the Klein four-group.
Structure and subfields.
Biquadratic fields are all obtained by adjoining two square roots. Therefore in explicit terms they have the form
for rational numbers "a" and "b". There is no loss of generality in taking "a" and "b" to be non-zero and square-free integers.
According to Galois theory, there must be three quadratic fields contained in "K", since the Galois group has three subgroups of index 2. The third subfield, to add to the evident Q() and Q(), is Q().
L-function.
Biquadratic fields are the simplest examples of abelian extensions of Q that are not cyclic extensions. According to general theory the Dedekind zeta-function of such a field is a product of the Riemann zeta-function and three Dirichlet L-functions. Those L-functions are for the Dirichlet characters which are the Jacobi symbols attached to the three quadratic fields. Therefore taking the product of the Dedekind zeta-functions of the quadratic fields, multiplying them together, and dividing by the square of the Riemann zeta-function, is a recipe for the Dedekind zeta-function of the biquadratic field. This illustrates also some general principles on abelian extensions, such as the calculation of the conductor of a field.
Such L-functions have applications in analytic theory (Siegel zeroes), and in some of Kronecker's work.