Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

On an Algorithm for Obtaining All Binary Matrices of Special Class Releted to V. E. Tarakanov’s Formula

Krasimir Yordzhev

Faculty of Mathematics and Natural Sciences, South-West University “N. Rilsky”, Blagoevgrad, Bulgaria

Abstract: An algorithm for obtaining all n×n binary matrices having exactly 2 units in every row and every column is described in the paper. After analysing the work of the algorithm a formula for calculating the number of these matrices has been obtained. This formula is known and has been obtained using other methods, which by their nature are purely analytical and not constructive. Thus a new, constructive proof of this known formula has been obtained.

Keywords: binary matrix, algorithm, constructive proof, tarakanov’s formula

Received September 23, 2013; Revised October 08, 2013; Accepted October 09, 2013

Citation: Krasimir Yordzhev, On an Algorithm for Obtaining All Binary Matrices of Special Class Releted to V. E. Tarakanov’s Formula. Journal of Mathematical Sciences and Applications, 1 (2). 36-38. January 2013. doi:10.12691/jmsa-1-2-5

1. Introduction

Everywhere in the current work will denote the set . If is a finite set, as usual will denote the cardinality of , and with we will be denoting the set of all permutations of the elements from . With we will be denoting the symmetric group, . If , then is the image of by the mapping .

Binary is called a matrix whose elements belong to the set .

-matrices we will call all binary matrices, in which in every row and every column there exist exactly identities and zeros. In the current work we will examine the following

Problem 1 Obtain all -matrices.

Let us denote with the number of all -matrices. In [3], the next formula is shown:

[picture] | (1)

Let us notice that formula (1) does not give a solution to problem 1, it only calculates the number of the objects which are being sought. We will give a solution to problem 1 with the help of algorithm 1 described below. Furthermore, formula (1) has been obtained by V. E. Tarakanov when examining an equivalence relation in the set of all ordered pairs of derangements. Let us remind that is called derangement, if for every . In the current work we will suggest a new constructive proof of formula (1) by suggesting an algorithm for obtaining all -matrices.

2. The Main Results

A partition of the set we will be calling every family of sets , such that for every , when . The subsets are called blocks of partition. We say that a partition is of type , if there exist exactly blocks with cardinality , . As it is well known [1] there exists an one-to-one correspondence between the set of all types of partitions of , and the set of all solutions to the equation .

Algorithm 1 Obtaining all -matrices.

1. For every solution to the equation Do begin

2. For every partition U of of type Do begin

3. For every partition V of of type Do begin

4. For every , for which Do begin

5. Form the sets

and

where U,V,

6. For every Do begin

7. For every Do begin

8.

/* - integer; - set of integers */

9.

10. For every permutation Do begin

11. For every permutation Do begin

12. If Then return to 11;

13.

14. Obtain the set of three-dimensional vectors:

15. End 11

16. End 10

17. End 7

18. Form the set

19. For every -tuple Do begin

20. Form the set of three-dimensional vectors:

21. End 19

22. End 6

23. End 4

24. For every -tuple Do begin

/* If , then by definition and . */

25. For every -tuple Do begin

/* If , then by definition и . */

26. Form the set of three-dimensional vectors:

/* If , then by definition и . */

27. From obtain only -matrix , such that if , then in in -th column the only two units stand in rows with numbers and ;

28. End 25

29. End 24

30. End 3

31. End 2

32. End 1

Theorem 1. With the help of algorithm 1, all -matrices are obtained, moreover during every execution of statement 27 a different -matrix is obtained.

Proof. Let and be two vectors from set , which is obtained during execution of statement 26 from algorithm 1. If there exist and , such that (i.e. and are obtained during single execution of statement 14), then according to statements 10 and 14 . According to statements 20 and 26 it is not possible to exist , , such that and and to be from one and the same set , which is obtained during execution of statement 26. If when , then and are from different blocks of the partition U, i.e. again . Furthermore, obviously for every there exists a block , such that and according to statements 10 and 14 there exist a natural number and , such that . Therefore, the first elements of every vector in the set during single execution of statement 26 correctly indicate a number of a column in a matrix.

Let . Since statements 11,12,14 and 26 are inner for loops with numbers 2 and 3, then according to these statements there exist unique three-dimensional vectors and , from the set during single execution of statement 26, such that be at second position in and at third position in . Therefore, in the matrices which are obtained in statement 27 there are exactly two units in every row and according to statement 27 exactly two units in every column.

We assume that there exist two sets and , obtained during different executions of statement 26, which are equal to each other. Then , which is impossible, bearing in mind the courses of action of statements 14, 20 and 26, and with what objects they work during each of their executions. Therefore, during every execution of statement 27 a different -matrix is obtained.

Let us denote with the set of the matrices obtained during the work of statement 27. Since in there are not any duplicate elements, then .

Let be an arbitrary -matrix. We will show that . Let in the beginning have not any marked rows and columns. In we build a walk, starting from the upper ''1'' of the leftmost unmarked column of the matrix, we continue to the next below ''1'' in the column, after that we reach the second ''1'' from the same row, then the second ''1'' from the same column and so on until we return to the initial cell. Moving on this walk we mark the rows and the columns we pass, and when passing through -th column we obtain the vector (we have first passed through the ''1'' in -th row, then through the ''1'' in -th row). We continue the same process with the unmarked rows and columns until we mark the whole matrix. Let be the minimum number among the numbers standing at first position of the vectors corresponding to a particular walk. Since the beginning of the loop starts from the upper ''1'' of the leftmost column of the walk, then for the vector the inequality is satisfied. Therefore, for every walk we obtain a set of vectors, which are obtained in statement 14 as well. Uniting the sets of all vectors which are obtained from walks in with the same length, we obtain a set, which is obtained in statement 20 as well. The union of all such sets corresponding to a particular matrix, is a set, which is obtained in statement 26 as well. Therefore , whence the assertion of the theorem follows.

With the help of Algorithm 1 and Theorem 1 we will also prove the next theorem, proven in [3] in a different way.

Theorem 2. [3] The number of all -matrices is given by the formula:

Proof. Let us denote with the number of the iterations of loop with number in Algorithm 1. Since Algorithm 1 has been maid so that every time during execution of statements 14, 20, 26 and therefore also statement 27 (it follows from Theorem 1) different objects are obtained, then

[picture] | (2)

It is easy to see that

According to a well-known formula [1] the next equation is true:

For and we obtain respectively:

Substituting in (2) we obtain the assertion of the theorem as well.

3. Conclusion

Comparing the proof of theorem 2 to formula (1) we are convinced of the high efficiency of algorithm 1. This is practically a proof of the fact that algorithm 1 works exactly as much as necessary.

References

[1]   | M. Aigner. Combinatorial Theori. Springer-Verlag, 1979.
[2]   | P. Lancaster, Theory of Matrices. Academic Press, NY, 1969.
[3]   | V. E. Tarakanov, Combinatorial problems on binary matrices. in Combinatorial Analysis, Vol. 5 (1980), Moscow State University, 4-15. (in Russian).