Matrix characterization of symmetry groups of boolean functions
We studies symmetry groups of boolean functions and construct new way of description of this problem in matrices language. Some theorems about constructions of symmetry groups with using matrices are presented. Some properties of this approach are given.
Збережено в:
| Дата: | 2012 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2012
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/152230 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Matrix characterization of symmetry groups of boolean functions / P. Jasionowski // Algebra and Discrete Mathematics. — 2012. — Vol. 14, № 1. — С. 71–83. — Бібліогр.: 10 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-152230 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1522302019-06-10T01:25:34Z Matrix characterization of symmetry groups of boolean functions Jasionowski, P. We studies symmetry groups of boolean functions and construct new way of description of this problem in matrices language. Some theorems about constructions of symmetry groups with using matrices are presented. Some properties of this approach are given. 2012 Article Matrix characterization of symmetry groups of boolean functions / P. Jasionowski // Algebra and Discrete Mathematics. — 2012. — Vol. 14, № 1. — С. 71–83. — Бібліогр.: 10 назв. — англ. 1726-3255 2010 MSC:05E05. http://dspace.nbuv.gov.ua/handle/123456789/152230 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We studies symmetry groups of boolean functions and construct new way of description of this problem in matrices language. Some theorems about constructions of symmetry groups with using matrices are presented. Some properties of this approach are given. |
| format |
Article |
| author |
Jasionowski, P. |
| spellingShingle |
Jasionowski, P. Matrix characterization of symmetry groups of boolean functions Algebra and Discrete Mathematics |
| author_facet |
Jasionowski, P. |
| author_sort |
Jasionowski, P. |
| title |
Matrix characterization of symmetry groups of boolean functions |
| title_short |
Matrix characterization of symmetry groups of boolean functions |
| title_full |
Matrix characterization of symmetry groups of boolean functions |
| title_fullStr |
Matrix characterization of symmetry groups of boolean functions |
| title_full_unstemmed |
Matrix characterization of symmetry groups of boolean functions |
| title_sort |
matrix characterization of symmetry groups of boolean functions |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2012 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/152230 |
| citation_txt |
Matrix characterization of symmetry groups of boolean functions / P. Jasionowski // Algebra and Discrete Mathematics. — 2012. — Vol. 14, № 1. — С. 71–83. — Бібліогр.: 10 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT jasionowskip matrixcharacterizationofsymmetrygroupsofbooleanfunctions |
| first_indexed |
2025-07-13T02:36:12Z |
| last_indexed |
2025-07-13T02:36:12Z |
| _version_ |
1837497505023000576 |
| fulltext |
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 14 (2012). Number 1. pp. 71 – 83
c© Journal “Algebra and Discrete Mathematics”
Matrix characterization of symmetry groups
of boolean functions
Pawel Jasionowski
Communicated by V. I. Sushchansky
Abstract. We studies symmetry groups of boolean functions
and construct new way of description of this problem in matrices
language. Some theorems about constructions of symmetry groups
with using matrices are presented. Some properties of this approach
are given.
Introduction
The main objects of study of this paper are symmetry groups of boolean
functions. We want to provide some algorithms to describe special kinds
of permutation groups and use groups theoretic techniques to show which
features of constructed boolean functions are important in determining
the representability of this permutation groups.
The starting point of this paper is [3] and [4] where basic structures and
some specific constructions of boolean functions are given. In [7] author
show first known example of permutation groups which is 3 representable
but is not 2 representable. Moreover in [5], [7] and [8] analysis of direct
sum and wreath product of permutation groups is presented.
The problem of symmetry group of boolean functions is important
not only from algebraic point of view. One of the application is associated
with computer science. We take a device (or "module") M with n inputs,
each of which can be in one of two possible states 0 or 1. An outputs
2010 MSC: 05E05.
Key words and phrases: Boolean function, invariance group, symmetry group.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
72 Matrix characterization
of M can assume 0 or 1 too. That kind of device can be represented
by boolean function f which n variables (we can consider generalized
modules M which have outputs from the set {0, 1, ..., k − 1}). In general
a value of that function depends on order of inputs. Of course there could
exist some permutation which leave f invariant. For example when f is
invariant under any permutation of inputs then we say that module M is
symmetric. In this paper we consider a partial-symmetric functions. It
is possible that study of this problem could help in optimizing module
positioning on integrated circuit in VLSI design technology.
There are many articles related to this problem. In this paper the main
is [3] where authors study boolean functions invariance groups and show
how we can construct examples of boolean functions which represent some
special kinds of permutation groups. Another important work is [7] where
the first known example of permutation groups which is 3 representable
but is not 2 representable is given.
1. Preliminaries
Let {0, 1}n is a set of all boolean vectors of length n. A mapping
f : {0, 1}n → {0, 1, ..., k − 1}, k ≥ 2
is called k valued boolean function. A set of all k valued boolean functions
with n variables is denoted as a Bn,k. We put Bn for a set of all boolean
functions with n variables and two possible values 0 and 1.
Let f ∈ Bn,k and let σ is a permutation from a symmetric group Sn
of set {1, ..., n}. We define an action σ on f(x1, ..., xn) in the following
way:
fσ(x1, x2, ..., xn) = f(xσ(1), xσ(2), ..., xσ(n))
Let
S(f) = {σ ∈ Sn : f = fσ}
It is easy to see that S(f) is a subgroup of group Sn. A group S(f) of all
permutation σ ∈ Sn such, that
f(x1, x2, ..., xn) = f(xσ(1), xσ(2), ..., xσ(n))
is called a symmetry group of k valued boolean function f . Moreover
the function f is called an invariant of the group S(f). Equivalently the
group S(f) is called an invariant group of boolean function f . We put 0i
or 1i to denote i consecutive 0 or 1.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
P. Jasionowski 73
A permutation group G ≤ Sn such, that G = S(f) for some boolean
function f : {0, 1}n → {0, 1, ..., k − 1} is called a group representable
by the k valued boolean function f (or k representable). A permutation
group G is called representable if it is k representable for some k.
Now let G ≤ Sn. The main point of research on permutation groups
and its representability as a symmetry group of some k valued boolean
function is to check how G act on the set {0, 1}n of all boolean vectors of
length n. We can see that any permutation group (G,X) where |X| = n
could be seen as a group which act on the set {0, 1}n. An action is given
by the following condition:
x → xσ : (x1, x2, ..., xn) → (xσ(1), xσ(2), ..., xσ(n))
An orbit of element x ∈ X is defined as xG = {xσ, σ ∈ G}.
We see that if G = S(f) for some f ∈ Bn,k then: (a) if x, y ∈ {0, 1}n
are in the same G-orbit, then f(x) = f(y); (b) for every τ 6∈ G there have
to exist element x ∈ X such, that x and xτ are in different G-orbits and
f(x) 6= f(xτ ).
For example a group Sn for some n is 2 representable. Sn = S(f)
for the constant boolean function f with n variables. A group {id} is
2 representable. The group {id} = S(f) where f(x) = 1 for x in the
form 0i1n−i and f(x) = 0 in other case (symbols 0i and 1i denote i
consecutive 0 or 1). Interesting and unexpected example is S2 × S2 =
{id, (1, 2)(3, 4), (1, 3)(2, 4), (1, 4)(2, 3)} which is 3 representable but is not
2 representable. It was presented in [7]. We can ask which permutation
groups are representable (or 2 representable) as symmetry groups of
boolean functions. It is important that we work only with permutation
groups and we do not consider abstract groups at all. It is easy to proof,
that every abstract group is representable as a symmetry group of some
boolean function.
2. Matrix characterization
Let n is a positive integer number. Now we would like to consider a
module M which is represented by boolean function f : {0, 1}n → {0, 1}.
Every mapping at that form can be represented as a vector
X = (f(00...0), f(00...1), ..., f(11...1)) = (x1, ..., x2n)
of value of that function. We say that this vector is the vector of value of
function f and we denote it by Xf . We consider an order given by the
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
74 Matrix characterization
following rule: xi = f(yi1, yi2, ..., yin) iff i = 2n−1yi1 +2n−2yi2 + ...+yin +1
for i = 1, 2, ..., 2n.
Let V2n is a set of that kind of vector. So
V2n = {X = (x1, ..., x2n), xi ∈ {0, 1}, i = 1, 2, ..., 2n}
Let Per(2n) is a set of all permutation matrices of size 2n. An action of
a permutation σ ∈ Sn at the boolean function f given by the rule
fσ(x1, x2, ..., xn) = f(xσ(1), xσ(2), ..., xσ(n))
can be considered as the matrices action in the following way
AXf = Xf (1)
where Xf ∈ V2n is a vector of value of function f . Here the vector Xf is
given, and we try to find every matrices A ∈ Per(2n) which preserve that
equality. First of all it is easy to see that if matrix A preserve the rule (1)
then A is an element of stabilizer StabP er(2n)Xf .
We can characterize the stabilizer of element Xf . We know that
Xf ∈ V2n so we can notice that there exist sets of indexes I = {i1, i2, ..., ik},
J = {j1, j2, ..., jm} , k,m ≤ 2n (I or J can be empty) such that |I|+ |J | =
2n and
xi =
{
1 i ∈ I
0 i ∈ J
So we see that
StabP er(2n)Xf
∼= S(i1, i2, ..., ik) ⊕ S(j1, j2, ..., jm) (2)
Now the question is which permutation matrices from StabP er(2n)Xf
correspond to permutations from Sn in following way: permutation σ ∈ Sn
correspond to matrix Aσ ∈ Per(2n) iff σ ∈ S(f) ⇔ AσXf = Xf where
f : {0, 1}n → {0, 1} is some boolean function.
Let f : {0, 1}n → {0, 1}. Let Xf is a vector of value of that function.
Now we construct a mapping ψ : Sn → Per(2n) such that
ψ−1(StabP er(2n)Xf ∩ ψ(Sn)) = S(f)
A positive integer number k which is presented in binary form is denoted as
a (k)2. Let σ ∈ Sn. Now we consider a vector c = ((0)2, (1)2, ..., (2
n − 1)2).
This vector can be considered as a matrix H of size 2n × n where a row
with number i is the i coordinate of the vector c, i = 1, 2, ..., 2n. We
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
P. Jasionowski 75
denote an element of matrix H by hi,j , 1 ≤ i ≤ 2n, 1 ≤ j ≤ n and say
that this is a generalized Hamming’s matrix.
We transform a matrix H to Hσ = [hi,σ−1(j)]1≤i≤2n,1≤j≤n. Now we
can create a vector hσ = [hi]1≤i≤2n in the following way:
hi = hi,σ−1(1) · 2n−1 + hi,σ−1(2) · 2n−2 + ...+ hi,σ−1(n)
for 1 ≤ i ≤ 2n. We consider a vector hσ in vertical form. In finally step
we create a matrix Aσ ∈ Per(2n), Aσ = [aij ]:
aij =
{
1 dla hi = j − 1
0 dla hi 6= j − 1
i, j ∈ {1, 2, ..., 2n}
Now we can define a mapping ψ : Sn → Per(2n) as ψ(σ) = Aσ. It is easy
to see that it is an injection.
When we have mapping ψ we can answer for a question about con-
struction of group S(f).
Theorem 1. Let n is a positive integer number and f : {0, 1}n → {0, 1}
is a boolean function. Let Xf is a vector of value of function f and
ψ : Sn → Per(2n) is a mapping which we construct before. Then
S(f) = ψ−1(StabP er(2n)Xf ∩ ψ(Sn))
Proof. When we have boolean function f : {0, 1}n → {0, 1} we can find a
vector Xf (vector of value of function f) and a group
StabP er(2n)Xf
∼= S(i1, i2, ..., ik) ⊕ S(j1, j2, ..., jm)
as we show in (2). It is easy to see, that a set ψ(Sn) ∩ StabP er(2n)Xf
is a set of matrices which hold the rule AXf = Xf on one hand, and
correspond to some permutation σ ∈ Sn which preserve f on the other
hand. Moreover we see, that there are no other permutations τ ∈ Sn
which preserve f , so
ψ−1(StabP er(2n)Xf ∩ ψ(Sn)) = S(f)
Now we have a good looking for a problem of 2-representability of
permutation groups. There are no big differences between this situation
and a k-representability for k ≥ 2. Let f : {0, 1}n → {0, 1, ..., k− 1}. Now
a vector Xf correspond to the boolean function f can be consider in
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
76 Matrix characterization
the following way: there exist sets of indexes I0 = {i01, i
0
2, ..., i
0
m0
}, I1 =
{i11, i
1
2, ..., i
1
m1
}, ..., Ik−1 = {ik−1
1 , ik−1
2 , ..., ik−1
mk−1
},mj < 2n, j = 0, 1, ..., k −
1 (Ij can be empty) and
∑k−1
j=0 |Ij | = 2n such that
xi =
0 i ∈ I0
1 i ∈ I1
... ...
k − 1 i ∈ Ik−1
So
StabP er(2n)Xf
∼= S(i01, ..., i
0
m0
) ⊕ S(i11, ..., i
1
m1
) ⊕ ...⊕ S(ik−1
1 , ..., ik−1
mk−1
)
Then ψ−1(StabP er(2n)Xf ∩ ψ(Sn)) = S(f).
As we could see before it is easy to construct a group StabP er(2n)Xf for
some k-valued boolean function f . The most difficult problem is to decide
which matrices from StabP er(2n)Xf correspond to some permutations
from Sn and how we can construct the group S(f). So now we try to
answer for question how we can construct w permutation σ ∈ Sn from
Aσ ∈ Per(2n) and which matrices A ∈ Per(2n) do not correspond to any
σ ∈ Sn.
Let Mn×n is a set of all matrices of size n.
Definition 1. A matrix Xσ ∈ Mn×n correspond to the permutation
σ ∈ Sn in the natural way if elements xij of this matrix hold following
condition:
xij =
{
1 for σ(i) = j
0 for σ(i) 6= j
i, j ∈ {1, 2, ..., n}
Let A ∈ Mn×n be a matrix which elements are only 0 or 1.
Definition 2. Matrix B ∈ Mn×n obtain from a matrix A through chang-
ing an element 0 to α and 1 to β (α, β ∈ R) is called a matrix (α, β)-
associate with A. If we know α and β then we simply say that A and B
are associate (and we write A ass B).
Let ψ : Sn → Per(2n) is the same mapping which we construct before.
Now with using Hamming’s generalized matrix we proof association of
matrices Xσ and Aσ.
Theorem 2. Let σ ∈ Sn and Xσ is a matrix which correspond to permu-
tation σ in the natural way. Let ψ(σ) = Aσ. Then there exists matrix H
of size 2n × n such that matrix Γ := HTAσH and Xσ are (2n−2, 2n−1)-
associate.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
P. Jasionowski 77
Proof. Let σ ∈ Sn, Aσ ∈ Per(2n). We have Aσ = [aij ], 1 ≤ i, j ≤ 2n.
Let H ∈ M2n×n is a generalized Hamming’s matrix, that is H = [hij ] ,
1 ≤ i ≤ 2n, 1 ≤ j ≤ n and hi,1 · 2n−1 + hi,2 · 2n−2 + ...+ hi,n = i− 1.
Moreover we put HTAσ = [ωi,j ] , 1 ≤ i ≤ n, 1 ≤ j ≤ 2n. Because of
construction of matrix Aσ we have, that aij = 1 if and only if
hi,σ−1(1) · 2n−1 + hi,σ−1(2) · 2n−2 + ...+ hi,σ−1(n) = j − 1
From that condition we get ωσ−1(i),j = hji what is equivalent to
ωij = hj,σ(i) (3)
Let h1, h2, ..., hn denote successive rows of matrix HT , while ω1, ω2, ..., ωn
denote successive rows of matrix HTAσ. From (3) we get that ωi = hσ(i),
1 ≤ i ≤ n.
Because the matrix H is a generalized Hamming’s matrix and Aσ ∈
Per(2n) then the matrix Γ := HTAσH = [γij ] 1 ≤ i, j ≤ n is consist from
elements in form γij = α = 2n−2 or γij = β = 2n−1.
Let i, j ∈ {1, 2, ..., 2n}. If there exists m ∈ {1, 2, ..., 2n} such that
ωim 6= hmj then γij = α. If for all m ∈ {1, 2, ..., 2n} we have ωim = hmj
then γij = β.
So the matrix Γ is in the form
γij =
{
α j 6= σ(i)
β j = σ(i)
for 1 ≤ i, j ≤ n.
When we consider the mapping 0 → α, 1 → β we see, that matrix Γ
is (2n−2, 2n−1)-associate with Xσ.
It is easy to see that if matrixA ∈ Per(2n) and there in no permutation
σ ∈ Sn such that ψ(σ) = A then matrix Γ1 := HTAH where H is a
generalized Hamming’s matrix is not associate with any permutation
matrix X of size n.
We can see that the mapping ψ and the matrix Γ := HTAσH create
correspondence between Sn and Per(2n). Now we ask what we can say
about this correspondence. A next theorem shows it’s two properties.
Theorem 3. Let n be a positive integer number. For any permutation
σ, σ1, σ2 ∈ Sn we have:
a. (Aσ)T = Aσ−1
= (Aσ)−1;
b. Aσ1σ2 = Aσ2Aσ1.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
78 Matrix characterization
Proof. a. We know, that HTAσH and Xσ are associate and
HT (Aσ)TH = (HTAσH)T ass XT
σ = Xσ−1 ass HTAσ−1
H
So (Aσ)T = Aσ−1
. We show, that(Aσ)T = (Aσ)−1. This equality is
equivalent to Aσ(Aσ)T = E.
Let
Aσ = [aij ], aij =
{
1 hi = j − 1
0 hi 6= j − 1
where hi = hi,σ−1(1) · 2n−1 + hi,σ−1(2) · 2n−2 + ...+ hi,σ−1(n). Moreover
(Aσ)T = [bij ], bij =
{
1 h′
i = j − 1
0 h′
i 6= j − 1
where h′
i = hi,σ(1) · 2n−1 + hi,σ(2) · 2n−2 + ...+ hi,σ(n) (because of (Aσ)T =
Aσ−1
).
Let Aσ(Aσ)T = [cij ] where cij =
∑2n
α=1 aiαbαj . We know, that aij = bji
so
cij =
2n
∑
α=1
aiαbαj =
2n
∑
α=1
aiαajα
That sum is equal 1 iff aiα = 1 and ajα = 1. We have aiα = 1 so
hi,σ−1(1) · 2n−1 + hi,σ−1(2) · 2n−2 + ...+ hi,σ−1(n) = α− 1 and ajα = 1. So
hj,σ−1(1) · 2n−1 + hj,σ−1(2) · 2n−2 + ...+ hj,σ−1(n) = α− 1. From that two
conditions we have i = j so cij = 1 iff i = j.
b. To show, that Aσ1σ2 = Aσ2Aσ1 we put
Aσ1σ2 = [aij ], aij =
{
1 hi = j − 1
0 hi 6= j − 1
where hi = h
i,σ−1
2
σ−1
1
(1) · 2n−1 + h
i,σ−1
2
σ−1
1
(2) · 2n−2 + ... + h
i,σ−1
2
σ−1
1
(n).
Moreover
Aσ2 = [bij ], bij =
{
1 h′
i = j − 1
0 h′
i 6= j − 1
where h′
i = h
i,σ−1
2
(1) · 2n−1 + h
i,σ−1
2
(2) · 2n−2 + ...+ h
i,σ−1
2
(n) and
Aσ1 = [cij ], cij =
{
1 h′′
i = j − 1
0 h′′
i 6= j − 1
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
P. Jasionowski 79
where h′′
i = h
i,σ−1
1
(1) · 2n−1 +h
i,σ−1
1
(2) · 2n−2 + ...+h
i,σ−1
1
(n). Let Aσ2Aσ1 =
[dij ], dij =
∑2n
α=1 biαcαj . That sum can be reduce to only one component
i.e. dij = 1 iff biα = 1 and cαj = 1. Let dij = 1. Then
biα = 1 ⇒ h′
i = h
i,σ−1
2
(1) ·2n−1+h
i,σ−1
2
(2) ·2n−2+...+h
i,σ−1
2
(n) = α−1 (4)
cαj = 1 ⇒ h′′
i = h
α,σ−1
1
(1)·2
n−1+h
α,σ−1
1
(2)·2
n−2+...+h
α,σ−1
1
(n) = j−1 (5)
Moreover from definition of H we have
hα,1 · 2n−1 + hα,2 · 2n−2 + ...+ hα,n = α− 1 (6)
From (4) and (6)
∑2n
k=1 hi,σ−1
2
(k) · 2n−k =
∑2n
k=1 hα,k · 2n−k so
h
i,σ−1
2
(k) = hα,k, 1 ≤ k ≤ n (7)
From (5) and (7)
h
α,σ−1
1
(k) = h
i,σ−1
2
σ−1
1
(k), 1 ≤ k ≤ n (8)
So from (5) and (8) we have, that
h
α,σ−1
1
(1)·2
n−1+...+h
α,σ−1
1
(n) = h
i,σ−1
2
σ−1
1
(1)·2
n−1+...+h
i,σ−1
2
σ−1
1
(n) = j−1
so aij = 1
In that way we create a new language to describe symmetry groups
of boolean functions which represent module M . Now when we have
module M and boolean function f of M is given then we can create
a group S(f) in a following way: when we consider a boolean function
f : {0, 1}n → {0, 1, ..., k − 1} then in natural way we can construct a
vector Xf of value of that function and a set StabP er(2n)Xf . Then because
of definition of mapping ψ : Sn → Per(2n) the group S(f) is equal to
ψ−1(StabP er(2n)Xf ∩ ψ(Sn)). From theorems 2 and 3 we have, that it
is not necessary to know all matrices ψ(σ) for all σ ∈ Sn because we
can consider only a matrices from StabP er(2n)Xf and then through the
construction described in theorem 3 i.e. Γ := HTAσH we can create a
group S(f).
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
80 Matrix characterization
3. Application of matrix characterization to constructions
of symmetry groups of boolean functions
In this section we construct a boolean function which represent direct
sum and wreath product of symmetric groups.
Let (G,X) and (H,Y ) are two permutation groups and |X| = n,
|Y | = m. For X ∩ Y = ∅ we construct a new group (G×H,X ∪ Y ). An
action is given by the following condition:
z(g,h) =
{
zg if z ∈ X
zh if z ∈ Y
where z ∈ X ∪ Y, g ∈ G, h ∈ H. We say that permutation group (G ×
H,X ∪ Y ) is a direct sum of permutation groups (G,X) and (H,Y ) and
denote it as G⊕H.
There are papers ([3], [7]) where direct sum of two permutation groups
are considered. Although, it is interesting to construct exact boolean
functions for some special kind of groups. Here we present construction of
2 valued boolean function which represent direct product of two symmetric
groups.
Let n1, n2 are any positive integer numbers, n1 +n2 = n. We construct
boolean function f in the following way:
Xf =
v1
v2
...
v2n2
v2n2 +1
...
vi
...
v2n
=
1
1
...
1
0
...
vi
...
1
(9)
where vi = 1 iff i = s · 2n2 , s = 1, 2, ..., 2n1 and 0 otherwise, i = 2n2 +
1, ..., 2n.
Theorem 4. For any positive integer n1, n2 the 2 valued boolean function
f constructed in (9) hold the following condition
S(f) = Sn1
⊕ Sn2
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
P. Jasionowski 81
Proof. Let n1, n2 are any positive integer numbers, n1 + n2 = n. We put
A1 = {1, 2, ..., n1}, A2 = {n1 + 1, ..., n1 + n2}. Now we take a boolean
function f defined in (9). Let’s a vector Xf is a vector of value of that
boolean function. Now we show that S(f) = Sn1
⊕ Sn2
. If σ ∈ Sn1
⊕ Sn2
then obviously matrix ψ(σ) preserve vectorXf so σ ∈ S(f). This situation
take places because permutation σ can be thought as a pair (ρ, τ) where ρ
act inside block A1 and τ act inside block A2 so matrix ψ(σ) preserve Xf .
We show that if there exist element i ∈ A2 such that σ(i) 6∈ A2 then
σ 6∈ S(f). So let there exists such element. We consider a boolean vector
x in the form 0n1x2 such that coordinate xi = 1.
The element v in the vector Xf corresponds to x is equal 1. Under
an action of matrix ψ(σ) on the Xf this vector can be transform to the
following elements: (a) vi1
which corresponds to vector of type 1n1x2; (b)
vi2
which corresponds to vector of type x10n2 ; (c) any element vi3
where
i 6= s · 2n2 , s = 1, 2, ..., 2n1 . In situations (a),(b),(c) we have that
AσXf 6= Xf
Moreover element v which corresponds to vector x can not be transform
to element v′ which correspond to the vector of type x11n2 . So S(f) =
Sn1
⊕ Sn2
.
Another natural construction is wreath product of two permutation
groups. Let (G,X) and (H,Y ) are permutation groups where |X| = n,
|Y | = m. We take a group (G×H,X × Y ). An action on the set X × Y
is given by the rule
(x, y)(g1,...,gm;h) = (xgy , yh)
where gi ∈ G, for i = 1, 2, ...,m,h ∈ H. We can see this action as
an action on the set A = {1, 2, ..., nm}. This set is divided into sets
Ai = {(i − 1)n + 1, ..., in}, for i = 1, 2, ...,m. Group G act inside Ai
independently, H act on the indexes of Ai.
As before in [3] and [7] authors consider wreath product of two per-
mutation groups, but we are interested in exact boolean function which
represent this product. Here we present construction of 2 valued boolean
function which represent wreath product of two symmetric groups.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
82 Matrix characterization
Let’s take
Xf =
v1
...
vi
...
v2n
=
1
...
vi
...
1
(10)
where vi = 1 iff vector x which corresponds to vi is in the form x1x2...xn2
,
xi = 0n1 or xi = 1n1 , i = 1, 2, ..., n2.
Theorem 5. For any positive integer n1, n2 the 2 valued boolean function
f constructed in (10) hold following condition
S(f) = Sn1
≀ Sn2
Proof. Let n1, n2 are any positive integer numbers, n1n2 = n. We put
A1 = {1, 2, ..., n1}, A2 = {n1+1, ..., 2n1}, ..., An2
= {(n2−1)n1+1, ..., n1n2}.
Let’s take a boolean function f defined in (10) and a vector Xf of value
of that boolean function. Now we show that S(f) = Sn1
≀ Sn2
. It is easy
to see that for every permutation σ ∈ Sn1
≀ Sn2
we have Xf = AσXf .
From the other hand if σ 6∈ Sn1
≀ Sn2
there exist positive integer i such
that σ(A1
i ) 6= A1
j , for j = 1, 2, ..., n2. Without loose of generality we can
assume that i = 1. Now we consider an element vk = 1 which corresponds
to the boolean vector x = 1n10n1 ...0n1 . An action AσXf give us a new
vector where element vk = 0. This situation take place because operation
Aσ change elements from different blocks, but not all block is changed by
another block. We have
AσXf 6= Xf
so S(f) = Sn1
≀ Sn2
4. Final remarks
The results of this paper show that we can construct the matrix
characterization of symmetry groups of boolean functions. In the section
2 we give some properties of this characterization. We show how we can
create permutations from S(f) when we have matrices which satisfy the
equation AX = X where X is a vector of value of function f . In the
section 3 using linearization techniques we give a special construction
of boolean functions which represent direct sum and wreath product of
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
P. Jasionowski 83
symmetric groups. Interesting question is to apply this characterization
of symmetry groups of boolean functions to construct boolean functions
which represent other well known permutation groups.
References
[1] N.L. Biggs, A.T. White Permutation groups and combinatorial structures, London
Math. Soc., Lecture Notes Series 33, Cambridge Univ. Press. Cambridge, 1979.
[2] P. Cameron.: Permutation Groups., Cambridge University Press, Cambridge ,
1999.
[3] P. Clote, E. Kranakis, Boolean function invariance groups, and parallel complexity.,
J. Comput., Vol. 20, No. 3, 1991, 553-590.
[4] P. Clote, E. Kranakis, Boolean function and Computation Models , Springer, Berlin
, 2002
[5] M. Grech, A. Kisielewicz, Direct product of automorphism groups of colored graphs,
Discrete Math., 283, 2004, 81-86.
[6] M. Grech, Regular symmetric groups of boolean function, Discrete Math., 310,
2010, 2877-2882.
[7] A. Kisielewicz, Symmetry groups of Boolean functions and constructions of per-
mutation groups, Journal of Algebra., 199 , 1998, 379-403.
[8] W. Peisert, Direct product and uniqueness of automorphism groups of graphs,
Discrete Math., 207, 1999, 189-197.
[9] H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1864.
[10] W. Xiao, Linear symmetries of Boolean functions, Discrete Applied Math., 149,
2005, 192-199.
Contact information
P. Jasionowski Institute of Applied Mathematics
Silesian University of Technology
ul. Kaszubska 23, 44-100 Gliwice, Poland
E-Mail: pawel.jasionowski@polsl.pl
Received by the editors: 27.02.2012
and in final form 25.04.2012.
P. Jasionowski
|