Multilinear algebra

In mathematics, multilinear algebra extends the methods of linear algebra. Just as linear algebra is built on the concept of a vector and develops the theory of vector spaces, multilinear algebra builds on the concepts of "p"-vectors and multivectors with Grassmann algebra.
Origin.
In a vector space of dimension "n", one usually considers only the vectors. According to Hermann Grassmann and others, this presumption misses the complexity of considering the structures of pairs, triples, and general multivectors. Since there are several combinatorial possibilities, the space of multivectors turns out to have 2"n" dimensions. The abstract formulation of the determinant is the most immediate application. Multilinear algebra also has applications in mechanical study of material response to stress and strain with various moduli of elasticity. This practical reference led to the use of the word tensor to describe the elements of the multilinear space. The extra structure in a multilinear space has led it to play an important role in various studies in higher mathematics. Though Grassmann started the subject in 1844 with his "Ausdehnungslehre", and republished in 1862, his work was slow to find acceptance as ordinary linear algebra provided sufficient challenges to comprehension.
The topic of multilinear algebra is applied in some studies of multivariate calculus and manifolds where the Jacobian matrix comes into play. The infinitesimal differentials of single variable calculus become differential forms in multivariate calculus, and their manipulation is done with exterior algebra.
After Grassmann, developments in multilinear algebra were made in 1872 by Victor Schlegel when he published the first part of his "System der Raumlehre", and by Elwin Bruno Christoffel. A major advance in multilinear algebra came in the work of Gregorio Ricci-Curbastro and Tullio Levi-Civita (see references). It was the "absolute differential calculus" form of multilinear algebra that Marcel Grossmann and Michele Besso introduced to Albert Einstein. The publication in 1915 by Einstein of a general relativity explanation for the precession of the perihelion of Mercury, established multilinear algebra and tensors as physically important mathematics.
Use in algebraic topology.
Around the middle of the 20th century the study of tensors was reformulated more abstractly. The Bourbaki group's treatise "Multilinear Algebra" was especially influential—in fact the term "multilinear algebra" was probably coined there.
One reason at the time was a new area of application, homological algebra. The development of algebraic topology during the 1940s gave additional incentive for the development of a purely algebraic treatment of the tensor product. The computation of the homology groups of the product of two topological spaces involves the tensor product; but only in the simplest cases, such as a torus, is it directly calculated in that fashion (see Künneth theorem). The topological phenomena were subtle enough to need better foundational concepts; technically speaking, the Tor functors had to be defined.
The material to organise was quite extensive, including also ideas going back to Hermann Grassmann, the ideas from the theory of differential forms that had led to de Rham cohomology, as well as more elementary ideas such as the wedge product that generalises the cross product.
The resulting rather severe write-up of the topic (by Bourbaki) entirely rejected one approach in vector calculus (the quaternion route, that is, in the general case, the relation with Lie groups). They instead applied a novel approach using category theory, with the Lie group approach viewed as a separate matter. Since this leads to a much cleaner treatment, there was probably no going back in purely mathematical terms. (Strictly, the universal property approach was invoked; this is somewhat more general than category theory, and the relationship between the two as alternate ways was also being clarified, at the same time.)
Indeed, what was done is almost precisely to explain that "tensor spaces" are the constructions required to reduce multilinear problems to linear problems. This purely algebraic attack conveys no geometric intuition.
Its benefit is that by re-expressing problems in terms of multilinear algebra, there is a clear and well-defined "best solution": the constraints the solution exerts are exactly those you need in practice. In general there is no need to invoke any "ad hoc" construction, geometric idea, or recourse to co-ordinate systems. In the category-theoretic jargon, everything is entirely "natural".
Conclusion on the abstract approach.
In principle the abstract approach can recover everything done via the traditional approach. In practice this may not seem so simple. On the other hand, the notion of "naturality" is consistent with the "general covariance" principle of general relativity. The latter deals with tensor fields (tensors varying from point to point on a manifold), but covariance asserts that the language of tensors is essential to the proper formulation of general relativity.
Some decades later the rather abstract view coming from category theory was tied up with the approach that had been developed in the 1930s by Hermann Weyl (by working through general relativity via abstract tensor analysis, and additionally in his book "The Classical Groups"). In a way this took the theory full circle, connecting once more the content of old and new viewpoints.
Topics in multilinear algebra.
The subject matter of multilinear algebra has evolved less than the presentation down the years. Here are further pages centrally relevant to it:
There is also a glossary of tensor theory.
Applications.
Some of the ways in which multilinear algebra concepts are applied:


Tangential angle

In geometry, the tangential angle of a curve in the Cartesian plane, at a specific point, is the angle between the tangent line to the curve at the given point and the -axis. (Note that some authors define the angle as the deviation from the direction of the curve at some fixed starting point. This is equivalent to the definition given here by the addition of a constant to the angle or by rotating the curve.)
Equations.
If a curve is given parametrically by , then the tangential angle at is defined (up to a multiple of ) by
Here, the prime symbol denotes the derivative with respect to . Thus, the tangential angle specifies the direction of the velocity vector , while the speed specifies its magnitude. The vector
is called the unit tangent vector, so an equivalent definition is that the tangential angle at is the angle such that is the unit tangent vector at .
If the curve is parametrized by arc length , so , then the definition simplifies to
In this case, the curvature is given by , where is taken to be positive if the curve bends to the left and negative if the curve bends to the right.
If the curve is given by , then we may take as the parametrization, and we may assume is between and . This produces the explicit expression
Polar tangential angle.
In polar coordinates, the polar tangential angle is defined as the angle between the tangent line to the curve at the given point and ray from the origin to the point. If denotes the polar tangential angle, then , where is as above and is, as usual, the polar angle.
If the curve is defined in polar coordinates by , then the polar tangential angle at is defined (up to a multiple of ) by
If the curve is parametrized by arc length as , , so , then the definition becomes
The logarithmic spiral can be defined a curve whose polar tangential angle is constant.


Continuous Hahn polynomials

In mathematics, the continuous Hahn polynomials are a family of orthogonal polynomials in the Askey scheme of hypergeometric orthogonal polynomials. They are defined in terms of generalized hypergeometric functions by
 give a detailed list of their properties.
Closely related polynomials include the dual Hahn polynomials "R""n"("x";γ,δ,"N"), the Hahn polynomials "Q""n"("x";"a","b","c"), and the continuous dual Hahn polynomials "S""n"("x";"a","b","c"). These polynomials all have "q"-analogs with an extra parameter "q", such as the q-Hahn polynomials "Q""n"("x";α,β, "N";"q"), and so on.
Orthogonality.
The continuous Hahn polynomials "p""n"("x";"a","b","c","d") are orthogonal with respect to the weight function
In particular, they satisfy the orthogonality relation
for formula_4, formula_5, formula_6, formula_7, formula_8, formula_9.
Recurrence and difference relations.
The sequence of continuous Hahn polynomials satisfies the recurrence relation
Rodrigues formula.
The continuous Hahn polynomials are given by the Rodrigues-like formula
Generating functions.
The continuous Hahn polynomials have the following generating function:
A second, distinct generating function is given by


Parabolic induction

In mathematics, parabolic induction is a method of constructing representations of a reductive group from representations of its parabolic subgroups.
If "G" is a reductive algebraic group and formula_1 is the Langlands decomposition of a parabolic subgroup "P", then parabolic induction consists of taking a representation of formula_2, extending it to "P" by letting "N" act trivially, and inducing the result from "P" to "G".
There are some generalizations of parabolic induction using cohomology, such as cohomological parabolic induction and Deligne–Lusztig theory.
Philosophy of cusp forms.
The "philosophy of cusp forms" was a slogan of Harish-Chandra, expressing his idea of a kind of reverse engineering of automorphic form theory, from the point of view of representation theory. The discrete group Γ fundamental to the classical theory disappears, superficially. What remains is the basic idea that representations in general are to be constructed by parabolic induction of cuspidal representations. A similar philosophy was enunciated by Israel Gelfand, and the philosophy is a precursor of the Langlands program. A consequence for thinking about representation theory is that cuspidal representations are the fundamental class of objects, from which other representations may be constructed by procedures of induction.
According to Nolan Wallach
Put in the simplest terms the "philosophy of cusp forms" says that for each Γ-conjugacy classes of Q-rational parabolic subgroups one should construct automorphic functions (from objects from spaces of lower dimensions) whose constant terms are zero for other conjugacy classes and the constant terms for [an] element of the given class give all constant terms for this parabolic subgroup. This is almost possible and leads to a description of all automorphic forms in terms of these constructs and cusp forms. The construction that does this is the Eisenstein series.


N-category


Inverse category


Random permutation

A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and simulation. A good example of a random permutation is the shuffling of a deck of cards: this is ideally a random permutation of the 52 cards.
Generating random permutations.
Entry-by-entry brute force method.
One method of generating a random permutation of a set of length "n" uniformly at random (i.e., each of the "n"! permutations is equally likely to appear) is to generate a sequence by taking a random number between 1 and "n" sequentially, ensuring that there is no repetition, and interpreting this sequence ("x"1, ..., "x""n") as the permutation
shown here in two-line notation.
This brute-force method will require occasional retries whenever the random number picked is a repeat of a number already selected. This can be avoided if, on the "i"th step (when "x"1, ..., "x""i" − 1 have already been chosen), one chooses a number "j" at random between 1 and "n" − "i" + 1 and sets "x""i" equal to the "j"th largest of the unchosen numbers.
Fisher-Yates shuffles.
A simple algorithm to generate a permutation of "n" items uniformly at random without retries, known as the Fisher–Yates shuffle, is to start with any permutation (for example, the identity permutation), and then go through the positions 0 through "n" − 2 (we use a convention where the first element has index 0, and the last element has index "n" − 1), and for each position "i" swap the element currently there with a randomly chosen element from positions "i" through "n" − 1 (the end), inclusive. It's easy to verify that any permutation of "n" elements will be produced by this algorithm with probability exactly 1/"n"!, thus yielding a uniform distribution over all such permutations.
unsigned uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m-1 with uniform distribution */
void initialize_and_permute(unsigned permutation[], unsigned n)
 unsigned i;
 for (i = 0; i <= n-2; i++) {
 unsigned j = i+uniform(n-i); /* A random integer such that i ≤ j < n */
 swap(permutation[i], permutation[j]); /* Swap the randomly picked element with permutation[i] */
Note that if the codice_1 function is implemented simply as codice_2 then a bias in the results is introduced if the number of return values of codice_3 is not a multiple of m, but this becomes insignificant if the number of return values of codice_3 is orders of magnitude greater than m.
Statistics on random permutations.
Fixed points.
The probability distribution of the number of fixed points in a uniformly distributed random permutation approaches a Poisson distribution with expected value 1 as "n" grows. In particular, it is an elegant application of the inclusion–exclusion principle to show that the probability that there are no fixed points approaches 1/"e". When "n" is big enough, the probability distribution of fixed points is almost the Poisson distribution with expected value 1. The first "n" moments of this distribution are exactly those of the Poisson distribution.
Randomness testing.
As with all random processes, the quality of the resulting distribution of an implementation of a randomized algorithm such as the Knuth shuffle (i.e., how close it is to the desired uniform distribution) depends on the quality of the underlying source of randomness, such as a pseudorandom number generator. There are many possible randomness tests for random permutations, such as some of the Diehard tests. A typical example of such a test is to take some permutation statistic for which the distribution is known and test whether the distribution of this statistic on a set of randomly generated permutations closely approximates the true distribution.


Xinyi Yuan

Xinyi Yuan () is a Chinese mathematician who is currently a professor of mathematics at Peking University working in number theory, arithmetic geometry, and automorphic forms. In particular, his work focuses on arithmetic intersection theory, algebraic dynamics, Diophantine equations and special values of L-functions.
Education.
Yuan is from Macheng, Huanggang, Hubei, and graduated from Huanggang Middle School in 2000. That year, he received a gold medal at the International Mathematical Olympiad while representing China. Yuan obtained his A.B. in mathematics from Peking University in 2003 and his Ph.D. in mathematics from the Columbia University in 2008 under the direction of Shou-Wu Zhang. His article "Big Line Bundles over Arithmetic Varieties," published in Inventiones Mathematicae, demonstrates a natural sufficient condition for when the orbit under the absolute Galois group is equidistributed.
Career.
He spent time at the Institute for Advanced Study, Princeton University, and Harvard University before joining the Berkeley faculty in 2012.
Yuan was appointed a Clay Research Fellow for a three-year term from 2008 to 2013. Together with a number of other collaborators, Yuan was profiled in Quanta Magazine and Business Insider for, among other things, his research on L-functions.
Research.
Together with Shou-Wu Zhang, Yuan proved the averaged Colmez conjecture which was later shown to imply the André–Oort conjecture for Siegel modular varieties by Jacob Tsimerman.


Affine root system

In mathematics, an affine root system is a root system of affine-linear functions on a Euclidean space. They are used in the classification of affine Lie algebras and superalgebras, and semisimple "p"-adic algebraic groups, and correspond to families of Macdonald polynomials. The reduced affine root systems were used by Kac and Moody in their work on Kac–Moody algebras. Possibly non-reduced affine root systems were introduced and classified by and (except that both these papers accidentally omitted the Dynkin diagram ).
Definition.
Let "E" be an affine space and "V" the vector space of its translations.
Recall that "V" acts faithfully and transitively on "E".
In particular, if formula_1, then it is well defined an element in "V" denoted as formula_2 which is the only element w such that formula_3.
Now suppose we have a scalar product formula_4 on "V".
This defines a metric on "E" as formula_5.
Consider the vector space "F" of affine-linear functions formula_6.
Having fixed a formula_7, very element in "F" can be written as formula_8 with formula_9 a linear function on "V" that doesn't depend on the choice of formula_10.
Now the dual of "V" can be identified with "V" thanks to the chosen scalar product and we can define a product on "F" as formula_11.
Set formula_12 and formula_13 for any formula_14 and formula_15 respectively.
The identification let us define a reflection formula_16 over "E" in the following way:
By transposition formula_16 acts also on "F" as
An "affine root system" is a subset formula_20 such that:
The elements of "S" are called "affine roots".
Denote with formula_21 the group generated by the formula_22 with formula_23.
We also ask


Preadditive category

In mathematics, specifically in category theory, a preadditive category is
another name for an Ab-category, i.e., a category that is enriched over the category of abelian groups, Ab.
That is, an Ab-category C is a category such that
every hom-set Hom("A","B") in C has the structure of an abelian group, and composition of morphisms is bilinear, in the sense that composition of morphisms distributes over the group operation.
In formulas:
formula_1
and
formula_2
where + is the group operation.
Some authors have used the term "additive category" for preadditive categories, but here we follow the current trend of reserving this word for certain special preadditive categories (see below).
Examples.
The most obvious example of a preadditive category is the category Ab itself. More precisely, Ab is a closed monoidal category. Note that commutativity is crucial here; it ensures that the sum of two group homomorphisms is again a homomorphism. In contrast, the category of all groups is not closed. See Medial category.
Other common examples:
These will give you an idea of what to think of; for more examples, follow the links to below.
Elementary properties.
Because every hom-set Hom("A","B") is an abelian group, it has a zero element 0. This is the zero morphism from "A" to "B". Because composition of morphisms is bilinear, the composition of a zero morphism and any other morphism (on either side) must be another zero morphism. If you think of composition as analogous to multiplication, then this says that multiplication by zero always results in a product of zero, which is a familiar intuition. Extending this analogy, the fact that composition is bilinear in general becomes the distributivity of multiplication over addition.
Focusing on a single object "A" in a preadditive category, these facts say that the endomorphism hom-set Hom("A","A") is a ring, if we define multiplication in the ring to be composition. This ring is the endomorphism ring of "A". Conversely, every ring (with identity) is the endomorphism ring of some object in some preadditive category. Indeed, given a ring "R", we can define a preadditive category R to have a single object "A", let Hom("A","A") be "R", and let composition be ring multiplication. Since "R" is an abelian group and multiplication in a ring is bilinear (distributive), this makes R a preadditive category. Category theorists will often think of the ring "R" and the category R as two different representations of the same thing, so that a particularly perverse category theorist might define a ring as a preadditive category with exactly one object (in the same way that a monoid can be viewed as a category with only one object—and forgetting the additive structure of the ring gives us a monoid).
In this way, preadditive categories can be seen as a generalisation of rings. Many concepts from ring theory, such as ideals, Jacobson radicals, and factor rings can be generalized in a straightforward manner to this setting. When attempting to write down these generalizations, one should think of the morphisms in the preadditive category as the "elements" of the "generalized ring".
Additive functors.
If C and D are preadditive categories, then a functor "F": C → D is additive if it too is enriched over the category Ab. That is, "F" is additive if and only if, given any objects "A" and "B" of C, the function "f": Hom("A","B") → Hom("F"("A"),"F"("B")) is a group homomorphism. Most functors studied between preadditive categories are additive.
For a simple example, if the rings "R" and "S" are represented by the one-object preadditive categories R and S, then a ring homomorphism from "R" to "S" is represented by an additive functor from R to S, and conversely.
If C and D are categories and D is preadditive, then the functor category DC is also preadditive, because natural transformations can be added in a natural way.
If C is preadditive too, then the category Add(C,D) of additive functors and all natural transformations between them is also preadditive.
The latter example leads to a generalization of modules over rings: If C is a preadditive category, then Mod(C) := Add(C,Ab) is called the module category over C. When C is the one-object preadditive category corresponding to the ring "R", this reduces to the ordinary category of (left) "R"-modules. Again, virtually all concepts from the theory of modules can be generalised to this setting.
-linear categories.
More generally, one can consider a category C enriched over the monoidal category of modules over a commutative ring , called an -linear category. In other words, each hom-set Hom("A","B") in C has the structure of an -module, and composition of morphisms is -bilinear.
When considering functors between two -linear categories, one often restricts to those that are -linear, so those that induce -linear maps on each hom-set.
Biproducts.
Any finite product in a preadditive category must also be a coproduct, and conversely. In fact, finite products and coproducts in preadditive categories can be characterised by the following "biproduct condition":
This biproduct is often written "A"1 ⊕ ··· ⊕ "An", borrowing the notation for the direct sum. This is because the biproduct in well known preadditive categories like Ab "is" the direct sum. However, although infinite direct sums make sense in some categories, like Ab, infinite biproducts do "not" make sense.
The biproduct condition in the case "n" = 0 simplifies drastically; "B" is a "nullary biproduct" if and only if the identity morphism of "B" is the zero morphism from "B" to itself, or equivalently if the hom-set Hom("B","B") is the trivial ring. Note that because a nullary biproduct will be both terminal (a nullary product) and initial (a nullary coproduct), it will in fact be a zero object.
Indeed, the term "zero object" originated in the study of preadditive categories like Ab, where the zero object is the zero group.
A preadditive category in which every biproduct exists (including a zero object) is called "additive". Further facts about biproducts that are mainly useful in the context of additive categories may be found under that subject.
Kernels and cokernels.
Because the hom-sets in a preadditive category have zero morphisms,
the notion of kernel and cokernel
make sense. That is, if "f": "A" → "B" is a
morphism in a preadditive category, then the kernel of "f" is the
equaliser of "f" and the zero morphism from "A" to "B", while the cokernel of "f" is the coequaliser of "f" and this zero morphism. Unlike with products and coproducts, the kernel and cokernel of "f" are generally not equal in a preadditive category.
When specializing to the preadditive categories of abelian groups or modules over a ring, this notion of kernel coincides with the ordinary notion of a kernel of a homomorphism, if one identifies the ordinary kernel "K" of "f": "A" → "B" with its embedding "K" → "A". However, in a general preadditive category there may exist morphisms without kernels and/or cokernels.
There is a convenient relationship between the kernel and cokernel and the abelian group structure on the hom-sets. Given parallel morphisms "f" and "g", the equaliser of "f" and "g" is just the kernel of "g" − "f", if either exists, and the analogous fact is true for coequalisers. The alternative term "difference kernel" for binary equalisers derives from this fact.
A preadditive category in which all biproducts, kernels, and cokernels exist is called "pre-abelian". Further facts about kernels and cokernels in preadditive categories that are mainly useful in the context of pre-abelian categories may be found under that subject.
Special cases.
Most of these special cases of preadditive categories have all been mentioned above, but they're gathered here for reference.
The preadditive categories most commonly studied are in fact abelian categories; for example, Ab is an abelian category.


Band matrix

In mathematics, particularly matrix theory, a band matrix or banded matrix is a sparse matrix whose non-zero entries are confined to a diagonal "band", comprising the main diagonal and zero or more diagonals on either side.
Band matrix.
Bandwidth.
Formally, consider an "n"×"n" matrix "A"=("a""i,j" ). If all matrix elements are zero outside a diagonally bordered band whose range is determined by constants "k"1 and "k"2:
then the quantities "k"1 and "k"2 are called the ' and ', respectively. The of the matrix is the maximum of "k"1 and "k"2; in other words, it is the number "k" such that formula_2 if formula_3.
Applications.
In numerical analysis, matrices from finite element or finite difference problems are often banded. Such matrices can be viewed as descriptions of the coupling between the problem variables; the banded property corresponds to the fact that variables are not coupled over arbitrarily large distances. Such matrices can be further dividedfor instance, banded matrices exist where every element in the band is nonzero. These often arise when discretising one-dimensional problems.
Problems in higher dimensions also lead to banded matrices, in which case the band itself also tends to be sparse. For instance, a partial differential equation on a square domain (using central differences) will yield a matrix with a bandwidth equal to the square root of the matrix dimension, but inside the band only 5 diagonals are nonzero. Unfortunately, applying Gaussian elimination (or equivalently an LU decomposition) to such a matrix results in the band being filled in by many non-zero elements.
Band storage.
Band matrices are usually stored by storing the diagonals in the band; the rest is implicitly zero.
For example, a tridiagonal matrix has bandwidth 1. The 6-by-6 matrix
is stored as the 6-by-3 matrix
A further saving is possible when the matrix is symmetric. For example, consider a symmetric 6-by-6 matrix with an upper bandwidth of 2:
This matrix is stored as the 6-by-3 matrix:
Band form of sparse matrices.
From a computational point of view, working with band matrices is always preferential to working with similarly dimensioned square matrices. A band matrix can be likened in complexity to a rectangular matrix whose row dimension is equal to the bandwidth of the band matrix. Thus the work involved in performing operations such as multiplication falls significantly, often leading to huge savings in terms of calculation time and complexity.
As sparse matrices lend themselves to more efficient computation than dense matrices, as well as in more efficient utilization of computer storage, there has been much research focused on finding ways to minimise the bandwidth (or directly minimise the fill-in) by applying permutations to the matrix, or other such equivalence or similarity transformations.
The Cuthill–McKee algorithm can be used to reduce the bandwidth of a sparse symmetric matrix. There are, however, matrices for which the reverse Cuthill–McKee algorithm performs better. There are many other methods in use.
The problem of finding a representation of a matrix with minimal bandwidth by means of permutations of rows and columns is NP-hard.


Nilpotent matrix

In linear algebra, a nilpotent matrix is a square matrix "N" such that
for some positive integer formula_2. The smallest such formula_2 is called the index of formula_4, sometimes the degree of formula_4.
More generally, a nilpotent transformation is a linear transformation formula_6 of a vector space such that formula_7 for some positive integer formula_2 (and thus, formula_9 for all formula_10). Both of these concepts are special cases of a more general concept of nilpotence that applies to elements of rings.
Examples.
Example 1.
The matrix
is nilpotent with index 2, since formula_12.
Example 2.
More generally, any formula_13-dimensional triangular matrix with zeros along the main diagonal is nilpotent, with index formula_14. For example, the matrix
is nilpotent, with
The index of formula_17 is therefore 4.
Example 3.
Although the examples above have a large number of zero entries, a typical nilpotent matrix does not. For example,
although the matrix has no zero entries.
Example 4.
Additionally, any matrices of the form
such as
or
square to zero.
Example 5.
Perhaps some of the most striking examples of nilpotent matrices are formula_22 square matrices of the form:
The first few of which are:
These matrices are nilpotent but there are no zero entries in any powers of them less than the index.
Characterization.
For an formula_25 square matrix formula_4 with real (or complex) entries, the following are equivalent:
The last theorem holds true for matrices over any field of characteristic 0 or sufficiently large characteristic. (cf. Newton's identities)
This theorem has several consequences, including:
Classification.
Consider the formula_25 shift matrix:
This matrix has 1s along the superdiagonal and 0s everywhere else. As a linear transformation, the shift matrix "shifts" the components of a vector one position to the left, with a zero appearing in the last position:
This matrix is nilpotent with degree formula_13, and is the canonical nilpotent matrix.
Specifically, if formula_4 is any nilpotent matrix, then formula_4 is similar to a block diagonal matrix of the form
where each of the blocks formula_44 is a shift matrix (possibly of different sizes). This form is a special case of the Jordan canonical form for matrices.
For example, any nonzero 2 × 2 nilpotent matrix is similar to the matrix
That is, if formula_4 is any nonzero 2 × 2 nilpotent matrix, then there exists a basis b1, b2 such that "Nb1 = 0 and "Nb2 = b1.
This classification theorem holds for matrices over any field. (It is not necessary for the field to be algebraically closed.)
Flag of subspaces.
A nilpotent transformation formula_6 on formula_48 naturally determines a flag of subspaces
and a signature
The signature characterizes formula_6 up to an invertible linear transformation. Furthermore, it satisfies the inequalities
Conversely, any sequence of natural numbers satisfying these inequalities is the signature of a nilpotent transformation.
Generalizations.
A linear operator formula_53 is locally nilpotent if for every vector formula_54, there exists a formula_55 such that
For operators on a finite-dimensional vector space, local nilpotence is equivalent to nilpotence.


Flat cover

In algebra, a flat cover of a module "M" over a ring is a surjective homomorphism from a flat module "F" to "M" that is in some sense minimal. Any module over a ring has a flat cover that is unique up to (non-unique) isomorphism. Flat covers are in some sense dual to injective hulls, and are related to projective covers and torsion-free covers.
Definitions.
The homomorphism "F"→"M" is defined to be a flat cover of "M" if it is surjective, "F" is flat, every homomorphism from flat module to "M" factors through "F", and any map from "F" to "F" commuting with the map to "M" is an automorphism of "F".
History.
While projective covers for modules do not always exist, it was speculated that for general rings, every module would have a flat cover. This flat cover conjecture was explicitly first stated in . The conjecture turned out to be true, resolved positively and proved simultaneously by . This was preceded by important contributions by P. Eklof, J. Trlifaj and J. Xu.
Minimal flat resolutions.
Any module "M" over a ring has a resolution by flat modules
such that each "F""n"+1 is the flat cover of the kernel of "F""n" → "F""n"−1.
Such a resolution is unique up to isomorphism, and is a minimal flat resolution in the sense that any flat resolution of "M" factors through it. Any homomorphism of modules extends to a homomorphism between the corresponding flat resolutions, though this extension is in general not unique.


Biorthogonal polynomial

In mathematics, a biorthogonal polynomial is a polynomial that is orthogonal to several different measures. Biorthogonal polynomials are a generalization of orthogonal polynomials and share many of their properties. There are two different concepts of biorthogonal polynomials in the literature: introduced the concept of polynomials biorthogonal with respect to a sequence of measures, while Szegő introduced the concept of two sequences of polynomials that are biorthogonal with respect to each other.
Polynomials biorthogonal with respect to a sequence of measures.
A polynomial "p" is called biorthogonal with respect to a sequence of measures "μ"1, "μ"2, ... if
Biorthogonal pairs of sequences.
Two sequences "ψ"0, "ψ"1, ... and "φ"0, "φ"1, ... of polynomials are called biorthogonal (for some measure "μ") if
whenever "m" ≠ "n".
The definition of biorthogonal pairs of sequences is in some sense a special case of the definition of biorthogonality with respect to a sequence of measures. More precisely two sequences ψ0, ψ1, ... and φ0, φ1, ... of polynomials are biorthogonal for the measure μ if and only if the sequence ψ0, ψ1, ... is biorthogonal for the sequence of measures φ0μ, φ1μ, ..., and the sequence φ0, φ1, ... is biorthogonal for the sequence of measures ψ0μ, ψ1μ...


Monotone matrix

A real square matrix formula_1 is monotone (in the sense of Collatz) if for all real vectors formula_2, formula_3 implies formula_4, where formula_5 is the element-wise order on formula_6.
Properties.
A monotone matrix is nonsingular.
"Proof": Let formula_1 be a monotone matrix and assume there exists formula_8 with formula_9. Then, by monotonicity, formula_10 and formula_11, and hence formula_12. formula_13
Let formula_1 be a real square matrix. formula_1 is monotone if and only if formula_16.
"Proof": Suppose formula_1 is monotone. Denote by formula_18 the formula_19-th column of formula_20. Then, formula_21 is the formula_19-th standard basis vector, and hence formula_10 by monotonicity. For the reverse direction, suppose formula_1 admits an inverse such that formula_16. Then, if formula_26, formula_27, and hence formula_1 is monotone. formula_13
Examples.
The matrix formula_30 is monotone, with inverse formula_31.
In fact, this matrix is an M-matrix (i.e., a monotone L-matrix).
Note, however, that not all monotone matrices are M-matrices. An example is formula_32, whose inverse is formula_33.


Ezra Brown

Ezra Abraham "Bud" Brown (born January 22, 1944 in Reading, PA) is an American mathematician active in combinatorics, algebraic number theory, elliptic curves, graph theory, expository mathematics and cryptography. He spent most of his career at Virginia Tech where he is now Alumni Distinguished Professor Emeritus of Mathematics.
Education and career.
Brown earned a B.A. at Rice University in 1965. He then studied mathematics at Louisiana State University (LSU), getting an M.S. in 1967 and a Ph.D. in 1969 with the dissertation "Representations of Discriminantal Divisors by Binary Quadratic Forms" under Gordon Pall. He joined Virginia Tech in 1969 becoming Assistant Professor (1969-73), Associate Professor (1973-81), Professor (1981-2005), and Alumni Distinguished Professor of Mathematicsand Distinguished Professor of Mathematics (2005-2017). He retired from Virginia Tech in 2017.
Brown became interested in elliptic curves while at LSU and this has remained one of his principal areas of research along with quadratic forms and algebraic number theory in general.
His books include "The Unity of Combinatorics" (MAA, 2020), co-authored with Richard K. Guy.
Personal life.
While at Rice he met his future wife Jo. They have been married now for over 53 years and have two children, Benjamin and Daniel. Brown remained at Virginia Tech until his retirement in 2017.
At the age of 16 Brown taught himself to play the piano, and in college he acted in several musicals and joined an a cappella chorus. In 1989, he joined the Blacksburg Master Chorale and the chorus of Opera Roanoke. Starting in 2011 he took his love of music and math to MathFest where he an his fellow mathematicians composed new words to old show tunes and even took part in a Gilbert-and-Sullivan Singalong at MathFest 2016 with his "Biscuits of Number Theory" co-editor Art Benjamin.
Brown and his mathematical grandfather, L. E. Dickson, have the same birthday.


Verma module

Verma modules, named after Daya-Nand Verma, are objects in the representation theory of Lie algebras, a branch of mathematics.
Verma modules can be used in the classification of irreducible representations of a complex semisimple Lie algebra. Specifically, although Verma modules themselves are infinite dimensional, quotients of them can be used to construct finite-dimensional representations with highest weight formula_1, where formula_1 is dominant and integral. Their homomorphisms correspond to invariant differential operators over flag manifolds.
Informal construction.
We can explain the idea of a Verma module as follows. Let formula_3 be a semisimple Lie algebra (over formula_4, for simplicity). Let formula_5 be a fixed Cartan subalgebra of formula_3 and let formula_7 be the associated root system. Let formula_8 be a fixed set of positive roots. For each formula_9, choose a nonzero element formula_10 for the corresponding root space formula_11 and a nonzero element formula_12 in the root space formula_13. We think of the formula_10's as "raising operators" and the formula_12's as "lowering operators."
Now let formula_16 be an arbitrary linear functional, not necessarily dominant or integral. Our goal is to construct a representation formula_17 of formula_3 with highest weight formula_1 that is generated by a single nonzero vector formula_20 with weight formula_1. The Verma module is one particular such highest-weight module, one that is maximal in the sense that every other highest-weight module with highest weight formula_1 is a quotient of the Verma module. It will turn out that Verma modules are always infinite dimensional; if formula_1 is dominant integral, however, one can construct a finite-dimensional quotient module of the Verma module. Thus, Verma modules play an important role in the classification of finite-dimensional representations of formula_3. Specifically, they are an important tool in the hard part of the theorem of the highest weight, namely showing that every dominant integral element actually arises as the highest weight of a finite-dimensional irreducible representation of formula_3.
We now attempt to understand intuitively what the Verma module with highest weight formula_1 should look like. Since formula_20 is to be a highest weight vector with weight formula_1, we certainly want
and
Then formula_17 should be spanned elements obtained by lowering formula_20 by the action of the formula_12's:
We now impose "only" those relations among vectors of the above form required by the commutation relations among the formula_35's. In particular, the Verma module is always infinite-dimensional. The weights of the Verma module with highest weight formula_1 will consist of all elements formula_37 that can be obtained from formula_1 by subtracting integer combinations of positive roots. The figure shows the weights of a Verma module for formula_39.
A simple re-ordering argument shows that there is only one possible way the full Lie algebra formula_3 can act on this space. Specifically, if formula_41 is any element of formula_3, then by the easy part of the Poincaré–Birkhoff–Witt theorem, we can rewrite
as a linear combination of products of Lie algebra elements with the raising operators formula_10 acting first, the elements of the Cartan subalgebra, and last the lowering operators formula_12. Applying this sum of terms to formula_20, any term with a raising operator is zero, any factors in the Cartan act as scalars, and thus we end up with an element of the original form.
To understand the structure of the Verma module a bit better, we may choose an ordering of the positive roots as formula_47 and we let the corresponding lowering operators by formula_48. Then by a simple re-ordering argument, every element of the above form can be rewritten as a linear combination of elements with the formula_35's in a specific order:
where the formula_51's are non-negative integers. Actually, it turns out that such vectors form a basis for the Verma module.
Although this description of the Verma module gives an intuitive idea of what formula_17 looks like, it still remains to give a rigorous construction of it. In any case, the Verma module gives—for "any" formula_1, not necessarily dominant or integral—a representation with highest weight formula_1. The price we pay for this relatively simple construction is that formula_17 is always infinite dimensional. In the case where formula_1 is dominant and integral, one can construct a finite-dimensional, irreducible quotient of the Verma module.
The case of sl(2; C).
Let formula_57 be the usual basis for formula_58:
with the Cartan subalgebra being the span of formula_60. Let formula_1 be defined by formula_62 for an arbitrary complex number formula_63. Then the Verma module with highest weight formula_1 is spanned by linearly independent vectors formula_65 and the action of the basis elements is as follows:
(This means in particular that formula_67 and that formula_68.) These formulas are motivated by the way the basis elements act in the finite-dimensional representations of formula_58, except that we no longer require that the "chain" of eigenvectors for formula_60 has to terminate.
In this construction, formula_63 is an arbitrary complex number, not necessarily real or positive or an integer. Nevertheless, the case where formula_63 is a non-negative integer is special. In that case, the span of the vectors formula_73 is easily seen to be invariant—because formula_74. The quotient module is then the finite-dimensional irreducible representation of formula_58 of dimension formula_76
Definition of Verma modules.
There are two standard constructions of the Verma module, both of which involve the concept of universal enveloping algebra. We continue the notation of the previous section: formula_3 is a complex semisimple Lie algebra, formula_5 is a fixed Cartan subalgebra, formula_7 is the associated root system with a fixed set formula_8 of positive roots. For each formula_9, we choose nonzero elements formula_82 and formula_83.
As a quotient of the enveloping algebra.
The first construction of the Verma module is a quotient of the universal enveloping algebra formula_84 of formula_3. Since the Verma module is supposed to be a formula_3-module, it will also be a formula_84-module, by the universal property of the enveloping algebra. Thus, if we have a Verma module formula_17 with highest weight vector formula_20, there will be a linear map formula_90 from formula_84 into formula_17 given by
Since formula_17 is supposed to be generated by formula_20, the map formula_90 should be surjective. Since formula_20 is supposed to be a highest weight vector, the kernel of formula_90 should include all the root vectors formula_10 for formula_100 in formula_8. Since, also, formula_20 is supposed to be a weight vector with weight formula_1, the kernel of formula_90 should include all vectors of the form
Finally, the kernel of formula_90 should be a left ideal in formula_84; after all, if formula_108 then formula_109 for all formula_110.
The previous discussion motivates the following construction of Verma module. We define formula_17 as the quotient vector space
where formula_113 is the left ideal generated by all elements of the form
and
Because formula_113 is a left ideal, the natural left action of formula_84 on itself carries over to the quotient. Thus, formula_17 is a formula_84-module and therefore also a formula_3-module.
By extension of scalars.
The "extension of scalars" procedure is a method for changing a left module formula_121 over one algebra formula_122 (not necessarily commutative) into a left module over a larger algebra formula_123 that contains formula_122 as a subalgebra. We can think of formula_123 as a right formula_122-module, where formula_122 acts on formula_123 by multiplication on the right. Since formula_121 is a left formula_122-module and formula_123 is a right formula_122-module, we can form the tensor product of the two over the algebra formula_122:
Now, since formula_123 is a left formula_123-module over itself, the above tensor product carries a left module structure over the larger algebra formula_123, uniquely determined by the requirement that
for all formula_139 and formula_140 in formula_123. Thus, starting from the left formula_122-module formula_121, we have produced a left formula_123-module formula_134.
We now apply this construction in the setting of a semisimple Lie algebra. We let formula_146 be the subalgebra of formula_3 spanned by formula_5 and the root vectors formula_10 with formula_9. (Thus, formula_146 is a "Borel subalgebra" of formula_3.) We can form a left module formula_153 over the universal enveloping algebra formula_154 as follows:
The motivation for this formula is that it describes how formula_154 is supposed to act on the highest weight vector in a Verma module.
Now, it follows from the Poincaré–Birkhoff–Witt theorem that formula_154 is a subalgebra of formula_84. Thus, we may apply the extension of scalars technique to convert formula_153 from a left formula_154-module into a left formula_84-module formula_17 as follow:
Since formula_17 is a left formula_84-module, it is, in particular, a module (representation) for formula_3.
The structure of the Verma module.
Whichever construction of the Verma module is used, one has to prove that it is nontrivial, i.e., not the zero module. Actually, it is possible to use the Poincaré–Birkhoff–Witt theorem to show that the underlying vector space of formula_17 is isomorphic to
where formula_174 is the Lie subalgebra generated by the negative root spaces of formula_3 (that is, the formula_12's).
Basic properties.
Verma modules, considered as formula_3-modules, are highest weight modules, i.e. they are generated by a highest weight vector. This highest weight vector is formula_178 (the first formula_179 is the unit in formula_180 and the second is
the unit in the field formula_181, considered as the formula_146-module
formula_153) and it has weight formula_1.
Multiplicities.
Verma modules are weight modules, i.e. formula_17 is a direct sum of all its weight spaces. Each weight space in formula_17 is finite-dimensional and the dimension of the formula_37-weight space formula_188 is the number of ways of expressing formula_189 as a sum of positive roots (this is closely related to the so-called Kostant partition function). This assertion follows from the earlier claim that the Verma module is isomorphic as a vector space to formula_173, along with the Poincaré–Birkhoff–Witt theorem for formula_173.
Universal property.
Verma modules have a very important property: If formula_121 is any representation generated by a highest weight vector of weight formula_1, there is a surjective formula_3-homomorphism formula_195 That is, all representations with highest weight formula_1 that are generated by the highest weight vector (so called highest weight modules) are quotients of formula_197
Irreducible quotient module.
formula_17 contains a unique maximal submodule, and its quotient is the unique (up to isomorphism) irreducible representation with highest weight formula_199 If the highest weight formula_1 is dominant and integral, one then proves that this irreducible quotient is actually finite dimensional.
As an example, consider the case formula_201 discussed above. If the highest weight formula_63 is "dominant integral"—meaning simply that it is a non-negative integer—then formula_203 and the span of the elements formula_73 is invariant. The quotient representation is then irreducible with dimension formula_205. The quotient representation is spanned by linearly independent vectors formula_206. The action of formula_207 is the same as in the Verma module, "except" that formula_208 in the quotient, as compared to formula_209 in the Verma module.
The Verma module formula_17 itself is irreducible if and only if none of the coordinates of formula_1 in the basis of fundamental weights is from the set formula_212.
Other properties.
The Verma module formula_17 is called "regular", if its highest weight λ is on the affine Weyl orbit of a dominant weight formula_214. In other word, there exist an element w of the Weyl group W such that
where formula_216 is the affine action of the Weyl group.
The Verma module formula_17 is called "singular", if there is no dominant weight on the affine orbit of λ. In this case, there exists a weight formula_214 so that formula_219 is on the wall of the fundamental Weyl chamber (δ is the sum of all fundamental weights).
Homomorphisms of Verma modules.
For any two weights formula_220 a non-trivial homomorphism
may exist only if formula_37 and formula_1 are linked with an affine action of the Weyl group formula_224 of the Lie algebra formula_3. This follows easily from the Harish-Chandra theorem on infinitesimal central characters.
Each homomorphism of Verma modules is injective and the dimension
for any formula_227. So, there exists a nonzero formula_221 if and only if formula_188 is isomorphic to a (unique) submodule of formula_17.
The full classification of Verma module homomorphisms was done by Bernstein–Gelfand–Gelfand and Verma and can be summed up in the following statement:
 There exists a nonzero homomorphism formula_221 if and only if there exists
a sequence of weights
such that formula_233 for some positive roots formula_234 (and formula_235 is the corresponding root reflection and formula_236 is the sum of all fundamental weights) and for each formula_237 is a natural number (formula_238 is the coroot associated to the root formula_234).
If the Verma modules formula_240 and formula_241 are regular, then there exists a unique dominant weight formula_214 and unique elements "w", "w"′ of the Weyl group "W" such that
and
where formula_216 is the affine action of the Weyl group. If the weights are further integral, then there exists a nonzero homomorphism
if and only if
in the Bruhat ordering of the Weyl group.
Jordan–Hölder series.
Let
be a sequence of formula_3-modules so that the quotient B/A is irreducible with highest weight μ. Then there exists a nonzero homomorphism formula_246.
An easy consequence of this is, that for any highest weight modules formula_251 such that
there exists a nonzero homomorphism formula_246.
Bernstein–Gelfand–Gelfand resolution.
Let formula_254 be a finite-dimensional irreducible representation of the Lie algebra formula_3 with highest weight λ. We know from the section about homomorphisms of Verma modules that there exists a homomorphism
if and only if
in the Bruhat ordering of the Weyl group. The following theorem describes a resolution of formula_254 in terms of Verma modules (it was proved by Bernstein–Gelfand–Gelfand in 1975) :
There exists an exact sequence of formula_3-homomorphisms
where "n" is the length of the largest element of the Weyl group.
A similar resolution exists for generalized Verma modules as well. It is denoted shortly as the "BGG resolution".


Spectral triple

In noncommutative geometry and related branches of mathematics and mathematical physics, a spectral triple is a set of data which encodes a geometric phenomenon in an analytic way. The definition typically involves a Hilbert space, an algebra of operators on it and an unbounded self-adjoint operator, endowed with supplemental structures. It was conceived by Alain Connes who was motivated by the Atiyah-Singer index theorem and sought its extension to 'noncommutative' spaces. Some authors refer to this notion as unbounded K-cycles or as unbounded Fredholm modules.
Motivation.
A motivating example of spectral triple is given by the algebra of smooth functions on a compact spin manifold, acting on the Hilbert space of L2-spinors, accompanied by the Dirac operator associated to the spin structure. From the knowledge of these objects one is able to recover the original manifold as a metric space: the manifold as a topological space is recovered as the spectrum of the algebra, while the (absolute value of) Dirac operator retains the metric. On the other hand, the phase part of the Dirac operator, in conjunction with the algebra of functions, gives a K-cycle which encodes index-theoretic information. The local index formula expresses the pairing of the K-group of the manifold with this K-cycle in two ways: the 'analytic/global' side involves the usual trace on the Hilbert space and commutators of functions with the phase operator (which corresponds to the 'index' part of the index theorem), while the 'geometric/local' side involves the Dixmier trace and commutators with the Dirac operator (which corresponds to the 'characteristic class integration' part of the index theorem).
Extensions of the index theorem can be considered in cases, typically when one has an action of a group on the manifold, or when the manifold is endowed with a foliation structure, among others. In those cases the algebraic system of the 'functions' which expresses the underlying geometric object is no longer commutative, but one may able to find the space of square integrable spinors (or, sections of a Clifford module) on which the algebra acts, and the corresponding 'Dirac' operator on it satisfying certain boundedness of commutators implied by the pseudo-differential calculus.
Definition.
An odd spectral triple is a triple (A, H, D) consisting of a Hilbert space H, an algebra A of operators on H (usually closed under taking adjoints) and a densely defined self adjoint operator D satisfying ‖[a, D]‖ < ∞ for any a ∈ A. An even spectral triple is an odd spectral triple with a Z/2Z-grading on H, such that the elements in A are even while D is odd with respect to this grading. One could also say that an even spectral triple is given by a quartet (A, H, D, γ) such that γ is a self adjoint unitary on H satisfying a γ = γ a for any a in A and D γ = - γ D.
A finitely summable spectral triple is a spectral triple (A, H, D) such that a.D for any a in A has a compact resolvent which belongs to the class of Lp+-operators for a fixed p (when A contains the identity operator on H, it is enough to require D−1 in Lp+(H)). When this condition is satisfied, the triple (A, H, D) is said to be p-summable. A spectral triple is said to be θ-summable when e−tD2 is of trace class for any t > 0.
Let δ(T) denote the commutator of |D| with an operator T on H. A spectral triple is said to be regular when the elements in A and the operators of the form [a, D] for a in A are in the domain of the iterates δn of δ.
When a spectral triple (A, H, D) is p-summable, one may define its zeta function ζD(s) = Tr(|D|−s); more generally there are zeta functions ζb(s) = Tr(b|D|−s) for each element b in the algebra B generated by δn(A) and δn([a, D]) for positive integers n. They are related to the heat kernel exp(-t|D|) by a Mellin transform. The collection of the poles of the analytic continuation of ζb for b in B is called the dimension spectrum of (A, H, D).
A real spectral triple is a spectral triple (A, H, D) accompanied with an anti-linear involution J on H, satisfying [a, JbJ] = 0 for a, b in A. In the even case it is usually assumed that J is even with respect to the grading on H.
Important concepts.
Given a spectral triple (A, H, D), one can apply several important operations to it. The most fundamental one is the polar decomposition D = F|D| of D into a self adjoint unitary operator F (the 'phase' of D) and a densely defined positive operator |D| (the 'metric' part).
Metric on the pure state space.
The positive |D| operator defines a metric on the set of pure states on the norm closure of A.
Pairing with K-theory.
The self adjoint unitary "F" gives a map of the K-theory of "A" into integers by taking Fredholm index as follows. In the even case, each projection "e" in "A" decomposes as "e"0 ⊕ "e"1 under the grading and "e"1"Fe"0 becomes a Fredholm operator from "e"0"H" to "e"1"H". Thus "e" → Ind "e"1"Fe"0 defines an additive mapping of "K"0("A") to Z. In the odd case the eigenspace decomposition of "F" gives a grading on "H", and each invertible element in "A" gives a Fredholm operator ("F" + 1) u ("F" − 1)/4 from ("F" − 1)"H" to ("F" + 1)"H". Thus "u" → Ind ("F" + 1) u ("F" − 1)/4 gives an additive mapping from "K"1("A") to Z.
When the spectral triple is finitely summable, one may write the above indexes using the (super) trace, and a product of "F", "e" (resp. "u") and commutator of "F" with "e" (resp. "u"). This can be encoded as a ("p" + 1)-functional on "A" satisfying some algebraic conditions and give Hochschild / cyclic cohomology cocycles, which describe the above maps from K-theory to the integers.


Igusa quartic

In algebraic geometry, the Igusa quartic (also called the Castelnuovo–Richmond quartic "CR"4 or the Castelnuovo–Richmond–Igusa quartic) is a quartic hypersurface in 4-dimensional projective space, studied by .
It is closely related to the moduli space of genus 2 curves with level 2 structure. It is the dual of the Segre cubic.
It can be given as a codimension 2 variety in "P"5 by the equations


Non-linear least squares

Non-linear least squares is the form of least squares analysis used to fit a set of "m" observations with a model that is non-linear in "n" unknown parameters ("m" ≥ "n"). It is used in some forms of nonlinear regression. The basis of the method is to approximate the model by a linear one and to refine the parameters by successive iterations. There are many similarities to linear least squares, but also some significant differences. In economic theory, the non-linear least squares method is applied in (i) the probit regression, (ii) threshold regression, (iii) smooth regression, (iv) logistic link regression, (v) Box-Cox transformed regressors (formula_1).
Theory.
Consider a set of formula_2 data points, formula_3 and a curve (model function) formula_4 that in addition to the variable formula_5 also depends on formula_6 parameters, formula_7 with formula_8 It is desired to find the vector formula_9 of parameters such that the curve fits best the given data in the least squares sense, that is, the sum of squares
is minimized, where the residuals (in-sample prediction errors) "ri" are given by
for formula_12
The minimum value of "S" occurs when the gradient is zero. Since the model contains "n" parameters there are "n" gradient equations:
In a nonlinear system, the derivatives formula_14 are functions of both the independent variable and the parameters, so in general these gradient equations do not have a closed solution. Instead, initial values must be chosen for the parameters. Then, the parameters are refined iteratively, that is, the values are obtained by successive approximation,
Here, "k" is an iteration number and the vector of increments, formula_16 is known as the shift vector. At each iteration the model is linearized by approximation to a first-order Taylor polynomial expansion about formula_17
The Jacobian, J, is a function of constants, the independent variable "and" the parameters, so it changes from one iteration to the next. Thus, in terms of the linearized model, formula_19 and the residuals are given by
Substituting these expressions into the gradient equations, they become
which, on rearrangement, become "n" simultaneous linear equations, the normal equations
The normal equations are written in matrix notation as
When the observations are not equally reliable, a weighted sum of squares may be minimized,
Each element of the diagonal weight matrix W should, ideally, be equal to the reciprocal of the error variance of the measurement.
The normal equations are then
These equations form the basis for the Gauss–Newton algorithm for a non-linear least squares problem.
Geometrical interpretation.
In linear least squares the objective function, "S", is a quadratic function of the parameters.
When there is only one parameter the graph of "S" with respect to that parameter will be a parabola. With two or more parameters the contours of "S" with respect to any pair of parameters will be concentric ellipses (assuming that the normal equations matrix formula_28 is positive definite). The minimum parameter values are to be found at the centre of the ellipses. The geometry of the general objective function can be described as paraboloid elliptical.
In NLLSQ the objective function is quadratic with respect to the parameters only in a region close to its minimum value, where the truncated Taylor series is a good approximation to the model.
The more the parameter values differ from their optimal values, the more the contours deviate from elliptical shape. A consequence of this is that initial parameter estimates should be as close as practicable to their (unknown!) optimal values. It also explains how divergence can come about as the Gauss–Newton algorithm is convergent only when the objective function is approximately quadratic in the parameters.
Computation.
Initial parameter estimates.
Some problems of ill-conditioning and divergence can be corrected by finding initial parameter estimates that are near to the optimal values. A good way to do this is by computer simulation. Both the observed and calculated data are displayed on a screen. The parameters of the model are adjusted by hand until the agreement between observed and calculated data is reasonably good. Although this will be a subjective judgment, it is sufficient to find a good starting point for the non-linear refinement. Initial parameter estimates can be created using transformations or linearizations. Better still evolutionary algorithms such as the Stochastic Funnel Algorithm can lead to the convex basin of attraction that surrounds the optimal parameter estimates. Hybrid algorithms that use randomization and elitism, followed by Newton methods have been shown to be useful and computationally efficient.
Solution.
Any method among the ones described below can be applied to find a solution.
Convergence criteria.
The common sense criterion for convergence is that the sum of squares does not decrease from one iteration to the next. However this criterion is often difficult to implement in practice, for various reasons. A useful convergence criterion is
The value 0.0001 is somewhat arbitrary and may need to be changed. In particular it may need to be increased when experimental errors are large. An alternative criterion is
Again, the numerical value is somewhat arbitrary; 0.001 is equivalent to specifying that each parameter should be refined to 0.1% precision. This is reasonable when it is less than the largest relative standard deviation on the parameters.
Calculation of the Jacobian by numerical approximation.
There are models for which it is either very difficult or even impossible to derive analytical expressions for the elements of the Jacobian. Then, the numerical approximation
is obtained by calculation of formula_33 for formula_34 and formula_35. The increment,formula_36, size should be chosen so the numerical derivative is not subject to approximation error by being too large, or round-off error by being too small.
Parameter errors, confidence limits, residuals etc..
Some information is given in the corresponding section on the linear least squares page.
Multiple minima.
Multiple minima can occur in a variety of circumstances some of which are:
where formula_38 is the height, formula_39 is the position and formula_40 is the half-width at half height, there are two solutions for the half-width, formula_41 and formula_42 which give the same optimal value for the objective function.
Not all multiple minima have equal values of the objective function. False minima, also known as local minima, occur when the objective function value is greater than its value at the so-called global minimum. To be certain that the minimum found is the global minimum, the refinement should be started with widely differing initial values of the parameters. When the same minimum is found regardless of starting point, it is likely to be the global minimum.
When multiple minima exist there is an important consequence: the objective function will have a maximum value somewhere between two minima. The normal equations matrix is not positive definite at a maximum in the objective function, as the gradient is zero and no unique direction of descent exists. Refinement from a point (a set of parameter values) close to a maximum will be ill-conditioned and should be avoided as a starting point. For example, when fitting a Lorentzian the normal equations matrix is not positive definite when the half-width of the band is zero.
Transformation to a linear model.
A non-linear model can sometimes be transformed into a linear one. For example, when the model is a simple exponential function,
it can be transformed into a linear model by taking logarithms.
Graphically this corresponds to working on a semi-log plot. The sum of squares becomes
This procedure should be avoided unless the errors are multiplicative and log-normally distributed because it can give misleading results. This comes from the fact that whatever the experimental errors on y might be, the errors on log y are different. Therefore, when the transformed sum of squares is minimized different results will be obtained both for the parameter values and their calculated standard deviations. However, with multiplicative errors that are log-normally distributed, this procedure gives unbiased and consistent parameter estimates.
Another example is furnished by Michaelis–Menten kinetics, used to determine two parameters formula_50 and formula_51:
The Lineweaver–Burk plot
of formula_54 against formula_55 is linear in the parameters formula_56 and formula_57, but very sensitive to data error and strongly biased toward fitting the data in a particular range of the independent variable formula_58.
Algorithms.
Gauss–Newton method.
The normal equations
may be solved for formula_60 by Cholesky decomposition, as described in linear least squares. The parameters are updated iteratively
where "k" is an iteration number. While this method may be adequate for simple models, it will fail if divergence occurs. Therefore, protection against divergence is essential.
Shift-cutting.
If divergence occurs, a simple expedient is to reduce the length of the shift vector, formula_62, by a fraction, "f"
For example, the length of the shift vector may be successively halved until the new value of the objective function is less than its value at the last iteration. The fraction, "f" could be optimized by a line search. As each trial value of "f" requires the objective function to be re-calculated it is not worth optimizing its value too stringently.
When using shift-cutting, the direction of the shift vector remains unchanged. This limits the applicability of the method to situations where the direction of the shift vector is not very different from what it would be if the objective function were approximately quadratic in the parameters, formula_64
Marquardt parameter.
If divergence occurs and the direction of the shift vector is so far from its "ideal" direction that shift-cutting is not very effective, that is, the fraction, "f" required to avoid divergence is very small, the direction must be changed. This can be achieved by using the Marquardt parameter. In this method the normal equations are modified
where formula_66 is the Marquardt parameter and I is an identity matrix. Increasing the value of formula_66 has the effect of changing both the direction and the length of the shift vector. The shift vector is rotated towards the direction of steepest descent
formula_69 is the steepest descent vector. So, when formula_66 becomes very large, the shift vector becomes a small fraction of the steepest descent vector.
Various strategies have been proposed for the determination of the Marquardt parameter. As with shift-cutting, it is wasteful to optimize this parameter too stringently. Rather, once a value has been found that brings about a reduction in the value of the objective function, that value of the parameter is carried to the next iteration, reduced if possible, or increased if need be. When reducing the value of the Marquardt parameter, there is a cut-off value below which it is safe to set it to zero, that is, to continue with the unmodified Gauss–Newton method. The cut-off value may be set equal to the smallest singular value of the Jacobian. A bound for this value is given by formula_71.
QR decomposition.
The minimum in the sum of squares can be found by a method that does not involve forming the normal equations. The residuals with the linearized model can be written as
The Jacobian is subjected to an orthogonal decomposition; the QR decomposition will serve to illustrate the process.
where Q is an orthogonal formula_74 matrix and R is an formula_75 matrix which is partitioned into an formula_76 block, formula_77, and a formula_78 zero block. formula_77 is upper triangular.
The residual vector is left-multiplied by formula_81.
This has no effect on the sum of squares since formula_83 because Q is orthogonal
The minimum value of "S" is attained when the upper block is zero. Therefore, the shift vector is found by solving
These equations are easily solved as R is upper triangular.
Singular value decomposition.
A variant of the method of orthogonal decomposition involves singular value decomposition, in which R is diagonalized by further orthogonal transformations.
where formula_86 is orthogonal, formula_87 is a diagonal matrix of singular values and formula_88 is the orthogonal matrix of the eigenvectors of formula_89 or equivalently the right singular vectors of formula_90. In this case the shift vector is given by
The relative simplicity of this expression is very useful in theoretical analysis of non-linear least squares. The application of singular value decomposition is discussed in detail in Lawson and Hanson.
Gradient methods.
There are many examples in the scientific literature where different methods have been used for non-linear data-fitting problems.
Direct search methods.
Direct search methods depend on evaluations of the objective function at a variety of parameter values and do not use derivatives at all. They offer alternatives to the use of numerical derivatives in the Gauss–Newton method and gradient methods.
More detailed descriptions of these, and other, methods are available, in "Numerical Recipes", together with computer code in various languages.


Hamming graph

Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics and computer science. Let "S" be a set of "q" elements and "d" a positive integer. The Hamming graph "H"("d","q") has vertex set "Sd", the set of ordered "d"-tuples of elements of "S", or sequences of length "d" from "S". Two vertices are adjacent if they differ in precisely one coordinate; that is, if their Hamming distance is one. The Hamming graph "H"("d","q") is, equivalently, the Cartesian product of "d" complete graphs "K""q".
In some cases, Hamming graphs may be considered more generally as the Cartesian products of complete graphs that may be of varying sizes. Unlike the Hamming graphs "H"("d","q"), the graphs in this more general class are not necessarily distance-regular, but they continue to be regular and vertex-transitive.
Applications.
The Hamming graphs are interesting in connection with error-correcting codes and association schemes, to name two areas. They have also been considered as a communications network topology in distributed computing.
Computational complexity.
It is possible in linear time to test whether a graph is a Hamming graph, and in the case that it is, find a labeling of it with tuples that realizes it as a Hamming graph.


Category algebra

In category theory, a field of mathematics, a category algebra is an associative algebra, defined for any locally finite category and commutative ring with unity. Category algebras generalize the notions of group algebras and incidence algebras, just as categories generalize the notions of groups and partially ordered sets.
Definition.
If the given category is finite (has finitely many objects and morphisms), then the following two definitions of the category algebra agree.
Group algebra-style definition.
Given a group "G" and a commutative ring "R", one can construct "RG", known as the group algebra; it is an "R"-module equipped with a multiplication. A group is the same as a category with a single object in which all morphisms are isomorphisms (where the elements of the group correspond to the morphisms of the category), so the following construction generalizes the definition of the group algebra from groups to arbitrary categories.
Let "C" be a category and "R" be a commutative ring with unity. Define "RC" (or "R"["C"]) to be the free "R"-module with basis consisting of the maps of "C". In other words, "RC" consists of formal linear combinations (which are finite sums) of the form formula_1, where "fi" are maps of "C", and "ai" are elements of the ring "R". Define a multiplication operation on "RC" as follows, using the composition operation in the category:
where formula_3 if their composition is not defined. This defines a binary operation on "RC", and moreover makes "RC" into an associative algebra over the ring "R". This algebra is called the category algebra of "C".
From a different perspective, elements of the free module "RC" could also be considered as functions from the maps of "C" to "R" which are finitely supported. Then the multiplication is described by a convolution: if formula_4 (thought of as functionals on the maps of "C"), then their product is defined as:
The latter sum is finite because the functions are finitely supported, and therefore formula_6.
Incidence algebra-style definition.
The definition used for incidence algebras assumes that the category "C" is locally finite (see below), is "dual" to the above definition, and defines a "different" object. This isn't a useful assumption for groups, as a group that is locally finite as a category is finite.
A locally finite category is one where every map can be written in only finitely many ways as the composition of two non-identity maps (not to be confused with the "has finite Hom-sets" meaning). The category algebra (in this sense) is defined as above, but allowing all coefficients to be non-zero.
In terms of formal sums, the elements are all formal sums
where there are no restrictions on the formula_8 (they can all be non-zero).
In terms of functions, the elements are any functions from the maps of "C" to "R", and multiplication is defined as convolution. The sum in the convolution is always finite because of the local finiteness assumption.
Dual.
The module dual of the category algebra (in the group algebra sense of the definition) is the space of all maps from the maps of "C" to "R", denoted "F"("C"), and has a natural coalgebra structure. Thus for a locally finite category, the dual of a category algebra (in the group algebra sense) is the category algebra (in the incidence algebra sense), and has both an algebra and coalgebra structure.


Suren Arakelov

Suren Yurievich Arakelov (, ) (born October 16, 1947 in Kharkiv) is a Soviet mathematician of Armenian descent known for developing Arakelov theory.
Biography.
Starting in 1965, Arakelov was a student of the Mathematics department of Moscow State University, where he graduated in 1971. The remarkable brilliance of his research career in this early stage was such that in
1974, he gave an invited talk at the International Congress of Mathematicians in Vancouver, even though it was only that same year that he received his
candidate of sciences degree from the Steklov Institute in Moscow, under the supervision of Igor Shafarevich. He then held the position of junior researcher at the Gubkin Russian State University of Oil and Gas in Moscow until 1979. During this period, however, he participated in public protests against the arrest of Alexander Solzhenitsyn, which some claim played a role in his being labeled as mentally ill by the Soviet authorities. In any case, he was being described as schizophrenic by 1976-1977 and was then confined to a mental hospital starting in 1979. This led Arakelov to cease his research activity and to instead pursue modest and conventional life goals. As of 2014 he lives in Moscow with his wife and children.
Arakelov theory.
Arakelov theory was exploited by Paul Vojta to give a new proof of the Mordell conjecture and by Gerd Faltings in his proof of Lang's generalization of the Mordell conjecture.


Weakly normal subgroup

In mathematics, in the field of group theory, a subgroup formula_1 of a group formula_2 is said to be weakly normal if whenever formula_3, we have formula_4.
Every pronormal subgroup is weakly normal.


Complete group

In mathematics, a group, , is said to be complete if every automorphism of is inner, and it is centerless; that is, it has a trivial outer automorphism group and trivial center.
Equivalently, a group is complete if the conjugation map, (sending an element to conjugation by ), is an isomorphism: injectivity implies that only conjugation by the identity element is the identity automorphism, meaning the group is centerless, while surjectivity implies it has no outer automorphisms.
Examples.
As an example, all the symmetric groups, , are complete except when . For the case , the group has a non-trivial center, while for the case , there is an outer automorphism.
The automorphism group of a simple group, , is an almost simple group; for a non-abelian simple group, , the automorphism group of is complete.
Properties.
A complete group is always isomorphic to its automorphism group (via sending an element to conjugation by that element), although the reverse need not hold: for example, the dihedral group of 8 elements is isomorphic to its automorphism group, but it is not complete. For a discussion, see .
Extensions of complete groups.
Assume that a group, , is a group extension given as a short exact sequence of groups
with kernel, , and quotient, . If the kernel, , is a complete group then the extension splits: is isomorphic to the direct product, . A proof using homomorphisms and exact sequences can be given in a natural way: The action of (by conjugation) on the normal subgroup, gives rise to a group homomorphism, . Since and has trivial center the homomorphism is surjective and has an obvious section given by the inclusion of in . The kernel of is the centralizer of in , and so is at least a semidirect product, , but the action of on is trivial, and so the product is direct. This proof is somewhat interesting since the original exact sequence is reversed during the proof.
This can be restated in terms of elements and internal conditions: If is a normal, complete subgroup of a group, , then is a direct product. The proof follows directly from the definition: is centerless giving is trivial. If is an element of then it induces an automorphism of by conjugation, but and this conjugation must be equal to conjugation by some element of . Then conjugation by is the identity on and so is in and every element, , of is a product in .


CUR matrix approximation

A CUR matrix approximation is a set of three matrices that, when multiplied together, closely approximate a given matrix. A CUR approximation can be used in the same way as the low-rank approximation of the Singular value decomposition (SVD). CUR approximations are less accurate than the SVD, but they offer two key advantages, both stemming from the fact that the rows and columns come from the original matrix (rather than left and right singular vectors):
Formally, a CUR matrix approximation of a matrix "A" is three matrices "C", "U", and "R" such that "C" is made from columns of "A", "R" is made from rows of "A", and that the product "CUR" closely approximates "A". Usually the CUR is selected to be a rank-"k" approximation, which means that "C" contains "k" columns of "A", "R" contains "k" rows of "A", and "U" is a "k"-by-"k" matrix. There are many possible CUR matrix approximations, and many CUR matrix approximations for a given rank.
The CUR matrix approximation is often used in place of the low-rank approximation of the SVD in principal component analysis. The CUR is less accurate, but the columns of the matrix "C" are taken from "A" and the rows of "R" are taken from "A". In PCA, each column of "A" contains a data sample; thus, the matrix "C" is made of a subset of data samples. This is much easier to interpret than the SVD's left singular vectors, which represent the data in a rotated space. Similarly, the matrix "R" is made of a subset of variables measured for each data sample. This is easier to comprehend than the SVD's right singular vectors, which are another rotations of the data in space.
Algorithms.
The CUR matrix approximation is not unique and there are multiple algorithms for computing one. One is ALGORITHMCUR.
Tensor.
Tensor-CURT decomposition
is a generalization of matrix-CUR decomposition. Formally, a CURT tensor approximation of a tensor "A" is three matrices and a (core-)tensor "C", "R", "T" and "U" such that "C" is made from columns of "A", "R" is made from rows of "A", "T" is made from tubes of "A" and that the product "U(C,R,T)" (where the formula_1-th entry of it is formula_2) closely approximates "A". Usually the CURT is selected to be a rank-"k" approximation, which means that "C" contains "k" columns of "A", "R" contains "k" rows of "A", "T" contains tubes of "A" and "U" is a "k"-by-"k"-by-"k" (core-)tensor.


Matrix consimilarity

In linear algebra, two "n"-by-"n" matrices "A" and "B" are called consimilar if
for some invertible formula_2 matrix formula_3, where formula_4 denotes the elementwise complex conjugation. So for real matrices similar by some real matrix formula_3, consimilarity is the same as matrix similarity.
Like ordinary similarity, consimilarity is an equivalence relation on the set of formula_2 matrices, and it is reasonable to ask what properties it preserves.
The theory of ordinary similarity arises as a result of studying linear transformations referred to different bases. Consimilarity arises as a result of studying antilinear transformations referred to different bases.
A matrix is consimilar to itself, its complex conjugate, its transpose and its adjoint matrix. Every matrix is consimilar to a real matrix and to a Hermitian matrix. There is a standard form for the consimilarity class, analogous to the Jordan normal form.


Abstract algebra

In algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras. The term "abstract algebra" was coined in the early 20th century to distinguish this area of study from the other parts of algebra.
Algebraic structures, with their associated homomorphisms, form mathematical categories. Category theory is a formalism that allows a unified way for expressing properties and constructions that are similar for various structures.
Universal algebra is a related subject that studies types of algebraic structures as single objects. For example, the structure of groups is a single object in universal algebra, which is called "variety of groups".
History.
As in other parts of mathematics, concrete problems and examples have played important roles in the development of abstract algebra. Through the end of the nineteenth century, manyperhaps mostof these problems were in some way related to the theory of algebraic equations. Major themes include:
Numerous textbooks in abstract algebra start with axiomatic definitions of various algebraic structures and then proceed to establish their properties. This creates a false impression that in algebra axioms had come first and then served as a motivation and as a basis of further study. The true order of historical development was almost exactly the opposite. For example, the hypercomplex numbers of the nineteenth century had kinematic and physical motivations but challenged comprehension. Most theories that are now recognized as parts of algebra started as collections of disparate facts from various branches of mathematics, acquired a common theme that served as a core around which various results were grouped, and finally became unified on a basis of a common set of concepts. An archetypical example of this progressive synthesis can be seen in the history of group theory.
Early group theory.
There were several threads in the early development of group theory, in modern language loosely corresponding to "number theory", "theory of equations", and "geometry".
Leonhard Euler considered algebraic operations on numbers modulo an integer—modular arithmetic—in his generalization of Fermat's little theorem. These investigations were taken much further by Carl Friedrich Gauss, who considered the structure of multiplicative groups of residues mod n and established many properties of cyclic and more general abelian groups that arise in this way. In his investigations of composition of binary quadratic forms, Gauss explicitly stated the associative law for the composition of forms, but like Euler before him, he seems to have been more interested in concrete results than in general theory. In 1870, Leopold Kronecker gave a definition of an abelian group in the context of ideal class groups of a number field, generalizing Gauss's work; but it appears he did not tie his definition with previous work on groups, particularly permutation groups. In 1882, considering the same question, Heinrich M. Weber realized the connection and gave a similar definition that involved the cancellation property but omitted the existence of the inverse element, which was sufficient in his context (finite groups).
Permutations were studied by Joseph-Louis Lagrange in his 1770 paper "Réflexions sur la résolution algébrique des équations (Thoughts on the algebraic solution of equations)" devoted to solutions of algebraic equations, in which he introduced Lagrange resolvents. Lagrange's goal was to understand why equations of third and fourth degree admit formulas for solutions, and he identified as key objects permutations of the roots. An important novel step taken by Lagrange in this paper was the abstract view of the roots, i.e. as symbols and not as numbers. However, he did not consider composition of permutations. Serendipitously, the first edition of Edward Waring's "Meditationes Algebraicae" ("Meditations on Algebra") appeared in the same year, with an expanded version published in 1782. Waring proved the fundamental theorem of symmetric polynomials, and specially considered the relation between the roots of a quartic equation and its resolvent cubic. "Mémoire sur la résolution des équations" ("Memoire on the Solving of Equations") of Alexandre Vandermonde (1771) developed the theory of symmetric functions from a slightly different angle, but like Lagrange, with the goal of understanding solvability of algebraic equations.
Paolo Ruffini was the first person to develop the theory of permutation groups, and like his predecessors, also in the context of solving algebraic equations. His goal was to establish the impossibility of an algebraic solution to a general algebraic equation of degree greater than four. En route to this goal he introduced the notion of the order of an element of a group, conjugacy, the cycle decomposition of elements of permutation groups and the notions of primitive and imprimitive and proved some important theorems relating these concepts, such as
However, he got by without formalizing the concept of a group, or even of a permutation group.
The next step was taken by Évariste Galois in 1832, although his work remained unpublished until 1846, when he considered for the first time what is now called the "closure property" of a group of permutations, which he expressed as
The theory of permutation groups received further far-reaching development in the hands of Augustin Cauchy and Camille Jordan, both through introduction of new concepts and, primarily, a great wealth of results about special classes of permutation groups and even some general theorems. Among other things, Jordan defined a notion of isomorphism, still in the context of permutation groups and, incidentally, it was he who put the term "group" in wide use.
The abstract notion of a group appeared for the first time in Arthur Cayley's papers in 1854. Cayley realized that a group need not be a permutation group (or even "finite"), and may instead consist of matrices, whose algebraic properties, such as multiplication and inverses, he systematically investigated in succeeding years. Much later Cayley would revisit the question whether abstract groups were more general than permutation groups, and establish that, in fact, any group is isomorphic to a group of permutations.
Modern algebra.
The end of the 19th and the beginning of the 20th century saw a shift in the methodology of mathematics. Abstract algebra emerged around the start of the 20th century, under the name "modern algebra". Its study was part of the drive for more intellectual rigor in mathematics. Initially, the assumptions in classical algebra, on which the whole of mathematics (and major parts of the natural sciences) depend, took the form of axiomatic systems. No longer satisfied with establishing properties of concrete objects, mathematicians started to turn their attention to general theory. Formal definitions of certain algebraic structures began to emerge in the 19th century. For example, results about various groups of permutations came to be seen as instances of general theorems that concern a general notion of an "abstract group". Questions of structure and classification of various mathematical objects came to forefront.
These processes were occurring throughout all of mathematics, but became especially pronounced in algebra. Formal definition through primitive operations and axioms were proposed for many basic algebraic structures, such as groups, rings, and fields. Hence such things as group theory and ring theory took their places in pure mathematics. The algebraic investigations of general fields by Ernst Steinitz and of commutative and then general rings by David Hilbert, Emil Artin and Emmy Noether, building up on the work of Ernst Kummer, Leopold Kronecker and Richard Dedekind, who had considered ideals in commutative rings, and of Georg Frobenius and Issai Schur, concerning representation theory of groups, came to define abstract algebra. These developments of the last quarter of the 19th century and the first quarter of 20th century were systematically exposed in Bartel van der Waerden's "Moderne Algebra", the two-volume monograph published in 1930–1931 that forever changed for the mathematical world the meaning of the word "algebra" from "the theory of equations" to the "theory of algebraic structures".
Basic concepts.
By abstracting away various amounts of detail, mathematicians have defined various algebraic structures that are used in many areas of mathematics. For instance, almost all systems studied are sets, to which the theorems of set theory apply. Those sets that have a certain binary operation defined on them form magmas, to which the concepts concerning magmas, as well those concerning sets, apply. We can add additional constraints on the algebraic structure, such as associativity (to form semigroups); identity, and inverses (to form groups); and other more complex structures. With additional structure, more theorems could be proved, but the generality is reduced. The "hierarchy" of algebraic objects (in terms of generality) creates a hierarchy of the corresponding theories: for instance, the theorems of group theory may be used when studying rings (algebraic objects that have two binary operations with certain axioms) since a ring is a group over one of its operations. In general there is a balance between the amount of generality and the richness of the theory: more general structures have usually fewer nontrivial theorems and fewer applications.
Examples of algebraic structures with a single binary operation are:
Examples involving several operations include:
Applications.
Because of its generality, abstract algebra is used in many fields of mathematics and science. For instance, algebraic topology uses algebraic objects to study topologies. The Poincaré conjecture, proved in 2003, asserts that the fundamental group of a manifold, which encodes information about connectedness, can be used to determine whether a manifold is a sphere or not. Algebraic number theory studies various number rings that generalize the set of integers. Using tools of algebraic number theory, Andrew Wiles proved Fermat's Last Theorem.
In physics, groups are used to represent symmetry operations, and the usage of group theory could simplify differential equations. In gauge theory, the requirement of local symmetry can be used to deduce the equations describing a system. The groups that describe those symmetries are Lie groups, and the study of Lie groups and Lie algebras reveals much about the physical system; for instance, the number of force carriers in a theory is equal to the dimension of the Lie algebra, and these bosons interact with the force they mediate if the Lie algebra is nonabelian.