Signing Balanced Incomplete Block Designs over the Group of Order Two

If the non-zero entries of an incidence matrix \(X\) of BIBD\((v, b, r, k, 2)\) have been signed to produce a \((0, 1, -1)\) matrix \(Y\0 such that

\[YY^T = rI_v,\]

then we say it has been signed. The resulting matrix \(Y\) is said to be a Bhaskar Rao design BRD\((v, k, 2)\). We discuss the complexity of two signing problems, (i) Given \(v\), \(k\), and \(\lambda\), decide whether there is a BRD\((v, k, 2\lambda)\), (ii) Given a BIBD\((v, k, 2\lambda)\), decide whether it is signable.
The paper describes related optimisation problems. We show that the signing problems are equivalent to finding the real roots of certain multi-variable polynomials. Then we describe some linear constraints which reduce the size of the second problem, we show certain special cases have polynomial complexity, and we indicate how in some cases the second problem can be decomposed into smaller independent problems. Finally, we characterise signable Steiner triple systems in terms of their block-intersection graphs, and show that the complexity of deciding whether a twofold triple system can be signed is linear in the number of blocks.