Permutation Matrices, Their Discrete Derivatives and Extremal Properties

Abstract

For a permutation $\pi$, and the corresponding permutation matrix, we introduce the notion of {\em discrete derivative}, obtained by taking differences of successive entries in $\pi$. We characterize the possible derivatives of permutations, and consider questions for permutations with certain properties satisfied by the derivative. For instance, we consider permutations with distinct derivatives, and the relationship to so-called Costas arrays.