Logo image
Back
On the matrix of rotation symmetric Boolean functions
Journal article   Open access   Peer reviewed

On the matrix of rotation symmetric Boolean functions

Lavinia C Ciungu and Miodrag C Iovanov
Discrete mathematics, Vol.341(12), pp.3271-3280
12/01/2018
DOI: 10.1016/j.disc.2018.04.019
url
https://doi.org/10.1016/j.disc.2018.04.019View
Published (Version of record) Open Access

Abstract

In the study of rotation symmetric Boolean functions (RSBFs), it is natural to consider the equivalence of Boolean vectors in F-2(n) given by v similar to w if w is obtained from v by cyclic permutation (rotation). Several authors (Clark, Cusick, Hell, Maitra, Maximov, Stanica), in relation to RSBFs, considered the square matrix nA obtained as follows: let (Gi()i=1, ...,gn) be the equivalence classes of this relation similar to and Lambda(i) be representatives; the entries of (n)A are (Sigma(x is an element of Gi)(-1)(x.Lambda 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 (n)A in general. One of our main results is that (n)A satisfies ((n)A)(2)=2(n)Id, 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 (p(v,w))(v,w) is an element of F-2(n)=((-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 semi-direct (or wreath) product of F-2(n) (sic)C-n, where C-n 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. (C) 2018 Published by Elsevier B.V.
 Mathematics Physical Sciences Science & Technology

Details

Metrics

19 Record Views
1 Times Cited - Web of Science
Logo image