On the number of disjoint pairs of S-permutation matrices

DOI10.1016/J.DAM.2013.06.007MaRDI QIDQ2446899zbMATH OpenOpenAlexFDO

Authors Krasimir Yordzhev

Publication date 23 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.1628

zbMATH Keywords

binary matrixbipartite graphdisjoint matricesS-permutation matrixSudoku matrix

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Orthogonal arrays, Latin squares, Room squares (05B15) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Factorial statistical designs (62K15)

Abstract: In [Journal of Statistical Planning and Inference (141) (2011) 3697-3704], Roberto Fontana offers an algorithm for obtaining Sudoku matrices. Introduced by Geir Dahl concept disjoint pairs of S-permutation matrices [Linear Algebra and its Applications (430) (2009) 2457-2463] is used in this algorithm. Analyzing the works of G. Dahl and R. Fontana, the question of finding a general formula for counting disjoint pairs of $n^{2}imes{n}^2$ S-permutation matrices as a function of the integer $n$ naturally arises. This is an interesting combinatorial problem that deserves its consideration. The present work solves this problem. To do that, the graph theory techniques have been used. It has been shown that to count the number of disjoint pairs of $n^{2}imes{n}^2$ S-permutation matrices, it is sufficient to obtain some numerical characteristics of the set of all bipartite graphs of the type $g=<R_{g}cup{C}_g,E_g>$, where $V=R_{g}cup{C}_g$ is the set of vertices, and $E_g$ is the set of edges of the graph $g$, $R_{g}cap{C}_g=emptyset$, $|R_g|=|C_g|=n$.

Recommendations

• Calculation of the number of all pairs of disjoint S-permutation matrices
• On the number of mutually disjoint pairs of \(S\)-permutation matrices
• Bipartite graphs related to mutually disjoint S-permutation matrices
• On the probability of two randomly generated \(S\)-permutation matrices to be disjoint
• On an algorithm for receiving sudoku matrices

Cites work

• Bipartite graphs related to mutually disjoint S-permutation matrices
• Fractions of permutations. An application to Sudoku
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Permutation matrices related to Sudoku
• Sudoku, Gerechte Designs, Resolutions, Affine Space, Spreads, Reguli, and Hamming Codes

Cited in

(11)

• Exact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquer
• Bipartite graphs related to mutually disjoint S-permutation matrices
• On the number of mutually disjoint pairs of \(S\)-permutation matrices
• On the probability of two randomly generated \(S\)-permutation matrices to be disjoint
• A new algorithm for enumerating all possible Sudoku squares
• Semi-canonical binary matrices
• scientific article; zbMATH DE number 7113387 (Why is no real title available?)
• On an algorithm for receiving sudoku matrices
• Calculation of the number of all pairs of disjoint S-permutation matrices
• Unveiling order in chaos: a systematic approach based on graph theory in enumerating Sudoku grids of rank n
• Classification of bipartite permutation matrices under local permutation equivalence

This page was built for publication: On the number of disjoint pairs of S-permutation matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446899)