Abstract: Some transformations have been designed and used on the Special (132)-avoiding Patterns of Permutations reported earlier by the Author. In this report, an algorithm has also been used to derive some matrix representations of the special permutation Scheme using binary coding. By the current development, an important theorem has now been formulated expressing some useful relationships between this scheme and a system of cellular algebra.
INTRODUCTION
The Special (132)-avoiding Permutation Pattern was earlier on Studied (Ibrahim and Audu, 2005; Ibrahim, 2007) in relation to some group theoretic Properties, Graph theoretic properties and enumeration procedure as permutation-avoiding subwords. Algorithmic method was also employed (Ibrahim, 2007) in the construction of some Eulerian circuits using the said scheme.
Algorithms are viewed, in Mathematics and computing as a set of procedure for accomplishing some task which posses a given initial state and a well defined end state. Algorithms have been used extensively in relation to graph-theoretic models (Ibrahim, 2006, 2007). Further, in relation to interconnection networks (Drager and Fettwies, 2002), algorithms have also proved to be very useful tools.
In this study, a relationship has been established between the special permutation pattern and cellular algebra. This procedure not only provide a good exposition of the subject matter of pattern avoidance but also introduces some new dimensions of theoretic interpretations of this class of permutation patterns in terms of other mathematical structures; such as coherent configurations.
In order for a good understanding of the paper, some basic notions are supplied below:
Cellular Algebra
A cellular algebra otherwise called a coherent configuration, can be defined
as an algebra on square matrices of complex numbers having some finite
basis
| (1) |
defined on a nonempty set
Ω = {1, 2,...,n} |
(2) |
and consisting of matrices whose entries are strictly 0 and 1 satisfying the following:
| • | |
| • | There exists a subset of (1) whose sum is I; the identity matrix. |
| • | The set Γfinite of 10 is closed under transposition. That is, for each i, there exists i* such that (Bi)T = Bi* |
| • |
| |
(3) |
Where, qi,jk in Eq. 3 are integers such that 1≤i, j, k≤m for some positive integer m. These integers are called intersection numbers. |
|
A detailed treatment of cellular algebra can be found in notes due to Cameron (n.d) especially in relation to association scheme and permutation groups (http://kissme.shinshu-u.ac.jp/as/). Further, Delsarte (1973) did one of the good investigations on relationships between association schemes and cellular algebra.
However, the approach in this research is on the use of succession schemes to propose a study of and a relationship there from with a system of cellular algebra.
Permutation Pattern
The listing 1,2,...,n of objects in a definite order is called a sequence.
And where a particular order of arrangement is desired, such an arrangement
becomes an ordered arrangement governed by a pattern and According to
Ibrahim (2007) each such permutation pattern σ ∈ Sn {n} naturally
results into a certain arrangement of 1,2,...,n given by:
σ(1)σ(2)...σ(n) |
(4) |
and is referred to as the arrangement associated with a permutation pattern of points of a nonempty set Ω.
On the other hand, permutation avoiding a particular pattern of arrangement can be understood in the light of two sequences: a sequence π consisting of n elements arranged in a given pattern and another sequence σ having m elements such that m<n. In such situations σ is said to be contained as a pattern in π provided π has a subsequence which is order isomorphic to σ. If π does not contain σ it is said to avoid it. The set of all the σ-avoiding permutations is denoted Sn(σ).
ALGEBRAIC INTERPRETATIONS
The fact that this special succession scheme forms a cyclic Structure has been reported earlier (Ibrahim, 2007). It was also reported that the scheme could be used to construct some interesting eulerian circuits (Ibrahim, 2007).
The main point of emphasis in this communication is therefore focused on finding out some further algebraic properties of this scheme as applied to a five element sample and, by extension, to samples of size n where n>5. This is achieved in this research by discovering some general rules satisfied by the scheme for all n∈|An,subwords|, n = 3,4,... (Ibrahim, 2007). In particular, the research identifies some useful transformation schemes using the established theoretic properties of the special permutation pattern in conjunction with the algorithmic procedure to discover some interesting interrelationships between the different structures of cyclic elements, the special permutation-avoiding patterns and the matrices of binary coding scheme.
Finally, the study proposes an open problem in the recommendation section.
Formulation of Cyclic Structures
Consider the special (132) avoiding subwords as reported (Ibrahim, 2007).
For sake of clarity, the format of the succession is treated in the following
proposition which also establishes a group-theoretic formalism of the
pattern as mentioned before.
Proposition One
Consider a mapping βn(x) on points x of a non empty set
Δ whose cardinality is |Δ| = n which acts on x in
such a way as to generate a cycle of consecutive positive integers with
x as the first element of a permutation pattern whose highest integer
is the cardinality |Δ| = n of a non-empty set. Then, βn
generates cycles which posses some interesting group-theoretic property
and which define a special pattern avoidance when viewed as subwords.
Proof
Based on the given conditions βn: Δ → (12...n)
so that βn(x) = (x(x+1)...n) and inductively over all
the points of Δ.
Without loss of generality, the following cycles are generated subsequently
((x + 1) (x + 2) ...x), ((x + 2) (x + 3) ...
(x + 1)),...(n x ... (n–1)) |
The results follow since each of the identical cycles forms a two group when paired with identity permutation (1). Further, when viewed as permutation subwords each of the elements generated represents a different subword which is also (132)-avoiding.
Example
For sample if we consider a set Δ of size |Δ| = 5
we have thus:
β5 (1) = (1 2 3 4 5), β5
(2) = (2 3 4 5 1), ..., β5 (5) = (5 1 2 3 4), |
Formulation of Algorithm
The following algorithm transforms the permutation patterns constructed
in the foregoing into matrix representation using a special coding scheme.
Step One
In the first row of the nxn matrix assign a 1 to the position ai,j
corresponding to the value i of the ith matrix element. The rest are assigned
a 0.
Step Two
Shift the entry 1 in the subsequent rows so that the non-zero entries
shift consecutively towards subsequent positions in the right of the diagonal.
Step Three
Continue the procedure in step two until a square matrix is formed.
Step Four
End if a square matrix is formed. Otherwise go to step two.
Example
The following example uses the above algorithm to construct matrices An
for sample of size n = 5.
It follows that for an mxm matrix, the algorithm is iterated m times so that at any stage t, the position of the non-zero entry on the first row is shifted rightwards as ai,j thereby generating m matrix elements.
As a further illustration, consider the following proposition and the accompanying example.
Proposition Two
Perform a transformation μ from elements of the special (132)-avoiding
subword βn(x) to elementsof corresponding nxn matrix representations
An defined by μ: βn(x) → An.
Then, the points x,x+1,... of the nonempty set Δ correspond to the
positions Ax,Ax+1,... of the corresponding nxn matrix
representations An which also specify the positions ax,j,ax+1,j
of the non-zero entries in such matrix representation.
Proof
The general form of βn(x) is βn(x) = (x(x
+ 1). . . n). Thus, for x = 1 we have the cycle (1,2,...n). It then follows
that the points 1,2,…n represent the positions of the non-zero entries
of the first matrix representation A1.
Using similar technique we can generate the rest of the transformations. That is, we can transform βn(2) to A2, βn(3) to A3 and subsequently.
The result follows.
APPLICATION
We state below a very interesting result linking up the enumeration scheme of the reported permutation pattern with cellular algebra.
Theorem
Denote by An = {β5(1), β5(2),...,βn(n)}
the set of cycles βn(x) of length 5 and assume a transformation
as in proposition two. Then A5 forms a cellular algebra.
Proof
Use A1 to A5 as in the example provided above. Then, define
a linear space over
Then;
| (3) |
Similarly, for each i ∈ {1,...,n} there exist i such that AiT = Ai. This follows readily since each Ai a is square matrix coupled with the fact that the sum total of all the five matrices gives rise to Eq. 3 above.
As a counter example, suppose for some i ∈ {1, ..., n}, AiT produces a matrix containing a 2 as an entry so that as,j = 2 say, for some s ∈ Ω. This will imply that for some matrix As s ∈ Ω one of the entriesis a 2 contradicting the definition of Ai hence, the result.
CONCLUSION
The special (132)-avoiding pattern of permutation under study has proved to have some useful algebraic-theoretic properties. In this study, more properties of this pattern have been investigated through some transformations using binary coding scheme and based on a designed algorithm.
RECOMMENDATION AND OPEN PROBLEM
More transformations should be investigated using this special succession scheme so as to further reveal more of the useful properties and applications. In addition, researches should focus on revealing more interrelationships of this permutation pattern and other algebraic structures. For instance, more relationship can be investigated in relation to semi groups and loops.