# 3d permutation matrices

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

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

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