Zentralblatt MATH

Zbl. 1360.13001
Kreuzer, Martin; Robbiano, Lorenzo
Computational linear and commutative algebra. (English)
Cham: Springer. xviii, 321 p. (2016)
ISBN 978-3-319-43599-2 (harcover); 978-3-319-43601-2 (ebook)

Let $K$ denote a field and let $V$ be a $K$-vector space with $d=\dim_K(V)$. Let $End_K(V)$ denote the $K$-vector space of all endomorphisms of $V$. By fixing a basis of $V$ clearly $End_K(V)$ coincides with the set of $n\times n$-matrices over $K$. Let $\phi\in End_K(V)$ denote an endomorphism. The kernel of the substitution homomorphism $\epsilon: K[z]\rightarrow K[\phi]$, $z\mapsto\phi$, is a non-vanishing polynomial. The minimal polynomial $\mu_\phi(z)$ of $\phi$ is the monic generator of $ker \epsilon$. Note that $ker \epsilon\ne 0$ is a principal ideal since $\dim_K (End_K(V))<\infty$.

Via the epimorphism $\epsilon: K[z]\rightarrow K[\phi]$ the $K$-vector space $V$ possesses the structure of a zero-dimensional $K[z]$-module defined by $f(z)\cdot v = f(\phi)(v)$ for all $f(z)\in K[z]$ and $v\in V$. Let $\mu_\phi(z) = p_1(z)^{m_1} \cdots p_s(z)^{m_s} \in K[z]$ be a decomposition (over $K$) of the minimal polynomial into pairwise distinct, monic, irreducible factors with multiplicities. These factors are called eigenfactors of $\phi$. Note that if an eigenfactor of $\phi$ has the form $z - \lambda$, then $\lambda$ is an eigenvector. This provides a Generalized Eigenspace Decomposition of $V$ into the “big” kernels of $p_i(\phi)$. It comes out that $V$ is a cyclic $K[z]$-module via $\phi$ if and only if $\mu_\phi(z) = \chi_\phi(z)$, the characteristic polynomial of $\phi$.

Among others this is explained in Section 1 “Endomorphisms” of the book. It could be considered as a “warm up” of linear algebra viewed by the module structure given by an endomorphism of $V$ over $K[z]$. By examples the authors introduce the computational aspect of these methods.

In Section 2 “Families of Commuting Endomorphisms” they introduce the zero-dimensional $K$-algebra $K[\phi_1,...,\phi_n]$ for a set $\Phi=\{\phi_1,...,\phi_n\}$ of commuting endomorphisms $\phi_i \in End_K(V)$. Let $P=K[x_1,...,x_n]$ denote the polynomial ring in $n$ variables. Then there is a presentation of $K[\phi_1,...,\phi_n] = P/Rel_P(\phi)$ induced by $x i \mapsto \phi_i$. As a first step there is the Moeller-Buchberger Algorithm for computing $Rel_P(\Phi)$ and an algorithm for computing the minimal polynomial of a family member. Then Eigenfactors, Joint Eigenspaces etc. as generalizations of the notions of Section 1 are discussed.

Section 3 “Special Families of Endomorphisms” is devoted to commuting families of different types, among them unigenerated families, commendable families, local families, dual families, extended families, etc. To mention one of them the authors consider commuting families over which the vector space $V$ is a cyclic module. They describe a cyclicity test. Moreover another family is the unigenerated one: there is an endomorphism such that all endomorphisms in the family are polynomials in it.

In Section 4 “Zero-Dimensional Affine Algebras” the authors build another bridge to commutative algebra. Let $R$ denote zero-dimensional $K$-algebra and $f\in R$. By multiplication by $f\in R$ there is a $K$-linear map $\theta_f: R\longrightarrow R$. The family $\mathcal{F}=K[\theta_f \mid f\in R]$ is called the multiplication family of $R$. For its study the several aspects of commutative algebra are developed (primary decomposition, separators, Hilbert functions, canonical modules, Gorenstein ring, Cayley-Bacharach property, ...). All of this related to the study of the zero-dimensional algebras in the view of the previous sections.

Let $R=P/I$ be a zero-dimensional $K$-algebra. In Section 5 “Computing Primary and Maximal Components” there are several strategies for computing the primary decomosition of $I$ as well as the maximal components of the radical of $I$. The basic observation is that $I$ may be considered as the ideal of relations of a commuting family. Moreover there are ”Monte Carlo”-like methods as well as results about finite fields.

In the final Section 6 “Solving Zero-Dimensional Polynomial Systems” there are various results for getting the zeros of commuting families, computing the zeros by Eigenvectors and Eigenspaces and solving polynomial systems over finite fields resp. the rationals.

The present monograph completes the authors’ books “Computational Commutative Algebra 1, 2” [Springer, Heidelberg (2000; Zbl 0956.13008), (2005; Zbl 1090.13021)] but it could be also independently read and used. As the authors explain the book is not a book about numerical linear algebra, it is – as the title says – a connection between linear and commutative algebra with a view towards computational aspects. There are various examples, algorithms and hints illustrating the authors intentions. The material presented in this form is new and not available elsewhere. The examples are done with the aid of the Computer Algebra System CoCoA, freely available.

The monograph could be used as a complementary source for classical Linear Algebra as well as an introductory book to Commutative Algebra and a starting lecture for Computer Algebra. For an interested reader it could be also a research monograph for an introduction to modern algebra. Even an experienced reader will discover new and unexpected aspects of the theory. The text is presented in the authors’ lively and humorous style as in their books “Computational Commutative Algebra 1, 2” [loc. cit.].

Reviewer: Peter Schenzel (Halle)

13-01 Textbooks (commutative algebra)
13Pxx Computational aspects and applications of commutative algebra
15A99 Miscellaneous topics in linear algebra

Keywords: computational linear algebra; commuting endomorphisms; zero-dimensional algebras; primary decomposition; polynomial system solving