• XAVIER VIENNOT
  • Foreword
    • Preface
    • Introduction
    • Acknowledgements
    • Lectures for wide audience
  • PART I
    • Preface
    • Abstract
    • Contents
    • Ch0 Introduction to the course
    • Ch1 Ordinary generating functions
    • Ch2 The Catalan garden
    • Ch3 Exponential structures and genarating functions
    • Ch4 The n! garden
    • Ch5 Tilings, determinants and non-intersecting paths
    • Lectures related to the course
    • List of bijections
    • Index
  • PART II
    • Preface
    • Abstract
    • Contents
    • Ch1 Commutations and heaps of pieces: basic definitions
    • Ch2 Generating functions of heaps of pieces
    • Ch3 Heaps and paths, flows and rearrangements monoids
    • Ch4 Linear algebra revisited with heaps of pieces
    • Ch5 Heaps and algebraic graph theory
    • Ch6 Heaps and Coxeter groups
    • Ch7 Heaps in statistical mechanics
    • Lectures related to the course
  • PART III
    • Preface
    • Abstract
    • Contents
    • Ch0 overview of the course
    • Ch1 RSK The Robinson-Schensted-Knuth correspondence
    • Ch2 Quadratic algebra, Q-tableaux and planar automata
    • Ch3 Tableaux for the PASEP quadratic algebra
    • Ch4 Trees and tableaux
    • Ch5 Tableaux and orthogonal polynomials
    • Ch6 Extensions: tableaux for the 2-PASEP quadratic algebra
    • Lectures related to the course
    • References, comments and historical notes
  • PART IV
    • Preface
    • Introduction
    • Contents
    • Ch0 Overview of the course
    • Ch1 Paths and moments
    • Ch2 Moments and histories
    • Ch3 Continued fractions
    • Ch4 Computation of the coefficients b(k) lambda(k)
    • Ch5 Orthogonality and exponential structures
    • Ch6 q-analogues
    • Lectures related to the course
    • Complements
    • References
  • Epilogue

The Art of Bijective Combinatorics    Part II
Commutations and heaps of pieces
with interactions in physics, mathematics and computer science

The Institute of Mathematical Sciences, Chennai, India  (January-March 2017)

Ch 4  Linear algebra revisited with heaps of pieces

Ch 4a   Inversion of a matrix, MacMahon Master theorem, Brauer identity for LERW

6 February 2017
slides_Ch4a      (pdf   12 Mo)    
video Ch4a  link to YouTube
video Ch4a  link to bilibili
Inversion of a matrix  4       2:08
recalling the classical formula for the inverse matrix with cofactor and determinant   5     2:16
replacing B by I-A   6     3:22
elementary lemma: paths and inversion of (I-A)   7     4:16
recalling the bijection khi between paths and heaps   8-9     6:42
applying the inversion lemma   10-11     9:02

proposition: expression of the generating function for weighted paths as the ratio N_i,j / D   12     11:33

elementary exercise: expressing the determinant of (I-A)   13     12:18
expressing the cofactor (i,j) of the numerator   14     15:26
end of the proof of the main proposition    15     17:12
discussion about this proof   17:34
Examples   16     26:24
transition matrix methodology in physics   17     26:31
        bounded Dyck paths   18     27:25
generating function for bounded Dyck paths   19-20     27:57
discussion      29:35
reminding the Fibonacci polynomials   21    37:25
semi-pyramids of dimers on a segment   22     37:55
generating function for Fibonacci polynomials   23-24     38:10
        exercise: directed paths on the square lattice  25-26     47:11
MacMahon Master theorem  27      50:54
        inversion lemma: heaps of cycles   31      52:13
        heaps of cycles and rearrangements  38        53:00
        MacMahon formulation    40-41     54:19
        relation with quivers and gauge theory in physics  42     1:01:02
Complements: an identity of Bauer for loop-erased random walks  43     1:03:14
Bauer's identity   46     1:05:40
proof of Bauer's identity   47-52     1:09:09
        research problem: substitution in heaps  53       1:14:52
the end  54   1:17:16

Ch 4b   Jacobi identity, 2nd proof with exponential generating function, β-extension of MacMahon Master theorem, Cayley-Hamilton theorem

9 February 2017
slides_Ch4b    (pdf     19 Mo)  
video Ch4b  link to YouTube
video Ch4b  link to bilbili
Correction to exercise 3, p65, Ch3b    3       0:09
From the previous lecture  4     2:17
From Ch2d: the logarithmic lemma   10      4:38
        a paradox ?    16         8:33
Proof of Jacobi identity   17      11:04
Jacobi identity with exponential generating function   25    19:26
condition (m) for an assemblée of labeled pyramids   31     26:19
going back to Part I, Ch3a with the example of a permutation (in cycle notation)    36:10
        discussion  on species, labeled pyramids and exponential generating functions     38:25
        end of discussion and end of the proof of Jacobi identity    42:04
Beta extension of MacMahon Master theorem   35      44:42
Cayley-Hamilton theorem  42     49:05
        another weight preserving involution  53       1:05:03
Complement and exercise: a general transfer theorem  57     1:07:40
       exercise   62     1:14:44
Next lecture: Jacobi duality   63      1:16:25
The end  65    1:17:42

Ch 4c   Jacobi dual identity, extension of LGV Lemma with heaps, relation with Fomin's theorem on LERW

13 February
slides_Ch4c     (pdf  23 Mo)      
video Ch4c  link to YouTube
video Ch4c  link to bilibili
Jacobi duality   4       0:48
the classical relation between the minors of a matrix and the minors of its inverse   5     0:56
        the main theorem   6      2:14
applying the inversion lemma from the main theorem   7-8     9:03
special case 1:  I and J have only one element   9        10:53
        deducing Jacobi identity from the main theorem   13-17     12:52
        a Lemma expressing minors  14      13:29
end of the combinatorial proof of Jacobi duality   17     17:20
        an example  18      17:32
Special case 2: no cycles  23      20:26
The LGV  Lemma (from the course IMSc 2016, Ch5a)   25        21:07
the crossing condition   30     23:08
the LGV Lemma with the crossing condition   31     24:08
A simple example   34      25:24
Another example: binomial determinants   38      26:50
Proof of the LGV  Lemma  48        30:28
the LGV Lemma in its general form   54     33:52
Proof of the main theorem: introduction  55      34:32
Visualization of the main theorem   60-61     37:11
Visualiation of what must be done in order to prove the main theorem   62     38:06
        how to handle this mixture of cycles, an idea coming from physics:
                    discussion for defining a simultaneous loop-erased process       38:34
        the problem for defining the involution  64      40:50
Proof of the main theorem: first step with Fomin theorem  65       41:45
Fomin's theorem   67      42:42
Proof of the main theorem: second step  75       51:15
another proposition   76     51:26
        end of the proof  78       
other proof using Grassmann algebra and integral related fo physics (Carrozza, Krajewski, Tanasa)   79     58:38
        another way to prove the Jacobi duality identity (Lalonde, Talaska)   80     59:07
Crossing condition   87     1:02:31
main theorem with crossing condition   89     1:02:46
a funny example with paths on the square lattice   91     1:03:55
The end  (of the video)   92     1:10:44
About the terminology  «LGV Lemma»  92    (not in the video)
The end  98
Corrections: