Arnoldi iteration

In numerical linear algebra, the Arnoldi iteration is an eigenvalue algorithm and an important example of an iterative method. Arnoldi finds an approximation to the eigenvalues and eigenvectors of general (possibly non-Hermitian) matrices by constructing an orthonormal basis of the Krylov subspace, which makes it particularly useful when dealing with large sparse matrices.
The Arnoldi method belongs to a class of linear algebra algorithms that give a partial result after a small number of iterations, in contrast to so-called "direct methods" which must complete to give any useful results (see for example, Householder transformation). The partial result in this case being the first few vectors of the basis the algorithm is building.
When applied to Hermitian matrices it reduces to the Lanczos algorithm. The Arnoldi iteration was invented by W. E. Arnoldi in 1951.
Krylov subspaces and the power iteration.
An intuitive method for finding the largest (in absolute value) eigenvalue of a given "m" × "m" matrix formula_1 is the power iteration: starting with an arbitrary initial vector b, calculate "Ab", "A"2"b", "A"3"b",… normalizing the result after every application of the matrix "A".
This sequence converges to the eigenvector corresponding to the eigenvalue with the largest absolute value, formula_2. However, much potentially useful computation is wasted by using only the final result, formula_3. This suggests that instead, we form the so-called "Krylov matrix":
The columns of this matrix are not in general orthogonal, but we can extract an orthogonal basis, via a method such as Gram–Schmidt orthogonalization. The resulting set of vectors is thus an orthogonal basis of the "Krylov subspace", formula_5. We may expect the vectors of this basis to span good approximations of the eigenvectors corresponding to the formula_6 largest eigenvalues, for the same reason that formula_3 approximates the dominant eigenvector.
The Arnoldi iteration.
The Arnoldi iteration uses the modified Gram–Schmidt process to produce a sequence of orthonormal vectors, "q"1, "q"2, "q"3, …, called the "Arnoldi vectors", such that for every "n", the vectors "q"1, …, "q""n" span the Krylov subspace formula_8. Explicitly, the algorithm is as follows:
The "j"-loop projects out the component of formula_14 in the directions of formula_15. This ensures the orthogonality of all the generated vectors.
The algorithm breaks down when "q""k" is the zero vector. This happens when the minimal polynomial of "A" is of degree "k". In most applications of the Arnoldi iteration, including the eigenvalue algorithm below and GMRES, the algorithm has converged at this point.
Every step of the "k"-loop takes one matrix-vector product and approximately 4"mk" floating point operations.
In the programming language python:
import numpy as np
def arnoldi_iteration(A, b, n: int):
 """Computes a basis of the (n + 1)-Krylov subspace of A: the space
 spanned by {b, Ab, ..., A^n b}.
 Arguments
 A: m × m array
 b: initial vector (length m)
 n: dimension of Krylov subspace, must be >= 1
 Returns
 Q: m x (n + 1) array, the columns are an orthonormal basis of the
 Krylov subspace.
 h: (n + 1) x n array, A on basis Q. It is upper Hessenberg.
 m = A.shape[0]
 h = np.zeros((n + 1, n))
 Q = np.zeros((m, n + 1))
 q = b / np.linalg.norm(b) # Normalize the input vector
 Q[:, 0] = q # Use it as the first Krylov vector
 for k in range(n):
 v = A.dot(q) # Generate a new candidate vector
 for j in range(k + 1): # Subtract the projections on previous vectors
 h[j, k] = np.dot(Q[:, j].conj(), v)
 v = v - h[j, k] * Q[:, j]
 h[k + 1, k] = np.linalg.norm(v)
 eps = 1e-12 # If v is shorter than this threshold it is the zero vector
 if h[k + 1, k] > eps: # Add the produced vector to the list, unless
 q = v / h[k + 1, k] # the zero vector is produced.
 Q[:, k + 1] = q
 else: # If that happens, stop iterating.
 return Q, h
 return Q, h
Properties of the Arnoldi iteration.
Let "Q""n" denote the "m"-by-"n" matrix formed by the first "n" Arnoldi vectors "q"1, "q"2, …, "q""n", and let "H""n" be the (upper Hessenberg) matrix formed by the numbers "h""j","k" computed by the algorithm:
The orthogonalization method has to be specifically chosen such that the lower Arnoldi/Krylov components are removed from higher Krylov vectors. As formula_17 can be expressed in terms of "q"1, …, "q""i+1" by construction, they are orthogonal to "q"i+2, …, "q""n",
We then have
The matrix "H""n" can be viewed as "A" in the subspace formula_8 with the Arnoldi vectors as an orthogonal basis; "A" is orthogonally projected onto formula_8. The matrix "H""n" can be characterized by the following optimality condition. The characteristic polynomial of "H""n" minimizes ||"p"("A")"q"1||2 among all monic polynomials of degree "n". This optimality problem has a unique solution if and only if the Arnoldi iteration does not break down.
The relation between the "Q" matrices in subsequent iterations is given by
where
is an ("n"+1)-by-"n" matrix formed by adding an extra row to "H""n".
Finding eigenvalues with the Arnoldi iteration.
The idea of the Arnoldi iteration as an eigenvalue algorithm is to compute the eigenvalues in the Krylov subspace. The eigenvalues of "H""n" are called the "Ritz eigenvalues". Since "H""n" is a Hessenberg matrix of modest size, its eigenvalues can be computed efficiently, for instance with the QR algorithm, or somewhat related, Francis's algorithm. Also Francis's algorithm itself can be considered to be related to power iterations, operating on nested Krylov subspace. In fact, the most basic form of Francis's algorithm appears to be to choose "b" to be equal to "Ae"1, and extending "n" to the full dimension of "A". Improved versions include one or more shifts, and higher powers of "A" may be applied in a single steps.
This is an example of the Rayleigh-Ritz method.
It is often observed in practice that some of the Ritz eigenvalues converge to eigenvalues of "A". Since "H""n" is "n"-by-"n", it has at most "n" eigenvalues, and not all eigenvalues of "A" can be approximated. Typically, the Ritz eigenvalues converge to the largest eigenvalues of "A". To get the smallest eigenvalues of "A", the inverse (operation) of "A" should be used instead. This can be related to the characterization of "H""n" as the matrix whose characteristic polynomial minimizes ||"p"("A")"q"1|| in the following way. A good way to get "p"("A") small is to choose the polynomial "p" such that "p"("x") is small whenever "x" is an eigenvalue of "A". Hence, the zeros of "p" (and thus the Ritz eigenvalues) will be close to the eigenvalues of "A".
However, the details are not fully understood yet. This is in contrast to the case where "A" is symmetric. In that situation, the Arnoldi iteration becomes the Lanczos iteration, for which the theory is more complete.
Implicitly restarted Arnoldi method (IRAM).
Due to practical storage consideration, common implementations of Arnoldi methods typically restart after some number of iterations. One major innovation in restarting was due to Lehoucq and Sorensen who proposed the Implicitly Restarted Arnoldi Method. They also implemented the algorithm in a freely available software package called ARPACK. This has spurred a number of other variations including Implicitly Restarted Lanczos method. It also influenced how other restarted methods are analyzed.
Theoretical results have shown that convergence improves with an increase in the Krylov subspace dimension "n". However, an a-priori value of "n" which would lead to optimal convergence is not known. Recently a dynamic switching strategy has been proposed which fluctuates the dimension "n" before each restart and thus leads to acceleration in the rate of convergence.
See also.
The generalized minimal residual method (GMRES) is a method for solving "Ax" = "b" based on Arnoldi iteration.


Fedor Bogomolov

Fedor Alekseyevich Bogomolov (born 26 September 1946) (Фёдор Алексеевич Богомолов) is a Russian and American mathematician, known for his research in algebraic geometry and number theory. Bogomolov worked at the Steklov Institute in Moscow before he became a professor at the Courant Institute in New York. He is most famous for his pioneering work on hyperkähler manifolds.
Born in Moscow, Bogomolov graduated from Moscow State University, Faculty of Mechanics and Mathematics, and earned his doctorate ("candidate degree") in 1973, at the Steklov Institute. His doctoral advisor was Sergei Novikov.
Geometry of Kähler manifolds.
Bogomolov's Ph.D. thesis was entitled "Compact Kähler varieties". In his early papers Bogomolov studied the manifolds which were later called Calabi–Yau and hyperkähler. He proved a decomposition theorem, used for the classification of manifolds with trivial canonical class. It has been re-proven using the Calabi–Yau theorem and Berger's classification of Riemannian holonomies, and is foundational for modern string theory.
In the late 1970s and early 1980s Bogomolov studied the deformation theory for manifolds with trivial canonical class. He discovered what is now known as Bogomolov–Tian–Todorov theorem, proving the smoothness and un-obstructedness of the deformation space for hyperkaehler manifolds (in 1978 paper) and then extended this to all Calabi–Yau manifolds in the 1981 IHES preprint. Some years later, this theorem became the mathematical foundation for Mirror Symmetry.
While studying the deformation theory of hyperkähler manifolds, Bogomolov discovered what is now known as the Bogomolov–Beauville–Fujiki form on formula_1. Studying properties of this form, Bogomolov erroneously concluded that compact hyperkaehler manifolds do not exist, with the exception of K3 surfaces, tori, and their products. Almost four years passed since this publication before Akira Fujiki found a counterexample.
Other works in algebraic geometry.
Bogomolov's paper on "Holomorphic tensors and vector bundles on projective manifolds" proves what is now known as the Bogomolov–Miyaoka–Yau inequality, and also proves that a stable bundle on a surface, restricted to a curve of sufficiently big degree, remains stable. In "Families of curves on a surface of general type", Bogomolov laid the foundations to the now popular approach to the theory of diophantine equations through geometry of hyperbolic manifolds and dynamical systems. In this paper Bogomolov proved that on any surface of general type with formula_2, there is only a finite number of curves of bounded genus. Some 25 years later, Michael McQuillan extended this argument to prove the famous Green–Griffiths conjecture for such surfaces. In "Classification of surfaces of class formula_3 with formula_4", Bogomolov made the first step in a famously difficult (and still unresolved) problem of classification of surfaces of Kodaira class VII. These are compact complex surfaces with formula_5. If they are in addition minimal, they are called "class formula_3". Kunihiko Kodaira classified all compact complex surfaces except class VII, which are still not understood, except the case formula_4 (Bogomolov) and formula_8 (Andrei Teleman, 2005).
Other works in arithmetic geometry.
Bogomolov has contributed to several aspects of arithmetic geometry. He posed the Bogomolov conjecture about small points. Twenty years ago he contributed a proof (among many proofs) of the geometric Szpiro's conjecture which appears to be the nearest to Shinichi Mochizuki's claimed proof of the arithmetic Szpiro conjecture.
Later career.
Bogomolov obtained his Habilitation (Russian "Dr. of Sciences") in 1983. In 1994, he emigrated to the United States and became a full professor at the Courant Institute. He is very active in algebraic geometry and number theory. From 2009 till March 2014 he served as the Editor-in-Chief of the Central European Journal of Mathematics. Since 2014 he serves as the Editor-in-Chief of the European Journal of Mathematics. Since 2010 he is the academic supervisor of the HSE Laboratory of algebraic geometry and its applications. Bogomolov has extensively contributed to the revival of Russian mathematics. Three major international conferences commemorating his 70th birthday were held in 2016: at the Courant Institute, the University of Nottingham, and the Higher School of Economics in Moscow.


Diagonalizable matrix

In linear algebra, a square matrix formula_1 is called diagonalizable or non-defective if it is similar to a diagonal matrix, i.e., if there exists an invertible matrix formula_2 and a diagonal matrix formula_3 such that or equivalently (Such formula_3 are not unique.) For a finite-dimensional vector space a linear map formula_5 is called diagonalizable if there exists an ordered basis of formula_6 consisting of eigenvectors of formula_7. These definitions are equivalent: if formula_7 has a matrix representation formula_9 as above, then the column vectors of formula_2 form a basis consisting of eigenvectors of and the diagonal entries of formula_3 are the corresponding eigenvalues of with respect to this eigenvector basis, formula_1 is represented by Diagonalization is the process of finding the above formula_2 and
Diagonalizable matrices and maps are especially easy for computations, once their eigenvalues and eigenvectors are known. One can raise a diagonal matrix formula_3 to a power by simply raising the diagonal entries to that power, and the determinant of a diagonal matrix is simply the product of all diagonal entries; such computations generalize easily to Geometrically, a diagonalizable matrix is an inhomogeneous dilation (or "anisotropic scaling") — it scales the space, as does a "homogeneous dilation", but by a different factor along each eigenvector axis, the factor given by the corresponding eigenvalue.
A square matrix that is not diagonalizable is called "defective". It can happen that a matrix formula_1 with real entries is defective over the real numbers, meaning that formula_9 is impossible for any invertible formula_2 and diagonal formula_3 with real entries, but it is possible with complex entries, so that formula_1 is diagonalizable over the complex numbers. For example, this is the case for a generic rotation matrix.
Many results for diagonalizable matrices hold only over an algebraically closed field (such as the complex numbers). In this case, diagonalizable matrices are dense in the space of all matrices, which means any defective matrix can be deformed into a diagonalizable matrix by a small perturbation; and the Jordan normal form theorem states that any matrix is uniquely the sum of a diagonalizable matrix and a nilpotent matrix. Over an algebraically closed field, diagonalizable matrices are equivalent to semi-simple matrices.
Definition.
A square formula_20 matrix formula_1 over a field formula_22 is called diagonalizable or nondefective if there exists an invertible matrix formula_2 such that formula_24 is a diagonal matrix. Formally,
Characterization.
The fundamental fact about diagonalizable maps and matrices is expressed by the following:
Another characterization: A matrix or linear map is diagonalizable over the field formula_22 if and only if its minimal polynomial is a product of distinct linear factors over (Put another way, a matrix is diagonalizable if and only if all of its elementary divisors are linear.)
The following sufficient (but not necessary) condition is often useful.
Let formula_1 be a matrix over If formula_1 is diagonalizable, then so is any power of it. Conversely, if formula_1 is invertible, formula_22 is algebraically closed, and formula_61 is diagonalizable for some formula_28 that is not an integer multiple of the characteristic of then formula_1 is diagonalizable. Proof: If formula_61 is diagonalizable, then formula_1 is annihilated by some polynomial which has no multiple root (since and is divided by the minimal polynomial of
Over the complex numbers formula_66, almost every matrix is diagonalizable. More precisely: the set of complex formula_20 matrices that are "not" diagonalizable over considered as a subset of has Lebesgue measure zero. One can also say that the diagonalizable matrices form a dense subset with respect to the Zariski topology: the non-diagonalizable matrices lie inside the vanishing set of the discriminant of the characteristic polynomial, which is a hypersurface. From that follows also density in the usual ("strong") topology given by a norm. The same is not true over
The Jordan–Chevalley decomposition expresses an operator as the sum of its semisimple (i.e., diagonalizable) part and its nilpotent part. Hence, a matrix is diagonalizable if and only if its nilpotent part is zero. Put in another way, a matrix is diagonalizable if each block in its Jordan form has no nilpotent part; i.e., each "block" is a one-by-one matrix.
Diagonalization.
If a matrix formula_1 can be diagonalized, that is,
then:
Writing formula_2 as a block matrix of its column vectors formula_72
the above equation can be rewritten as
So the column vectors of formula_2 are right eigenvectors of and the corresponding diagonal entry is the corresponding eigenvalue. The invertibility of formula_2 also suggests that the eigenvectors are linearly independent and form a basis of This is the necessary and sufficient condition for diagonalizability and the canonical approach of diagonalization. The row vectors of formula_77 are the left eigenvectors of
When a complex matrix formula_78 is a Hermitian matrix (or more generally a normal matrix), eigenvectors of formula_1 can be chosen to form an orthonormal basis of and formula_2 can be chosen to be a unitary matrix. If in addition, formula_81 is a real symmetric matrix, then its eigenvectors can be chosen to be an orthonormal basis of formula_82 and formula_2 can be chosen to be an orthogonal matrix.
For most practical work matrices are diagonalized numerically using computer software. Many algorithms exist to accomplish this.
Simultaneous diagonalization.
A set of matrices is said to be "simultaneously diagonalizable" if there exists a single invertible matrix formula_2 such that formula_24 is a diagonal matrix for every formula_1 in the set. The following theorem characterizes simultaneously diagonalizable matrices: A set of diagonalizable matrices commutes if and only if the set is simultaneously diagonalizable.
The set of all formula_20 diagonalizable matrices (over with formula_88 is not simultaneously diagonalizable. For instance, the matrices
are diagonalizable but not simultaneously diagonalizable because they do not commute.
A set consists of commuting normal matrices if and only if it is simultaneously diagonalizable by a unitary matrix; that is, there exists a unitary matrix formula_90 such that formula_91 is diagonal for every formula_1 in the set.
In the language of Lie theory, a set of simultaneously diagonalizable matrices generate a toral Lie algebra.
Examples.
Matrices that are not diagonalizable.
In general, a rotation matrix is not diagonalizable over the reals, but all rotation matrices are diagonalizable over the complex field. Even if a matrix is not diagonalizable, it is always possible to "do the best one can", and find a matrix with the same properties consisting of eigenvalues on the leading diagonal, and either ones or zeroes on the superdiagonal – known as Jordan normal form.
Some matrices are not diagonalizable over any field, most notably nonzero nilpotent matrices. This happens more generally if the algebraic and geometric multiplicities of an eigenvalue do not coincide. For instance, consider
This matrix is not diagonalizable: there is no matrix formula_90 such that formula_98 is a diagonal matrix. Indeed, formula_99 has one eigenvalue (namely zero) and this eigenvalue has algebraic multiplicity 2 and geometric multiplicity 1.
Some real matrices are not diagonalizable over the reals. Consider for instance the matrix
The matrix formula_101 does not have any real eigenvalues, so there is no real matrix formula_102 such that formula_103 is a diagonal matrix. However, we can diagonalize formula_101 if we allow complex numbers. Indeed, if we take
then formula_103 is diagonal. It is easy to find that formula_101 is the rotation matrix which rotates counterclockwise by angle formula_108
Note that the above examples show that the sum of diagonalizable matrices need not be diagonalizable.
How to diagonalize a matrix.
Diagonalizing a matrix is the same process as finding its eigenvalues and eigenvectors, in the case that the eigenvectors form a basis. For example, consider the matrix
The roots of the characteristic polynomial formula_110 are the eigenvalues Solving the linear system formula_111 gives the eigenvectors formula_112 and while formula_113 gives that is, formula_114 for These vectors form a basis of so we can assemble them as the column vectors of a change-of-basis matrix formula_2 to get:
formula_116
We may see this equation in terms of transformations: formula_2 takes the standard basis to the eigenbasis, so we have:
formula_118
so that formula_119 has the standard basis as its eigenvectors, which is the defining property of
Note that there is no preferred order of the eigenvectors in changing the order of the eigenvectors in formula_2 just changes the order of the eigenvalues in the diagonalized form of
Application to matrix functions.
Diagonalization can be used to efficiently compute the powers of a matrix
and the latter is easy to calculate since it only involves the powers of a diagonal matrix. For example, for the matrix formula_1 with eigenvalues formula_123 in the example above we compute:
This approach can be generalized to matrix exponential and other matrix functions that can be defined as power series. For example, defining we have:
This is particularly useful in finding closed form expressions for terms of linear recursive sequences, such as the Fibonacci numbers.
Particular application.
For example, consider the following matrix:
Calculating the various powers of formula_127 reveals a surprising pattern:
The above phenomenon can be explained by diagonalizing To accomplish this, we need a basis of formula_129 consisting of eigenvectors of One such eigenvector basis is given by
where e"i" denotes the standard basis of R"n". The reverse change of basis is given by
Straightforward calculations show that
Thus, "a" and "b" are the eigenvalues corresponding to u and v, respectively. By linearity of matrix multiplication, we have that
Switching back to the standard basis, we have
The preceding relations, expressed in matrix form, are
thereby explaining the above phenomenon.
Quantum mechanical application.
In quantum mechanical and quantum chemical computations matrix diagonalization is one of the most frequently applied numerical processes. The basic reason is that the time-independent Schrödinger equation is an eigenvalue equation, albeit in most of the physical situations on an infinite dimensional space (a Hilbert space).
A very common approximation is to truncate Hilbert space to finite dimension, after which the Schrödinger equation can be formulated as an eigenvalue problem of a real symmetric, or complex Hermitian matrix. Formally this approximation is founded on the variational principle, valid for Hamiltonians that are bounded from below.
First-order perturbation theory also leads to matrix eigenvalue problem for degenerate states.


Nullspace property

In compressed sensing, the nullspace property gives necessary and sufficient conditions on the reconstruction of sparse signals using the techniques of formula_1-relaxation. The term "nullspace property" originates from Cohen, Dahmen, and DeVore. The nullspace property is often difficult to check in practice, and the restricted isometry property is a more modern condition in the field of compressed sensing.
The technique of formula_1-relaxation.
The non-convex formula_3-minimization problem,
formula_4 subject to formula_5,
is a standard problem in compressed sensing. However, formula_3-minimization is known to be NP-hard in general. As such, the technique of formula_1-relaxation is sometimes employed to circumvent the difficulties of signal reconstruction using the formula_3-norm. In formula_1-relaxation, the formula_1 problem,
formula_11 subject to formula_5,
is solved in place of the formula_3 problem. Note that this relaxation is convex and hence amenable to the standard techniques of linear programming - a computationally desirable feature. Naturally we wish to know when formula_1-relaxation will give the same answer as the formula_3 problem. The nullspace property is one way to guarantee agreement.
Definition.
An formula_16 complex matrix formula_17 has the nullspace property of order formula_18, if for all index sets formula_19 with formula_20 we have that: formula_21 for all formula_22.
Recovery Condition.
The following theorem gives necessary and sufficient condition on the recoverability of a given formula_18-sparse vector in formula_24. The proof of the theorem is a standard one, and the proof supplied here is summarized from Holger Rauhut.
formula_25 Let formula_17 be a formula_16 complex matrix. Then every formula_18-sparse signal formula_29 is the unique solution to the formula_1-relaxation problem with formula_31 if and only if formula_17 satisfies the nullspace property with order formula_18.
formula_34 For the forwards direction notice that formula_35 and formula_36 are distinct vectors with formula_37 by the linearity of formula_17, and hence by uniqueness we must have formula_21 as desired. For the backwards direction, let formula_40 be formula_18-sparse and formula_42 another (not necessary formula_18-sparse) vector such that formula_44 and formula_45. Define the (non-zero) vector formula_46 and notice that it lies in the nullspace of formula_17. Call formula_19 the support of formula_40, and then the result follows from an elementary application of the triangle inequality: formula_50, establishing the minimality of formula_40. formula_52


Finite module


Ascending chain condition on principal ideals

In abstract algebra, the ascending chain condition can be applied to the posets of principal left, principal right, or principal two-sided ideals of a ring, partially ordered by inclusion. The ascending chain condition on principal ideals (abbreviated to ACCP) is satisfied if there is no infinite strictly ascending chain of principal ideals of the given type (left/right/two-sided) in the ring, or said another way, every ascending chain is eventually constant.
The counterpart descending chain condition may also be applied to these posets, however there is currently no need for the terminology "DCCP" since such rings are already called left or right perfect rings. (See " below.)
Noetherian rings (e.g. principal ideal domains) are typical examples, but some important non-Noetherian rings also satisfy (ACCP), notably unique factorization domains and left or right perfect rings.
Commutative rings.
It is well known that a nonzero nonunit in a Noetherian integral domain factors into irreducibles. The proof of this relies on only (ACCP) not (ACC), so in any integral domain with (ACCP), an irreducible factorization exists. (In other words, any integral domains with (ACCP) are atomic. But the converse is false, as shown in .) Such a factorization may not be unique; the usual way to establish uniqueness of factorizations uses Euclid's lemma, which requires factors to be prime rather than just irreducible. Indeed, one has the following characterization: let "A" be an integral domain. Then the following are equivalent.
The so-called Nagata criterion holds for an integral domain "A" satisfying (ACCP): Let "S" be a multiplicatively closed subset of "A" generated by prime elements. If the localization "S"−1"A" is a UFD, so is "A". (Note that the converse of this is trivial.)
An integral domain "A" satisfies (ACCP) if and only if the polynomial ring "A"["t"] does. The analogous fact is false if "A" is not an integral domain.
An integral domain where every finitely generated ideal is principal (that is, a Bézout domain) satisfies (ACCP) if and only if it is a principal ideal domain.
The ring Z+"X"Q["X"] of all rational polynomials with integral constant term is an example of an integral domain (actually a GCD domain) that does not satisfy (ACCP), for the chain of principal ideals
is non-terminating.
Noncommutative rings.
In the noncommutative case, it becomes necessary to distinguish the right ACCP from left ACCP. The former only requires the poset of ideals of the form "xR" to satisfy the ascending chain condition, and the latter only examines the poset of ideals of the form "Rx".
A theorem of Hyman Bass in now known as "Bass' Theorem P" showed that the "descending chain condition" on principal "left" ideals of a ring "R" is equivalent to "R" being a "right" perfect ring. D. Jonah showed in that there is a side-switching connection between the ACCP and perfect rings. It was shown that if "R" is right perfect (satisfies right DCCP), then "R" satisfies the left ACCP, and symmetrically, if "R" is left perfect (satisfies left DCCP), then it satisfies the right ACCP. The converses are not true, and the above switches between "left" and "right" are not typos.
Whether the ACCP holds on the right or left side of "R", it implies that "R" has no infinite set of nonzero orthogonal idempotents, and that "R" is a Dedekind finite ring.


Stephen R. Doty

Stephen Richard Doty (born April 16, 1953) is an American mathematician specializing in algebraic representation theory (especially modular representation theory).
He earned a doctorate in mathematics from University of Notre Dame in 1982 under the supervision of Warren J. Wong with dissertation "The Submodule Structure of Weyl Modules for Groups of Type An". After post-doctoral positions at University of Washington and University of Notre Dame, he joined the faculty at Loyola University Chicago in 1987.
In 2007 Doty was named the Inaugural Yip Fellow of Magdalene College, Cambridge University. In 2009 he was a Mercator Professor in Germany.


Differential of the first kind

In mathematics, differential of the first kind is a traditional term used in the theories of Riemann surfaces (more generally, complex manifolds) and algebraic curves (more generally, algebraic varieties), for everywhere-regular differential 1-forms. Given a complex manifold "M", a differential of the first kind ω is therefore the same thing as a 1-form that is everywhere holomorphic; on an algebraic variety "V" that is non-singular it would be a global section of the coherent sheaf Ω1 of Kähler differentials. In either case the definition has its origins in the theory of abelian integrals.
The dimension of the space of differentials of the first kind, by means of this identification, is the Hodge number
The differentials of the first kind, when integrated along paths, give rise to integrals that generalise the elliptic integrals to all curves over the complex numbers. They include for example the hyperelliptic integrals of type
where "Q" is a square-free polynomial of any given degree > 4. The allowable power "k" has to be determined by analysis of the possible pole at the point at infinity on the corresponding hyperelliptic curve. When this is done, one finds that the condition is
or in other words, "k" at most 1 for degree of "Q" 5 or 6, at most 2 for degree 7 or 8, and so on (as "g" = [(1+ deg "Q")/2]).
Quite generally, as this example illustrates, for a compact Riemann surface or algebraic curve, the Hodge number is the genus "g". For the case of algebraic surfaces, this is the quantity known classically as the irregularity "q". It is also, in general, the dimension of the Albanese variety, which takes the place of the Jacobian variety.
Differentials of the second and third kind.
The traditional terminology also included differentials of the second kind and of the third kind. The idea behind this has been supported by modern theories of algebraic differential forms, both from the side of more Hodge theory, and through the use of morphisms to commutative algebraic groups.
The Weierstrass zeta function was called an "integral of the second kind" in elliptic function theory; it is a logarithmic derivative of a theta function, and therefore has simple poles, with integer residues. The decomposition of a (meromorphic) elliptic function into pieces of 'three kinds' parallels the representation as (i) a constant, plus (ii) a linear combination of translates of the Weierstrass zeta function, plus (iii) a function with arbitrary poles but no residues at them.
The same type of decomposition exists in general, "mutatis mutandis", though the terminology is not completely consistent. In the algebraic group (generalized Jacobian) theory the three kinds are abelian varieties, algebraic tori, and affine spaces, and the decomposition is in terms of a composition series.
On the other hand, a meromorphic abelian differential of the "second kind" has traditionally been one with residues at all poles being zero. One of the third kind is one where all poles are simple. There is a higher-dimensional analogue available, using the Poincaré residue.


Degree of an algebraic variety

In mathematics, the degree of an affine or projective variety of dimension is the number of intersection points of the variety
with hyperplanes in general position. For an algebraic set, the intersection points must be counted with their intersection multiplicity, because of the possibility of multiple components. For (irreducible) varieties, if one takes into account the multiplicities and, in the affine case, the points at infinity, the hypothesis of "general position" may be replaced by the much weaker condition that the intersection of the variety has the dimension zero (that is, consists of a finite number of points). This is a generalization of Bézout's theorem (For a proof, see ).
The degree is not an intrinsic property of the variety, as it depends on a specific embedding of the variety in an affine or projective space.
The degree of a hypersurface is equal to the total degree of its defining equation. A generalization of Bézout's theorem asserts that, if an intersection of projective hypersurfaces has codimension , then the degree of the intersection is the product of the degrees of the hypersurfaces.
The degree of a projective variety is the evaluation at of the numerator of the Hilbert series of its coordinate ring. It follows that, given the equations of the variety, the degree may be computed from a Gröbner basis of the ideal of these equations.
Definition.
For "V" embedded in a projective space "P""n" and defined over some algebraically closed field "K", the degree "d" of "V" is the number of points of intersection of "V", defined over "K", with a linear subspace "L" in general position, such that
Here dim("V") is the dimension of "V", and the codimension of "L" will be equal to that dimension. The degree "d" is an extrinsic quantity, and not intrinsic as a property of "V". For example, the projective line has an (essentially unique) embedding of degree "n" in "P""n".
Properties.
The degree of a hypersurface "F" = 0 is the same as the total degree of the homogeneous polynomial "F" defining it (granted, in case "F" has repeated factors, that intersection theory is used to count intersections with multiplicity, as in Bézout's theorem).
Other approaches.
For a more sophisticated approach, the linear system of divisors defining the embedding of "V" can be related to the line bundle or invertible sheaf defining the embedding by its space of sections. The tautological line bundle on "P""n" pulls back to "V". The degree determines the first Chern class. The degree can also be computed in the cohomology ring of "P""n", or Chow ring, with the class of a hyperplane intersecting the class of "V" an appropriate number of times.
Extending Bézout's theorem.
The degree can be used to generalize Bézout's theorem in an expected way to intersections of "n" hypersurfaces in "P""n".


Quasi-Hopf algebra

A quasi-Hopf algebra is a generalization of a Hopf algebra, which was defined by the Russian mathematician Vladimir Drinfeld in 1989.
A "quasi-Hopf algebra" is a quasi-bialgebra formula_1 for which there exist formula_2 and a bijective antihomomorphism "S" (antipode) of formula_3 such that
for all formula_6 and where
and
where the expansions for the quantities formula_10and formula_11 are given by
and
As for a quasi-bialgebra, the property of being quasi-Hopf is preserved under twisting.
Usage.
Quasi-Hopf algebras form the basis of the study of Drinfeld twists and the representations in terms of F-matrices associated with finite-dimensional irreducible representations of quantum affine algebra. F-matrices can be used to factorize the corresponding R-matrix. This leads to applications in Statistical mechanics, as quantum affine algebras, and their representations give rise to solutions of the Yang–Baxter equation, a solvability condition for various statistical models, allowing characteristics of the model to be deduced from its corresponding quantum affine algebra. The study of F-matrices has been applied to models such as the Heisenberg XXZ model in the framework of the algebraic Bethe ansatz. It provides a framework for solving two-dimensional integrable models by using the quantum inverse scattering method.


Hahn series

In mathematics, Hahn series (sometimes also known as Hahn–Mal'cev–Neumann series) are a type of formal infinite series. They are a generalization of Puiseux series (themselves a generalization of formal power series) and were first introduced by Hans Hahn in 1907 (and then further generalized by Anatoly Maltsev and Bernhard Neumann to a non-commutative setting). They allow for arbitrary exponents of the indeterminate so long as the set supporting them forms a well-ordered subset of the value group (typically formula_1 or formula_2). Hahn series were first introduced, as groups, in the course of the proof of the Hahn embedding theorem and then studied by him as fields in his approach to Hilbert's seventeenth problem.
Formulation.
The field of Hahn series formula_3 (in the indeterminate "T") over a field "K" and with value group "Γ" (an ordered group) is the set of formal expressions of the form
with formula_5 such that the support formula_6 of "f" is well-ordered. The sum and product of
are given by
and
(in the latter, the sum formula_11 over values formula_12 such that formula_13 and formula_14 is finite because a well-ordered set cannot contain an infinite decreasing sequence).
For example, formula_15 is a Hahn series (over any field) because the set of rationals
is well-ordered; it is not a Puiseux series because the denominators in the exponents are unbounded. (And if the base field "K" has characteristic "p", then this Hahn series satisfies the equation formula_17 so it is algebraic over formula_18.)
Properties.
Properties of the valued field.
The valuation formula_19 of a non zero Hahn series
is defined as the smallest formula_21 such that formula_22 (in other words, the smallest element of the support of formula_23): this makes formula_24 into a spherically complete valued field with value group formula_25 and residue field formula_26 (justifying "a posteriori" the terminology). In fact, if formula_26 has characteristic zero, then formula_28 is up to (non unique) isomorphism the only spherically complete valued field with residue field formula_26 and value group formula_25.
The valuation formula_31 defines a topology on formula_3. If formula_33, then "v" corresponds to an ultrametric absolute value formula_34, with respect to which formula_3 is a complete metric space. However, unlike in the case of formal Laurent series or Puiseux series, the formal sums used in defining the elements of the field do "not" converge: in the case of formula_15 for example, the absolute values of the terms tend to 1 (because their valuations tend to 0), so the series is not convergent (such series are sometimes known as "pseudo-convergent").
Algebraic properties.
If "K" is algebraically closed (but not necessarily of characteristic zero) and "Γ" is divisible, then formula_3 is algebraically closed. Thus, the algebraic closure of formula_38 is contained in formula_39, where formula_40 is the algebraic closure of formula_26 (when "K" is of characteristic zero, it is exactly the field of Puiseux series): in fact, it is possible to give a somewhat analogous description of the algebraic closure of formula_38 in positive characteristic as a subset of formula_3.
If "K" is an ordered field then formula_3 is totally ordered by making the indeterminate "T" infinitesimal (greater than 0 but less than any positive element of "K") or, equivalently, by using the lexicographic order on the coefficients of the series. If "K" is real-closed and "Γ" is divisible then formula_3 is itself real closed. This fact can be used to analyse (or even construct) the field of surreal numbers (which is isomorphic, as an ordered field, to the field of Hahn series with real coefficients and value group the surreal numbers themselves).
If "κ" is an infinite regular cardinal, one can consider the subset of formula_3 consisting of series whose support set formula_47 has cardinality (strictly) less than "κ": it turns out that this is also a field, with much the same algebraic closedness properties as the full formula_3: e.g., it is algebraically closed or real closed when "K" is so and "Γ" is divisible.
Summable families.
Summable families.
One can define a notion of summable families in formula_3. If formula_50 is a set and formula_51 is a family of Hahn series formula_52, then we say that formula_51 is summable if the set formula_54 is well-ordered, and each set formula_55 for formula_21 is finite.
We may then define the sum formula_57 as the Hahn series formula_58.
If formula_59 are summable, then so are the families formula_60, and we have
formula_61 and formula_62.
This notion of summable family does not correspond to the notion of convergence in the valuation topology on formula_3. For instance, in formula_64, the family formula_65 is summable but the sequence formula_66 does not converge.
Evaluating analytic functions.
Let formula_67< and let formula_68 denote the ring of real-valued functions which are analytic on a neighborhood of formula_69.
If formula_26 contains formula_2, then we can evaluate every element formula_23 of formula_68 at every element of formula_3 of the form formula_75, where the valuation of formula_76 is strictly positive.
Indeed, the family formula_77 is always summable, so we can define formula_78. This defines a ring morphism formula_79.
Hahn–Witt series.
The construction of Hahn series can be combined with Witt vectors (at least over a perfect field) to form twisted Hahn series or Hahn–Witt series: for example, over a finite field "K" of characteristic "p" (or their algebraic closure), the field of Hahn–Witt series with value group "Γ" (containing the integers) would be the set of formal sums formula_80 where now formula_81 are Teichmüller representatives (of the elements of "K") which are multiplied and added in the same way as in the case of ordinary Witt vectors (which is obtained when "Γ" is the group of integers). When "Γ" is the group of rationals or reals and "K" is the algebraic closure of the finite field with "p" elements, this construction gives a (ultra)metrically complete algebraically closed field containing the "p"-adics, hence a more or less explicit description of the field formula_82 or its spherical completion.


Square class

In mathematics, specifically abstract algebra, a square class of a field formula_1 is an element of the square class group, the quotient group formula_2 of the multiplicative group of nonzero elements in the field modulo the square elements of the field. Each square class is a subset of the nonzero elements (a coset of the multiplicative group) consisting of the elements of the form "xy"2 where "x" is some particular fixed element and "y" ranges over all nonzero field elements.
For instance, if formula_3, the field of real numbers, then formula_4 is just the group of all nonzero real numbers (with the multiplication operation) and formula_5 is the subgroup of positive numbers (as every positive number has a real square root). The quotient of these two groups is a group with two elements, corresponding to two cosets: the set of positive numbers and the set of negative numbers. Thus, the real numbers have two square classes, the positive numbers and the negative numbers.
Square classes are frequently studied in relation to the theory of quadratic forms. The reason is that if formula_6 is an formula_1-vector space and formula_8 is a quadratic form and formula_9 is an element of formula_6 such that formula_11, then for all formula_12, formula_13 and thus it is sometimes more convenient to talk about the square classes which the quadratic form represents.
Every element of the square class group is an involution. It follows that, if the number of square classes of a field is finite, it must be a power of two.


Rupture field

In abstract algebra, a rupture field of a polynomial formula_1 over a given field formula_2 such that formula_3 is a field extension of formula_2 generated by a root formula_5 of formula_1.
For instance, if formula_7 and formula_8 then formula_9 is a rupture field for formula_1.
The notion is interesting mainly if formula_1 is irreducible over formula_2. In that case, all rupture fields of formula_1 over formula_2 are isomorphic, non canonically, to formula_15: if formula_16 where formula_5 is a root of formula_1, then the ring homomorphism formula_19 defined by formula_20 for all formula_21 and formula_22 is an isomorphism. Also, in this case the degree of the extension equals the degree of formula_23.
A rupture field of a polynomial does not necessarily contain all the roots of that polynomial: in the above example the field formula_9 does not contain the other two (complex) roots of formula_1 (namely formula_26 and formula_27 where formula_28 is a primitive third root of unity). For a field containing all the roots of a polynomial, see the splitting field.
Examples.
A rupture field of formula_29 over formula_30 is formula_31. It is also a splitting field.
The rupture field of formula_29 over formula_33 is formula_34 since there is no element of formula_33 with square equal to formula_36 (and all quadratic extensions of formula_33 are isomorphic to formula_34).


Comma category

In mathematics, a comma category (a special case being a slice category) is a construction in category theory. It provides another way of looking at morphisms: instead of simply relating objects of a category to one another, morphisms become objects in their own right. This notion was introduced in 1963 by F. W. Lawvere (Lawvere, 1963 p. 36), although the technique did not become generally known until many years later. Several mathematical concepts can be treated as comma categories. Comma categories also guarantee the existence of some limits and colimits. The name comes from the notation originally used by Lawvere, which involved the comma punctuation mark. The name persists even though standard notation has changed, since the use of a comma as an operator is potentially confusing, and even Lawvere dislikes the uninformative term "comma category" (Lawvere, 1963 p. 13).
Definition.
The most general comma category construction involves two functors with the same codomain. Often one of these will have domain 1 (the one-object one-morphism category). Some accounts of category theory consider only these special cases, but the term comma category is actually much more general.
General form.
Suppose that formula_1, formula_2, and formula_3 are categories, and formula_4 and formula_5 (for source and target) are functors:
formula_6
We can form the comma category formula_7 as follows:
Morphisms are composed by taking formula_22 to be formula_23, whenever the latter expression is defined. The identity morphism on an object formula_8 is formula_25.
Slice category.
The first special case occurs when formula_26, the functor formula_4 is the identity functor, and formula_28 (the category with one object formula_29 and one morphism). Then formula_30 for some object formula_31 in formula_1.
formula_33
In this case, the comma category is written formula_34, and is often called the "slice category" over formula_31 or the category of "objects over formula_31". The objects formula_37 can be simplified to pairs formula_38, where formula_39. Sometimes, formula_40 is denoted by formula_41. A morphism formula_42 from formula_43 to formula_44 in the slice category can then be simplified to an arrow formula_18 making the following diagram commute:
Coslice category.
The dual concept to a slice category is a coslice category. Here, formula_46, formula_4 has domain formula_48 and formula_5 is an identity functor.
formula_50
In this case, the comma category is often written formula_51, where formula_52 is the object of formula_2 selected by formula_4. It is called the "coslice category" with respect to formula_55, or the category of "objects under formula_55". The objects are pairs formula_57 with formula_58. Given formula_57 and formula_60, a morphism in the coslice category is a map formula_19 making the following diagram commute:
Arrow category.
formula_4 and formula_5 are identity functors on formula_3 (so formula_65).
formula_66
In this case, the comma category is the arrow category formula_67. Its objects are the morphisms of formula_3, and its morphisms are commuting squares in formula_3.
Other variations.
In the case of the slice or coslice category, the identity functor may be replaced with some other functor; this yields a family of categories particularly useful in the study of adjoint functors. For example, if formula_5 is the forgetful functor mapping an abelian group to its underlying set, and formula_71 is some fixed set (regarded as a functor from 1), then the comma category formula_72 has objects that are maps from formula_71 to a set underlying a group. This relates to the left adjoint of formula_5, which is the functor that maps a set to the free abelian group having that set as its basis. In particular, the initial object of formula_72 is the canonical injection formula_76, where formula_77 is the free group generated by formula_71.
An object of formula_72 is called a "morphism from formula_71 to formula_5" or a "formula_5-structured arrow with domain formula_71". An object of formula_84 is called a "morphism from formula_4 to formula_86" or a "formula_4-costructured arrow with codomain formula_86".
Another special case occurs when both formula_4 and formula_5 are functors with domain formula_48. If formula_92 and formula_93, then the comma category formula_7, written formula_95, is the discrete category whose objects are morphisms from formula_9 to formula_11.
An inserter category is a (non-full) subcategory of the comma category where formula_98 and formula_99 are required. The comma category can also be seen as the inserter of formula_100 and formula_101, where formula_102 and formula_103 are the two projection functors out of the product category formula_104.
Properties.
For each comma category there are forgetful functors from it.
Examples of use.
Some notable categories.
Several interesting categories have a natural definition in terms of comma categories.
Limits and universal morphisms.
Limits and colimits in comma categories may be "inherited". If formula_1 and formula_2 are complete, formula_152 is a continuous functor, and formula_153 is another functor (not necessarily continuous), then the comma category formula_7 produced is complete, and the projection functors formula_155 and formula_156 are continuous. Similarly, if formula_1 and formula_2 are cocomplete, and formula_159 is cocontinuous, then formula_7 is cocomplete, and the projection functors are cocontinuous.
For example, note that in the above construction of the category of graphs as a comma category, the category of sets is complete and cocomplete, and the identity functor is continuous and cocontinuous. Thus, the category of graphs is complete and cocomplete.
The notion of a universal morphism to a particular colimit, or from a limit, can be expressed in terms of a comma category. Essentially, we create a category whose objects are cones, and where the limiting cone is a terminal object; then, each universal morphism for the limit is just the morphism to the terminal object. This works in the dual case, with a category of cocones having an initial object. For example, let formula_3 be a category with formula_162 the functor taking each object formula_163 to formula_164 and each arrow formula_134 to formula_166. A universal morphism from formula_167 to formula_168 consists, by definition, of an object formula_164 and morphism formula_170 with the universal property that for any morphism formula_171 there is a unique morphism formula_172 with formula_173. In other words, it is an object in the comma category formula_174 having a morphism to any other object in that category; it is initial. This serves to define the coproduct in formula_3, when it exists.
Adjunctions.
Lawvere showed that the functors formula_176 and formula_177 are adjoint if and only if the comma categories formula_178 and formula_179, with formula_180 and formula_181 the identity functors on formula_182 and formula_3 respectively, are isomorphic, and equivalent elements in the comma category can be projected onto the same element of formula_184. This allows adjunctions to be described without involving sets, and was in fact the original motivation for introducing comma categories.
Natural transformations.
If the domains of formula_185 are equal, then the diagram which defines morphisms in formula_186 with formula_187 is identical to the diagram which defines a natural transformation formula_188. The difference between the two notions is that a natural transformation is a particular collection of morphisms of type of the form formula_189, while objects of the comma category contains "all" morphisms of type of such form. A functor to the comma category selects that particular collection of morphisms. This is described succinctly by an observation by S.A. Huq
that a natural transformation formula_190, with formula_191, corresponds to a functor formula_192 which maps each object formula_9 to formula_194 and maps each morphism formula_195 to formula_17. This is a bijective correspondence between natural transformations formula_188 and functors formula_192 which are sections of both forgetful functors from formula_186.


Plactic monoid

In mathematics, the plactic monoid is the monoid of all words in the alphabet of positive integers modulo Knuth equivalence. Its elements can be identified with semistandard Young tableaux. It was discovered by (who called it the tableau algebra), using an operation given by in his study of the longest increasing subsequence of a permutation.
It was named the ""monoïde plaxique" by , who allowed any totally ordered alphabet in the definition. The etymology of the word "plaxique"" is unclear; it may refer to plate tectonics ("tectonique des plaques" in French), as elementary relations that generate the equivalence allow conditional commutation of generator symbols: they can sometimes slide across each other (in apparent analogy to tectonic plates), but not freely.
Definition.
The plactic monoid over some totally ordered alphabet (often the positive integers) is the monoid with the following presentation:
Knuth equivalence.
Two words are called Knuth equivalent if they represent the same element of the plactic monoid, or in other words if one can be obtained from the other by a sequence of elementary Knuth transformations.
Several properties are preserved by Knuth equivalence.
Correspondance with Semistandard Young Tableaux.
Every word is Knuth equivalent to the word of a unique semistandard Young tableau (this means that each row is non-decreasing and each column is strictly increasing) over the same ordered alphabet, where the tableau may be read by rows or by columns. So the elements of the plactic monoid can be identified with the semistandard Young tableaux, which therefore also form a monoid.
Multiplying the word of a semistandard Young tableau to the left with a generator is equivalent to Schensted insertion into the Young tableau. In row order, the word of the tableau is equivalent to a product of increasingly longer nondecreasing sequences of generators. The new generator may be inserted in its proper place by either appending it if it is larger, and otherwise by repeatedly applying the plactic relations to move the out of sequence element to the next row. In the latter case, the out of order element replaces the leftmost entry larger than it in each row, and the displaced element is then inserted in the next row.
Since Schensted insertion preserves Young tableaux, this gives an inductive proof that elements of the plactic monoid can be written in a standard form corresponding to a Young tableau, and the construction defines a natural product of semistandard tableaux.
Jeu de Taquin.
Two skew Young Tableaux are Jeu de taquin equivalent if and only if their word readings are Knuth equivalent, i.e. correspond to equivalent elements of the plactic group. This gives an alternative definition of the plactic group product directly in terms of Young tableaux. Two tableaux may be multiplied by drawing them both around an empty rectangle to form a skew tableau, and using Jeu de taquin slides to rectify it.
Tableau ring.
The tableau ring is the monoid ring of the plactic monoid, so it has a Z-basis consisting of elements of the plactic monoid, with the same product as in the plactic monoid.
There is a homomorphism from the plactic ring on an alphabet to the ring of polynomials (with variables indexed by the alphabet) taking any tableau to the product of the variables of its entries.
Growth.
The generating function of the plactic monoid on an alphabet of size "n" is
showing that there is polynomial growth of dimension formula_2.


ComSpec (environment variable)