ABSTRACT

Boolean homomorphisms of a hypercube, which correspond to the morphisms in the category of finite Boolean algebras, coincide with the linear isometries of the category of finite binary metric vector spaces.

Keywords:Boolean Automorphisms, Boolean Algebra, Hypercube, Linear Isometries

1. Introduction

An automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms of an object forms a group, called the automorphism group. It is, loosely speaking, the symmetry group of the object.

As is well known, a Boolean lattice is a partially ordered set with some special properties of its partial order relation, and it can also be envisaged as an algebraic system with two algebraic binary operations. This algebraic system is the so-called Boolean algebra, associated to the Boolean lattice. The Boolean algebra can also be provided with a ring structure, the so-called Boolean ring, associated to the Boolean lattice. It can even be regarded as a binary vector space, that is, a vector space over the binary field of two elements [1] . These four categories are functorial related by isofunctors that carry over the morphisms of one category over morphisms of the other [2] . The Boolean lattice is also a metric space with the so-called Hamming distance, where the morphisms are the so-called isometries.

The aim of the present work is to show that the Boolean homomorphisms, that is, the morphisms in the category of the finite Boolean algebras, are the same to the linear isometries in the category of finite binary vector spaces when the Hamming distance is used.

2. Some Previous Definitions and Concepts

2.1. Definition

Given a Boolean algebra a function such that for all x, y of B, and where 0 and 1 denote the neutral elements of respectively, is called a Boolean endomorphism. If f is bijective, it is called a Boolean automorphism.

It is immediate that, for the Boolean addition +, defined as which provides to B a structure of Abelian group, f is a group endomorphism, or a group authomorphism if it is bijective.

It is well known that the triple where denotes the obviously defined external operation of the binary field over B, is a -vector space.

It is not difficult to prove that every group endomorphism of the Abelian group is also a linear endomorphism of the vector space

The triplet is a unitary commutative ring, such that every element is idempotent, that is,

It is easy to notice that every Boolean endomorphism is also a unitary ring endomorphism, and conversely, every unitary ring endomorphism is a Boolean endomorphism.

It is also well known that, the binary relation defined as is a partial order relation with minimum and maximum 0 and 1, respectively.

The ordered pair defines a lattice, such that for every binary subset the elements and are, respectively, the least upper bound (supremum) and the greatest lower bound (infimum) of the set

A function is a Boolean endomorphism if, and only if, it is isotonic with respect to the partial order relation that is, if for all x, y of B..

If the vector space has a finite basis of n elements, we will say that the Boolean algebra is finite-dimensional, being the number n its dimension.

It can be proved that every n-dimensional Boolean algebra is isomorphic to the Boolean algebra where the operations are bitwise induced by the logic operations of disjunction and conjunction, according to the following Table1

The elements 0 and 1 represent, respectively, falsity or veracity of a proposition. The Boolean algebra is generally called the n-dimensional hypercube. It is due to the fact that in the case the triplets of zeros and ones are the algebraic representations of the vertexes of a cube, inserted, as a subset, in the 3-dimensional -vector space being the field of real numbers.

2.2. The Inner Product in the Hypercube

2.2.1. Definition

For two n-tuples and of we call scalar product or inner product of u with v the number where the addition and the multiplication are the ordinary operations in the ring of integers.

This inner product is the restriction to the set of the ordinary inner product of the Euclidean n-dimensional -vector space

If the column matrices and are the matrix representation of the n-tuples u and v, respectively, the inner product can be expressed as the matrix product where denotes the transpose matrix of X, that is, the row matrix

2.2.2. Definition

For a vector we call the norm, absolute value, or weight of u, the inner product of u with itself, denoted as Obviously, the norm is equal to the number of times the number 1 is a component of u.

It is not difficult to notice that the inner product of the vector u and v, is equal to the norm of the vector product in the Boolean ring

A vector u of norm is called unitary vector. The only unitary vectors are

and they conform the so-called canonical basis of the binary vector space

3. The Concept of Orthogonality

wang#_2title:spDefinition

We say that two vectors u and v are orthogonal or perpendicular if the inner product is equal to 0.

4. The Hamming Distance in the Hypercube

wang#_2title:spDefinition

For two vectors u and v, we define the Hamming distance between them, as the norm of their Boolean addition. Obviously, it is equal to the number of places where the components of both vectors are different.

5. Linear Isometries of the Hypercube

Definition

A function is called an isometry if it preserves the distance between points, that is, if

for all of the set.

If the isometry f is also a linear transformation, then, the matrix A of f, with respect to the canonical basis is an orthogonal matrix, that is, such that the identity matrix.

It is clear that a linear isometry also preserves the absolute value of any vector and the inner product of any two vectors.

The hypercube can also be envisaged as a graph, where the vertexes or nodes are the n-tuplesand the edges are the binary subsets such that the distance is equal to 1. Two vectors u and v of an edge that is, such that, are called adjacent points of the hypercube.

It can be proved that the Hamming distance between two points u and v is equal to the minimal length of a path between them, that is, the minimal number of edges for going from one to the other.

6. Main Results

6.1. Lemma

In the hypercube the only set of n non-null vectors, which are pairwise orthogonal, is the set of the unitary canonical vectors.

Proof: (Induction over n)

For n = 2 the assertion is trivially true.

Let us suppose that it is true for every, being

Let be a set of non-null and pairwise orthogonal vectors in the hypercube To prove that they are all unitary vectors let us suppose that one of them, say a₁ is not unitary, that is of norm Then, the vectors belong to the -dimensional vector subspace, which is the supplementary orthogonal vector subspace of the line As the vectors are linearly independent, then then in contradiction with the assumption Hence, all the vectors of the set are unitary, as we wanted to show.

Now, we are in conditions to carry out the proof of the following.

6.2. Theorem

A function f is a Boolean automorphism if, and only if, it is a linear isometry.

Proof: If f is a Boolean automorphism it means that for all u, v of and

Then, for the Boolean addition + such that, Hence, f is a linear transformation of the vector space.

For canonical vectors we have that if, and if, which means that they are unitary and pairwise orthogonal. From this, we have that if and if. Then, the vectors are pairwise orthogonal and, from the lemma, they are unitary vectors. Hence, the linear function f is a permutation of the canonical basis. Then, the matrix A of f, with respect to this basis, is orthogonal, that is, such that Then, f is a linear isometry of the space, as we wanted to prove.

Conversely, if f is a Boolean isometry, for all i and j, then for

and, ,.

Then,

On the other hand, it is known that for all u and v. Then,

.

Then, we have proved that, for all u, v elements of the space.

As f is linear we have and as for every u, we obtain that

Then, we have proved that f is a Boolean homomorphism.

7. Concluding Remarks

In this work we have demonstrated that Boolean automorphisms of a hypercube are the same to the linear isometries of finite binary metric spaces taking as a metric the Hamming distance. This fundamental result becomes of much interest when characterizing the symmetry groups of polytopes [3] . The use of the theory of categories imparts novel insights for understanding and generalizing the symmetries of any object. This result is of interest in many areas of research. For example, the representation of the Universal Genetic Code as a 6-dimensional hypercube [4] [5] has permitted to study its evolution by a series of successive symmetry breakings [6] .

Acknowledgements

MVJ was financially supported by PAPIIT-IN107112, UNAM, México.

References