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

Abstract

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.