Permanents of woven matrices (Q1870074)

Let \(D=(d_{ij})\) be an \(m\times n\)-\((0,1)\)-matrix of row sums \(r_1,\dots, r_m,\) column sums \(c_1,\dots, c_n,\) and sum of entries \(N.\) For \(i=1,\dots m; j=1,\dots,n,\) let \(R_i\) be an \(r_i\times r_i\) matrix, and \(C_j\) a \(c_j\times c_j\) matrix. Define \(s(i,j)=\#\{\ell: 1\leq \ell \leq j, d_{i\ell}=1 \},\) \(t(i,j)=\#\{\ell: 1\leq \ell \leq i, d_{\ell j}=1 \},\) and the \(N\times N\) matrix \(P_D\) as a matrix of blocks by putting its \((i,j)\)-block of size \(r_i\times c_j\) equal to the zero matrix if \(d_{ij}=0,\) and equal to the elementary matrix \(E_{s(i,j),t(i,j)},\) otherwise. The matrix woven from the `warps' \(R_i\), `woofs' \(C_j,\) and the `lattice' \(D\), can be defined as the \(N\times N\) matrix \(W=W(D)=(R_1\oplus \dots \oplus R_m)P_D(C_1\oplus \dots \oplus C_n)\) or, alternatively, as a certain generalization of tensor products. The main result is that there holds the permanental identity \[ \operatorname{per} (W)=\pm \prod_{i=1}^m \operatorname{per} R_i \cdot \prod_{i=1}^n \operatorname{per} C_j, \] if and only if the bipartite graph associated with \(D\) is a forest. (The corresponding determinantal analogue is always true.) A consequence of this result is that for certain classes of matrices there is an effective way to convert the problem of calculating permanents to calculation of determinants. The procedure of weaving was originally conceived to solve problems in combinatorial design theory; see e.g. \textit{R. Craigen} [J. Comb. Des. 3, 1-13 (1995; Zbl 0839.05022)].