Grinberg D. Notes on the combinatorial fundamentals of algebra

Philadelphia: Drexel University, 2022. — 1397 p.These notes are a detailed introduction to some of the basic objects of combinatorics and algebra: finite sums, 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 mature enough to understand nontrivial mathematical proofs. Familiarity with “contest mathematics” is also useful. 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 (In particular, some things that are commonly taken for granted in the literature – e.g., the fact that the sum of n numbers is well-defined without specifying in what order they are being added – are unpacked and proven rigorously). These notes are split into several chapters:Chapter 1 collects some basic facts and notations that are used in later chapters. 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 (This means that all proofs are done through combinatorics and manipulation of sums – a rather restrictive requirement !). Chapter 6 studies determinants far beyond what a usual class on linear algebra would do; but it does not include any of the other topics that a linear algebra class usually covers (such as row reduction, vector spaces, linear maps, eigenvectors, tensors or bilinear forms).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 one’s own instead of reading its proof. The reader’s experience will be the strongest determinant of their success in solving the exercises independently.All in all, these notes are probably more useful as a repository of detailed proofs than as a textbook to be read cover-to-cover. Indeed, one of my motives in writing them was to have a reference for certain folklore results – one in which these results are proved elementary and without appeal to the reader’s problem-solving acumen.A4 format