0
$\begingroup$

$8 \times 8$ permutation matrices correspond to patterns of 8 rooks on a chessboard with exactly 1 rook in each row or column, never 2.

Consider patterns of $n^2$ "3d rooks" in an $n \times n \times n$ cube, with exactly 1 rook in each of the $3n^2$ lines parallel to the $x, y, z$ axes. Two equivalent descriptions:

  • each plane cross section is an $n \times n$ permutation matrix
  • $n^3$ bits, binary variables $x_i$, which solve the $3n^2 \times n^3$ system of linear equations $Ax = 1$ where $A$ for $n=3$ looks like this:

    [111........................]
    [...111.....................]
    [......111..................]
    [.........111...............]
    [............111............]
    ...
    [1..1..1....................]
    [.1..1..1...................]
    [..1..1..1..................]
    [.........1..1..1...........]
    [..........1..1..1..........]
    ...
    [[1........1........1........]
    [.1........1........1.......]
    [..1........1........1......]
    [...1........1........1.....]
    [....1........1........1....]
    ...

My questions:

  1. what are these objects called -- is there a standard name, other descriptions ?
  2. about how many different $n \times n \times n$ such patterns are there ?
  3. about how many different vertices / extreme points does the convex polytope $\{x: Ax = 1, 0 \leq x \leq 1 \}$ have ?

(Background: to generate test cases for linear programming, continuous not binary, the 2d assignment problem, is too easy -- $1000 \times 1000$ runs in about a minute with the opensource GLPK simplex solver. Extended Latin squares, the above in 4d not 3d, give LP problems that run for hours: see many-vertex-test-problems-for-the-simplex-method on SO.)

$\endgroup$
1
  • 3
    $\begingroup$ These are exactly equivalent to Latin squares! To get the corresponding Latin square, for each coordinate $(i,j,k)$ in the cube where a $1$ is located, label row $i$ and column $j$ in the Latin square with symbol $k$. $\endgroup$ Commented Sep 26, 2019 at 16:29

1 Answer 1

1
$\begingroup$

What Mike Earnest said in the comments is correct:

These are exactly equivalent to Latin squares! To get the corresponding Latin square, for each coordinate (i,j,k) in the cube where a 1 is located, label row i and column j in the Latin square with symbol k.

Thus the number of such $n \times n \times n$ cubes is equal to the number of Latin squares of order $n$

Jacobson and Matthews, Generating Uniformly Distributed Random Latin Squares, J. Comb. Des. (1996) called this

  • the incidence-cube representation of a Latin square or
  • incidence cube for short.

(I have no idea about the third question.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .