Circulant matrices and affine equivalence of monomial rotation symmetric Boolean functions
Loading...
Authors
Canright, David
Chung, Jong H.
Stănică, Pantelimon
Subjects
Boolean functions
Circulant matrices
Affine equivalence
Permutations
Circulant matrices
Affine equivalence
Permutations
Advisors
Date of Issue
2015
Date
Publisher
Elsevier
Language
Abstract
The goal of this paper is two-fold. We first focus on the problem of deciding whether two monomial rotation symmetric (MRS) Boolean functions are affine equivalent via a permutation. Using a correspondence between such functions and circulant matrices, we give a simple necessary and sufficient condition. We connect this problem with the well known Ádám’s conjecture from graph theory. As applications, we reprove easily several main results of Cusick et al. on the number of equivalence classes under permutations for MRS in prime power dimensions, as well as give a count for the number of classes in pq number of variables, where p, q are prime numbers with p < q < p2. Also, we find a connection between the generalized inverse of a circulant matrix and the invertibility of its generating
polynomial over F2, modulo a product of cyclotomic polynomials, thus generalizing a known result on nonsingular circulant matrices.
Type
Article
Description
The article of record as published may be found at http://dx.doi.org/10.1016/j.disc.2015.05.017
Series/Report No
Department
Applied Mathematics
Organization
Naval Postgraduate School (U.S.)
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
16 p.
Citation
D. Canright, J.H. Chung, P. Stănică, "Circulant matrices and affine equivalence or monomial rotation symmetric Boolean functions," Discrete Mathematics, v. 338 (2015), pp. 2197-2211
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.