Unformatted text preview:

Review: groups, rings, fieldsPolynomials and idealsAlgebraically closed and formally real fieldsIdealsAssociative algebrasQuestions about polynomials1 MIT 6.972 Algebraic techniques and semidefinite optimization February 16, 2006 Lecture 4 Lecturer: Pablo A . Parrilo Scribe: Pablo A. Parrilo In this lecture we will review some basic elements of abstract algebra. We also introduce and begin studying the main objects of our considerations, multivariate polynomials. Review: groups, rings, fields We present here standard background material on abstract algebra. Most of the definitions are from [Lan71, CLO97, DF91, BCR98]. Definition 1 A group consists of a set G and a binary operation “ ” defined on G, for which the · following conditions are satisfied: 1. Associative: (a · b) · c = a · (b · c), for all a, b, c ∈ G. 2. Identity: There exist 1 ∈ G such that a · 1 = 1 · a = a, for all a ∈ G. 3. Inverse: Given a ∈ G, there exists b ∈ G such that a · b = b · a = 1. For example, the integers Z form a group under addition, but not under multiplication. Another example is the set GL(n, R) of real nonsingular n × n matrices, under matrix multiplication. If we drop the condition on the existence of an inverse, we obtain a monoid. Note that a monoid always has at least one element, the identity. As an example, given a set S, then the set of all strings of elements of S is a monoid, where the monoid operation is s tring concatenation and the identity is the empty string λ. Another example is given by N0, with the operation being addition (in this case, the identity is the zero). Monoids are also known as semigroups with identity. In a group we only have one binary operation (“multiplication”). We will introduce another operation (“addition”), and study the structure that results from their interaction. Definition 2 A commutative ring (with identity) consists of a set k and two binary operations “ ·” and “+”, defined on k, for which the following conditions are satisfied: 1. Associative: (a + b) + c = a + (b + c) and (a · b) · c = a · (b · c), for all a, b, c ∈ k . 2. Commutative: a + b = b + a and a · b = b · a, for all a, b ∈ k. 3. Distributive: a · (b + c) = a · b + a · c, for all a, b, c ∈ k. 4. Identities: There exist 0, 1 ∈ k such t hat a + 0 = a · 1 = a, for all a ∈ k. 5. Additive inverse: Given a ∈ k, t here exists b ∈ k such that a + b = 0. A simple example of a ring are the integers Z under the usual operations. After formally introducing polynomials, we will see a few more examples of rings. If we add a requirement for the existence of multiplicative inverses, we obtain fields. Definition 3 A field consists of a set k and two binary operations “ ·” a nd “+”, defined on k, for which the following conditions are satisfied: 1. Associative: (a + b) + c = a + (b + c) and (a · b) · c = a · (b · c), for all a, b, c ∈ k . 2. Commutative: a + b = b + a and a · b = b · a, for all a, b ∈ k. 3. Distributive: a · (b + c) = a · b + a · c, for all a, b, c ∈ k. 4-1��� 4. Identities: There exist 0, 1 ∈ k, where 0 = 1, such that a + 0 = a · 1 = a, for all a ∈ k. 5. Additive inverse: Given a ∈ k, t here exists b ∈ k such that a + b = 0. 6. Multiplicative inverse: Given a ∈ k, a = 0, there exists c ∈ k such that a · c = 1. Any field is obviously a commutative ring. Some commonly used fields are the rationals Q, the reals R and the complex numbers C. There are also Galois or finite fields (the set k has a finite number of elements), such as Zp, the set of integers modulo p, where p is a prime. Another important field is given by k(x1, . . . , xn), the set of rational functions with coefficients in the field k, with the natural operations. 2 Polynomials and ideals Consider a given field k, and let x1, . . . , xn be indeterminates. We can then define polynomials. Definition 4 A polynomial f in x1, . . . , xn with coefficients in a field k is a fi nite linear combination of monomials: � � α1 αnf = cαx α = cαx1 . . . x n , cα ∈ k, (1) α α where the sum is over a finite number of n-tuples α = (α1, . . . , αn), αi ∈ N0. The set of all polynomials in x1, . . . , xn with coefficients in k is denoted k[x1, . . . , xn]. It follows from the previous definitions that k[x1, . . . , xn], i.e., the set of polynomials in n variables with coefficients in k, is a commutative ring with identity. We also notice that it is possible (and sometimes, convenient) to define polynomials where the coefficients belong to a ring with identity, not necessarily to a field. Definition 5 A form is a polynomial where all the monomials have the same degree d := αi. In this i case, the polynomial is homogeneous of degree d, since it satisfies f (λx1, . . . , λxn) = λdf(x1, . . . , xn). A commutative ring is called an integral domain if it has no zero divisors, i.e. a = 0� , b = 0 a· b = 0. � ⇒ �Every field is also an integral domain (why?). Two examples of rings that are not integral domains are the set of matrices Rn×n, and the set of integers modulo n, when n is a composite number (with the usual operations). If k is an integral domain, then so is k[x1, . . . , xn]. Remark 6 Another important example of a ring (in this case, non-commutative) appears in systems and control theory, through the ring M(s) of stable proper rational functions. This is t he set of matri-ces (of fixed dimension) whose entries are rational functions of s (i.e., in the field C(s)), are bounded at infinity, and have all poles in the strict left-half plane. In this algebraic setting (usually called “co-prime factorization approach”), the question of finding a stabilizing controller is exactly equivalent to the solvability of a Diophantine equation ax + by = 1. 2.1 Algebraically closed and formally real fields A very important property of a univariate polynomial p is the existence of a root, i.e., an element x0 for which p(x0) = 0. Depending …


View Full Document

MIT 6 972 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?