Quotient group

A quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure (the rest of the structure is "factored" out). For example, the cyclic group of addition modulo "n" can be obtained from the group of integers under addition by identifying elements that differ by a multiple of "n" and defining a group structure that operates on each such class (known as a congruence class) as a single entity. It is part of the mathematical field known as group theory.
In a quotient of a group, the equivalence class of the identity element is always a normal subgroup of the original group, and the other equivalence classes are precisely the cosets of that normal subgroup. The resulting quotient is written , where "G" is the original group and "N" is the normal subgroup. (This is pronounced ""G" mod "N"", where "mod" is short for modulo.)
Much of the importance of quotient groups is derived from their relation to homomorphisms. The first isomorphism theorem states that the image of any group "G" under a homomorphism is always isomorphic to a quotient of "G". Specifically, the image of "G" under a homomorphism is isomorphic to where ker("φ") denotes the kernel of "φ".
The dual notion of a quotient group is a subgroup, these being the two primary ways of forming a smaller group from a larger one. Any normal subgroup has a corresponding quotient group, formed from the larger group by eliminating the distinction between elements of the subgroup. In category theory, quotient groups are examples of quotient objects, which are dual to subobjects. For other examples of quotient objects, see quotient ring, quotient space (linear algebra), quotient space (topology), and quotient set.
Definition and illustration.
Given a group "G" and a subgroup "H", and an element "a" ∈ "G", one can consider the corresponding left coset: "aH" := { "ah" : "h" ∈ "H" }. Cosets are a natural class of subsets of a group; for example consider the abelian group "G" of integers, with operation defined by the usual addition, and the subgroup "H" of even integers. Then there are exactly two cosets: 0 + "H", which are the even integers, and 1 + "H", which are the odd integers (here we are using additive notation for the binary operation instead of multiplicative notation).
For a general subgroup "H", it is desirable to define a compatible group operation on the set of all possible cosets, { "aH" : "a" ∈ "G" }. This is possible exactly when "H" is a normal subgroup, see below. A subgroup "N" of a group "G" is normal if and only if the coset equality "aN" = "Na" holds for all "a" ∈ "G". A normal subgroup of "G" is denoted .
Definition.
Let "N" be a normal subgroup of a group "G". Define the set "G"/"N" to be the set of all left cosets of "N" in "G". That is, . Since the identity element "e" ∈ "N", "a" ∈ "aN". Define a binary operation on the set of cosets, "G"/"N", as follows. For each "aN" and "bN" in "G"/"N", the product of "aN" and "bN", ("aN")("bN"), is ("ab")"N". This works only because ("ab")"N" does not depend on the choice of the representatives, "a" and "b", of each left coset, "aN" and "bN". To prove this, suppose "xN" = "aN" and "yN" = "bN" for some "x", "y", "a", "b" ∈ "G". Then
This depends on the fact that "N" is a normal subgroup. It still remains to be shown that this condition is not only sufficient but necessary to define the operation on "G"/"N".
To show that it is necessary, consider that for a subgroup "N" of "G", we have been given that the operation is well defined. That is, for all "xN" = "aN" and "yN" = "bN," for "x", "y", "a", "b" ∈ "G", ("ab")"N" = ("xy")"N."
Let "n" ∈ "N" and "g" ∈ "G". Since "eN" = "nN," we have, "gN" = ("eg")"N" = ("ng")"N."
Now, "gN" = ("ng")"N" ⇔ "N" = "g"−1("ng")"N" ⇔ "g"−1"ng" ∈ "N" ∀ "n" ∈ "N" and "g" ∈ "G".
Hence "N" is a normal subgroup of "G".
It can also be checked that this operation on "G"/"N" is always associative. "G"/"N" has identity element "N" and the inverse of element "aN" can always be represented by "a"−1"N". Therefore, the set "G"/"N" together with the operation defined by ("aN")("bN") = ("ab")"N" forms a group, the quotient group of "G" by "N".
Due to the normality of "N", the left cosets and right cosets of "N" in "G" are the same, and so, "G"/"N" could have been defined to be the set of right cosets of "N" in "G".
Example: Addition modulo 6.
For example, consider the group with addition modulo 6: "G" = {0, 1, 2, 3, 4, 5}. Consider the subgroup "N" = {0, 3}, which is normal because "G" is abelian. Then the set of (left) cosets is of size three:
The binary operation defined above makes this set into a group, known as the quotient group, which in this case is isomorphic to the cyclic group of order 3.
Motivation for the name "quotient".
The reason "G"/"N" is called a quotient group comes from division of integers. When dividing 12 by 3 one obtains the answer 4 because one can regroup 12 objects into 4 subcollections of 3 objects. The quotient group is the same idea, although we end up with a group for a final answer instead of a number because groups have more structure than an arbitrary collection of objects.
To elaborate, when looking at "G"/"N" with "N" a normal subgroup of "G", the group structure is used to form a natural "regrouping". These are the cosets of "N" in "G". Because we started with a group and normal subgroup, the final quotient contains more information than just the number of cosets (which is what regular division yields), but instead has a group structure itself.
Examples.
Even and odd integers.
Consider the group of integers Z (under addition) and the subgroup 2Z consisting of all even integers. This is a normal subgroup, because Z is abelian. There are only two cosets: the set of even integers and the set of odd integers, and therefore the quotient group Z/2Z is the cyclic group with two elements. This quotient group is isomorphic with the set with addition modulo 2; informally, it is sometimes said that Z/2Z "equals" the set with addition modulo 2.
Example further explained...
Remainders of integer division.
A slight generalization of the last example. Once again consider the group of integers Z under addition. Let "n" be any positive integer. We will consider the subgroup "nZ of Z consisting of all multiples of "n". Once again "nZ is normal in Z because Z is abelian. The cosets are the collection {"nZ, 1+"nZ, ..., ("n"−2)+"nZ, ("n"−1)+"nZ}. An integer "k" belongs to the coset "r"+"nZ, where "r" is the remainder when dividing "k" by "n". The quotient Z/"nZ can be thought of as the group of "remainders" modulo "n". This is a cyclic group of order "n".
Complex integer roots of 1.
The twelfth roots of unity, which are points on the complex unit circle, form a multiplicative abelian group "G", shown on the picture on the right as colored balls with the number at each point giving its complex argument. Consider its subgroup "N" made of the fourth roots of unity, shown as red balls. This normal subgroup splits the group into three cosets, shown in red, green and blue. One can check that the cosets form a group of three elements (the product of a red element with a blue element is blue, the inverse of a blue element is green, etc.). Thus, the quotient group "G"/"N" is the group of three colors, which turns out to be the cyclic group with three elements.
The real numbers modulo the integers.
Consider the group of real numbers R under addition, and the subgroup Z of integers. Each coset of Z in R is a set of the form "a"+Z, where "a" is a real number. Since "a1"+Z and "a2"+Z are identical sets when the non-integer parts of "a1" and "a2" are equal, one may impose the restriction without change of meaning. Adding such cosets is done by adding the corresponding real numbers, and subtracting 1 if the result is greater than or equal to 1. The quotient group R/Z is isomorphic to the circle group, the group of complex numbers of absolute value 1 under multiplication, or correspondingly, the group of rotations in 2D about the origin, that is, the special orthogonal group SO(2). An isomorphism is given by (see Euler's identity).
Matrices of real numbers.
If "G" is the group of invertible 3 × 3 real matrices, and "N" is the subgroup of 3 × 3 real matrices with determinant 1, then "N" is normal in "G" (since it is the kernel of the determinant homomorphism). The cosets of "N" are the sets of matrices with a given determinant, and hence "G"/"N" is isomorphic to the multiplicative group of non-zero real numbers. The group "N" is known as the special linear group SL(3).
Integer modular arithmetic.
Consider the abelian group (that is, the set with addition modulo 4), and its subgroup . The quotient group is . This is a group with identity element , and group operations such as . Both the subgroup and the quotient group are isomorphic with Z2.
Integer multiplication.
Consider the multiplicative group formula_39. The set "N" of "n"th residues is a multiplicative subgroup isomorphic to formula_40. Then "N" is normal in "G" and the factor group "G"/"N" has the cosets "N", (1+"n")"N", (1+"n")2N, ..., (1+"n")"n"−1N. The Paillier cryptosystem is based on the conjecture that it is difficult to determine the coset of a random element of "G" without knowing the factorization of "n".
Properties.
The quotient group is isomorphic to the trivial group (the group with one element), and is isomorphic to "G".
The order of , by definition the number of elements, is equal to , the index of "N" in "G". If "G" is finite, the index is also equal to the order of "G" divided by the order of "N". The set may be finite, although both "G" and "N" are infinite (for example, ).
There is a "natural" surjective group homomorphism , sending each element "g" of "G" to the coset of "N" to which "g" belongs, that is: . The mapping "π" is sometimes called the "canonical projection of G onto ". Its kernel is "N".
There is a bijective correspondence between the subgroups of "G" that contain "N" and the subgroups of ; if "H" is a subgroup of "G" containing "N", then the corresponding subgroup of is "π"("H"). This correspondence holds for normal subgroups of "G" and as well, and is formalized in the lattice theorem.
Several important properties of quotient groups are recorded in the fundamental theorem on homomorphisms and the isomorphism theorems.
If "G" is abelian, nilpotent, solvable, cyclic or finitely generated, then so is .
If "H" is a subgroup in a finite group "G", and the order of "H" is one half of the order of "G", then "H" is guaranteed to be a normal subgroup, so exists and is isomorphic to "C"2. This result can also be stated as "any subgroup of index 2 is normal", and in this form it applies also to infinite groups. Furthermore, if "p" is the smallest prime number dividing the order of a finite group, "G", then if has order "p", "H" must be a normal subgroup of "G".
Given "G" and a normal subgroup "N", then "G" is a group extension of by "N". One could ask whether this extension is trivial or split; in other words, one could ask whether "G" is a direct product or semidirect product of "N" and . This is a special case of the extension problem. An example where the extension is not split is as follows: Let "G" = Z4 = {0, 1, 2, 3}, and "N" = {0, 2}, which is isomorphic to Z2. Then is also isomorphic to Z2. But Z2 has only the trivial automorphism, so the only semi-direct product of "N" and is the direct product. Since Z4 is different from , we conclude that "G" is not a semi-direct product of "N" and .
Quotients of Lie groups.
If "formula_41" is a Lie group and "formula_42" is a normal and closed (in the topological rather than the algebraic sense of the word) Lie subgroup of "formula_41", the quotient is also a Lie group. In this case, the original group "formula_41" has the structure of a fiber bundle (specifically, a principal "formula_42"-bundle), with base space and fiber "formula_42". The dimension of equals formula_47.
Note that the condition that "formula_42" is closed is necessary. Indeed, if "formula_42" is not closed then the quotient space is not a T1-space (since there is a coset in the quotient which cannot be separated from the identity by an open set), and thus not a Hausdorff space.
For a non-normal Lie subgroup "formula_42", the space of left cosets is not a group, but simply a differentiable manifold on which "formula_41" acts. The result is known as a homogeneous space.


Vector calculus

Vector calculus, or vector analysis, is concerned with differentiation and integration of vector fields, primarily in 3-dimensional Euclidean space formula_1 The term "vector calculus" is sometimes used as a synonym for the broader subject of multivariable calculus, which spans vector calculus as well as partial differentiation and multiple integration. Vector calculus plays an important role in differential geometry and in the study of partial differential equations. It is used extensively in physics and engineering, especially in the description of
electromagnetic fields, gravitational fields, and fluid flow.
Vector calculus was developed from quaternion analysis by J. Willard Gibbs and Oliver Heaviside near the end of the 19th century, and most of the notation and terminology was established by Gibbs and Edwin Bidwell Wilson in their 1901 book, "Vector Analysis". In the conventional form using cross products, vector calculus does not generalize to higher dimensions, while the alternative approach of geometric algebra which uses exterior products does (see below for more).
Basic objects.
Scalar fields.
A scalar field associates a scalar value to every point in a space. The scalar is a mathematical number representing a physical quantity. Examples of scalar fields in applications include the temperature distribution throughout space, the pressure distribution in a fluid, and spin-zero quantum fields (known as scalar bosons), such as the Higgs field. These fields are the subject of scalar field theory.
Vector fields.
A vector field is an assignment of a vector to each point in a space. A vector field in the plane, for instance, can be visualized as a collection of arrows with a given magnitude and direction each attached to a point in the plane. Vector fields are often used to model, for example, the speed and direction of a moving fluid throughout space, or the strength and direction of some force, such as the magnetic or gravitational force, as it changes from point to point. This can be used, for example, to calculate work done over a line.
Vectors and pseudovectors.
In more advanced treatments, one further distinguishes pseudovector fields and pseudoscalar fields, which are identical to vector fields and scalar fields, except that they change sign under an orientation-reversing map: for example, the curl of a vector field is a pseudovector field, and if one reflects a vector field, the curl points in the opposite direction. This distinction is clarified and elaborated in geometric algebra, as described below.
Vector algebra.
The algebraic (non-differential) operations in vector calculus are referred to as vector algebra, being defined for a vector space and then globally applied to a vector field. The basic algebraic operations consist of:
Also commonly used are the two triple products:
Operators and theorems.
Differential operators.
Vector calculus studies various differential operators defined on scalar or vector fields, which are typically expressed in terms of the del operator (formula_2), also known as "nabla". The three basic vector operators are:
Also commonly used are the two Laplace operators:
A quantity called the Jacobian matrix is useful for studying functions when both the domain and range of the function are multivariable, such as a change of variables during integration.
Integral theorems.
The three basic vector operators have corresponding theorems which generalize the fundamental theorem of calculus to higher dimensions:
In two dimensions, the divergence and curl theorems reduce to the Green's theorem:
Applications.
Linear approximations.
Linear approximations are used to replace complicated functions with linear functions that are almost the same. Given a differentiable function with real values, one can approximate for close to by the formula
The right-hand side is the equation of the plane tangent to the graph of at
Optimization.
For a continuously differentiable function of several real variables, a point "P" (that is, a set of values for the input variables, which is viewed as a point in R"n") is critical if all of the partial derivatives of the function are zero at "P", or, equivalently, if its gradient is zero. The critical values are the values of the function at the critical points.
If the function is smooth, or, at least twice continuously differentiable, a critical point may be either a local maximum, a local minimum or a saddle point. The different cases may be distinguished by considering the eigenvalues of the Hessian matrix of second derivatives.
By Fermat's theorem, all local maxima and minima of a differentiable function occur at critical points. Therefore, to find the local maxima and minima, it suffices, theoretically, to compute the zeros of the gradient and the eigenvalues of the Hessian matrix at these zeros.
Physics and engineering.
Vector calculus is particularly useful in studying:
Generalizations.
Different 3-manifolds.
Vector calculus is initially defined for Euclidean 3-space, formula_4 which has additional structure beyond simply being a 3-dimensional real vector space, namely: a norm (giving a notion of length) defined via an inner product (the dot product), which in turn gives a notion of angle, and an orientation, which gives a notion of left-handed and right-handed. These structures give rise to a volume form, and also the cross product, which is used pervasively in vector calculus.
The gradient and divergence require only the inner product, while the curl and the cross product also requires the handedness of the coordinate system to be taken into account (see cross product and handedness for more detail).
Vector calculus can be defined on other 3-dimensional real vector spaces if they have an inner product (or more generally a symmetric nondegenerate form) and an orientation; note that this is less data than an isomorphism to Euclidean space, as it does not require a set of coordinates (a frame of reference), which reflects the fact that vector calculus is invariant under rotations (the special orthogonal group SO(3)).
More generally, vector calculus can be defined on any 3-dimensional oriented Riemannian manifold, or more generally pseudo-Riemannian manifold. This structure simply means that the tangent space at each point has an inner product (more generally, a symmetric nondegenerate form) and an orientation, or more globally that there is a symmetric nondegenerate metric tensor and an orientation, and works because vector calculus is defined in terms of tangent vectors at each point.
Other dimensions.
Most of the analytic results are easily understood, in a more general form, using the machinery of differential geometry, of which vector calculus forms a subset. Grad and div generalize immediately to other dimensions, as do the gradient theorem, divergence theorem, and Laplacian (yielding harmonic analysis), while curl and cross product do not generalize as directly.
From a general point of view, the various fields in (3-dimensional) vector calculus are uniformly seen as being "k"-vector fields: scalar fields are 0-vector fields, vector fields are 1-vector fields, pseudovector fields are 2-vector fields, and pseudoscalar fields are 3-vector fields. In higher dimensions there are additional types of fields (scalar/vector/pseudovector/pseudoscalar corresponding to 0/1/"n"−1/"n" dimensions, which is exhaustive in dimension 3), so one cannot only work with (pseudo)scalars and (pseudo)vectors.
In any dimension, assuming a nondegenerate form, grad of a scalar function is a vector field, and div of a vector field is a scalar function, but only in dimension 3 or 7 (and, trivially, in dimension 0 or 1) is the curl of a vector field a vector field, and only in 3 or 7 dimensions can a cross product be defined (generalizations in other dimensionalities either require formula_5 vectors to yield 1 vector, or are alternative Lie algebras, which are more general antisymmetric bilinear products). The generalization of grad and div, and how curl may be generalized is elaborated at Curl: Generalizations; in brief, the curl of a vector field is a bivector field, which may be interpreted as the special orthogonal Lie algebra of infinitesimal rotations; however, this cannot be identified with a vector field because the dimensions differ – there are 3 dimensions of rotations in 3 dimensions, but 6 dimensions of rotations in 4 dimensions (and more generally formula_6 dimensions of rotations in "n" dimensions).
There are two important alternative generalizations of vector calculus. The first, geometric algebra, uses "k"-vector fields instead of vector fields (in 3 or fewer dimensions, every "k"-vector field can be identified with a scalar function or vector field, but this is not true in higher dimensions). This replaces the cross product, which is specific to 3 dimensions, taking in two vector fields and giving as output a vector field, with the exterior product, which exists in all dimensions and takes in two vector fields, giving as output a bivector (2-vector) field. This product yields Clifford algebras as the algebraic structure on vector spaces (with an orientation and nondegenerate form). Geometric algebra is mostly used in generalizations of physics and other applied fields to higher dimensions.
The second generalization uses differential forms ("k"-covector fields) instead of vector fields or "k"-vector fields, and is widely used in mathematics, particularly in differential geometry, geometric topology, and harmonic analysis, in particular yielding Hodge theory on oriented pseudo-Riemannian manifolds. From this point of view, grad, curl, and div correspond to the exterior derivative of 0-forms, 1-forms, and 2-forms, respectively, and the key theorems of vector calculus are all special cases of the general form of Stokes' theorem.
From the point of view of both of these generalizations, vector calculus implicitly identifies mathematically distinct objects, which makes the presentation simpler but the underlying mathematical structure and generalizations less clear.
From the point of view of geometric algebra, vector calculus implicitly identifies "k"-vector fields with vector fields or scalar functions: 0-vectors and 3-vectors with scalars, 1-vectors and 2-vectors with vectors. From the point of view of differential forms, vector calculus implicitly identifies "k"-forms with scalar fields or vector fields: 0-forms and 3-forms with scalar fields, 1-forms and 2-forms with vector fields. Thus for example the curl naturally takes as input a vector field or 1-form, but naturally has as output a 2-vector field or 2-form (hence pseudovector field), which is then interpreted as a vector field, rather than directly taking a vector field to a vector field; this is reflected in the curl of a vector field in higher dimensions not having as output a vector field.


Toric stack

In algebraic geometry, a toric stack is a stacky generalization of a toric variety. More precisely, a toric stack is obtained by replacing in the construction of a toric variety a step of taking GIT quotients with that of taking quotient stacks. Consequently, a toric variety is a coarse approximation of a toric stack. A toric orbifold is an example of a toric stack.


Pseudo-abelian category

In mathematics, specifically in category theory, a pseudo-abelian category is a category that is preadditive and is such that every idempotent has a kernel
. Recall that an idempotent morphism formula_1 is an endomorphism of an object with the property that formula_2. Elementary considerations show that every idempotent then has a cokernel. The pseudo-abelian condition is stronger than preadditivity, but it is weaker than the requirement that every morphism have a kernel and cokernel, as is true for abelian categories.
Synonyms in the literature for pseudo-abelian include pseudoabelian and Karoubian.
Examples.
Any abelian category, in particular the category Ab of abelian groups, is pseudo-abelian. Indeed, in an abelian category, "every" morphism has a kernel.
The category of associative rngs (not rings!) together with multiplicative morphisms is pseudo-abelian.
A more complicated example is the category of Chow motives. The construction of Chow motives uses the pseudo-abelian completion described below.
Pseudo-abelian completion.
The Karoubi envelope construction associates to an arbitrary category formula_3 a category formula_4 together with a functor
such that the image formula_6 of every idempotent formula_1 in formula_3 splits in formula_4.
When applied to a preadditive category formula_3, the Karoubi envelope construction yields a pseudo-abelian category formula_4
called the pseudo-abelian completion of formula_3. Moreover, the functor
is in fact an additive morphism.
To be precise, given a preadditive category formula_3 we construct a pseudo-abelian category formula_4 in the following way. The objects of formula_4 are pairs formula_17 where formula_18 is an object of formula_3 and formula_1 is an idempotent of formula_18. The morphisms
in formula_4 are those morphisms
such that formula_25 in formula_3.
The functor
is given by taking formula_18 to formula_29.


Trivial representation

In the mathematical field of representation theory, a trivial representation is a representation of a group "G" on which all elements of "G" act as the identity mapping of "V". A trivial representation of an associative or Lie algebra is a (Lie) algebra representation for which all elements of the algebra act as the zero linear map (endomorphism) which sends every element of "V" to the zero vector.
For any group or Lie algebra, an irreducible trivial representation always exists over any field, and is one-dimensional, hence unique up to isomorphism. The same is true for associative algebras unless one restricts attention to unital algebras and unital representations.
Although the trivial representation is constructed in such a way as to make its properties seem tautologous, it is a fundamental object of the theory. A subrepresentation is equivalent to a trivial representation, for example, if it consists of invariant vectors; so that searching for such subrepresentations is the whole topic of invariant theory.
The trivial character is the character that takes the value of one for all group elements.


Stacky curve

In mathematics, a stacky curve is an object in algebraic geometry that is roughly an algebraic curve with potentially "fractional points" called stacky points. A stacky curve is a type of stack used in studying Gromov–Witten theory, enumerative geometry, and rings of modular forms.
Stacky curves are deeply related to 1-dimensional orbifolds and therefore sometimes called orbifold curves or orbicurves.
Definition.
A stacky curve formula_1 over a field is a smooth proper geometrically connected Deligne–Mumford stack of dimension 1 over that contains a dense open subscheme.
Properties.
A stacky curve is uniquely determined (up to isomorphism) by its coarse space (a smooth quasi-projective curve over ), a finite set of points (its stacky points) and integers (its ramification orders) greater than 1. The canonical divisor of formula_1 is linearly equivalent to the sum of the canonical divisor of and a ramification divisor :
Letting be the genus of the coarse space , the degree of the canonical divisor of formula_1 is therefore:
A stacky curve is called spherical if is positive, Euclidean if is zero, and hyperbolic if is negative.
Although the corresponding statement of Riemann–Roch theorem does not hold for stacky curves, there is a generalization of Riemann's existence theorem that gives an equivalence of categories between the category of stacky curves over the complex numbers and the category of complex orbifold curves.
Applications.
The generalization of GAGA for stacky curves is used in the derivation of algebraic structure theory of rings of modular forms.
The study of stacky curves is used extensively in equivariant Gromov–Witten theory and enumerative geometry.


Prehomogeneous vector space

In mathematics, a prehomogeneous vector space (PVS) is a finite-dimensional vector space "V" together with a subgroup "G" of the general linear group GL("V") such that "G" has an open dense orbit in "V". Prehomogeneous vector spaces were introduced by Mikio Sato in 1970 and have many applications in geometry, number theory and analysis, as well as representation theory. The irreducible PVS were classified by Sato and Tatsuo Kimura in 1977, up to a transformation known as "castling". They are subdivided into two types, according to whether the semisimple part of "G" acts prehomogeneously or not. If it doesn't then there is a homogeneous polynomial on "V" which is invariant under the semisimple part of "G".
Setting.
In the setting of Sato, "G" is an algebraic group and "V" is a rational representation of "G" which has a (nonempty) open orbit in the Zariski topology. However, PVS can also be studied from the point of view of Lie theory: for instance, in Knapp (2002), "G" is a complex Lie group and "V" is a holomorphic representation of "G" with an open dense orbit. The two approaches are essentially the same, and the theory has validity over the real numbers. We assume, for simplicity of notation, that the action of "G" on "V" is a faithful representation. We can then identify "G" with its image in GL("V"), although in practice it is sometimes convenient to let "G" be a covering group.
Although prehomogeneous vector spaces do not necessarily decompose into direct sums of irreducibles, it is natural to study the irreducible PVS (i.e., when "V" is an irreducible representation of "G"). In this case, a theorem of Élie Cartan shows that
is a reductive group, with a centre that is at most one-dimensional. This, together with the obvious dimensional restriction
is the key ingredient in the Sato–Kimura classification.
Castling.
The classification of PVS is complicated by the following fact. Suppose "m" > "n" > 0 and "V" is an "m"-dimensional representation of "G" over a field F. Then:
The proof is to observe that both conditions are equivalent to there being an open dense orbit of the action of "G" on the Grassmannian of
"n"-planes in "V", because this is isomorphic to the Grassmannian of ("m"-"n")-planes in "V"*.
This transformation of PVS is called castling. Given a PVS "V", a new PVS can be obtained by tensoring "V" with F and castling. By repeating this process, and regrouping tensor products, many new examples can be obtained, which are said to be "castling-equivalent". Thus PVS can be grouped into castling equivalence classes. Sato and Kimura show that in each such class, there is essentially one PVS of minimal dimension, which they call "reduced", and they classify the reduced irreducible PVS.
Classification.
The classification of irreducible reduced PVS ("G","V") splits into two cases: those for which "G" is semisimple, and those for which it is reductive with one-dimensional centre. If "G" is semisimple, it is (perhaps a covering of) a subgroup of SL("V"), and hence "G"×GL(1) acts prehomogenously on "V", with one-dimensional centre. We exclude such trivial extensions of semisimple PVS from the PVS with one-dimensional center. In other words, in the case that "G" has one-dimensional center, we assume that the semisimple part does "not" act prehomogeneously; it follows that there is a "relative invariant", i.e., a function invariant under the semisimple part of "G", which is homogeneous of a certain degree "d".
This makes it possible to restrict attention to semisimple "G" ≤ SL("V") and split the classification as follows:
However, it turns out that the classification is much shorter, if one allows not just products with GL(1), but also with SL("n") and GL("n"). This is quite natural in terms of the castling transformation discussed previously. Thus we wish to classify irreducible reduced PVS in terms of semisimple "G" ≤ SL("V") and "n" ≥ 1 such that either:
In the latter case, there is a homogeneous polynomial which separates the "G"×GL("n") orbits into "G"×SL(n) orbits.
This has an interpretation in terms of the grassmannian Gr"n"("V") of "n"-planes in "V" (at least for "n" ≤ dim "V"). In both cases "G" acts on Gr"n"("V") with a dense open orbit "U". In the first case the complement Gr"n"("V")-"U" has codimension ≥ 2; in the second case it is a divisor of some degree "d", and the relative invariant is a homogeneous polynomial of degree "nd".
In the following, the classification list will be presented over the complex numbers.
Irregular examples.
Type 1
Type 2
Both of these examples are PVS only for "n"=1.
Remaining examples.
The remaining examples are all type 2. To avoid discussing the finite groups appearing, the lists present the Lie algebra of the isotropy group rather than the isotropy group itself.
Here formula_8 denotes the space of 3-forms whose contraction with the given symplectic form is zero.
Proofs.
Sato and Kimura establish this classification by producing a list of possible irreducible prehomogeneous ("G","V"), using the fact that "G" is reductive and the dimensional restriction. They then check whether each member of this list is prehomogeneous or not.
However, there is a general explanation why most of the pairs ("G","V") in the classification are prehomogeneous, in terms of isotropy representations of generalized flag varieties. Indeed, in 1974, Richardson observed that if "H" is a semisimple Lie group with a parabolic subgroup "P", then the action of "P" on the nilradical formula_9 of its Lie algebra has a dense open orbit. This shows in particular (and was noted independently by Vinberg in 1975) that the Levi factor "G" of "P" acts prehomogeneously on formula_10. Almost all of the examples in the classification can be obtained by applying this construction with "P" a maximal parabolic subgroup of a simple Lie group "H": these are classified by connected Dynkin diagrams with one distinguished node.
Applications.
One reason that PVS are interesting is that they classify generic objects that arise in "G"-invariant situations. For example, if "G"=GL(7), then the above tables show that there are generic 3-forms under the action of "G", and the stabilizer of such a 3-form is isomorphic to the exceptional Lie group G2.
Another example concerns the prehomogeneous vector spaces with a cubic relative invariant. By the Sato-Kimura classification, there are essentially four such examples, and they all come from complexified isotropy representations of hermitian symmetric spaces for a larger group "H" (i.e., "G" is the semisimple part of the stabilizer of a point, and "V" is the corresponding tangent representation).
In each case a generic point in "V" identifies it with the complexification of a Jordan algebra of 3 x 3 hermitian matrices (over the division algebras R, C, H and O respectively) and the cubic relative invariant is identified with a suitable determinant. The isotropy algebra of such a generic point, the Lie algebra of "G" and the Lie algebra of "H" give the complexifications of the first three rows of the Freudenthal magic square.
Other Hermitian symmetric spaces yields prehomogeneous vector spaces whose generic points define Jordan algebras in a similar way.
The Jordan algebra "J"("m"−1) in the last row is the spin factor (which is the vector space R"m"−1 ⊕ R, with a Jordan algebra structure defined using the inner product on R"m"−1). It reduces to formula_11 for "m"= 3, 4, 6 and 10 respectively.
The relation between hermitian symmetric spaces and Jordan algebras can be explained using Jordan triple systems.


Bernhard Keller

Bernhard Keller (born 1962) is a Swiss mathematician, specializing in algebra. He is a professor at the University of Paris.
Keller received in 1990 his PhD from the University of Zurich under Pierre Gabriel with the thesis "On Derived Categories".
His research is in homological algebra and the representation theory of quivers and finite-dimensional algebras. He has applied triangulated Calabi-Yau categories to the (additive) categorification
of cluster algebras.
In 2013, he received an honorary degree from the University of Antwerp.
In 2014 he received the Sophie Germain Prize.
He was an Invited Speaker at the International Congress of Mathematicians in Madrid in 2006,
with a talk "On differential graded categories."
Keller is a fellow of the American Mathematical Society.


Wedge product


Eulerian poset

In combinatorial mathematics, an Eulerian poset is a graded poset in which every nontrivial interval has the same number of elements of even rank as of odd rank. An Eulerian poset which is a lattice is an Eulerian lattice. These objects are named after Leonhard Euler. Eulerian lattices generalize face lattices of convex polytopes and much recent research has been devoted to extending known results from polyhedral combinatorics, such as various restrictions on "f"-vectors of convex simplicial polytopes, to this more general setting.


Coefficient matrix

In linear algebra, a coefficient matrix is a matrix consisting of the coefficients of the variables in a set of linear equations. The matrix is used in solving systems of linear equations.
Coefficient matrix.
In general, a system with "m" linear equations and "n" unknowns can be written as
where formula_2 are the unknowns and the numbers formula_3 are the coefficients of the system. The coefficient matrix is the "m" × "n" matrix with the coefficient formula_4 as the ("i", "j")th entry:
Then the above set of equations can be expressed more succinctly as
where "A" is the coefficient matrix and b is the column vector of constant terms.
Relation of its properties to properties of the equation system.
By the Rouché–Capelli theorem, the system of equations is inconsistent, meaning it has no solutions, if the rank of the augmented matrix (the coefficient matrix augmented with an additional column consisting of the vector b) is greater than the rank of the coefficient matrix. If, on the other hand, the ranks of these two matrices are equal, the system must have at least one solution. The solution is unique if and only if the rank "r" equals the number "n" of variables. Otherwise the general solution has "n" – "r "free parameters; hence in such a case there are an infinitude of solutions, which can be found by imposing arbitrary values on "n" – "r" of the variables and solving the resulting system for its unique solution; different choices of which variables to fix, and different fixed values of them, give different system solutions.
Dynamic equations.
A first-order matrix difference equation with constant term can be written as
where "A" is "n" × "n" and y and c are "n" × 1. This system converges to its steady-state level of "y" if and only if the absolute values of all "n" eigenvalues of "A" are less than 1.
A first-order matrix differential equation with constant term can be written as
This system is stable if and only if all "n" eigenvalues of "A" have negative real parts.


C. S. Seshadri

Conjeevaram Srirangachari Seshadri FRS (29 February 1932 – 17 July 2020) was an Indian mathematician. He was the founder and director-emeritus of the Chennai Mathematical Institute, and is known for his work in algebraic geometry. The Seshadri constant is named after him.
He was a recipient of the Padma Bhushan in 2009, the third highest civilian honor in the country.
Degrees and posts.
He received his B.A. (Hons) degree in Mathematics from Madras University in 1953 and was mentored by Fr. Racine (born 1897 in France - died 1976 in India; Fr. means Father as he was a Jesuit priest, his first name was Charles) and S Naryanan there. He completed his PhD from Bombay University in 1958 under the supervision of K. S. Chandrasekharan. He was elected Fellow of the Indian Academy of Sciences in 1971.
He also served on the Mathematical Sciences jury for the Infosys Prize in 2010 and 2011.
Seshadri worked in the School of Mathematics at TIFR in Bombay from 1953 to 1984 starting as a Research Scholar and rising to a senior professor. From 1984 to 1989, he worked in IMSc in Chennai. From 1989 to 2010, he worked as the founding director of the Chennai Mathematical Institute. He stepped down from his Directorship of the Chennai Mathematical Institute in December 2010, and continued to be a part of CMI as "Director-Emeritus" till his death in 2020.
Visiting professorships.
He has given talks at the ICM.
Research work.
Seshadri's main work was in algebraic geometry. His work with M S Narasimhan on unitary vector bundles and the Narasimhan–Seshadri theorem has influenced the field. His work on Geometric Invariant Theory and on Schubert varieties, in particular his introduction of standard monomial theory, is widely recognized. Seshadri's contributions include the creation of the Chennai Mathematical Institute, an institute for the study of mathematics in India.


Pseudo-canonical variety

In mathematics, a pseudo-canonical variety is an algebraic variety of "general type".
Formal definition.
Formally, a variety "X" is pseudo-canonical if the canonical class is pseudo-ample.
Results.
For a non-singular projective variety, a result of Kodaira states that this is equivalent to a divisor in the class being the sum of an ample divisor and an effective divisor.


Mihnea Popa

Mihnea Popa (born 11 August 1973) is a Romanian-American mathematician at Harvard University, specializing in algebraic geometry. He is known for his work on complex birational geometry, Hodge theory, abelian varieties, and vector bundles.
Academic career.
Popa received his bachelor's degree in 1996 from the University of Bucharest. He studied mathematics at the University of California, Los Angeles from 1996 to 1997, and then in 2001 he received his Ph.D. from the University of Michigan under the supervision of Robert Lazarsfeld. His thesis was titled "Linear Series on Moduli Spaces of Vector Bundles on Curves". From 2001 to 2005, Popa was a Benjamin Peirce Assistant Professor at Harvard University and from 2005 to 2007 an assistant professor at the University of Chicago. He joined the University of Illinois at Chicago as an associate professor in 2007 and became a full professor in 2011. In 2014 he moved to Northwestern University, and in 2020 he became a professor at Harvard University.
Awards and honors.
Popa is an honorary member of the Institute of Mathematics of the Romanian Academy. He was an AMS Centennial Fellow in 2005–2007, a Sloan Research Fellow in 2007–2009, and a Simons Fellow in 2015–2016. In 2015 he became a fellow of the American Mathematical Society. In 2018 he was an Invited Speaker at the International Congress of Mathematicians in Rio de Janeiro.


Noncommutative measure and integration

Noncommutative measure and integration refers to the theory of weights, states, and traces on von Neumann algebras (Takesaki 1979 v. 2 p. 141).


Square root of a 2 by 2 matrix

A square root of a 2×2 matrix "M" is another 2×2 matrix "R" such that "M" = "R"2, where "R"2 stands for the matrix product of "R" with itself. In general, there can be zero, two, four, or even an infinitude of square-root matrices. In many cases, such a matrix "R" can be obtained by an explicit formula.
Square roots that are not the all-zeros matrix come in pairs: if "R" is a square root of "M", then −"R" is also a square root of "M", since (−"R")(−"R") = (−1)(−1)("RR") = "R"2 = "M". A 2×2 matrix with two distinct nonzero eigenvalues has four square roots. A positive-definite matrix has precisely one positive-definite square root.
A general formula.
The following is a general formula that applies to almost any 2 × 2 matrix. Let the given matrix be
where "A", "B", "C", and "D" may be real or complex numbers. Furthermore, let "τ" = "A" + "D" be the trace of "M", and "δ" = "AD" − "BC" be its determinant. Let "s" be such that "s"2 = "δ", and "t" be such that "t"2 = "τ" + 2"s". That is,
Then, if "t" ≠ 0, a square root of "M" is
Indeed, the square of "R" is
Note that "R" may have complex entries even if "M" is a real matrix; this will be the case, in particular, if the determinant "δ" is negative.
The general case of this formula is when "δ" is nonzero, and "τ"2 ≠ 4"δ", in which case "s" is nonzero, and "t" is nonzero for each choice of sign of "s". Then the formula above will provide four distinct square roots "R", one for each choice of signs for "s" and "t".
Special cases of the formula.
If the determinant "δ" is zero, but the trace "τ" is nonzero, the general formula above will give only two distinct solutions, corresponding to the two signs of "t". Namely,
where "t" is any square root of the trace "τ".
The formula also gives only two distinct solutions if "δ" is nonzero, and "τ"2 = 4"δ" (the case of duplicate eigenvalues), in which case one of the choices for "s" will make the denominator "t" be zero. In that case, the two roots are
where "s" is the square root of "δ" that makes "τ" − 2"s" nonzero, and "t" is any square root of "τ" − 2"s".
The formula above fails completely if "δ" and "τ" are both zero; that is, if "D" = −"A", and "A"2 = −"BC", so that both the trace and the determinant of the matrix are zero. In this case, if "M" is the null matrix (with "A" = "B" = "C" = "D" = 0), then the null matrix is also a square root of "M", as is any matrix
where "b" and "c" are arbitrary real or complex values. Otherwise "M" has no square root.
Formulas for special matrices.
Idempotent matrix.
If "M" is an idempotent matrix, meaning that "MM" = "M", then if it is not the identity matrix, its determinant is zero, and its trace equals its rank, which (excluding the zero matrix) is 1. Then the above formula has "s" = 0 and "τ" = 1, giving "M" and −"M" as two square roots of "M".
Exponential matrix.
If the matrix "M" can be expressed as real multiple of the exponent of some matrix "A", formula_8, then two of its square roots are formula_9. In this case the square root is real.
Diagonal matrix.
If "M" is diagonal (that is, "B" = "C" = 0), one can use the simplified formula
where "a" = ±√"A", and "d" = ±√"D". This, for the various sign choices, gives four, two, or one distinct matrices, if none of, only one of, or both "A" and "D" are zero, respectively.
Identity matrix.
Because it has duplicate eigenvalues, the 2×2 identity matrix formula_11 has infinitely many symmetric rational square roots given by
where are any complex numbers such that formula_13
Matrix with one off-diagonal zero.
If "B" is zero, but "A" and "D" are not both zero, one can use
This formula will provide two solutions if "A" = "D" or "A" = 0 or "D" = 0, and four otherwise. A similar formula can be used when "C" is zero, but "A" and "D" are not both zero.


Lattice word

In mathematics, a lattice word (or lattice permutation) is a string composed of positive integers, in which every prefix contains at least as many positive integers "i" as integers "i" + 1.
A reverse lattice word, or Yamanouchi word, is a string whose reversal is a lattice word.
Examples.
For instance, 11122121 is a lattice permutation, so 12122111 is a Yamanouchi word, but 12122111 is not a lattice permutation, since the sub-word 12122 contains more two's than one's.


Category of chain complexes


2-transitive group

A 2-transitive group is a transitive group used in group theory in which the stabilizer subgroup of every point acts transitively on the remaining points. Equivalently, a group formula_1 acts 2-transitively on a set formula_2 if it acts transitively on the set of distinct ordered pairs formula_3. That is, assuming (without a real loss of generality) that formula_1 acts on the left of formula_2, for each pair of pairs formula_6 with formula_7 and formula_8, there exists a formula_9 such that formula_10. Equivalently, formula_11 and formula_12, since the induced action on the distinct set of pairs is formula_13.
Classifications of 2-transitive groups.
Every 2-transitive group is a primitive group, but not conversely. Every Zassenhaus group is 2-transitive, but not conversely. The solvable 2-transitive groups were classified by Bertram Huppert and are described in the list of transitive finite linear groups. The insoluble groups were classified by using the classification of finite simple groups and are all almost simple groups.


Reality structure

In mathematics, a reality structure on a complex vector space "V" is a decomposition of "V" into two real subspaces, called the real and imaginary parts of "V":
Here "V"R is a real subspace of "V", i.e. a subspace of "V" considered as a vector space over the real numbers. If "V" has complex dimension "n" (real dimension 2"n"), then "V"R must have real dimension "n".
The standard reality structure on the vector space formula_2 is the decomposition
In the presence of a reality structure, every vector in "V" has a real part and an imaginary part, each of which is a vector in "V"R:
In this case, the complex conjugate of a vector "v" is defined as follows:
This map formula_6 is an antilinear involution, i.e.
Conversely, given an antilinear involution formula_8 on a complex vector space "V", it is possible to define a reality structure on "V" as follows. Let
and define
Then
This is actually the decomposition of "V" as the eigenspaces of the real linear operator "c". The eigenvalues of "c" are +1 and −1, with eigenspaces "V"R and formula_12 "V"R, respectively. Typically, the operator "c" itself, rather than the eigenspace decomposition it entails, is referred to as the reality structure on "V".


Henselian ring

In mathematics, a Henselian ring (or Hensel ring) is a local ring in which Hensel's lemma holds. They were introduced by , who named them after Kurt Hensel. Azumaya originally allowed Henselian rings to be non-commutative, but most authors now restrict them to be commutative.
Some standard references for Hensel rings are , , and .
Definitions.
In this article rings will be assumed to be commutative, though there is also a theory of non-commutative Henselian rings.
A local ring "R" with maximal ideal "m" is called Henselian if Hensel's lemma holds. This means that if "P" is a monic polynomial in "R"["x"], then any factorization of its image "P" in ("R"/"m")["x"] into a product of coprime monic polynomials can be lifted to a factorization in "R"["x"].
A local ring is Henselian if and only if every finite ring extension is a product of local rings.
A Henselian local ring is called strictly Henselian if its residue field is separably closed.
A field with valuation is said to be Henselian if its valuation ring is Henselian.
A ring is called Henselian if it is a direct product of a finite number of Henselian local rings.
Henselian rings in algebraic geometry.
Henselian rings are the local rings of "points" with respect to the Nisnevich topology, so the spectra of these rings do not admit non-trivial connected coverings with respect to the Nisnevich topology. Likewise strict Henselian rings are the local rings of geometric points in the étale topology.
Henselization.
For any local ring "A" there is a universal Henselian ring "B" generated by "A", called the Henselization of "A", introduced by , such that any local homomorphism from "A" to a Henselian ring can be extended uniquely to "B". The Henselization of "A" is unique up to unique isomorphism. The Henselization of "A" is an algebraic substitute for the completion of "A". The Henselization of "A" has the same completion and residue field as "A" and is a flat module over "A". If "A" is Noetherian, reduced, normal, regular, or excellent then so is its Henselization. For example, the Henselization of the ring of polynomials "k"["x","y"...] localized at the point (0,0...) is the ring of algebraic formal power series (the formal power series satisfying an algebraic equation). This can be thought of as the "algebraic" part of the completion.
Similarly there is a strictly Henselian ring generated by "A", called the strict Henselization of "A". The strict Henselization is not quite universal: it is unique, but only up to non-unique isomorphism. More precisely it depends on the choice of a separable algebraic closure of the residue field of "A", and automorphisms of this separable algebraic closure correspond to automorphisms of the corresponding strict Henselization. For example, a strict Henselization of the field of "p"-adic numbers is given by the maximal unramified extension, generated by all roots of unity of order prime to "p". It is not "universal" as it has non-trivial automorphisms.


Stanley decomposition

In commutative algebra, a Stanley decomposition is a way of writing a ring in terms of polynomial subrings. They were introduced by .
Definition.
Suppose that a ring "R" is a quotient of a polynomial ring "k"["x"1...] over a field by some ideal. A Stanley decomposition of "R" is a representation of "R" as a direct sum (of vector spaces)
where each "x""α" is a monomial and each "X""α" is a finite subset of the generators.


Analytically unramified ring

In algebra, an analytically unramified ring is a local ring whose completion is reduced (has no nonzero nilpotent).
The following rings are analytically unramified:
 showed that every local ring of an algebraic variety is analytically unramified.
 gave an example of an analytically ramified reduced local ring. showed that every 1-dimensional normal Noetherian local ring is analytically unramified; more precisely he showed that a 1-dimensional normal Noetherian local domain is analytically unramified if and only if its integral closure is a finite module. This prompted to ask whether a local Noetherian domain such that its integral closure is a finite module is always analytically unramified. However gave an example of a 2-dimensional normal analytically ramified Noetherian local ring. Nagata also showed that a slightly stronger version of Zariski's question is correct: if the normalization of every finite extension of a given Noetherian local ring "R" is a finite module, then "R" is analytically unramified.
There are two classical theorems of that characterize analytically unramified rings. The first says that a Noetherian local ring ("R", "m") is analytically unramified if and only if there are a "m"-primary ideal "J" and a sequence formula_1 such that formula_2, where the bar means the integral closure of an ideal. The second says that a Noetherian local domain is analytically unramified if and only if, for every finitely-generated "R"-algebra "S" lying between "R" and the field of fractions "K" of "R", the integral closure of "S" in "K" is a finitely generated module over "S". The second follows from the first.
Nagata's example.
Let "K"0 be a perfect field of characteristic 2, such as F2.
Let "K" be "K"0({"u""n", "v""n" : "n" ≥ 0}), where the "u""n" and "v""n" are indeterminates.
Let "T" be the subring of the formal power series ring "K"  generated by "K" and "K""2"  and the element ∑("u""n""x""n"+ "v""n""y""n"). Nagata proves that "T" is a normal local noetherian domain whose completion has nonzero nilpotent elements, so "T" is analytically ramified.


Complex Hadamard matrix

A complex Hadamard matrix is any complex
formula_1 matrix formula_2 satisfying two conditions:
where formula_5 denotes the Hermitian transpose of formula_2 and formula_7 is the identity matrix. The concept is a generalization of the Hadamard matrix. Note that any complex Hadamard matrix formula_2 can be made into a unitary matrix by multiplying it by formula_9; conversely, any unitary matrix whose entries all have modulus formula_9 becomes a complex Hadamard upon multiplication by formula_11.
Complex Hadamard matrices arise in the study of operator algebras and the theory of quantum computation. Real Hadamard matrices and Butson-type Hadamard matrices form particular cases of complex Hadamard matrices.
Complex Hadamard matrices exist for any natural formula_12 (compare the real case, in which existence is not known for every formula_12). For instance the Fourier matrices (the complex conjugate of the DFT matrices without the normalizing factor),
belong to this class.
Equivalency.
Two complex Hadamard matrices are called equivalent, written formula_15, if there exist diagonal unitary matrices formula_16 and permutation matrices formula_17
such that
Any complex Hadamard matrix is equivalent to a dephased Hadamard matrix, in which all elements in the first row and first column are equal to unity.
For formula_19 and formula_20 all complex Hadamard matrices are equivalent to the Fourier matrix formula_21. For formula_22 there exists
a continuous, one-parameter family of inequivalent complex Hadamard matrices,
For formula_24 the following families of complex Hadamard matrices
are known:
It is not known, however, if this list is complete, but it is conjectured that formula_36 is an exhaustive (but not necessarily irredundant) list of all complex Hadamard matrices of order 6.


Wei Zhang (mathematician)

Wei Zhang (; born 1981) is a Chinese mathematician specializing in number theory. He is currently a Professor of Mathematics at the Massachusetts Institute of Technology.
Education.
Zhang grew up in Sichuan province in China and attended Chengdu No.7 High School. He earned his B.S. in Mathematics from Peking University in 2004 and his Ph.D. from Columbia University in 2009 under the supervision of Shou-Wu Zhang.
Career.
Zhang was a postdoctoral researcher and Benjamin Peirce Fellow at Harvard University from 2009 to 2011. He was a member of the mathematics faculty at Columbia University from 2011 to 2017, initially as an assistant professor before becoming a full professor in 2015. He has been a full professor at the Massachusetts Institute of Technology since 2017.
Work.
His collaborations with Zhiwei Yun, Xinyi Yuan and Xinwen Zhu have received attention in publications such as Quanta Magazine and Business Insider. In particular, his work with Zhiwei Yun on the Taylor expansion of L-functions is "already being hailed as one of the most exciting breakthroughs in an important area of number theory in the last 30 years."
Zhang has also made substantial contributions to the global Gan–Gross–Prasad conjecture.
Awards.
He was a recipient of the SASTRA Ramanujan Prize in 2010, for "far-reaching contributions by himself and in collaboration with others to a broad range of areas in mathematics, including number theory, automorphic forms, L-functions, trace formulas, representation theory, and algebraic geometry.” In 2013, Zhang received a Sloan Research Fellowship; in 2016 Zhang was awarded the Morningside Gold Medal of Mathematics. In December 2017 he was awarded 2018 New Horizons In Mathematics Prize together with Zhiwei Yun, Aaron Naber and Maryna Viazovska. In 2019 he received the Clay Research Award.
He was included in the 2019 class of fellows of the American Mathematical Society "for contributions to number theory, algebraic geometry and geometric representation theory".


Symmetric variety

In algebraic geometry, a symmetric variety is an algebraic analogue of a symmetric space in differential geometry, given by a quotient "G"/"H" of a reductive algebraic group "G" by the subgroup "H" fixed by some involution of "G".


Margarethe Kahn

Margarethe Kahn (known as Grete Kahn, also Margarete Kahn, born 27 August 1880, missing after deportation to Piaski, Poland on 28 March 1942) was a German mathematician and Holocaust victim. She was among the first women to obtain a doctorate in Germany. Her doctoral work was on the topology of algebraic curves.
Life and work.
Margarethe Kahn was the daughter of Eschwege merchant and flannel factory owner Albert Kahn (1853–1905) and his wife Johanne (née Plaut, 1857–1882). She had an older brother Otto (1879–1932). Five years after the untimely death of his wife Johanne, their father married her younger sister Julie (1860–1934), with whom he had a daughter, Margaret's half-sister Martha (1888–1942).
After attending elementary school from 1887, and the Higher School for Girls from 1889 to 1896, Kahn until 1904 took private lessons to prepare for her "Abitur", because few high schools for girls existed at that time in Hesse, Germany. In 1904 she was given permission to take her "Abitur" at the Royal "Gymnasium" in Bad Hersfeld. Thus she belonged to the small elite of young women in Germany at the beginning of the 20th century who were allowed to take the "Abitur" externally at boys' schools. Konrad Duden signed her "Abitur" certificate as school principal.
Since Prussia began to allow women to formally attend university only from the winter semester of 1908–09, Kahn and her friend Klara Löbenstein first attended the universities of Berlin and Göttingen as guest students. In addition, Kahn attended lectures and tutorials in mathematics at the Technical University of Berlin. They studied mathematics, physics, and propaedeutics at Berlin and Göttingen. At the University of Göttingen she attended lectures given by, among others, David Hilbert, Felix Klein, Woldemar Voigt, and Georg Elias Müller; in Berlin she attended lectures by Hermann Amandus Schwarz and Paul Drude at the Royal Prussian Academy of Sciences. Her field of expertise was algebraic geometry. Together with Löbenstein she made a contribution to Hilbert's sixteenth problem. Hilbert's sixteenth problem concerned the topology of algebraic curves in the complex projective plane; as a difficult special case in his formulation of the problem Hilbert proposed that there are no algebraic curves of degree 6 consisting of 11 separate ovals. Kahn and Löbenstein developed methods to address this problem.
Against opposition in particular from the Berlin faculty, but supported by the University of Göttingen and Felix Klein, Kahn obtained a doctorate in 1909 under David Hilbert in Göttingen, with a dissertation titled "Eine allgemeine Methode zur Untersuchung der Gestalten algebraischer Kurven" [A general method to investigate the shapes of algebraic curves] and was therefore one of the first German women to obtain a doctorate in mathematics (the mathematics division was part of the faculty of philosophy then). She took her oral examination – again, along with Löbenstein – on 30 June 1909.
Kahn could not pursue a scientific career because women in Germany were not admitted to habilitation before 1920. She therefore sought a career as a schoolteacher, and in October 1912 she obtained a job in the Prussian school system, where she worked as a teacher for secondary schools in Katowice, Dortmund, and from 1929, in Berlin-Tegel at today's Gabriele-von-Bülow-Gymnasium and later in Berlin-Pankow at today's Carl-von-Ossietzky-Gymnasium.
As a Jew, she was forced to go on leave by the Nazis in 1933, and was dismissed from the school in 1936. She was forced to work as a factory worker at the "Nordland Schneeketten" (Nordland snow chains) factory. On 28 March 1942, Kahn and her by then widowed sister Martha were deported to Piaski and are considered missing since then.
On 13 September 2008, a "Stolperstein" was laid at 127 "Rudolstädter Straße" in Wilmersdorf in memory of Margarethe Kahn, as well as on 26 May 2010 in front of her parents' former house at Stad 29 in Eschwege, where additionally a commemorative plaque was attached on 13 December 2017. In 2013, a street in Leverkusen was named after her.


Combinatorial species

In combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for deriving the generating functions of discrete structures, which allows one to not merely count these structures but give bijective proofs involving them. Examples of combinatorial species are (finite) graphs, permutations, trees, and so on; each of these has an associated generating function which counts how many structures there are of a certain size. One goal of species theory is to be able to analyse complicated structures by describing them in terms of transformations and combinations of simpler structures. These operations correspond to equivalent manipulations of generating functions, so producing such functions for complicated structures is much easier than with other methods. The theory was introduced, carefully elaborated and applied by the Canadian group of people around André Joyal.
The power of the theory comes from its level of abstraction. The "description format" of a structure (such as adjacency list versus adjacency matrix for graphs) is irrelevant, because species are purely algebraic. Category theory provides a useful language for the concepts that arise here, but it is not necessary to understand categories before being able to work with species.
The category of species is equivalent to the category of symmetric sequences in finite sets.
Definition of species.
Any structure — an instance of a particular species — is associated with some set, and there are often many possible structures for the same set. For example, it is possible to construct several different graphs whose node labels are drawn from the same given set. At the same time, any set could be used to build the structures. The difference between one species and another is that they build a different set of structures out of the same base set.
This leads to the formal definition of a "combinatorial species". Let formula_1 be the category of finite sets, with the morphisms of the category being the bijections between these sets. A "species" is a functor
For each finite set "A" in formula_1, the finite set "F"["A"] is called the set of "F"-structures on "A", or the set of structures of species "F" on "A". Further, by the definition of a functor, if φ is a bijection between sets "A" and "B", then "F"[φ] is a bijection between the sets of "F"-structures "F"["A"] and "F"["B"], called "transport of F-structures along φ".
For example, the "species of permutations" maps each finite set "A" to the set of all permutations of "A", and each bijection from "A" to another set "B" naturally induces a bijection from the set of all permutations of "A" to the set of all permutations of "B". Similarly, the "species of partitions" can be defined by assigning to each finite set the set of all its partitions, and the "power set species" assigns to each finite set its power set. The adjacent diagram shows a structure on a set of five elements: arcs connect the structure (red) to the elements (blue) from which it is built.
Because a bijection exists between two finite sets if and only if the two sets have the same cardinality (the number of elements), for each finite set "A", the cardinality of formula_4, which is finite, depends only on the cardinality of "A". (This follows from the formal definition of a functor.) In particular, the "exponential generating series" "F"("x") of a species "F" can be defined:
where formula_6 is the cardinality of formula_4 for any set "A" having "n" elements; e.g., formula_8.
Some examples: writing formula_9,
Calculus of species.
Arithmetic on generating functions corresponds to certain "natural" operations on species. The basic operations are addition, multiplication, composition, and differentiation; it is also necessary to define equality on species. Category theory already has a way of describing when two functors are equivalent: a natural isomorphism. In this context, it just means that for each "A" there is a bijection between "F"-structures on "A" and "G"-structures on "A", which is "well-behaved" in its interaction with transport. Species with the same generating function might not be isomorphic, but isomorphic species do always have the same generating function.
Addition.
Addition of species is defined by the disjoint union of sets, and corresponds to a choice between structures. For species "F" and "G", define ("F" + "G")["A"] to be the disjoint union (also written "+") of "F"["A"] and "G"["A"]. It follows that ("F" + "G")("x") = "F"("x") + "G"("x"). As a demonstration, take "E"+ to be the species of non-empty sets, whose generating function is "E"+("x") = "e""x" − 1, and 1 the species of the empty set, whose generating function is 1("x") = 1. It follows that "E" = 1 + "E"+: in words, "a set is either empty or non-empty". Equations like this can be read as referring to a single structure, as well as to the entire collection of structures.
The original definition of the species inspired three directions of investigation.
- On the categorical side, ones needs a larger frame to content both the product and coproduct. The price is the loss of the cycle index.
- Another approach brings in the Burnside rings or rigs. The Burnside summation of representations is a formal notation used in the elaboration of marks tables theory.
- Finally, the usual definition does not take into account the functoriality and the fact that a species, even seen as a rule, is unique. For a rule F there isn't the second rule F to produce a disjoint sum F+F. In this approach the definition of summing is actually a definition by example. The advantage is the natural insertion of the cycle index as the power tool.
Multiplication.
Multiplying species is slightly more complicated. It is possible to just take the Cartesian product of sets as the definition, but the combinatorial interpretation of this is not quite right. (See below for the use of this kind of product.) Rather than putting together two unrelated structures on the same set, the multiplication operator uses the idea of splitting the set into two components, constructing an "F"-structure on one and a "G"-structure on the other.
This is a disjoint union over all possible binary partitions of "A". It is straightforward to show that multiplication is associative and commutative (up to isomorphism), and distributive over addition. As for the generating series, ("F" · "G")("x") = "F"("x")"G"("x").
The diagram below shows one possible ("F" · "G")-structure on a set with five elements. The "F"-structure (red) picks up three elements of the base set, and the "G"-structure (light blue) takes the rest. Other structures will have "F" and "G" splitting the set in a different way. The set ("F" · "G")["A"], where "A" is the base set, is the disjoint union of all such structures.
The addition and multiplication of species are the most comprehensive expression of the sum and product rules of counting.
Composition.
Composition, also called substitution, is more complicated again. The basic idea is to replace components of "F" with "G"-structures, forming ("F"∘"G"). As with multiplication, this is done by splitting the input set "A"; the disjoint subsets are given to "G" to make "G"-structures, and the set of subsets is given to "F", to make the "F"-structure linking the "G"-structures. It is required for "G" to map the empty set to itself, in order for composition to work. The formal definition is:
Here, "P" is the species of partitions, so "P"["A"] is the set of all partitions of "A". This definition says that an element of ("F" ∘ "G")["A"] is made up of an "F"-structure on some partition of "A", and a "G"-structure on each component of the partition. The generating series is formula_18.
One such structure is shown below. Three "G"-structures (light blue) divide up the five-element base set between them; then, an "F"-structure (red) is built to connect the "G"-structures.
These last two operations may be illustrated by the example of trees. First, define "X" to be the species "singleton" whose generating series is "X"("x") = "x". Then the species "Ar" of rooted trees (from the French "arborescence") is defined recursively by "Ar" = "X" · "E"("Ar"). This equation says that a tree consists of a single root and a set of (sub-)trees. The recursion does "not" need an explicit base case: it only generates trees in the context of being applied to some finite set. One way to think about this is that the "Ar" functor is being applied repeatedly to a "supply" of elements from the set — each time, one element is taken by "X", and the others distributed by "E" among the "Ar" subtrees, until there are no more elements to give to "E". This shows that algebraic descriptions of species are quite different from type specifications in programming languages like Haskell.
Likewise, the species "P" can be characterised as "P" = "E"("E"+): "a partition is a pairwise disjoint set of nonempty sets (using up all the elements of the input set)". The exponential generating series for "P" is formula_19, which is the series for the Bell numbers.
Differentiation.
Differentiation of species intuitively corresponds to building "structures with a hole", as shown in the illustration below.
Formally,
where formula_21 is some distinguished new element not present in formula_22.
To differentiate the associated exponential series, the sequence of coefficients needs to be shifted one place to the "left" (losing the first term). This suggests a definition for species: "F' "["A"] = "F"["A" + {*}], where {*} is a singleton set and "+" is disjoint union. The more advanced parts of the theory of species use differentiation extensively, to construct and solve differential equations on species and series. The idea of adding (or removing) a single part of a structure is a powerful one: it can be used to establish relationships between seemingly unconnected species.
For example, consider a structure of the species "L" of linear orders—lists of elements of the ground set. Removing an element of a list splits it into two parts (possibly empty); in symbols, this is "L"' = "L"·"L". The exponential generating function of "L" is "L"("x") = 1/(1 − "x"), and indeed:
The species "C" of cyclic permutations takes a set "A" to the set of all cycles on "A". Removing a single element from a cycle reduces it to a list: "C"' = "L". We can integrate the generating function of "L" to produce that for "C".
A nice example of integration of a species is the completion of a line (coordinatizated by a field) with the infinite point and obtaining a projective line.
Further operations.
There are a variety of other manipulations which may be performed on species. These are necessary to express more complicated structures, such as directed graphs or bigraphs.
Pointing selects a single element in a structure. Given a species "F", the corresponding pointed species "F"• is defined by "F"•["A"] = "A" × "F"["A"]. Thus each "F"•-structure is an "F"-structure with one element distinguished. Pointing is related to differentiation by the relation "F"• = "X"·"F' ", so "F"•("x") = "x" "F' "("x"). The species of pointed sets, "E"•, is particularly important as a building block for many of the more complex constructions.
The Cartesian product of two species is a species which can build two structures on the same set at the same time. It is different from the ordinary multiplication operator in that all elements of the base set are shared between the two structures. An ("F" × "G")-structure can be seen as a superposition of an "F"-structure and a "G"-structure. Bigraphs could be described as the superposition of a graph and a set of trees: each node of the bigraph is part of a graph, and at the same time part of some tree that describes how nodes are nested. The generating function ("F" × "G")("x") is the Hadamard or coefficient-wise product of "F"("x") and "G"("x").
The species "E"• × "E"• can be seen as making two independent selections from the base set. The two points might coincide, unlike in "X"·"X"·"E", where they are forced to be different.
As functors, species "F" and "G" may be combined by functorial composition: formula_25 (the box symbol is used, because the circle is already in use for substitution). This constructs an "F"-structure on the set of all "G"-structures on the set "A". For example, if "F" is the functor taking a set to its power set, a structure of the composed species is some subset of the "G"-structures on "A". If we now take "G" to be "E"• × "E"• from above, we obtain the species of directed graphs, with self-loops permitted. (A directed graph is a set of edges, and edges are pairs of nodes: so a graph is a subset of the set of pairs of elements of the node set "A".) Other families of graphs, as well as many other structures, can be defined in this way.
Software.
Operations with species are supported by SageMath and, using a special package, also by Haskell.
Variants.
If “finite sets with bijections” is replaced with “finite vector spaces with linear transformations”, then one gets the notion of polynomial functor (after imposing some finiteness condition).


Posetal category

In mathematics, specifically category theory, a posetal category, or thin category, is a category whose homsets each contain at most one morphism. As such, a posetal category amounts to a preordered class (or a preordered set, if its objects form a set). As suggested by the name, the further requirement that the category be skeletal is often assumed for the definition of "posetal"; in the case of a category that is posetal, being skeletal is equivalent to the requirement that the only isomorphisms are the identity morphisms, equivalently that the preordered class satisfies antisymmetry and hence, if a set, is a poset.
All diagrams commute in a posetal category. When the commutative diagrams of a category are interpreted as a typed equational theory whose objects are the types, a codiscrete posetal category corresponds to an inconsistent theory understood as one satisfying the axiom "x" = "y" at all types.
Viewing a 2-category as an enriched category whose hom-objects are categories, the hom-objects of any extension of a posetal category to a 2-category having the same 1-cells are monoids.
Some lattice-theoretic structures are definable as posetal categories of a certain kind, usually with the stronger assumption of being skeletal. For example, under this assumption, a poset may be defined as a small posetal category, a distributive lattice as a small posetal distributive category, a Heyting algebra as a small posetal finitely cocomplete cartesian closed category, and a Boolean algebra as a small posetal finitely cocomplete *-autonomous category. Conversely, categories, distributive categories, finitely cocomplete cartesian closed categories, and finitely cocomplete *-autonomous categories can be considered the respective categorifications of posets, distributive lattices, Heyting algebras, and Boolean algebras.


Absolute presentation of a group

In mathematics, an absolute presentation is one method of defining a group.
Recall that to define a group formula_1 by means of a presentation, one specifies a set formula_2 of generators so that every element of the group can be written as a product of some of these generators, and a set formula_3 of relations among those generators. In symbols:
Informally formula_1 is the group generated by the set formula_2 such that formula_7 for all formula_8. But here there is a tacit assumption that formula_1 is the "freest" such group as clearly the relations are satisfied in any homomorphic image of formula_1. One way of being able to eliminate this tacit assumption is by specifying that certain words in formula_2 should not be equal to formula_12 That is we specify a set formula_13, called the set of irrelations, such that formula_14 for all formula_15.
Formal definition.
To define an absolute presentation of a group formula_1 one specifies a set formula_2 of generators, a set formula_3 of relations among those generators and a set formula_13 of irrelations among those
generators. We then say formula_1 has absolute presentation
provided that:
A more algebraic, but equivalent, way of stating condition 2 is:
Remark: The concept of an absolute presentation has been fruitful in fields such as algebraically closed groups and the Grigorchuk topology.
In the literature, in a context where absolute presentations are being discussed, a presentation (in the usual sense of the word) is sometimes referred to as a relative presentation, which is an instance of a retronym.
Example.
The cyclic group of order "8" has the presentation
But, up to isomorphism there are three more groups that "satisfy" the relation formula_33 namely:
However none of these satisfy the irrelation formula_37. So an absolute presentation for the cyclic group of order 8 is:
It is part of the definition of an absolute presentation that the irrelations are not satisfied in any proper homomorphic image of the group. Therefore:
Is "not" an absolute presentation for the cyclic group of order 8 because the irrelation formula_40 is satisfied in the cyclic group of order 4.
Background.
The notion of an absolute presentation arises from Bernhard Neumann's study of the isomorphism problem for algebraically closed groups.
A common strategy for considering whether two groups formula_41 and formula_42 are isomorphic is to consider whether a presentation for one might be transformed into a presentation for the other. However algebraically closed groups are neither finitely generated nor recursively presented and so it is impossible to compare their presentations. Neumann considered the following alternative strategy:
Suppose we know that a group formula_41 with finite presentation formula_44 can be embedded in the algebraically closed group formula_45 then given another algebraically closed group formula_46, we can ask "Can formula_41 be embedded in formula_46?"
It soon becomes apparent that a presentation for a group does not contain enough information to make this decision for while there may be a homomorphism formula_49, this homomorphism need not be an embedding. What is needed is a specification for formula_45 that "forces" any homomorphism preserving that specification to be an embedding. An absolute presentation does precisely this.


Artinian ring

In abstract algebra, an Artinian ring (sometimes Artin ring) is a ring that satisfies the descending chain condition on ideals; that is, there is no infinite descending sequence of ideals. Artinian rings are named after Emil Artin, who first discovered that the descending chain condition for ideals simultaneously generalizes finite rings and rings that are finite-dimensional vector spaces over fields. The definition of Artinian rings may be restated by interchanging the descending chain condition with an equivalent notion: the minimum condition.
A ring is left Artinian if it satisfies the descending chain condition on left ideals, right Artinian if it satisfies the descending chain condition on right ideals, and Artinian or two-sided Artinian if it is both left and right Artinian. For commutative rings the left and right definitions coincide, but in general they are distinct from each other.
The Artin–Wedderburn theorem characterizes every simple Artinian ring as a ring of matrices over a division ring. This implies that a simple ring is left Artinian if and only if it is right Artinian.
The same definition and terminology can be applied to modules, with ideals replaced by submodules.
Although the descending chain condition appears dual to the ascending chain condition, in rings it is in fact the stronger condition. Specifically, a consequence of the Akizuki–Hopkins–Levitzki theorem is that a left (resp. right) Artinian ring is automatically a left (resp. right) Noetherian ring. This is not true for general modules; that is, an Artinian module need not be a Noetherian module.
Examples.
The ring of integers formula_8 is a Noetherian ring but is not Artinian.
Modules over Artinian rings.
Let "M" be a left module over a left Artinian ring. Then the following are equivalent (Hopkins' theorem): (i) "M" is finitely generated, (ii) "M" has finite length (i.e., has composition series), (iii) "M" is Noetherian, (iv) "M" is Artinian.
Commutative Artinian rings.
Let "A" be a commutative Noetherian ring with unity. Then the following are equivalent.
Let "k" be a field and "A" finitely generated "k"-algebra. Then "A" is Artinian if and only if "A" is finitely generated as "k"-module.
An Artinian local ring is complete. A quotient and localization of an Artinian ring is Artinian.
Simple Artinian ring.
A simple Artinian ring "A" is a matrix ring over a division ring. Indeed, let "I" be a minimal (nonzero) right ideal of "A". Then, since formula_11 is a two-sided ideal, formula_12 since "A" is simple. Thus, we can choose formula_13 so that formula_14. Assume "k" is minimal with respect that property. Consider the map of right "A"-modules:
It is surjective. If it is not injective, then, say, formula_16 with nonzero formula_17. Then, by the minimality of "I", we have: formula_18. It follows:
which contradicts the minimality of "k". Hence, formula_20 and thus formula_21.


Rybicki Press algorithm

The Rybicki–Press algorithm is a fast direct algorithm for inverting a matrix, whose entries are given by formula_1, where formula_2. It is a computational optimization of a general set of statistical methods developed to determine whether two noisy, irregularly sampled data sets are, in fact, dimensionally shifted representations of the same underlying function. The most common use of the algorithm is in the detection of periodicity in astronomical observations.
Recently, this method has been extended (Generalized Rybicki Press algorithm) for inverting matrices whose entries of the form formula_3. The key observation in the Generalized Rybicki Press (GPP) algorithm is that the matrix formula_4 is a semi-separable matrix with rank formula_5. More precisely, if the matrix formula_6 has a semi-separable rank is formula_5, the cost for solving the linear system formula_8 and obtaining the determinant of the matrix scales as formula_9, thereby making it extremely attractive for large matrices. This implementation of the GPP algorithm can be found here. The key idea is that the dense matrix formula_4 can be converted into a sparser matrix of a larger size (see figure on the right), whose sparsity structure can be leveraged to reduce the computational complexity.
The fact that matrix formula_4 is a semi-separable matrix also forms the basis for library, which is a library for fast and scalable Gaussian Process (GP) Regression in one dimension with implementations in C++, Python, and Julia. The method also provides an algorithm for generating samples from a high-dimensional distribution. The method has found attractive applications in a wide range of fields, especially in astronomical data analysis.


Hierarchical matrix

In numerical mathematics, hierarchical matrices (H-matrices)
are used as data-sparse approximations of non-sparse matrices.
While a sparse matrix of dimension formula_1 can be represented efficiently in formula_2 units of storage
by storing only its non-zero entries, a non-sparse matrix would require formula_3 units of storage, and using this type
of matrices for large problems would therefore be prohibitively expensive in terms of storage and computing time.
Hierarchical matrices provide an approximation requiring only formula_4 units of storage, where formula_5 is a
parameter controlling the accuracy of the approximation.
In typical applications, e.g., when discretizing integral equations
,
preconditioning the resulting systems of linear equations
or solving elliptic partial differential equations
a rank proportional to formula_6 with a small constant formula_7 is sufficient to ensure an
accuracy of formula_8.
Compared to many other data-sparse representations of non-sparse matrices, hierarchical matrices offer a major advantage:
the results of matrix arithmetic operations like matrix multiplication, factorization or inversion can be approximated
in formula_9 operations, where formula_10
Basic idea.
Hierarchical matrices rely on local low-rank approximations:
let formula_11 be index sets, and let formula_12 denote the matrix we have to approximate.
In many applications (see above), we can find subsets formula_13 such that formula_14
can be approximated by a rank-formula_5 matrix.
This approximation can be represented in factorized form formula_16 with factors
formula_17.
While the standard representation of the matrix formula_14 requires formula_19 units of storage,
the factorized representation requires only formula_20 units.
If formula_5 is not too large, the storage requirements are reduced significantly.
In order to approximate the entire matrix formula_22, it is split into a family of submatrices.
Large submatrices are stored in factorized representation, while small submatrices are stored in standard representation
in order to improve efficiency.
Low-rank matrices are closely related to degenerate expansions used in panel clustering and the fast multipole method
to approximate integral operators.
In this sense, hierarchical matrices can be considered the algebraic counterparts of these techniques.
Application to integral operators.
Hierarchical matrices are successfully used to treat integral equations, e.g., the single and double layer potential operators
appearing in the boundary element method.
A typical operator has the form
The Galerkin method leads to matrix entries of the form
where formula_25 and formula_26 are families of finite element basis functions.
If the kernel function formula_27 is sufficiently smooth, we can approximate it by polynomial interpolation to obtain
where formula_29 is the family of interpolation points and formula_30
is the corresponding family of Lagrange polynomials.
Replacing formula_27 by formula_32 yields an approximation
with the coefficients
If we choose formula_13 and use the same interpolation points for all formula_37, we obtain
formula_38.
Obviously, any other approximation separating the variables formula_39 and formula_40, e.g., the multipole expansion,
would also allow us to split the double integral into two single integrals and thus arrive at a similar factorized low-rank matrix.
Of particular interest are cross approximation techniques
that use only the entries of the original matrix formula_22 to construct a low-rank approximation.
Application to elliptic partial differential equations.
Since the solution operator of an elliptic partial differential equation can be expressed as an integral operator involving
Green's function, it is not surprising that the inverse of the stiffness matrix arising from the finite element method
and spectral method
can be approximated by a hierarchical matrix.
Green's function depends on the shape of the computational domain, therefore it is usually not known.
Nevertheless, approximate arithmetic operations can be employed to compute an approximate inverse without knowing the
function explicitly.
Surprisingly, it is possible to prove that the inverse can be approximated even if
the differential operator involves non-smooth coefficients and Green's function is therefore not smooth.
Arithmetic operations.
The most important innovation of the hierarchical matrix method is the development of efficient algorithms for performing
(approximate) matrix arithmetic operations on non-sparse matrices, e.g., to compute approximate inverses, LU decompositions
and solutions to matrix equations.
The central algorithm is the efficient matrix-matrix multiplication, i.e., the computation of formula_42
for hierarchical matrices formula_43 and a scalar factor formula_44.
The algorithm requires the submatrices of the hierarchical matrices to be organized in a block tree structure and takes
advantage of the properties of factorized low-rank matrices to compute the updated formula_45 in
formula_46 operations.
Taking advantage of the block structure, the inverse can be computed by using recursion to compute inverses and
Schur complements of diagonal blocks and combining both using the matrix-matrix multiplication.
In a similar way, the LU decomposition
can be constructed using only recursion and multiplication.
Both operations also require formula_46 operations.
H2-matrices.
In order to treat very large problems, the structure of hierarchical matrices can be improved:
H2-matrices
replace the general low-rank structure of the blocks by a hierarchical representation closely related to the
fast multipole method in order to reduce the storage complexity to formula_48.
In the context of boundary integral operators, replacing the fixed rank formula_5 by block-dependent ranks
leads to approximations that preserve the rate of convergence of the underlying boundary element method
at a complexity of formula_50
Arithmetic operations like multiplication, inversion, and Cholesky or LR factorization of H2-matrices
can be implemented based on two fundamental operations: the matrix-vector multiplication with submatrices
and the low-rank update of submatrices.
While the matrix-vector multiplication is straightforward, implementing efficient low-rank updates with
adaptively optimized cluster bases poses a significant challenge.
Software.
HLib is a C software library implementing the most important algorithms for hierarchical and formula_51-matrices.
AHMED is a C++ software library that can be downloaded for educational purposes.
HLIBpro is an implementation of the core hierarchical matrix algorithms for commercial applications.
H2Lib is an open source implementation of hierarchical matrix algorithms intended for research and teaching.
awesome-hierarchical-matrices is a repository containing a list of other H-Matrices implementations.
HierarchicalMatrices.jl is a Julia package implementing hierarchical matrices.