Pairwise Reflection Symmetry in Generalized Latin Rectangles
2026-06-26 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study special types of matrices called generalized Latin rectangles, where symbols appear in a balanced way across rows and columns. They focus on an extra fairness condition called pairwise reflection-symmetry, meaning symbol pairs appear equally often in both orders to ensure unbiased comparisons, useful in tournaments or experiments. They found that making these matrices with certain repeat counts (λ) is trickier when λ is odd, but possible for large odd values. A key finding is that the smallest repeat count λ=1 works only when the matrix size n is a power of two. They also use computer programs to find examples and notice these designs often have connections to group theory.
Latin squaresGeneralized Latin rectanglesPairwise reflection-symmetryCombinatorial designOrder-balanceTournament schedulingColumn multiplicityGroup-theoretic structureInteger programming
Authors
Enrico Iurlano, Günther R. Raidl
Abstract
Many combinatorial designs ask for equal distribution of given symbols across the entries of a matrix. The paramount examples are Latin squares, where each symbol from $\{1,\dots,n\}$ appears once per row and column of an $n\times n$ matrix. Generalized Latin rectangles extend this to $λn \times n$ matrices with repeated symbols under controlled column frequencies. In this more general setting, we examine structural properties of pairwise reflection-symmetry, which requires that, on every pair of columns, each ordered symbol pair $(p,q)$ occurs as often as its reversal $(q,p)$. This order-balance is precisely what makes head-to-head comparisons unbiased, i.e., no symbol gains a systematic advantage from the position it occupies relative to another, a fairness demand arising for instance when scheduling tournaments or laying out comparative trials. Existence of such objects for odd $λ$ turns out to be remarkably more subtle than for even $λ$. After showing that existence holds also for sufficiently large odd $λ$, we initiate the search for the smallest possible value of $λ$ in this setting. We obtain the insight that a column multiplicity of $λ=1$ can be achieved if and only if $n$ is a power of two. We complement the existence results with a direct product construction and add several further observations on the property. Finally, we propose and evaluate a quadratically constrained integer program to computationally search for these objects. The resulting experiments reveal that many of them possess an underlying group-theoretic structure which, as we conjecture, may even be unavoidable in certain settings.