著者

Boris Aronov 浅野哲夫 菊地洋右 SubhasC.Nandy 笹原 慎司 宇野 毅明

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.26, pp.63-69, 2005-03-17

参考文献数

2

---

n×nの行列に整数0 ... n2-1を配置し、どの行和、列和も等しいものをsemimagic squareとよばれる。ここでは列和、行和のかわりにk×kの部分行列に含まれる要素の和を考え、この和が等しいn×n行列をzero k×k-discrepancy matrixとよぶ。そしてこのような行列はkとnがともに偶数であるとき存在し、kとnが互いに素であるとき存在しないことを示す。さらに、k m●2を整数としたときn=k*であるならばzerok×k-discrepancy matrix の存在がいえる。このzero k×k discrepancy matrixの恒星にはconstant-gap matricesを用いる。また、constant-gap matricesの特徴づけを行なう。A semimagic square of order n is an n×n matrix containning the integers 0,...,n2-1arranged 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 requiremento tha 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 sub matrix be the same.We show that such matrices exist if k and n are both even,and do not if kand n are are relatively prime.Further,the existence is also guaranteed whenever n=k ●,for some integers k,m●2. A class of matirices,called constant-gap matrices plays an important role.We give a characterization of such matrices.