0–1 matrices whose k-th powers have bounded entries

ABSTRACT

Let $\mathrm{\Gamma }(n,k,t)$ be the set of 0–1 matrices of order n such that each entry of the k-th powers of these matrices is bounded by t. Let $\gamma (n,k,t)$ be the maximum number of nonzero entries of a matrix in $\mathrm{\Gamma }(n,k,t)$. Given any positive integer t, we prove that $\gamma (n,k,t)=n(n-1)/2$ for $k\ge n-1$ when n is sufficiently large, and this maximum number is attained at A if and only if A is permutation similar to the upper triangular tournament matrix of order n.

COMMUNICATED BY:

• B. Shader

Keywords:

• 0–1 matrix
• digraph
• walk
• tournament

2010 Mathematics Subject Classifications:

• 15B36
• 05C35

Acknowledgments

The authors are grateful to the referee for helpful suggestions. The second author also thanks Professor Tin-Yau Tam for helpful discussions on matrix theory during his visit.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The research of Huang was supported by a Fundamental Research Fund for the Central Universities. Partial of this work was done when Huang was visiting Georgia Institute of Technology and Lyu was visiting Auburn University with the financial support of China Scholarship Council.