Enumeration of Parallelograms in Permutation Matrices for Improved Bounds on the Density of Costas Arrays

  • Christopher N. Swanson
  • Bill Correll, Jr.
  • Randy W. Ho
Keywords: Costas array, Permutation, Enumeration


A Costas array of order $n$ is an $n\times n$ permutation matrix such that all vectors between pairs of ones are distinct. Thus, a permutation matrix fails to be a Costas array if and only if it contains ones that form a (possibly degenerate) parallelogram. In this paper, we enumerate parallelograms in an $n\times n$ permutation matrix. We use our new formulas to improve Davies's $O(n^{-1})$ result for the density of Costas arrays.
Article Number