Article ID Journal Published Year Pages File Type
9514430 Discrete Mathematics 2018 10 Pages PDF
Abstract
In the study of rotation symmetric Boolean functions (RSBFs), it is natural to consider the equivalence of Boolean vectors in F2n given by v∼w if w is obtained from v by cyclic permutation (rotation). Several authors (Clark, Cusick, Hell, Maitra, Maximov, Stănică), in relation to RSBFs, considered the square matrix nA obtained as follows: let (Gi)i=1,…,gn be the equivalence classes of this relation ∼ andΛi be representatives; the entries of nA are (∑x∈Gi(−1)x⋅Λj)i,j. Some properties of this matrix were obtained for n odd in the literature. We obtain a few new formulas regarding the number of classes of various types, and investigate the matrix nA in general. One of our main results is that nA satisfies (nA)2=2nId, and it is conjugate to its transpose by a diagonal matrix. This is not an immediate consequence of the similar property of the related Hadamard type matrix (pv,w)v,w∈F2n=((−1)v⋅w)v,w, but it is rather connected to character theory. We show that the entries of the matrix nA are essentially the character values of the irreducible representations of the semidirect (or wreath) product of F2n⋊Cn, where Cn is the cyclic group with n elements, which yields further properties of this matrix. This connection suggests possible future investigations, and motivates the introduction of Boolean functions with various other types of symmetry.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,