Grinberg D. Notes on the combinatorial fundamentals of algebra

Minneapolis: University of Minnesota, 2019. — 1327 p.These notes are a detailed introduction to some of the basic objects of combinatorics and algebra: binomial coefficients, permutations and determinants (from a combinatorial viewpoint – no linear algebra is presumed). To a lesser extent, modular arithmetic and recurrent integer sequences are treated as well. The reader is assumed to be proficient in high-school mathematics and low-level “contest mathematics”, and mature enough to understand rigorous mathematical proofs. One feature of these notes is their focus on rigorous and detailed proofs. Indeed, so extensive are the details that a reader with experience in mathematics will probably be able to skip whole paragraphs of proof without losing the thread (As a consequence of this amount of detail, the notes contain far less material than might be expected from their length). Rigorous proofs mean that (with some minor exceptions) no “handwaving” is used; all relevant objects are defined in mathematical (usually set-theoretical) language, and are manipulated in logically well-defined ways. These notes are split into several chapters:Chapter 1 collects some basic facts and notations that are used in later chapter. This chapter is not meant to be read first; it is best consulted when needed.Chapter 2 is an in-depth look at mathematical induction (in various forms, including strong and two-sided induction) and several of its applications (including basic modular arithmetic, division with remainder, Bezout’s theorem, some properties of recurrent sequences, the well-definedness of compositions of n maps and sums of n numbers, and various properties thereof).Chapter 3 surveys binomial coefficients and their basic properties. Unlike most texts on combinatorics, our treatment of binomial coefficients leans to the algebraic side, relying mostly on computation and manipulations of sums; but some basics of counting are included.Chapter 4 treats some more properties of Fibonacci-like sequences, including explicit formulas (à la Binet) for two-term recursions of the form xn = axn−1+bxn−2.Chapter 5 is concerned with permutations of finite sets. The coverage is heavily influenced by the needs of the next chapter (on determinants); thus, a great role is played by transpositions and the inversions of a permutation.Chapter 6 is a comprehensive introduction to determinants of square matrices over a commutative ring, from an elementary point of view. This is probably the most unique feature of these notes: I define determinants using Leibniz’s formula (i.e., as sums over permutations) and prove all their properties (Laplace expansion in one or several rows; the Cauchy-Binet, Desnanot-Jacobi and Plücker identities; the Vandermonde and Cauchy determinants; and several more) from this vantage point, thus treating them as an elementary object unmoored from its linear-algebraic origins and applications. No use is made of modules (or vector spaces), exterior powers, eigenvalues, or of the “universal coefficients” trick. (This means that all proofs are done through combinatorics and manipulation of sums – a rather restrictive requirement !)The notes include numerous exercises of varying difficulty, many of them solved. The reader should treat exercises and theorems (and propositions, lemmas and corollaries) as interchangeable to some extent; it is perfectly reasonable to read the solution of an exercise, or conversely, to prove a theorem on their own instead of reading its proof.True PDF (A4 format)