Department of Computer Science, University of Waterloo, Waterloo, Ont., N2L 3G1 Canada
Abstract:
Let A be an n × n matrix with non-negative entries and no entry in (0, 1). We prove that there exist integers r, s with 0 rs 2n such that ArAs. We prove that 2n cannot be replaced with e√n log n. We also give an application to the theory of formal languages.