(with Kimmo Eriksson)

We define a class of hypercubic (shape $[n]^d$) arrays
that in a certain sense are $d$-dimensional analogs of permutation
matrices, with motivation {}from algebraic geometry.
Various characterizations of permutation arrays are proved,
an efficient generation algorithm is given and enumerative
questions are discussed, though not settled.
There is a partial order on the permutation arrays, specializing to
the
Bruhat order on $S_n$ when $d$ equals 2, and specializing to the
lattice of
partitions of a $d$-set when $n$ equals 2.