Nicholas Loehr - Combinatorics, Second Edition

This appendix reviews some definitions from abstract algebra and linear algebra that are needed in certain parts of the main text.

This section defines abstract algebraic structures called rings and fields. (Groups are studied in detail in .) Our main purpose for introducing these concepts is to specify the most general setting in which certain algebraic identities are true.

Definition of a Ring. rings A ring consists of a set R and two binary operations + (addition) and (multiplication) with domain R R , subject to the following axioms.associativitycommutativity

We often write xy instead of x y . R is a commutative ring iff R satisfies the additional axiom

For example, Z (the set of integers), Q (the set of rational numbers), R (the set of real numbers), and C (the set of complex numbers) are all commutative rings under the usual operations of addition and multiplication. For n > 0 , the set Z n = { 0 , 1 , 2 , , n - 1 } of integers modulo n is a commutative ring using the operations of addition and multiplication mod n . For n > 1 , the set M n ( R ) of n n matrices with real entries is a non-commutative ring.

Definition of an Integral Domain. An integral domain integral domains is a commutative ring R such that 1 R 0 R and R has no zero divisors:

For example, Z is an integral domain. Z 6 is not an integral domain, since 2 and 3 are nonzero elements of Z 6 whose product in this ring is 0.

Definition of a Field. A field fields is a commutative ring F such that 1 F 0 F and every nonzero element of F has a multiplicative inverse:

For example, Q , R , and C are fields, but Z is not a field. One can show that Z n is a field iff n is prime.

Let R be a ring, and suppose x 1 , x 2 , , x n R . Because addition is associative, we can unambiguously write a sum like x 1 + x 2 + x 3 + + x n without parentheses. Similarly, associativity of multiplication implies that we can write the product x 1 x 2 x n without parentheses. Because addition in the ring is commutative, we can permute the summands in a sum like x 1 + x 2 + + x n without changing the answer. More formally, for any bijection f : { 1 , 2 , , n } { 1 , 2 , , n } and all x 1 , , x n R , we have

It follows that if { x i : i I } is a finite indexed family of ring elements, then the sum of all these elements (denoted i I x i ) is well-defined. Similarly, if A is a finite subset of R , then x A x is well-defined. On the other hand, the products i I x i and x A x are not well-defined (when R is non-commutative) unless we specify in advance a total ordering on I and A .

Let F be a field with additive identity 0 F and multiplicative identity 1 F . It sometimes happens that there exist positive integers n such that n . 1 F (the sum of n copies of 1 F ) is equal to 0 F . The characteristic characteristic of a field of F is defined to be the least n > 0 such that n . 1 F = 0 F ; if no such n exists, the characteristic of F is zero. For example, Q , R , and C are fields of characteristic zero, whereas Z p (the integers modulo p for a prime p ) is a field of characteristic p . It can be shown that the characteristic of every field is either zero or a prime positive integer. When F has characteristic zero, all the field elements n . 1 F (for n Z > 0 ) are nonzero and hence invertible in F .

Next we recall the definitions of the fundamental algebraic structures of linear algebra.

Definition of a Vector Space. vector spaces Given a field F , a vector space over F consists of a set V , an addition operation + with domain V V , and a scalar multiplication with domain F V , that satisfy the following axioms.

When discussing vector spaces, elements of V are often called vectors , while elements of F are called scalars . For any field F , the set F n = { ( x 1 , , x n ) : x i F } is a vector space over F with operations

Definition of an Algebra. algebras Given a field F , an algebra over F is a set A that is both a ring and a vector space over F such that the ring multiplication (denoted v w ) and the scalar multiplication (denoted c v ) satisfy this axiom:

We only consider associative algebras. For example, given any field F , let F [ x ] be the set of all formal polynomials a 0 + a 1 x + + a k x k where all coefficients a 0 , a 1 , , a k come from F . This is a commutative algebra over F (called the one-variable polynomial ring with coefficients in F ) using the standard operations of polynomial addition, polynomial multiplication, and multiplication of a polynomial by a scalar. Some relatives of this algebra appear in the main text when we study formal power series and Laurent series. An example of a non-commutative algebra is the set M n ( R ) of n n real-valued matrices, where n > 1 . More generally, for any field F , the set M n ( F ) of n n matrices with entries in F is an algebra over F using the usual formulas for the matrix operations.

We can also consider algebras where the field F of scalars is a replaced by any commutative ring R . For example, the set of polynomials R [ x 1 , , x N ] is a commutative algebra over R , and the set of matrices M n ( R ) is a non-commutative algebra over R when n > 1 and | R | > 1 .

Subgroups of groups are defined and studied in . Here we define the analogous concepts for other algebraic structures: subrings, ideals, subspaces, and subalgebras. In each case, we are looking at subsets that are closed under the relevant algebraic operations.

Definition of Subrings and Ideals. subringsideals Let R be a ring. A subring of R is a subset S of R such that 0 R S , 1 R S , and for all x , y S , x + y and - x and xy are in S . An ideal of R is a subset I of R such that 0 R I and for all x , y I and all r R , x + y and - x and rx and xr are in I .

Definition of Subspaces. subspaces Let V be a vector space over a field F . A subspace of V is a subset W of V such that 0 V W and for all x , y W and all c F , x + y and cx are in W .