Reference : Sudokus' ranks |

E-prints/Working papers : First made available on ORBi | |||

Physical, chemical, mathematical & earth Sciences : Mathematics | |||

http://hdl.handle.net/2268/95678 | |||

Sudokus' ranks | |

English | |

[fr] Rangs des Matrices Sudoku | |

Merciadri, Luca [Université de Liège - ULg > > > 1re an. bac. sc. ing., or. ing. civil] | |

Eastham, Chip [> >] | |

16-Jul-2011 | |

7 | |

No | |

[en] Sudoku ranks ; Latin square ; Euler's totient function | |

[en] 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.) | |

Researchers ; Students | |

http://hdl.handle.net/2268/95678 | |

The article is not finished yet. |

File(s) associated to this reference | ||||||||||||||

| ||||||||||||||

All documents in ORBi are protected by a user license.