Skip to Main Content

The Weingarten Calculus

Benoît Collins
Sho Matsumoto
Jonathan Novak

Communicated by Notices Associate Editor Steven Sam

Article cover

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 on a compact group 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 is the compact group of unitary matrices 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 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 and where is the noncompact abelian group of Hermitian matrices equipped with a Gaussian measure of mean and variance , and is the compact nonabelian group of unitary matrices 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 of symmetric polynomials in eigenvalues as a basic class of test functions, and integrate such functions by realizing them as elements of the algebra 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 , which may be represented as traces of matrix powers (elements of ); 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 -spaces, the algebra of polynomial functions in matrix elements admits the orthogonal decomposition

where is the space of homogeneous degree polynomial functions in matrix elements. Thus, modulo the algebraic issues inherent in transitioning from to , linearity of expectation reduces implementation of the method to computing scalar products of monomials of equal degree, which are expressions of the form

and

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 . The upshot is that scalar products in 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 are identically distributed, thanks to the invariance of Haar measure, but they are also highly correlated, due to the constraint 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 of a finite set of size , and integration on the automorphism group of -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 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 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 lattice gauge theory.

Section 5 gives a necessarily brief discussion of Weingarten calculus for the remaining classical groups, namely the orthogonal group and the symplectic group 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 , a finite-dimensional Hilbert space with a specified orthonormal basis , and a continuous group homomorphism from to the unitary group of , let be the corresponding matrix element functionals,

The Weingarten integrals of the unitary representation are the integrals

where ranges over the set of positive integers, and the multi-indices range over the set of functions from to . Clearly, if we can compute all Weingarten integrals , then we can integrate any function on which is a polynomial in the matrix elements 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 the integrals , , are themselves the matrix elements of a linear operator. Indeed, we have

where

is the orthonormal basis of corresponding to the specified orthonormal basis in , and

are the matrix elements of the unitary operator in this basis. We thus have that

where are the matrix elements of the selfadjoint operator

obtained by integrating the unitary operators against Haar measure. The basic problem of Weingarten calculus is thus equivalent to computing the matrix elements of , for all

This is where the characteristic feature of Haar measure, the invariance

comes into play: it forces Thus is a selfadjoint idempotent, and as such orthogonally projects onto its image, which is the space of -invariant tensors in

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 -invariant tensors in for all

Indeed, suppose we have access to a basis of . Then, by elementary linear algebra, we have everything we need to calculate the matrix

of degree Weingarten integrals. Let be the matrix whose columns are the coordinates of the basic invariants in the desired basis,

Then we have the matrix factorization

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 matrix is nothing but the Gram matrix

of the basic -invariants in , 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 Extracting matrix elements on either side of the factorization , we obtain the Fundamental Theorem of Weingarten Calculus.

Theorem 2.1.

For any and we have

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 and let be the symmetric group of rank viewed as the group of bijections 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 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 is the unitary representation in which is an -dimensional Hilbert space with orthonormal basis and is defined by

The corresponding system of matrix elements is given by

We will evaluate the Weingarten integrals of

Each Weingarten integral is a finite sum with terms, each equal to zero or one:

Thus, simply counts permutations which solve the equation This is an elementary counting problem, and a good way to solve it is to think of the given functions “backwards,” as the ordered lists of their fibers:

The fiber fingerprint of the composite function is then

and so we have if and only if

Clearly, such a permutation exists if and only if the fibers of and are the same up to the labels of their base points, which is the case if and only if

where is the partition of obtained by forgetting the order on the fibers of and throwing away empty fibers. The permutations we wish to count thus number

in total, where denotes the number of blocks of the set partition . We conclude that the integral is given by

Let us now evaluate using the Fundamental Theorem of Weingarten Calculus. The first step is to solve the basic problem of invariant theory for the representation This is again straightforward. Fix let denote the set of partitions of with at most blocks, and to each associate the tensor

where It is apparent that the set is a basis of . Indeed, taking the unit tensor

corresponding to a function and symmetrizing it using the action of permutations on multi-indices produces the tensor

which is clearly -invariant, and moreover it is clear that every -invariant tensor in is a linear combination of tensors of this form. Furthermore,

so that the distinct invariants produced by symmetrization of the initial basis in are

These tensors are pairwise orthogonal: for any , we have

So, the Gram matrix of the basis