3d permutation matrices

Question

$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.)

Answer 1

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.)