Harmonic analysis on finite groups: representation theory, Gelfand pairs and Markov chains

Tullio Ceccherini-Silberstein, Fabio Scarabotti, Filippo Tolli0521883369, 9780521883368, 9780511388811

Starting from a few concrete problems such as random walks on the discrete circle and the finite ultrametric space, this book develops the necessary tools for the asymptotic analysis of these processes. Its topics range from the basic theory needed for students new to this area, to advanced topics such as the theory of Green’s algebras, the complete analysis of the random matchings, and a presentation of the presentation theory of the symmetric group. This self-contained, detailed study culminates with case-by-case analyses of the cut-off phenomenon discovered by Persi Diaconis.

---

Table of contents :
Cover……Page 1
Half-title……Page 3
Series-titles……Page 4
Title……Page 5
Copyright……Page 6
Contents……Page 9
Preface……Page 13
Part I Preliminaries, examples and motivations……Page 17
1.1 Preliminaries and notation……Page 19
1.2 Four basic examples……Page 20
1.3 Markov chains……Page 26
1.4 Convergence to equilibrium……Page 34
1.5 Reversible Markov chains……Page 37
1.6 Graphs……Page 42
1.7 Weighted graphs……Page 44
1.8 Simple random walks……Page 49
1.9 Basic probabilistic inequalities……Page 53
1.10 Lumpable Markov chains……Page 57
2.1 Harmonic analysis on finite cyclic groups……Page 62
2.2 Time to reach stationarity for the simple random walk on the discrete circle……Page 71
2.3 Harmonic analysis on the hypercube……Page 74
2.4 Time to reach stationarity in the Ehrenfest diffusion model……Page 77
2.5 The cutoff phenomenon……Page 82
2.6 Radial harmonic analysis on the circle and the hypercube……Page 85
Part II Representation theory and Gelfand pairs……Page 91
3.1 Group actions……Page 93
3.3 Unitary representations……Page 99
3.4 Examples……Page 103
3.5 Intertwiners and Schur’s lemma……Page 104
3.6 Matrix coefficients and their orthogonality relations……Page 105
3.7 Characters……Page 108
3.8 More examples……Page 112
3.9 Convolution and the Fourier transform……Page 114
3.10 Fourier analysis of random walks on finite groups……Page 119
3.11 Permutation characters and Burnside’s lemma……Page 121
3.12 An application: the enumeration of finite graphs……Page 123
3.13 Wielandt’s lemma……Page 126
3.14 Examples and applications to the symmetric group……Page 129
4 Finite Gelfand pairs……Page 133
4.1 The algebra of bi-K-invariant functions……Page 134
4.2 Intertwining operators for permutation representations……Page 136
4.3 Finite Gelfand pairs: definition and examples……Page 139
4.4 A characterization of Gelfand pairs……Page 141
4.5 Spherical functions……Page 143
4.6 The canonical decomposition of L(X) via spherical functions……Page 148
4.7 The spherical Fourier transform……Page 151
4.8 Garsia’s theorems……Page 156
4.9 Fourier analysis of an invariant random walk on X……Page 159
5.1 Harmonic analysis on distance-regular graphs……Page 163
5.2 The discrete circle……Page 177
5.3 The Hamming scheme……Page 178
5.4 The group-theoretical approach to the Hammming scheme……Page 181
6.1 The Johnson scheme……Page 184
6.2 The Gelfand pair (Sn, Sn-m × Sm) and the associated intertwining functions……Page 192
6.3 Time to reach stationarity for the Bernoulli–Laplace diffusion model……Page 196
6.4 Statistical applications……Page 200
6.5 The use of Radon transforms……Page 203
7.1 The rooted tree Tq,n……Page 207
7.2 The group Aut(Tq,n) of automorphisms……Page 208
7.3 The ultrametric space……Page 210
7.4 The decomposition of the space L(Σn) and the spherical functions……Page 212
7.5 Recurrence in finite graphs……Page 215
7.6 A Markov chain on Σn……Page 218
Part III Advanced theory……Page 223
8.1 Generalities on posets……Page 225
8.2 Spherical posets and regular semi-lattices……Page 232
8.3 Spherical representations and spherical functions……Page 238
8.4 Spherical functions via Moebius inversion……Page 245
8.5 q-binomial coefficients and the subspaces of a finite vector space……Page 255
8.6 The q-Johnson scheme……Page 259
8.7 A q-analog of the Hamming scheme……Page 267
8.8 The nonbinary Johnson scheme……Page 273
9.1 Tensor products……Page 283
9.2 Representations of abelian groups and Pontrjagin duality……Page 290
9.3 The commutant……Page 292
9.4 Permutation representations……Page 295
9.5 The group algebra revisited……Page 299
9.6 An example of a not weakly symmetric Gelfand pair……Page 307
9.7 Real, complex and quaternionic representations: the theorem of Frobenius and Schur……Page 310
9.8 Greenhalgebras……Page 320
9.9 Fourier transform of a measure……Page 330
10.1 Preliminaries on the symmetric group……Page 335
10.2 Partitions and Young diagrams……Page 338
10.3 Young tableaux and the Specht modules……Page 341
10.4 Representations corresponding to transposed tableaux……Page 349
10.5 Standard tableaux……Page 351
10.6 Computation of a Fourier transform on the symmetric group……Page 359
10.7 Random transpositions……Page 364
10.8 Differential posets……Page 374
10.9 James’ intersection kernels theorem……Page 381
11.1 The Gelfand pair (S2n, S2 Sn)……Page 387
11.2 The decomposition of L(X) into irreducible components……Page 389
11.3 Computing the spherical functions……Page 390
11.4 The first nontrivial value of a spherical function……Page 391
11.5 The first nontrivial spherical function……Page 392
11.6 Phylogenetic trees and matchings……Page 394
11.7 Random matchings……Page 396
Appendix 1 The discrete trigonometric transforms……Page 408
Appendix 2 Solutions of the exercises……Page 423
Bibliography……Page 437
Index……Page 449