References of "Eastham, Chip"
     in
Bookmark and Share    
Full Text
See detailSudokus' ranks
Merciadri, Luca ULg; Eastham, Chip

E-print/Working paper (2011)

A Latin square of order n^2 is a Sudoku matrix if subdividing its entries into n^2 disjoint n-by-n subblocks causes each symbol to appear once in each subblock. Symbols are taken from {1, ..., n^2}, and n ... [more ▼]

A Latin square of order n^2 is a Sudoku matrix if subdividing its entries into n^2 disjoint n-by-n subblocks causes each symbol to appear once in each subblock. Symbols are taken from {1, ..., n^2}, and n^2 = 9 then corresponds to the familiar recreation. A construction of cyclic latin squares (see Shiu, W.C. and Fang, K.T. and Ma, S. L., On the Rank of Cyclic Latin Squares, Linear and Multilinear Algebra, Vol. 40, pp. 183-188) determines their minimum rank and shows they can attain full rank. It follows that Sudoku matrices can also be full rank. The present authors initially thought that the minimum ranks of Sudoku matrices would equal the minimum ranks of cyclic latin squares of the same order, i.e. 1 + \sum_{i=1}^{s} \varphi\left((p_i)^{t_i}\right) where n=\prod_{i=1}^{s} (p_i)^{t_i} is the prime factorization (of n), and \varphi is Euler's totient function. However, a block-cyclic latin square construction is found that attains a smaller rank. For the case n^2 = 9, one gets a rank 5 matrix rather than rank 7. Some generalizations such as taking symbols from {0, ..., n^2 -1} are discussed, and comparisons made to ranks of more general kinds of latin squares. We also discuss the possibility of finding a rank inferior to 5 for a 9*9 Sudoku matrix. (Until here, no test revealed such a possibility, but tests are not finished yet.) [less ▲]

Detailed reference viewed: 55 (11 ULg)