\documentclass[%
version=last,%
a5paper,
12pt,%
headings=small,%
bibliography=totoc,%
index=totoc,%
%abstract=true,%
titlepage=no,%
twoside,%
reqno,%
cleardoublepage=empty,%
open=any,%
%parskip=half,%
titlepage=false,%
%draft=false,%
draft=true,%
%DIV=classic,%
DIV=12,%
headinclude=false,%
pagesize]%
{scrbook}
%{scrreprt}
%{scrartcl}

%\usepackage{layout}
%\usepackage[notref,notcite]{showkeys}

\usepackage{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\refoot{Finite fields}
\lofoot{\leftmark}
\ofoot{\pagemark}
%\ifoot{\headmark}

\usepackage{moredefs,lips}
%\makeindex
%\usepackage{makeidx}

\usepackage[perpage,symbol]{footmisc}
%\renewcommand{\captionformat}{. }

%\usepackage[safe]{tipa} % For IPA

%\usepackage{chngcntr}
%\counterwithout{figure}{chapter}
%\counterwithout{table}{chapter}

\usepackage{graphicx} % allows \rotatebox
\usepackage{verbatim}
%\usepackage{subfig}
%\usepackage{float}
%\floatplacement{figure}{t}
%\usepackage[section]{placeins} % floats do not cross sectional divisions
%\usepackage{placeins} % floats do not cross \FloatBarrier
%\usepackage{afterpage}

\usepackage{relsize} % Here \smaller scales by 1/1.2; \relscale{X} scales by X


%\begin{comment}

\renewenvironment{quote}{\begin{list}{}
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}}
\item\relax}
{\end{list}}

\renewenvironment{quotation}{\begin{list}{}%
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}
\setlength{\listparindent}{1em}
\setlength{\itemindent}{\listparindent}
\setlength{\parsep}{\parskip}}
\item\relax}
{\end{list}}

%\end{comment}

%\usepackage{verse}

%\usepackage{multicol}
\usepackage{pstricks,pst-node,pst-plot,pst-math}

\usepackage{amsmath,amsthm,amssymb,bm,upgreek}
%\allowdisplaybreaks
\DeclareMathOperator{\Endo}{End}
\newcommand{\End}[1][V,+]{\Endo(#1)}

\DeclareMathOperator{\identity}{id} % gives weird spacing
\newcommand{\id}[1][V]{\identity_{#1}}
%\newcommand{\id}[1][V]{\mathsf{id}_{#1}}
\newcommand{\inv}{^{-1}}
%\renewcommand{\phi}{\varphi}
\newcommand{\divides}{\mid}
\newcommand{\ndivides}{\nmid}
\newcommand{\gpgen}[1]{\langle#1\rangle}
\newcommand{\euphi}{\upvarphi}
\newcommand{\included}{\subseteq}
\newcommand{\pincluded}{\subset}
\renewcommand{\vec}[1]{\bm{#1}}

\newcommand{\C}{\mathbb C}
\newcommand{\R}{\mathbb R}
\newcommand{\Q}{\mathbb Q}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\F}[1][p]{\mathbb F_{#1}}
\newcommand{\units}[1]{#1{}^{\times}}
\DeclareMathOperator{\dee}{d}
\renewcommand{\setminus}{\smallsetminus}
\DeclareMathOperator{\automorphisms}{Aut}
\newcommand{\Aut}[1][\Zmod,+]{\automorphisms(#1)}
\DeclareMathOperator{\genlin}{GL}
\newcommand{\GL}[1][n]{\genlin_{#1}(\Z)}
\DeclareMathOperator{\diagonal}{diag}
\newcommand{\diag}[1]{\diagonal(#1)}
\newcommand{\alg}[1]{#1{}^{\mathrm{alg}}}
\DeclareMathOperator{\matrices}{M}
\newcommand{\Mat}[1][K]{\matrices_n(#1)}
\DeclareMathOperator{\Identity}{I}
\newcommand{\Id}[1][n]{\Identity_{#1}}
\DeclareMathOperator{\adjoint}{adj}
\newcommand{\adj}[1][B]{\adjoint(#1)}
\DeclareMathOperator{\Span}{span}
\DeclareMathOperator{\symmetric}{Sym}
\newcommand{\Sym}[1][n]{\symmetric(#1)}
\DeclareMathOperator{\signum}{sgn}
\newcommand{\sgn}[1][\sigma]{\signum(#1)}

%\newcommand{\mi}{\mathrm i\,}
%\newcommand{\me}{\mathrm e}
%\newcommand{\T}{\mathbb T}
%\newcommand{\pru}[1][n]{\upomega_{#1}{}}
\newcommand{\Zmod}[1][n]{\Z_{#1}}
%\DeclareMathOperator{\Li}{Li}
%\newcommand{\conj}[1]{\overline{#1}}
%\newcommand{\doubtful}{\textsuperscript?}
%\newcounter{xnum}
%\newcommand{\xnum}{\refstepcounter{xnum}[\arabic{xnum}]}

\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\Forall}[1]{\forall#1\;}
%\newcommand{\The}[1]{\text{\rotatebox[origin=c]{180}{$\iota$}}#1\;}

\newtheorem*{Euclem}{Euclid's Lemma}
\newtheorem*{Eugen}{Euclid's Lemma, generalized}
\newtheorem*{Bezout}{B\'ezout's Lemma}
\newtheorem*{Cfag}{Classification of finite abelian groups}
\newtheorem*{theorem}{Theorem}

%\newcommand{\Ham}{\mathbb H}
%\DeclareMathOperator{\cont}{C}
%\newcommand{\lto}{\Rightarrow}
%\newcommand{\liff}{\Leftrightarrow}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\emptyset}{\varnothing}
%\renewcommand{\epsilon}{\varepsilon}
%\newcommand{\gid}{\mathrm e}

\usepackage[all]{xy}
%\renewcommand{\theequation}{\fnsymbol{equation}}

%\usepackage[utf8]{inputenc}
%\usepackage[turkish,english]{babel}

%\usepackage{gfsneohellenic}
%\newcommand{\gr}[1]{\foreignlanguage{polutonikogreek}{%
%\relscale{0.9}\textneohellenic{#1}}}

\usepackage[polutonikogreek,english]{babel}
\newcommand{\gr}[1]{\foreignlanguage{polutonikogreek}{#1}}
%\usepackage{gfsporson} % this conflicts with bm, not allowing a boldface digit 0
%\usepackage{gfsneohellenic} % so does this, more so, since it changes the digits anyway
%\newcommand{\gr}[1]{\foreignlanguage{polutonikogreek}{%
%\relscale{0.9}
%\textporson{#1}}}

\newcommand{\enquote}[1]{``#1''}

%\newcommand{\grm}[1]{\ensuremath{\text{\foreignlanguage{polutonikogreek}{#1}}}}
%\newcommand{\grm}[1]{\ensuremath{\text{\gr{#1}}}}
%\newcommand{\myXi}{X}

\newcommand{\abs}[1]{\left\lvert#1\right\rvert}


\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}
\usepackage{url}

\begin{document}

\subtitle{A course at the Nesin Mathematics Village}
\title{Finite fields}
\author{David Pierce}
\date{January 18--24, 2016\\Last edited, February 25, 2016}
\publishers{Matematik B\"ol\"um\"u\\
Mimar Sinan G\"uzel Sanatlar \"Universitesi\\
\.Istanbul\\
\url{mat.msgsu.edu.tr/~dpierce/}\\
\url{dpierce@msgsu.edu.tr}}

\maketitle
\thispagestyle{empty}
%\tableofcontents
%\setcounter{chapter}{-1}
\chapter*{Preface}

The present typeset document is based on
a course of lectures at the Nesin Mathematics Village in \c Sirince,
Sel\c cuk, \.Izmir, January 18--24 (Monday--Sunday), 2016.

My course was one of three on the general theme of linear algebra.
The students were mostly advanced undergraduates,
though not necessarily from mathematics departments.
The daily schedule was as follows.
\begin{center}\relscale{0.9}
\begin{tabular}{rl}
9:00&Ali Nesin\\
11:00&Ali Nesin\\
13:00&lunch, chores, rest\\
15:00&Haluk Oral\\
17:00&David Pierce\\
19:00&dinner
\end{tabular}
\end{center}
Thursdays at the Village are free in the summer,
but not in the winter.
However, on the Friday of the program, Haluk took my hours,
so that he could leave the next morning;
I took his hours that afternoon.
Most students were gone by Sunday afternoon,
but I gave a lecture then to the few who remained
and wanted to come.

Haluk's course treated basic linear algebra
(subspaces, linear independence, etc.);
Ali's, modules.
Ali suggested on Monday morning 
that my course
\begin{quote}
treat one or several of the following:
\begin{compactenum}
\item
Finite fields.
\item
Nondegenerate bilinear forms and some classification problems.
\item
Tensor product of modules.
\item
Jordan normal form.
\end{compactenum}
\end{quote}
I chose finite fields,
with Jordan normal forms on the last day,
since one student asked to hear about eigenvectors.

I started typesetting this document
on Thursday morning,
after three lectures had been completed.
The sources are 
\begin{inparaenum}[(1)]
\item
my handwritten notes, prepared before the lectures,
\item
my memory of what happened in the lectures,
and sometimes
\item
my wishes for enlargements or improvements.
\end{inparaenum}
Thus
the notes are not a precise record of what actually happened,
though they should be close.
The appendix completes the work on Jordan normal forms
started in the last class.

I started the first lecture in Turkish,
though writing on the board in English.
During the break after fifty minutes,
students invited me to speak in English.
Since nobody in the class as a whole 
expressed a preference for Turkish when I asked,
I did switch to English, mostly.
Sometimes students asked questions,
or asked for clarifications, in Turkish. 

I originally learned much of the content of the course
in a graduate algebra course by Larry Washington
that used Hungerford \cite{MR600654} as a reference.
I learned elementary number theory through teaching it,
in a course based on Burton \cite{Burton}.
In \c Sirince, for the linear algebra,
I had the books of Cemal Ko\c c \cite{CK-I,CK-II} at hand;
for finite fields, 
I had a look at Lidl and Niederreiter \cite{MR860948}.

\tableofcontents
\listoffigures

\addchap{Introduction}

The main aim of the course is to establish
the classification and description of finite fields as follows.
\begin{compactenum}
\item
The size of every finite field is a power of a prime.
\item
For each prime power $p^n$, there is, up to isomorphism, 
exactly one field, called $\F[p^n]$, whose size is $p^n$.
\item
$\F[p^m]\included\F[p^n]$ if and only if $m\divides n$.
\item
The group of units of every finite field is cyclic.
\end{compactenum}
There is a similar list on page \pageref{ff-thms}.
Our work will require the classication of finite abelian groups
(page \pageref{class}),
which uses linear algebra.
The full statement of the classification 
uses the Chinese Remainder Theorem (page \pageref{CRT}).

Our work will also involve polynomial rings (in one variable) over fields.
Such rings are analogous to the ring $\Z$ of rational integers.
An incidental aim then is to analyze three theorems about integers:
\begin{compactenum}
\item
Euclid's Lemma (pages \pageref{Euclem} and \pageref{Euclem2}), 
namely Proposition 30 of Book \textsc{vii} of Euclid's \emph{Elements};
\item
B\'ezout's Lemma (pages \pageref{Bezout} and \pageref{Bezout2}); and
\item
the efficacy of the Euclidean Algorithm (page \pageref{Eucalg}) for finding greatest common divisors:
Propositions 1 and 2 of Book \textsc{vii} of the \emph{Elements.}
\end{compactenum}
Among commutative rings
that have no infinite descending chains of divisors,
that is, no sequences $(a_0,a_1,a_2,\dots)$ such that $a_{n+1}\divides a_n$,
but $a_n\ndivides a_{n+1}$,
the three theorems establish sufficient and necessary conditions for being, respectively,
\begin{compactenum}[(1)]
\item
a unique factorization domain (UFD),
\item
a principal ideal domain (PID), and
\item
a Euclidean domain (ED).
\end{compactenum}



\chapter{Monday, January 18}


What is a \emph{vector space}?  The answer could be
\begin{compactitem}\sloppy
\item
a definition: ``A vector space is $X$'';
\item
an example (or family of examples):
``$X$ is a vector space.''
\end{compactitem}

\addsec{Definitions}

By definition, a \textbf{vector space} is an \emph{abelian group,}
together with a homomorphism from a \emph{field} to the \emph{endomorphism ring} of the group.

An \textbf{abelian group} is a pair $(V,+)$,
where $+$ is a binary operation called \textbf{addition} on the set $V$, and
\begin{compactenum}[1)]
\item
the equations
\begin{align*}
	\vec u+\vec v&=\vec v+\vec u,&\vec u+(\vec v+\vec w)&=(\vec u+\vec v)+\vec w
\end{align*}
are \emph{identities} on $V$,
that is, $+$ is \textbf{commutative} and \textbf{associative} on $V$;
\item
there is an \textbf{identity} for $+$ in $V$,
namely an element of $V$ denoted by
\begin{equation*}
\vec0
\end{equation*}
and called \textbf{zero,}
such that, for all $\vec a$ in $V$,
\begin{equation*}
\vec a+\vec0=\vec a
\end{equation*}
(and therefore $\vec0+\vec a=\vec a$, since $+$ is commutative);
\item
each $\vec a$ in $V$ has an \textbf{(additive) inverse,}
namely an element of $V$ denoted by
\begin{equation*}
-\vec a
\end{equation*} 
such that
\begin{equation*}
-\vec a+\vec a=\vec0
\end{equation*}
(and therefore $\vec a+(-\vec a)=\vec0$).
\end{compactenum}
Yes, we use the word ``identity'' in two ways, 
to describe both
\begin{inparaenum}[(1)]
\item\label{identity}
an equation that is true for all values of its variables, and also
\item
an element of a set that has no effect when combined with others by means of some operation.
\end{inparaenum}

We may speak of $V$ as an abelian group if it is clear that we mean $(V,+)$.

An \textbf{endomorphism} of $(V,+)$
is a function $f$ from $V$ to itself such that the equation
\begin{equation*}
f(\vec u+\vec v)=f(\vec u)+f(\vec v)
\end{equation*}
is an identity on $V$.
The set of endomorphisms of $(V,+)$ can be denoted by
\begin{equation*}
\End.
\end{equation*}
This contains the function $\vec v\mapsto\vec v$, called
the \textbf{identity} on $V$ and abbreviated by
\begin{equation*}
\id.
\end{equation*}
Also $\End$ is closed under the binary operations of \textbf{composition} and \textbf{addition,}
defined by the identities
\begin{align*}
	(f\circ g)(\vec v)&=f(g(\vec v)),&
	(f+g)(\vec v)&=f(\vec v)+g(\vec v).
\end{align*}
Addition in $\End$ is different from addition in $V$,
but they are related, and they are given the same symbol.
The quadruple $(\End,+,\circ,\id)$ is a \textbf{ring:}\label{End}
this means
\begin{compactenum}[1)]\sloppy
\item
$\End$ is an abelian group with respect to $+$;
\item
composition on $\End$ is associative,
and $\id$ is an identity for it;
this means that the structure
$(\End,\circ,\id)$ a \textbf{monoid,}
though I did not use this term in class;
\item
the equations
\begin{align*}
	(f+g)\circ h&=f\circ h+g\circ h,&
	f\circ(g+h)&=f\circ g+f\circ h
\end{align*}
are identities on $\End$, that is,
composition \textbf{distributes} over addition.
\end{compactenum}
The element $\id$ of $\End$ is the \textbf{identity}
both of the monoid and of the ring.
Some persons' rings are not required to have identities;
but our rings are.
In our example, composition is the \textbf{multiplication} of the ring.
In an arbitrary ring, this operation may be denoted by a dot,
or by nothing at all, as in $a\cdot b$ or $ab$.
Also, the identity of the ring may be denoted by $1$.
If the multiplication of a ring is commutative,
then the ring itself is called a \textbf{commutative ring.}%%%%%
\footnote{The question arose among students in \c Sirince
of why rings are so called.
If $\eta$ is a complex number such that
$\eta^2+B\eta+C=0$ for some integers $B$ and $C$,
then the abelian group $\gpgen{1,\eta}$,
namely $\{x+\eta y\colon(x,y)\in\Z\times\Z\}$,
is closed under multiplication.
According to Harvey Cohn \cite[p.~49]{Cohn-ANT},
David Hilbert in 1892 introduced the term \emph{number ring} (\emph{Zahlring})
for the group, because $\eta^2$ ``circles directly back'' to the group
as $-B\eta-C$.}

A ring $(K,+,{}\cdot{},1)$ is a \textbf{field} if
$(K\setminus\{0\},{}\cdot{})$ is an abelian group,
where $0$ is the identity of the group $(K,+)$.
In this case, if $\varphi$ is a function from $K$ to $\End$
such that the equations
\begin{align*}
	\varphi(x+y)&=\varphi(x)+\varphi(y),&
	\varphi(xy)&=\varphi(x)\circ\varphi(y),&
	\varphi(1)&=\id
\end{align*}
are identities,
this means $\varphi$ \emph{preserves} addition, multiplication, and the identity,
and $\varphi$ is a
\textbf{homomorphism} from $K$ as a ring to $\End$ as a ring.
In this case, the triple $(V,+,\varphi)$ is a vector space.
We may also say that the pair $(V,+)$ is vector space \textbf{over} $K$,
with respect to $\varphi$.
Preservation of the identity by $\varphi$ is important.
without it, $\varphi$ could be $x\mapsto0$,
where $0$ stands for the element $\vec v\mapsto\vec0$ of $\End$,
even if $V$ has more than one element, and so $\id$ is different from $0$ in $\End$.
We do not wish to allow $\varphi$ to be $x\mapsto0$
unless $V=\{\vec0\}$.

In this last case, when $V=\{\vec0\}$,
then $(V,+)$ is a \textbf{trivial group,}
$\End$ is the \textbf{trivial ring,}
having a single element,
which is both $\vec v\mapsto\vec0$ and $\id$,
the zero and the identity.
In this case, $V$ is a vector space over every field.
In case $V$ is nontrivial,
then every $\varphi$ as above must be injective,
and therefore it can be understood as an identity,
so that $K$ is just a sub-ring of $\End$ that happens to be a field.

\addsec{Examples}

Examples of fields are $\R$, $\C$, and $\Q$.

$\Z$ is a commutative ring, but not a field.

The \textbf{counting numbers} are $1$, $2$, $3$, and so on.
I use the expression
\begin{equation*}
\N
\end{equation*}
to denote the set of these numbers.
Here presumably $\N$ stands for the \textbf{natural numbers.}
Some persons count $0$ as a natural number,
considering it to belong to $\N$.
I prefer to use the notation
\begin{equation*}
\upomega=\{0,1,2,\dots\}=\{0\}\cup\N.
\end{equation*}
Neither $\N$ nor $\upomega$ is a ring.

If $n\in\N$, then by definition
\begin{equation*}
\Zmod=\{[x]\colon x\in\Z\},
\end{equation*}
where
\begin{align*}
[x]=[y]
&\iff x\equiv y\pmod n\\
&\iff n\divides x-y.
\end{align*}
Here ``$x\equiv y\pmod n$'' is read as \textbf{$x$ is congruent to $y$ \emph{modulo} $n$}.%%%%%
\footnote{\emph{Modulo} is the dative or ablative case (roughly,
the Turkish \emph{-e} or \emph{-den hali})
of the Latin noun \emph{modulus.}
Writing entirely in Latin,
Gauss in the \emph{Disquisitiones Arithmeticae} uses the expression \emph{secundum modulum} $n$, 
``according to the modulus $n$'' \cite[p.~2]{Gauss-Latin}.}
The definition of $\Zmod$ does not say what $[x]$ \emph{is};\label{is}
it says only when two instances of $[x]$ are to be counted as the \emph{same.}
We can think that
\begin{equation}\label{eqn:Zmod}
\Zmod=\{0,\dots,n-1\}=\{x\in\upomega\colon x<n\},
\end{equation}
since every integer is indeed congruent \emph{modulo} $n$
to an element of this set,
but no two elements are congruent to one another.
Since, \emph{modulo} $n$,
\begin{equation*}
x\equiv x_1\And y\equiv y_1\implies x+y\equiv x_1+y_1\And xy\equiv x_1y_1,
\end{equation*}
operations of addition and multiplication on $\Zmod$ are well defined by the rules
\begin{align*}
	[x]+[y]&=[x+y],&
	[x]\cdot[y]&=[xy].
\end{align*}
With respect to these operations,
$\Zmod$ is a commutative ring,
because $\Z$ is a commutative ring.
If we use the understanding in \eqref{eqn:Zmod},
then for example $[n]=0$, $[n+1]=1$, and $[-1]=n-1$.

When is the ring $\Zmod$ a field, that is,
when do nonzero elements have (multiplicative) inverses?
\begin{compactitem}
\item
If $n=1$, then $\Zmod=\{0\}$, which cannot be a field,
since $\{0\}\setminus\{0\}=\emptyset$, and every group is nonempty
(it contains at least the identity).
\item
Suppose $n$ is composite, that is, $n=ab$ for some $a$ and $b$ such that $1<a<n$,
so that also $1<b<n$.
If $ax\equiv1\pmod n$, then
\begin{equation*}
b\equiv bax\equiv nx\equiv0\pmod n,
\end{equation*}
which is absurd.
Thus $\Zmod$ is not a field in this case.
\item
If $n$ is prime, we shall show $\Zmod$ is a field.
The proof will use the following.
\end{compactitem}

\begin{Euclem}\label{Euclem}
In $\Z$, for all primes $p$,
\begin{equation*}
p\divides ab\And p\ndivides a\implies p\divides b.
\end{equation*}
\end{Euclem}

Proving this is an \textbf{exercise}
(which will be solved on pages \pageref{thm:EL} and \pageref{EL}).
The letter $p$ will always stand for a prime.
Because of the Lemma,
if $1\leq a<p$, then the endomorphism $x\mapsto ax$
of $(\Zmod,+)$ is injective, since, \emph{modulo} $p$,
\begin{align*}
	ax\equiv ay
	&\implies p\divides ax-ay&&\\
	&\implies p\divides a(x-y)&&\\
	&\implies p\divides x-y&&\text{[by the Lemma, since $p\ndivides a$]}\\
	&\implies x\equiv y.&&
\end{align*}
By the Pigeonhole Principle, since $\Zmod[p]$ is finite,
$x\mapsto ax$ must also be surjective.
In particular, the congruence
\begin{equation*}
ax\equiv1\pmod p
\end{equation*}
is soluble.

So now $\Zmod[p]$ is field,\label{Zp-field} 
called
\begin{equation*}
\F.
\end{equation*}
We shall show that there are other finite fields.
In particular, for every prime $p$,
for every $n$ in $\N$,
there will be a unique field called
\begin{equation*}
\F[p^n]
\end{equation*}
of size $p^n$.
For example, $\F[4]=\{0,1,\alpha,\alpha+1\}$,\label{F4}
with multiplication defined so that
\begin{equation*}
\alpha^2=\alpha+1.
\end{equation*}
\begin{comment}

Thus the operations are as follows:
\begin{gather*}
	\begin{array}{c|*4c}
	       +&       0&       1&  \alpha&\alpha+1\\\hline
	       0&       0&       1&  \alpha&\alpha+1\\
	       1&       1&       0&\alpha+1&\alpha  \\
	  \alpha&  \alpha&\alpha+1&       0&       1\\
	\alpha+1&\alpha+1&  \alpha&       1&       0
	\end{array}\\
	\begin{array}{c|*4c}
	  \times&       0&       1&  \alpha&\alpha+1\\\hline
	       0&       0&       0&       0&       0\\
	       1&       0&       1&  \alpha&\alpha+1\\
	  \alpha&       0&  \alpha&\alpha+1&       1\\
	\alpha+1&       0&\alpha+1&       1&  \alpha
	\end{array}
\end{gather*}

\end{comment}
If we write $\beta$ for $\alpha+1$, the operations are thus:
\begin{align*}
&	\begin{array}{c|*4c}
	       +&       0&       1&  \alpha&\beta\\\hline
	       0&       0&       1&  \alpha&\beta\\
	       1&       1&       0&\beta&\alpha  \\
	  \alpha&  \alpha&\beta&       0&       1\\
	\beta&\beta&  \alpha&       1&       0
	\end{array}&
&	\begin{array}{c|*4c}
	  \times&       0&       1&  \alpha&\beta\\\hline
	       0&       0&       0&       0&       0\\
	       1&       0&       1&  \alpha&\beta\\
	  \alpha&       0&  \alpha&\beta&       1\\
	\beta&       0&\beta&       1&  \alpha
	\end{array}	
\end{align*}
If $K$ is a finite field,
then as a group it has the subgroup
denoted by
\begin{equation*}
\gpgen1,
\end{equation*}
namely the smallest subgroup that contains $1$.
Since $K$ is finite, $\gpgen1$ must be $\Zmod$ for some $n$.
This will be a sub-ring of $K$,
and so $n$ must be prime,
since (in the terms of tomorrow's lecture)
every sub-ring of a field must be an \emph{integral domain,}
and we have shown in effect that $\Zmod$ is not an integral domain
if $n=1$ or $n$ is composite.
The prime $p$ such that $\gpgen1=\Zmod[p]$,
or rather such that
\begin{equation*}
\underbrace{1+\dots+1}_p=0
\end{equation*} 
in $K$,
is called the \textbf{characteristic} of the field.
There is no such $p$
for the fields $\Q$, $\R$, and $\C$,
and so these are said to have characteristic $0$.

If $K$ is a field, and $n\in\N$,
then $K^n$ is a vector space over $K$.
The elements of $K^n$ are
\begin{equation*}
(x_1,\dots,x_n),
\end{equation*}
where each $x_j$ is in $K$.
Addition in $K^n$ is given by
\begin{equation*}
(x_1,\dots,x_n)+(y_1,\dots,y_n)=(x_1+y_1,\dots,x_n+y_n),
\end{equation*}
and each $a$ in $K^n$ determines the endomorphism
\begin{equation*}
(x_1,\dots,x_n)\mapsto(ax_1,\dots,ax_n).
\end{equation*}
But what \emph{is} $(x_1,\dots,x_n)$?
It is the function on $\{1,\dots,n\}$
that takes the value $x_j$ at each $j$.

If $A$ is an arbitrary set, then we can define
\begin{equation*}
K^A=\{\text{functions from $A$ to $K$}\};
\end{equation*}
this is a vector space over $K$,
just as $K^n$ is.
In particular,
\begin{equation*}
K^n=K^{\{1,\dots,n\}}.
\end{equation*}
We cannot define $n$ as $\{1,\dots,n\}$.
We can however define\label{vN}
\begin{equation*}
n=\{0,\dots,n-1\}.
\end{equation*}
Thus
\begin{align*}
	0&=\emptyset,&n+1&=n\cup\{n\}.
\end{align*}
With this understanding,
which is the one that I prefer,
elements of $K^n$ can be written as
\begin{equation*}
(x_0,\dots,x_{n-1}).
\end{equation*}

\chapter{Tuesday, January 19}

\addsec{Products}

For any sets $A$ and $B$, we can let
\begin{equation*}
B^A=\{\text{functions from $A$ to $B$}\}.
\end{equation*}
If $B$ is a field, then, as we said yesterday, $B^A$ is a vector space.
Moreover, if $B$ is itself a vector space over some field,
then $B^A$ is also a vector space over that field.
If $B$ is a group or a ring, then so is $B^A$.

More generally, if we are given a set $B_a$ for each $a$ in $A$,
we define the \textbf{product}
\begin{equation*}
\prod_{a\in A}B_a
\end{equation*}
to be the set of functions $f$ on $A$ such that, for each $a$ in $A$,
\begin{equation*}
f(a)\in B_a.
\end{equation*}
Thus
\begin{equation*}
B^A=\prod_{a\in A}B.
\end{equation*}
Also, if $n\in\upomega$, we may use the notations
\begin{align*}
\prod_{i\in n}B_i&=B_0\times\dots\times B_{n-1},&
B^n&=\underbrace{B\times\dots\times B}_n.	
\end{align*}
If each $B_a$ is a vector space (over the same field),
or a group, or a ring,
then so is $\prod_{a\in A}B_a$.
In each case,
this is because, for example, 
if $*$ is a binary operation on each $B_a$,
then the ``same'' operation can be defined on $\prod_{a\in A}B_a$ by
\begin{equation*}
(f*g)(x)=f(x)*g(x).
\end{equation*}
As we have seen, groups, rings, and vector spaces over a given field
are defined by \emph{identities,}
namely (as we said on page \pageref{identity})
equations that hold for all possible values of the variables.
An identity on $B$ is also an identity on $B^A$.
However, among the field axioms, there is the formula
\begin{equation*}
\Exists y(x\neq0\implies xy=1).
\end{equation*}
As an axiom,
this formula is understood to hold for all values of its free variable, which is $x$.
But the formula is not an equation,
and so we cannot automatically expect it to hold in a product of fields.
Indeed $K^A$ is not a field when $K$ is,
unless $\abs A=1$.

\addsec{Integral domains}

An \textbf{integral domain} is a nontrivial commutative ring
with no \textbf{zero divisors,} that is, 
no nonzero elements $a$ and $b$ such that $ab=0$.
Thus integral domains have the axiom
\begin{equation*}
xy=0\And x=0\implies y=0,
\end{equation*}
which is not an equation.
Indeed, in $\Z\times\Z$, we have
\begin{equation*}
(1,0)\cdot(0,1)=(0,0),
\end{equation*}
and $(0,0)$ is the group identity of $\Z\times\Z$;
so $(1,0)$ and $(0,1)$ are zero divisors.

If $n$ is a composite element of $\N$,
we proved yesterday that $\Zmod$ is not a field by showing,
in effect, that $\Zmod$ has zero divisors,
and these are not invertible.
This is true in every ring:
a zero divisor cannot be invertible.
Thus invertible elements are not zero divisors,
and therefore every field is an integral domain.
However, the converse fails:
$\Z$ is an integral domain that is not a field.

\addsec{Finite cyclic groups}

As we showed yesterday,
\begin{itemize}
\item
$\Zmod[1]$ is the trivial ring, which is not a field;
\item
$\Zmod$ is not a field when $n$ is composite;
\item
$\Zmod[p]$ is a field when $p$ is prime.
\end{itemize}
Thus if $n\in\N$ and $\Zmod$ is a field, then $n$ must be prime,
by pure logic.
If $n$ is composite, so that $n=ab$,
where $a$ and $b$ are strictly between $1$ and $n$,
then $a$ and $b$ are zero divisors in $\Zmod$.
We consider the first few groups $\Zmod$.
\begin{compactitem}
\item
$\Zmod[2]$ and $\Zmod[3]$ are fields.
\item
In $\Zmod[4]$, $1^2=1$, $2^2=0$, $3^2=1$, so $1$ and $3$ are invertible,
but $2$ is a zero-divisor and is therefore not invertible.
\item
$\Zmod[5]$ is a field.
\item
In $\Zmod[6]$, $1^2=1$, $2\cdot3=0$, $4\cdot3=0$, $5^2=1$;
so $1$ and $5$ are invertible, but $2$, $3$, and $4$
are zero divisors.
\item
$\Zmod[7]$ is a field.
\item
In $\Zmod[8]$, $1^2=3^3=5^2=7^2$, but $2\cdot4=6\cdot4=0$.
\item
In $\Zmod[9]$, $1^2=2\cdot5=4\cdot7=8^2=1$, but $3^2=6^2=0$.
\end{compactitem}

\addsec{Groups of units}

If $R$ is a commutative ring, we define
\begin{equation*}
\units R=\{\text{invertible elements of $R$}\}.
\end{equation*}
Here $\times$ is the multiplication sign
(and not the letter $x$).
Thus if $p$ is prime, then
\begin{equation*}
\units{\Zmod[p]}=\{1,\dots,p-1\};
\end{equation*}
but
\begin{align*}
	\units{\Zmod[4]}&=\{1,3\},&
	\units{\Zmod[6]}&=\{1,5\},&
	\units{\Zmod[8]}&=\{1,3,5,7\},
\end{align*}
\begin{align*}
	\units{\Zmod[9]}&=\{1,2,4,5,7,8\},&
	\units{\Zmod[10]}&=\{1,3,7,9\}.
\end{align*}	
In general, $\units R$ is called the \textbf{group of units} of $R$.
The set $\units R$
is indeed a group with respect to multiplication,
since each element $a$ by definition has an inverse, $a\inv$,
and then this too has an inverse, namely $a$,
and so $a\inv\in\units R$.
Invertible elements of a ring are \textbf{units.}

\begin{theorem}
For all $n$ in $\N$,
\begin{equation}\label{eqn:Zn-gcd}
\units{\Zmod}=\{k\in\upomega\colon k<n\And\gcd(k,n)=1\}.
\end{equation}
\end{theorem}

\begin{proof}
Assuming $0\leq k<n$, we want to show that, \emph{modulo} $n$,
\begin{equation*}
\gcd(k,n)=1\iff \Exists xkx\equiv1.
\end{equation*}
($\Leftarrow$).  Suppose $ka\equiv1$.
Then $n\divides ka-1$, so
\begin{equation*}
\gcd(k,n)\divides ka-1.
\end{equation*}
But $\gcd(k,n)\divides ka$, so $\gcd(k,n)\divides1$,
and therefore $\gcd(k,n)=1$.

($\Rightarrow$).  Suppose $\gcd(k,n)=1$.
As yesterday, the endomorphism $x\mapsto kx$ of $\Zmod$
is injective, by the more general form of Euclid's Lemma below.
Again $x\mapsto kx$ must be surjective by the Pigeonhole Principle, 
so $kx\equiv1\pmod n$ is soluble.
\end{proof}

So the proof is completed by the following.

\begin{Eugen}\label{thm:EL}
For all $m$ in $\N$, for all $a$ and $b$ in $\upomega$,
\begin{equation}\label{eqn:claim}
m\divides ab\And\gcd(m,a)=1\implies m\divides b.
\end{equation}
\end{Eugen}

\begin{proof}
Suppose the claim is false; we shall find a contradiction.
If the claim is false, then,
because $\N$ is well ordered,
there is a \emph{minimal counterexample,}
namely some $n$ in $\N$ such that, for all $m$ in $\N$,
if $m<n$, then for all $a$ and $b$ in $\upomega$, \eqref{eqn:claim} holds;
but for some $a$ and $b$ in $\upomega$,
\begin{equation}\label{eqn:nab}
n\divides ab\And\gcd(n,a)=1\And n\ndivides b.
\end{equation}
If $a\geq n$, then we can replace $a$ with $a-n$.
Thus, since $\upomega$ is well ordered, we may assume $a<n$.
Similarly we may assume $b<n$.
Then $ab<n^2$, and so, for some $m$,
\begin{equation*}
mn=ab\And m<n.
\end{equation*}
In particular,
\begin{equation*}
\frac m{\gcd(m,a)}\cdot n=\frac a{\gcd(m,a)}\cdot b.
\end{equation*}
Therefore in \eqref{eqn:nab} we can replace $a$ with $a/\gcd(m,a)$.
Thus we may assume $\gcd(m,a)=1$.
Now, \eqref{eqn:claim} holds, since $m<n$.
Therefore $m\divides b$.
Hence in \eqref{eqn:nab} we can replace $b$ with $b/m$.
But in this case $n=ab$, so $\gcd(n,a)=a$.
Thus $a=1$, and so $n\divides b$,
contradicting \eqref{eqn:nab}.
So there is no minimal counterexample to the original claim.
Therefore there is no counterexample at all,
and the claim holds.
\end{proof}

By definition,
\begin{equation*}
\euphi(n)=\{x\in\upomega\colon x<n\And\gcd(n,x)=1\},
\end{equation*}
and so now we have, by \eqref{eqn:Zn-gcd},
\begin{equation*}
\euphi(n)=\abs{\units{\Zmod}}.
\end{equation*}
Here $\euphi$ is the \textbf{Euler phi-function.}%%%%%
\footnote{This terminology is used by Burton \cite[pp.\ 131--2]{Burton},
who mentions also the alternative terms \emph{indicator} and \emph{totient,}
while saying, ``the functional notation $\phi(n)$, however,
is credited to Gauss.''
Burton does not say who does the crediting.
Kline \cite[p.\ 608]{MR0472307} does it, saying,
``The notation $\phi(n)$ was introduced by Gauss.''
Indeed, Article 38 of the \emph{Disquisitiones Arithmeticae} \cite[p.\ 20]{Gauss} is,
``\textsc{problem.}  \emph{To find how many positive numbers are smaller than a given positive number $A$
and relatively prime to it.}  For brevity we will designate the number of positive numbers which are relatively prime to the given number and smaller than it by the prefix $\phi$.  We seek therefore $\phi A$.''
In the next article, Gauss adjusts the definition to allow $\phi1$ to be $1$ (as we do) and not $0$.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
A few values are as follows.
\begin{equation*}
\begin{array}{c|*{12}c}
       n &1&2&3&4&5&6&7&8&9&10&11&12\\\hline
\euphi(n)&1&1&2&2&4&2&6&4&6& 4&10& 4
\end{array}
\end{equation*}
In general,
\begin{align*}
	\euphi(p)&=p-1,&\euphi(p^{n+1})&=p^{n+1}-p^n.
\end{align*}
From the table,
\begin{gather*}
	\euphi(6)=\euphi(2)\cdot\euphi(3),\\
	\euphi(10)=\euphi(2)\cdot\euphi(5),\\
	\euphi(12)=\euphi(3)\cdot\euphi(4).
\end{gather*}
We are going to prove that this is not an accident,
but $\euphi$ is \textbf{multiplicative,}
that is,%%%%%
\footnote{It may be noted that, for the letter phi, 
instead of $\phi$ I prefer $\varphi$,
as being less like the symbol $\emptyset$ for the empty set,
and as being more like what I write by hand.
For use as a permanently defined constant,
I prefer the upright form $\euphi$.
Most of the students were familiar with the phi-function,
though a few were not.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{equation*}
\gcd(x,y)=1\implies\euphi(xy)=\euphi(x)\cdot\euphi(y).
\end{equation*}

\chapter{Wednesday, February 19}

\addsec{Finite fields}

Our ultimate goal is to prove the following four theorems:
\begin{enumerate}\label{ff-thms}
\item
For every prime $p$,
for every $n$ in $\N$,
there is a field of size $p^n$.
\item
There is a unique such field (up to isomorphism), called $\F[p^n]$.
\item
The group of units of a finite field is cyclic, so
\begin{equation*}
\units{\F[p^n]}\cong\Zmod[p^n-1].
\end{equation*}
\item
$\F[p^m]\included\F[p^n]$ if and only if---what?
\end{enumerate}
We answer the last question as follows.
For every field $L$,
if $K$ is a subfield of $L$, 
then $L$ is a vector space over $K$.
In this case, suppose the \textbf{dimension} of $L$ over $K$ is $n$:
\begin{equation*}
\dim_KL=d.
\end{equation*}
What is the size of $L$?%%%%%
\footnote{One student initially proposed the answer $n\cdot\abs K$.}
We know $L$ has a \textbf{basis} $(a_i\colon i<d)$;%%%%%
\footnote{Probably in class I wrote $\{a_i\colon i<d\}$, 
but strictly this notation does not establish that the basis has size $d$.
The ensuing explanation of a basis
relies not just on the \emph{set} of basis elements,
but on a function into this set from a set of size $d$.
Here the set of size $d$ is $d$ itself (page \pageref{vN}),
which is $\{0,\dots,d-1\}$ or $\{x\in\upomega\colon x<d\}$,
and the function on it is $i\mapsto a_i$.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
this means that every element of $L$ is uniquely of the form
\begin{equation*}
\sum_{i<d}x_ia_i,
\end{equation*}
where $x_i\in K$.
Thus
\begin{equation*}
\abs L=\abs K^d.
\end{equation*}
In case $K=\F[p^m]$, we have $\abs L=p^{md}$.  Thus
\begin{equation*}
\F[p^m]\included\F[p^n]\implies m\divides n.
\end{equation*}
The converse will be true as well.
Thus the finite fields of characteristic $p$ will form a tree,
part of which is seen in Figure \ref{fig:tree}.
\begin{figure}
\begin{equation*}
\xymatrix{&&&&\\
&\F[p^4]\ar@{.}[ul]&\F[p^6]&\F[p^9]\ar@{.}[u]&\\
&&\F[p^2]\ar@{-}[ul]\ar@{-}[u]&\F[p^3]\ar@{-}[ul]\ar@{-}[u]\ar@{.}[ur]&\cdots\\
&&&\F[p]\ar@{-}[ul]\ar@{-}[u]\ar@{-}[ur]&&
}
\end{equation*}
\caption{The tree of finite fields of characteristic $p$}\label{fig:tree}
\end{figure}
In fact there will be a field $\F[p^{\ell}]$ right above $\F[p]$ in the tree
for every prime $\ell$.
Also, for all $a$ and $b$ in $\N$,
both $\F[p^a]$ and $\F[p^b]$ will be included in $\F[p^{\gcd(a,b)}]$.
Thus the union $\bigcup_{n\in\N}\F[p^n]$ 
of all of the finite fields of characteristic $p$ will be a field,
namely the \emph{algebraic closure} of $\F[p]$.
(See page \pageref{acl}.)

\addsec{Polynomial rings}

On page \pageref{F4} we saw $\F[4]=\{0,1,\alpha,\alpha+1\}$.
A better way to write this will be as $\F[2][\alpha]$ or else
\begin{equation*}
\F[2][X]/(X^2+X+1).
\end{equation*}
For any commutative ring $R$,
\begin{align*}
R[X]
&=\{\text{polynomials in $X$ over $R$}\}\\
&=\{0\}\cup\left\{\sum_{i=0}^na_iX^i\colon n\in\upomega\And a_i\in R\And a_n\neq0\right\}.
\end{align*}
If $f=\sum_{i=0}^na_iX^i$, where $a_n\neq0$, 
then we say the \textbf{degree} of $f$ is $n$,
that is,
\begin{equation*}
\deg f=n.
\end{equation*}
Also, by definition,
\begin{equation*}
\deg 0=-\infty.
\end{equation*}
Then for all $f$ and $g$ in $R[X]$,
\begin{equation*}
\deg(fg)\leq\deg f+\deg g,
\end{equation*}
with equality if $R$ is an integral domain.
In this case, $R[X]$ too must be an integral domain.

We are interested mainly in the case where $R$ is a field $K$.
If $f\in K[X]$, we define
\begin{equation*}
K[X]/(f)=\{[g]\colon g\in K[X]\},
\end{equation*}
where
\begin{equation*}
[g]=[h]\iff f\divides g-h.
\end{equation*}
In the same way, 
if $n\in\N$,
we can write
\begin{equation*}
\Z/(n)=\Zmod,
\end{equation*}
since $\Zmod=\{[x]\colon x\in\Z\}$, where
\begin{equation*}
[x]=[y]\iff n\divides x-y.
\end{equation*}
Indeed, we are going to be investigating an analogy between $\Z$ and $K[X]$.
(See the remark on page \pageref{is} about how we do not say what $[x]$ is in itself.)

In $K[X]/(f)$, if we write $[X]$ as $\alpha$
(that is, $[g]=\alpha$ when $g$ is $X$),
then for any $g$ in $K[X]$,
\begin{equation*}
[g]=g(\alpha).
\end{equation*}
Assuming $\deg f=n>0$,
by \emph{division} (see below) we have that,
for every $g$ in $K[X]$,
there is $g_1$ in $K[X]$ such that
\begin{align*}
	f&\divides g-g_1,&\deg g_1&<n.
\end{align*}
Here $g_1$ is the \textbf{remainder} after dividing $g$ by $f$.
Thus
\begin{equation*}
K[X]/(f)=\{g(\alpha)\colon g\in K[X]\And\deg g<n\}.
\end{equation*}
We may denote this set also by
\begin{equation*}
K[\alpha].
\end{equation*}
In fact it is a ring in a fairly obvious way.
For, we may assume that $f$ is \textbf{monic,} that is, $f=X^n-g$
for some $g$ having degree less than $n$.
Then multiplication in $K[\alpha]$ is as we expect,
except that $f(\alpha)=0$,
so that $\alpha^n$ is replaced with $g(\alpha)$
whenever it comes up.
We shall say more on this tomorrow.

If $f=gh$, where $0<\deg g<n$, then also $0<\deg h<n$,
and so $g(\alpha)$ and $g(\alpha)$ are nonzero,
although their product is $0$.
Thus $K[\alpha]$ has zero divisors in this case.
We say $f$ is \textbf{reducible.}

Otherwise $f$ is \textbf{irreducible,}
and then $K[\alpha]$ is an integral domain.
In this case, if $K$ is finite,\label{K-fin}
then $K[\alpha]$ is actually a field,
for the same reason that $\Zmod[p]$ was shown to be a field on page \pageref{Zp-field}:
multiplication by a nonzero element is an injective endomorphism of the additive group,
so it is also surjective.
(By a different argument, $K[\alpha]$ will be a field,
even if $K$ is infinite; see page \pageref{K[a]}.)

Thus, to prove the first of the four theorems above about finite fields,
for each prime $p$, for each $n$ in $\N$,
we shall show that there is an irreducible polynomial over $\F[p]$ of degree $n$.

For example, $X^2+X+1$ is irreducible over $\F[2]$,
because for all $a$ and $b$ in $\F[2]$,
\begin{equation*}
(X-a)(X-b)=X^2-(a+b)X+ab,
\end{equation*}
but
\begin{gather*}
	a=b\implies a+b=0,\\
	a\neq b\implies ab=0,
\end{gather*}
and so
\begin{equation*}
(X-a)(X-b)\neq X^2+X+1.
\end{equation*}
Similarly, $X^3+X+1$ is irreducible over $\F[2]$:
showing this is an \textbf{exercise.}

\addsec{The Euclidean algorithm}\label{Eucalg}

The chief analogy between $\Z$ and $K[X]$
lies in the similarity of the functions $x\mapsto\abs x$ on $\Z$
and $f\mapsto\deg f$ on $K[X]$.
Each one allows us to perform \textbf{division} effectively.\label{division}
Indeed, for all $a$ in $\Z\setminus\{0\}$, for all $b$ in $\Z$,
we have
\begin{equation*}
b=ax+y
\end{equation*}
for some unique $x$ and $y$ in $\Z$ such that also
\begin{equation*}
0\leq y<\abs a.
\end{equation*}
Similarly, for all $f$ in $K[X]\setminus\{0\}$,
for all $g$ in $K[X]$,
we have
\begin{equation*}
g=fh+r
\end{equation*}
for some unique $h$ and $r$ in $K[X]$ such that also
\begin{equation*}
\deg r<\deg f.
\end{equation*}
This means that, in both $\Z$ and $K[X]$,
the \textbf{Euclidean algorithm} can be used
to find greatest common divisors.
For example, in $\Z$, we have $\gcd(13,8)=1$, because
\begin{align*}
	13&=8+5,\\
	8&=5+3,\\
	5&=3+2,\\
	3&=2+1.
\end{align*}
Reversing the steps, we find
\begin{align*}
	1
	&=3-2\\
	&=3-(5-3)=3\cdot 2-5\\
	&=(8-5)\cdot2-5=8\cdot2-5\cdot3\\
	&=8\cdot2-(13-8)\cdot3=8\cdot5-13\cdot3.
\end{align*}
In the same way, for all $a$ and $b$ in $\Z$
that are not both $0$,
the equation
\begin{equation}\label{eqn:Bezout}
ax+by=\gcd(a,b)
\end{equation}
is soluble in $\Z$.
This result can be called \textbf{B\'ezout's Lemma.}\label{Bezout}%%%%%
\footnote{The term is used in \emph{Wikipedia,}
but I have not found clear historical justification for it.
B\'ezout's relevant concern seems to have been polynomials.
According to Morris Kline \cite[p.\ 608]{MR0472307}
(who writes B\'ezout's name without the accent),
``Bezout's idea [sketched first in 1764]
was that by multiplying $f(x,y)$ and $g(x,y)$
by suitable polynomials, $F(x)$ and $G(x)$ respectively,
he could form $R(y)=F(x)f(x,y)+G(x)g(x,y)$.''
Now, an ``idea'' is not necessarily a theorem;
but perhaps Kline made a mistake,
and $F$ and $G$ were supposed to be polynomials in $x$ \emph{and} $y$.
This way, unless $f$ and $g$ have a common factor in $x$,
the $x$ can be eliminated by performing the Euclidean algorithm in $K(y)[x]$,
then clearing fractions.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
This now gives us an easy proof\label{EL} 
of the general form of Euclid's Lemma on page \pageref{thm:EL}.
We assume $n\divides ab$ and $\gcd(n,a)=1$.
Then for some $x$ and $y$ we have
\begin{gather*}
nx+ay=1,\\
bnx+aby=b,
\end{gather*}
and so $n\divides b$
since $n\divides bnx$ and $n\divides aby$.

A reason for giving the other proof is that solubility of \eqref{eqn:Bezout}
is actually stronger than Euclid's Lemma:
there are rings in which the latter is true, 
but \eqref{eqn:Bezout} is not always soluble.
We shall see an example tomorrow (page \pageref{Z[X]}).

\addsec{The Chinese Remainder Theorem}\label{CRT}

For any $k$ and $m$ in $\N$,
there is a well-defined ring homomorphism $x\mapsto(x,x)$ 
from $\Zmod[km]$ to $\Zmod[k]\times\Zmod[m]$.
If $\gcd(k,m)=1$, this homomorphism is injective:
this was shown in Ali Nesin's class earlier today.
In this case, it follows that
\begin{equation*}
\units{\Zmod[km]}\cong\units{\Zmod[k]}\times\units{\Zmod[m]},
\end{equation*}
and so
\begin{equation*}
\euphi(km)=\euphi(k)\cdot\euphi(m).
\end{equation*}
What is the inverse of the isomorphism $x\mapsto(x,x)$?
It is given by the \textbf{Chinese Remainder Theorem.}
For all $a$ and $b$ in $\Z$,
we know that the congruences
\begin{align}\label{eqn:CRT}
	x&\equiv a\pmod k,&
	x&\equiv b\pmod m
\end{align}
are equivalent to a single congruence
\begin{equation*}
x\equiv\underline{\phantom{amc+bkd}}\pmod{km}.
\end{equation*}
Indeed, we just let $x$ be the inverse image of $(a,b)$ under $x\mapsto(x,x)$.
We expect
\begin{equation*}
x\equiv a\underline{\phantom{mc}}+b\underline{\phantom{kd}}\pmod{km}.
\end{equation*}
The multiple of $a$ should disappear \emph{modulo} $k$,
and the multiple of $b$ should disappear \emph{modulo} $m$.
Thus we expect
\begin{equation*}
x\equiv am\underline{\phantom{c}}+bk\underline{\phantom{d}}\pmod{km}.
\end{equation*}
But then the multiple of $a$ should be $a$ \emph{modulo} $k$,
and the multiple of $b$ should be $b$ \emph{modulo} $m$.
Therefore the congruences \eqref{eqn:CRT} are equivalent to
\begin{equation*}
x\equiv amc+bkd\pmod{km},
\end{equation*}
where
\begin{align*}
	mc&\equiv1\pmod k,&
	kd&\equiv1\pmod m.
\end{align*}
Such $c$ and $d$ exist since $\gcd(k,m)=1$, so that
\begin{align*}
	m&\in\units{\Zmod[k]},&
	k&\in\units{\Zmod[m]}.
\end{align*}
The inverse of $x\mapsto(x,x)$ is now
\begin{equation*}
(y,z)\mapsto mcy+kdz.
\end{equation*}
One can read the values of this inverse off a table, 
as in Figure \ref{fig:CRT-table},
\begin{figure}
\begin{equation*}
\begin{array}{r|r|rrrr|}
\multicolumn{2}{c}{}&\multicolumn{4}{c}{\Zmod[4]}\\\cline{3-6}
\multicolumn{2}{c|}{}&\phantom10&\phantom11& 2& 3\\\cline{2-6}
                 &0&0&9& 6& 3\\
         \Zmod[3]&1&4&1&10& 7\\
                 &2&8&5& 2&11\\\cline{2-6}
\end{array}
\end{equation*}
\caption{The Chinese Remainder Theorem in a table}\label{fig:CRT-table}
\end{figure}
where one can read directly that the solution to
\begin{align*}
  x&\equiv1\pmod3,&x&\equiv2\pmod4
\end{align*}
is $10$.

There is also a well-defined homomorphism
\begin{equation*}
(y,z)\mapsto my+kz
\end{equation*}
from $\Zmod[k]\times\Zmod[m]$ to $\Zmod[km]$ as \emph{groups,} 
again assuming $\gcd(k,m)=1$.
There are group endomorphisms $x\mapsto cx$ of $\Zmod[k]$
and $x\mapsto dx$ of $\Zmod[m]$.
These fit into a commutative diagram as in Figure \ref{fig:CRT}.
\begin{figure}
\centering
\psset{unit=1.8cm,nodesep=2mm,nrot=:U,arrowsize=5pt 2}
\begin{pspicture}(-2,-1.9)(2,1.9)
%\psgrid
\rput(-1,-1.73){\rnode{A}{\larger$\Zmod[k]\times\Zmod[m]$}}
\rput(2,0){\rnode{B}{\larger$\Zmod[km]$}}
\rput(-1,1.73){\rnode{C}{\larger$\Zmod[k]\times\Zmod[m]$}}
\ncline{->}AB\nbput{$(y,z)\longmapsto my+kz$}
\ncline{->}BC\nbput{$x\longmapsto(x,x)$}
\ncline{->}CA\nbput{$(y,z)\longmapsto(cy,dz)$}
\end{pspicture}
\caption{The Chinese Remainder Theorem in three isomorphisms}\label{fig:CRT}
\end{figure}
We can therefore conclude that
$(x,y)\mapsto mx+ky$ is an \emph{iso}morphism
from $\Zmod[k]\times\Zmod[m]$ as a group to $\Zmod[km]$. 

This means for example that every element of $\Zmod[12]$
is, in exactly one way, the difference of an element of $\gpgen3$
and an element of $\gpgen4$; see Figure \ref{fig:34}.
\begin{figure}
  \centering
\psset{unit=2.7cm}
  \begin{pspicture}(-1.2,-1.2)(1.2,1.2)
\pscircle(0,0)1
    \pspolygon(1;90)(1;180)(1;270)(1;0)
    \pspolygon(1;90)(1;-30)(1;-150)
\psdots(1;30)(1;60)(1;120)(1;150)(1;240)(1;300)
\uput[  90](1;  90){$0$}
\uput[  60](1;  60){$1$}
\uput[  30](1;  30){$2$}
\uput[   0](1;   0){$3$}
\uput[ -30](1; -30){$4$}
\uput[ -60](1; -60){$5$}
\uput[ -90](1; -90){$6$}
\uput[-120](1;-120){$7$}
\uput[-150](1;-150){$8$}
\uput[-180](1;-180){$9$}
\uput[ 150](1; 150){$10$}
\uput[ 120](1; 120){$11$}
  \end{pspicture}
  \caption{$\Zmod[12]=\gpgen3\times\gpgen4\cong\Zmod[4]\times\Zmod[3]$}%
\label{fig:34}
  
\end{figure}

\chapter{Thursday, January 21}

\addsec{Endomorphism rings}

We have observed (page \pageref{End}) that, for every abelian group $(V,+)$,
there is an \textbf{endomorphism ring,} namely
\begin{equation*}
(\End,+,\circ,\id).
\end{equation*}
If the abelian group $V$ is trivial, then the endomorphism ring $\End$ is trivial.
If $\End$ is not trivial,
then $V$ is a vector space over any sub-ring of $\End$ that happens to be a field.
Also $V$ is a \textbf{module} over any sub-ring of $\End$ at all.
($V$ is a \textbf{left} module over a sub-ring of $\End$,
if the elements of $\End$ are written on the left of their arguments,
or more precisely if $(f\circ g)(x)$ means $f(g(x))$ and not $g(f(x))$.)

What is $\End[\Zmod,+]$?
Suppose $\varphi\in\End[\Zmod,+]$.  If $0\leq k<n$, then
\begin{equation*}
\varphi(k)=\varphi(\underbrace{1+\dots+1}_k)
=\underbrace{\varphi(1)+\dots+\varphi(1)}_k=\varphi(1)\cdot k.
\end{equation*}
Thus $\varphi$ is determined by $\varphi(1)$.
Conversely, if $a\in\Zmod$, we can define $\varphi_a$ in $\End[\Zmod,+]$ by
\begin{equation*}
\varphi_a(x)=ax.
\end{equation*}
Thus $\varphi=\varphi_{\varphi(1)}$.
We have moreover
\begin{align*}
	\varphi_{ab}&=\varphi_a\circ\varphi_b,&
	\varphi_{a+b}&=\varphi_a+\varphi_b.
\end{align*}
Since, finally, $\varphi_1=\id[\Zmod]$,
we can conclude
\begin{equation*}
x\longmapsto\varphi_x\colon(\Zmod,+,{}\cdot{},1)\overset{\cong}{\longrightarrow}(\End[\Zmod,+],+,\circ,\id[\Zmod]).
\end{equation*}
%that $x\mapsto\varphi_x$ is an isomorphism from $(\Zmod,+,{}\cdot{},1)$ to $(\End[\Zmod,+],+,\circ,\id[\Zmod])$.
In this way, the ring structure of $\Zmod$
is determined by the group structure.

\addsec{Automorphism groups}

An \textbf{automorphism}\label{auto}
is an endomorphism that is invertible as an endomorphism.
In other words, it is an isomorphism from a structure to itself.
(The letters AU of ``auto-'' in ``automorphism'' are related to \emph{EF}
in the Turkish \emph{efendi,}
since the latter---which was taken into English as ``effendi''---%
comes from the Greek \gr{a>uj'enths},
source also of the English ``authentic'' 
and a compound of \gr{a>uto-} and \gr{<'enths}.)
The automorphisms of $(\Zmod,+)$, for example, compose a set denoted by
\begin{equation*}
\Aut.
\end{equation*}
Then by what we have just shown,
\begin{equation*}
\Aut\cong\units{\Zmod}.
\end{equation*}
We are going to show
\begin{equation*}
\Aut[{\Zmod[p]}]\cong\Zmod[p-1].
\end{equation*}
Meanwhile, what is $\Aut[{\Zmod[10]}]$?  We have
\begin{gather*}
\units{\Zmod[10]}=\{1,3,7,9\}=\{1,3,-3,-1\},\\
3^2=-1,\quad 3^3=-3,
\end{gather*}
and therefore $\units{\Zmod[10]}\cong\Zmod[4]$.
However,
\begin{equation*}
\units{\Zmod[30]}=\{1,7,11,13,-13,-11,-7,-1\}
\end{equation*}
(the number of elements is correct since
$\euphi(30)=\euphi(2)\cdot\euphi(3)\cdot\euphi(5)=2\cdot4=8$).
We find
\begin{gather*}
	7^2=-11,\quad 7^3=13,\quad 7^4=1,\\
	\gpgen7\cong\Zmod[4],\\
	\units{\Zmod[30]}=\gpgen{7,-1}\cong\Zmod[4]\times\Zmod[2].
\end{gather*}
It is also the case that $\units{\Zmod[30]}=\gpgen{7,-7}$.
However, $\gpgen7\cap\gpgen{-7}=\gpgen{-11}\cong\Zmod[2]$,
so $\units{\Zmod[30]}$ is not $\gpgen7\times\gpgen{-7}$:
this product is too big.
The main point to observe is that $\units{\Zmod[30]}$ is not cyclic.

For any group $(G,{}\cdot{})$, abelian or not,
if $G$ contains $a$ and $b$,
and $ab=ba$, and $\gpgen a\cap\gpgen b$ is trivial,
then $\gpgen{a,b}\cong\gpgen a\times\gpgen b$.
(In class I stated this only for abelian groups,
written additively; but it is not hard to prove in any case.)

As an \textbf{exercise,} write $\units{\Zmod[24]}$
as a product of finite cyclic groups.
In fact
\begin{equation*}
\units{\Zmod[24]}=\gpgen{5,7,-1}\cong\Zmod[2]{}^3.
\end{equation*}
It is a theorem (which we are not going to prove in its entirety)
that $\units{\Zmod}$ is cyclic if and only if $n$ is $2$, $4$, $p^k$,
or $2p^k$ for some $k$ in $\N$ and some odd prime $p$.

Suppose $\gcd(k,m)=1$.  
Then $k\in\units{\Zmod[m]}$ and $m\in\units{\Zmod[k]}$,
so $c$ and $d$ exist as before such that
\begin{align*}
	mc&\equiv1\pmod k,&
	kd&\equiv1\pmod m.
\end{align*}
Then $c\in\units{\Zmod[k]}$ and $d\in\units{\Zmod[m]}$,
so $(x,y)\mapsto(cx,dy)$ is indeed an automorphism of $\Zmod[k]\times\Zmod[m]$.
Then $x\mapsto(cx,dx)$ is an isomorphism from $\Zmod[km]$ to $\Zmod[k]\times\Zmod[m]$.
As an \textbf{exercise,}
verify our earlier claim that the inverse of this isomorphism is $(x,y)\mapsto mx+ky$.

If $K$ is a field and $f\in K[X]$, we defined
\begin{equation*}
K[X]/(f)=\{[g]\colon g\in K[X]\},
\end{equation*}
where
\begin{align*}
	[g]=[h]
	&\iff f\divides g-h\\
	&\iff g\equiv h\mod f.
\end{align*}
We let $\alpha=[X]$ and wrote $K[X]/(f)$ as $K[\alpha]$,
noting $g(\alpha)=[g]$.
We observed that,
if $\deg f=n>0$, then
\begin{equation*}
K[\alpha]=\{g(\alpha)\colon g\in K[X]\And\deg g<n\}.
\end{equation*}
In particular,
$K[\alpha]$ has basis $\{1,\alpha,\dots,\alpha^{n-1}\}$
as a vector space over $K$.
This is true, even if $n=0$, in the sense that the basis is empty in this case.
For, if $\deg f=0$, this means $f\in\units K$.
Moreover,
\begin{equation}\label{eqn:KKX}
\units K=\units{K[X]}.
\end{equation}
Thus $f$ is invertible, which means it divides everything in $K[X]$,
and so $[g]=[h]$ for all $g$ and $h$ in $K[X]$.
In particular, $K[\alpha]=\{0\}=\{\alpha\}$.

There is a final case to consider.  If $f=0$, then
\begin{equation*}
[g]=[h]\iff g=h.
\end{equation*}
Thus $K[X]/(0)\cong K[X]$.

\addsec{Irreducibles}

By \eqref{eqn:KKX}, for all $f$ in $K[X]$,
\begin{equation*}
\deg f=0\iff f\in\units{K[X]}.
\end{equation*}
This allows us to rewrite the definition of irreducible polynomial
in a form that makes sense for any commutative ring.
If $R$ is such a ring, an element $\pi$ is \textbf{irreducible}
if $\pi\neq0$ and $\pi\notin\units R$ and
\begin{equation*}
\pi=ab\And a\notin\units R\implies b\in\units R.
\end{equation*}
By this definition, the irreducibles of $\Z$ are just $\pm p$.
An element $\pi$ of $R$ is \textbf{prime} if $\pi\neq0$ and $\pi\notin\units R$ and
$\pi$ satisfies Euclid's Lemma, that is,
\begin{equation*}
\pi\divides ab\And\pi\ndivides a\implies\pi\ndivides b.
\end{equation*}
Then we can reformulate an earlier statement (from page \pageref{Euclem}) as follows:

\begin{Euclem}\label{Euclem2}
In $\Z$, all irreducibles are prime.
\end{Euclem}

Euclid's Lemma ensures that irreducible factorizations are unique, 
when they exist at all.  Thus if
\begin{equation*}
  p_0\cdots p_{m-1}=q_0\cdots q_{n-1},
\end{equation*}
where $p_i$ and $q_j$ are positive irreducibles in $\Z$,
then
\begin{equation*}
p_0\divides q_0\cdots q_{n-1},
\end{equation*}
and so $p_0\divides q_j$ for some $j$,
and then $p_0=q_j$.
In this way $m=n$, and for some permutation $\sigma$ of $m$,
\begin{equation*}
  p_0\cdots p_{m-1}=q_{\sigma(0)}\cdots q_{\sigma(m-1)}.
\end{equation*}
The converse of Euclid's Lemma is more generally true:

\begin{theorem}\sloppy
In every integral domain, all primes are irreducible.
\end{theorem}

\begin{proof}
Suppose $\pi$ is prime and $\pi=ab$.
Then $\pi\divides ab$, so we may assume $\pi\divides a$.
For some $c$ then, $c\pi=a$.  Hence
\begin{equation*}
bc\pi=ab=\pi,
\end{equation*}
so $bc=1$ in an integral domain.  In this case, $c$ is invertible.
\end{proof}

In integral domain whose every nonzero element 
is uniquely the product of irreducibles 
is called a \textbf{unique factorization domain} or UFD.
Here the uniqueness is up to replacement by \emph{associates};
two elements of a ring are \textbf{associates} if they divide one another,
like $a$ and $-a$ in $\Z$.
Euclid's Lemma is that $\Z$ is a UFD.
Any two elements of a UFD that are not both $0$
have a greatest common divisor.%%%%%
\footnote{In class I did not define associates
or show that greatest common divisors exist in UFDs.}
Indeed, if two elements $a$ and $b$ are respectively
\begin{align*}
	&\prod_{i<n}\pi^{a(i)},&
	&\prod_{i<n}\pi^{b(i)},
\end{align*}
where the $\pi_i$ are irreducible,
then
\begin{equation*}
\gcd(a,b)=\prod_{i<n}\pi^{\min(a(i),b(i))}.
\end{equation*}
We also proved something stronger for $\Z$ (page \pageref{Bezout}):

\begin{Bezout}\label{Bezout2}
In $\Z$, for all $a$ and $b$ that are not both $0$, the equation
\begin{equation}\label{eqn:ax+by}
ax+by=\gcd(a,b)
\end{equation}
is soluble.
\end{Bezout}

This is stronger than Euclid's Lemma,
since in $\Z[X]$,\label{Z[X]} 
all irreducibles are prime,
and in fact $\Z[X]$ is a UFD;
but $\gcd(X,2)=1$, and the equation
\begin{equation*}
2u+Xt=1
\end{equation*}
is insoluble.
A UFD in which B\'ezout's Lemma holds
is a \textbf{principal ideal domain} or PID.

As earlier (page \pageref{division}),
we can derive B\'ezout's Lemma from the following:

\begin{theorem}[division algorithm]\label{thm:div}
On $\Z$, the function $x\mapsto\abs x$ on $\Z$
has the following properties.
\begin{compactenum}
\item
Its range is well ordered.
\item
For every nonzero $a$,
for every $b$, for some $c$,
\begin{align*}
	a&\divides b-c,&\abs c&<\abs a.
\end{align*}
\end{compactenum}
\end{theorem}

Any commutative ring with the properties of $\Z$ in the theorem
is a \textbf{Euclidean domain} or ED.
Thus if $K$ is a field, then $K[X]$ is an ED.
Some PIDs are not EDs, though this is hard to prove.

As a reminder that not all EDs are PIDs,
one may wish to prove B\'ezout's Lemma for $\Z$
without relying on the Euclidean algorithm,
just as we originally proved Euclid's Lemma on page \pageref{thm:EL}.
If $a$ and $b$ are not both $0$,
one can show that the least positive element of $\{ax+by\colon(x,y)\in\Z^2\}$
must be $\gcd(a,b)$.

Nonetheless, we may understand \textbf{B\'ezout's Lemma}\label{Bezout3}
as the theorem that equation \eqref{eqn:ax+by} is always soluble
in any Euclidean domain, particularly $K[X]$ when $K$ is a field.

\chapter{Saturday, January 23}

About finite fields, we know that
\begin{compactenum}[1)]
\item
the size of each of them is a power of a prime, and
\item
if $L$ is a finite field with subfield $K$, then for some $n$ in $\N$,
\begin{equation*}
\abs L=\abs K^n.
\end{equation*}
\end{compactenum}
We are now going to show that $\units L$ is cyclic.

\addsec{Finite abelian groups}

On Thursday we looked at $\units{\Zmod}$ when $n$ is $10$ and $24$.
Also,
\begin{align*}
\units{\Zmod[28]}&=\{x\in\Z\colon-14<x\leq14\And\gcd(28,x)=1\}\\
&=\{\pm1,\pm3,\pm5,\pm9,\pm11,\pm13\},	
\end{align*}
which is confirmed by
\begin{equation*}
	\euphi(28)=\euphi(4)\cdot\euphi(7)=2\cdot6=12.
\end{equation*}
We compute
\begin{equation*}
	\begin{array}{c|*7r}
	  k&1&2& 3& 4& 5&6&\\\hline
	3^k&3&9&-1&-3&-9&1&\pmod{28}
	\end{array},
\end{equation*}
so that $\gpgen3\cong\Zmod[6]$.  Since $13^2=169$ and $6\cdot28=168$, we have
\begin{gather*}
	13^2\equiv1\pmod{28},\\
	\gpgen{13}\cap\gpgen 3=\{1\},\\
	\gpgen{13,3}=\gpgen{13}\times\gpgen3,\\
	\units{\Zmod[28]}=\gpgen{13}\times\gpgen{3}\cong\Zmod[2]\times\Zmod[6].
\end{gather*}
We use here the more general result that, 
if $(G,\cdot)$ is an arbitrary group with elements $a$ and $b$ such that $ab=ba$,
then there is a well-defined homomorphism $(x,y)\mapsto xy$
or $(a^i,b^j)\mapsto a^ib^j$ from $\gpgen a\times\gpgen b$ to $G$
(\textbf{exercise}).
If, further, $\gpgen a\cap\gpgen b=\{1\}$,
then the homomorphism is injective,
since if $a^ib^j=1$, then $a^i=b^{-j}$,
so both of these are in $\gpgen a\cap\gpgen b$,
and therefore they are $1$.
In this case
\begin{equation*}
\gpgen a\times\gpgen b\cong\gpgen{a,b}.
\end{equation*}
We can write this as an equation if it is understood that $a$ and $b$ indeed belong to the same group,
so that $\gpgen a\times\gpgen b$ is the so-called \textbf{internal direct product.}%%%%%
\footnote{I did not use this terminology in class,
but I stated the theorem because of a question from a student.}

We know $\Zmod[6]\cong\Zmod[2]\times\Zmod[3]$, 
and in fact $\Zmod[6]$ is the internal direct product $\gpgen3\times\gpgen2$.
Thus
\begin{gather*}
	\units{\Zmod[28]}\cong\Zmod[2]\times\Zmod[2]\times\Zmod[3],\\
\units{\Zmod[28]}\cong\gpgen{13}\times\gpgen{3^3}\times\gpgen{3^2}\cong\gpgen{13}\times\gpgen{-1}\times\gpgen9.
\end{gather*}

\begin{Cfag}\label{class}\sloppy
Every finite abelian group is isomorphic to a product
\begin{equation*}
\Zmod[k(0)]\times\dots\times\Zmod[k(n-1)]
\end{equation*}
for some $n$ in $\upomega$, for some $k(i)$ in $\N\setminus\{1\}$ such that
\begin{equation*}
k(0)\divides k(1)\And\dots\And k(n-2)\divides k(n-1).
\end{equation*}
(If $n=0$, the product is the trivial product,
which is the trivial group.)
By the Chinese Remainder Theorem,
every finite abelian group is therefore isomorphic to a product
\begin{equation*}
\Zmod[q(0)]\times\dots\times\Zmod[q(m-1)]
\end{equation*}
for some $m$ in $\upomega$, for some powers $q(j)$ of primes.
The latter factorization is unique, and therefore the former is unique.
\end{Cfag}

\begin{proof}
We shall prove only the existence of the former factorization,
because that is all that we shall need;
the rest is an \textbf{exercise.}
Every finite abelian group $(G,+)$ is $\gpgen{a_0,\dots,a_{n-1}}$,
that is,
\begin{equation*}
\{a_0x_0+\dots+a_{n-1}x_{n-1}\colon\vec x\in\Z^n\},
\end{equation*}
for some $a_i$ in $G$.
Here possibly $G=\{a_0,\dots,a_{n-1}\}$ as a set;
but instead we could require $n$ to be minimal such that 
$G=\gpgen{a_0,\dots,a_{n-1}}$ for some $a_i$ in $G$.
In any case, there is an \textbf{epimorphism}
(a surjective homomorphism)
\begin{equation*}
\vec x\mapsto\sum_{i<n}a_ix_i
\end{equation*}
from $\Z^n$ onto $G$.  
Let $N$ be the kernel of this epimorphism;
then by the (first) \textbf{isomorphism theorem}
(learned in Ali Nesin's class),
\begin{equation*}
G\cong\Z^n/N.
\end{equation*}
We can think of the elements of $\Z^n$ as $1\times n$ matrices,
which are \textbf{row vectors.}
Then every \emph{automorphism} (invertible endomorphism, as on page \pageref{auto}) 
of $\Z^n$ can be understood as $\vec x\mapsto\vec x\cdot Q$
for some $n\times n$ invertible matrix $Q$ over $\Z$.
The set of such matrices
(or else the automorphisms that they represent) 
is denoted by
\begin{equation*}
\GL,
\end{equation*}
where GL stands for ``general linear [group].''
Then the function
\begin{equation*}
\vec x\cdot Q\mapsto\sum_{i<n}a_ix_i,
\end{equation*}
namely $\vec x\mapsto\vec x\cdot Q\inv$ followed by $\vec x\mapsto\sum_{i<n}a_ix_i$,
is an epimorphism from $\Z^n$ onto $G$ with kernel
\begin{equation*}
\{\vec x\cdot Q\colon\vec x\in N\}.
\end{equation*}
Thus $G\cong\Z^n/\{\vec x\cdot Q\colon\vec x\in N\}$.
We are going to find $Q$ so that $\{\vec x\cdot Q\colon\vec x\in N\}$
is generated by the rows of an $n\times n$ diagonal matrix
as in Figure \ref{fig:diag};
\begin{figure}
\begin{equation*}
\begin{pmatrix}
   k(0)&    0 & \dots&  0   \\
     0 &  k(1)&\ddots&\vdots\\
\vdots &\ddots&\ddots&  0   \\
	   0 & \dots&    0 &k(n-1)
	\end{pmatrix}
\end{equation*}
\caption{A diagonal matrix}\label{fig:diag}
\end{figure}
we can write the matrix also as
\begin{equation*}
\diag{k(0),\dots,k(n-1)}.
\end{equation*}
We shall be able to require further that
\begin{equation*}
k(0)\divides\dots\divides k(n-1);
\end{equation*}
and in this case $G$ will be as desired.
(Some of the $k(i)$ at the end might be $0$.)

The first step is to show that any subgroup of $\Z^n$
is generated by $n$ elements.
Suppose $s\geq n$, and some subgroup of $\Z^n$
is generated by $s$ elements.
Let those $s$ elements by the rows of an $s\times n$ matrix $A$ over $\Z$.
Then we can write the group as
\begin{equation*}
\gpgen A.
\end{equation*}
For all $P$ in $\GL[s]$,
the matrix product $PA$ is obtained from $A$
by a sequence of \textbf{elementary row operations,}
namely
\begin{compactenum}[1)]
	\item
	adding a multiple of one row to another,
	\item
	interchanging two rows,
	\item
	multiplying a row by an element of $\units{\Z}$, which is $\{\pm1\}$.
\end{compactenum}
Thus
\begin{equation*}
\gpgen{PA}=\gpgen A.
\end{equation*}
For some $P$ in $\GL[s]$,
$PA$ will be an upper triangular matrix,
having the form in Figure \ref{fig:UT}.
\begin{figure}
\begin{equation*}
\begin{pmatrix}
  a_0 &    * & \dots&   *   \\
    0 &   a_1&\ddots& \vdots\\
\vdots&\ddots&\ddots&   *   \\
	  0 & \dots&    0 &a_{n-1}\\\hline
	  0 &   \hdotsfor2&   0   \\
\vdots&      &      &\vdots\\
	  0 &   \hdotsfor2&   0
	\end{pmatrix}
\end{equation*}
\caption{An upper triangular matrix}\label{fig:UT}
\end{figure}
For example, by elementary row operations, we obtain
\begin{multline*}
\begin{pmatrix}
8&14\\
4&13\\
6& 9
\end{pmatrix},
\begin{pmatrix}
0&-12\\
4&13\\
2&-4
\end{pmatrix},
\begin{pmatrix}
0&-12\\
0&21\\
2&-4
\end{pmatrix},\\
\begin{pmatrix}
0&-12\\
0& -3\\
2& -4
\end{pmatrix},
\begin{pmatrix}
0& 0\\
0&-3\\
2&-4
\end{pmatrix},
\begin{pmatrix}
2&-4\\
0&-3\\
0& 0
\end{pmatrix},
\begin{pmatrix}
2& 2\\
0&3\\
0& 0
\end{pmatrix},
\end{multline*}
and so
\begin{equation*}
\gpgen{(8,14),(4,13),(6,9)}=\gpgen{(2,2),(0,3)}.
\end{equation*}
The general procedure is the following.
\begin{compactenum}[1)]\sloppy
\item
If the first column of $A$ is $(a_0\;\cdots\;a_{n-1})^T$
(that is, the column vector that is the transpose of the row vector 
$(a_0\;\dots\;a_{n-1})$),
then, using the Euclidean algorithm,
reduce this to
\begin{equation*}
(\gcd(a_0,\dots,a_{n-1})\;0\;\cdots\;0)^T.
\end{equation*}
\item
If the second column of the resulting matrix is $(b_0\;\cdots\;b_{n-1})^T$,
reduce this to
\begin{equation*}
(b_0\;\gcd(b_1,\dots,b_{n-1})\;0\;\cdots\;0)^T.
\end{equation*}
\item
Treat the third column similarly, and so on.
\end{compactenum}
This shows that any subgroup of $\Z^n$ generated by $s$ elements
is generated by $n$ elements.
The same goes for subgroups generated by infinitely many elements,
since the foregoing procedure applies to $\infty\times n$ matrices.

In the second and final step,
we may assume $N$ is generated by the rows of an $n\times n$ matrix $A$.
If $P$ and $Q$ are in $\GL$, we say that $PAQ$ is \textbf{similar} to $A$.
We want to show that $A$ is similar to a diagonal matrix as above.
Let $\ell(0)$ be the least positive entry of any matrix similar to $A$.
Then
\begin{equation*}
A\sim
\left(
\begin{array}{c|c}
\ell(0)&*\\\hline
*&*
\end{array}
\right)\sim
\left(
\begin{array}{c|c}
\ell(0)&\vec0\\\hline
\vec0&A_1
\end{array}
\right)
\end{equation*}
since otherwise the first row or column
can be given a positive entry that is less than $\ell(0)$.
Now let $\ell(1)$ be the least positive entry of any such matrix $A_1$.
Then
\begin{equation*}
A\sim
\left(
\begin{array}{cc|c}
\ell(0)&     0 &\vec0\\
     0 &\ell(1)&\vec0\\\hline
  \vec0 &  \vec0 & A_2
\end{array}
\right),
\end{equation*}
and so on.
Thus
\begin{equation*}
A\sim\diag{\ell(0),\ell(1),\dots,\ell(n-1)}.
\end{equation*}
Finally we obtain $A$ as desired by observing
\begin{equation*}
\begin{pmatrix}
a&0\\
0&b
\end{pmatrix}\sim
\begin{pmatrix}
a&b\\
0&b
\end{pmatrix}
\sim
\begin{pmatrix}
\gcd(a,b)&0\\
bx&by
\end{pmatrix}
\sim
\begin{pmatrix}
\gcd(a,b)&0\\
0&by
\end{pmatrix},
\end{equation*}
and $\gcd(a,b)\divides by$.
\end{proof}

\addsec{Units of finite fields}

\begin{theorem}
The group of units of every finite field is cyclic.
\end{theorem}

\begin{proof}
Let $K$ be a finite field.
Then by the classification of finite abelian groups, 
$\units K$ is isomorphic to a product
\begin{equation*}
\Zmod[k(0)]\times\dots\times\Zmod[k(n-1)]
\end{equation*}
for some $n$ in $\upomega$, for some $k(i)$ in $\N\setminus\{1\}$ such that
\begin{equation*}
k(0)\divides\dots\divides k(n-1).
\end{equation*}
If $n=0$, the product is the trivial group, which is cyclic,
and so we are done.
(The trivial group is the group of units of $\F[2]$.)   
We may henceforth assume $n>0$.
For every $(x_0,\dots,x_{n-1})$ 
in $\Zmod[k(0)]\times\dots\times\Zmod[k(n-1)]$,
writing $k(n-1)$ as $k$, we have
\begin{equation*}
k\cdot(x_0,\dots,x_{n-1})=(kx_0,\dots,kx_{n-1})=(0,\dots,0)=0,
\end{equation*}
since $k(i)\divides k$.
Therefore, for every $a$ in $\units K$ we have
\begin{equation*}
a^k=1.
\end{equation*}
Thus every element of $\units K$ is a zero of the polynomial
\begin{equation*}
X^k-1.
\end{equation*}

Over any field,
for every $d$ in $\upomega$,
every polynomial of degree $d$ has at most $d$ zeroes.
We prove this by induction.
A polynomial of degree $0$ is a nonzero constant,
so it has $0$ zeroes.
Suppose $\deg f=d+1$ and $f(\alpha)=0$.
By division,
\begin{equation*}
f=(X-\alpha)\cdot g+h,
\end{equation*}
where $g$ is a polynomial of degree $d$, and $\deg h<1$,
so $h$ is constant.
But then
\begin{equation*}
0=f(\alpha)=0\cdot g(\alpha)+h=h.
\end{equation*}
Thus $f=(X-\alpha)\cdot g$.
Suppose $\beta$ is a zero of $f$ different from $\alpha$.
Then
\begin{equation*}
(\beta-\alpha)\cdot g(\beta)=0,
\end{equation*}
so $g(\beta)=0$ since a field is an integral domain.
So the zeroes of $f$, other than $\alpha$,
are zeroes of $g$.
If $g$ has at most $d$ zeroes,
then $f$ must have at most $d+1$ zeroes.
This completes the induction.

We now have
\begin{gather*}
\abs{\units K}\leq k=k(n-1)\leq k(0)\cdots k(n-1)=\abs{\units K},\\
	k(n-1)=k(0)\cdots k(n-1),
\end{gather*}
and so $n=1$ (since we assume $k(0)>1$).  Thus
\begin{equation*}
\units K\cong\Zmod[k]=\Zmod[\abs K-1].\qedhere
\end{equation*}
\end{proof}

\addsec{Existence of finite fields}

If $K$ is a finite field of size $p^n$,
then we now know that the elements of $\units K$
are precisely the zeroes of the polynomial $X^{p^n-1}-1$
in any field that includes $K$.
Hence the elements of $K$ are precisely the zeroes of the polynomial
\begin{equation*}
X^{p^n}-X
\end{equation*}
in any field that includes $K$.
This means the elements of $K$ are the fixed points of the function
$x\mapsto x^{p^n}$.
Now, in $\Z$ we have
\begin{equation*}
(a+b)^{p^n}\equiv a^{p^n}+b^{p^n}\pmod p,
\end{equation*}
since, for example,
\begin{multline*}
(a+b)^p=a^p+pa^{p-1}b+\binom p2a^{p-2}b^2+\dots+pab^{p-1}+b^p\\
\equiv a^p+b^p\pmod p;
\end{multline*}
the general result is left as an \textbf{exercise.}
In a field of characteristic $p$ then, we have
\begin{align*}
(x+y)^{p^n}&=x^{p^n}+y^{p^n},&
(xy)^{p^n}&=x^{p^n}\cdot y^{p^n},&
1^{p^n}&=1.	
\end{align*}
Thus $x\mapsto x^{p^n}$ is an endomorphism of the field.

For any endomorphism $\varphi$ of a field,
the set $\{x\colon\varphi(x)=x\}$ of fixed points
is a subfield: this too is an \textbf{exercise.}
Thus, to show that there is finite field of size $p^n$,
we need only show that there is a field of characteristic $p$
that contains $p^n$ zeroes of $X^{p^n}-X$;
these zeroes will then constitute the desired subfield.
An example of a field containing $p^n$ zeroes of $X^{p^n}-X$ 
is the \emph{algebraic closure} of $\F$.

A field is \textbf{algebraically closed}
if the only irreducible polynomials over it are \textbf{linear}
(that is, of degree $1$).
An example is $\C$, though we are not going to prove this;
the result does follow from the fact that $\R$ is \textbf{real closed,}
that is, every polynomial function that takes both positive and negative values
has a zero.

We have seen that if $f$ is irreducible over a field $K$,
then $f$ has a zero in $K[X]/(f)$,
namely the element called $[X]$.
We showed on page \pageref{K-fin} 
that $K[X]/(f)$ is a field if $K$ is finite.\label{K[a]}
In fact it is a field in any case.
For if $f\ndivides g$,
then, since $f$ is irreducible and therefore prime,
we have $\gcd(f,g)=1$, and so, by B\'ezout's Lemma
(in the sense of page \pageref{Bezout3}),
or by the Euclidean algorithm,
we can find polynomials $h$ and $k$ such that
\begin{equation*}
fh+gk=1.
\end{equation*}
In $K[X]/(f)$ then, $[g][k]=1$, so $[g]$ is invertible.
We could have proved similarly that $\F$ is a field.

Starting with $\F$, we can obtain a \textbf{chain} or \textbf{tower}
\begin{equation*}
K_0\included K_1\included K_2\included\cdots
\end{equation*}
of fields,
where $K_0=\F$ and for each $n$ in $\upomega$,
for some irreducible $f_n$ over $K_n$,
\begin{equation*}
K_{n+1}=K_n[X]/(f_n).
\end{equation*}
Then $\bigcup_{n\in\upomega}K_n$ is a field,
and if we have chosen the $f_n$ properly,
that field will be algebraically closed.
It will then be the algebraic closure
\begin{equation*}
\alg{\F}
\end{equation*}
of $\F$,
in the sense described below.
Inside this field, we can find each $\F[p^n]$, as above.

Actually we have to show also%%%%%
\footnote{I did not do this in class.}
%%%%%%%%%%%%%%%%%%%%%%%%%%
that the polynomial $X^{p^n}-X$
has $p^n$ \emph{distinct} zeroes in $\alg{\F}$.
For example,
the polynomial $X^{p^n}-1$ has only one zero
in a field of characteristic $p$,
since there the polynomial factorizes as $(X-1)^{p^n}$.
If $X^{p^n}-X$ has fewer than $p^n$ distinct zeroes in $\alg{\F}$,
then for one of those zeroes, say $\alpha$, 
for some polynomial $g$ of degree $p^n-2$,
we must have
\begin{equation*}
X^{p^n}-X=(X-\alpha)^2\cdot g.
\end{equation*}
In this case, by \emph{formal differentiation,}
since we are in a field of characteristic $p$,
\begin{equation}\label{eqn:'}
\begin{aligned}
	-1
	&=2(X-\alpha)\cdot g+(X-\alpha)^2\cdot g'\\
	&=(X-\alpha)\cdot\bigr(2g+(X-\alpha)\cdot g'\bigr),
\end{aligned}
\end{equation}
which is absurd.
Here \textbf{formal differentiation} over a field $K$
is the endomorphism $f\mapsto f'$
of $K[X]$ as a vector space over $K$ given by
\begin{equation*}
\left(\sum_{i=0}^na_iX^i\right)'=\sum_{i=1}^n ia_iX^{i-1}.
\end{equation*}
One shows that
\begin{equation}\label{eqn:L}
(fg)'=f'g+fg',
\end{equation}
which is what we used to establish \eqref{eqn:'}.
One can prove \eqref{eqn:L}
by induction on $\deg g$,
or directly from the equation
\begin{equation*}
\left(\sum_ia_iX^i\right)\cdot\sum_jb_jX^j
=\sum_k\left(\sum_{i+j=k}a_ib_j\right)X^k
\end{equation*}

\addsec{Uniqueness of finite fields}

We establish the uniqueness of $\F[p^n]$ as follows.
If $f$ is irreducible over a field $K$,
but has a zero $\alpha$ in some larger field $L$,
we let
\begin{equation*}
K[\alpha]
\end{equation*}
denote the smallest sub-ring of $L$ that includes $K\cup\{\alpha\}$.
In fact this sub-ring will be $\{g(\alpha)\colon g\in K[X]\}$,
which is the image of the ring $K[X]$ under the homomorphism $g\mapsto g(\alpha)$.
Also the kernel of this homomorphism is $(f)$, that is, $\{g\in K[X]\colon f\divides g\}$.
Thus, by the isomorphism theorem,
\begin{equation*}
K[X]/(f)\cong K[\alpha].
\end{equation*}
Hence $K[\alpha]$ is a field.
Using this, one shows that the algebraically closed field $\bigcup_{n\in\upomega}K_n$
constructed above \textbf{embeds} in every algebraically closed field that includes $\F$.
(An embedding is a \textbf{mono\-morphism,}
that is, an injective homomorphism.)
This is the sense in which the field $\bigcup_{n\in\upomega}K_n$ 
is the \textbf{algebraic closure}\label{acl} of $\F$.
There is only one algebraic closure, up to isomorphism, called $\alg{\F}$ as above;
its uniqueness proves the uniqueness of each $\F[p^n]$.

\chapter{Sunday, January 24}

\addsec{Endomorphisms of groups and vector spaces}

We said yesterday that the automorphisms of $\Z^n$ are the functions
\begin{equation*}
\vec x\mapsto\vec x\cdot Q,
\end{equation*}
where $\vec x$ is an element of $\Z^n$ considered as a row vector,
and $Q$ is an invertible $n\times n$ matrix, that is,
\begin{equation*}
Q\in\GL.
\end{equation*}
Why is this?  If $i<n$, let
\begin{equation*}
\vec e^i=(e^i_0,\dots,e^i_{n-1}),\quad\text{ where }\quad
e^i_j=\begin{cases}
	1,&\text{ if $i=j$},\\
	0,&\text{ if $i\neq j$}.
\end{cases}
\end{equation*}
Then
\begin{equation*}
\vec x=\sum_{i<n}x_i\vec e^i
\end{equation*}
for all $\vec x$ in $\Z^n$.  Thus if $\varphi$ in $\End[\Z^n]$,
then
\begin{equation*}
\varphi(\vec x)
=\sum_{i<n}\varphi(x_i\vec e^i)
=\sum_{i<n}x_i\cdot\varphi(\vec e^i)
=\vec x\cdot
\begin{pmatrix}
\varphi(\vec e^0)\\\hline
\vdots\\\hline
\varphi(\vec e^{n-1})
\end{pmatrix}.
\end{equation*}
If $\varphi\in\Aut[\Z^n]$, 
this means the $n\times n$ matrix whose rows are the $\varphi(\vec e^i)$ must be invertible.

Here we have been considering $\Z^n$ as an abelian group, not a ring:
as $(\Z^n,+)$, not $(\Z^n,+,{}\cdot{},1)$.

We know that $\R^n$ is a vector space over $\R$,
which means there is a homomorphism from $\R$ to $\End[\R^n,+]$.
As a vector space over $\R$, $\R^n$ has the endomorphism ring
\begin{equation*}
\Mat[\R],
\end{equation*}
namely the ring of $n\times n$ matrices over $\R$,
by the same reasoning as for $\Z^n$.
However, as a group, $\R^n$ has a larger endomorphism ring,
unless $n=0$.
For, as a group, $\R$ is a vector space over $\Q$,
in the sense that
\begin{equation*}
\frac km\cdot x=y\iff k\cdot x=m\cdot y
\end{equation*}
for all $x$ and $y$ in $\R$, all $k$ in $\Z$, and all $m$ in $\N$.
But $\R$ then has a basis over $\Q$
(by the Axiom of Choice, as discussed in Ali Nesin's class),
in fact an uncountable basis of size $\abs{\R}$;
and then $\End[\R,+,\Q]$ will have size $\abs{2^{\R}}$.

\addsec{The characteristic polynomial of a matrix}

$\R$ embeds in $\Mat[\R]$ under
\begin{equation*}
x\mapsto x\cdot\Id,
\end{equation*}
where $\Id$ is the $n\times n$ identity matrix, that is,
\begin{equation*}
\Id=\begin{pmatrix}
\vec e^0\\\hline
\vdots\\\hline
\vec e^{n-1}
\end{pmatrix}
=\begin{pmatrix}
     1 &    0 & \dots&  0   \\
     0 &\ddots&\ddots&\vdots\\
\vdots &\ddots&\ddots&  0   \\
	   0 & \dots&    0 &  1
	\end{pmatrix}.
\end{equation*}
The same is true when $\R$ is replaced with an arbitrary field $K$.
Let $A\in\Mat$.
It may be that for some nonzero $\vec v$ in $K^n$,
for some $\lambda$ in $K$,
\begin{equation*}
\vec v\cdot A=\lambda\cdot\vec v.
\end{equation*}
This means
\begin{equation*}
\vec0=\vec v\cdot(\lambda\cdot\Id-A).
\end{equation*}
Since we assume $\vec v\neq\vec0$,
the matrix $\lambda\cdot\Id-A$ must not be invertible,
and so we must have $\det(\lambda\cdot\Id-A)=0$.
The polynomial
\begin{equation*}
\det(X\cdot\Id-A)
\end{equation*}
in $X$ of degree $n$ over $K$ is the \textbf{characteristic polynomial} of $A$.
Its zeroes are the \textbf{characteristic values} or \textbf{eigenvalues} of $A$.
If $\lambda$ is an eigenvalue of $A$,
then the solution space of the equation
\begin{equation*}
\vec0=\vec x\cdot(\lambda\cdot\Id-A)
\end{equation*}
is the \textbf{eigenspace} associated with $\lambda$,
and its nonzero elements are the \textbf{eigenvectors}
(or \textbf{characteristic vectors}) associated with $\lambda$.

\addsec{Diagonalizable matrices}

For example, if
\begin{equation*}
A=\begin{pmatrix}-1&-5\\-5&-1\end{pmatrix},
\end{equation*}
then
\begin{multline*}
\det(X\cdot\Id[2]-A)
=\det\begin{pmatrix}X+1&5\\5&X+1\end{pmatrix}\\
=(X+1)^2-25=X^2+2X-24=(X+6)(X-4),
\end{multline*}
so the eigenvalues of $A$ are $-6$ and $4$.
The corresponding eigen\-spaces are as follows.
\begin{compactitem}
\item
$\lambda=-6$:
\begin{align*}
	\vec0=\vec x\cdot\begin{pmatrix}-5&5\\5&-5\end{pmatrix}
	&\iff	\vec0=\vec x\cdot\begin{pmatrix}1&0\\-1&0\end{pmatrix}\\
	&\iff(0,0)=(x_0-x_1,0)\\
	&\iff x_0=x_1\\
	&\iff\vec x=t\cdot(1,1)\text{ for some $t$ in $K$.}
\end{align*}
\item
$\lambda=4$:
\begin{align*}
	\vec0=\vec x\cdot\begin{pmatrix}5&5\\5&5\end{pmatrix}
	&\iff	\vec0=\vec x\cdot\begin{pmatrix}1&0\\1&0\end{pmatrix}\\
	&\iff x_0=-x_1\\
	&\iff\vec x=t\cdot(1,-1)\text{ for some $t$ in $K$.}
\end{align*}
\end{compactitem}
Letting the eigenvectors $(1,1)$ and $(1,-1)$ be the rows of a matrix,
we obtain
\begin{gather*}
	\begin{pmatrix}1&1\\1&-1\end{pmatrix}\cdot A
=	\begin{pmatrix}-6&-6\\4&-4\end{pmatrix}
=	\begin{pmatrix}-6&0\\0&4\end{pmatrix}
\cdot	\begin{pmatrix}1&1\\1&-1\end{pmatrix},\\
\begin{pmatrix}-6&0\\0&4\end{pmatrix}
=\begin{pmatrix}1&1\\1&-1\end{pmatrix}\cdot A\cdot\begin{pmatrix}1&1\\1&-1\end{pmatrix}\inv.
\end{gather*}
In general, if $A$ is an $n\times n$ matrix with $n$ distinct eigenvalues
$\lambda_0$, \dots, $\lambda_{n-1}$,
and $\vec v_0$, \dots, $\vec v_{n-1}$ are corresponding eigenvectors,
then
\begin{equation*}
PA=\diag{\lambda_0,\dots,\lambda_{n-1}}\cdot P,
\end{equation*}
where
\begin{equation*}
P=	\begin{pmatrix}
\vec v_0\\\hline
\vdots\\\hline
\vec v_{n-1}\end{pmatrix}.
\end{equation*}
We can conclude that $PAP\inv$ is a diagonal matrix
whose diagonal entries are the eigenvalues of $A$,
provided $A$ is invertible.
It is invertible by the following.

\begin{theorem}
Eigenvectors corresponding to distinct eigenvalues of any matrix are linearly independent.
\end{theorem}

\begin{proof}
We prove the claim by induction on the number of eigenvectors.
The empty set of eigenvectors is trivially linearly independent.
Suppose $\vec v_i$ is the eigenvector corresponding to $\lambda_i$,
and
\begin{equation}\label{eqn:eig}
\sum_{i<n+1}x^i\vec v_i=\vec0.
\end{equation}
Multiplying by the matrix gives
\begin{equation*}
\sum_{i<n+1}\lambda_ix^i\vec v_i=\vec0.
\end{equation*}
But just multiplying by $\lambda_n$ gives
\begin{equation*}
\sum_{i<n+1}\lambda_nx^i\vec v_i=\vec0.
\end{equation*}
By subtraction, one term is cancelled, and we have
\begin{equation*}
\sum_{i<n}(\lambda_n-\lambda_i)x^i\vec v_i=\vec0.
\end{equation*}
If $n$ eigenvectors corresponding to distinct eigenvalues must be linearly independent,
then we can conclude
$(\lambda_n-\lambda_i)x^i=0$ when $i<n$,
so $x^i=0$ when $i<n$,
and then also $x^n=0$ by \eqref{eqn:eig};
so $n+1$ eigenvectors corresponding to distinct eigenvalues must be linearly independent.
\end{proof}

\addsec{A nondiagonalizable matrix}

Possibly an $n\times n$ matrix does not have $n$ distinct eigenvectors.
Still, if the sum of the dimensions of the eigenspaces is $n$,
$A$ will be \textbf{diagonalizable,}
just as in the case where there are $n$ distinct eigenvectors.

However, not every square matrix is diagonalizable,
even over an algebraically closed field.
Suppose for example
\begin{equation*}
A=\begin{pmatrix}8&4\\-9&-4\end{pmatrix}.
\end{equation*}
Then
\begin{multline*}
\det(X\cdot\Id[2]-A)
=\det\begin{pmatrix}X-8&-4\\9&X+4\end{pmatrix}\\
=(X-8)(X+4)+36
=X^2-4X+4
=(X-2)^2,
\end{multline*}
so $A$ has the unique eigenvalue $2$.
Moreover,
\begin{align*}
	\vec0=\vec x\cdot(2\Id[2]-A)
	&\iff\vec0=\vec x\cdot\begin{pmatrix}-6&-4\\9&6\end{pmatrix}\\
	&\iff\vec0=\vec x\cdot\begin{pmatrix}2&2\\-3&-3\end{pmatrix}\\
	&\iff\vec0=\vec x\cdot\begin{pmatrix}2&0\\-3&0\end{pmatrix}\\
	&\iff2x_0=3x_1\\
	&\iff\vec x=t\cdot(3,2)\text{ for some $t$ in $K$,}
\end{align*}
so the unique eigenspace is one-dimensional,
spanned by $(3,2)$.
But then
\begin{align*}
	&\phantom{{}\iff{}}(3,2)=\vec x\cdot(2\Id[2]-A)\\
	&\iff(3,2)=\vec x\cdot\begin{pmatrix}-6&-4\\9&6\end{pmatrix}\\
	&\iff(-1,-1)=\vec x\cdot\begin{pmatrix}2&2\\-3&-3\end{pmatrix}\\
	&\iff(-1,0)=\vec x\cdot\begin{pmatrix}2&0\\-3&0\end{pmatrix}\\
	&\iff-1=2x_0-3x_1\\
	&\iff\vec x=t\cdot(3,2)-(\textstyle\frac12,0)\text{ for some $t$ in $K$.}
\end{align*}
One solution here is $(1,1)$.
Call this $\vec c$, and let $(3,2)=\vec b$.
Then
\begin{align*}
	\vec0&=2\vec b-\vec b\cdot A,&
	\vec b&=2\vec c-\vec c\cdot A,
\end{align*}
that is,
\begin{align*}
	\vec b\cdot A&=2\vec b,&
	\vec c\cdot A&=2\vec c-\vec b,
\end{align*}
and so
\begin{gather*}
\begin{pmatrix}\vec c\\\hline\vec b\end{pmatrix}\cdot A
=\begin{pmatrix}2\vec c-\vec b\\\hline2\vec b\end{pmatrix}
=\begin{pmatrix}2&-1\\0&2\end{pmatrix}\cdot\begin{pmatrix}\vec c\\\hline\vec b\end{pmatrix},\\
\begin{pmatrix}\vec c\\\hline\vec b\end{pmatrix}\cdot A\cdot\begin{pmatrix}\vec c\\\hline\vec b\end{pmatrix}\inv
=\begin{pmatrix}2&-1\\0&2\end{pmatrix}.
\end{gather*}
We also have
\begin{equation*}
\begin{pmatrix}-\vec c\\\hline\vec b\end{pmatrix}\cdot A\cdot\begin{pmatrix}-\vec c\\\hline\vec b\end{pmatrix}\inv
=\begin{pmatrix}2&1\\0&2\end{pmatrix}.
\end{equation*}
The general claim, which we are not proving,
is that, for every square matrix $A$ over an algebraically closed field,
for some invertible $P$,
\begin{equation*}
PAP\inv=\diag{B_0,\dots,B_{k-1}},
\end{equation*}
where each $B_i$ is not necessarily a number,
but a square matrix, of the form
\begin{equation*}
\begin{pmatrix}
\lambda&      1&     0& \dots&      0\\
      0&\lambda&     1&\ddots& \vdots\\
 \vdots& \ddots&\ddots&\ddots&      0\\
 \vdots&       &\ddots&\ddots&      1\\
      0&    \hdotsfor2&     0&\lambda    
			\end{pmatrix},
\end{equation*}
where $\lambda$ is an eigenvalue of $A$.
The matrix $\diag{B_0,\dots,B_{k-1}}$ 
is the \textbf{Jordan normal form} of $A$.
Note that the same eigenvalue 
may appear in more than one of the matrices $B_i$.

\appendix

\chapter{Jordan Normal Form}
We are going to show that every square matrix over an algebraically closed field
is ``almost'' diagonalizable,
in the sense of having the Jordan normal form described above.
We shall show moreover that the procedure used above 
for finding a Jordan normal form works generally.
The presentation is based mainly on that of Lang \cite{Lang-LA}.

\addsec{Polynomial functions of matrices}

Although $K$ is a field,
the ring $\Mat$ is not commutative.
However, it has commutative sub-rings.
Indeed, for every $A$ in $\Mat$,
there is smallest sub-ring of $\Mat$ that contains $A$.
We may denote this sub-ring by
\begin{equation*}
K[A].
\end{equation*}
This ring is commutative.
As a vector space over $K$,
$K[A]$ is spanned by $\Id$ and the positive powers of $A$.
Indeed, for any $f$ in $K[X]$,
for any $A$ in $\Mat$,
there is a well-defined matrix $f(A)$ in $\Mat$.
In particular, if $f=\sum_{i=0}^nb_iX^i$, then
\begin{equation*}
f(A)=\sum_{i=0}^nb_iA^i.
\end{equation*}
Then
\begin{equation*}
K[A]=\bigl\{f(A)\colon f\in K[X]\bigr\}.
\end{equation*}
If $f(A)$ is the zero matrix,
we may say $A$ is a \textbf{zero} of $f$.
Note however that $K[A]$ may have zero divisors.
Indeed, $A$ itself may be a zero divisor, since for example
\begin{equation*}
\begin{pmatrix}
0&1\\0&0
\end{pmatrix}
^2=0
\end{equation*}
(where the last $0$ is the zero matrix).

In proving that the group of units of every finite field is cyclic,
we showed that a polynomial has no more zeros than its degree;
but these zeroes belong to a \emph{field} over which the polynomial is defined.
If $f\in K[X]$, and $K$ is a subfield of a field $L$,
then the number of zeroes of $f$ in $L$ is no greater than $\deg f$.

We know that $K$ embeds in $\Mat$ under $x\mapsto x\cdot\Id$;
but a polynomial over $K$ can have any number of zeroes in $\Mat$
or even in a sub-ring $K[A]$.  Indeed, if 
$A=\left(\begin{smallmatrix}
0&1\\0&0
\end{smallmatrix}
\right)$
as above, then $\beta\cdot A$ belongs to $K[A]$ for all $\beta$ in $K$,
and $\beta\cdot A$ is a zero of $X^2$.

\addsec{Cayley--Hamilton Theorem}

Given a square matrix over some field,
we are going to want to know that the matrix is a zero
of some nonzero polynomial.
The following gives us this.

\begin{theorem}[Cayley--Hamilton]
Over any field,
every matrix is a zero of its characteristic polynomial.
\end{theorem}

\begin{proof}[First proof.]
Let $K$ be a field,
let $A\in\Mat$, and let
\begin{equation}\label{eqn:f=det}
  f=\det(X\cdot\Id-A),
\end{equation}
the characteristic polynomial of $A$.
We want to show $f(A)=0$.  
It so happens that
$\det(A\cdot\Id-A)=\det(0)=0$.
Thus we want to show
\begin{equation*}%\label{eqn:fA=det}
  f(A)=\det(A\cdot\Id-A).
\end{equation*}
This does \emph{not} follow immediately from \eqref{eqn:f=det}
by replacing $X$ with the matrix $A$,
because the multiplications symbolized in the terms $X\cdot\Id$
and $A\cdot\Id$ are two different operations,
namely scalar multiplication
and matrix multiplication respectively.

Since the determinant function is multiplicative,
for every $P$ in $\GL$,
\begin{align*}
\det(X\cdot\Id-A)
&=\det\bigl(P\cdot(X\cdot\Id-A)\cdot P\inv\bigr)\\
&=\det(X\cdot\Id-PAP\inv).
\end{align*}
For some $P$, $PAP\inv$ is a \textbf{lower triangular matrix,}
as we shall show presently,
so that we may assume $A$ is as in Figure \ref{fig:A}.
\begin{figure}
\begin{equation*}%\label{eqn:A}
\begin{pmatrix}
a^   0 _0&0    &\hdotsfor2   &0            \\
a^   1 _0&a^1_1&\ddots&      &\vdots       \\
\vdots   &     &\ddots&\ddots&\vdots       \\
\vdots   &     &      &\ddots&0            \\
a^{n-1}_0&\hdotsfor3         &a^{n-1}_{n-1}
\end{pmatrix}
\end{equation*}
\caption{A lower triangular matrix}\label{fig:A}
\end{figure}
The characteristic polynomial of $A$ is now
\begin{equation*}
\prod_{i<n}(X-a^i_i).
\end{equation*}
We have to show
\begin{equation*}
\prod_{i<n}(A-a^i_i\Id)=0.
\end{equation*}
The product here is independent of the order of the factors.
If $j<n$, then row $j$ of the product is
\begin{equation*}
\vec e^j\cdot\prod_{i<n}(A-a^i_i\Id).
\end{equation*}
However, since $A$ is the matrix in Figure \ref{fig:A}, we have
\begin{equation*}
\vec e^j\cdot(A-a^j_j\Id)
=\vec e^j\cdot A-a^j_j\vec e^j
=\sum_{i<j}a^j_i\vec e^i.
\end{equation*}
By induction then,
\begin{equation*}
\vec e^j\cdot\prod_{i\leq j}(A-a^i_i\Id)=\vec0;
\end{equation*}
for if this is true when $j<k$, then
\begin{equation*}
\vec e^k\cdot\prod_{i\leq k}(A-a^i_i\Id)
=\sum_{i<k}a^k_i\vec e^i\cdot\prod_{i<k}(A-a^i_i\Id)=\vec0.
\end{equation*}

\begin{sloppypar}
It remains to find, for arbitrary $B$ in $\Mat$,
an invertible matrix $P$ such that $PBP\inv$ is lower triangular.
We shall use induction.
Replacing $K$ with its algebraic closure if necessary,
we know there is a basis $(\vec v^i\colon i<n)$ of $K^n$
such that $\vec v^0$ is an eigenvector.
Let $C$ and $D$ in $\Mat$ be such that
\begin{align*}
	\sum_{i<n}x_i\vec v^i\cdot C&=x_0\vec v^0,&
	\sum_{i<n}x_i\vec v^i\cdot D&=\sum_{0<i<n}x_i\vec v^i.
\end{align*}
Then
$\vec x\mapsto\vec x\cdot BC$ is a homomorphism from $K^n$ to $\Span(\vec v^0)$,
and $\vec x\mapsto\vec x\cdot BD$ is an endomorphism of $\Span(\vec v^i\colon 0<i<n)$,
and
\begin{equation}\label{eqn:C+D}
\vec x\cdot B=\vec x\cdot BC+\vec x\cdot BD.
\end{equation} 
As an inductive hypothesis,
we assume that $\Span(\vec v^i\colon 0<i<n)$ has a basis $(\vec w^i\colon 0<i<n)$
such that
\begin{equation*}
\vec w^j\cdot BD\in\Span(\vec w^i\colon 0<i\leq j)
\end{equation*}
whenever $0<j<n$.
Then $(\vec v^0,\vec w^1,\dots,\vec w^{n-1})$ is a basis of $K^n$,
and
\begin{equation*}
\vec v^0\cdot B\in\Span(\vec v^0)
\end{equation*}
since $\vec v^0$ is an eigenvector of $B$, and by \eqref{eqn:C+D},
\begin{equation*}
\vec w^j\cdot B
\in\Span(\vec v^0,\vec w^0,\dots,\vec w^j)
\end{equation*}
whenever $0<j<n$.
This completes the induction.
If we now define $a^j_i$ by
\begin{align*}
	\vec v^0\cdot B&=a^0_0\vec v^0,&
	\vec w^j\cdot B&=a^j_0\vec v^0+a^j_1\vec w^1+\dots+a^j_j\vec w^j,
\end{align*}
and we let $P$ be the matrix whose $n$ rows are $(\vec v^0,\vec w^1,\dots,\vec w^{n-1})$,
then, with $A$ as in Figure \ref{fig:A}, we have $PB=AP$,
so $P$ is as desired.
\end{sloppypar}
\end{proof}

\begin{proof}[Second proof.]
For every $B$ in $\Mat$, 
there is a matrix in $\Mat$ called the \textbf{adjoint} of $B$,
and denoted by $\adj$, such that
\begin{equation}\label{eqn:adj}
\det B\cdot\Id=B\cdot\adj.
\end{equation}
This is all we need to know about the adjoint;
but in fact, if
\begin{equation*}
B=(b^i_j)^{i\in n}_{j\in n},
\end{equation*}
so that
\begin{equation*}
\det B=\sum_{\sigma\in\Sym}\sgn\cdot\prod_{i<n}b^i_{\sigma(i)},
\end{equation*}
then
\begin{equation*}
\adj=\biggl((-1)^{i+j}\cdot\det\Bigl((b^k_{\ell})^{k\in n\setminus\{i\}}_{\ell\in n\setminus\{j\}}\Bigr)\biggr)^{j\in n}_{i\in n}.
\end{equation*}
From \eqref{eqn:adj}, if we let $B=X\cdot\Id-A$, then we have
\begin{equation}\label{eqn:XI-A}
\det(X\cdot\Id-A)\cdot\Id=(X\cdot\Id-A)\cdot\adj.
\end{equation}
The two members of this equation are elements of $\Mat[{K[X]}]$;
that is, they are matrices with polynomial entries.
We can write out the left-hand member as a sum
\begin{equation}\label{eqn:XC}
X^m\cdot C_m+X^{m-1}\cdot C_{m-1}+\dots+X\cdot C_1+C_0,
\end{equation}
where $C_i\in\Mat$ and, as it happens, $m=n$.
\begin{comment}
  

This sum is a polynomial with matrix coefficients.
It so happens that these matrices are square,
but they need not be, as long as they are all of the same size.
We can multiply two polynomials that have matrix coefficients,
if the dimensions of the coefficients are compatible;
but the multiplication is not generally commutative.
As a scalar, $X$ does commute with matrices.


\end{comment}
We are going to perform a variant of the division algorithm
(page \pageref{thm:div}).
Again, the sum in \eqref{eqn:XC} is equal to either member of \eqref{eqn:XI-A}.
if we abbreviate the sum by $C$,
then we have
\begin{equation}\label{eqn:CD}
C=(X\cdot\Id-A)\cdot X^{m-1}\cdot C_m+D,
\end{equation}
where $D$ stands for
\begin{equation*}
X^{m-1}\cdot(A\cdot C_m+C_{m-1})
	+X^{m-2}\cdot C_{m-2}+\dots+X\cdot C_1+C_0.
\end{equation*}
If we replace $X$ with $A$,
either in $C$ or $D$,
by \eqref{eqn:CD} we get the same result.
By induction, for some $Q$ in $\Mat[{K[X]}]$ and $R$ in $\Mat$,
\begin{equation*}
C=(X\cdot\Id-A)\cdot Q+R,
\end{equation*}
where $R$ is the result of replacing $X$ in $C$ with $A$.
Moreover, $Q$ and $R$ are unique.
Comparing with \eqref{eqn:XI-A}, we conclude that $Q=\adj$ and,
what is the point for us, $R=0$.
\end{proof}

\addsec{Direct sums}

Suppose $V$ is a vector space over $K$,
and $n\in\N$,
and for each $j$ in $n$,
$V_j$ is a subspace of $V$.
If the homomorphism
\begin{equation*}
(v_i\colon i<n)\mapsto\sum_{i<n}v_i
\end{equation*}
from $\prod_{i<n}V_i$ to $V$ is surjective,
then $V$ is the \textbf{sum}
of the subspaces $V_i$,
and we may write
\begin{equation*}
V=V_0+\dots+V_{n-1}=\sum_{i<n}V_i.
\end{equation*}
If, further, the homomorphism is injective,
then $V$ is the \textbf{direct sum} of the $V_i$,
and we may write
\begin{equation*}
V=V_0\oplus\dots\oplus V_{n-1}=\bigoplus_{i<n}V_i.
\end{equation*}


Given $A$ in $\Mat$, we shall understand by
\begin{equation*}
\ker A
\end{equation*}
the kernel of the endomorphism $\vec x\mapsto\vec x\cdot A$ of $K^n$.
Suppose $A$ has characteristic polynomial $f$,
and $K$ is algebraically closed.
We may suppose that the zeroes of $f$ in $K$ are given to us in some order,
as the entries of a list $(\lambda_j\colon j<m)$.
Then
\begin{equation*}
  f=\prod_{j<m}(X-\lambda_j)^{r_j}
\end{equation*}
for some $r_j$ in $\N$.
Now, $\ker\bigl(f(A)\bigr)=K^n$
by the Cayley--Hamilton Theorem.
We are going to show
\begin{equation}\label{eqn:Kn=sum}
K^n=\bigoplus_{j<m}\ker\left(B_j{}^{r_j}\right),
\end{equation}
where
\begin{equation*}
B_j=A-\lambda_j\cdot\Id.
\end{equation*}
The result is easier to prove if stated more generally, as follows.

\begin{theorem}
If $m\in\N$, and $(f_i\colon i<m)\in K[X]^m$,
and each $f_i$ is prime to each of the others,
then
for all $A$ in $\Mat$,
\begin{equation}\label{eqn:Knker}
\ker\left(\prod_{i<m}f_i(A)\right)=\bigoplus_{i<m}\ker(f_i(A)).
\end{equation}
\end{theorem}

\begin{proof}
The case when $m=1$ is trivial.
Suppose $m=2$.
By B\'ezout's Lemma
(in the sense of page \pageref{Bezout3}), 
for some $g_0$ and $g_1$ in $K[X]$,
\begin{equation*}
f_0\cdot g_0+f_1\cdot g_1=1.
\end{equation*}
Therefore
\begin{equation}\label{eqn:ff_1}
f_0(A)\cdot g_0(A)+f_1(A)\cdot g_1(A)=\Id,
\end{equation}
and so, for all $\vec v$ in $K^n$,
\begin{equation}\label{eqn:v=}
\vec v=\vec v\cdot f_0(A)\cdot g_0(A)+\vec v\cdot f_1(A)\cdot g_1(A).
\end{equation}
Now, if we should have 
\begin{equation*}
\vec v\in\ker(f_0(A)\cdot f_1(A)),
\end{equation*}
then we can conclude
\begin{align*}
	\vec v\cdot f_0(A)&\in\ker(f_1(A)),&
	\vec v\cdot f_1(A)&\in\ker(f_0(A)).
\end{align*}
Comparing with \eqref{eqn:v=} shows
\begin{equation*}
\ker(f_0(A)\cdot f_1(A))=\ker(f_1(A))+\ker(f_0(A)).
\end{equation*}
Now, suppose
\begin{equation*}
\vec v=\vec u+\vec w,
\end{equation*}
where
\begin{align*}
\vec u&\in\ker(f_1(A)),&\vec w&\in\ker(f_0(A)).
\end{align*}
Then
\begin{equation*}
\vec v\cdot f_0(A)\cdot g_0(A)=\vec u\cdot f_0(A)\cdot g_0(A);
\end{equation*}
but also, applying \eqref{eqn:ff_1} to $\vec u$ yields
\begin{equation*}
\vec u=\vec u\cdot f_0(A)\cdot g_0(A),
\end{equation*}
and so
\begin{equation*}
\vec v\cdot f_0(A)\cdot g_0(A)=\vec u.
\end{equation*}
This is enough to establish \eqref{eqn:Knker}
in case $m=2$.
The general case follows by induction.
Indeed, under the hypothesis that each $f_i$ is prime to each of the others,
it must be prime to the product of the others.
In particular,
if $m\geq3$ we have $\gcd\left(\prod_{i<m-1}f_i,f_{m-1}\right)=1$,
so
\begin{equation*}
\ker\left(\prod_{i<m}f_i(A)\right)
=\ker\left(\prod_{i<m-1}f_i(A)\right)\oplus\ker(f_{m-1}(A)),
\end{equation*}
and the inductive hypothesis will take care of $\prod_{i<m-1}f_i(A)$.
\end{proof}

\addsec{Cyclic spaces}

Assuming again $A\in\Mat$,
let $\vec v_0$ be an eigenvector of $A$
corresponding to an eigenvalue $\lambda$.
If we let
\begin{equation}\label{eqn:Bl}
  B_{\lambda}=A-\lambda\cdot\Id,
\end{equation}
then $\vec v_0\in\ker B_{\lambda}\setminus\{\vec0\}$.
We continue recursively.
Given a vector $\vec v_i$ in $K^n$,
if possible we let $\vec v_{i+1}$ be a solution of
\begin{equation*}
\vec v_i=\vec x\cdot B_{\lambda}.
\end{equation*}
Then by \eqref{eqn:Bl},
\begin{equation*}
\lambda\cdot\vec v_{i+1}+\vec v_i=\vec v_{i+1}\cdot A,
\end{equation*}
but also, by induction,
\begin{equation*}
\vec v_i\in\ker(B_{\lambda}{}^{i+1}).
\end{equation*}
If $\vec v_{r-1}$ exists, let
\begin{equation*}
  P=\begin{pmatrix}
\vec v_{r-1}\\\hline
\vdots\\\hline
\vec v_1\\\hline
\vec v_0
\end{pmatrix}.
\end{equation*}
Then
\begin{equation}\label{eqn:PA}
PA
=\begin{pmatrix}
\lambda\vec v_{r-1}+\vec v_{r-2}\\\hline
\vdots\\\hline
\lambda\vec v_1+\vec v_0\\\hline
\lambda\vec v_0
\end{pmatrix}
=\begin{pmatrix}
\lambda&     1&     0&  \dots&      0\\
      0&\ddots&\ddots& \ddots& \vdots\\
 \vdots&\ddots&\ddots& \ddots&      0\\
 \vdots&      &\ddots&\lambda&		  1\\
      0&   \hdotsfor2&      0&\lambda
\end{pmatrix}P.
\end{equation}
We show next that the rows of $P$ are linearly independent,
at least under an additional assumption,
which will turn out later always to hold.

\begin{theorem}
Suppose $\vec v\in K^n$, $B\in\Mat$, and
\begin{equation}\label{eqn:Bs}
\vec0=\vec v\cdot B^s
\end{equation}
for some $s$ in $\N$.
If $r$ is the \emph{least} such $s$,
then the $r$-tuple
\begin{equation*}%\label{eqn:cyc}
(\vec v,\vec v\cdot B,\dots,\vec v\cdot B^{r-1})
\end{equation*}
is linearly independent over $K$.
\end{theorem}

\begin{proof}
Suppose \eqref{eqn:Bs} holds,
but the $s$-tuple $(\vec v\cdot B^i\colon i<s)$ is linearly dependent over $K$.
This means
\begin{equation}\label{eqn:0c0}
\vec0=c_0\vec v+c_1\vec v\cdot B+\dots+c_{s-1}\vec v\cdot B^{s-1}
\end{equation}
for some $\vec c$ in $K^s\setminus\{\vec0\}$.
We can write \eqref{eqn:0c0} as
\begin{equation*}
\vec0=\vec v\cdot f(B),
\end{equation*}
where
\begin{equation*}
f=c_0+c_1X+\dots+c_{s-1}X^{s-1}.
\end{equation*}
Let $g=\gcd(X^s,f)$.
By B\'ezout's Lemma,
\begin{equation*}
\vec0=\vec v\cdot g(B).
\end{equation*}
But $g$ must be $X^r$ for some $r$ that is less than $s$.
\end{proof}

If $B\in\Mat$, and $V$ is a subspace of $K^n$,
we let $VB$ be the image of $V$ 
under the endomorphism $\vec x\mapsto\vec x\cdot B$ of $K^n$.
Thus
\begin{equation*}
VB=\{\vec x\cdot B\colon x\in V\}.
\end{equation*}
If $VB\included V$, let us say $V$ is \textbf{$B$-invariant.}
For example, $V$ is $B$-invariant
if it is spanned by $\{\vec v\cdot B^k\colon k\in\upomega\}$
for some $\vec v$ in $V\setminus\{\vec0\}$.
If $V$ is thus, and also $\vec v\cdot B^s=\vec0$ for some $s$ in $\N$,
let us say that $V$ is \textbf{$B$-cyclic.}
If $r$ is the least $s$,
then by the last theorem, $(\vec v\cdot B^i\colon i<r)$ is a basis of the $B$-cyclic space.

\begin{theorem}
For all $B$ in $\Mat$,
for all $s$ in $\N$,
$\ker(B^s)$
is the direct sum of $B$-cyclic subspaces.
\end{theorem}

\begin{proof}
  \begin{sloppypar}
We shall prove that every $B$-invariant subspace of $\ker(B^s)$
is the direct sum of $B$-cyclic subspaces.
We use induction on the dimension of the subspace.
If the dimension is $0$, the claim is vacuously true.
Suppose $V$ is a $B$-invariant subspace of $\ker(B^s)$
having positive dimension.
Then
\begin{equation*}
VB\included V\cap\ker(B^{s-1})\included V.
\end{equation*}
If $r$ is the \emph{least} $s$ for which $V\included\ker(B^s)$, 
then $V\cap\ker(B^{r-1})\pincluded V$.
This shows
\begin{equation*}
VB\pincluded V.
\end{equation*}
As an inductive hypothesis, we assume
\begin{equation}\label{eqn:oplus}
VB=\bigoplus_{i<m}W_i,
\end{equation}
where each $W_i$ is $B$-cyclic.
Then for some $(\vec w_i\colon i<m)$ in $V^m$,
for some $(r_i\colon i<m)$ in $\N^m$,
\begin{align}\label{eqn:basis}
W_i&=\Span(\vec w_i,\vec w_i\cdot B,\dots,\vec w_i\cdot B^{r_i-1}),&
\vec0&=\vec w_i\cdot B^{r_i}.
\end{align}
For some $\vec v_i$ in $V$,
\begin{equation}\label{eqn:wvB}
\vec w_i=\vec v_i\cdot B.
\end{equation}
By the last theorem, we know that the tuple
\begin{equation*}
(\vec v_i,\vec w_i,\vec w_i\cdot B,\dots,\vec w_i\cdot B^{r_i-1}),
\end{equation*}
which is
\begin{equation*}
(\vec v_i,\vec v_i\cdot B,\dots,\vec v_i\cdot B^{r_i}),
\end{equation*}
is linearly independent.  
Let $V_i$ be the $B$-cyclic space that it is a basis of.
We shall show that the sum of the $V_i$ is direct.
  \end{sloppypar}

An arbitrary element of $V_i$ is $\vec v_i\cdot f_i(B)$ for some $f_i$ in $K[X]$
such that
\begin{equation}\label{eqn:degfi}
\deg f_i\leq r_i.
\end{equation}
Suppose
\begin{equation}\label{eqn:vf}
\vec0=\sum_{i<m}\vec v_i\cdot f_i(B).
\end{equation}
Then by \eqref{eqn:wvB},
\begin{equation*}
\vec0=\sum_{i<m}\vec w_i\cdot f_i(B).
\end{equation*}
But then by \eqref{eqn:oplus},
\begin{equation*}
\vec0=\vec w_i\cdot f_i(B),
\end{equation*}
so by \eqref{eqn:degfi}, and \eqref{eqn:basis}, and the previous theorem,
\begin{equation*}
f_i=c_iX^{r_i}
\end{equation*}
for some $c_i$ in $K$.
In this case,
\eqref{eqn:vf} can be written as
\begin{equation*}
\vec0=\sum_{i<m}c_i\vec w_i\cdot B^{r_i-1},
\end{equation*}
which implies that each $c_i$ is $0$.  Thus $f_i=0$.

Now we can let
\begin{equation*}
V'=\bigoplus_{i<m}V_i.
\end{equation*}
Then $V'\included V$.
By construction, $V_iB=W_i$, so
\begin{equation*}
V'B=W=VB.
\end{equation*}
Therefore $V\setminus V'\included\ker B$, and so
\begin{equation*}
V=V'+\ker B.
\end{equation*}
Each element of $\ker B$ constitutes a basis of a one-dimensional $B$-cyclic space.
Then $V$ is the direct sum of some of these spaces, along with the $V_i$,
as desired.
\end{proof}

In the notation of \eqref{eqn:Kn=sum},
there is $(n_j\colon j<m)$ in $\N^m$
such that there are elements
\begin{itemize}
\item 
$\bigl((\vec v_{j,k}\colon k<n_j)\colon j<m\bigr)$ of $\prod_{j<m}\ker\left(B_j{}^{r_j}\right)^{n_j}$,
\item
$\bigl((s_{j,k}\colon k<n_j)\colon j<m\bigr)$ of $\prod_{j<m}\N^{n_j}$, and
\item
$\bigl((V_{j,k}\colon k<n_j)\colon j<m\bigr)$ of 
  \begin{equation*}
  \prod_{j<m}\{\text{subspaces of }\ker(B_j{}^{r_j})\}^{n_j}
  \end{equation*}
\end{itemize}
such that, for each $j$ in $m$,
\begin{itemize}
\item 
$\ker(B_j)$ has the basis
$(\vec v_{j,k}\cdot B_j{}^{s_{j,k}-1}\colon k<n_j)$,
\item
$\ker(B_j{}^{r_j})=\bigoplus_{k<n_j}V_{j,k}$, and
\item
for each $k$ in $n_j$, $V_{j,k}$ 
has the basis
$(\vec v_{j,k}\cdot B_j{}^{\ell}\colon\ell<s_{j,k})$.
\end{itemize}
Now we may let
\begin{equation*}
P=
\begin{pmatrix}
P_0\\\hline\vdots\\\hline P_{m-1}
\end{pmatrix},
\end{equation*}
where, for each $j$ in $m$,
\begin{equation*}
P_j=
\begin{pmatrix}
P_{j,0}\\\hline\vdots\\\hline P_{j,n_j-1}
\end{pmatrix},
\end{equation*}
where, for each $k$ in $n_j$,
\begin{equation*}
P_{j,k}=
\begin{pmatrix}
\vec v_{j,k}\cdot B_j{}^{s_{j,k}-1}\\\hline
\vdots\\\hline 
\vec v_{j,k}\cdot B_j\\\hline
\vec v_{j,k}
\end{pmatrix}.
\end{equation*}
Then $PAP\inv$ is a \textbf{Jordan normal form} for $A$.
Indeed, by the considerations yielding \eqref{eqn:PA},
\begin{equation*}
PAP\inv=\diag{\Lambda_0,\dots,\Lambda_{m-1}},
\end{equation*}
where, for each $j$ in $m$,
\begin{equation*}
\Lambda_j=\diag{\Lambda_{j,0},\dots,\Lambda_{j,n_j-1}},
\end{equation*}
where, for each $k$ in $n_j$,
\begin{equation*}
\Lambda_{j,k}=
\begin{pmatrix}
\lambda_j&     1&     0& \dots&        0\\
        0&\ddots&\ddots&\ddots&   \vdots\\
   \vdots&\ddots&\ddots&\ddots&        0\\
   \vdots&      &\ddots&\ddots&        1\\
	      0& \dots& \dots&     0&\lambda_j
				\end{pmatrix},
\end{equation*}
which is in $\matrices_{s_{j,k}}(K)$.

%\relscale{0.9}
\smaller
%\bibliographystyle{plain}
%\bibliography{../../../references}
\begin{thebibliography}{10}

\bibitem{Burton}
David~M. Burton.
\newblock {\em Elementary Number Theory}.
\newblock McGraw-Hill, Boston, sixth edition, 2007.

\bibitem{Cohn-ANT}
Harvey Cohn.
\newblock {\em Advanced Number Theory}.
\newblock Dover, New York, 1980.
\newblock Corrected republication of 1962 edition.

\bibitem{Gauss-Latin}
Carl~Friedrich Gauss.
\newblock {\em Disquisitiones Arithmeticae}.
\newblock Carl Friedrich Gauss Werke. Gerh.\ Fleischer Jun., Leipzig, 1801.
\newblock Electronic version of the original Latin text from Goettingen State
  and University Library.

\bibitem{Gauss}
Carl~Friedrich Gauss.
\newblock {\em Disquisitiones Arithmeticae}.
\newblock Springer-Verlag, New York, 1986.
\newblock Translated into English by Arthur A. Clarke, revised by William C.
  Waterhouse.

\bibitem{MR600654}
Thomas~W. Hungerford.
\newblock {\em Algebra}, volume~73 of {\em Graduate Texts in Mathematics}.
\newblock Springer-Verlag, New York, 1980.
\newblock Reprint of the 1974 original.

\bibitem{MR0472307}
Morris Kline.
\newblock {\em Mathematical Thought from Ancient to Modern Times}.
\newblock Oxford University Press, New York, 1972.

\bibitem{CK-I}
Cemal Ko{\c c}.
\newblock Linear algebra {I}.
\newblock Printed by the Department of Mathematics, Middle East Technical
  University, 1998.
\newblock No ISBN.

\bibitem{CK-II}
Cemal Ko{\c c}.
\newblock Topics in linear algebra.
\newblock Printed by the Department of Mathematics, Middle East Technical
  University, 2010.
\newblock No ISBN.

\bibitem{Lang-LA}
Serge Lang.
\newblock {\em Linear Algebra}.
\newblock Addison-Wesley, Reading, Massachusetts, second edition, 1970.
\newblock World Student Series edition, second printing, 1972.

\bibitem{MR860948}
Rudolf Lidl and Harald Niederreiter.
\newblock {\em Introduction to finite fields and their applications}.
\newblock Cambridge University Press, Cambridge, 1986.

\end{thebibliography}

\end{document}

