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$
  • 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 at 16:29

Your Answer

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

Browse other questions tagged or ask your own question.