Codex @codex  0

Chapter of Abstract Algebra by Romyar Sharifi, with the same Romyar Sharifi byline; no distinct contributed chapter author is established.

Online text: math.ucla.edu/~sharifi/notes/algebra-ch03.html

Cited passages: §3.9, Theorem 3.9.1 and proof, polynomial division when the leading coefficient is a unit; Proposition 3.9.7 and proof, the factor theorem. No publication date is inferred from the URL.

If $W$ is an invariant subspace for a finite-dimensional diagonalizable linear map $T$, its restriction is diagonalizable over the same field. The minimal polynomial of $T{|}_W$ divides that of $T$: an annihilating polynomial for $T$ still annihilates the restriction, and polynomial division by its minimal polynomial proves divisibility. A divisor of a product of distinct linear polynomials remains a product of distinct linear polynomials, proving the assertion. This is the key step in simultaneous diagonalization of commuting linear maps.

For a polynomial $f$ over a field, $f(a)=0$ exactly when $X-a$ divides $f(X)$. Polynomial division by the monic linear factor givesThe constant polynomial remainder is thus the value obtained by evaluation. For $p(X)=X^3-3X^2+4$, the root of a polynomial $2$ gives factor $X-2$ and polynomial quotient $X^2-X-2$. The latter also vanishes at $2$, explaining the repeated factor. This provides a practical way to move between evaluation and factorization.

Online text: jmilne.org/math/CourseNotes/FT.pdf

By James S. Milne, credited as J.S. Milne on the cover and James S. Milne in the author-supplied BibTeX. Version 5.10, September 2022; this is a version date. The version history separately dates the first web version to 21 August 1996.

Cited passages: Chapter 1, Review of polynomial rings, printed p. 10, §1.6, unique polynomial division with zero remainder or strict polynomial degree bound; §1.7, division by a linear factor and evaluation. No separate chapter byline is supplied.

Gaussian quadrature is a quadrature rule that chooses both sample locations and coefficients to achieve unusually high polynomial exactness. For a finite interval $[a,b]$ with $a<b$, assume the integration weight $w$ is integrable and positive almost everywhere. DefineLet $p_n$ be the monic orthogonal polynomial of polynomial degree $n$ for the inner product $⟨u,v{⟩}_w={\int }_a^{b}u(x)v(x)w(x)dx$: it satisfies $⟨p_n,q{⟩}_w=0$ for every polynomial $q$ of polynomial degree below $n$. The polynomial roots of $p_n$ are distinct and inside $(a,b)$; take them as the nodes $x_i$. Integrate the Lagrange cardinal polynomials ${\ell }_i$ to obtain $A_i=I_w({\ell }_i)$. These coefficients are positive, andThe integration weight $w(x)$ and the discrete coefficients $A_i$ play different roles: $w$ specifies the integral being approximated, while $A_i$ tell us how much each sample contributes.^[ref]

A proof outline explains the gain over simply integrating an arbitrary polynomial interpolation. Use polynomial division to write $f=p_{n}q+r$, with $\mathrm{deg}q\le n-1$ and $\mathrm{deg}r\le n-1$. Orthogonality makes $I_w(p_{n}q)=0$, and sampling at the polynomial roots of $p_n$ makes $Q_n(p_{n}q)=0$. The Lagrange cardinal polynomials recover $r$ exactly, so both expressions agree. Also $A_i=Q_n({\ell }_i^2)=I_w({\ell }_i^2)>0$, since ${\ell }_i^2$ has polynomial degree $2n-2$. This is the mechanism behind positive weights of Gaussian quadrature.

For a concrete two-node example, set $w=1$ on $[-1,1]$. The Legendre polynomial $P_2(x)=(3x^2-1)/2$ has polynomial roots $x=\pm 1/\sqrt{3}$. Its monic polynomial version $p_2=x^2-1/3$ has zero integral against both $1$ and $x$, as required. Symmetry and exactness for the constant polynomial give $A_1=A_2=1$. Thus the Gauss–Legendre instance of Gaussian quadrature isDirect evaluation on $1,x,x^2,x^3$ gives $2,0,2/3,0$, exactly their integrals. For the polynomial $f(x)=1+x+x^2+x^3$, two samples therefore give $8/3$ exactly. But for $x^4$ the rule gives $2/9$, whereas the integral is $2/5$: the error $I_1-Q_2$ is $8/45$.

The ceiling $2n-1$ is sharp for $n$ distinct real nodes under the positive-weight assumptions. Their squared nodal polynomial ${\prod }_i(x-x_i{)}^2$ has polynomial degree $2n$, is zero at every sample, and has a strictly positive weighted integral. Thus no such quadrature rule integrates every polynomial of polynomial degree $2n$ exactly. Nor does Gaussian quadrature integrate every nonpolynomial function exactly: the same two-node example gives $Q_2(|x|)=2/\sqrt{3}$, while $I_1(|x|)=1$.

Gaussian quadrature is useful when evaluations are costly and a modest polynomial captures the integrand well. More precisely, for a continuous function $f$ and any polynomial $r$ of polynomial degree at most $2n-1$, positivity and constant exactness giveThe uniform norm on $[a,b]$ measures the approximation between samples. This bound connects quadrature rule accuracy to uniform approximation, rather than promising an error from sample count alone. Corners, sharp unresolved features and roundoff error require their own assessment; the absolute value function example already shows why polynomial exactness is a qualified guarantee.

Horner's method evaluates a polynomial by nested multiplication, requiring one multiplication and one addition per degree after initialization.

For $p(X)=a_n{X}^n+\cdots +a_0$, start with $b_n=a_n$ and compute $b_j=x{b}_{j+1}+a_j$ for $j=n-1,\dots ,0$. The final value is $b_0=p(x)$. Equivalently,This reorganization reuses intermediate results, avoiding separate computation of every power. A dense degree-$n$ polynomial takes $n$ multiplications and $n$ coefficient additions after reading its leading coefficient; special zero coefficients may permit further simplifications.

For our cubic, the coefficient list in descending order is $1,-3,0,4$. The zero is important: it occupies the missing $X$ term's position. At $x=2$, the accumulated values areAt $x=3$, the same operations give $1,0,0,4$, confirming $p(3)=4$.

The intermediate values do more than evaluate. They are the coefficients of the polynomial quotient in polynomial division by $X-x$, with the final value as the polynomial remainder. At $x=2$, the first three values give $X^2-X-2$, soAt $x=3$, they give $X^2$, so $p(X)=(X-3)X^2+4$. This links an efficient numerical calculation with the exact factor theorem.

William George Horner's 1819 paper concerns solving numerical equations by successive approximation. The Royal Society archive records the manuscript and its reading on 1 July 1819; it provides a historical reference for the method's name. ^[ref]

// Target: geometry-and-topology.bigb

A nonzero polynomial of degree $d$ over a field has at most $d$ distinct roots. Indeed, each root supplies a linear factor by polynomial division, and induction on $d$ gives the bound.

The minimal polynomial $m_T$ is the monic polynomial of least polynomial degree such that $m_T(T)=0$. Here a polynomial $p(x)={\sum }_j{c}_j{x}^j$ is evaluated at the linear operator by $p(T)={\sum }_j{c}_j{T}^j$, with the constant term acting as $c_{0}I$.

An annihilating polynomial exists because $I,T,T^2,\dots$ lie in the finite-dimensional vector space ${\mathrm{End}}_F(V)$ and are therefore eventually linearly dependent. Uniqueness follows by subtracting two monic annihilators of the same least degree: their difference has smaller degree and still annihilates $T$.

Equivalently,For the forward implication evaluate the factorization at $T$. For the reverse implication divide $p$ by $m_T$ using polynomial division; the remainder annihilates $T$, so minimality makes it zero. This also identifies the annihilating polynomials as the principal ideal generated by $m_T$.

A maximal ideal is a proper ideal $I$ of $R$ such that an ideal $J$ with $I\subseteq J\subseteq R$ is either $I$ or $R$. Suppose first that $I$ is a maximal ideal. If $a\notin I$, then $I+(a)=R$, so $1=i+ra$ for some $i\in I$ and $r\in R$. In the quotient ring, $(r+I)(a+I)=1+I$. Every nonzero element of $R/I$ therefore has a multiplicative inverse, so $R/I$ is a field. Conversely, if $R/I$ is a field and $J$ properly contains $I$, choose $a\in J\setminus I$. The element $a+I$ has a multiplicative inverse $r+I$, whence $1-ra\in I\subset J$, giving $1\in J$ and $J=R$. ThusThe squares in ${\mathbb{F}}_7$ are $0,1,2,4$, which do not include $-1=6$. Hence $X^2+1$ has no root in ${\mathbb{F}}_7$. A polynomial of degree two or three over a field is an irreducible polynomial exactly when it has no root: any proper polynomial factorization of such a degree has a factor of degree one. The polynomial ring over a field is a Euclidean domain, so the ideal generated by an irreducible polynomial is a maximal ideal. It follows thatis a field. Every coset has a unique representative $a+bX$, by polynomial division, so $|F|=7^2=49$.

Let $j$ be the coset of $X$ in this field. Since $j^2=-1$, the mapis a ring homomorphism. It is surjective by the representative description. Since $1,j$ are linearly independent over ${\mathbb{F}}_7$, its kernel of a ring homomorphism isThere is also a field with $343$ elements. The cubes in ${\mathbb{F}}_7$ are $0,1,-1$, so $X^3-2$ has no root and is an irreducible polynomial. Thereforeis a field whose unique representatives have degree below three. There are $7^3=343$ such representatives.

Apply polynomial division in $F[x]$:Evaluation at $T$ gives $r(T)=f(T)-q(T)m_T(T)=0$. A nonzero remainder could be rescaled to a monic polynomial annihilating $T$ of smaller degree, contradicting the defining minimality. Hence $r=0$ andIn particular, the annihilating polynomials form the principal ideal $(m_T)$.

Represent the data bits, most significant first, by a polynomial $M(x)$ whose polynomial coefficients lie in the field with two elements ${\mathbb{F}}_2$. Here addition and subtraction are both exclusive or, with no carries. Choose a fixed CRC generator polynomial $G(x)$ of polynomial degree $r$, with leading and constant polynomial coefficients one. Both endpoints know $G$ and the bit ordering.

Multiply $M$ by $x^r$, which appends $r$ zero bits. Use polynomial division to obtainReplace the appended zeros by the $r$ bits of the polynomial remainder $R$, retaining leading zeros when necessary. The transmitted polynomial isThe last equality holds because adding $R$ cancels the existing polynomial remainder in the field with two elements. It is the simple systematic cyclic redundancy check convention used here; practical variants can add agreed initialization and final transformations.

The receiver divides the entire received polynomial by $G$. A nonzero polynomial remainder detects corruption. If the received word is $T+E$, where the ones in the error polynomial $E$ mark flipped bits, its polynomial remainder is $E\mathrm{mod}G$. Thus the undetected nonzero errors are exactly the multiples of $G$; a zero result does not prove that transmission was error-free. Operationally, polynomial long division repeatedly cancels a leading one using a shifted copy of $G$, implemented with exclusive or operations.

The fundamental theorem of algebra says that every nonconstant polynomial with complex number coefficients has a root in the complex numbers. Repeated polynomial division by a factor of degree one therefore factors a degree-three polynomial with complex number coefficients into three factors of degree one, with algebraic multiplicities included.

For a matrix with complex number entries $A$ of size three, its characteristic polynomial is ${\chi }_A(t)=\det (tI-A)$, and its characteristic equation is ${\chi }_A(t)=0$. A complex number $\lambda$ is an eigenvalue exactly when $\lambda I-A$ is singular, equivalently when its null space contains a nonzero vector. Thus the three roots of the characteristic polynomial are the three eigenvalues counted with algebraic multiplicity.

For the specified matrix, expansion along the first row givesHence the eigenvalues are $1,1,-1$. Corresponding eigenvectors areThe matrix with these three columns has determinant $2i\ne 0$, so these eigenvectors are linearly independent. A repeated eigenvalue does not in general guarantee two independent eigenvectors; here they have been exhibited directly.

Represent a word $(c_0,\dots ,c_{n-1})$ in the Hamming space $H_{n,q}$ by the polynomial $c(x)={\sum }_{j=0}^{n-1}{c}_j{x}^j$. A cyclic code is a linear code invariant under the cyclic coordinate shift $(c_0,\dots ,c_{n-1})\mapsto (c_{n-1},c_0,\dots ,c_{n-2})$. Under this identification the shift is multiplication by $x$ modulo $x^n-1$. A shift-invariant vector subspace is closed under multiplication by every polynomial, since such multiplication is a linear combination of shifts. It is therefore an ideal ofConversely every ideal of $R$ is a vector subspace closed under multiplication by $x$, hence a cyclic code. Invariance means equality under the shift, since applying it $n$ times is the identity.

Let $J$ be the inverse image of the code ideal under the quotient map ${\mathbb{F}}_q[x]\to R$. It contains $(x^n-1)$ and is nonzero. Choose a nonzero element of $J$ of smallest degree and scale it to a monic polynomial $g$. For any $f\in J$, polynomial division gives $f=ag+r$ with $\mathrm{deg}r<\mathrm{deg}g$. Since $r=f-ag\in J$, minimality forces $r=0$. Thus $J=(g)$ and in particularThis is the required generator polynomial of a cyclic code; the divisibility direction in the printed formula is reversed. The quotient-ring modulus is $x^n-1$, with $1$ denoting the multiplicative identity of the finite field. If $r=\mathrm{deg}g$, every codeword has a unique representative $ag$ with $\mathrm{deg}a<n-r$. Indeed reduction of $a$ modulo $(x^n-1)/g$ gives this form, and two such products cannot differ by a nonzero multiple of $x^n-1$ because their difference has degree less than $n$. ThereforeFor the zero code the convention is $g=x^n-1$ and this basis is empty; for the full word space $g=1$.

The zeros of a cyclic code are the polynomial roots of $g$ in a splitting field $E$ of $x^n-1$. Suppose first that the characteristic $p$ of ${\mathbb{F}}_q$ does not divide $n$. The formal derivative of $x^n-1$ is $n{x}^{n-1}$, which has no common root with $x^n-1$; all roots of $g$ are therefore simple. If they are ${\alpha }_1,\dots ,{\alpha }_r$, then $g\mid c$ is equivalent to $c({\alpha }_i)=0$ for all $i$. A root-evaluation parity-check matrix of a cyclic code, written with checks as rows, is consequentlyIts entries may lie in $E$, rather than in the original finite field. To obtain a parity-check matrix over ${\mathbb{F}}_q$, choose a basis of $E$ over ${\mathbb{F}}_q$ and replace each equation by the equations for all of its field coordinates. The resulting matrix has the same kernel $C$, hence rank $r=n-\dim C$; retain any $r$ independent rows. More economically, choose one root from each Frobenius conjugate orbit. For $c\in {\mathbb{F}}_q[x]$, $c({\alpha }^q)=c(\alpha {)}^q$, so checking one representative checks its whole orbit. Expanding that representative's equation in a basis of ${\mathbb{F}}_q(\alpha )$ gives precisely the number of checks equal to its orbit length.

No coprimality hypothesis is stated in the question, so the repeated-root cyclic code case must also be distinguished. Distinct roots alone cannot determine these codes: in ${\mathbb{F}}_2[x]/(x^2-1)$, the generators $x+1$ and $(x+1{)}^2$ have the same zero, but generate codes of dimensions one and zero. In general write $g={\prod }_i(x-{\alpha }_i{)}^{m_i}$ in $E[x]$. The correct checks areusing Hasse derivatives. Indeed $c({\alpha }_i+z)={\sum }_{\ell }{c}^{[\ell ]}({\alpha }_i)z^{\ell }$, so vanishing of the first $m_i$ coefficients is equivalent to divisibility by $(x-{\alpha }_i{)}^{m_i}$. A repeated-root parity-check matrix over $E$ thus has rows indexed by $(i,\ell )$ and entriesAs before, expand to equations over ${\mathbb{F}}_q$ and retain $\mathrm{deg}g={\sum }_i{m}_i$ independent rows. The ordinary root-evaluation matrix is exactly the special case $m_i=1$.

For the binary Hamming code, let $s\ge 2$, $n=2^s-1$, and let $\omega$ generate the multiplicative group of a finite field ${\mathbb{F}}_{2^s}^{\times }$. This is possible because that group is a cyclic group. Choose a basis of ${\mathbb{F}}_{2^s}$ over ${\mathbb{F}}_2$. The coordinate columns of $1,\omega ,\dots ,{\omega }^{n-1}$ then run through every nonzero vector of ${\mathbb{F}}_2^s$ exactly once. They are a parity-check matrix $H$ for a Hamming code, possibly after permuting the columns of a given Hamming matrix. Thusis equivalent to the Hamming code. Multiplication by $x$ modulo $x^n-1$ multiplies its evaluation at $\omega$ by $\omega$, so $C$ is a cyclic code.

The parity-check matrix has rank $s$ because its columns contain a basis. It has no zero column or repeated column, so no nonzero word of weight one or two is in its kernel. Two distinct nonzero columns have a nonzero sum, which is a third distinct column; these three columns give a word of weight three. Hence $C$ has parameters $[2^s-1,2^s-s-1,3]$.

A polynomial over ${\mathbb{F}}_2$ vanishes at $\omega$ exactly when it is divisible by its minimal polynomial of an algebraic element $m_{\omega }$. The finite-field Frobenius automorphism gives all conjugates of $\omega$ as ${\omega }^{2^j}$. Their orbit length is $s$: if ${\omega }^{2^d}=\omega$ with $0<d<s$, then the order $2^s-1$ of $\omega$ would divide $2^d-1$, which is a smaller positive integer. Therefore the Hamming code as a cyclic code hasThe last exponent here is $2^{s-1}$. The printed exponent $2^s-1$ would give ${\omega }^{2^s-1}=1$, which is not a root of the degree-$s$ irreducible minimal polynomial of an algebraic element for $s\ge 2$.

First quotient by $3$, obtaining the quotient ringPolynomial division by this monic quadratic gives a unique representative $a+bX$ with $a,b\in {\mathbb{F}}_3$. Uniqueness holds because a nonzero multiple of a monic quadratic cannot have degree less than two. Therefore $|R|=3^2=9$.

In characteristic three, $X^2+X+1=(X-1{)}^2$. The residue $ϵ=X-1$ is nonzero by the uniqueness of the degree-one representative, but ${ϵ}^2=0$. Thus $ϵ$ is both a nilpotent element and a zero divisor. Consequently $R$ is not an integral domain. Equivalently, its multiplication is that of ${\mathbb{F}}_3[ϵ]/({ϵ}^2)$, rather than that of a field with nine elements.

The evaluation map $\phi :\mathbb{R}[x]\to \mathbb{C}$, $p\mapsto p(i)$, is a ring homomorphism and is onto because $a+bx$ maps to any $a+bi$. By polynomial division, writeThen $p(i)=0$ precisely when $a=b=0$. Thus $\ker \phi =(x^2+1)$, and the first isomorphism theorem givesSince the quotient ring is a field, $(x^2+1)$ is a maximal ideal.

Evaluation at a real point defines a surjective ring homomorphism $p\mapsto p(a,b)$ from $\mathbb{R}[x,y]$ to $\mathbb{R}$. Its kernel is $(x-a,y-b)$: subtracting the constant $p(a,b)$ expresses the remainder as a multiple of $x-a$ plus a multiple of $y-b$, by successive polynomial division. The first isomorphism theorem therefore identifies the quotient ring with the field $\mathbb{R}$, proving each $I_{a,b}$ is maximal.

For a maximal ideal not on this list, takeEvaluation $p(x,y)\mapsto p(i,0)$ is onto $\mathbb{C}$, and its kernel is $J$: first subtract a multiple of $y$, then divide the remaining polynomial in $x$ by $x^2+1$. Hence $\mathbb{R}[x,y]/J\cong \mathbb{C}$, a field. Finally, if $J=I_{a,b}$ for real $a,b$, the member $x^2+1\in J$ would vanish at $(a,b)$, requiring $a^2+1=0$, which is impossible over $\mathbb{R}$.

Here is an intrinsic definition that also proves well-definedness. For a complex line bundle $L$, define its First Chern class to be the Euler class of its canonically oriented underlying real rank-two bundle: pull its integral Thom class back along the zero section after forgetting relative support. The complex orientation fixes the sign, so this construction makes no arbitrary choice of generator.

For a rank-$r>0$ complex vector bundle $E$, let $\pi :\mathbb{P}(E)\to X$ be its projective bundle of lines, let $S\subset {\pi }^{\ast }E$ be the tautological bundle, and put $h=-c_1(S)=c_1(S^{\ast })$. On every fiber ${\mathbb{CP}}^{r-1}$, $h$ is the positive degree-two generator. The Leray-Hirsch theorem says that if globally defined cohomology classes restrict to a free basis of the cohomology of every fiber, then multiplication by those classes identifies the cohomology of the total space with a free module over the base. Applied here, it givesThe finite trivializing cover in the question is sufficient for this application: the assertion holds on each trivializing open set by the Künneth theorem, since the fiber has finite free cohomology, and the Mayer–Vietoris sequence and the Five lemma glue it over the finite cover. The same local argument constructs the oriented Thom class used for line bundles. It does not require a choice of classifying map.

There are therefore unique classes $c_i(E)\in H^{2i}(X;\mathbb{Z})$ such thatDefine $c_0(E)=1$ and $c_i(E)=0$ for $i>r$. For rank zero the Total Chern class is $1$. This is the projective bundle definition of Chern classes. Existence and uniqueness follow by expressing $h^r$ in the displayed free module basis, with degrees determining each coefficient. The projective bundle and tautological bundle are intrinsic to $E$, and the line Thom class is uniquely fixed by orientation. Hence the resulting Chern classes do not depend on trivializations or other auxiliary choices. For a line bundle the relation is $h+c_1(E)=0$, agreeing with the original normalization. Pulling back this unique relation also proves naturality. This standard construction and the sum theorem are treated in Vector Bundles and K-Theory, Section 3.1.

The requested result is the Whitney sum formula for Chern classes:Here $c(E)=1+c_1(E)+\cdots +c_r(E)$, and the formula holds for complex vector bundles over a common base. In particular, a trivial bundle has total Chern class $1$.

Now take $B={\mathbb{CP}}^{n-1}$ and let $L\subset B\times {\mathbb{C}}^n$ be its tautological bundle. The standard Hermitian inner product gives the rank-$(n-1)$ complex bundle $Q=L^{\perp }$, with $L\oplus Q\cong {\underline{\mathbb{C}}}^n$. The orthogonal complex line flag manifold in the question is precisely $\mathbb{P}(Q)$: over a first line $\ell$, the second line is any line in ${\ell }^{\perp }$. Local orthonormal frames give this identification as a fiber bundle, with fiber ${\mathbb{CP}}^{n-2}$.

Let $x=c_1(L^{\ast })$ on $B$, also writing $x$ for its pullback to $\mathbb{P}(Q)$. By part 3(a), $H^{\ast }(B;\mathbb{Z})=\mathbb{Z}[x]/(x^n)$. The Whitney sum formula for Chern classes givesLet $S_2$ be the second tautological line on $\mathbb{P}(Q)$, and set $y=c_1(S_2^{\ast })$. Thus $x,y$ are exactly the pullbacks of the positive hyperplane classes from the two projective factors. The projective bundle definition of Chern classes for $Q$ givesTogether with $x^n=0$, this gives a surjective graded ring mapThere are no additional relations. Indeed the second relation is monic of degree $n-1$ in $y$, so polynomial division makes its source free over $\mathbb{Z}[x]/(x^n)$ on $1,y,\dots ,y^{n-2}$. The projective bundle formula for complex vector bundles gives exactly the same free basis on the target. The map sends each basis element to its corresponding basis element, and is therefore an isomorphism. ConsequentlyThis is the cohomology ring of the orthogonal complex line flag manifold. Its additive basis is $x^i{y}^j$ with $0\le i<n$, $0\le j<n-1$. As a symmetry check, multiplying the second relation by $y-x$ gives $y^n-x^n=0$, so $y^n=0$ as expected from the second projection. For $n=2$, every line has a unique orthogonal line, and the relations become $x^2=0$, $x+y=0$, giving the ring of ${\mathbb{CP}}^1$. If $n=1$, the space is empty and the second relation is $1=0$, so the printed formula still gives the zero cohomology ring.

Reducing coefficients modulo $p$ gives the ring isomorphismIf $d=\mathrm{deg}f>0$, its monic leading coefficient remains one modulo $p$, so $\mathrm{deg}\bar{f}=d$. Polynomial division gives a unique representative of degree less than $d$: existence follows by division, and the difference of two such representatives cannot be a nonzero multiple of a degree-$d$ monic polynomial. There are $p$ choices for each of the $d$ coefficients, provingIrreducibility of $\bar{f}$ is not needed for finiteness; without it the quotient ring need not be a field.

The structure theorem for finitely generated modules over a principal ideal domain applies in particular to a Euclidean domain $R$: every finitely generated module has an isomorphismwith each $d_i$ nonzero and a nonunit. The rank of a free module $r$ and the invariant factors of a finitely generated module $d_i$ are unique up to multiplication by units; empty sums are allowed. This is the classification theorem being used, without a proof of that theorem.

The rational canonical form theorem states that for a linear operator $T$ on a finite-dimensional vector space over any field $F$, there are unique monic nonconstant polynomials $p_1\mid \cdots \mid p_k$ such that some basis givesHere, for $p(t)=t^d+a_{d-1}{t}^{d-1}+\cdots +a_0$, the companion matrix has ones on its subdiagonal and last column $(-a_0,\dots ,-a_{d-1}{)}^T$. The empty matrix covers a zero-dimensional space. Two linear operators have matrix similarity exactly when they have the same invariant factors of a linear operator.

For the proof, make $V$ an $F[t]$-module by $t\cdot v=T(v)$. It is a finitely generated module, since a vector-space basis also generates it as a module. It is a torsion module: the powers of $T$ have linear dependence in the finite-dimensional space ${\mathrm{End}}_F(V)$, so some nonzero polynomial annihilates every vector. Because $F[t]$ is a Euclidean domain, the classification theorem givesThere is no free summand, since a nonzero free module over $F[t]$ is not a torsion module. Choose monic generators of the ideals. On $F[t]/(p_i)$, the classes of $1,t,\dots ,t^{d_i-1}$ form an $F$-basis by polynomial division. Multiplication by $t$ is exactly $C(p_i)$ in that basis, proving existence. Uniqueness in the classification theorem proves uniqueness of the rational canonical form. Finally, an $F[t]$-module isomorphism is precisely an invertible $F$-linear map intertwining the operators, establishing the assertion about matrix similarity. In particular the characteristic polynomial is ${\prod }_i{p}_i$ and the minimal polynomial is $p_k$ for nonzero $V$.

The Cayley-Hamilton theorem states that every square matrix satisfies its characteristic polynomial: if ${\chi }_A(t)=\det (tI-A)$, then ${\chi }_A(A)=0$.

For the proof, the adjugate identity givesWrite $\mathrm{adj}(tI-A)=B_0+B_{1}t+\cdots +B_{n-1}{t}^{n-1}$ and compare coefficients. Multiplying the resulting recurrence by successive powers of $A$ and summing telescopically yields ${\chi }_A(A)=0$.

By polynomial division, $p=q{\chi }_A+r$ with $\mathrm{deg}r<n$. Therefore $p(A)=r(A)$ by Cayley-Hamilton, while $p(\lambda )=r(\lambda )$ for every eigenvalue $\lambda$, since ${\chi }_A(\lambda )=0$.

For the displayed matrix,The remainder of $t^{1000}$ modulo this polynomial has the form $a{t}^2+c$, because its values at $i$ and $-i$ are both $1$. The equations $-a+c=1$ and $4a+c=2^{1000}$ giveSince $(A^2{)}_{11}=3$, the requested entry is