0–1 matrices whose k-th powers have bounded entries. Issue 10 (2nd October 2020) - Huang, Zejun; Lyu, Zhenhua
ABSTRACT: Let Γ ( 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 γ ( n, k, t ) be the maximum number of nonzero entries of a matrix in Γ ( n, k, t ) . Given any positive integer t, we prove that γ ( n, k, t ) = n ( n − 1 ) / 2 for k ≥ 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 .