Notes on the combinatorial fundamentals of algebra∗ Darij Grinberg January 10, 2019 (with minor corrections June 5, 2019)† Contents Introduction 1.1 Prerequisites 1.2 Notations 1.3 Injectivity, surjectivity, bijectivity 1.4 Sums and products: a synopsis 1.4.1 Definition of ∑ 1.4.2 Properties of ∑ 1.4.3 Definition of ∏ 1.4.4 Properties of ∏ 1.5 Polynomials: a precise definition A closer look at induction 2.1 Standard induction 2.1.1 The Principle of Mathematical Induction 2.1.2 Conventions for writing induction proofs 2.2 Examples from modular arithmetic 2.2.1 Divisibility of integers 2.2.2 Definition of congruences 2.2.3 Congruence basics 2.2.4 Chains of congruences 2.2.5 Chains of inequalities (a digression) 2.2.6 Addition, subtraction and multiplication of congruences ∗ old † The title: PRIMES 2015 reading project: problems and solutions numbering in this version is compatible with that in the version of 10 January 2019 11 12 12 16 17 22 41 45 49 57 57 57 60 63 63 65 66 68 71 72 Notes on the combinatorial fundamentals of algebra page 2.2.7 Substitutivity for congruences 74 2.2.8 Taking congruences to the k-th power 77 2.3 A few recursively defined sequences 78 q 2.3.1 an = an−1 + r 78 2.3.2 The Fibonacci sequence and a generalization 81 2.4 The sum of the first n positive integers 85 2.5 Induction on a derived quantity: maxima of sets 87 2.5.1 Defining maxima 87 2.5.2 Nonempty finite sets of integers have maxima 89 2.5.3 Conventions for writing induction proofs on derived quantities 91 2.5.4 Vacuous truth and induction bases 93 2.5.5 Further results on maxima and minima 95 2.6 Increasing lists of finite sets 97 2.7 Induction with shifted base 103 2.7.1 Induction starting at g 103 2.7.2 Conventions for writing proofs by induction starting at g 107 2.7.3 More properties of congruences 109 2.8 Strong induction 112 2.8.1 The strong induction principle 112 2.8.2 Conventions for writing strong induction proofs 116 2.9 Two unexpected integralities 119 2.9.1 The first integrality 119 2.9.2 The second integrality 122 2.10 Strong induction on a derived quantity: Bezout’s theorem 129 2.10.1 Strong induction on a derived quantity 129 2.10.2 Conventions for writing proofs by strong induction on derived quantities 132 2.11 Induction in an interval 134 2.11.1 The induction principle for intervals 134 2.11.2 Conventions for writing induction proofs in intervals 138 2.12 Strong induction in an interval 139 2.12.1 The strong induction principle for intervals 139 2.12.2 Conventions for writing strong induction proofs in intervals 143 2.13 General associativity for composition of maps 144 2.13.1 Associativity of map composition 144 2.13.2 Composing more than maps: exploration 145 2.13.3 Formalizing general associativity 146 2.13.4 Defining the “canonical” composition C ( f n , f n−1 , , f ) 148 2.13.5 The crucial property of C ( f n , f n−1 , , f ) 149 2.13.6 Proof of general associativity 151 2.13.7 Compositions of multiple maps without parentheses 153 2.13.8 Composition powers 155 2.13.9 Composition of invertible maps 164 Notes on the combinatorial fundamentals of algebra page 2.14 General commutativity for addition of numbers 2.14.1 The setup and the problem 2.14.2 Families 2.14.3 A desirable definition 2.14.4 The set of all possible sums 2.14.5 The set of all possible sums is a 1-element set: proof 2.14.6 Sums of numbers are well-defined 2.14.7 Triangular numbers revisited 2.14.8 Sums of a few numbers 2.14.9 Linearity of sums 2.14.10.Splitting a sum by a value of a function 2.14.11.Splitting a sum into two 2.14.12.Substituting the summation index 2.14.13.Sums of congruences 2.14.14.Finite products 2.14.15.Finitely supported (but possibly infinite) sums 2.15 Two-sided induction 2.15.1 The principle of two-sided induction 2.15.2 Division with remainder 2.15.3 Backwards induction principles 2.16 Induction from k − to k 2.16.1 The principle 2.16.2 Conventions for writing proofs using “k − to k” induction On binomial coefficients 3.1 Definitions and basic properties 3.1.1 The definition 3.1.2 Simple formulas 3.1.3 The recurrence relation of the binomial coefficients 3.1.4 The combinatorial interpretation of binomial coefficients 3.1.5 Upper negation 3.1.6 Binomial coefficients of integers are integers 3.1.7 The binomial formula 3.1.8 The absorption identity 3.1.9 Trinomial revision 3.2 Binomial coefficients and polynomials 3.3 The Chu-Vandermonde identity 3.3.1 The statements 3.3.2 An algebraic proof 3.3.3 A combinatorial proof 3.3.4 Some applications 3.4 Further results 3.5 The principle of inclusion and exclusion 3.6 Additional exercises 165 165 166 170 171 174 178 181 183 185 190 195 198 199 201 203 206 206 211 217 218 218 222 224 224 224 225 229 231 232 234 235 235 236 238 242 242 243 247 249 259 274 284 Notes on the combinatorial fundamentals of algebra Recurrent sequences 4.1 Basics 4.2 Explicit formulas (à la Binet) 4.3 Further results 4.4 Additional exercises page Permutations 5.1 Permutations and the symmetric group 5.2 Inversions, lengths and the permutations si 5.3 The sign of a permutation 5.4 Infinite permutations 5.5 More on lengths of permutations 5.6 More on signs of permutations 5.7 Cycles 5.8 The Lehmer code 5.9 Extending permutations 5.10 Additional exercises 290 290 293 295 298 300 300 305 309 311 319 322 327 332 335 337 An introduction to determinants 6.1 Commutative rings 6.2 Matrices 6.3 Determinants 6.4 det ( AB) 6.5 The Cauchy-Binet formula 6.6 Prelude to Laplace expansion 6.7 The Vandermonde determinant 6.7.1 The statement 6.7.2 A proof by induction 6.7.3 A proof by factoring the matrix 6.7.4 Remarks and variations 6.8 Invertible elements in commutative rings, and fields 6.9 The Cauchy determinant 6.10 Further determinant equalities 6.11 Alternating matrices 6.12 Laplace expansion 6.13 Tridiagonal determinants 6.14 On block-triangular matrices 6.15 The adjugate matrix 6.16 Inverting matrices 6.17 Noncommutative rings 6.18 Groups, and the group of units 6.19 Cramer’s rule 6.20 The Desnanot-Jacobi identity 6.21 The Plücker relation 341 342 353 357 372 388 401 406 406 408 416 419 423 428 429 431 432 444 451 455 463 471 474 476 481 500 ∈ Sn Notes on the combinatorial fundamentals of algebra page 6.22 Laplace expansion in multiple rows/columns 6.23 det ( A + B) 6.24 Some alternating-sum formulas 6.25 Additional exercises Solutions 7.1 Solution to Exercise 1.1 7.2 Solution to Exercise 2.1 7.3 Solution to Exercise 2.2 7.4 Solution to Exercise 2.3 7.5 Solution to Exercise 2.4 7.6 Solution to Exercise 2.5 7.7 Solution to Exercise 2.6 7.8 Solution to Exercise 2.7 7.9 Solution to Exercise 2.8 7.10 Solution to Exercise 2.9 7.11 Solution to Exercise 3.1 7.12 Solution to Exercise 3.2 7.12.1 The solution 7.12.2 A more general formula 7.13 Solution to Exercise 3.3 7.14 Solution to Exercise 3.4 7.15 Solution to Exercise 3.5 7.16 Solution to Exercise 3.6 7.17 Solution to Exercise 3.7 7.18 Solution to Exercise 3.8 7.19 Solution to Exercise 3.9 7.20 Solution to Exercise 3.10 7.21 Solution to Exercise 3.11 7.22 Solution to Exercise 3.12 7.23 Solution to Exercise 3.13 7.24 Solution to Exercise 3.15 7.25 Solution to Exercise 3.16 7.26 Solution to Exercise 3.18 7.27 Solution to Exercise 3.19 7.28 Solution to Exercise 3.20 7.29 Solution to Exercise 3.21 7.30 Solution to Exercise 3.22 7.30.1 First solution 7.30.2 Second solution 7.30.3 Addendum 7.31 Solution to Exercise 3.23 7.32 Solution to Exercise 3.24 7.33 Solution to Exercise 3.25 509 514 518 522 527 527 529 531 534 544 547 547 548 549 552 556 558 558 568 572 576 579 584 587 592 595 597 601 603 606 612 618 621 642 646 657 659 659 662 669 670 674 676 Notes on the combinatorial fundamentals of algebra 7.34 Solution to Exercise 3.26 7.34.1 First solution 7.34.2 Second solution 7.35 Solution to Exercise 3.27 7.36 Solution to Exercise 4.1 7.37 Solution to Exercise 4.2 7.38 Solution to Exercise 4.3 7.39 Solution to Exercise 4.4 7.39.1 The solution 7.39.2 A corollary 7.40 Solution to Exercise 5.1 7.41 Solution to Exercise 5.2 7.42 Solution to Exercise 5.3 7.43 Solution to Exercise 5.4 7.44 Solution to Exercise 5.5 7.45 Solution to Exercise 5.6 7.46 Solution to Exercise 5.7 7.47 Solution to Exercise 5.8 7.48 Solution to Exercise 5.9 7.48.1 Preparations 7.48.2 Solving Exercise 5.9 7.48.3 Some consequences 7.49 Solution to Exercise 5.10 7.50 Solution to Exercise 5.11 7.51 Solution to Exercise 5.12 7.52 Solution to Exercise 5.13 7.53 Solution to Exercise 5.14 7.54 Solution to Exercise 5.15 7.55 Solution to Exercise 5.16 7.55.1 The “moving lemmas” 7.55.2 Solving Exercise 5.16 7.55.3 A particular case 7.56 Solution to Exercise 5.17 7.57 Solution to Exercise 5.18 7.58 Solution to Exercise 5.19 7.59 Solution to Exercise 5.20 7.60 Solution to Exercise 5.21 7.61 Solution to Exercise 5.22 7.62 Solution to Exercise 5.23 7.63 Solution to Exercise 5.24 7.64 Solution to Exercise 5.25 7.65 Solution to Exercise 5.27 7.66 Solution to Exercise 5.28 7.67 Solution to Exercise 5.29 page 686 686 690 700 708 711 715 717 717 720 724 730 742 742 743 743 743 743 746 746 753 754 757 761 763 765 773 793 797 797 799 803 804 813 822 838 850 863 881 885 888 895 908 919 Notes on the combinatorial fundamentals of algebra 7.68 7.69 7.70 7.71 7.72 7.73 7.74 7.75 7.76 7.77 7.78 7.79 7.80 7.81 7.82 7.83 7.84 7.85 7.86 Solution to Exercise 6.1 Solution to Exercise 6.2 Solution to Exercise 6.3 Solution to Exercise 6.4 Solution to Exercise 6.5 Solution to Exercise 6.6 Solution to Exercise 6.7 Solution to Exercise 6.8 Solution to Exercise 6.9 Solution to Exercise 6.10 Solution to Exercise 6.11 Solution to Exercise 6.12 Solution to Exercise 6.13 Solution to Exercise 6.14 Solution to Exercise 6.15 Solution to Exercise 6.16 Solution to Exercise 6.17 Solution to Exercise 6.18 Solution to Exercise 6.19 7.86.1 The solution 7.86.2 Solution to Exercise 6.18 7.87 Solution to Exercise 6.20 7.88 Second solution to Exercise 6.16 7.89 Solution to Exercise 6.21 7.90 Solution to Exercise 6.22 7.91 Solution to Exercise 6.23 7.92 Solution to Exercise 6.24 7.93 Solution to Exercise 6.25 7.94 Solution to Exercise 6.26 7.95 Solution to Exercise 6.27 7.96 Solution to Exercise 6.28 7.97 Solution to Exercise 6.29 7.98 Solution to Exercise 6.30 7.99 Second solution to Exercise 6.6 7.100.Solution to Exercise 6.31 7.101.Solution to Exercise 6.33 7.102.Solution to Exercise 6.34 7.102.1.Lemmas 7.102.2.The solution 7.102.3.Addendum: a simpler variant 7.102.4.Addendum: another sum of Vandermonde determinants 7.102.5.Addendum: analogues involving products of all but one x j 7.103.Solution to Exercise 6.35 7.104.Solution to Exercise 6.36 page 929 934 941 942 943 945 947 956 958 962 964 966 967 982 986 997 1005 1015 1016 1016 1020 1035 1037 1039 1047 1051 1056 1061 1064 1066 1073 1078 1081 1083 1084 1089 1096 1097 1104 1106 1107 1109 1131 1132 Notes on the combinatorial fundamentals of algebra 7.105.Solution to Exercise 6.37 7.106.Solution to Exercise 6.38 7.107.Solution to Exercise 6.39 7.108.Solution to Exercise 6.40 7.109.Solution to Exercise 6.41 7.110.Solution to Exercise 6.42 7.111.Solution to Exercise 6.43 7.112.Solution to Exercise 6.44 7.113.Solution to Exercise 6.45 7.114.Solution to Exercise 6.46 7.115.Solution to Exercise 6.47 7.116.Solution to Exercise 6.48 7.117.Solution to Exercise 6.49 7.118.Solution to Exercise 6.50 7.119.Solution to Exercise 6.51 7.120.Solution to Exercise 6.52 7.121.Solution to Exercise 6.53 7.122.Solution to Exercise 6.54 7.123.Solution to Exercise 6.55 7.123.1.Solving the exercise 7.123.2.Additional observations 7.124.Solution to Exercise 6.56 7.124.1.First solution 7.124.2.Second solution 7.124.3.Addendum 7.125.Solution to Exercise 6.57 7.126.Solution to Exercise 6.59 7.127.Solution to Exercise 6.60 Appendix: Old citations page 1133 1134 1135 1145 1155 1157 1163 1166 1184 1191 1198 1201 1205 1211 1224 1228 1239 1241 1254 1254 1267 1269 1269 1274 1285 1286 1297 1310 1318 Introduction 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 Notes on the combinatorial fundamentals of algebra page 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 in a rigorous way.) These notes are split into several chapters: • Chapter 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 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 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 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 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 is a comprehensive introduction to determinants of square matrices over a commutative ring1 , 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” trick2 (This means that all proofs are done through The notion of a commutative ring is defined (and illustrated with several examples) in Section 6.1, but I don’t delve deeper into abstract algebra This refers to the standard trick used for proving determinant identities (and other polynomial identities), in which one first replaces the entries of a matrix (or, more generally, the variables appearing in the identity) by indeterminates, then uses the “genericity” of these indeterminates (e.g., to invert the matrix, or to divide by an expression that could otherwise be 0), and finally substitutes the old variables back for the indeterminates Notes on the combinatorial fundamentals of algebra page 10 combinatorics and manipulation of sums – a rather restrictive requirement!) This is a conscious and (to a large extent) aesthetic choice on my part, and I not consider it the best way to learn about determinants; but I regard it as a road worth charting, and these notes are my attempt at doing so 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 I have not meant these notes to be a textbook on any particular subject For one thing, their content does not map to any of the standard university courses, but rather straddles various subjects: • Much of Chapter (on binomial coefficients) and Chapter (on permutations) is seen in a typical combinatorics class; but my focus is more on the algebraic side and not so much on the combinatorics • Chapter studies determinants far beyond what a usual class on linear algebra would do; but it does not include any of the other topics of a linear algebra class (such as row reduction, vector spaces, linear maps, eigenvectors, tensors or bilinear forms) • Being devoted to mathematical induction, Chapter appears to cover the same ground as a typical “introduction to proofs” textbook or class (or at least one of its main topics) In reality, however, it complements rather than competes with most “introduction to proofs” texts I have seen; the examples I give are (with a few exceptions) nonstandard, and the focus different • While the notions of rings and groups are defined in Chapter 6, I cannot claim to really be doing any abstract algebra: I am merely working in rings (i.e., working with matrices over rings), rather than working with rings Nevertheless, Chapter might help familiarize the reader with these concepts, facilitating proper learning of abstract algebra later on All in all, these notes are probably more useful as a repository of detailed proofs than as a textbook read cover-to-cover Indeed, one of my motives in writing them was to have a reference for certain folklore results – particularly one that could convince people that said results not require any advanced abstract algebra to prove These notes began as worksheets for the PRIMES reading project I have mentored in 2015; they have since been greatly expanded with new material (some of it originally written for my combinatorics classes, some in response to math.stackexchange questions) The notes are in flux, and probably have their share of misprints I thank Anya Zhang and Karthik Karnik (the two students taking part in the 2015 PRIMES ... said, mathematicians often show some nuance by using one of them and not the other However, we not need to concern ourselves with this here Notes on the combinatorial fundamentals of algebra. .. for s ∈ X, and the other consisting of the as for s ∈ Y), then take the sum of each of these two sub-bunches, and finally add together the two sums For a rigorous proof of (3), see Theorem 2.130... inverses of f , then g1 = g2 In other words, any two inverses of f must be equal In other words, if an inverse of f exists, then it is unique Notes on the combinatorial fundamentals of algebra