MAA201 Lecture Notes
Uploaded by
salome.mose2MAA201 Lecture Notes
Uploaded by
salome.mose2Javier Fresán
REDUCTION OF ENDOMORPHISMS
– MAA
Javier Fresán
Year -
REDUCTION OF ENDOMORPHISMS – MAA
Javier Fresán
CONTENTS
. Arithmetic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Euclidean division. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Equivalence relations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Prime numbers and the fundamental theorem of arithmetic . . . . . . . . . . . . . . .
.. Greate common divisor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Groups. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. The notion of group. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Group morphisms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Subgroups. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Rings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Definition of rings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Subrings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Ideals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Invertible elements and fields. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Ring morphisms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Polynomials. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Euclidean division. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Ideals of the ring of polynomials. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Irreducible polynomials and roots. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Endomorphisms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Minimal polynomial of an endomorphism. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Eigenvalues and eigenve ors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Diagonalisable endomorphisms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Chara eri ic polynomial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. The Jordan-Chevalley decomposition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
CHAPTER
ARITHMETIC
In what follows, we shall denote by
N = {, , , . . . }
the set of natural numbers and by
Z = {. . . , −, −, , , , . . . }
the set of integers. The set Z is equipped with operations
– sum + : Z × Z → Z, (x, y) 7→ x + y
– produ × : Z × Z → Z, (x, y) 7→ xy
– opposite − : Z × Z, x 7→ −x
We will write x − y in ead of x + (−y) and call it the difference of the integers x and y.
The theory of groups and rings is a generalisation of (some of) the properties satis-
fied by these operations
The set of integers is also equipped with an order relation x ≤ y (that sometimes we
also write as y ≥ x)
Given an integer x, we call absolute value of x the natural number |x| given by
x
if x ≥ ,
|x| =
−x if x ≤ .
We shall repeatedly use the following axiom:
Well-ordering principle. — Any non-empty subset S of the natural numbers N contains
a minimal element, that is, an element s such that s ≤ x for all x ∈ S.
Algebra MAA – Bachelor – Year Chapter – Arithmetic
.. Euclidean division
Theorem . (Euclidean division). — Given two integers a, b ∈ Z with b , , there exi s
a unique pair of integers (q, r) ∈ Z × Z such that
a = qb + r, ≤ r < |b|.
We call q the quotient and r the remainder.
Proof. — We fir prove exi ence. Let us consider the set
() S = {a − bk | k ∈ Z} ∩ N.
We observe that S is non-empty. Indeed, if a ≥ , then a ∈ S (take k = in ()). If
a < , then a( + b) ∈ S if b ≤ − (take k = −a) and a( − b) ∈ S if b ≥ (take k = a). By
the well-ordering principle, S contains a minimal element r, which is thus of the form
a − bq for some integer q ∈ Z. We have in this way written a = bq + r with r ≥ and it
remains to show that r < |b|. Assume by contradi ion that r ≥ |b|. Then
a − b(q + ) if b ≥
≤ r − |b| = a − bq − |b| =
a − b(q − ) if b ≤ −
belongs to the subset S. Since r is the minimal element of S and r −|b| is ri ly smaller
than r this yields a contradi ion. Therefore, r < |b|.
We now turn to the proof of unicity. For this, let (q , r ) and (q , r ) be two pairs of
integers satisfying the conditions in the theorem, that is
a = bq + r , a = bq − r , ≤ r < |b|, ≤ r < |b|.
The difference of the fir two equalities gives
= b(q − q ) + (r − r )
and, passing to the absolute value, |b||q −q | = |r −r |. Since r and r lie in the interval
[, |b|), their difference is ri ly smaller than the size of the interval: |r − r | < |b|.
Therefore, |q − q | < . The only integer whose absolute value is ri ly smaller than
being , we find q = q , then r = r . This proves unicity and completes the proof of
the theorem.
Definition .. — Given two integers a and b, we say that b divides a (or that b is a
divisor of a, or yet that a is divisible by b) if there exi s an integer k ∈ Z such that
a = bk.
Algebra MAA – Bachelor – Year Chapter – Arithmetic
If b = , then a = as well. Otherwise, the definition is equivalent to asking that
r = in the Euclidean division.
Example .. — Let us determine the integers n ∈ Z such that n + is divisible by
n + . We fir exclude the case n = −, since for this particular value n + = but
n + = . If n + , , we consider the equality
n + = (n + )(n − ) +
If < |n−|, that is, if n < {, }, then the integers q = n− and r = satisfy the conditions
of the theorem and n + is not divisible by n + . In the remaining cases, one checks
that + = is divisible by + = and that + = is divisible by + = .
Therefore, the only integers with this property are n = and n = .
For each natural number n ≥ , we will denote by
Z/nZ = {[], [], . . . , [n − ]}
the set of all possible reminders of division by n. In the next se ion, we explain an
ab ra way to under and this con ru ion by means of equivalence relations.
.. Equivalence relations
Definition . (Binary relation). — Let S be a set. A binary relation on S is a subset R
of the produ
S × S = {(a, b) | a, b ∈ S}.
We write aRb or a ∼ b to indicate that the pair (a, b) belongs to S.
Definition . (Equivalence). — A binary relation is said to be an equivalence relation
if the following three properties are satisfied:
. Reflexivity: x ∼ x for all elements x ∈ S;
. Symmetry: for each two elements x, y ∈ S, if x ∼ y then y ∼ x;
. Transitivity: for each three elements x, y, z ∈ S, if x ∼ y and y ∼ z, then x ∼ z.
Example .. — Let S = {a, b, c} be a set consi ing of three elements. The number of
possible binary relations on S is simply the number of subsets of S × S. Since S × S has
elements, this number is = . Let us see how many among these are equivalence
relations. Fir of all, by reflexivity, a subset needs to contain (a, a), (b, b) and (c, c) to
be an equivalence relation. This is the minimal possibility (the equivalence relation
Algebra MAA – Bachelor – Year Chapter – Arithmetic
being equality). Assume the subset contains another element, say (a, b). Then, by
symmetry, it also needs to contain (b, a). The subset {(a, a), (b, b), (c, c), (a, c), (c, a)} is an
equivalence relation, and {(a, a), (b, b), (c, c), (b, c), (c, b)} and {(a, a), (b, b), (c, c), (a, b), (b, a)}
are equivalence relations as well the equivalence relation contains (a, b) and (b, c). Then
it is easy to check that, by transitivity, the subset is the whole S × S. In conclusion,
among the binary relations there are only equivalence relations, namely:
{(a, a), (b, b), (c, c)}, {(a, a), (b, b), (c, c), (a, b), (b, a)}, {(a, a), (b, b), (c, c), (b, c), (c, b)},
{(a, a), (b, b), (c, c), (a, b), (b, a)}, S × S.
Example .. — An important example for us will be the following. Fix an integer
n ≥ and consider the binary relation on the set S = Z given by
x ∼ y if n divides x − y.
We will also write x ≡ y mod n and say that x and y are congruent modulo n. Let us
check that it is an equivalence relation:
. Reflexivity: for each integer x, we have x ∼ x since n divides x − x = .
. Symmetry: if x ∼ y, then n divides x − y, which means that there exi s an integer
k ∈ Z such that x − y = kn. Then n divides y − x = (−k)n as well, so y ∼ x.
. Transitivity: if x ∼ y and y ∼ z, then there exi s integers k , k ∈ Z such that
x − y = k n and y − z = k n. Then
x − z = (x − y) + (y − z) = k n + k n = (k + k )n
is divisible by n, and therefore x ∼ z.
Definition . (Equivalence class). — Let S be a set and let ∼ be an equivalence rela-
tion on S. Given an element x ∈ S, the equivalence class of x is the subset
[x] = {y ∈ S | x ∼ y} ⊂ S.
Observe that, by symmetry, it does not matter if we write x ∼ y or y ∼ x in the above
definition. We say that x is a representative of the equivalence class [x].
Lemma .. — The equivalence classes form a partition of S. In other words,
[
S= [x]
x∈S
and, if [x ] ∩ [x ] , ∅, then [x ] = [x ].
Algebra MAA – Bachelor – Year Chapter – Arithmetic
Proof. — Since ∼ is reflexive, each element x of S belongs to its equivalence class [x]
and S is therefore the union of [x]. Now let x , x ∈ S and suppose that the equiva-
lence classes [x ] and [x ] interse . Let y ∈ [x ] ∩ [x ]. Then x ∼ y and y ∼ x , so by
transitivity x ∼ x . This implies that [x ] = [x ].
Definition .. — A binary relation is said to be antisymmetric if, for each two elements
x, y ∈ S such that x ∼ y and y ∼ x, one has x = y. An order relation is a binary relation
which is reflexive, antisymmetric, and transitive.
For example, the subset {(x, y) ∈ Z | x ≤ y} is an order relation on S = Z.
.. Prime numbers and the fundamental theorem of arithmetic
Definition . (Prime number). — A prime number is an integer p ≥ whose only
divisors are and p.
Equivalently, prime numbers are those integers ≥ that cannot be written as a prod-
u ab with a ≥ and b ≥ . Here is the li of the fir prime numbers:
, , , , , , , . . .
Lemma .. — Every integer n ≥ is a produ of prime numbers.
Proof. — If n is not prime, then we can write n = ab with a, b < n. If one among a and
b is not prime, we continue. The process ops since each time we get ri ly smaller
integers.
Theorem . (Euclid). — There exi infinitely many prime numbers.
Proof. — By contradi ion, assume that there are only finitely many prime numbers,
say p , . . . , pr . Consider the integer
N = p . . . pr + .
By Lemma ., N should be divisible by a prime number. However N is not divisible
by any of the pi (the remainder in Euclidean division is ). This is a contradi ion.
Remark .. — One could think, examining this proof, that if p , . . . , pr denote the fir
r prime numbers, then the integer p . . . pr + is a prime number. This is not true, the
fir example being
· · · · · + = · .
Algebra MAA – Bachelor – Year Chapter – Arithmetic
Theorem . (Euclid’s lemma). — Let a, b be integers. If a prime number p divides ab,
then p divides either a or b.
Proof. — We assume that p does not divide a and we wish to prove that p divides b.
For this, consider the set
S = {n ≥ | p divides an}.
This is a non-empty set of the natural numbers N since it contains p. By the well-
ordering principle, it contains a minimal element m, which satisfies m ≥ since p does
not divide a by assumption. Let n be an element of S. Performing Euclidean division,
we can write n = mq + r with ≤ r < m. Then
ar = an − (am)q
and, since p divides both an and am (this is what the conditions n ∈ S and m ∈ S
mean), we have that p divides ar. Since r < m and m is the minimal element ≥ with
the property that p divides am, we find r = . In other words, all elements of S are
multiples of m. Since p ∈ S and b ∈ S by the assumption that p divides ab, this means
that m divides p and m divides b. Since m ≥ and p is prime, we deduce m = p.
Therefore, p divides b.
Corollary .. — If a prime number p divides a produ of integers, then it divides one of
the fa ors. In particular, if p divides a produ of prime numbers, then it is equal to one of
them.
Theorem . (Fundamental theorem of arithmetic). — Every integer n ≥ can be
uniquely written as
n n n
n = p · p · · · pr r ,
where pi are prime numbers, ordered as p < p < · · · < pr , and ni ≥ are integers. We call
this the decomposition of n into prime fa ors.
Proof. — The exi ence follows immediately from Lemma ., one ju needs to re-
group the fa ors. To prove unicity, assume that
n n m ms
p . . . pr r = q . . . qs
are two such fa orisations. By Corollary ., the sets {p , . . . , pr } and {q , . . . , qs } coin-
cide, hence r = s. On the other hand, since p < p < and q < q , we have pi = qi for all
i = , . . . , r. Finally, ni = mi since otherwise there would be a prime number dividing a
produ of prime numbers di in from it.
Algebra MAA – Bachelor – Year Chapter – Arithmetic
We define the p-adic valuation
vp : Z −→ N ∪ {+∞}
as follows:
. vp () = +∞ and vp () = ,
. vp (−n) = vp (n),
. for each integer n ≥ , vp (n) is the exponent of p in the decomposition of n into
prime fa ors.
.. Greate common divisor
Definition .. — Let a, b be two integers. We say that a and b are coprime if there is
no prime number dividing both a and b.
Proposition .. — Let a, b ∈ Z be integers, not both equal to zero. There exi s a unique
integer d ≥ such that d is a common divisor of a and b and such that every common divisor
of a and b divides d. Explicitly,
Y
d= pmin(vp (a),vp (b)) .
p prime
We call d the greate common divisor of a and b and we denote it by gcd(a, b).
Proof. — The integer d is well defined since a and b are both non-zero. Since
min(vp (a), vp (b) is ≤ vp (a) and ≤ vp (b), then d divides a and d divides b (that is, d
is a common divisor of a and b). If c divides both a and b, then vp (c) ≤ vp (a) and
vp (c) ≤ vp (b). Therefore, vp (c) ≤ min(vp (a), vp (b)), which implies that c divides d.
Finally, if d 0 is another integer with the same properties, then d divides d 0 and d 0
divides d, so d = d 0 .
Remark .. — Two integers a and b are coprime if and only if gcd(a, b) = .
Remark .. — The integers a/d and b/d are coprime. Indeed,
vp (a/d) = vp (a) − vp (d), vp (b/d) = vp (b) − vp (d)
and since vp (d) is either vp (a) or vp (b), we have
min(vp (a/d), vp (b/d)) = ,
which means that the greate common divisor of a and b is .
Algebra MAA – Bachelor – Year Chapter – Arithmetic
Theorem . (Bézout). — Given any two integers a, b ∈ Z, not both equal to zero, there
exi s integers u and v such that
gcd(a, b) = au + bv.
In particular, if a and b are coprime, there exi s integers u, v such that = au + bv.
Proof. — Consider the set
S = {au + bv | u, v ∈ Z} ∩ (N \ {}).
It is a non-empty subset of N, so by the well-ordering principle it contains a minimal
element c. Since S does not contain , we have c ≥ . We claim that S = {ck | k ≥ } and
that c is the greate common divisor of a and b. We fir observe that {ck | k ≥ } ⊂ S.
Indeed, since c is an element of S, it can be written as c = au + bv for some integers u
and v , and then ck = a(u k) + b(v k) belongs to S. Conversely, take n ∈ S. By Euclidean
division, there exi s integers q, r ∈ Z such that
n = cq + r, ≤ r < c.
Since r = n − cq belongs to S, this implies r = by minimality of c. We have thus
checked the equality S = {ck | k ≥ }. It remains to prove that c is the greate common
divisor of a and b. For this, we observe that c divides a and b and that, since c = au +bv,
every common divisor of a and b divides c as well.
CHAPTER
GROUPS
.. The notion of group
Definition .. — A group is a set G together with an operation ∗ : G × G → G, called
the group law, that satisfies the following three properties:
() Associativity: the equality
x ∗ (y ∗ z) = (x ∗ y) ∗ z
holds for any three elements x, y, z ∈ G.
() Exi ence of a neutral element: there exi s an element e ∈ G such that
x∗e = e∗x = x
for all elements x ∈ G.
() Exi ence of an inverse: given any x ∈ G, there exi s an element y ∈ G such that
x ∗ y = y ∗ x = e.
Definition .. — We say that a group G is abelian (or, sometimes, commutative) if the
group law is commutative, that is, the equality
x∗y = y ∗x
holds for all elements x, y ∈ G.
A few remarks about these definitions are in order:
Remark . (Uniqueness of the neutral element). — For the condition on the exis-
tence of an inverse to make sense, one needs to know that the element e in property ()
Algebra MAA – Bachelor – Year Chapter – Groups
is unique. Indeed, if there are two such elements e and e , then
e = e ∗ e apply () to e and x = e
= e apply () to e and x = e .
Therefore, there is a unique element e ∈ G such that x ∗ e = e ∗ x = x for all x ∈ G. We
call it the neutral element of the group G. When we want to emphasise the group we
are referring to, we will write eG for the neutral element.
Remark . (Uniqueness of the inverse element). — Next we can show that, for a
fixed x ∈ G, there is a unique element y ∈ G such that x ∗ y = y ∗ x = e. Indeed, assume
there are two such elements y and y . Then:
y = y ∗ e e is the neutral element
= y ∗ (x ∗ y ) y satisfies x ∗ y = e
= (y ∗ x) ∗ y associativity of the group law
= e ∗ y y satisfies y ∗ x = e
= y e is the neutral element.
We will call the unique y such that x ∗ y = y ∗ x = e the inverse of x for the group law ∗
and denote it by x− . Since x− ∗ x = x ∗ x− = e, the element x is an inverse of x− , and
hence (x− )− = x by uniqueness of the inverse.
Remark . (About notation). — In Definition . we used the notation ∗ for the
group law. We will often write xy in ead of x ∗y (multiplicative notation) or x +y if the
group G is abelian (additive notation). In the multiplicative case, the neutral element
is often denoted by . In the additive case, the neutral element is often denoted by
and the inverse element by −x in ead of x− .
.. Examples
A group cannot be empty since it always contains at lea the neutral element e.
Example .. — If G consi s of one element, then G = {e} and the group law is given
by e ∗ e = e. This is called the trivial group. We say that a group G is non-trivial if G is
not equal to the trivial group, that is, if G contains at lea two elements.
Algebra MAA – Bachelor – Year Chapter – Groups
Example .. — If G has two elements, say the neutral element e and a second ele-
ment a, then e ∗ e = e and e ∗ a = a ∗ e = a by the definition of the neutral element. To
determine the group law it remains to compute a ∗ a, which takes one of the values e
or a. But if a ∗ a = a, then a would not have an inverse. Therefore, a ∗ a = e. The group
law is pi ured in the following mutliplication table:
∗ e a
e e a
a a e
Example .. — We now assume that G consi s of three elements e, a, b. Again by
definition of the neutral element,
e ∗ e = e, e ∗ a = a ∗ e = a, e ∗ b = b ∗ e = b.
In determining the re of the group law, the following lemma will be useful:
Lemma .. — Let G be a group and let g ∈ G be an element. The map
ϕ : G −→ G
x 7−→ x ∗ g
is a bije ion. The same is true for the map x 7→ g ∗ x.
Proof. — Let x, y ∈ G be elements such that ϕ(x) = ϕ(y), that is, x∗g = y ∗g. Multiplying
on the left by the inverse g − of g yields x = y; therefore, ϕ is an inje ive map. Now
let h ∈ G. Since h = h ∗ e = h ∗ (g − ∗ g) = (h ∗ g − ) ∗ g = ϕ(h ∗ g − ), the map ϕ is surje ive.
The proof for the second claim is identical.
In terms of the multiplication table, the lemma says that in each row and column
all elements of the group should appear exa ly one time. It is like filling a Sudoku!
Going back to our example of a group of three elements, this implies that the only
possible group law is given by
∗ e a b
e e a b
a a b e
b b e a
Algebra MAA – Bachelor – Year Chapter – Groups
(For example, a ∗ a cannot be equal to a, since this would imply a = e, and if a ∗ a = e,
then the la entry of the second row should be equal to b, but then b appears twice on
the third column). It is easy to check that the operation defined by the above table is
associative and defines thus a group law on G.
Example .. — The set of integers Z together with the sum + : Z × Z → Z forms an
abelian group. Indeed, addition of integers is associative and commutative. The neu-
tral element is and the inverse of an integer n is the integer −n. Similarly, the rational
numbers Q, the real numbers R, and the complex numbers C are abelian groups to-
gether with addition. When we speak of the groups Z, Q, R, or C, without making the
group law explicit, it always means that we are considering addition.
Example .. — The set G = Z \ {} of non-zero integers together with the multipli-
cation · : G × G → G does not form a group since the neutral element is but the only
integers x ∈ Z × {} such that the equation xy = has an integer solution y ∈ Z are x =
and x = −. In other words, an integer different from and − does not have an in-
verse for multiplication. However, if one enlarges to non-zero rational numbers Q× or
to non-zero real numbers R× with multiplication, one obtains groups. Also the set of
positive real numbers R> = {x ∈ R | x > } is a group with respe to multiplication.
Example . (The group of integers modulo n). — Let n ≥ be an integer. Recall
from Se ion . the set Z/nZ of equivalence classes of integers with respe to the
equivalence relation x ∼ y if n divides x − y. It has representatives
Z/nZ = {[], [], · · · , [n − ]}.
We define an operation
+ : Z/nZ × Z/nZ −→ Z/nZ
([x], [y]) 7−→ [x + y].
The fir thing we need to check is that this definition does not depend on the choice
of representatives of the equivalence classes, that is, if we replace the integers x and y
with integers x0 and y 0 such that [x] = [x0 ] and [y] = [y 0 ], then we ill get the same
result. Indeed, the equality [x] = [x0 ] means that there exi s an integer k such that
x − x0 = k n and [y] = [y 0 ] means that there exi s an integer k such that y − y 0 = k n.
But then
(x + y) − (x0 + y 0 ) = (x − x0 ) + (y − y 0 ) = k n + k n = (k + k )n
Algebra MAA – Bachelor – Year Chapter – Groups
is divisible by n, which means that [x +y] = [x0 +y 0 ]. The operation is thus well defined.
It is associative, since sum of integers is, it has neutral element [], and the inverse
of an equivalence class [x] is the equivalence class [−x]. Moreover, this operation is
commutative. Therefore, (Z/nZ, +) is an abelian group. Again, when we speak of the
group Z/nZ without specifying the group law, we always mean addition.
For example, here is the multiplication table of the group Z/Z:
∗ [] [] [] [] [] []
[] [] [] [] [] [] []
[] [] [] [] [] [] []
[] [] [] [] [] [] []
[] [] [] [] [] [] []
[] [] [] [] [] [] []
[] [] [] [] [] [] []
Example . (The symmetric group). — Let n ≥ be an integer and let X be a finite
set of n elements, for example X = {, , . . . , n}. Let G be the set of all permutations of X,
that is, of all bije ive maps σ : X → X. Each such map has an inverse σ − : X → X with
the property that σ ◦σ − = σ − ◦σ = Id, where Id : X → X is the identity map that sends
every element x ∈ X to itself. We endow G with the group law
G × G −→ G (σ , σ ) 7−→ σ ◦ σ ,
where ◦ ands for the composition of maps from X to X. This operation is associative,
since composition of maps is, has as neutral element Id, and the inverse of a permu-
tation σ is the inverse map σ − . The resulting group is called the symmetric group Sn
and has n! elements. A way to pi ure a permutation σ is as a matrix with two rows
··· n
σ () σ () ··· σ (n)
where we write below each element x ∈ X the element σ (x) ∈ X to which x is mapped
by the permutation.
The symmetric group Sn is not abelian for n ≥ . For example, for n = it consi s
of the following six elements:
Id, σ = , σ = , τ = , τ = , τ =
Algebra MAA – Bachelor – Year Chapter – Groups
and one checks that the two elements
σ τ = ◦ = = τ
τ σ = ◦ = = τ
are different. Here is the complete multiplication table for S :
∗ Id σ σ τ τ τ
Id Id σ σ τ τ τ
σ σ σ Id τ τ τ
σ σ Id σ τ τ τ
τ τ τ τ Id σ σ
τ τ τ τ σ Id σ
τ τ τ τ σ σ Id
Example .. — Let GL (R) be the set of invertible by matrices with real coeffi-
cients. Since such a matrix is invertible if and only if its discriminant is non-zero, we
can explicitly describe this set as
n o
GL (R) = ac db | a, b, c, d ∈ R, ad − bc , .
Together with multiplication of matrices as a group law, GL (R) is a group. The neutral
element is the identity matrix ( ), and the inverse is given by
!− d −b
!
a b
= ad−bc
−c
ad−bc ,
a
c d ad−bc ad−bc
which lies in GL (R) since it has real entries and determinant equal to (ad − bc)− , .
This groups is not abelian. For example,
! ! ! ! ! !
= but = .
Algebra MAA – Bachelor – Year Chapter – Groups
.. Group morphisms
Definition .. — Let G and G be two groups with group laws ∗ and ∗ respe ively.
A group morphism (also called a group homomorphism or simply a homomorphism) is a
map ϕ : G → G which is compatible with the group laws in that
() ϕ(x ∗ y) = ϕ(x) ∗ ϕ(y)
for all elements x, y ∈ G .
Lemma .. — Let ϕ : G → G be a group homomorphism.
(a) One has ϕ(eG ) = eG , where eG and eG denote the neutral elements of G and G .
(b) For all x ∈ G , one has ϕ(x− ) = ϕ(x)− .
Proof. — Pick an element x ∈ G (recall that all groups are non-empty!) Plugging the
element y = eG in equation () yields
ϕ(x) = ϕ(x) ∗ ϕ(eG )
and multiplying both sides on the left by the inverse of ϕ(x) for the group law ∗ we
get ϕ(eG ) = eG . This proves the fir claim.
For the second one, plugging y = x− in equation () yields
eG = ϕ(eG ) = ϕ(x) ∗ ϕ(x− )
for all x ∈ G , and exchanging the roles of x and y yields eG = ϕ(x− ) ∗ ϕ(x) for
all x ∈ G . Therefore, ϕ(x− ) is the inverse of ϕ(x) for the group law ∗ .
Example .. — Let (Z, +) be the group of integers together with addition as the
group law and let n be an integer. The map ϕ : Z → Z that sends x ∈ Z to ϕ(x) = nx is
a group homomorphism. Indeed,
ϕ(x + y) = n(x + y) = nx + ny = ϕ(x) + ϕ(y)
for all integers x, y ∈ Z. Moreover, all group homomorphisms ϕ : Z → Z are of this
form. Indeed, setting n = ϕ(), we have
ϕ(x) = ϕ( + · · · + ) = ϕ() + · · · + ϕ() = nx
| {z } | {z }
x times x times
for all x > by the definition of group homomorphism, and ϕ() = and ϕ(−x) = −ϕ(x)
by Lemma .. Hence ϕ(x) = nx for all x ∈ Z.
Algebra MAA – Bachelor – Year Chapter – Groups
Example .. — On the contrary, the map ϕ : Z → Z given by ϕ(x) = x is not a group
homomorphism, as ϕ(x+y) = (x+y) = x +y +xy is different from ϕ(x)+ϕ(y) = x +y .
Example .. — The map
det : GL (R) −→ R∗
!
a b
7−→ ad − bc
c d
is a group homomorphism, since the determinant of a produ of two matrices is the
produ of their determinants.
Example .. — Consider the group (R, +) of real numbers together with addition
(Example .) and the group (R> , ·) of positive real numbers together with multipli-
cation (Example .). The exponential
exp : (R, +) −→ (R> , ·), x 7−→ exp(x)
is a group morphism since exp(x) is positive for all x ∈ R and exp(x + y) = exp(x) exp(y)
for all x, y ∈ R. The inverse of this map, the logarithm
log : (R> , ·) −→ (R, +), x 7−→ log(x)
is also a group morphism, as log(xy) = log(x)+log(y). This can be seen as an illu ration
of the general lemma below.
Lemma .. —
. Let G , G , G be groups and let f : G → G and g : G → G be group morphisms.
Then g ◦ f : G → G is also a group morphism.
. If a group morphism f : G → G is bije ive, then the inverse map f − : G → G is a
group morphism as well.
Proof. — To prove the fir claim, we denote by ∗ , ∗ and ∗ the group laws in G , G
and G respe ively. Let x, y ∈ G be any two elements. Then:
(g ◦ f )(x ∗ y) = g(f (x ∗ y)) definition of composition
= g(f (x) ∗ f (y)) f is a group morphism
= g(f (x)) ∗ g(f (y)) g is a group morphism
= (g ◦ f )(x) ∗ (g ◦ f )(y) definition of composition.
This shows that g ◦ f : G → G is a group morphism.
Algebra MAA – Bachelor – Year Chapter – Groups
We now turn to the proof of the second claim. Let f − : G → G be the inverse map
of f . We need to check that
() f − (x ∗ y) = f − (x) ∗ f − (y)
for any two elements x, y ∈ G . Since the map f is bije ive, it is in particular inje ive,
so it suffices to see that both sides of () have the same image under f . The image of
the left hand side is
f (f − (x ∗ y)) = x ∗ y
since f ◦ f − is the identity, and the image of the right hand side is
f (f − (x) ∗ f − (y)) = f (f − (x)) ∗ f (f − (y)) = x ∗ y
since f is a group morphism. This proves the second claim.
Definition .. — We say that two groups G and G are isomorphic if there exi s a
bije ive group morphism f : G → G .
Example .. — In terms of this definition, Examples ., . and . from the pre-
vious se ion are reinterpreted as follows:
– A group of one element is isomorphic to the trivial group.
– A group of two elements is isomorphic to the group Z/Z.
– A group of three elements is isomorphic to the group Z/Z.
.. Subgroups
Definition .. — Let G be a group and let H be a subset of G. We say that H is a
subgroup if the following three conditions hold:
() The neutral element e belongs to H
() If x, y ∈ H, then x ∗ y ∈ H
() For every x ∈ H, the inverse element x− ∈ G lies in H.
In other words, H is a subgroup of G if the group law ∗ : G × G → G re ri s to a group
law ∗ : H × H → H.
A non-trivial group G always contains at lea two subgroups: the whole G and the
trivial subgroup {e}.
Algebra MAA – Bachelor – Year Chapter – Groups
Lemma .. — A subset H of G is a subgroup if and only if H is non-empty and x ∗ y −
belongs to H for all x, y ∈ H.
Proof. — If H is a subgroup, then H is non-empty since it contains the neutral ele-
ment e, and x ∗ y − belongs to H for all x, y ∈ H since y − belongs to H by point () in
the definition and the produ of two elements of H is in H by condition ().
Conversely, assume that H is non-empty and x ∗ y − ∈ H for all x, y ∈ H. Since H
is non-empty, we can pick an element x ∈ H and plug y = x into the assumption; we
find that the neutral element e = x ∗ x− belongs to H. It follows that y − = e ∗ y −
belongs to H for all y ∈ H. We have thus check conditions () and () in the definition
of subgroup. Finally, condition () is seen by writing x ∗ y = x ∗ (y − )− which lies in H
since x and y − do.
Example .. — Consider the group GL (R) of invertible two by two matrices with
real coefficients, as introduced in Example .. The subset
H = {( x ) | x ∈ R}
is a subgroup of GL (R). Indeed, let us check the conditions in Definition .:
() The neutral element ( ) belongs to H (take x = ).
() The produ of two elements of H belongs to H since
() ( x ) · ( y ) = ( x+y
).
() The inverse of an element of H belongs to H since
( x )− = ( −x
).
Thus, H forms a group with respe to multiplication. Equation () says that the map
ϕ : (R, +) −→ H, x 7→ ( x )
is a group morphism. As it is clearly bije ive, the group H is isomorphic to the group
of real numbers with respe to addition.
Example .. — The subset H ⊂ GL (R) consi ing of matrices with integer coeffi-
cients is not a subgroup. It contains the neutral element and is able under multipli-
cation, but it is not true that the inverse of a matrix with integer coefficients ill has
integer coefficients. For example,
( )− = ( / ).
Algebra MAA – Bachelor – Year Chapter – Groups
To get a subgroup, one needs to re ri to those matrices with determinant equal to
or −. Then the subset
n o
H= a b | a, b, c, d ∈ Z, ad − bc ∈ {±} .
c d
is a subgroup of GL (R).
Proposition .. — All subgroups of the integers Z are of the form
nZ = {kn | k ∈ Z}
for some integer n ≥ .
Proof. — The case n = corresponds to the trivial subgroup. Let us assume that H ⊂ Z
is a subgroup different from {}. The set
S = H ∩ (N \ {})
is non-empty since H contains an element x , and −x belongs to H as well. By the
well-ordering principle S contains a minimal element n ∈ S. We claim that H = nZ.
Fir , observe that we have the inclusion nZ ⊂ H. Indeed, an element of nZ is of the
form kn and
k=
k>
n + ··· + n
| {z }
kn = k times
+ · · · + (−n) k <
(−n)
| {z }
−k times
belongs to H since H is a subgroup. Now let x ∈ H. By euclidean division (Theo-
rem .), there exi s unique integers q, r ∈ Z such that x = qn + r and ≤ r < n. Now,
the integer r = x − qn belongs to H since x and −qn do and H is a subgroup. Since n is
the minimal integer > in H, we necessarily have r = , hence x = qn ∈ nZ. This shows
the converse inclusion, hence the equality H = nZ.
Algebra MAA – Bachelor – Year Chapter – Groups
Example .. — Let G be a group and let x ∈ G be an element. Given an integer
k ∈ Z, we define the k-th power of x as
e
k=
k>
x ∗ ··· ∗ x
k
| {z }
x = k times
−
∗ · · · ∗ x− k<
x
| {z }
−k times
The set {xk | k ∈ Z} is a subgroup of G. A group is called cyclic if there exi s an element
x such that this subgroup is the whole G.
CHAPTER
RINGS
.. Definition of rings
Definition .. — A ring is a triple (R, +, ·) consi ing of a set R and two operations
+ : R × R −→ R (“addition”)
· : R × R −→ R (“multiplication”)
such that the following properties hold:
() The pair (R, +) is an abelian group in the sense of Definitions . and .. Its
neutral element will be denoted by , or R if we want to emphasise the ring.
() Multiplication is associative, that is,
x · (y · z) = (x · y) · z
for all elements x, y, z ∈ R.
() There exi s a neutral element ∈ R such that · x = x · = x for all x ∈ R. When we
want to emphasise the ring R, we will write R for the neutral element.
() Multiplication is di ributive with respe to addition, that is:
x · (y + z) = x · y + x · z
(x + y) · z = x · z + y · z
for all elements x, y, z ∈ R.
Definition .. — A ring R is called commutative if · is commutative, that is:
x·y = y ·x
for all x, y ∈ R.
Algebra MAA – Bachelor – Year Chapter – Rings
Remark .. — For all x, y, z ∈ R, the following identities hold:
x · (y − z) = x · y − x · z,
(x − y) · z = x · z − y · z.
Adding x · z to both sides, the fir identity amounts to x · (y − z) + x · z = z · y. To prove
it, one uses the axioms as follows:
x · (y − z) + x · z = x · [(y − z) + z] di ributivity of multiplication
= x · [y + ((−z) + z)] associativity of addition
= x · [y + ] −z is the inverse of z for the group law
= x·y is the neutral element
The proof is the same for the second identity. From this, we immediately see that
() ·x = x· =
for all x ∈ R (take y = z in the fir identity above and x = y in the second) and that
(−) · x = x · (−) = −x
for all x ∈ R (take y = and z = in the fir identity above and x = and y = in the
second).
.. Examples
Example .. — The set R = {} consi ing of a single element is a ring in which = .
The operations are + = and · = . It is called the trivial ring. A ring is non-trivial
if and only if , in R (indeed, if = , then x = x · = x · = for all x ∈ R).
Example .. — The ring of integers Z is the set Z together with the usual addition
and multiplication, which satisfy the axioms in the definition. It is a commutative ring.
The same is true for the sets Q, R, and C of rational, real, and complex numbers.
Example . (The ring of matrices Mn (R)). — Let R be a ring and let n ≥ be an
integer. We denote by
Mn (R) = {A = (aij )≤i,j≤n | aij ∈ R}
Algebra MAA – Bachelor – Year Chapter – Rings
the set of n by n matrices with coefficients in R. The index i indicates the row and the
index j indicates the column. Given two matrices A = (aij ) and B = (bij ), we define
their addition as the matrix
A + B = (aij + bij ),
where aij + bij ands for the addition in the ring R, and their multiplication as the
matrix A · B = (cij ), where
n
X
cij = aik · bkj ,
k=
where aik ·bkj is the multiplication in the ring R. With these operations, Mn (R) is a ring.
– For n = , we have M (R) = R.
– If n ≥ and R is non-trivial, the ring Mn (R) is always non-commutative. For this,
we fir observe that in M (R) we have
( ) · ( ) = ( ) , ( ) · ( ) = ( ) .
Since , , these two matrices are different and M (R) is non-commutative.
By adding rows and columns of zeros to these two matrices, one obtains non-
commuting matrices in any Mn (R) with n ≥ . For example, the matrices
and
in M (R) do not commute.
Example . (The ring of polynomials). — Let R be a ring. A polynomial in one vari-
able with coefficients in R is a sequence
P = (an )n≥ , an ∈ R
such that there exi s an integer d ≥ such that an = for all n > d. If not all an are
equal to zero, the minimal integer d satisfying this property is called the degree of P . If
an = for all n, we will adopt the convention that the degree of P is −∞. We let R[X]
denote the set of all polynomials in one variable with coefficients in R.
We endow R[X] with a ring ru ure as follows:
– the addition of two polynomials P = (an )n≥ and Q = (bn )n≥ is defined as
P + Q = (an + bn )n≥ ,
where an + bn ands for the addition in the ring R;
Algebra MAA – Bachelor – Year Chapter – Rings
– the multiplication of two polynomials P = (an )n≥ and Q = (bn )n≥ is defined as
P · Q = (a · b , a · b + a · b , a · b + a · b + a · b , . . . )
In general, the n-th term of the sequence P · Q is
n
X
ai · bn−i ,
i=
where the produ s ai · bj are performed using multiplication in the ring R;
– the neutral element for addition is the zero polynomial = (, , . . . );
– the neutral element for multiplication is polynomial = (, , , . . . ).
It is raightforward to check that R[X] together with these operations forms a ring.
This ring is commutative if and only if R is commutative.
We now explain how to recover the more familiar notation for polynomials. For all
elements a ∈ R, we write
a = (a, , , . . . ) ∈ R[X].
This is the element a seen as a con ant polynomial. Next, we set
X = (, , , . . . ) ∈ R[X].
With these notation, for each integer n ≥ , we have
aX n = (, . . . , , a, , . . . )
with the coefficient a sitting in the n-th position. If P = (an ) is a polynomial such that
an = for all n > d, we can rewrite it as
P = a + a X + a X + · · · + ad X d .
Remark .. — If we drop the condition that an = for n sufficiently big and allow
for infinitely many non-zero terms, we ill obtain a ring. It is called the ring of formal
power series with coefficients in R and denote it by R[[X]].
Example . (Produ of rings). — If R , . . . , Rn is a finite colle ion of rings, then the
cartesian produ
R = R × · · · × Rn = {(a , . . . , an ) | ai ∈ Ri }
has a ring ru ure in which addition and multiplication are defined componentwise,
that is:
Algebra MAA – Bachelor – Year Chapter – Rings
– addition:
(a , a , . . . , an ) + (b , b , . . . , bn ) = (a + b , a + b , . . . , an + bn )
– multiplication:
(a , a , . . . , an ) · (b , b , . . . , bn ) = (a · b , a · b , . . . , an · bn )
where the operations ai + bi and ai · bi are performed in the ring Ri .
We call R the dire produ of the rings R.
.. Subrings
Definition .. — Let R be a ring and let S ⊂ R be a subset. We say that S is a subring
of R if the following three conditions hold:
. (S, +) is an additive subgroup of (R, +). Recall from Definition . that this means
that S contains the neutral element for addition ∈ R, that if x, y ∈ S, then x+y ∈ S,
and thaf if x ∈ S, then −x ∈ S.
. S is able under multiplication, that is, if x, y ∈ S, then x · y ∈ S.
. The neutral element for multiplication R belongs to S.
Said differently, the operations + : R × R → R and · : R × R → R re ri to operations
on S and the triple (S, +, ·) is a ring.
Example .. — In the chain of inclusions
Z ⊂ Q ⊂ R ⊂ C,
all subsets are subrings.
Example .. — We now give some examples and non-examples of subrings of the
ring of matrices Mn (R) with coefficients in a ring R (see Example .):
– diagonal matrices
– upper triangular matrices
– upper triangular matrices with on the diagonal do not form a subring of Mn (R)
(it is not an additive subgroup, as it does not contain the zero matrix).
Algebra MAA – Bachelor – Year Chapter – Rings
.. Ideals
Throughout this se ion, we assume that R is a commutative ring.
Definition .. — A subset I of R is called an ideal if the following conditions hold:
. I is a subgroup of (R, +).
. For all x ∈ R and all y ∈ I, the element x · y belongs to I.
There are always at lea two ideals in a non-trivial ring: I = {} and I = R. Indeed,
since x · = for all x ∈ R by (), the subset I = {} satisfies the second property above.
Remark .. — To prove that a non-empty subset I ⊂ R is an ideal, it suffices to show
that condition above holds and that, if x, y ∈ I, then x + y ∈ I. Indeed, since (−) · x =
−x is the additive inverse of x, condition implies that, if x ∈ I, then −x ∈ I. Then,
= x + (−x) belongs to I, thus showing that I is an additive subgroup.
Remark .. — The notion of ideal exi s for non-commutative rings as well, but
then it makes a difference to ask x · y ∈ I (“left ideal”), y · x ∈ I (“right ideal”), or both
conditions (“two-side ideal”). For example, if R is a ring the subset of the ring of ×
matrices M (R) which are of the form ( ba ) for some a, b ∈ R is a left ideal but not a
right ideal, as the following computation shows:
ax ay
( ba ) · xz yt = bx by , a ax+by
x y
z t · ( b ) = az+bt
.
To avoid this issue, in this course we will only discuss ideals of commutative rings.
Remark .. — It is in ru ive to compare the definitions of subring and ideal. In
the latter, we do not require that belongs to I. There is a good reason for that!
Lemma .. — Let I be an ideal of R. Then I = R if and only if ∈ I.
Proof. — If I = R, we obviously have ∈ I. Conversely, assume ∈ I and let x ∈ R be
any element of the ring. Since x = x · and ∈ I, we get x ∈ I by the definition of ideal.
Therefore, I = R.
Proposition .. — All ideals of Z are of the form nZ for some integer n ≥ .
Proof. — We know by Proposition . that all additive subgroups of Z are of this form,
so it suffices to show that nZ satisfies the second condition in the definition of ideal.
This is raightforward since the produ of any integer x with an integer of the form
ny is n(xy), ill a multiple of n.
Algebra MAA – Bachelor – Year Chapter – Rings
Example . (Principal ideals). — Let R be a commutative ring and let x ∈ R be an
element. The subset
xR = {xy | y ∈ R},
which is also denoted by (x), is an ideal of R. Indeed, it is an additive subgroup since
– it contains = x · ,
– x · y + x · y = x · (y + y ) by di ributivity,
– the inverse of x · y is −x · y = x · (−y)
and it satisfies the second condition in the definition as well: given z ∈ R and x · y ∈ xR,
the produ z · (x · y) = x · (z · y) belongs to xR. Ideals of this form are called principal
ideals. A concise way to summarise Proposition . is by saying that all ideals of Z are
principal.
Definition .. — Let R be a ring and let I be an ideal of R. We say that
. I is a maximal ideal if I , R and if there exi s no ideal J such that I ( J ( R.
. I is a prime ideal if I , R and the following condition holds: if the produ xy of
two elements of R belongs to I, then either x ∈ I or y ∈ I.
Example .. — In a ring R, the zero ideal {} is prime if and only if x · y = implies
that either x = or y = . This means that R does not contain any zero divisors.
Example .. — Let us examine the ideals of Z. By Proposition ., we know that
they are all of the form nZ for some integer n ≥ . If n = , we get the ideal {}
which is prime by the previous example but not maximal, as it satisfies for example
{} ( Z ( Z. Let n ≥ be an integer. If n is not a prime number, then the ideal nZ
is neither prime nor maximal. Indeed, if n = n n is a non-trivial fa orisation of n,
the inclusions nZ ( n Z ( Z show that nZ is not maximal and we have two elements
n , n that do not belong to the ideal nZ but whose produ does.
Let now p be a prime number. The ideal pZ is prime by Euclid’s lemma (Theorem
.). Let us show it is maximal as well. Suppose, by contradi ion, that there exi s an
ideal I such that pZ ( I. Then I contains an integer r that is coprime to p. By Bézout’s
identity (Theorem .), there exi integers u, v ∈ Z such that ru + pv = . Since I is an
ideal that contains r and all multiples of p, on a ru ∈ I and pv ∈ I, hence ru + pv by
additivity. It follows that ∈ I, hence I = Z by Lemma .. We have thus proved that
pZ is maximal. The table in the next page summarises the situation.
Algebra MAA – Bachelor – Year Chapter – Rings
n maximal prime
no yes
no no
prime yes yes
non-prime no no
Table . Maximal and prime ideals of Z
In the course of this exemple, we observe that all maximal ideals of Z are prime as
well. This is indeed a general property:
Proposition .. — Let R be a commutative ring and let I be an ideal of R. If I is maximal,
then I is prime.
Proof. — Assume by contradi ion that I is not a prime ideal. By definition, this means
that there exi s two elements a, b ∈ R \ I such that a · b ∈ I. Consider the subset
B = {x + a · r | x ∈ I, r ∈ R}.
It satisfies I ( B since any element x ∈ I can be written as x = x + a · ∈ B, but the
element a = + a · lies in B \ I. Therefore, if we prove that B is an ideal, then B = R by
the assumption that I is maximal.
Let us check that B is an ideal. Fir ly, the element = +a· belongs to B. Secondly,
(x + a · r ) + (x + a · r ) = (x + x ) + a · (r + r )
shows that B is able under addition since, I being an ideal, if x , x ∈ I, then x +x ∈ I.
Moreover, −(x + a · r) = (−x) + a · (−r) belongs to B for all x ∈ I. This shows that B is an
additive subgroup of R. Finally, if x + a · r ∈ B and y ∈ R, we have
y · (x + a · r) = (y · x) + a · (y · r) ∈ B
since, I being an ideal, y · x ∈ I. Therefore, B is an ideal.
Now that we know that B is the whole ring R, we have in particular ∈ R. Therefore,
we can find elements x ∈ I and r ∈ R such that = x + a · r. Multiplying both sides by b,
we find b = b · x + (a · b)r. Since this is in contradi ion with the initial assumption that
b does not belong to I, we have ju proved that I is prime.
Algebra MAA – Bachelor – Year Chapter – Rings
.. Invertible elements and fields
We are back to the setting where R is any ring, not necessarily commutative.
Definition .. — Let R be a ring. An element x of R is said to be invertible if there
exi s an element y ∈ R such that x · y = y · x = . We denote by R× the set of invertible
elements of R.
For example, the element ∈ R is never invertible, as we proved that x · = · x =
for all elements x ∈ R.
Remark .. — If x is invertible, there exi s a unique y ∈ R such that x · y = y · x =
and we denote it by x− . Indeed, if y and y are two such elements, then
y = y · is the neutral element
= y · (x · y ) y satisfies x · y =
= (y · x) · y associativity of the group law
= · y y satisfies y · x =
= y is the neutral element.
Lemma .. — If R is non-trivial, then (R× , ×) is a group
Proof. — Since multiplication is associative, the neutral element belongs to R× and
invertible elements have an inverse by definition, the only remaining property to check
is that the produ of two invertible elements is again invertible. This follows from
(x · y) · (y − · x− ) = x · (y · y − ) · x− = x · x− =
(y − · x− ) · (x · y) = y − · (x− · x) · y = y − · y = ,
which shows that x · y is again invertible and that its inverse is y − · x− .
Lemma .. — Let R be a commutative ring and let I be an ideal. If I contains an invertible
element, then I = R.
Proof. — If x ∈ I is invertible, then = x · x− belongs to I by the second condition in
the definition of ideal, hence I = R by Lemma ..
Example .. — The invertible elements of the ring of integers are Z× = {, −}. In-
deed, if x, y ∈ Z are integers such that xy = , then |x||y| = , hence |x| = . The only
possibilities are x = and x = −. This group is isomorphic to Z/Z.
Algebra MAA – Bachelor – Year Chapter – Rings
Example . (Gaussian integers). — Let Z[i] = {a + bi | a, b ∈ Z} be the ring of Gaus-
sian integers. It is a subring of the complex numbers. Let z ∈ Z[i] be an invertible
element. Then the square of the absolute value |z| = a + b is a positive invertible
integer. By the previous example, is the only such integer, so a + b = . The only
integral solutions to this equation are (, ), (−, ), (, ), (, −). Therefore,
Z[i]× = {, −, i, −i}.
√
Example . (Eisen ein integers). — Set ρ = eπi/ = (− + i)/ and consider the
subset of the complex numbers
Z[ρ] = {a + bρ | a, b ∈ Z}.
Definition .. — A field is a non-trivial commutative ring R in which all non-zero
elements are invertible, that is, R× = R \ {}.
Example .. — Q, R, and C are all fields.
Example .. — The ring Z[i] is not a field, as it contains many non-zero elements
which are not invertible. However, if one considers
Q[i] = {a + bi | a, b ∈ Q}
in ead, one gets a field, since the inverse of a non-zero element x = a + bi ∈ Q[i] is
a b
= − i,
a + bi a + b a + b
which ill lies in Q[i] since a/(a + b ) and −b/(a + b ) are rational numbers.
.. Ring morphisms
Definition .. — Let R and S be two rings. A ring morphism is a fun ion f : R → S
such that
. f : (R, +) → (S, +) is a group morphism in the sense of Definition ., that is,
f (x + y) = f (x) + f (y)
for all elements x, y ∈ R.
. f (x · y) = f (x) · f (y) for all x, y ∈ R
. f (R ) = S
Algebra MAA – Bachelor – Year Chapter – Rings
Remark .. — Contrary to the case of groups, it does not follow from conditions
and above that f (R ) = S , so one needs to impose it in the definition.
Lemma .. — Let f : R → S be a ring morphism. The kernel
ker(f ) = {x ∈ R | f (x) = S }
is an ideal of R. The map f is inje ive if and only ker(f ) is the zero ideal {}.
Proof. — Take x ∈ R and y ∈ ker(f ). By condition in the definition of ring morphism,
f (x·y) = f (x)·f (y) = f (x)·S = S since y lies in the kernel of f . Therefore, x·y ∈ ker(f ).
Moreover, R ∈ ker(f ) since f (R ) = S because f is a morphism of additive groups. To
conclude that ker(f ) is an ideal of R, it remains to show that, if x, y ∈ ker(f ), then
x + y ∈ ker(f ). But f (x + y) = f (x) + f (y) = . Now, let x, y ∈ R. If f (x) = f (y), then
f (x − y) = , so f is inje ive if and only if ker(f ) = .
Proposition .. — Let f : R → S be a ring morphism.
. The image of a subring of R is a subring of S. In particular, f (R) is a subring of S.
. The inverse image of a subring of S is a subring of R.
. The inverse image of an ideal of S is an ideal of R.
Remark .. — The image of an ideal of R is not necessarily an ideal of S. For exam-
ple, if f : Z → Q is the inclusion, the image of an ideal nZ is the subset nZ of Q which
is not an ideal.
CHAPTER
POLYNOMIALS
Let K be a field. Recall from Example . that the ring K[X] of polynomials in one
variable with coefficients in K consi s of
K[X] = {a + a X + · · · + ad X d | d ≥ , ai ∈ K}.
Consider the set N ∪ {−∞} of natural numbers with −∞ added. We extend addition
and the order relation from N to N ∪ {−∞} by setting:
• −∞ ≤ n for all n ∈ N,
• (−∞) + n = n + (−∞) = −∞ for all n ∈ N,
• (−∞) + (−∞) = −∞.
We define a degree map
deg : K[X] −→ N ∪ {−∞}
P 7−→ deg(P )
as follows: if P = (that is, if all ai = ), then deg(P ) = −∞ and, if P , , then deg(P ) is
the large integer n ≥ such that an is non-zero.
Lemma .. — Let P , Q ∈ K[X] be polynomials.
. deg(P + Q) ≤ max(deg(P ), deg(Q)), with equality if deg(P ) , deg(Q).
. deg(P · Q) = deg(P ) + deg(Q).
Proof. — We fir check the case where one of the polynomials, say Q, is zero. Then
deg(Q) = −∞, so the fir atement reads deg(P ) ≤ max(deg(P ), −∞) = deg(P ) and the
Algebra MAA – Bachelor – Year Chapter – Polynomials
second deg() = deg(P ) + (−∞) = −∞; they are both obviously true. If both P and Q are
non-zero, we set deg(P ) = r ≥ and deg(Q) = s ≥ . We then have
P = ar X r + · · · , ar ,
Q = bs X s + · · · , bs , .
Computing the sum and the produ
P + Q = ar X r + bs X s + terms of degree < max(r, s),
P Q = ar bs X r+s + terms of degree < r + s
we see that deg(P + Q) ≤ max(r, s) with equality if r , s (otherwise, ar and bs could
cancel each other, giving rise a smaller degree polynomial) and that deg(P · Q) = r + s
since ar bs , because a field does not contain zero divisors.
Corollary .. — The ring K[X] is an integral domain. The invertible elements are the
non-zero con ant polynomials: K[X]× = K × .
.. Euclidean division
Theorem . (Euclidean division of polynomials). — Let A, B ∈ K[X] be polynomials
such that B , . There exi s a unique pair of polynomials Q, R ∈ K[X] such that
A = BQ + R, deg(R) < deg(B).
The polynomial Q is called the quotient and the polynomial R is called the remainder of
Euclidean division.
Definition .. — We say that B divides A if, in the above theorem, the remainder is
equal to zero, that is, if there exi s a polynomial Q ∈ K[X] such that A = BQ.
In the course of the proof, we will need the following lemma:
Lemma .. — Let U , V ∈ K[X] be polynomials such that V , and deg(V ) ≤ deg(U ).
There exi s a polynomial Q ∈ K[X] such that
deg(U − V Q) < deg(U ).
Algebra MAA – Bachelor – Year Chapter – Polynomials
Proof. — Since V , and deg(V ) ≤ deg(U ), the polynomial U is non-zero as well. We
can therefore write
U = ar X r + · · · with ar , and deg(U ) = r
s
V = bs X + · · · with bs , and deg(V ) = s.
By assumption, s ≤ r. We can then consider the polynomial Q = ar bs− X r−s ∈ K[X],
which makes sense since r − s ≥ and bs is invertible because any non-zero element in
a field is invertible. Computing
U − V Q = (ar X r + · · · ) − ar bs− X r−s (bs X s + · · · )
= ar X r − ar X r + lower degree terms,
| {z }
we see that deg(U − V Q) < r, as we wanted to prove.
Proof of Theorem .. — We fir prove exi ence. Consider the set
S = {A − BQ | Q ∈ K[X]}
and let Q ∈ K[X] be a polynomial such that deg(A − BQ) ∈ N ∪ {−∞} is the smalle
possible among elements of S. Set R = A − BQ and r = deg(R). Since A = BQ + R, it
remains to show that r < deg(B). By contradi ion, assume r ≥ deg(B). Then Lemma
. applied to U = A − BQ and V = B shows that there exi s a polynomial Q0 ∈ K[X]
such that
A − BQ − BQ0 = A − B(Q + Q0 )
has degree < r. This is not possible since Q was a polynomial minimising the degree of
elements of S. Therefore, r < deg(B) and we have proved exi ence.
We now turn to unicity. Assume that there exi two polynomials Q , Q ∈ K[X] such
that
deg(A − BQ ) < deg(B), deg(A − BQ ) < deg(B).
Then
A − BQ − (A − BQ ) = B(Q − Q )
has degree < deg(B), as a difference of two polynomials of degree < deg(B). On the
other hand, by Lemma ., deg(B(Q − Q )) = deg(B) + deg(Q − Q ) and the only way
that this quantity is < deg(B) is that we have deg(Q − Q ) = −∞, that is Q = Q . Since
R = A − BQ, this yields unicity of R as well.
Algebra MAA – Bachelor – Year Chapter – Polynomials
Example .. — In the Euclidean division of A = X +X + by B = X +, the quotient
is Q = X + X − and the remainder is R = −X + .
.. Ideals of the ring of polynomials
As for the ring of integers, an important consequence of Euclidean division is that
all ideals of the ring of polynomials K[X] are principal.
Theorem .. — Let K be a field and let I be a non-zero ideal of K[X]. There exi s a unique
monic polynomial P ∈ K[X] such that I = P · K[X].
Proof. — Let P be a non-zero element of smalle degree belonging to I. Since I is an
ideal, the produ of P and any element of K ill belongs to I, so after multiplying by
the inverse of its leading term we can assume that P is monic. Let us check that
I = P · K[X].
The inclusion ⊇ is a raightforward consequence of I being an ideal. For the other
inclusion ⊆, take A ∈ I. By Euclidean division (Theorem .), there exi polynomials
Q, R ∈ K[X] such that A = P Q + R and deg(R) < deg(P ). Since
R= A − P · Q ∈I
|{z} |{z} |{z}
∈I ∈I ∈K[X]
belongs to I and has degree ri ly smaller than P , we necessarily have R = , which
shows that all elements of I are multiples of P . This shows exi ence.
For the unicity, assume I = P · K[X] = P · K[X] for two monic polynomials P , P .
Since P ∈ P · K[X], there exi s a polynomial B ∈ K[X] such that P = BP . Similarly,
since P ∈ P · K[X], there exi s a polynomial C ∈ K[X] such that P = CP . Therefore,
P = BP = BCP or, equivalently, P · ( − BC) = . Since K[X] is an integral domain
by Corollary . and P , , this yields BC = . By the same corollary, the invertible
elements of K[X] are the non-zero con ant polynomials, so that B, C ∈ K × . Finally,
since the two polynomials P , P were assumed to be monic, these con ants are equal
to and P = P . This finishes the proof of unicity.
Algebra MAA – Bachelor – Year Chapter – Polynomials
.. Irreducible polynomials and roots
Definition .. — A polynomial P ∈ K[X] is said to be irreducible if deg(P ) ≥ and if
there is no polynomial Q ∈ K[X] with ≤ deg(Q) ≤ deg(P ) − such that Q divides P .
Said differently, if P = QQ0 , then either Q or Q0 have degree zero.
Let P ∈ K[X] be a polynomial, say P = ad X d + · · · + a X + a . With P is associated a
fun ion
P : K −→ K
α 7−→ P (α) = ad α d + · · · + a α + a
Definition .. — We say that α ∈ K is a root of P if P (α) = .
Lemma .. — Let P ∈ K[X] be a polynomial. An element α ∈ K is a root of P if and only
if X − α divides P .
Corollary .. — Let P ∈ K[X] be a polynomial of degree ≥ . If P has a root α ∈ K, then
P is not irreducible over K.
Theorem . (Fundamental theorem of algebra). — Every polynomial with complex
coefficients of degree ≥ has a root.
CHAPTER
ENDOMORPHISMS
Let K be a field. We fir recall the notions of K-ve or space and endomorphism of
a K-ve or space from MAA.
Definition .. — A K-ve or space is a set E endowed with an addition
+ : E × E −→ E
(x, y) 7−→ x + y
and with an external multiplication
· : K × E −→ E
(λ, x) 7−→ λ · x
such that the following conditions hold:
. (E, +) is an abelian group,
. λ · (x + y) = λ · x + λ · y,
. (λ + µ) · x = λ · x + µ · x,
. λ · (µ · x) = (λµ) · x,
. · x = x.
A ve or space E has dimension zero if and only if it is the trivial ve or space E = {}.
Let n ≥ be an integer. A K-ve or space E has dimension n if there exi s a basis
e , . . . , en of cardinal n (this means that every element x of E can be uniquely written as
x = λ e + · · · + λn en for some λi ∈ K). If there exi s an integer n ≥ such that E has
dimension n, we say that E is finite-dimensional.
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
Definition .. — Let E be a K-ve or space. A map f : E → E is called linear if
f (λx + µy) = λf (x) + µf (y)
for all x, y ∈ E and all λ, µ ∈ K. An endomorphism of E is a linear map f : E → E. We
denote by L (E) the set of endomorphisms of E.
The set L (E) has extra ru ure. On the one hand, it is a K-ve or space, as was
explained in MAA . If E has dimension n, then L (E) has dimension n . On the
other hand, L (E) is a ring in which
. addition is given by (f , g) 7→ f + g, where f + g is the endomorphism E → E that
sends x to f (x) + g(x);
. multiplication is given by (f , g) 7→ f ◦ g, where f ◦ g is the endomorphism E → E
that sends x to f (g(x)).
Recall that an endomorphism f ∈ L (E) can be represented by a matrix: if e , . . . , en
is a basis of E, there exi unique elements λij ∈ K such that
f (e ) = λ e + λ e + · · · + λn en
..
.
f (en ) = λn e + λn e + · · · + λnn en .
Then we associate to f the n by n matrix
λ λ · · · λn
λ λ · · · λn
A = . .. .. .
.. . .
λn λn . . . λnn
Addition and multiplication in the ring L (E) correspond to usual addition and multi-
plication of matrices.
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
.. Minimal polynomial of an endomorphism
Let K be a field and let E be a finite-dimensional K-ve or space. For each endomor-
phism f ∈ L (E), we define an “evaluation map”
evf : K[X] −→ L (E)
d
X d
X
i
() P= ai X 7−→ P (f ) = ai f i .
i= i=
i
Here, f = Id is the identity endomorphism and f = f ◦ · · · · ◦f for each i ≥ ,
| {z }
i times
It is raightforward to check the following:
Lemma .. — The map evf is a ring morphism.
Since evf is a ring morphism, by Lemma ., its kernel ker(evf ) is an ideal of
the ring of polynomials K[X]. It is a non-zero ideal because evf is a map from the
infinite-dimensional K-ve or space K[X] to the finite-dimensional K-ve or space
L (E), which has dimension (dim E) , and therefore cannot be inje ive. By the char-
a erisation of non-zero ideals in the ring K[X] (Theorem .), there exi s a unique
monic polynomial Pf such that
ker(evf ) = Pf · K[X].
Definition .. — We call Pf the minimal polynomial of f .
Therefore, the minimal polynomial of an endomorphism f is the monic polynomial
of smalle degree P ∈ K[X] such that P (f ) = . There is also a variant for matrices: if
A is an n by n matrix with coefficients in K, then we consider the evaluation map
evA : K[X] −→ Mn (K)
d
X d
X
i
P= ai X 7−→ P (A) = ai Ai
i= i=
and we define the minimal polynomial of A as the unique monic polynomial PA ∈ K[X]
such that ker(evA ) = PA · K[X].
Example .. — Consider the matrix A = ( ). Since A = ( ), this matrix satisfies
the equation A − A + I = . Therefore, the polynomial X − X + = (X − ) belongs
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
to the kernel of the evaluation map evA . Since the minimal polynomial divides every
polynomial in this kernel, the only possibilities are X − and (X − ) . But the fir one
does not lie in ker(evA ), as A − I = ( ) , . We conclude that the minimal polynomial
of A is (X − ) .
.. Eigenvalues and eigenve ors
Let E be a finite-dimensional K-ve or space and f ∈ L (E) an endomorphism.
Definition .. — An element λ ∈ K is said to be an eigenvalue of f if there exi s a
non-zero ve or v ∈ E \ {} such that f (v) = λv. When this is the case, one says that v is
an eigenve or associated with the eigenvalue λ.
Since every linear map f satisfies f () = , if we did not ask v to be non-zero in the
above definition, then all elements of K would be eigenvalues.
Definition .. — Let λ ∈ K be an eigenvalue of f . The eigenspace associated with λ is
the subset Eλ ⊂ E defined as
Eλ = {v ∈ E | f (v) = λv}.
Therefore, Eλ contains and all eigenve ors associated with the eigenvalue λ.
Lemma .. — Eλ ⊂ E is a subve or space.
Proof. — We need to check the properties:
– ∈ Eλ
– if v, w ∈ Eλ , then av + bw ∈ Eλ for all a, b ∈ K.
The fir one holds since a linear map satisfies f () = = λ · . To e ablish the second
one, using that f is a linear map and v, w ∈ Eλ we have:
f (av + bw) = af (v) + bf (w) = aλv + bλw = λ(av + bw).
Therefore, av + bw ∈ Eλ .
In particular, Eλ is a finite-dimensional K-ve or space and dimK Eλ ≤ dimK E.
Proposition .. — Let λ , . . . , λr be di in eigenvalues of f . Then the subve or spaces
Eλ , . . . , Eλr ⊂ E form a dire sum.
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
Recall that this means that, if i∈I vi = for some index subset I ⊂ {, . . . , r} and
P
ve ors vi ∈ Eλi , then vi = for all i ∈ I.
Proof. — By contradi ion, assume that there is a relation i∈I vi = between non-zero
P
ve ors. If I has cardinal `, after arranging the order of the eigenvalues if necessary, we
can assume that the relation is of the form
X̀
vi =
i=
for non-zero ve ors vi ∈ Eλi \ {}. Then
X̀
() v = − vi ,
i=
so that f (v ) = − `i= f (vi ) by linearity of f . Since vi are eigenve ors associated with
P
the eigenvalues λi , we have f (vi ) = λvi for i = , . . . , `. Therefore, λ v = − `i= λi vi
P
and, plugging the formula () for v in, we find
X̀
(λi − λ )vi = .
i=
Iterating ` − more times this procedure, we find the equation
(λ` − λ`− ) · · · (λ` − λ )(λ` − λ )v` = .
Since all the eigenvalues λi are di in , the scalar multiplying v` is non-zero. There-
fore, v` = , which contradi s the initial assumption that the relation was between
non-zero eigenve ors.
Corollary .. — Let E be an n-dimensional K-ve or space. An endomorphism f ∈ L (E)
has only finitely many eigenvalues (in fa , at mo n eigenvalues).
Proof. — Let λ , λ , . . . be eigenvalues of f . Then Eλi has dimension ≥ . By the propo-
P
sition, Eλ ⊕ Eλ ⊕ · · · ⊂ E and therefore i dimK Eλi ≤ dim E.
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
.. Diagonalisable endomorphisms
Definition .. — Let E be a finite-dimensional K-ve or space. An endomorphism
f ∈ L (E) is said to be diagonalisable if
M
E= Eλ .
λ eigenvalue
of f
P
(this amounts to asking that dimK Eλ = dimK E.)
The term “diagonalisable” is explained as follows. Let λ , . . . , λr be the eigenvalues
of f . If f is diagonalisable, then there exi s a basis v , . . . , vn of E consi ing of ve ors
that belong to the eigenspaces Eλ , . . . , Eλr . In such a basis, f is represented by the
diagonal matrix
λ
λ
.
.
.
λ
λ ,
. . .
λ
. . .
λr
where the multiplicity of λi is the dimension of Eλi .
Example .. — Set K = R and E = R . Let f be the endomorphism represented by
the matrix A = ( ). That is, in the andard basis e , e of E, we have
f (e ) = e , f (e ) = e + e .
To find the eigenvalues of A, we need to determine the values of λ ∈ R such that
x
! ! !
x
=λ ,
y y
has a solution (x, y) , (, ). This yields the equations
x + y = λx
y = λy
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
Rewriting the second one as (λ − )y = , we see that y = or λ = . If y = , then
x = λx and, since x needs to be non-zero, we find λ = . If λ = , then x + y = x yields
y = . Therefore, the only eigenvalue of A is λ = and the eigenspace Eλ= consi s of
the ve ors of the form ( x ). Since Eλ= is one-dimensional but E is two-dimensional,
the endomorphism f is not diagonalisable.
Example .. — In the same setting as the previous example, let f be the endomor-
phism represented by the matrix A = ( −
). We fir compute its eigenvalues. Since
− x
! ! !
−y
= ,
y x + y
we look for the values of λ ∈ R such that the equations
−y = λx
x + y = λy
admit a solution (x, y) , (, ). Plugging y = − λ x in the second equation yields
λ
( − λ + )x = .
If x = , then y = as well and we would not get a solution with the required property.
Therefore, − λ+ λ = or, equivalently, λ −λ+ = . This equation has two di in
solutions λ = and λ = . We thus find that the eigenspaces
Eλ= = {( yx ) | x = −y}, Eλ= = {( yx ) | x = −y}
are both one-dimensional. It follows that E = Eλ= ⊕ Eλ= , so that f is diagonalisable.
Theorem .. — Let E be a finite-dimensional K-ve or space. An endomorphism
f ∈ L (E) is diagonalisable if and only if its minimal polynomial is a produ of di in
fa ors of degree one in K[X].
Proof. — Assume that f is diagonalisable, with eigenvalues λ , . . . , λr . We will show
that the minimal polynomial of f is then
P = (X − λ ) · · · (X − λr ) ∈ K[X].
We fir prove that P belongs to the kernel of the evaluation map evf from (), in
other words, that the endomorphism ri= (f − λi · Id) is identically zero. Since f is
Q
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
diagonalisable, E = Eλ ⊕ · · · ⊕ Eλr , which means that every ve or v ∈ E can be written
uniquely as v = ri= vi for ve ors vi ∈ Eλi . By linearity, to show that
P
r
Y
(f − λi · Id)(v) =
i=
for all v ∈ E, it suffices to show that ri= (f − λi · Id)(vi ) = for all vi ∈ Eλi . This follows
Q
from the computation
Y r Y
(f − λi · Id)(vi ) = (f − λi · Id)(f − λi · Id)(vi ) = ,
i= j,i
where we have used that the endomorphisms f − λi · Id commute with each other and
that (f − λi · Id)(vi ) = since f (vi ) = λi vi .
By definition of the minimal polynomial of f , all polynomials in the kernel of the
evaluation map, in particular (X − λ ) · · · (X − λr ), are divisible by it. Therefore, the
minimal polynomial of f is a produ of some of the fa ors X −λ , . . . , X −λr . However,
Y
() (f − λi · Id) ,
i∈I
for each ri subset I ( {, . . . , r}. Indeed, if an index j does not belong to I, then
the image of a non-zero ve or vj ∈ Eλj by the endomorphism () does not vanish. We
conclude that the minimal polynomial of f is P .
Conversely, assume that the minimal polynomial of the endomorphism f is
P = (X − λ ) · · · (X − λr ),
Lr
with λi ∈ K all di in . We need to show that E = E . This follows from the la
i= λi
assertion of the theorem below, on noting that the kernel ker(f − λi Id) is precisely the
eigenspace Eλi .
Theorem .. — () Let E be a finite-dimensional K-ve or space, let f ∈ L (E) be an en-
domorphism, and let P ∈ K[X] be a polynomial. Assume that P = P · · · Ph , where Pi ∈ K[X]
are pairwise coprime polynomials, and set Ki = ker Pi (f ). Then:
. The ve or subspaces Ki satisfy f (Ki ) ⊂ Ki ;
Lh
. ker P (f ) = K;
i= i
()
In French, this theorem is usually referred to as “lemme des noyaux”
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
Lh
. If P is the minimal polynomial of f , then E = i=
Ki and the re ri ion f |Ki of f to
Ki has minimal polynomial Pi .
Proof. — To prove the fir assertion, we need to show that, for every ve or v such
that Pi (f )(v) = , we have Pi (f )(f (v)) = as well. But
Pi (f )(f (v)) = f (Pi (f )(v)) = f () =
since f is a linear map.
We prove the second assertion by indu ion on h. Let us fir treat the case h = .
Since P and P are coprime, by Bézout’s identity there exi polynomials U , V ∈ K[X]
such that = U P + V Q. Then Id = U (f ) ◦ P (f ) + V (f ) ◦ P (f ) and therefore every
x ∈ ker P (f ) can we written as
x = (U (f ) ◦ P (f ))(x) + (V (f ) ◦ P (f ))(x) .
| {z } | {z }
x x
The ve or x satisfies P (f )(x ) = (P (f ) ◦ U (f ) ◦ P (f ))(x ) = (U (f ) ◦ P (f ))(x ) = , since
all endomorphisms of the form Q(f ), for Q ∈ K[X], commute with each other and x
belongs to ker P (f ). Therefore, x ∈ K = ker P (f ). Similarly, x ∈ K = ker P (f ). We
have thus showed that ker P (f ) = K + K . It remains to prove that K ∩ K = {}. Let
x ∈ K ∩ K . Using Bézout’s identity again,
x = (U (f ) ◦ P (f ))(x) + (V (f ) ◦ P (f ))(x) = .
This settles the case h = .
Assuming that the result holds for h − , let us show it for h. If P = P P · · · Ph with Pi
pairwise coprime, then the polynomials P and P · · · Ph are coprime, whence
ker P (f ) = ker P (f ) ⊕ ker(P · · · Ph )(f ) = ker P (f ) ⊕ ker P (f ) ⊕ · · · ⊕ ker Ph (f )
by the indu ion hypothesis.
Finally, let us prove the third assertion. If P is the minimal polynomial of f L , then
P (f ) = , so that ker P (f ) = E. By the second part of the theorem, we have E = Ki .
Since f (Ki ) ⊂ Ki , the re ri ion f |Ki is an endomorphism of Ki ; its minimal polyno-
mial divides Pi since Pi (f |Ki ) = Pi (f )|Ki = . By contradi ion, assume that the minimal
Q
polynomial is a proper divisor Q of Pi . Then R = Q j,i Pj would be a proper divi-
sor of P such that R(f ) = , contradi ion with the assumption that P is the minimal
polynomial. This concludes the proof.
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
Example .. — As we saw in Example ., the minimal polynomial of the endomor-
phism represented by the matrix ( ) is (X − ) . Since this is not a produ of di in
fa ors of degree one, the endomorphism is not diagonalisable. This is in accordance
with Example ..
Example .. — The endomorphism represented by the matrix ( ) has minimal
polynomial (X − )(X − ). Since this is a produ of di in fa ors of degree one,
the endomorphism is diagonalisable, in accordance with Example ..
.. Chara eri ic polynomial
So far, we do not know any efficient way to compute the eigenvalues of an endomor-
phism. For this, we introduce the notion of chara eri ic polynomial. The chara eri ic
polynomial of an n by n matrix A ∈ Mn (K) with coefficients in a field K is defined as
χA = det(A − X · In ) ∈ K[X],
where In ands for the n by n identity matrix. It is a polynomial of degree n with
leading coefficient (−)n .
Definition .. — Let E be an n-dimensional K-ve or space and let f ∈ L (E) be an
endomorphism. The chara eri ic polynomial of f is the chara eri ic polynomial of a
matrix A representing f in a basis of E. We write:
χf = det(f − X · Id) = det(A − X · In ).
For this definition to make sense, one needs to show that the chara eri ic polyno-
mial does not depend on the choice of a basis of E. Indeed, if we pick a different basis,
the endomorphism f will be represented by the matrix P − AP , where P ∈ GLn (K) is
the matrix of change of basis, and we have:
det(P − AP − X · In ) = det(P − (A − X · In )P )
= det(P − ) det(A − X · In ) det(P )
= det(A − X · In ).
The degree of the chara eri ic polynomial of an endomorphism f ∈ L (E) is the di-
mension of the ve or space E.
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
Proposition .. — Let f ∈ L (E). An element λ ∈ K is an eigenvalue of f if and only if λ
is a root of the chara eri ic polynomial of f .
Proof. — Recall from Definition . that λ ∈ K is an eigenvalue of f if there exi s a
non-zero ve or v ∈ E \ {} such that f (v) = λv. Since such a v belongs to the kernel of
the endomorphism f − λ · Id, this is equivalent to asking that f − λ · Id is not invertible.
Therefore, λ ∈ K is an eigenvalue of f if and only if det(f − λId) = , that is, if and only
if λ is a root of the chara eri ic polynomial det(f − X · Id).
Corollary .. — If K = C and E is a K-ve or space of dimension ≥ , then f has at lea
one eigenvalue.
Proof. — By the fundamental theorem of algebra (Theorem .), every polynomial of
degree ≥ with complex coefficients has at lea one root.
This result does not hold if one replaces the field of complex numbers with K = R.
For example, the endomorphism represented by the matrix ( − ) has chara eri ic
polynomial X + ∈ R[X]. Since this polynomial does not have real roots, the endomor-
phism does not have eigenvalues. In the following example, we analyse all possibilities
for endomorphisms of two-dimensional ve or spaces over the real numbers.
Example .. — Let K = Rand E = R . An endomorphism f ∈ L (E) represented by a
two by two matrix A = ac db ∈ M (R). The chara eri ic polynomial of f is equal to
!
a−X b
χf = det = (a − X)(d − X) − bc
c d −X
= X − (a + d)X + ad − bc.
The eigenvalues of f are the real roots of this polynomial, whose discriminant is given
by ∆ = (a + d) − (ad − bc). Therefore, we have the three following possibilities:
. if ∆ < , then f has no eigenvalues;
. if ∆ = , then f has one eigenvalue;
. if ∆ > , then f has two di in eigenvalues.
Theorem . (Cayley–Hamilton). — Let E be a finite-dimensional K-ve or space and
let f ∈ L (E) be an endomorphism. The minimal polynomial of f divides the chara eri ic
polynomial of f .
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
Proof. — Set χf = det(f −X·Id) = (−)n X n +· · ·+c X+c . By Cramer’s rule for computing
the inverse of the matrix A − X · In , we have the identity
() (A − X · In ) · B(X) = χf · In ,
where B(X) denotes the transpose of the cofa or matrix whose (i, j) entry is given by
(−)i+j times the determinant of the (n − ) by (n − ) matrix obtained by removing the
i-th column and the j-th row of A − X · In . We write
B(X) = Bn− X n− + · · · + B X + B
with matrices Bi ∈ Mn (K). Then () translates into
AB + (AB − B )X + · · · + (ABn− − Bn− )X n− − Bn− X n = c + c X + · · · + (−)n X n .
Identifying coefficients degree by degree, we get the equations
AB = c In
AB − B = c In
AB − B = c In
..
.
ABn− − Bn− = cn− In
−Bn− = (−)n In
Multiplying the second equation by A on the left and using that AB = c In , we find
= A B − AB − c A = A B − c A − c .
By the third equation, B = AB − c In , whence
= A (AB − c In ) − c A − c = A B − c A − c A − c A.
Iterating this process, we arrive at
(−)n+ An − cn− An− − · · · − c A − c In =
or, equivalently,
(−)n An + cn− An− + · · · + c A + c In = .
This means that the chara eri ic polynomial of A belongs to the kernel of the evalu-
ation map evA and it is thus a multiple of the minimal polynomial of A.
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
Corollary .. — Let E be an n-dimensional K-ve or space. If the chara eri ic poly-
nomial of f has n di in roots in K, then it agrees with the minimal polynomial and f is
diagonalisable.
Proof. — Since the chara eri ic polynomial has degree n, if it has n di in roots in
K, then it is of the form (X − λ ) · · · (X − λn ) ∈ K[X]. By Proposition ., the roots λi
are the eigenvalues of f . By the Cayley–Hamilton theorem, the minimal polynomial
of f divides its chara eri ic polynomial. But arguing as in the proof of Theorem .,
none of the proper divisors of (X −λ ) · · · (X −λn ) belongs to the kernel of the evaluation
map. Therefore, the minimal polynomial is equal to (X − λ ) · · · (X − λn ). Since this is a
produ of di in fa ors of degree one, f is diagonalisable by Theorem ..
Let us know ate a criterium for diagonalisation in terms of the chara eri ic poly-
nomial:
Theorem .. — Let f ∈ L (E) be an endomorphism and let λ , . . . , λr be the di in
eigenvalues of f . Then f is diagonalisable if and only the chara eri ic polynomial of f is
equal to χf = ri= (λi − X)ni with ni = dim Eλi .
Q
Proof. — If f is diagonalisable, then E = Eλ ⊕ · · · ⊕ Eλr . With respe to a basis of E
adapted to this dire sum decomposition, the chara eri ic polynomial of f equals
λ − X
..
.
λ − X
det = (λ − X)n · · · (λr − X)nr ,
λ − X
.
. .
λr − X
where ni = dim Eλi . This proves the dire implication.
Conversely, assume that χf = ri= (λi − X)ni with ni = dim Eλi . Since the degree of
Q
χf agrees with the dimension of E, we have
dim E = n + · · · + nr = dim Eλ + · · · + dim Eλr = dim(Eλ ⊕ · · · ⊕ Eλr )
on noting that the eigenspaces Eλi form a dire sum since all the λi are di in (Propo-
sition .). Since Eλ ⊕ · · · ⊕ Eλr ⊂ E is a subve or space of the same dimension as E, we
necessarily have E = Eλ ⊕ · · · ⊕ Eλr and f is diagonalisable.
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
Example .. — Set E = K and let f ∈ L (E) be the endomorphism given by the matrix
in the andard basis of E. The chara eri ic polynomial of f being equal to
−X
det −X = X ( − X),
−X
to decide whether f is diagonalisable or not we need to see whether the eigenspace
Eλ= associated with the eigenvalue is two-dimensional or not. Since
x y
y = ,
z
z
this eigenspace consi s of those ve ors with y = z = and it is therefore one-
dimensional. By the above theorem, f is not diagonalisable.
If we are given a diagonalisable endomorphism f ∈ L (E), then we can find a basis of
E with respe to which the matrix representing f is diagonal. If we are given a second
diagonalisable endomorphism g ∈ L (E), then we can also find a basis of E in which g
is given by a diagonal. But is it possible to find a basis that diagonalises both f and
g? In that case, we say that f and g are simultaneously diagonalisable. The following
proposition gives a complete answer:
Proposition .. — Two diagonalisable endomorphisms f , g ∈ L (E) are simultaneously
diagonalisable if and only if f ◦ g = g ◦ f .
Proof. — If f , g are simultaneously diagonalisable, then f ◦ g = g ◦ f , as all diagonal
matrices commute with each other. Conversely, assume that f and g commute. We
shall prove by indu ion on the dimension n = dim E that there exi s a basis with
respe to which f and g are simultaneously diagonalisable. The case n = is obvious,
as well as the case where f = λ · Id and g = µ · Id for some λ, µ ∈ K. So let us assume
n ≥ and that one of the endomorphisms, say f , is not a multiple of the identity. Let
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
λ , . . . , λr be the eigenvalues of f . Since f is diagonalisable,
r
M
E= E λi
i=
and all the summands have dimension ≤ n − (since, if there was a λi such that Eλi is
n-dimensional, then E = Eλi and f = λi Id, contradi ing the assumption that f is not a
multiple of the identity). Since f and g commute, g(Eλi ) ⊂ Eλi . Indeed, if v ∈ Eλi , then
f (g(v)) = g(f (v)) = g(λi v) = λi g(v),
and therefore g(v) ∈ Eλi . It follows that g|Eλ is an endomorphism of Eλi . Moreover,
i
g|Eλ is diagonalisable as the re ri ion of a diagonalisable endomorphism, and f |Eλ
i i
and g|Eλ commute. By the indu ion hypothesis, there exi s a basis of each of the
i
eigenspaces Eλi which respe to which f |Eλ and g|Eλ are simultaneously diagonalis-
i i
able. Putting all these bases together yields the desired basis.
.. The Jordan-Chevalley decomposition
Theorem .. — Let f ∈ L (E) be an endomorphism whose chara eri ic polynomial is of
the form χf = ri= (λi − X)ni . There exi s a unique pair (d, n) ∈ L (E) such that
Q
. f = d +n
. d is diagonalisable
. n is nilpotent
. d and n commute, that is, d ◦ n = n ◦ d
Proof. — Let us fir prove exi ence. Set Fi = ker(f − λi · Id)ni . By Theorem ., there
is a dire sum decomposition
r
M
E= Fi .
i=
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
Pr
Therefore, any ve or x ∈ E can be uniquely written as x = i= xi with xi ∈ Fi . We
define the endomorphisms d and n as follows:
r
X
d(x) = λi xi
i=
r
X
n(x) = (f − λi Id)(xi ),
i=
so that, by con ru ion, f = d + n and d is diagonalisable. To prove that n is nilpotent,
set k = max(n , . . . , nr ). Then
r
X
k
n (x) = (f − λi Id)k (xi ) = ,
i=
since xi ∈ ker((f − λi Id)ni ) ⊂ ker((f − λi Id)k ) because k ≥ ni for all i = , . . . , k. It remains
to show that d and n commute. Since (f − λi Id)(xi ) ill belongs to Fi for all i, we have
r
X r
X r
X
d(n(x)) = λi (f − λi Id)(xi ) = (f − λi Id)(λi xi ) = (f − λi Id)(d(xi )) = n(d(x))
i= i= i=
for all x ∈ E. This finishes the proof of the exi ence.
We now turn to uniqueness. Assume that f = d 0 + n0 is another decomposition satis-
fying properties , , , and of the atement. Since
d 0 ◦ f = d 0 ◦ (d 0 + n0 ) = d 0 ◦ d 0 + d 0 ◦ n0 = d 0 ◦ d 0 + n0 ◦ d 0 = (d 0 + n0 ) ◦ d 0 = f ◦ d 0 ,
the endomorphisms d 0 and f commute. Therefore, d 0 (Fi ) ⊂ Fi for each i = , . . . , r.
Since d|Fi = λi · Id, the re ri ions d|Fi and d 0 |Fi and, therefore, d and d 0 commute. By
Proposition ., d and d 0 are simultaneously diagonalisable, which implies that their
difference d − d 0 is diagonalisable. On the other hand, n and n0 commute since
n ◦ n0 = (f − d) ◦ (f − d 0 ) = f ◦ f − f ◦ d 0 − d ◦ f + d ◦ d 0
= f ◦ f − f ◦ d − d 0 ◦ f + d 0 ◦ d = (f − d 0 ) ◦ (f − d) = n0 ◦ n.
It follows that n − n0 is nilpotent. But d 0 − d = n − n0 and a nilpotent and diagonalisable
endomorphism is necessarily identically zero by the lemma below. Therefore, n = n0
and d = d 0 .
Algebra MAA – Bachelor – Year Chapter – Endomorphisms
Lemma .. — Let f ∈ L (E) be an endomorphism. If f is nilpotent and diagonalisable,
then f = .
Proof. — If f is nilpotent, then there exi s an integer k such that f k = . Let k be the
smalle integer with this property. Then the minimal polymomial of f is X k . On the
other hand, since f is diagonalisable, its minimal polynomial is a produ of di in
fa ors of degree one by Theorem .. Therefore, k = and f = .
You might also like
- Fabula Ultima Errata & F.A.Q. ENG Core Rulebook (Updated May 10th, 2024)No ratings yetFabula Ultima Errata & F.A.Q. ENG Core Rulebook (Updated May 10th, 2024)9 pages
- Foundations of Nonlinear Algebra (John Perry)100% (1)Foundations of Nonlinear Algebra (John Perry)425 pages
- Ywhi 44 V M9 B3 S DNF 7 IBLP6 R WB1 B KWLMNo ratings yetYwhi 44 V M9 B3 S DNF 7 IBLP6 R WB1 B KWLM592 pages
- 350010Abstract Algebra Structures And Applications 1st Edition Stephen Lovett pdf download100% (2)350010Abstract Algebra Structures And Applications 1st Edition Stephen Lovett pdf download89 pages
- Buy ebook Abstract Algebra Structures and Applications 1st Edition Stephen Lovett cheap priceNo ratings yetBuy ebook Abstract Algebra Structures and Applications 1st Edition Stephen Lovett cheap price79 pages
- Abstract Algebra Structures and Applications 1st Edition Stephen Lovett instant download100% (2)Abstract Algebra Structures and Applications 1st Edition Stephen Lovett instant download70 pages
- Abstract Algebra_ Structures and Applications ( PDFDrive )No ratings yetAbstract Algebra_ Structures and Applications ( PDFDrive )717 pages
- PDF Advanced Modern Algebra 1, Second Printing Edition Joseph J. Rotman downloadNo ratings yetPDF Advanced Modern Algebra 1, Second Printing Edition Joseph J. Rotman download51 pages
- Foundations of Nonlinear Algebra (John Perry) (May 2, 2013)No ratings yetFoundations of Nonlinear Algebra (John Perry) (May 2, 2013)424 pages
- Abstract Algebra Structures and Applications 1st Edition Stephen Lovett - Download the ebook now for the best reading experienceNo ratings yetAbstract Algebra Structures and Applications 1st Edition Stephen Lovett - Download the ebook now for the best reading experience84 pages
- D. S. Malik, John N. Mordeson, M. K. Sen - MTH 581-582 Introduction To Abstract Algebra (2010)No ratings yetD. S. Malik, John N. Mordeson, M. K. Sen - MTH 581-582 Introduction To Abstract Algebra (2010)276 pages
- MTH 581 582 Introduction To Abstract AlgNo ratings yetMTH 581 582 Introduction To Abstract Alg276 pages
- MTH 4104 Introduction To Algebra: Notes (Version of April 6, 2018) Spring 2018No ratings yetMTH 4104 Introduction To Algebra: Notes (Version of April 6, 2018) Spring 201883 pages
- Challenges Encountered by The Micro-Enterprises in The During and Post-Pandemic Stage in Lucena CityNo ratings yetChallenges Encountered by The Micro-Enterprises in The During and Post-Pandemic Stage in Lucena City40 pages
- Community Leaders Candidate Submission Assignment Grading RubricNo ratings yetCommunity Leaders Candidate Submission Assignment Grading Rubric1 page
- Service Contract For Construction of Boreholes at Dangote Refinery - Final100% (1)Service Contract For Construction of Boreholes at Dangote Refinery - Final6 pages
- The Feasibility Study of Producing BioethanolNo ratings yetThe Feasibility Study of Producing Bioethanol23 pages
- Golden Era of Pia: Special Interest ArticlesNo ratings yetGolden Era of Pia: Special Interest Articles5 pages
- Abstract Algebra - Basic, Polynomials, Galois Theory, Categorial and Commutative Algebra83% (6)Abstract Algebra - Basic, Polynomials, Galois Theory, Categorial and Commutative Algebra383 pages
- Blood Chemistry and CBC Analysis - Clinical Laboratory Testing From A Functional Perspective - Quick Reference Guide75% (20)Blood Chemistry and CBC Analysis - Clinical Laboratory Testing From A Functional Perspective - Quick Reference Guide29 pages
- Fields and Galois Theory: J.S. Milne August 31, 2003No ratings yetFields and Galois Theory: J.S. Milne August 31, 200399 pages
- 10 Toxins and How To Antidote Them With Homeopathy100% (1)10 Toxins and How To Antidote Them With Homeopathy7 pages
- In Sight of the Aspen Grove Book 2 Poetry from Rist CreekFrom EverandIn Sight of the Aspen Grove Book 2 Poetry from Rist CreekNo ratings yet
- C Programs For Beginners: A Step-by-Step Guide to Coding Your First C ProgramsFrom EverandC Programs For Beginners: A Step-by-Step Guide to Coding Your First C ProgramsNo ratings yet
- The Silence of Everything: Unspoken emotions of the loudest soundFrom EverandThe Silence of Everything: Unspoken emotions of the loudest soundNo ratings yet
- The Essential Robert Frost: Collected Poems 1913-1923 (Warbler Classics Annotated Edition)From EverandThe Essential Robert Frost: Collected Poems 1913-1923 (Warbler Classics Annotated Edition)No ratings yet
- Ascending Master's Guide: A textbook tool fusing science with spirituality.From EverandAscending Master's Guide: A textbook tool fusing science with spirituality.No ratings yet
- Knit Soxx for Everyone: 25 Colorful Sock Patterns for the Whole FamilyFrom EverandKnit Soxx for Everyone: 25 Colorful Sock Patterns for the Whole Family4.5/5 (2)
- The Future Is Ours: The Collected Science Fiction of Edward D. HochFrom EverandThe Future Is Ours: The Collected Science Fiction of Edward D. HochNo ratings yet
