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
  • 2
    $\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$ – Mike Earnest Sep 26 '19 at 16:29
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.