Communicated by Notices Associate Editor Steven Sam
1. Introduction
Every compact topological group supports a unique translation invariant probability measure on its Borel sets — the Haar measure. The Haar measure was first constructed for certain families of compact matrix groups by Hurwitz in the nineteenth century in order to produce invariants of these groups by averaging their actions. Hurwitz’s construction has been reviewed from a modern perspective by Diaconis and Forrester, who argue that it should be regarded as the starting point of modern random matrix theory DF17. An axiomatic construction of Haar measures in the more general context of locally compact groups was published by Haar in the 1930s, with further important contributions made in work of von Neumann, Weil, and Cartan; see Bou04. The existence of recent works on the Haar measure, see, e.g., DS14 or Mec19, can be seen as a token of the timeliness of this object as a modern research topic.
Given a measure, one wants to integrate. The Bochner integral for continuous functions $F$ on a compact group $\mathrm{G}$ taking values in a given Banach space is called the Haar integral; it is almost always written simply
with no explicit notation for the Haar measure. While integration on groups is a concept of fundamental importance in many parts of mathematics, including functional analysis and representation theory, probability, and ergodic theory, etc., the actual computation of Haar integrals is a problem which has received curiously little attention. As far as the authors are aware, it was first considered by theoretical physicists in the 1970s in the context of nonabelian gauge theories, where the issue of evaluating — or at least approximating — Haar integrals plays a major role. In particular, the physics literature on quantum chromodynamics, the main theory of strong interactions in particle physics, is littered with so-called “link integrals,” which are Haar integrals of the form
where $\mathrm{U}(N)$ is the compact group of unitary matrices $U=[U_{xy}]_{x,y=1}^N.$ Confronted with a paucity of existing mathematical tools for the evaluation of such integrals, physicists developed their own methods, which allowed them to obtain beautiful explicit formulas such as
an evaluation which holds for all unitary groups of rank $N \geq 3.$ Although exceedingly clever, the bag of tricks for evaluating Haar integrals assembled by physicists is ad hoc and piecemeal, lacking the unity and coherence which are the hallmarks of a mathematical theory.
The missing theory of Haar integrals began to take shape in the early 2000s, driven by an explosion of interest in random matrix theory. The basic Hilbert spaces of random matrix theory are $L^2(\mathrm{H}(N),\text{Gauss})$ and $L^2(\mathrm{U}(N),\text{Haar}),$ where $\mathrm{H}(N)$ is the noncompact abelian group of Hermitian matrices $H=[H_{xy}]_{x,y=1}^N$ equipped with a Gaussian measure of mean $\mu =0$ and variance $\sigma >0$, and $\mathrm{U}(N)$ is the compact nonabelian group of unitary matrices $U=[U_{xy}]_{x,y=1}^N$ equipped with the Haar measure, just as above. Given a probability measure on some set of matrices, the basic goal of random matrix theory is to understand the induced distribution of eigenvalues, which in the selfadjoint case form a random point process on the line, and in the unitary case constitute a random point process on the circle. The moment method in random matrix theory, pioneered by Wigner (Wig58) in the 1950s, is an algebraic approach to this problem. The main idea is to adopt the algebra $\mathcal{S}$ of symmetric polynomials in eigenvalues as a basic class of test functions, and integrate such functions by realizing them as elements of the algebra $\mathcal{A}$ of polynomials in matrix elements, which can then (hopefully) be integrated by leveraging the defining features of the matrix model under consideration. The canonical example is sums of powers of eigenvalues (elements of $\mathcal{S})$, which may be represented as traces of matrix powers (elements of $\mathcal{A}$); more generally, all coefficients of the characteristic polynomial are sums of principal matrix minors.
It is straightforward to see that, in both of the above $L^2$-spaces, the algebra $\mathcal{A}$ of polynomial functions in matrix elements admits the orthogonal decomposition
where $\mathcal{A}^{[d]}$ is the space of homogeneous degree $d$ polynomial functions in matrix elements. Thus, modulo the algebraic issues inherent in transitioning from $\mathcal{S}$ to $\mathcal{A}$, linearity of expectation reduces implementation of the method to computing scalar products of monomials of equal degree, which are expressions of the form
In the Gaussian case, monomial scalar products can be computed systematically using a combinatorial algorithm which physicists call the “Wick formula” and statisticians call the “Isserlis theorem.” This device leverages independence together with the characteristic feature of centered normal distributions — vanishing of all cumulants but the second — to compute Gaussian expectations as polynomials in the variance parameter $\sigma$. The upshot is that scalar products in $L^2(\mathrm{H}(N),\text{Gauss})$ are closely related to the combinatorics of graphs drawn on compact Riemann surfaces, which play the role of Feynman diagrams for selfadjoint matrix-valued field theories. We recommend (Zvo97) as an entry point into the fascinating combinatorics of Wick calculus.
The case of Haar unitary matrices is a priori more complicated: the random variables $\{U_{xy} \colon x,y \in [N]\}$ are identically distributed, thanks to the invariance of Haar measure, but they are also highly correlated, due to the constraint $U^*U=I.$ Moreover, each individual entry follows a complicated law not uniquely determined by its mean and variance. Despite these obstacles, it turns out that, when packaged correctly, the invariance of Haar measure provides everything needed to develop an analogue of Wick calculus for Haar unitary matrices. Moreover, once the correct general perspective has been found, one realizes that it applies equally well to any compact group, and even to compact symmetric spaces and compact quantum groups. The resulting analogue of Wick calculus has come to be known as Weingarten calculus, a name chosen by Collins Col03 to honor the contributions of Donald Weingarten, a physicist whose early work in the subject is of foundational importance.
The Weingarten calculus has matured rapidly over the course of the past decade, and the time now seems right to give a pedagogical account of the subject. The authors are currently preparing a monograph intended to meet this need. In this article, we aim to provide an easily digestible and hopefully compelling preview of our forthcoming work, emphasizing the big picture but still providing some of the important details.
First and foremost, we wish to impart the insight that, like the calculus of Newton and Leibniz, the core of Weingarten calculus is a fundamental theorem which converts a computational problem into a symbolic problem: whereas the usual fundamental theorem of calculus converts the problem of integrating functions on the line into computing antiderivatives, the fundamental theorem of Weingarten calculus converts the problem of integrating functions on groups into computing certain matrices associated to tensor invariants. The fundamental theorem of Weingarten calculus is presented in detail in Section 2.
We then turn to examples illustrating the fundamental theorem in action. We present two detailed case studies: integration on the automorphism group $\mathrm{S}(N)$ of a finite set of size $N$, and integration on the automorphism group $\mathrm{U}(N)$ of $N$-dimensional Hilbert space. These are natural examples, given that the symmetric group and the unitary group are model examples of a finite and infinite compact group, respectively. The $\mathrm{S}(N)$ case, presented in Section 3, is a toy example chosen to illustrate how Weingarten calculus works in an elementary situation where the integrals to which it applies can easily be evaluated from first principles. The $\mathrm{U}(N)$ case, discussed in Section 4, is an example of real interest, and we give a detailed workup showing how Weingarten calculus handles the link integrals of $\mathrm{U}(N)$ lattice gauge theory.
Section 5 gives a necessarily brief discussion of Weingarten calculus for the remaining classical groups, namely the orthogonal group $\mathrm{O}(N)$ and the symplectic group $\mathrm{Sp}(N),$ both of which receive a detailed treatment in a book in preparation by the authors. Finally, Section 6 extols the universality of Weingarten calculus, briefly discussing how it can be transported to compact symmetric spaces and compact quantum groups, and indicating applications in quantum information theory.
2. The Fundamental Theorem
Given a compact group $\mathrm{G}$, a finite-dimensional Hilbert space $\mathcal{H}$ with a specified orthonormal basis $e_1,\dots ,e_N$, and a continuous group homomorphism $U \colon \mathrm{G} \to \mathrm{U}(\mathcal{H})$ from $\mathrm{G}$ to the unitary group of $\mathcal{H}$, let $U_{xy} \colon \mathrm{G} \to \mathbb{C}$ be the corresponding matrix element functionals,
where $d$ ranges over the set $\mathbb{N}$ of positive integers, and the multi-indices $i,j$ range over the set $\operatorname {Fun}(d,N)$ of functions from $[d]=\{1,\dots ,d\}$ to $[N]=\{1,\dots ,N\}$. Clearly, if we can compute all Weingarten integrals $I_{ij}$, then we can integrate any function on $\mathrm{G}$ which is a polynomial in the matrix elements $U_{xy}.$ This is the basic problem of Weingarten calculus: compute the Weingarten integrals of a given unitary representation of a given compact group.
The fundamental theorem of Weingarten calculus addresses this problem by linearizing it. The basic observation is that, for each $d \in \mathbb{N},$ the $N^{2d}$ integrals $I_{ij}$,$i,j \in \operatorname {Fun}(d,N)$, are themselves the matrix elements of a linear operator. Indeed, we have
where $P_{ij} = \langle e_i,P e_j \rangle$ are the matrix elements of the selfadjoint operator
$$\begin{equation*} P = \int _\mathrm{G} U^{\otimes d}(g) \mathrm{d}g \end{equation*}$$
obtained by integrating the unitary operators $U^{\otimes d}(g)$ against Haar measure. The basic problem of Weingarten calculus is thus equivalent to computing the matrix elements of $P \in \operatorname {End}\mathcal{H}^{\otimes d}$, for all $d \in \mathbb{N}.$
This is where the characteristic feature of Haar measure, the invariance
comes into play: it forces $P^2=P.$ Thus $P$ is a selfadjoint idempotent, and as such $P$ orthogonally projects $\mathcal{H}^{\otimes d}$ onto its image, which is the space of $\mathrm{G}$-invariant tensors in $\mathcal{H}^{\otimes d},$
$$\begin{equation*} (\mathcal{H}^{\otimes d})^\mathrm{G} = \{ t \in \mathcal{H}^{\otimes d} \colon U^{\otimes d}(g)t = t \text{ for all }g \in \mathrm{G}\}. \end{equation*}$$
Thus, we see that the basic problem of Weingarten calculus is in fact very closely related to the basic problem of invariant theory, which is to determine a basis for the space of $\mathrm{G}$-invariant tensors in $\mathcal{H}^{\otimes d}$ for all $d \in \mathbb{N}.$
Indeed, suppose we have access to a basis $a_1,\dots ,a_m$ of $(\mathcal{H}^{\otimes d})^{\mathrm{G}}$. Then, by elementary linear algebra, we have everything we need to calculate the matrix
of degree $d$ Weingarten integrals. Let $\mathbf{A}$ be the $N^d \times m$ matrix whose columns are the coordinates of the basic invariants in the desired basis,
familiar from matrix analysis as the multidimensional generalization of the undergraduate “outer product divided by inner product” formula for orthogonal projection onto a line. The $m \times m$ matrix $\mathbf{A}^*\mathbf{A}$ is nothing but the Gram matrix
of the basic $\mathrm{G}$-invariants in $\mathcal{H}^{\otimes d}$, whose linear independence is equivalent to the invertibility of the Gram matrix. Let us give the inverse Gram matrix a name: we call
the Weingarten matrix of the invariants $a_1,\dots ,a_m.$ Extracting matrix elements on either side of the factorization $\mathbf{P}=\mathbf{A}\mathbf{W}\mathbf{A}^*$, we obtain the Fundamental Theorem of Weingarten Calculus.
Does Theorem 2.1 actually solve the basic problem of Weingarten calculus? Yes, insofar as the classical fundamental theorem of calculus solves the problem of computing definite integrals: it reduces a numerical problem to a symbolic problem. In order to apply the fundamental theorem of calculus to integrate a given function, one must find its antiderivative, and as every student of calculus knows this can be a wild ride. In order to use the fundamental theorem of Weingarten calculus to compute the Weingarten integrals of a given unitary representation, one must solve a souped-up version of the basic problem of invariant theory which involves not only finding basic tensor invariants, but computing their Weingarten matrices. Just like the computation of antiderivatives, this may prove to be a difficult task.
3. The Symmetric Group
In this Section, we consider a toy example. Fix $N \in \mathbb{N},$ and let $\mathrm{S}(N)$ be the symmetric group of rank $N,$ viewed as the group of bijections $g \colon [N] \to [N].$ This is a finite group, its topology and resulting Haar measure are discrete, and all Haar integrals are finite sums. We will solve the basic problem of Weingarten calculus for the permutation representation of $\mathrm{S}(N)$ in two ways: using elementary combinatorial reasoning, and using the fundamental theorem of Weingarten calculus. It is both instructive and psychologically reassuring to work through the two approaches and see that they agree.
The permutation representation of $\mathrm{S}(N)$ is the unitary representation $(\mathcal{H},U)$ in which $\mathcal{H}$ is an $N$-dimensional Hilbert space with orthonormal basis $e_1,\dots ,e_N,$ and $U \colon \mathrm{S}(N) \to \mathrm{U}(\mathcal{H})$ is defined by
$$\begin{equation*} U(g)e_x = e_{g(x)}, \quad x \in [N]. \end{equation*}$$
The corresponding system of matrix elements $U_{xy} \colon \mathrm{S}(N) \to \mathbb{C}$ is given by
Thus, $N! I_{ij}$ simply counts permutations $g \in \mathrm{S}(N)$ which solve the equation $g^{-1}i=j.$ This is an elementary counting problem, and a good way to solve it is to think of the given functions $i,j \in \operatorname {Fun}(d,N)$ “backwards,” as the ordered lists of their fibers:
Clearly, such a permutation exists if and only if the fibers of $i$ and $j$ are the same up to the labels of their base points, which is the case if and only if
where $\mathsf{type}(i)$ is the partition of $[d]$ obtained by forgetting the order on the fibers of $i$ and throwing away empty fibers. The permutations we wish to count thus number
Let us now evaluate $I_{ij}$ using the Fundamental Theorem of Weingarten Calculus. The first step is to solve the basic problem of invariant theory for the representation $(\mathcal{H},U).$ This is again straightforward. Fix $d \in \mathbb{N},$ let $\mathsf{Par}_N(d)$ denote the set of partitions of $[d]$ with at most $N$ blocks, and to each $\mathsf{p} \in \mathsf{Par}_N(d)$ associate the tensor
where $e_i = e_{i(1)} \otimes \dots \otimes e_{i(d)} \in \mathcal{H}^{\otimes d}.$ It is apparent that the set $\{a_{\mathsf{p}} : \mathsf{p} \in \mathsf{Par}_N(d)\}$ is a basis of $(\mathcal{H}^{\otimes d})^{\mathrm{S}(N)}$. Indeed, taking the unit tensor
which is clearly $\mathrm{S}(N)$-invariant, and moreover it is clear that every $\mathrm{S}(N)$-invariant tensor in $\mathcal{H}^{\otimes d}$ is a linear combination of tensors of this form. Furthermore,