A generalization of magic squares with applications to digital halftoning

Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas C. Nandy, Shinji Sasahara, Takeaki Uno

    Research output: Contribution to journalArticlepeer-review


    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×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.

    Original languageEnglish (US)
    Pages (from-to)143-156
    Number of pages14
    JournalTheory of Computing Systems
    Issue number2
    StatePublished - Feb 2008


    • Digital halftoning
    • Discrepancy
    • Latin square
    • Magic square
    • Matrix

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computational Theory and Mathematics


    Dive into the research topics of 'A generalization of magic squares with applications to digital halftoning'. Together they form a unique fingerprint.

    Cite this