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

Christopher N. Swanson, Bill Correll, Jr., Randy W. Ho


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.


Costas array; Permutation; Enumeration

Full Text: