Brauer, BMW, and Partition Diagram Algebras

A symmetric bilinear form on a finite-dimensional $k$-space has a basis with diagonal matrix: if the form is nonzero, polarization in characteristic different from two gives a vector $v$ with $B(v,v)\mathrm{\ne }0$; scale $v$ to norm one using a square root in $k$, split off $kv$ and induct on its orthogonal complement. For an alternating form, choose nonzero $v$, choose $w$ with $B(v,w)=1$, split off the nondegenerate plane they span, and induct on its orthogonal complement. Applying the same argument after quotienting by the radical shows that any rank-$r$ symmetric matrix is congruent to $\mathrm{diag}(I_r,0)$ and any rank-$r$ alternating matrix is congruent to $J_r\oplus 0$, with $r$ even in the latter case.

Conversely, every Gram matrix has rank at most $\dim V$, since it factors through the linear map $k^t\to V$ whose columns are the chosen vectors. For every canonical rank-$r$ matrix in step 1.1, choose $r$ vectors in $V$ giving that standard form and set the remaining vectors to zero. If $S$ is an invertible $t\times t$ matrix satisfying $S^{\mathsf{T}}GS=C$ for an arbitrary rank-$r$ matrix $G$ and its canonical matrix $C$, multiplying the chosen tuple by $S^{-1}$ gives Gram matrix $G$. This realizes every matrix in the rank-bounded image.

Let $f_1,f_2:k^t\to V$ be the surjective maps defined by two tuples with the same rank-$m$ Gram matrix $G$. For $c\in k^t$, $f_i(c)=0$ implies $Gc=0$; conversely $Gc=0$ implies $B(f_i(c),f_i(d))=0$ for every $d$, and surjectivity plus nondegeneracy gives $f_i(c)=0$. Thus $\ker f_1=\ker f_2$, so $T(f_1(c))=f_2(c)$ is a well-defined linear isomorphism. The equality of Gram matrices makes $T$ preserve the form. It is the unique isometry carrying the first tuple to the second, and a form-preserving map fixing a spanning tuple is the identity.

A rank-$r$ symmetric matrix is equivalent to its kernel, a $(t-r)$-plane, and a nondegenerate symmetric form on the $r$-dimensional quotient. The finitely many standard graph charts cover the Grassmannian of $(t-r)$-planes, and each chart has $r(t-r)$ coordinates. Over such a chart, symmetric forms on the quotient have $r(r+1)\mathrm{/}2$ free coordinates, and nondegeneracy is the nonvanishing of the determinant, an open condition. Thus this stratum has dimension $r(t-r)+r(r+1)\mathrm{/}2=rt-r(r-1)\mathrm{/}2$. In the alternating case the form space has dimension $r(r-1)\mathrm{/}2$ and nondegeneracy is again open, so the stratum dimension is $r(t-r)+r(r-1)\mathrm{/}2=rt-r(r+1)\mathrm{/}2$.

Each indicated minor is multihomogeneous, with degree ${\sum }_{i\in I}{e}_i+{\sum }_{j\in J}{e}_j$. If $I\cap J\mathrm{\ne }\mathrm{\varnothing }$, some label has degree at least $2e_i$, so multiplying by any polynomial with nonnegative multidegrees cannot produce degree $(1,\dots ,1)$. If $I$ and $J$ are disjoint, the complementary multidegree is one copy of $e_a$ for each unused label; its monomials are exactly products of off-diagonal variables over perfect matchings of those labels. Since the ideal component is a sum of homogeneous generator multiples, these are precisely its spanning elements.

A Pfaffian generator on $S$ already has multidegree ${\sum }_{i\in S}{e}_i$, because every term uses each label of $S$ once. Its complementary multidegree is therefore one copy of $e_a$ for each label outside $S$, whose monomials are exactly the stated perfect-matching products. Homogeneity of the generated ideal gives both inclusions and proves the Pfaffian assertion.

We first give a finite interval bijection. Fix partitions $\lambda ,\rho$. Common lower interlacers $\mu \prec \lambda ,\rho$ have independent coordinates $\max ({\lambda }_{i+1},{\rho }_{i+1})\le {\mu }_i\le \min ({\lambda }_i,{\rho }_i)$. If one interval is empty, there are no common upper interlacers either. Otherwise, from such a $\mu$ and an integer $a\ge 0$, set ${\nu }_1=\max ({\lambda }_1,{\rho }_1)+a$ and ${\nu }_{i+1}=\max ({\lambda }_{i+1},{\rho }_{i+1})+\min ({\lambda }_i,{\rho }_i)-{\mu }_i$. These are precisely the independent intervals for a common upper interlacer $\lambda ,\rho \prec \nu$, with its first coordinate unbounded above. The coordinates form a partition since successive intervals are separated by $\max ({\lambda }_{i+1},{\rho }_{i+1})\ge \min ({\lambda }_{i+1},{\rho }_{i+1})$. The inverse recovers $a$ from ${\nu }_1$ and reverses each finite interval. Summing the coordinates gives $\mathrm{\mid }\nu \mathrm{\mid }+\mathrm{\mid }\mu \mathrm{\mid }=\mathrm{\mid }\lambda \mathrm{\mid }+\mathrm{\mid }\rho \mathrm{\mid }+a$.

On the vector space with partitions as basis define $U_x\lambda ={\sum }_{\lambda \prec \nu }{x}^{\mathrm{\mid }\nu \mathrm{\mid }-\mathrm{\mid }\lambda \mathrm{\mid }}\nu$ and $D_y\lambda ={\sum }_{\mu \prec \lambda }{y}^{\mathrm{\mid }\lambda \mathrm{\mid }-\mathrm{\mid }\mu \mathrm{\mid }}\mu$, interpreted coefficientwise in formal power series. The coefficient from $\lambda$ to $\rho$ in $D_y{U}_x$ sums over the common upper interlacers, while that in $U_x{D}_y$ sums over the common lower interlacers. The bijection of step 1.1 gives $x^{\mathrm{\mid }\nu \mathrm{\mid }-\mathrm{\mid }\lambda \mathrm{\mid }}{y}^{\mathrm{\mid }\nu \mathrm{\mid }-\mathrm{\mid }\rho \mathrm{\mid }}=(xy{)}^a{x}^{\mathrm{\mid }\rho \mathrm{\mid }-\mathrm{\mid }\mu \mathrm{\mid }}{y}^{\mathrm{\mid }\lambda \mathrm{\mid }-\mathrm{\mid }\mu \mathrm{\mid }}$. Thus $D_y{U}_x=(1-xy{)}^{-1}{U}_x{D}_y$. All coefficients of prescribed total degree involve only finitely many partitions, so these rearrangements are valid formally.

Let $E$ be the partitions with even parts and let ${\pi }_E$ be the linear functional equal to one on $E$ and zero on the other partition basis vectors. Fix $\lambda$ and put ${\alpha }_i=\lfloor {\lambda }_i\mathrm{/}2\rfloor$, ${\beta }_i=\lceil {\lambda }_i\mathrm{/}2\rceil$. An even upper interlacer $2\theta$ of $\lambda$ is equivalent to a common upper interlacer $\theta$ of $\alpha ,\beta$: its inequalities are ${\theta }_i\ge {\beta }_i$ and ${\theta }_{i+1}\le {\alpha }_i$. Similarly an even lower interlacer $2\eta$ is equivalent to a common lower interlacer $\eta$ of $\alpha ,\beta$, since ${\alpha }_i\ge {\eta }_i\ge {\beta }_{i+1}$. Apply step 1.1 to $\alpha ,\beta$. As $\mathrm{\mid }\alpha \mathrm{\mid }+\mathrm{\mid }\beta \mathrm{\mid }=\mathrm{\mid }\lambda \mathrm{\mid }$, it gives $\mathrm{\mid }2\theta \mathrm{\mid }-\mathrm{\mid }\lambda \mathrm{\mid }=\mathrm{\mid }\lambda \mathrm{\mid }-\mathrm{\mid }2\eta \mathrm{\mid }+2a$. Consequently ${\pi }_E{U}_x=(1-x^2{)}^{-1}{\pi }_E{D}_x$. This includes the case of empty interlacer sets and the empty partition.

A chain $\mathrm{\varnothing }={\lambda }^{(0)}\prec {\lambda }^{(1)}\prec \cdots \prec {\lambda }^{(t)}$ corresponds bijectively to a semistandard tableau: fill ${\lambda }^{(i)}\mathrm{/}{\lambda }^{(i-1)}$ with $i$. The horizontal-strip condition forbids repeated labels in a column; the nested partition condition makes the rows weakly increasing. Conversely the boxes with entries at most $i$ in any such tableau form the required partition. Thus its weight-generating series, restricted to even row lengths, is ${\pi }_E{U}_{x_t}\cdots U_{x_1}\mathrm{\varnothing }$. Apply step 2.2 to the leftmost up operator, then step 2.1 to commute $D_{x_t}$ past each preceding $U_{x_i}$. Since $D_{x_t}\mathrm{\varnothing }=\mathrm{\varnothing }$, this produces the factor $(1-x_t^2{)}^{-1}{\prod }_{i<t}(1-x_i{x}_t{)}^{-1}$ and the same expression with $t-1$ operators. Induction from $t=0$ proves the displayed identity. Substituting all $x_i=q$ gives $(1-q^2{)}^{-t(t+1)\mathrm{/}2}$, whose coefficient of $q^{2d}$ is the stated binomial coefficient by the product expansion counting monomials of degree $d$ in $t(t+1)\mathrm{/}2$ independent variables.

We first prove independence under the Gram substitution in every rank $r\ge 1$. Put $Z=X{X}^{\mathsf{T}}$, where $X=(x_{ic})$ is a generic $t\times r$ matrix, and order variables lexicographically by columns first: $x_{11}>\cdots >x_{t1}>x_{12}>\cdots >x_{tr}$. Cauchy–Binet says $p(A,B)(X{X}^{\mathsf{T}})={\sum }_{C\subseteq [r],\mathrm{\mid }C\mathrm{\mid }=s}\det X_{A,C}\det X_{B,C}$ for $\mathrm{\mid }A\mathrm{\mid }=\mathrm{\mid }B\mathrm{\mid }=s\le r$. For completeness, this identity follows by expanding each entry $z_{ij}={\sum }_c{x}_{ic}{x}_{jc}$ in the Leibniz determinant: group terms by the chosen column indices; repeated indices cancel by pairing permutations exchanging them, and the terms with one fixed set $C$ give the two displayed determinants. A determinant's leading monomial pairs the smallest available row with its first column, then the next row with its next column, recursively. Comparing column sets in this sum, the largest summand has $C=(1,\dots ,s)$. Thus the minor has leading monomial ${\prod }_{c=1}^s{x}_{a_{c}c}{x}_{b_{c}c}$ with coefficient one.

For a standard product, remove empty factors and reverse the sequence of its columns to obtain $B_q,A_q,\dots ,B_1,A_1$. Column lengths are nonincreasing, rows are weakly increasing by the standard-chain inequalities, and columns are strictly increasing. Each column length occurs an even number of times, so all row lengths are even. Conversely a semistandard tableau with even row lengths has an even number of columns of each length: those numbers are consecutive differences of even row lengths. Pairing consecutive equal-height columns and reversing their sequence gives a unique standard product. Finally its Gram leading monomial from step 1.1 records the entries in each tableau row, and weak increase uniquely reconstructs each row from those multiplicities. Distinct standard products with minor sizes at most $r$ therefore have distinct leading monomials and are linearly independent after the rank-$r$ Gram substitution.

Take $r=t$ in step 2.1. A standard product of polynomial degree $d$ corresponds exactly to an even-row tableau with $2d$ boxes and entries in $[t]$. By [F1], the number of these is $\left(\genfrac{}{}{0px}{}{N+d-1}{d}\right)$, where $N=t(t+1)\mathrm{/}2$. This equals the dimension of the degree-$d$ homogeneous part of the polynomial ring in the $N$ entries of $Z$: the monomials $z^e$ are indexed by $e\in {\mathbb{N}}^N$ with $\sum e_{ij}=d$. Step 2.1 proves independence of all these standard products already in this polynomial ring, because a linear relation there would remain a relation under Gram substitution. An independent set of the full finite dimension is a basis. Consequently the standard products of all minor sizes span the polynomial ring in every degree.

We make the resulting identities completely indexed and constructive. Let ${\mathcal{E}}_d=\{e=(e_{ij}{)}_{i\le j}:\sum e_{ij}=d\}$ and let ${\mathcal{T}}_d$ be the standard products of degree $d$, without empty factors; order both finite sets lexicographically in any fixed encoding. For a product $Q={\prod }_{h=1}^{q}p(A_h,B_h)$, with $s_h=\mathrm{\mid }{A}_h\mathrm{\mid }=\mathrm{\mid }{B}_h\mathrm{\mid }$ and ${\sum }_h{s}_h=d$, define $b_e(Q)={\sum }_{{\sigma }_h\in {\mathfrak{S}}_{s_h}}{\prod }_h\mathrm{sgn}({\sigma }_h)$, where the sum is restricted by the following explicit indexing condition: the multiset of unordered pairs $\{\min (a_{hc},b_{h,{\sigma }_h(c)}),\max (a_{hc},b_{h,{\sigma }_h(c)})\}$, over all $h$ and $1\le c\le s_h$, contains $(i,j)$ exactly $e_{ij}$ times. An empty restricted sum is zero. Leibniz expansion gives exactly $Q={\sum }_{e\in {\mathcal{E}}_d}{b}_e(Q)z^e$. Form the square integer matrix $M_d=(b_e(T){)}_{e\in {\mathcal{E}}_d,T\in {\mathcal{T}}_d}$. It is invertible over $\mathbb{Q}$ by step 3.1 applied over an algebraic closure of $\mathbb{Q}$. Since its nonzero determinant is an integer and $k$ has characteristic zero, it is invertible over $k$ as well.

If $M_d[T\leftarrow b(Q)]$ denotes the matrix with column $T$ replaced by $(b_e(Q){)}_e$, the explicit straightening identity is $Q={\sum }_{T\in {\mathcal{T}}_d}(\det M_d[T\leftarrow b(Q)]\mathrm{/}\det M_d)T$. Indeed multiplying the coefficient vector on the right by $M_d$ gives $b(Q)$ by [F2] applied to the finite square matrix $M_d$ over $k$, so its coefficient of each monomial $z^e$ is precisely the coefficient on the left. All sets, entries, signs, and denominators in this identity have been specified by finite ordered index data; no existence of a straightening law is assumed. Applying it once replaces any nonstandard product directly by standard products, so no further nonstandard term is produced and rewriting terminates. For $d=0$ both indexing sets consist of the unit and the matrix is $(1)$.

Return to $0<m<t$. Every minor of size $s\ge m+1$ lies in $I_{m+1}$. Explicitly, for increasing $A,B$ of size $s$, write $A^{\mathrm{\prime }}=\{a_1,\dots ,a_{m+1}\}$. Laplace expansion along those rows is $p(A,B)={\sum }_{C\subseteq B,\mathrm{\mid }C\mathrm{\mid }=m+1}(-1{)}^{(m+1)(m+2)\mathrm{/}2+{\sum }_{b_j\in C}j}p(A^{\mathrm{\prime }},C)p(A\setminus A^{\mathrm{\prime }},B\setminus C)$, with the zero-size determinant interpreted as one. Each summand contains a generating $(m+1)$-minor. Thus step 5.1, followed by discarding every standard product containing such a minor, spans the quotient by standard products with all sizes at most $m$. All generators of $I_{m+1}$ vanish under the rank-$m$ Gram substitution, so a relation among these surviving classes would contradict their Gram independence from step 2.1. They form a basis, and the same finite indexed identities, reduced modulo the ideal, supply terminating straightening there. For $m=0$, the quotient by the ideal of entries is $k$ and the only allowed product is the unit. For $m=t$, the ideal is zero and steps 3.1–5.1 give the polynomial-ring assertion.

We first give an indexed shuffle identity, including an explicit way to expand its right side. Pfaffians with arbitrary ordered lists are interpreted alternatingly, and vanish on repeated indices. If $h\ge h^{\mathrm{\prime }}$ are positive even integers, $1\le s\le h^{\mathrm{\prime }}$, $U=(u_1,\dots ,u_{h+s})$, and $C=(c_1,\dots ,c_{h^{\mathrm{\prime }}-s})$, put $ϵ(D,U\setminus D)$ equal to the sign of the permutation listing first the positions $D$ and then their complement, both increasingly. Then [given, algebra]

Here is a polynomial identity proving this membership, rather than a set-theoretic rank argument. Use exterior variables $e_1,\dots ,e_{h+s},f_1,\dots ,f_{h^{\mathrm{\prime }}-s}$, in that order, and put $\mathrm{\Omega }={\sum }_{i<j}{a}_{u_i{u}_j}{e}_i{e}_j$, $\mathrm{\Theta }={\sum }_{i,j}{a}_{u_i{c}_j}{e}_i{f}_j$, and $\mathrm{\Psi }={\sum }_{i<j}{a}_{c_i{c}_j}{f}_i{f}_j$. The displayed sum is the coefficient of $e_1\cdots e_{h+s}{f}_1\cdots f_{h^{\mathrm{\prime }}-s}$ in

Here ${\mathrm{pr}}_{a,b}$ means projection to exterior bidegree $(a,b)$ in the $e$ and $f$ variables. For $r\ge 1$, expand the coefficient of ${\mathrm{\Omega }}^{h\mathrm{/}2+r}\mathrm{/}(h\mathrm{/}2+r)!$: each coefficient is a Pfaffian of size $h+2r$. For $r=0$, $q=s\ge 1$; expand ${\mathrm{\Theta }}^q$ as a sum of products of ${\theta }_j{f}_j$, where ${\theta }_j={\sum }_i{a}_{u_i{c}_j}{e}_i$, and single out its first factor. Each coefficient of ${\mathrm{\Omega }}^{h\mathrm{/}2}{\theta }_j\mathrm{/}(h\mathrm{/}2)!$ is, with its exterior sign, $P_{(U_E,c_j)}$ for $\mathrm{\mid }E\mathrm{\mid }=h+1$: this follows by expanding the Pfaffian along $c_j$. Expanding the remaining exterior factors gives a completely specified finite sum of larger Pfaffians times polynomials. Thus the identity proves the asserted ideal membership. Repeated actual labels cause no difficulty because the identity is alternating in the formally labelled positions. Larger Pfaffians themselves belong to the ideal of size $h+2$ by repeated expansion along the first index.

Order nonempty Pfaffian symbols by decreasing size, then lexicographically by their index words written in decreasing order; order products by first sorting their factors in this order and then lexicographically. Suppose a sorted adjacent pair $P_A,P_B$, of sizes $h\ge h^{\mathrm{\prime }}$, fails $a_j\le b_j$ for some $j\le h^{\mathrm{\prime }}$. Choose such an $s$. Apply step 1.1 to the ordered list $U=(a_s,\dots ,a_h,b_1,\dots ,b_s)$ and the fixed list consisting of $a_1,\dots ,a_{s-1}$ in the first Pfaffian and $b_{s+1},\dots ,b_{h^{\mathrm{\prime }}}$ in the second. To justify this version with fixed positions explicitly, define $H_{i,j}(A;B;U)={\sum }_{\mathrm{\mid }D\mathrm{\mid }=i}ϵ(D,D^c)P_{(A,U_D)}{P}_{(U_{D^c},B)}$, with $\mathrm{\mid }A\mathrm{\mid }=h-i$, $\mathrm{\mid }B\mathrm{\mid }=h^{\mathrm{\prime }}-j$, $\mathrm{\mid }U\mathrm{\mid }=i+j$. Splitting according to the factor containing the first position $x$ gives the exact recurrence [step 1.1, algebra]

For $i+j>h$, repeatedly applying it reduces to $i=h$, where step 1.1 applies; $j$ stays positive since $i+j>h$. This proves membership in the larger-Pfaffian ideal and gives its expansion by a finite recurrence. Take $i=h-s+1$, $j=s$, $A=(a_1,\dots ,a_{s-1})$, and $B=(b_{s+1},\dots ,b_{h^{\mathrm{\prime }}})$. The resulting relation has the form

The coefficient of $P_A{P}_B$ is $1$ up to its displayed ordering sign. Indeed $b_i\le b_s<a_s\le a_j$ for $i\le s\le j$, so the two shuffled groups have no common label. When $h=h^{\mathrm{\prime }}$, no second occurrence arises by exchanging the two factors: every changed first factor precedes $P_A$, whereas the originally sorted $P_B$ does not. Every other nonzero first factor replaces at least one of $a_s,\dots ,a_h$ by an index below $a_s$, and therefore precedes $P_A$. Every term in the larger-Pfaffian expansion has a factor of size at least $h+2$ and also precedes $P_A$. Solving this relation rewrites the offending product into strictly earlier sorted products. Sorting all factors preserves this strict decrease: the unchanged factors occur in both multisets, and the replacement introduces a factor preceding $P_A$ while the two removed factors are both at least $P_A$. All relations preserve the ordinary degree, with $\mathrm{deg}{P}_S=\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$; in any fixed degree only finitely many products exist. Rewriting therefore terminates. Its terminal products are precisely chains for $⪯$. In the quotient, factors of size greater than $m$ vanish by Pfaffian expansion, so the surviving chains are exactly those stated. This proves spanning.

For independence put $m=2n$ and introduce independent variables $x_{ij}$, $1\le i\le t$, $1\le j\le m$. Substitute [step 2.1, algebra]

Exterior expansion gives $P_S\mapsto {\sum }_H\det X_{S,H}$, where $H$ runs over unions of complete consecutive column pairs and $\mathrm{\mid }H\mathrm{\mid }=\mathrm{\mid }S\mathrm{\mid }$; each coefficient is $1$. If $\mathrm{\mid }S\mathrm{\mid }>m$ the sum is empty. Order the $x$ variables column first and then row, giving earlier columns and smaller rows priority, and use lexicographic monomial order. For $S=(s_1<\cdots <s_h)$ with $h\le m$, the unique leading monomial of its image is $d_S={\prod }_{j=1}^h{x}_{s_j,j}$, with coefficient $1$: at each successive column the determinant term with the smallest unused row has priority, and the first $h$ columns beat every other union of column pairs. Multiplicativity gives leading monomial ${\prod }_a{d}_{S_a}$ for a standard product. Recover this product uniquely by sorting the row indices appearing in each column of its monomial increasingly; the resulting rows, read from longest to shortest, are exactly $S_1,S_2,\dots$. Hence distinct standard products have distinct leading monomials. Their images, and therefore their residue classes, are linearly independent. For $m=0$ all entries vanish and only the empty product survives. Together with spanning this proves the assertion, including the zero-ideal case.

Regard the three diagrams as disjoint finite graphs (for Brauer) or disjoint finite vertex sets carrying partitions (for partition diagrams). Glue both middle interfaces at once, and let $\sim$ be the least equivalence relation generated by all diagram edges or blocks and both sets of interface identifications. The relation $\sim$ is independent of the order in which the two interfaces are glued, since the least equivalence relation generated by a fixed set of pairs is unique. Thus both bracketings retain exactly the same equivalence classes meeting the outer boundary.

The classes meeting no outer vertex are also the same for both bracketings. Any class removed when the first two diagrams are composed meets neither of their exposed boundaries, so it contains no vertex of the third diagram; it can never merge with another class in the second composition. Conversely, every final class meeting no outer vertex is either removed at the first composition or is removed at the second. Hence the sum of the two loop counts in either bracketing equals the number of classes of $\sim$ meeting no outer vertex.

By [F1], each bracketing therefore has the same outer diagram and coefficient ${\delta }^{\mathrm{\ell }}$, with the same integer $\mathrm{\ell }$. The two bracketings agree on basis diagrams, so bilinearity gives associativity on the free modules. The identity diagrams add no new equivalence identifications and remove no class; they act as left and right units.

Let $M_{2a}$ be the number of perfect matchings of $2a$ labels. For $a=0$ the empty matching gives $M_0=1$. For $a\ge 1$, the first label can be paired with any of the remaining $2a-1$ labels, and deleting that pair leaves an arbitrary matching of $2a-2$ labels. Hence $M_{2a}=(2a-1)M_{2a-2}$, and induction gives $M_{2a}=(2a-1)(2a-3)\cdots 1=(2a-1)!!$.

By [F1], partition diagrams are in bijection with set partitions of the $2a$ boundary labels. Their number is $\mathrm{Bell}(2a)$ by the definition in the Statement, and the module is free on precisely that set.