Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Maximum exponent of boolean circulant matrices with constant number of nonzero entries in their generating vector. | Maximum exponent of boolean circulant matrices with constant number of nonzero entries in their generating vector . Bueno Department of Mathematics and The College of Creative Studies University of California Santa Barbara USA mbueno@ S. Furtado Í Faculdade de Economia do Porto Rua Dr. Roberto Frias 4200-464 Porto Portugal sbf@ N. Sherer Ỉ The College of Creative Studies University of California Santa Barbara USA nsherer@ Submitted Sep 11 2008 Accepted May 19 2009 Published May 29 2009 Mathematics Subject Classification 11P70 05C25 05C50 Abstract It is well-known that the maximum exponent that an n-by-n boolean primitive circulant matrix can attain is n 1. In this paper we find the maximum exponent attained by n-by-n boolean primitive circulant matrices with constant number of nonzero entries in their generating vector. We also give matrices attaining such exponents. Solving this problem we also solve two equivalent problems 1 find the maximum exponent attained by primitive Cayley digraphs on a cyclic group whose vertices have constant outdegree 2 determine the maximum order of a basis for Zn with fixed cardinality. Supported by a Faculty Career Development Award granted by UCSB in Summer 2008 and supported by Direccion General de Investigation Ministerio de Ciencia y Tecnologia of Spain under grant MTM2006-06671. iThis work was done within the activities of Centro de Estruturas Lineares e Combinatorias da Universidade de Lisboa. Supported by a Summer Undergraduate Research Fellowship granted by the College of Creative Studies at UCSB. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R66 1 1 Introduction A boolean matrix is a matrix over the binary Boolean algebra 0 1 . An n-by-n boolean matrix C is said to be circulant if each row of C except the first is obtained from the preceding row by shifting the elements cyclically 1 column to the right. In other words the entries of a circulant matrix C cj are related in the manner ci .