A Generalization of Magic Squares with Applications to Digital Halftoning.

Saved in:

Bibliographic Details
Title:	A Generalization of Magic Squares with Applications to Digital Halftoning.
Authors:	Aronov, Boris¹, Asano, Tetsuo² t-asano@jaist.ac.jp, Kikuchi, Yosuke³ kikuchi@qci.jst.go.jp, Nandy, Subhas⁴ nandysc@isical.ac.in, Sasahara, Shinji⁵ shinji.sasahara@fujixerox.co.jp, Uno, Takeaki⁶ uno@nii.jp
Source:	Theory of Computing Systems. Feb2008, Vol. 42 Issue 2, p143-156. 14p. 2 Diagrams, 2 Graphs.
Subjects:	Magic squares, Halftone process, Algebraic number theory, Irregularities of distribution (Number theory), Prime numbers, Matrices (Mathematics), Algorithms
Abstract:	A semimagic square of order n is an n× n matrix containing the integers 0,..., n 2−1 arranged in such a way that each row and column add up to the same value. We generalize this notion to that of a zero k× k -discrepancy matrix by replacing the requirement that the sum of each row and each column be the same by that of requiring that the sum of the entries in each k× k square contiguous submatrix be the same. We show that such matrices exist if k and n are both even, and do not if k and n are relatively prime. Further, the existence is also guaranteed whenever n= k m , for some integers k, m≥2. We present a space-efficient algorithm for constructing such a matrix. Another class that we call constant-gap matrices arises in this construction. We give a characterization of such matrices. An application to digital halftoning is also mentioned. [ABSTRACT FROM AUTHOR]
	Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	A semimagic square of order n is an n× n matrix containing the integers 0,..., n 2−1 arranged in such a way that each row and column add up to the same value. We generalize this notion to that of a zero k× k -discrepancy matrix by replacing the requirement that the sum of each row and each column be the same by that of requiring that the sum of the entries in each k× k square contiguous submatrix be the same. We show that such matrices exist if k and n are both even, and do not if k and n are relatively prime. Further, the existence is also guaranteed whenever n= k m , for some integers k, m≥2. We present a space-efficient algorithm for constructing such a matrix. Another class that we call constant-gap matrices arises in this construction. We give a characterization of such matrices. An application to digital halftoning is also mentioned. [ABSTRACT FROM AUTHOR]
ISSN:	14324350
DOI:	10.1007/s00224-007-9005-x