Codex Wiki
A field is a commutative ring in which every nonzero element has a multiplicative inverse.
A field is algebraically closed when every nonconstant polynomial over it has a root in it, equivalently when every such polynomial splits into linear factors.
The characteristic of a field is the least positive integer for which , or zero if no such integer exists.
A polynomial is a finite sum of monomials with coefficients in a ring.
A monic polynomial has leading coefficient one.
A root of a polynomial is a scalar satisfying .
A root has multiplicity when divides the polynomial but does not. It is a multiple root when .
A common root of polynomials and is a scalar satisfying .
The elementary symmetric polynomials in are the sums of all products of distinct variables, for .
Every symmetric polynomial over a commutative ring has a unique expression as a polynomial in the elementary symmetric polynomials.
Newton's identities relate the elementary symmetric polynomials to the power sums . The first three give
An irreducible polynomial is a nonconstant polynomial that cannot be written as a product of two nonconstant polynomials over its coefficient field. Over a general integral domain, neither factor may be a unit.
For polynomials and nonzero over a field, there are unique polynomials such that and .
The degree of a nonzero polynomial is the largest exponent of a monomial having nonzero coefficient.
A nonzero polynomial of degree over a field has at most distinct roots. Indeed, each root supplies a linear factor by polynomial division, and induction on gives the bound.
A quadratic function of one variable has the form with .
An algebraic number is an algebraic integer when it satisfies a monic polynomial with integer coefficients. Algebraic integers are closed under addition and multiplication.
For square-free , an integral basis is when , and otherwise. The discriminant is respectively and .
For a quadratic field of discriminant and a rational prime , the ideal splits into two distinct prime ideals, remains prime, or ramifies according as the quadratic character is , , or . The corresponding prime-ideal norms are , , and , respectively.
A prime ramifies in a number field when its prime-ideal factorization contains a factor with exponent greater than one.
If and , then . The generator's minimal polynomial reduces modulo to , so splits into two distinct prime ideals of norm three.
The discriminant of a biquadratic field is the product of the fundamental discriminants of its three quadratic subfields.
An element is integral over exactly when it acts stably on some faithful nonzero finitely generated -module containing one.
A ring generated over by finitely many algebraic integers is a finitely generated -module.
If is integral over and an element is integral over , then it is integral over .
An integral basis is a -basis of the ring of integers of a number field.
The field discriminant is the discriminant of any integral basis and controls the index of every suborder.
Let be an integral basis and let be a rational basis of algebraic integers, with integer matrix . Their trace Gram matrices satisfysoThe absolute discriminant is minimized exactly when is unimodular, equivalently when the form an integral basis.
The polynomial is irreducible over . Forone hasThe field has ring of integers and field discriminant .
The elementsform an integral basis. Relative to this basis, multiplication by has integer matrixThe basis discriminant is one quarter of the discriminant of , hence is the square-free integer .
The field norm is the determinant of multiplication by , equivalently the product of its conjugates when the extension is separable.
If in a number field, then ; a norm that is not a square in the base field therefore obstructs square roots.
An algebraic integer whose absolute norm is or is a unit, because its conjugate product supplies an integral inverse.
If is a full lattice and a measurable convex centrally symmetric set has volume greater than , then contains a nonzero lattice point.
For a real quadratic field with embeddings , the imageis a lattice in of covolume , and the product of the two coordinates is the field norm.
If , its Mahler measure is
Let an irreducible have and a root outside the closed unit disk. Its leading coefficient must have absolute value one. The product of all roots outside the unit disk is then an algebraic integer with ; conjugate pairs make real, so . The quotient of the norm of any root by is both rational and an algebraic integer, and its absolute value is at most one. It is therefore , so every root has absolute norm two.
If a number field has real embeddings and conjugate pairs of complex embeddings, thenwhere is the finite group of roots of unity in .
If is real quadratic and is a number-field extension with finite, then the unit ranks agree. If and has signature , this forcesFor a proper extension the only possibility is and signature . For , the example has this signature and a nontrivial finite quotient because is a new root of unity.
Choose the real embeddings and one embedding from each complex-conjugate pair. The weighted logarithmic embedding isFor a unit, the sum of these coordinates is .
The kernel of is exactly . If every conjugate of a unit has modulus one, all its powers lie in a bounded subset of the discrete Minkowski lattice , so two powers coincide and the unit is a root of unity.
The logarithms of a fundamental system of units form a basis of the hyperplaneand their integer span is a full lattice in .
Every principal ideal of a number field has a generator satisfyingat every archimedean embedding. Multiply an arbitrary generator by a unit so that its logarithmic unit-lattice coordinates lie in a fixed bounded fundamental parallelepiped.
For a primitive fifth root of unity ,The explicit units and generate a subgroup of finite index.
The field trace is the trace of multiplication by , equivalently the sum of its conjugates in a separable extension.
The trace form of a number field is the symmetric bilinear form
In a quadratic extension , an element is integral exactly when its relative trace and norm lie in .
A fractional ideal of a number field is a nonzero -submodule for which for some nonzero .
An integral ideal is a fractional ideal contained in the ring of integers .
For a nonzero integral ideal , its norm is the finite index . Norms multiply under ideal multiplication.
The ideal class group is the group of nonzero fractional ideals modulo principal fractional ideals.
If a number field of degree and signature has discriminant , every ideal class contains an integral ideal with
For with , the field discriminant is and the Minkowski bound is . The prime ideals above and are principal, so every ideal class has a principal representative and
The field has ring of integers , discriminant , and Minkowski bound below eight. The nonprincipal ramified ideals above two and three generate four classes, and the split primes above seven introduce no new class. Hence
The order of the class of a fractional ideal is the least positive integer for which is principal.
Let , , and let be a prime-ideal factor of . If and is odd, then does not have order . Otherwise would givefor . The bound forces , after which is an integer square, impossible for odd .
If every integral ideal contains nonzero with , then is an integral representative of with norm at most .
Bounded-norm representatives prove class-group finiteness because only finitely many integral ideals have norm at most a fixed constant.
Every element of a finite ideal class group has finite order. Therefore every nonzero ideal has a positive power that is principal.
Every nonzero proper ideal of a number ring factors uniquely as a finite product of positive powers of distinct nonzero prime ideals.
If and the minimal polynomial of factors modulo a rational prime asthenand the prime ideal has norm .
For a number field , the Dedekind zeta function is formally
Unique factorization of nonzero ideals and multiplicativity of the ideal norm give the formal identitywhere the product ranges over nonzero prime ideals.
For a quadratic field of discriminant ,where is , , or according as splits, remains prime, or ramifies in . Comparing the three possible local Euler factors proves the formal identity.
An ideal is primary when and imply for some positive integer .
The radical of a primary ideal is prime. In a number ring this forces a nonzero primary ideal to have only one prime in its unique factorization.
In a field of characteristic , the Frobenius map is an injective field endomorphism becauseConsequently every element of an extension field has at most one th root.
The formal derivative of is . In characteristic , the coefficient vanishes exactly when divides .
Over a field of characteristic ,for some polynomial . Indeed, zero derivative says every exponent with nonzero coefficient is divisible by .
A polynomial over a field is separable when it has no repeated root in a splitting field. Equivalently, it is coprime to its formal derivative.
For a finite extension , the automorphism group has order dividing . Indeed, Artin's theorem gives , while and the tower law gives the divisibility.
An element of a field extension is algebraic over when some nonzero polynomial in vanishes at .
The minimal polynomial of an algebraic element over is the unique monic polynomial of least positive degree in that vanishes at . It is irreducible, and its degree equals .
A primitive element of a finite extension is an element such that .
Every finite separable extension is generated by one element: for some .
A finite separable extension is simple by the primitive element theorem. A simple separable extension is finite because its generator is separable and hence algebraic. Finite and simple does not imply separable: in characteristic , is finite and simple but purely inseparable.
If are nonsquares in a field of characteristic other than two, thenis a degree-four Galois extension with group . Its three quadratic intermediate fields are , , and .
Up to conjugacy, the transitive subgroups of are , , , , and .
If cyclically sends and fixes while negating , then and . These automorphisms realize as the Galois group of the corresponding quartic splitting field.
A field embedding is an injective field homomorphism. A -embedding fixes every element of the base field .
Distinct field embeddings are linearly independent over as functions on . Thus a nontrivial linear combination cannot vanish on every element of .
If has order and the fixed field contains a primitive th root , thensatisfies . Independence of the powers of ensures that is nonzero for some .
An embedding of extends across by sending it to a root of its transformed minimal polynomial. There are between one and the relative degree many choices, with equality for a separable extension.
For finite extensions , the degrees multiply: .
The splitting field of a polynomial over is the smallest field extension of in which the polynomial is a product of linear factors.
Every nonconstant polynomial has a splitting field of finite degree over . It is constructed by adjoining a root of an irreducible factor and repeating over the enlarged field. Any two splitting fields of over are isomorphic by an isomorphism that fixes . Inside one fixed algebraic closure, the field generated by all roots is unique as a subfield.
A finite extension is normal exactly when it is the splitting field over of some polynomial. For the forward direction, multiply the minimal polynomials of finitely many generators of ; normality puts all their roots in . The reverse direction follows because a -embedding permutes the roots of a polynomial and hence preserves its splitting field.
Let in characteristic , let , let split over , and let split over . If are the roots of and , then the Frobenius endomorphism makes each unique andbecause . Thus is already the splitting field of over , and every root of is purely inseparable over .
An algebraic extension is normal when every irreducible polynomial over with a root in splits in . For finite extensions, equivalently every -embedding into an algebraic closure has image .
An algebraic extension is separable when every element has a minimal polynomial with distinct roots.
An algebraic element over is separable when its minimal polynomial over has no repeated root in a splitting field. For an irreducible polynomial , this is equivalent to , because then .
An algebraic extension in characteristic is purely inseparable when every one of its elements is purely inseparable over the base field.
An algebraic element is purely inseparable over when for some .
An element is purely inseparable over exactly when its minimal polynomial has the formTo prove the nontrivial direction, repeatedly factor a zero formal derivative through until the remaining irreducible polynomial has nonzero derivative. Since has only the root , that remaining separable polynomial must be linear.
If is purely inseparable, an embedding of into an algebraic closure has at most one extension to : if , the image of must be the unique th root of the image of . Existence in a normal overfield therefore implies uniqueness.
A finite extension is Galois when it has automorphisms fixing .
A separable extension has embeddings in an algebraic closure, and normality makes every one an automorphism of . Hence a finite normal separable extension is Galois.
The multiplicative group is cyclic of order , so it contains all th roots of unity when divides and the characteristic does not divide .
If a field has characteristic prime to and contains all th roots of unity, then is a cyclic Galois extension of degree , with automorphisms .
The Galois group of a separable polynomial acts faithfully on its roots; this action is transitive exactly when the polynomial is irreducible.
Suppose a group of field automorphisms acts transitively on elements , and each has a unique th root in a stable extension. If every automorphism extends, it sends to the unique root above its image of , so the extended group acts transitively on the .
Let be irreducible and separable in characteristic , and put . Every monic irreducible factor of is either itself or separable. Indeed, if were inseparable, then ; divisibility of into forces , hence and .
Under the same hypotheses, is reducible exactly when every coefficient of is a th power in . If , thenConversely, if is reducible, all its irreducible factors are separable. Its zero derivative forces every factor multiplicity to be divisible by , so it is a th power in and all its coefficients are th powers.
Over , Frobenius acts on roots of an irreducible degree- polynomial as an -cycle. Factor degrees therefore give its cycle type.
At an unramified prime, the degrees of the irreducible factors of a polynomial modulo that prime give the cycle type of an element of the Galois group.
is the monic polynomial whose roots are the primitive th roots of unity. It belongs to and is irreducible over .
Partitioning the roots of by their exact orders givesInduction and Gauss's lemma then show that every has integer coefficients.
If the prime does not divide , then is square-free over because its derivative is coprime to it. Its factor is therefore separable modulo .
If is the splitting field of over a characteristic-zero field , choosing a primitive root gives an injectionIt is surjective exactly when is irreducible over .
A cyclotomic field is generated by a root of unity. If and is primitive, every -conjugate of is a power and already lies in . Thus is Galois, and its Galois group embeds in , so it is abelian.
The roots of unity in form a cyclic group of order
For a primitive seventh root of unity ,where . Its four intermediate fields correspond to the four subgroups of the cyclic group .
The unique cubic subfield is the maximal real subfieldandIt is the fixed field of complex conjugation.
For a field inside a fixed algebraic closure, the maximal cyclotomic extension is the union of the fields generated by roots of unity.
The maximal cyclotomic extension of is , since adjoining a primitive fourth root of unity adjoins .
The maximal cyclotomic extension of is a proper subfield of . Every finite subextension inside a cyclotomic field is Galois and abelian, whereas is not normal.
The maximal cyclotomic extension of is . A primitive th root of unity generates over , and these finite fields exhaust the algebraic closure.
A finite real extension is constructible when it is contained in a towerEquivalently, every element of can be obtained from rational numbers by field operations and successive square roots.
The real cyclotomic fieldis Galois of degree eight with cyclic Galois group . A subgroup chain of successive index two gives a tower of three quadratic extensions, proving that is constructible.
For a group of automorphisms of a field , the fixed field isFor one automorphism , it is also written .
If a finite group acts faithfully by automorphisms on a field , then is Galois, has degree , and has Galois group .
For a finite Galois extension, subgroups correspond in reverse order to intermediate fields by taking fixed fields and field-fixing subgroups.
For a finite Galois extension with group , an intermediate extension is normal exactly when its corresponding subgroup is a normal subgroup of .
Every subgroup of an abelian group is normal. Hence every intermediate field of a finite abelian Galois extension is itself Galois over the base field.
For , choose a prime by Dirichlet's theorem. The cyclic grouphas a subgroup of index , whose fixed field is cyclic Galois of degree over .
Let an automorphism of an algebraically closed field have finite order and fixed field . Artin's fixed-field theorem makes finite cyclic Galois. Every finite extension embeds in : in characteristic zero, choose a primitive generator and send it to a root in . Its image is an intermediate field of a cyclic extension and is therefore Galois and cyclic over .
Put and . The dihedral group acts byThe ten subgroups and their fixed fields areThe normal subgroups are , , the two displayed Klein four-groups, , and .
For a monic polynomial with roots , the discriminant is and vanishes exactly for a repeated root.
The Vandermonde product is alternating, and its square is the discriminant of the monic polynomial with roots .
The depressed cubic has discriminant .
For a monic separable polynomial over a field of characteristic other than two, its Galois group is contained in the alternating group exactly when its discriminant is a square in the base field. The Galois action multiplies the Vandermonde product by the sign of the induced root permutation.
For cubic roots and a cube root of unity , the Fourier combinations and have cubes satisfying a quadratic resolvent.
For , the Lagrange-resolvent cubes are roots of .
Cardano's formula solves a depressed cubic by taking square roots in its quadratic resolvent and then compatible cube roots.
A polynomial is solvable by radicals when its roots lie in a tower obtained by adjoining successive roots; equivalently, its Galois group is solvable.
An irreducible cubic over a field of characteristic other than two has Galois group when its discriminant is a square and otherwise.
The polynomial is irreducible over and has discriminant , so its splitting field has Galois group . Its unique quadratic subfield is the fixed field of , namely .
The discriminant square class detects whether the transitive cubic Galois group lies in the alternating group.
Let be the roots of the separable polynomial in characteristic two. The cyclic sumsare the distinct roots ofEven root permutations fix , while odd permutations interchange them. The cubic Galois group is therefore contained in exactly when this quadratic splits over the base field.
A group representation is a group homomorphism from a group to the general linear group of a vector space. It realizes abstract group elements as invertible linear transformations.
A representation is semisimple when it is a direct sum of irreducible representations. Equivalently, every invariant subspace has an invariant complement.
Every group representation of a finite group over a field whose characteristic does not divide the number of elements of the group is semisimple. Given an invariant subspace, averaging any projection onto it over the group produces an equivariant projection, whose kernel is an invariant complement.
A complex representation of a group is a homomorphism for a complex vector space .
A finite-dimensional continuous representation of a topological group is a continuous homomorphism , where is a finite-dimensional complex vector space.
The degree of a finite-dimensional representation is .
Representations and are isomorphic when an invertible linear map intertwines the actions: for every .
A representation is faithful when its kernel is trivial.
The left regular representation acts on the basis by . It is faithful.
By Maschke's theorem, the complex regular representation of a finite group is a direct sum of irreducibles. Its kernel is the intersection of their kernels. If the group is simple, each kernel is either trivial or the whole group; faithfulness of the regular representation therefore forces at least one irreducible constituent to be faithful.
For a -cycle , each with is conjugate to . In a faithful complex representation, has a nontrivial th-root eigenvalue , and similarity of and puts all values in its spectrum. Hence the representation has dimension at least .
Commuting complex involutions are simultaneously diagonalizable, so can act faithfully in dimension only if . A group containing for arbitrarily large , such as the full permutation group of , has no faithful finite-dimensional complex representation.
Let be the real upper unitriangular three-by-three group, let be its centre, and let be the integer subgroup of . Every finite-dimensional continuous complex representation of kills the central circle , and hence is not faithful.
The image of a one-dimensional representation lies in the abelian group , so its kernel contains the commutator subgroup of the represented group.
Finite-dimensional complex representations of are completely reducible, and their irreducibles are indexed by nonnegative integers.
The irreducible representation consists of homogeneous degree- polynomials in two variables, with the action induced from the standard two-dimensional representation. It has dimension .
Every finite-dimensional complex -representation is a direct sum of the pairwise nonisomorphic irreducibles .
The standard invariant alternating form identifies with its dual. Its symmetric powers identify every with , and complete reducibility then gives for every finite-dimensional complex -representation.
On , the central element acts as . It therefore acts trivially on , although it need not act trivially on the tensor square of a representation containing irreducibles of both parities.
For ,The identity follows by multiplying the weight characters and comparing their nested weight strings.
On the multiplicity-one summand , interchange of tensor factors acts by . A highest-weight vector exhibiting the sign is
The odd-parity summands give
The alternating summands in the tensor square give . Since is self-dual and has trivial determinant,
For any finite-dimensional complex representation,
Newton's identities applied to the eigenvalues of give
Averaging any object over a finite group, , produces a group-invariant object whenever the relevant operations are linear.
A complex representation is unitary when every representing matrix preserves a positive-definite Hermitian inner product.
Average a positive-definite Hermitian form over a finite group and choose an orthonormal basis for the averaged form. In that basis every representing matrix is unitary.
For a compact group with normalized Haar measure, averaging any positive-definite Hermitian form,produces an invariant positive-definite Hermitian form.
Every finite-dimensional continuous complex representation of is unitary and decomposes into one-dimensional weight spaces. Its continuous one-dimensional characters are for .
If a central subgroup is isomorphic to , its weight spaces are invariant under the entire group, because every representing operator commutes with the central circle action.
Irreducible characters are orthonormal for , and .
The character table of a finite group lists its irreducible complex characters on its conjugacy classes. The number of rows equals the number of conjugacy classes, and the squared row degrees sum to the group order.
The degree of an irreducible character is , the dimension of the corresponding irreducible representation.
A linear character is the character of a one-dimensional representation and therefore has degree one.
A nonlinear irreducible character has degree greater than one.
The character of a finite-dimensional representation is the class function . Isomorphic representations have the same character.
For a finite group acting on a finite set , the number of orbits isIt follows by counting pairs with first by and then by .
If a finite group acts two-transitively on , thenwhere is irreducible and nontrivial. The character norm is the number of orbits on , namely the diagonal and its complement.
For a finite -set , the character of at is . Its invariant dimension is the number of -orbits.
Let act on the -element subsets of , with permutation character . If , thenbecause orbits of pairs are classified by intersection size .
For , the equivariant map from -subsets to -subsets that sends each subset to the sum of the -subsets containing it is injective over . Hence is the character of a representation.
The permutation representation of on decomposes asThe first summand is the trivial representation and the second is the -dimensional standard representation.
An intertwining operator between representations and is a linear map satisfying for every group element .
An intertwiner between irreducible complex representations is either zero or an isomorphism; an endomorphism of one irreducible is scalar.
The kernel and image of an intertwiner are invariant subspaces. Irreducibility therefore makes a nonzero intertwiner injective and surjective. For an endomorphism of a finite-dimensional irreducible complex representation, choose an eigenvalue . The noninvertible intertwiner must be zero, so .
If a finite group has a faithful irreducible complex representation, every central element acts as a scalar by Schur lemma. Faithfulness embeds the centre into , and every finite subgroup of is cyclic. Hence the group centre must be cyclic.
For a representation on , the dual action on is .
Let act on by . Its character is zero unless and are conjugate, in which case it equals . Character column orthogonality gives the same character forwhere the run through the irreducible complex representations. Maschke's theorem therefore gives an isomorphism of the two representations.
A bilinear form on is invariant exactly when is a -homomorphism . On an irreducible representation, Schur's lemma makes a nonzero such form nondegenerate and unique up to scale.
Transposing a nonzero invariant bilinear form on an irreducible complex representation gives a scalar multiple . Transposing twice yields , so the form is symmetric or alternating.
Induction extends a representation of a subgroup to the whole group; Frobenius reciprocity computes its multiplicities.
Let be abelian and let a linear character of have stabilizer exactly under conjugation by . Then is irreducible of degree . Its value is zero outside , while on it is the sum of the characters in the -orbit of .
For with faithful action, the abelianization supplies five linear characters. The two orbits of size five on the nontrivial characters of induce two irreducible characters of degree five. Their squared degrees satisfyso these seven characters are all the irreducible characters of .
For a -representation and an -representation ,On group-algebra tensors the isomorphism sends to .
For , an -representation , and a -representation ,Equivalently, induction and restriction are adjoint for character inner products.
For an irreducible -representation , the induced representation is irreducible exactly when, for every nonidentity double coset representative , the restrictions of and its -conjugate to have inner product zero.
For the upper-triangular subgroup of andthe two double cosets are and , and , the diagonal subgroup.
Every linear character of the upper-triangular subgroup with is obtained from a multiplicative character of . Its induction to is irreducible exactly when .
The diagonal subgroup of conjugates to . It therefore has two orbits, each of size , on the nontrivial characters of the unipotent subgroup: one indexed by squares and one by nonsquares.
If is the upper-triangular subgroup of and is one-dimensional on , thenis the direct sum of three pairwise nonisomorphic irreducibles. Their restrictions to have character supports given by the trivial character, the square orbit, and the nonsquare orbit, so their dimensions are .
An irreducible representation has no nonzero proper invariant subspace.
If conjugation sends an operator to its inverse, the conjugating element sends its -eigenspace to the -eigenspace.
For , every irreducible complex representation has degree at most two. If is an eigenvector of with eigenvalue , then has eigenvalue , so irreducibility makes the representation equal to .
For and , defineThese representations are irreducible and pairwise nonisomorphic. They give all two-dimensional irreducibles: of them for odd , and for even .
For , the matricesdefine a faithful irreducible two-dimensional complex representation.
The infinite dihedral group is .
Its irreducible complex representations have dimension at most two; the two-dimensional family pairs eigenvalues and of the rotation generator.
For , the rotation acts by and the reflection interchanges the two eigenlines.
A one-dimensional character is a homomorphism from a group to the multiplicative group of its scalar field.
Every one-dimensional character kills the commutator subgroup and therefore factors through the abelianization. Conversely, every character of the abelianization pulls back to a one-dimensional character of the group.
A representation factors through a finite quotient exactly when its kernel contains the defining kernel of that quotient.
An indecomposable representation cannot be expressed as a direct sum of two nonzero invariant subspaces.
A nonsplit extension contains an invariant subrepresentation with no invariant complementary subspace.
A unipotent operator has every eigenvalue equal to one and may create a nonsplit Jordan-block extension.
A binary code is a set of distinct words in whose minimum pairwise Hamming distance is . Here is the block length and is the number of codewords.
The Hamming distance between two equal-length words is the number of coordinates in which they differ.
For messages in a finite additive group, a one-time pad encrypts as , where the key is uniform and independent of , as long as the message, and never reused. Then is uniform and independent of , giving perfect secrecy.
An encryption scheme has perfect secrecy when the ciphertext and plaintext are independent random variables, so observing the ciphertext does not change the plaintext's probability distribution.
If an interceptor knows that an additive one-time-pad ciphertext encrypts plaintext and wants it to decrypt as , replacing it byworks without knowing the key, since .
A discrete memoryless channel has finite input and output alphabets and transition probabilities . Conditional on the input symbols, different channel uses have independent outputs governed by the same transition probabilities.
For a discrete memoryless channel, operational capacity equalsRates below admit codes whose error tends to zero, while rates above cannot have vanishing error.
A binary linear-feedback shift register of degree updates a -bit state by shifting and inserting a fixed linear combination over . With recurrenceits feedback polynomial is .
A feedback shift register updates a finite state by shifting its stored symbols and inserting the value of a feedback function of the previous state. The feedback function need not be linear.
The Berlekamp-Massey algorithm finds the shortest linear recurrence satisfied by a finite sequence over a field. It processes symbols incrementally, updating the connection polynomial whenever the current recurrence has a nonzero discrepancy.
The shortest binary linear recurrence producing the prefix has length three:Its connection polynomial is .
A degree- binary register has states. The zero state is fixed, so a nonzero periodic orbit has length at most .
A maximal-period feedback polynomial cannot have as a root. Over , this saysso an even number of the coefficients equal one and the full monic polynomial has an odd number of nonzero coefficients.
If an output prefix contains consecutive zeros followed by a one, no register of degree at most can generate it: the all-zero state would have been reached and would remain zero forever.
The seven consecutive zeros followed by one force degree at least eight. Degree eight is attained by , with initial state and feedback polynomial .
Let , let generate , and let be nonzero linear with nondegenerate bilinear form . If the minimal polynomial of is , then satisfiesso it is produced by an LFSR of length at most . Its period is exactly : any period would imply for every , hence by nondegeneracy.
A binary linear code is a -dimensional subspace of with least nonzero weight . A parity-check matrix presents it as a kernel.
The length- even-weight code consists of binary words whose coordinates sum to zero. It has parameters .
The binary repetition code is and has parameters .
The zero code contains only the zero word and has dimension zero.
The whole-space binary code is , with parameters .
The Hamming weight of a word is the number of its nonzero coordinates.
The minimum Hamming distance of a nonzero linear code is the smallest Hamming weight of a nonzero codeword.
A generator matrix for a linear code has a basis of the code as its rows, so its row space is the code.
The parity-check extension of a binary linear code appends to each codeword the sum of its coordinates in , making every extended word have even Hamming weight.
Puncturing a code at one coordinate deletes that coordinate from every codeword. For a code of minimum distance , puncturing preserves its number of words and gives minimum distance or .
Shortening a code at one coordinate first retains only words with a chosen symbol there and then deletes that coordinate. The minimum distance cannot decrease. In a binary code one coordinate-symbol fibre contains at least half of the words.
The dual code consists of the words orthogonal to every word of under the standard dot product. A parity-check matrix for is a generator matrix for .
The binary Reed-Muller code evaluates Boolean polynomials of degree at most on . It has parametersThe dimension counts square-free monomials, and the minimum weight follows inductively from the decomposition .
Under the standard binary inner product,The product of representing polynomials has degree at most , so its evaluation word has even weight; equality follows by comparing dimensions.
The binary Hamming code of redundancy has parameters . Its parity-check matrix has every nonzero vector of as a column.
The binary simplex code is the dual of the binary Hamming code. For redundancy it has parameters .
A Hamming code has words, and each radius-one Hamming ball contains vectors. Its minimum distance is three, so these balls are disjoint, and their total size is . They therefore partition the ambient space, making the code perfect.
A code of minimum Hamming distance detects every pattern of at most errors and uniquely corrects every pattern of at most errors. The correction claim follows because Hamming balls of that radius around distinct codewords are disjoint.
A length- cyclic code over is an ideal of . It is generated by a monic divisor of .
The unique monic divisor of generating a cyclic code is its generator polynomial. The code has dimension .
The dual of a cyclic code is cyclic. If , then the dual generator is the monic reciprocal polynomial .
Over ,Its eight monic divisors generate the eight cyclic codes of length seven: the whole-space, even-weight, two Hamming, two simplex, repetition, and zero codes.
Given a primitive th root , a BCH code of design distance has a generator polynomial vanishing at consecutive powers .
For error locations in a cyclic code with primitive root , the error locator polynomial is . Its roots encode the error positions.
The minimum distance of a BCH code is at least its design distance. A hypothetical word of smaller weight yields a square Vandermonde system from the consecutive-root equations; its support elements are distinct, so the determinant is nonzero and every word coefficient must vanish.
A binary length- code of size and distance at least satisfiesEquality means the code is perfect.
Rabin encryption sends to modulo a product of two secret primes. Decryption computes the four square roots by the Chinese remainder theorem.
Given a cyclic group generator and an element , the discrete logarithm problem asks for an exponent such that .
Alice publishes and Bob publishes in a public cyclic group; each can then compute the shared secret . Its security relies on the difficulty of recovering the exponents or otherwise solving the computational Diffie--Hellman problem.
A code is decipherable, or uniquely decodable, when every finite concatenation of codewords has at most one decomposition into source codewords.
In a prefix code no codeword is the prefix of another, so concatenated messages have unique instantaneous decoding.
The lengths of every decipherable binary code satisfyConversely, any positive integer lengths satisfying this bound can be realized by a prefix code.
If a decipherable binary code has codewords of lengths , thenThis follows by applying the entropy lower bound with the uniform source distribution.
Shannon--Fano coding assigns a symbol of probability a prefix-code length near .
Order source probabilities as , putand take the first binary digits of as the codeword for symbol . Since for , two cumulative probabilities cannot lie in the same dyadic interval selected by the earlier codeword. The resulting code is prefix-free.
Every binary prefix code has expected length at least its source entropy; Shannon lengths achieve expected length strictly below .
A binary symmetric channel independently flips each transmitted bit with a fixed crossover probability .
An error is undetected by codeword-membership checking when the received word is a different valid codeword. For a linear code this occurs exactly when the nonzero channel-error vector is itself a codeword.
At crossover probability , the two rows of the transition matrix of a binary symmetric channel coincide. Its output is then independent of its input and its capacity is zero.
If , choose . Binary codes of relative minimum distance above have positive asymptotic rate by a greedy packing bound, and nearest-codeword decoding fails only when more than channel errors occur. That probability tends to zero.
Maximum a posteriori decoding chooses the codeword maximizing prior probability times channel likelihood and minimizes average decision error.
Maximum-likelihood decoding chooses the codeword under which the received word has greatest conditional probability.
Minimum-distance decoding chooses a codeword closest to the received word; on a binary symmetric channel with , it is maximum-likelihood decoding under Hamming distance.
A Cartesian basis is an orthonormal basis associated with perpendicular Cartesian coordinate axes.
A bilinear form on a vector space over a field is a map that is linear in each argument separately.
The radical of a symmetric bilinear form isThe form is nondegenerate exactly when its radical is zero.
A bilinear form on a finite-dimensional vector space is nondegenerate whenequivalently when is an isomorphism from to its dual space.
A symplectic vector space is a vector space equipped with a nondegenerate antisymmetric bilinear form. Every finite-dimensional symplectic vector space has even dimension: splitting off one symplectic two-plane leaves a smaller nondegenerate antisymmetric space, and induction completes the decomposition.
If is a nondegenerate bilinear form on a finite-dimensional vector space and is any bilinear form, there is a unique linear map such thatThe right radical of is .
The inertia of a real symmetric bilinear form is the triple giving the numbers of positive, negative, and zero squares in a diagonalization. Sylvester's law of inertia makes it independent of the chosen basis.
A complex sesquilinear form is linear in one argument and conjugate-linear in the other. Here the first argument is taken to be linear.
A Hermitian form is a complex sesquilinear form satisfying .
For a basis , the matrix of a Hermitian form has entries . With the convention that is linear in its first argument, coordinate columns satisfy .
A vector space consists of vectors that may be added and multiplied by scalars, subject to the vector-space axioms.
A linear combination of vectors is a sum with scalar coefficients .
A scalar multiple of a vector is a vector of the form for a scalar .
The dimension of a vector space is the cardinality of any of its bases.
The direct sum of two vector spaces consists of pairs with componentwise operations. A vector space is an internal direct sum of subspaces and exactly when every vector has a unique expression with and .
For finite-dimensional subspaces of a common vector space,
For every subspace of a finite-dimensional vector space , extending a basis of to a basis of produces a subspace such that .
Vectors are linearly dependent when some nonzero choice of coefficients gives a vanishing linear combination.
A vector is an element of a vector space.
The cross product of two three-dimensional vectors is perpendicular to both, has magnitude , and is oriented by the right-hand rule.
A scalar is an element of the field over which a vector space is defined.
A linear map preserves vector addition and scalar multiplication.
For a linear map , the induced mapis a vector-space isomorphism.
A linear isomorphism is a bijective linear map. Its inverse is also linear.
A real linear function on has the form .
Linearity is the property .
For a homogeneous linear equation, every linear combination of solutions is again a solution.
A linear operator is a linear map from a vector space to itself.
A unitary operator on a complex vector space with an inner product satisfies and therefore preserves inner products.
Linear operators and on the same finite-dimensional vector space are conjugate when for some linear isomorphism . Their matrices in any fixed basis are similar.
For an invertible operator on , the mapis a linear isomorphism. Conjugate choices of induce conjugate operators .
A matrix represents a linear map after bases have been chosen for its domain and codomain.
The matrix unit has entry one in row , column , and zero in every other position. The matrix units form the standard basis of the vector space of matrices of a fixed size.
The rank of a matrix is the dimension of its column space, equivalently the dimension of its row space.
The identity matrix has ones on its main diagonal and zeros elsewhere, and satisfies whenever the products are defined.
A nonzero matrix has rank one exactly when it can be written as an outer product .
An upper bidiagonal matrix can have nonzero entries only on its main diagonal and first superdiagonal.
Matrix multiplication represents composition of linear maps. Its entries are .
The outer product of column vectors and is the rank-at-most-one matrix , whose entry is .
An upper Hessenberg matrix has zero entries below its first subdiagonal: whenever .
A permutation matrix has exactly one entry equal to one in each row and column and zeros elsewhere. Left or right multiplication permutes coordinates, and .
Given ordered bases and , the matrix has column equal to the -coordinate vector of .
For matrices and , the Kronecker product replaces each entry by the block . It satisfieswhenever the products are defined.
Every complex matrix has a factorization with unitary and diagonal with nonnegative entries. The squared singular values are the eigenvalues of .
An integral square matrix is unimodular when its determinant is or . Its inverse again has integral entries, so it defines an invertible change of integer coordinates.
For unit , is an orthogonal reflection. Successive Householder similarities reduce a symmetric matrix while preserving symmetry.
For a linear map with finite-dimensional domain,If a basis of is extended to a basis of , the images of the added basis vectors form a basis of . Counting the two parts proves the formula.
The dual space of a vector space over is . If is finite-dimensional, then .
A linear functional is a linear map from a vector space to its scalar field.
For a basis of , its dual basis is characterized by .
For the map represented by a matrix , column rank is the rank of the map and row rank is the rank of its dual. Since the dual map has kernel equal to the annihilator of the original image, rank-nullity gives equal ranks.
If the columns of an by matrix are independent, some by row minor is nonzero. A nonzero term of that minor's determinant selects distinct nonzero coordinates , and replacing the corresponding standard basis vectors by the leaves a basis.
For a finite-dimensional vector space and , dualizing the quotient and inclusion maps gives
If are linearly independent, thenmaps onto . Otherwise a nonzero functional annihilating its proper image would give a nontrivial linear relation among the .
A polynomial moment functional evaluates a polynomial through a weighted integral, such as ; finitely many moments determine it on a bounded-degree polynomial space.
If the th column of a matrix is , then its image lies in . If is not constant and at least two differ, the rank is exactly two; for columns the nullity is .
A matrix inverse satisfies .
A similarity transformation sends a square matrix to for an invertible matrix . It changes the basis of a linear operator and preserves its characteristic polynomial and eigenvalues.
Every square matrix over a field is similar to its transpose.
If real matrices satisfy for an invertible complex , then , so both real matrices intertwine and . Since is a nonzero real polynomial, some real makes invertible and supplies a real similarity.
The trace is the sum of diagonal entries,Index interchange proves and hence cyclic invariance under any cyclic permutation of a product.
Linear operator theory studies linear maps, their spectra, invariant subspaces, and normal forms.
The spectrum of a linear operator consists of the scalars for which is not invertible. In finite dimensions it is the set of eigenvalues.
If is a subspace of a space with an inner product and is its orthogonal projection, the compression of an operator to isIf the columns of are an orthonormal basis of , its matrix in that basis is .
Every self-adjoint operator on a finite-dimensional real inner-product space has an orthonormal basis of eigenvectors and only real eigenvalues.
On polynomials with weighted inner productthe operatoris self-adjoint because . Its eigenvalues on polynomials of degree at most are ; its eigenvectors are scalar multiples of the Laguerre polynomials.
The generalized Laguerre polynomial is orthogonal on for the weight when .
A Rodrigues formula constructs an orthogonal polynomial by differentiating a weight multiplied by a power. For generalized Laguerre polynomials,
Every real symmetric matrix is orthogonally diagonalizable. Distinct eigenspaces are orthogonal because symmetry gives .
Iterate . With a unique dominant eigenvalue separated by a spectral gap and a starting vector that is nonorthogonal to its eigenvector, the directions converge at the spectral-ratio rate.
For a real symmetric matrix with and a starting vector having nonzero component in the leading eigendirection, power-method direction errors arewhereas the Rayleigh quotient error isThe improvement occurs because orthogonality cancels terms linear in the direction error.
The active spectrum consists of eigenvalues whose eigenspaces have nonzero projection of the starting vector. The power method converges toward the eigenvalue of largest modulus in this active spectrum; an exactly absent dominant component is never created in exact arithmetic.
Inverse iteration repeatedly solves and normalizes. It is the power method for and converges toward an eigenvector whose eigenvalue is closest to the shift .
If is real symmetric, is not an eigenvalue, one eigenvalue is uniquely closest to , and the initial vector has a nonzero component in its eigenspace, fixed-shift inverse iteration converges to that eigenspace. Its asymptotic direction-error ratio iswhere is second closest to .
Subspace iteration repeatedly applies a matrix to several independent vectors and orthonormalizes them, converging to a dominant invariant subspace when a spectral gap separates the selected eigenvalue cluster.
A dominant invariant subspace is spanned by eigenvectors whose eigenvalue moduli exceed those outside the subspace.
When several eigenvalues share the largest modulus, normalized power iterates need not converge individually, but every limit lies in their joint invariant subspace.
The characteristic polynomial isIts roots are precisely the eigenvalues of .
For real matrices , is a real polynomial. If , it is not the zero polynomial, so some real satisfies .
Every square matrix over an algebraically closed field is similar to an upper-triangular matrix. Choose an eigenvector, extend it to a basis, and apply induction to the induced lower-right block.
Eigenvalue interlacing bounds the ordered eigenvalues of a compressed or rank-modified operator between those of the original operator.
The algebraic multiplicity of an eigenvalue is its multiplicity as a root of the characteristic polynomial. In Jordan form it is the sum of the sizes of all blocks carrying that eigenvalue.
The geometric multiplicity of an eigenvalue is the dimension of its eigenspace. In Jordan form it equals the number of blocks carrying that eigenvalue.
A Jordan block has one eigenvalue on its diagonal and ones on its superdiagonal.
A nilpotent Jordan block has zeros on its diagonal and ones on its superdiagonal. Its th power has ones on the th superdiagonal, and a block of size satisfies .
If has eigenvalues and is diagonalizable on a two-dimensional complex vector space, thenIf has one size-two Jordan block, then
Over an algebraically closed field, the characteristic polynomial gives the total size of the Jordan blocks for each eigenvalue, while the minimal polynomial gives the largest block size. For total dimension at most three, these two numbers determine the partition into block sizes: a multiplicity-three eigenvalue has partition , , or according as its largest block has size , , or . Hence two matrices of size at most three with the same characteristic and minimal polynomials are similar.
A generalized eigenvector lies in the kernel of a positive power of A minus lambda I.
For a linear operator , the generalized eigenspacesbelonging to distinct eigenvalues are linearly independent. On the generalized -eigenspace, is invertible for because the nilpotent part has a finite geometric-series inverse.
For a square matrix , its exponential is the convergent power seriesIt is the fundamental matrix for and satisfies .
The minimal polynomial is the unique monic polynomial of least degree satisfying . It divides every polynomial that annihilates .
If are pairwise coprime, thenBezout identities between the factors construct the corresponding projections.
If an upper-triangular by matrix has diagonal entries , its standard invariant flag satisfiesThe commuting product therefore vanishes, proving without invoking the full Cayley-Hamilton theorem.
Let and suppose . Then is nilpotent. For the derivation , one has . If , induction givesIndeed, if , differentiating and multiplying on the left by gives ; for this replaces by . Taking makes a nonzero constant and proves nilpotence.
On all real-valued functions on , define . The operators commute, and every real number except is an eigenvalue. For eigenvalue , values may be chosen independently on the cosets of and extended by , so every eigenspace is infinite-dimensional.
If has degree and leading coefficient , then for nonzero steps ,Consequently a degree- polynomial cannot be the sum of functions each periodic with some nonzero period.
A right eigenvector satisfies .
A left eigenvector satisfies , equivalently over the real numbers.
The eigenspace for is .
An eigenbasis is a basis consisting of eigenvectors of one operator.
An eigenvalue is simple when it has algebraic multiplicity one.
For unit left eigenvector and right eigenvector of a real matrix at a simple eigenvalue , its normwise sensitivity isIt measures the first-order amplification of a matrix perturbation into an eigenvalue perturbation.
If and is a differentiable function defining a simple eigenvalue, thenThe Cauchy-Schwarz inequality and the operator norm give
A matrix is diagonalizable exactly when its eigenvectors span the whole vector space.
Let be invertible over an algebraically closed field. If is diagonalizable for some , then is diagonalizable. Indeed, a nontrivial Jordan block has andThe first nonzero nilpotent term prevents this power from being diagonalizable.
Suppose real matrices satisfy for an invertible complex matrix . Then and . The real polynomial is not identically zero because its value at is nonzero, so some real makes invertible. This real matrix intertwines and .
Eigenvectors belonging to distinct eigenvalues are linearly independent. Consequently, an -dimensional operator with distinct eigenvalues is diagonalizable.
A spectral decomposition expresses a linear operator through its eigenvalues and projections onto its eigenspaces.
An eigenvalue is dominant when its modulus is greater than or equal to that of every other eigenvalue. It is uniquely dominant when the inequality is strict.
A spectral gap is a positive separation between designated parts of the spectrum of a linear operator. For the power method, the relevant gap separates the modulus of the dominant eigenvalue from the other eigenvalue moduli.
The adjoint of a complex matrix is its conjugate transpose,
A complex matrix is unitary when . Its columns form an orthonormal basis, and it preserves inner products and norms.
A matrix is normal when .
Every finite-dimensional complex normal matrix has an orthonormal eigenbasis, equivalentlyfor some unitary and diagonal .
Every complex square matrix is unitarily similar to an upper triangular matrix. The proof selects an eigenvector, extends it to an orthonormal basis, and applies induction to the compression on its orthogonal complement.
The unilateral shifts on sequences move every component one place left or right. Their spectra illustrate behavior absent in finite dimensions.
The point spectrum of an operator is its set of eigenvalues.
An operator is a unilateral shift exactly when it is an isometry, is one-dimensional, and . A unit vector in the first orthogonal complement is wandering, and is a complete orthonormal basis.
Starting from a unit vector , Rayleigh quotient iteration sets , solvesand normalizes . The shift is updated from the new vector.
The extremal Rayleigh quotients of a self-adjoint operator are the extremal spectral values. In particular, a Hamiltonian with a discrete spectrum satisfies , with equality precisely on its ground-state eigenspace. More generally, minimizing over states orthogonal to the first eigenspaces gives an upper bound on .
For a one-dimensional even potential, the ground state is even and the first excited state is odd. Every normalized odd trial wavefunction is therefore orthogonal to the ground state and gives
Forand the trial state ,This is negative for some for every , proving that the attractive well has a bound state. For small , taking gives
For an orthonormal trial set , the Rayleigh quotient on their span isIts minimum is the smallest eigenvalue of , which is therefore the optimal variational upper bound available in that trial subspace.
For the first two sine modes in a width- infinite well with
, the Hamiltonian in units isIts lower eigenvalue gives the upper bound
, the Hamiltonian in units isIts lower eigenvalue gives the upper bound
A cyclic vector has iterates under an operator that span the whole vector space.
A companion matrix represents multiplication by x in the power basis modulo a monic polynomial.
An invariant direct-sum decomposition splits a space into nonzero subspaces preserved by the operator.
Rational canonical form expresses a linear map as a direct sum of companion matrices of invariant factors, and works over any field.
Multilinear algebra studies maps linear in each of several arguments, including determinants and tensor products.
A rank- tensor on a vector space is a multilinear map of vector or covector arguments, equivalently an element of an -fold tensor product. Its components transform by one copy of the change-of-basis matrix for each index.
A covariant tensor is multilinear in vector arguments and transforms with one covariant index for each argument.
A second-rank Cartesian tensor is antisymmetric when . Orthogonal coordinate changes preserve this property because implies .
A tensor changes sign whenever two indices are interchanged. In three dimensions, a rank-two antisymmetric tensor is , a rank-three one is , and every totally antisymmetric tensor of rank greater than three vanishes.
An isotropic tensor is invariant under every proper orthogonal change of basis. A rank-four isotropic tensor has the formRank-five isotropic pseudotensors are formed by multiplying one Kronecker delta by one Levi-Civita symbol and permuting the five indices.
Einstein notation sums automatically over an index repeated once up and once down, or twice in Euclidean coordinates.
For a basis with scalar triple product , the reciprocal vectors are cyclic cross products divided by and satisfy .
The scalar triple product is the signed volume of the parallelepiped spanned by three vectors.
An oriented volume retains the sign of a determinant; reversing the orientation changes that sign.
The determinant is the alternating multilinear volume scale of a square matrix; it is nonzero exactly for invertible matrices.
The determinant is linear in each row and in each column when all the others are held fixed.
For diagonal entries , superdiagonal entries , and subdiagonal entries , the leading principal determinants satisfy
A linear system is consistent when lies in the column space of ; its solutions form a translate of .
A linear equation is an equation in which the unknowns occur only to the first power and are combined linearly.
The system is solvable exactly when is orthogonal to every vector in .
Every square matrix decomposes uniquely as , a symmetric part plus an antisymmetric part.
A real matrix is symmetric when . It represents a self-adjoint operator in the standard Euclidean inner product.
An axis-angle map fixes or scales one axis and acts on its perpendicular plane by a rotation, possibly combined with a dilation.
Invert the axial scalar and invert the perpendicular complex scalar as .
A plane reflection with unit normal is ; it fixes the plane and negates .
For a nonzero normal vector , reflection in has matrixIts eigenvalues are along and on , so its determinant is .
The composition of reflections in two planes through the origin is a rotation about their line of intersection through twice the oriented angle between the planes.
A rotation matrix is an orthogonal matrix with determinant .
An object has rotational symmetry when a nontrivial rotation matrix leaves it unchanged.
A Cartesian coordinate system specifies a point by its signed components along mutually perpendicular coordinate axes.
The positive quadrant of the Cartesian plane is the set of points with and .
For invertible , .
The adjugate is the transpose of the cofactor matrix and satisfies .
Equivalent matrices represent the same linear map after independent changes of domain and codomain bases.
For maps through a finite-dimensional intermediate space V, rank(alpha beta) is at least rank(alpha)+rank(beta)-dim(V).
For an invertible block P, the Schur complement of P in a block matrix is .
Orthogonal similarity maps A to QAQ^T and preserves eigenvalues and symmetry.
Every complex square matrix is a product of two symmetric matrices, one invertible.
For vectors , the Gram matrix isTwo finite vector families with the same Gram matrix are related by an isometry between their spans; in finite dimensions that isometry can be extended to a unitary map after completing orthonormal bases.
If is an orthogonal basis of a finite-dimensional subspace , the unique closest point in to isThe residual is orthogonal to .
A complex matrix is an orthogonal projection exactly whenIts image and kernel are orthogonal complements.
For orthogonal polynomials under a positive weighted integral inner product, the least-squares approximation to of degree at most isIts residual is orthogonal to every polynomial of degree at most .
Two vectors are orthogonal when their inner product is zero.
Two vectors are nonorthogonal when their inner product is nonzero. In the power method, the starting vector must be nonorthogonal to a dominant eigenvector.
The Gram-Schmidt process replaces linearly independent vectors by orthogonal vectors with the same successive spans, subtracting from each its projections onto the preceding vectors.
A reduced QR decomposition of a full-column-rank matrix writes , where has orthonormal columns and is upper triangular with positive diagonal.
For a symmetric bilinear form , the same projection formulaproduces a -orthogonal basis whenever the chosen pivots are nonzero. Reordering the input vectors can avoid a zero pivot when a suitable anisotropic vector remains.
A quadratic form is a homogeneous degree-two function represented in coordinates by with symmetric.
The rank of a quadratic form is the rank of its associated symmetric bilinear form.
The signature of a real quadratic form is the number of positive squares minus the number of negative squares in its diagonal normal form.
Over a field of characteristic other than two, a quadratic form recovers its symmetric bilinear form by
For a complex sesquilinear form , the values determine . In particular, expanding at and shows that for every implies . Over the reals this conclusion can fail for nonsymmetric bilinear forms, as a nonzero skew-symmetric form has zero diagonal.
A symmetric bilinear form is positive semidefinite when for every , and positive definite when equality is possible only for .
A real symmetric or complex Hermitian matrix is positive semidefinite when for every vector , equivalently when all its eigenvalues are nonnegative.
If is real symmetric and positive semidefinite, its principal square root isIt is symmetric and positive semidefinite, and is positive definite exactly when is.
Every invertible real matrix has the polar decompositionwhere is symmetric positive definite and is orthogonal.
A real symmetric matrix is positive definite whenfor every nonzero real vector . It therefore defines the inner product and is invertible.
A Hermitian matrix is positive definite exactly when all its leading principal minors are positive.
For a real symmetric positive-definite matrix,It measures the sensitivity of the linear system and controls convergence bounds for iterative solvers.
A complex matrix is Hermitian positive definite when and for every nonzero complex vector .
A Toeplitz matrix is constant along each diagonal, so its entries have the form .
Every real quadratic form is congruent to a diagonal form with entries , and the numbers of entries of each kind are invariant.
A subspace is totally isotropic for when for all . For a real nondegenerate bilinear form of inertia , its dimension is at most .
A vector is isotropic for a quadratic form when .
For symmetric , the quadratic form has gradient .
The entrywise product of two positive semidefinite matrices is positive semidefinite. Writing each matrix as a sum of rank-one Gram matrices reduces the claim to .
The real orthogonal group is . Its tangent space at the identity is the vector space of skew-symmetric matrices.
A real square matrix is orthogonal when , equivalently when its columns form an orthonormal basis.
The special orthogonal group isEvery element of is a rotation in the plane. Every element of fixes an axis and restricts to a planar rotation on its perpendicular plane.
A matrix is skew-symmetric when .
The tensor product is determined by and linear extension.
For with , .
A diagonal matrix has zero entries away from its main diagonal. Its eigenvalues are its diagonal entries.
A block-diagonal matrix has square matrices along its block diagonal and zero off-diagonal blocks. Its determinant is the product of the block determinants.
An upper or lower triangular matrix has all entries on one side of the main diagonal equal to zero. Its eigenvalues, with algebraic multiplicity, are its diagonal entries.
A square root of an element is an element such that . The notation denotes the nonnegative square root when is a nonnegative real number.
Integer polynomials form a countable set and each has finitely many roots, so the algebraic numbers are countable.
A countable union of countable sets is countable, using a diagonal enumeration.
The Cantor pairing function is an explicit bijection between and , obtained by enumerating lattice points along successive diagonals.
Cantor's diagonal argument proves that the set of infinite binary sequences is uncountable: a sequence obtained by changing the th digit of the th listed sequence differs from every sequence in the list.
For finite extensions ,
Inside a common overfield, the compositum is the smallest field containing both and .
Finite extensions and are linearly disjoint when products of basis elements form a basis of their compositum. In particular,Extensions of coprime finite degrees are linearly disjoint.
An algebraic closure of a field is an algebraic extension for which is algebraically closed.
For a field extension , an intermediate field is a field satisfying .
A quadratic extension is a field extension of degree two. It is normal because the other root of the minimal polynomial of any non-base-field element is and lies in the same extension.
If and are algebraic field extensions, then is algebraic. In particular, an element algebraic over an algebraic extension of is algebraic over .
A finite field is a field with finitely many elements; its size is a prime power.
The nonzero elements of every finite field form a cyclic group. For a field with elements, combine elements realizing each prime-power factor of the group exponent to obtain an element of exponent order; the root bound for then forces that order to be .
Every finite subgroup of the multiplicative group of a field is cyclic. If is the exponent of , commutativity lets one combine elements whose orders realize the prime-power factors of , producing an element of order . Every element of is a root of , so the Lagrange root bound over a field gives . Since , equality holds and that element generates .
In a finite field with elements, the equation has exactly solutions. Indeed, after choosing a generator of the multiplicative group, is a solution exactly when .
For odd , the nonzero squares form an index-two subgroup of . Given nonzero , either or is a square, or both occupy the nontrivial coset and is a square. Taking and shows that one of is a square, apart from the immediate zero case .
For a sequence , the ordinary generating function isMultiplying a linear recurrence by and summing converts shifts of the sequence into polynomial multiples of .
The sequence has generating function
An affine recurrence has the form and is solved by a matrix geometric sum.
If the spectral radius of is below one, converges to the unique fixed point .
Linearization replaces a nonlinear relation near a reference state by its first-order approximation.
Strong induction allows the step for an integer to use the result for every smaller integer.
Backward induction proves or computes a finite sequence of statements by starting at its terminal index and stepping toward the initial index.
The ascending chain condition requires every chainof ideals to stabilize. A ring is Noetherian exactly when it satisfies this condition, equivalently when every ideal is finitely generated.
If a ring is finitely generated as an abelian group, then it is Noetherian. Every ideal is an additive subgroup of that finitely generated abelian group and is therefore generated by finitely many elements as an abelian group. The same elements generate it as an -ideal because integer multiples are already scalar multiples by elements of .
A polynomial ring over a Noetherian ring is Noetherian.
For a nonsquare integer ,The integers are Noetherian, the Hilbert basis theorem makes Noetherian, and quotients preserve Noetherianity.
In , the idealhas additive index two. If were principal, multiplication by its generator would givewhich has no solution in integers. Thus is not principal.
The subring is not Noetherian. Its idealsform a strict ascending chain because multiplying by a nonconstant element of introduces at least a second power of .
Hermite interpolation prescribes values and finitely many derivatives of a polynomial at distinct points.
If the same invertible message is sent under one RSA modulus with coprime public exponents , choose integers with . From one recoversusing modular inverses for negative exponents.
Knowledge of a valid public and private exponent gives , a nonzero multiple of . Writing it as with odd and testing random bases produces a nontrivial square root of one modulo with high probability; a greatest common divisor then factors . Thus one customer's private key under a shared semiprime modulus compromises every exponent using that modulus.
A primitive th root of unity has multiplicative order exactly .
For ,This is the finite geometric series identity and expresses orthogonality of the characters of .
For every integer matrix , there are unimodular matrices such thatThe positive diagonal entries are unique. Their products are the greatest common divisors of the -rowed minors.
A Liouville number admits rational approximations of every fixed polynomial order; Liouville's approximation theorem makes every such irrational number transcendental.
A unit in a ring is an element with a multiplicative inverse.
The units of a ring form a group under multiplication.
The multiplicative group of integers modulo consists of the residue classes coprime to . It has order .
For a prime ,Every nonzero residue other than and pairs with a distinct multiplicative inverse, leaving only in the product.
Every nonconstant complex polynomial has a complex root and therefore factors completely into linear factors over .
Group theory studies groups, homomorphisms, actions, quotients, and symmetry.
A group is a set with an associative binary operation, an identity, and an inverse for every element.
A finite group is a group with finitely many elements. Its number of elements is its order.
The order of a finite group is its number of elements.
A nontrivial group has more than one element.
The inverse of a group element satisfies .
A group operation is the associative binary operation of a group. It has an identity element, and every element has an inverse element.
Left and right multiplication by a fixed group element are bijections, called left and right translations.
A cyclic group is generated by one element. A cyclic group of order has exactly solutions of for every positive integer divisor of .
Every finite subgroup of is cyclic. If its exponent is , it is a subgroup of the cyclic group of th roots of unity.
A finite additive group is a finite group whose operation is written as addition. Its identity element is denoted , the inverse element of is denoted , and translation is a bijection.
A subgroup is a subset of a group that is itself a group under the restricted operation.
The index is the number of left cosets of in .
Every subgroup of index two is normal: the two left cosets and the two right cosets are both and its complement, so they agree.
The direct product has componentwise multiplication. An element of finite component orders has order .
The commutator subgroup is generated by all . It is characteristic, is abelian, and every normal subgroup with abelian quotient contains .
The abelianization of a group is the quotient by its commutator subgroup. It is the largest abelian quotient of .
If is cyclic, then is abelian. Indeed, if generates the quotient, every element is with , and any two such elements commute.
A group acts on itself and on its subgroups by conjugation: and .
The normalizer of a subgroup is .
For a finite group acting on a set and any point ,Indeed, is a well-defined bijection from the left cosets of the stabilizer to the orbit.
An action is doubly transitive when the group acts transitively on ordered pairs of distinct points. Equivalently, each point stabilizer acts transitively on the remaining points.
The full isometry group of a cube has order . Its transitive actions on the vertices, edges, and main diagonals have stabilizers isomorphic respectively toThe action on main diagonals has kernel .
A group action is faithful when only the identity acts as the identity on every point.
If a group acts transitively on a set of prime size and is normal, then the -orbits form a -invariant block system of equal size. They are therefore either singletons or the whole set. In a faithful action the singleton case forces , so every nontrivial normal subgroup is transitive.
The orbit of is .
The stabilizer of is the subgroup .
The symmetric group acts on -element subsets by applying a permutation to every member.
A group acts on the left cosets of a subgroup by left multiplication; its kernel is the core of that subgroup.
For a subgroup , a left coset is . The left cosets partition and all have cardinality .
For subgroups , the double coset of isThe double cosets partition . The action of on the left cosets of givesby the orbit-stabilizer theorem.
If is a Sylow subgroup of a finite group and , some intersection is a Sylow subgroup of . Otherwise every double-coset sizewould be divisible by a larger power of than , as would their sum .
For a finite group and subgroup , the order of divides the order of , and the quotient is the number of left cosets:
A group embedding is an injective group homomorphism. It identifies its domain with an isomorphic subgroup of its codomain.
Every group embeds in the symmetric group on its underlying set through the left-regular action .
For , a cyclic group of prime-power order cannot embed in , because a permutation of order requires a cycle of length at least . If is not a prime power, every group of order embeds in by combining coset actions on subgroups of two distinct prime orders.
For an abelian group , the generalized dihedral group is the semidirect product in which the nonidentity element of acts on by inversion.
The general linear group is the group of invertible linear maps from a vector space to itself, with composition as its operation.
A group homomorphism preserves multiplication: .
A homomorphism from is determined by the image of one generator; a surjection exists exactly when .
The kernel is a normal subgroup of the domain.
The image of a group homomorphism is the subgroup of .
Finite group theory studies groups with finitely many elements.
The sign homomorphism sends an even permutation to and an odd permutation to ; its kernel is the alternating group.
A symmetric group is the group of all bijections from a set to itself, with function composition as its operation.
A three-cycle is a permutation cycle of length three. On any chosen set of three letters, the two possible three-cycles are inverses of one another.
Permutation cycles with disjoint supports commute. The order of their product is the least common multiple of their lengths.
The support of a permutation is the set of elements it does not fix. A permutation has finite support when this set is finite.
The sign homomorphism is the determinant of the corresponding permutation matrix. A transposition has sign , so this also proves that the parity of any transposition decomposition is well-defined.
The quaternion group is a nonabelian Dedekind group.
A nontrivial simple group has no normal subgroups other than the identity subgroup and itself.
The conjugacy classes of have sizesA normal subgroup is a union of these classes containing the identity. No proper nontrivial such union has size dividing , so Lagrange's theorem proves that is simple.
Every finite nonabelian simple group has order at least 60; the alternating group A5 attains this bound.
The group consists of invertible by matrices over the finite field .
Choosing linearly independent columns successively gives
The upper unitriangular group consists of upper triangular matrices with every diagonal entry equal to one. Over it has order and is a Sylow subgroup of .
The projective line over a field is the set of one-dimensional subspaces of and may be identified with .
The translations for form a Sylow -subgroup of . Every nonidentity translation fixes infinity and exchanges the four finite points in two transpositions, so its action lies in .
The determinant-one matrices form the normal subgroup .
The dihedral group is generated by a rotation of order and a reflection with ; it has order .
If with , then has subgroups of order , every -subgroup lies in one, and all such Sylow subgroups are conjugate. Their number satisfies and .
Let be prime numbers. A nonabelian group of order has a unique Sylow -subgroup and exactly Sylow -subgroups. Hence the Sylow count satisfies , so .
A group, or one of its Sylow subgroups, acts on the set of Sylow subgroups by conjugation.
The Sylow -subgroups of are its three transposition subgroups, while its unique Sylow -subgroup is . The three Sylow -subgroups of are dihedral groups of order eight and are the normalizers of the three cyclic subgroups generated by inverse pairs of -cycles. The five Sylow -subgroups of are Klein four-groups, one fixing each letter.
If is a Sylow -subgroup of and is any -subgroup, let act on . Since does not divide , some coset is fixed. Hence , or equivalently .
Suppose a group acts faithfully and transitively on seven points, every point stabilizer is , and every two-point stabilizer is a Klein four-group. Then the group has order andCount pairs consisting of a point and a Sylow subgroup fixing it for ; the two-point stabilizer ensures uniqueness. For , a normal Sylow subgroup would force the group into its order- normalizer in .
Suppose a finite group has no index-two subgroup, is a Sylow -subgroup, has index two in , and has order two. The sign of the action on defines a homomorphism and is therefore trivial. Since , a fixed-point-free involution would be an odd number of transpositions. Thus fixes a coset , equivalently .
If a prime divides the order of a finite group, the group contains an element of that prime order.
One proof lets a cyclic group of order rotate the tuplesThe tuple set has size , and its fixed tuples are precisely with . Counting nonfixed orbits modulo forces a nonidentity fixed tuple.
A composition series is a finite subnormal chain whose successive quotients are simple.
The Klein four-group is the abelian group with three nonidentity elements, all of order two.
A torsion element has finite order.
A free abelian group has a basis over and is isomorphic to a direct sum of copies of .
A subgroup is normal when for every .
The preimage of a normal subgroup under any group homomorphism is normal.
Under a surjective homomorphism, the image of a normal subgroup is normal.
A Dedekind group is a group in which every subgroup is normal.
The projective linear group is and acts on projective space.
A Möbius transformation of the Riemann sphere has the formThe group is generated by translations, nonzero complex scalings, and inversion .
For four distinct points of the Riemann sphere, their cross-ratio iswith the evident limiting conventions at infinity. Every Möbius transformation preserves it.
A generalized circle is either a Euclidean circle or a straight line together with the point at infinity. Every Möbius transformation maps generalized circles to generalized circles. A Euclidean circle becomes a line exactly when it contains the pole, the preimage of infinity.
The transformations that take every Euclidean circle to a Euclidean circle are preciselyThey form the stabilizer of infinity in the Möbius group and are not a normal subgroup.
A fixed point of a Möbius transformation satisfies a quadratic equation on the Riemann sphere.
For , the finite fixed points are the roots ofThus a repeated fixed point or two prescribed fixed points determine and by the usual sum and product of roots.
Every nonidentity finite-order Möbius transformation has exactly two fixed points on the Riemann sphere. A transformation with one repeated fixed point is conjugate to a nontrivial translation and therefore has infinite order.
A condition fixes the oriented angle subtended by . Its locus is an arc of a circle through those two points, with the endpoints excluded.
For determinant-one real representatives, trace magnitude below, equal to, or above two gives elliptic, parabolic, or hyperbolic type.
The Möbius transformations commuting with are exactlyThey preserve the open unit disc exactly when . The identityproves the latter assertion.
A Möbius transformation is represented by an invertible two-by-two matrix, with nonzero scalar multiples representing the same map.
A semidirect product combines a normal subgroup with a subgroup acting on it by automorphisms.
The one-dimensional affine group over consists of maps with .
For an odd prime , the splitting fieldof has Galois groupThe translation subgroup multiplies by powers of , while the multiplicative subgroup acts on by cyclotomic automorphisms.
Let be the subgroup of nonzero squares in . The affine mapsform the nonabelian semidirect product , with multiplication
This group has seven conjugacy classes: the identity; two classes of five nonidentity translations, distinguished by square class of the translation parameter; and, for each of the four , one class of size eleven.
A solvable group has a subnormal series whose factor groups are abelian.
The exponent of a finite group is the least common multiple of the orders of all its elements.
Every finite subgroup of is cyclic. If its exponent is , all its elements are roots of , so its size is at most ; finite abelian group theory supplies an element of order , forcing equality.
The order of an element is the least positive power equal to the identity and divides the order of a finite group.
A polynomial is homogeneous of degree when scaling all variables by scales its value by .
Commutative algebra studies commutative rings, ideals, modules, and their spectra.
The polynomial ring consists of polynomials in an indeterminate with coefficients in a ring .
A proper ideal of a commutative ring is maximal when no proper ideal lies strictly between and . Equivalently, is a field.
An ideal of a commutative unital ring is maximal exactly when is a field.
A local ring is a commutative ring with exactly one maximal ideal.
A discrete valuation ring is a principal ideal domain with exactly one nonzero maximal ideal. Every nonzero element of its fraction field is a unit times a unique integer power of a uniformizer.
A ring has addition and multiplication, with an abelian group under addition and multiplication distributive over addition.
An element of a ring is nilpotent when for some positive integer . A field has no nonzero nilpotent elements.
A commutative ring is a ring whose multiplication satisfies .
A graded ring is a direct sum with .
An ideal is an additive subgroup of a ring that absorbs multiplication by ring elements.
A set generates an ideal when every element of is a finite sum of ring multiples of elements of .
A principal ideal is generated by one element: .
The product consists of finite sums of products with and .
The set-theoretic intersection of any family of ideals is again an ideal.
Ideals and are comaximal when .
For finitely many distinct prime ideals, one can prescribe finite valuation data simultaneously by the Chinese remainder theorem.
Reduction modulo an ideal is the quotient homomorphism .
An ideal in a graded ring is homogeneous when it is generated by homogeneous elements, equivalently when every homogeneous component of each of its elements also belongs to the ideal.
A ring homomorphism preserves addition, multiplication, and, under the convention used here, the multiplicative identity.
Every ring homomorphism induces an isomorphism
An element is idempotent when .
An integral domain is a nonzero commutative ring with identity and without zero divisors.
A nonzero nonunit in an integral domain is prime when implies or .
A nonzero nonunit in an integral domain is irreducible when every factorization has at least one unit factor.
A greatest-common-divisor domain is an integral domain in which every two nonzero elements have a greatest common divisor, defined up to multiplication by a unit.
If and in a greatest-common-divisor domain, then . Indeed, the least common multiple of and is associate to and divides every common multiple; applying this to and cancelling proves the claim.
The fraction field of an integral domain consists of fractions with and , modulo the usual equivalence relation.
A principal ideal domain is an integral domain whose every ideal has one generator.
Every submodule of a finite-rank free module over a principal ideal domain is free. Induction on rank splits off a generator of the image under one coordinate projection and applies the result to the kernel.
A Euclidean domain admits division with remainder measured by a decreasing Euclidean function.
A Euclidean function on an integral domain assigns a nonnegative integer to every nonzero element so that, for with , there are satisfying and either or .
A Gaussian integer has the form with . Its multiplicative norm is , which makes a Euclidean domain.
For a primitive cube root of unity , the Eisenstein integers form the triangular latticeTheir multiplicative norm is .
Every complex number is within squared distance at most of an Eisenstein integer: write it as and round and to integers. Therefore, for nonzero and arbitrary , a nearest lattice point to givesThe norm makes the Eisenstein integers a Euclidean domain.
A Bézout domain is an integral domain in which every finitely generated ideal is principal. Equivalently, every pair has a greatest common divisor satisfying a Bézout identity . A Noetherian Bézout domain is a principal ideal domain because all its ideals are finitely generated.
A commutative ring has a nontrivial idempotent exactly when it decomposes as a product of two nontrivial rings. The isomorphism determined by iswith inverse .
A fiber product of rings consists of pairs having the same image in a third ring.
Modulo a prime power, a class is a unit exactly when it is not divisible by that prime.
Modulo p^e, a class is nilpotent exactly when its reduction modulo p is zero.
Reduction between quotient rings sends units to units and is surjective when every target unit avoids the same prime factors.
The content of a polynomial is a greatest common divisor of its coefficients, up to a unit.
A primitive polynomial has unit content.
Over a UFD, products of primitive polynomials are primitive and factorization over the fraction field descends after content is removed.
If is a unique factorization domain with fraction field , then is a unique factorization domain. A primitive polynomial irreducible in remains irreducible, hence prime, in the principal ideal domain ; Gauss lemma for polynomials brings divisibility back to .
Every rational function in fixed by exchanging and is a quotient of coprime symmetric polynomials. In a coprime presentation , symmetry givesUnique factorization implies and . The alternative would make both divisible by , contradicting coprimality, so .
For a primitive polynomialif a prime does not divide , divides every for , and has , then is irreducible. If , reduction modulo forces both and to be positive-degree monomials. Their constant terms are consequently divisible by , making , a contradiction. Gauss lemma for polynomials transfers the result between and .
For ,is irreducible over the integers exactly when is prime. Composite gives a geometric factorization; for prime , translation makes the polynomial Eisenstein at .
Every zero and pole of a square in has even order. Thus a rational function with a zero or pole of odd order cannot be a square. For characteristic different from two, this proves that is not a square in .
Module theory extends linear algebra by allowing scalars from a ring rather than only a field.
A finitely generated module over a principal ideal domain decomposes aswith finitely many irreducibles . The free rank and primary cyclic factors are unique up to associates and ordering.
An -module is an abelian group equipped with scalar multiplication by a ring , satisfying the usual distributive and associative laws.
A submodule of an -module is a subset closed under addition, additive inverses, and scalar multiplication by every element of .
For a submodule , the quotient module consists of additive cosets with scalar multiplication .
A free module has a basis: every element has a unique finite linear combination in that basis with coefficients in the scalar ring.
A basis of an -module is a subset such that every element of has a unique expression as a finite -linear combination of elements of .
A module is free on a set exactly when every function from to any module extends uniquely to an -module homomorphism .
For a nonzero commutative scalar ring, every two bases of a finite-rank free module have the same cardinality. This cardinality is the rank.
If is a nonzero commutative ring and , reduction modulo a maximal ideal produces isomorphic vector spaces of dimensions and . Hence .
A module over an integral domain is torsion-free when with implies .
A module is projective when every map from through the target of a surjection lifts through that surjection.
Lift the image of each basis element independently through the given surjection, then extend the chosen lifts linearly.
A module is cyclic when one element generates it: .
An irreducible, or simple, module is nonzero and has no submodules other than zero and itself.
Every simple module over a commutative ring is isomorphic to for a maximal ideal ; its annihilator is therefore maximal.
The annihilator is the ideal of scalars that kill every element of .
Every finitely generated module over a PID is a direct sum of a free module and cyclic prime-power torsion modules.
Every finitely generated torsion-free module over a principal ideal domain is free. In the structure theorem, torsion-freeness removes every cyclic torsion summand and leaves only the free summand.
An integral matrix satisfying makes a module over the Eisenstein integers by letting the primitive cube root act as . This module is finitely generated and torsion-free, hence free. Since the Eisenstein integers have integer rank two, such matrices exist only for ; for that dimension every one is integrally conjugate to
An elementary divisor is a prime power occurring in the cyclic decomposition of a finitely generated torsion module.
A finite abelian group is indecomposable exactly when it is cyclic of prime-power order. The structure theorem proves necessity. Conversely, every nonzero subgroup of contains its unique subgroup of order , so two nonzero subgroups cannot be complementary direct summands.
An ideal is prime when implies or , equivalently when the quotient is an integral domain.
For a commutative unital ring , an ideal is prime exactly when is an integral domain. The zero-product condition in the quotient translates directly to .
A Boolean ring satisfies for every element. Expanding shows that it has characteristic two.
A nonzero Boolean integral domain has only the elements zero and one, so it is . The quotient criterion then makes every prime quotient of a Boolean ring a field, and every prime ideal maximal.
For an ideal of a commutative ring , reducing coefficients modulo is a surjection with kernel . Hence
The irreducible polynomials over have degree one, or degree two with negative discriminant.
Over a field containing the relevant roots of unity, is irreducible when the valuation data prevent from being a proper prime-divisor power, with the standard fourth-power exception.