The Hafnian master theorem

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Determinants, permanents, traces, other special matrix functions (15A15) Toeplitz, Cauchy, and related matrices (15B05)

Review text

The permanent of a square matrix \(A=(a_{ij})_{1 \le i,j \le n}\) is defined as \[\operatorname{per} A= \sum_{\sigma \in S_n} a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{n \sigma(n)},\] where the sum extends over all elements \(\sigma\) of the symmetric group \(S_n\). The famous master theorem by \textit{P. A. MacMahon} [Combinatory analysis. Vol. 2. Cambridge: Univ. Press (1915; JFM 46.0118.07)] can be formulated as follows: Let \(Z\) be the diagonal matrix with diagonal entries \(z_1,z_2,\dots\). If we expand \((\det (I-ZA))^{-1}\) in terms of \(z_j\)'s, then the coefficients are given as permanents with matrix entries from \(A\). In this article, an extension of that formula involving Hafnians is obtained. The Hafnian of a symmetric matrix \(S=(s_{ij})_{1 \le i,j \le 2m}\) is defined as \[ \operatorname{Hf} S= \frac{1}{2^m m!} \sum_{\sigma \in S_{2m}} s_{\sigma(1) \sigma(2)} s_{\sigma(3) \sigma(4)} \dots s_{\sigma(2m-1) \sigma(2m)}. \] This is the sign-less version of the Pfaffian. The main theorem in this article states that all coefficients of \(z_j\)'s in the expansion of \((\det(I-\mathbf{Z} S))^{-1/2}\) are given by Hafnians. Here \(\mathbf{Z}\) is the direct sum of matrices \(\left(\begin{smallmatrix} 0 & z_j \\ z_j & 0 \end{smallmatrix}\right)\). An alternative extension of the master theorem was studied in [\textit{S. Matsumoto}, Linear Algebra Appl. 403, 369--398 (2005; Zbl 1077.15008)].

Recommendations

Cites work

Cited in

(3)

This page was built for publication: The Hafnian master theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2158281)