0–1 matrices whose k-th powers have bounded entries. Issue 10 (2nd October 2020)

• Record Type: Journal Article
• Authors: Huang, Zejun; Lyu, Zhenhua
• Is Part Of: Linear & multilinear algebra. Volume 68:Issue 10(2020)
• Page Start: 1972
• Page End: 1982
• Publication Date: 2020-10-02
• Subjects: B. Shader; 0–1 matrix -- digraph -- walk -- tournament; 15B36 -- 05C35; Algebras, Linear -- Periodicals; Multilinear algebra -- Periodicals; 512.505
• DOI: 10.1080/03081087.2019.1567671
• Languages: English
• ISSNs: 0308-1087

Abstract

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 .