tailieunhanh - Báo cáo toán học: "Maximum exponent of boolean circulant matrices with constant number of nonzero entries in their generating vector"

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 .