数理解析研究所講究録 1440 巻 2005 年 102-106

102

D-optimal designs and group divisible designs
田村 宏樹 (Hiroki Tamura)

東北大学大学院情報科学研究科

Introduction

1

を成分が全て$\mathcal{X}_{n}$である$\pm 1$列式 $md(n)$ を持つものを$n$$n$次正方行列の集合とし、 その中で最大の行次の$\mathrm{D}$-optirnal design と呼ぶ。 $md(n)$ の上限

は Hadamard や Ehlich $[4, 5]$ らによって、 以下のように与えられてmcd 4$n$$md(n)^{2}$0$(2n - 1)$$n$-$((n - 2)I_{n/2}+2J_{n/2})\otimes I_{2}$$2_{/}^{\backslash n-2}$$\det$ $D_{n}$ $(l)$$I_{k}$

は$k$

次の単位行列、は対角成分が$D_{n}(l)$($D_{n}(l)$$J_{k}$

は-1 であり、 各ブロックの大きさが、 [ロック構造をもった

$n$

$k$

次の成分がすべて 1 の正方行列、対角ブロックの非対角成分が 3$n\text{、}$$4^{\nearrow}\overline{\mathrm{T}}F^{1}\mathrm{J}$$(n - 1)I_{n}+J_{n}$$(_{\backslash }n - 1)^{n-1}$$(2n - 2)^{2}$

Gram

る。

$nI_{n}$$n^{n}$

123

但し、$+\beta \mathrm{E}\not\in_{\mathrm{i}\grave{\mathrm{t}}}\acute{\mathfrak{F}}f_{-}^{arrow}\mathrm{Y}/\dagger\overline{\mathrm{T}}F^{1}\mathrm{J}\mathcal{D}$$\mathcal{D}[perp]arrow\beta \mathrm{E}$$4\backslash$$n/l_{\mathrm{J}}^{\rceil}$$\text{、}$

その他の成分がまたは $[n/l]+1$ となる $l><l$ のブ次の正方行列である。 特に$n$が$l$の倍数であるときは、 $n=kl$ とおくと $D_{n}(l)=[(n-3)I_{k}+4J_{k}]\otimes I_{l}-J_{n}$ と表される。
$n\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d} 4)$の場合、 現在まで上限を満たす行列の存在は知られていな

いが、 存在するための$n$に関する必要条件として、かつ $4n/7-3$ が平方数であることが、$r\iota$が 63 以上の 7 の倍数

Cohn によって示された [3]$\text{。}$非存在定理と group divisible design との関連

2

Definition 1.

$(P, S, A)\mathrm{B}_{\grave{\grave{1}}}$group divisible design GDD$(v, k, m, n, \lambda_{1} , \lambda_{2})$とは、$\bullet$.

$\bullet$$P$

は点の集合で、 $|P|=v=mn$$S$

は $P$ の、$m$$A$

は $P$ の、

$k_{J}(\geq 2)$

点ずつの部分集合 (group ) への分割
点部分集合 (ブロック) のクラス

103
同一 group の異なる 2 点を共に含むプロソクは丁度$\bullet$$\text{・}$異なる group の 2 点を共に含むブロックは丁度$\lambda_{2}$$\lambda_{1}$個個

group divisible design を square さらに点とブロックを入れ替えても group divisible design であるとき、 symmetric という。

$|P|=|A|$ のとき、

GDD$\text{、}$$(v, k, m, n, \lambda_{1}, \lambda_{2})$$(\lambda_{1}-\lambda_{2}‘)J_{m})\otimes \mathrm{h}+\lambda_{2}J_{v}$のインシデンス行列 $B$ は、 $BB^{T}=((r-\lambda_{1})I_{m}+$を満たす。

Group divisible design の存在に関する Bose と Connor の定理 [1, Theorem9] の一般化として、 次が成り立つ。
Theorem 1. $n=kl$ を奇数とし、$a,$ $b,$ $c$を 0 でない整数かつ、 $a,$ $a+bk,$ $a+$$bk+cn$ がいずれも正とする。 このとき $XX^{T}=(aI_{k}+bJ_{k})\otimes I_{l}+cJ_{n}$ を満次の正方整数行列 $X$ が存在する必要条件は、(1) $a+bk+cn$ が平方数かっ、(2) $(a, (-1)^{\frac{k-1}{9_{\sim}}}k)_{p}=(a+bk, (-1)^{\frac{l-1}{2}}l)_{p}$ がすべての奇素数

たす$n$$p$に対し成り立つ。
$(\cdot, \cdot)_{p}$は Hilbert 記号を表す。

ここで、$a=n-3,$ $b=4,$ $c=-1$ とおくとCororally 2.

$n=kl\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d} 4)$とする。

$XX^{T}=D_{n}(l)$

を満たす

$n$

次の正方整数行列 $X$ が存在する必要条件は、(f) $4k-3$ が平方数かつ、(2) $(n-3)x^{2}+(-1)$ 早 y2 $=(n+4k-3)z^{2}$ が非自明な整数解を持つ。

Cororally 2 の条件を満たす $(k, l)$ の組は、 が小さい方から、 $(k, l)=(3,13)$ ,$(21,3)$ , $(7,13)$ , $(7,17)$ , $(3,49)$ , $(7,21)$ , $(7,25)$ , $(13,15)$ , $(73,3)$ , $(7,371f(3,109)$ ,と$(13,27)$ , $(7,53)$ 7 $(7,57)$ , $(13,31)$ , $(31,13)$ , $(7,61)$ , $(3,145)$ , $(7,73)_{\gamma}(73,7),$$n$$\cdots$なる。 特に、Cororally 3. $XX^{T}=D_{n}(7)$ を満たす

$n$次の正方整数行列 $X$ が存在するならば、 $n\geq 5110$$(k_{7}l)=(3,13)$については $XX^{T}=D_{n}(l)$ を満たす$\mathcal{X}_{n}$の元 $X$ が、 groupはこれまでに知られている
divisible design より得られ、 その行列式$md(39)$ の下限.1241[6] よりも大きい。
(但し、 $t^{2}=a+bk+$
一般に、 squareが存在すれば、 そのインシデンス行列中の 0 を一 1 で置き換えること$2^{50}\cdot 3^{33}$$2^{38}\cdot 3^{3.4}.$$\mathrm{G}\mathrm{D}\mathrm{D}(n, \frac{n-t}{2}, k, l, \frac{n-2t+b+c}{4}, \frac{n-2t+c}{4})$$\mathrm{c}n)$により、 $XX^{T}=(aI_{k}+bJ_{k})\otimes I_{l}.+cJ_{n}$ を満たす $X$ が得られる。 その逆が成り立つかどうかは分からないが、 ある条件下では、 そのような $X$ が存在すれば group divisible design に由来していることが示される。

104
Theorem 4. $n=kl=a+b+c$ とし、 $X$ C 、ゼユが $XX^{T}=\{aI_{k}+bJ_{k})\otimes$
以下のいずれかを満たせば、 $X$ は$I_{l}+cJ_{n}$ を満たすとする。 このとき、

square$GDD(n, \frac{n-t}{2}?

k, l, \frac{n-2t+b+c}{4}, \frac{n-2t+\mathrm{c}}{4})$(但し、 $t^{2}=a+bk+cn$ ) に由来する。

(1) $b+cl\neq 0$ かっ $XX^{T}=X^{T}X$ずつの小行列に分割したとき、 各行列の中で列(2) $c\neq 0$ かっ $X$ を$c,$$k\mathrm{x}k$の総和は一定(3)$n$が奇数、 $b\neq 0$ で $(a, b)=4$ かつ $(ac, f^{2})$ が平方因子を含まない

特に、 (f) と (3) においては、3$GDD$ はsymmetric となる。

Ehlich ブロック行列
この節では、 $D_{n}(l)$ より一般的に、 各ブロックの大きさが$k_{1},$$\cdots,$$k_{l}$である Ehlich ブロック行列 $D_{n}(k_{1}, \cdots, k_{l})$ について述べる。 $XX^{T}=Y.--$$D_{n}(k_{1}., \cdots, k_{l})$を満たす$X_{n}$の元 $X$ が存在する必要条件は、数かつ、 $Y$ が単位行列と有理同値となることである。 また、ベクトル、$\hat{v}=(\hat{v}_{1}\cdots\hat{v}_{l})$

を

$v$

をサイズ

$k_{1},$$\cdots,$$k_{l}$$\det Y$$v^{T}$が平方を $X$ の列に分割して、 各小ベクトルごとの成分の総和をとったものとすると、Lemma 5. 正則行列

$A$が $AA^{T}=B$ を満たしているとき、$v^{T}$

を $A$ の列ベクトルとすると、 $vB^{-1}v^{T}=1$ が成り立つ。
から、$\hat{v}$Lemma 6.の候補 $\{u^{(1)}, \cdots, u^{(s)}\}$ が求められ、$v^{(n)^{T}}$$v^{(1)^{T}},$$\cdots,$

を $X$ のすべての列べクトルとすると、$\sum_{i=1}^{n}v^{(i)}v^{\hat{(}i)}\wedge T=Z.--(Z_{ij})_{i,j=1,\cdots,l}$

ここで $Z_{ii}=k_{i}(n+3k_{i}-3),$$Z_{ij}=-k_{i}k_{j}(\mathrm{i}\neq j)_{\text{。}}$らない。 これらの条件から、 $XX^{T}=D_{n}(k_{1}, \cdots, k_{l})$ となるする可能性のある $(k_{1}, \cdots, k_{l})$ を列挙すると、$n$7,2,2,2,1$k_{17}\cdots$$k_{l}$$3,3,1$$1,\cdots,1$$4,3$

7
11

5,2,2,2$1,\cdots 1)$.
$\uparrow’\overline{\mathrm{T}}F^{1}lfi$$/2^{n-1}$

98875320
243$T\mp 7\pm-$$\gamma \mathrm{X}^{\backslash }\pi’\backslash$$\mathrm{O}$$\mathrm{O}$$\mathrm{O}$$\mathrm{O}$$\mathrm{O}$$\mathrm{O}$$\mathrm{O}$$\mathrm{O}$$\mathrm{O}$$\mathrm{O}$$\mathrm{O}$$\mathrm{O}$$\mathrm{O}$$\mathrm{O}$$X\in \mathcal{X}_{n}$

が存在

105

表中の 「対称」 は、 $XX^{T}=X^{T}X$ なる $X$ が存在するか否かを表す。
$(k_{1}, \cdots, k_{l})=(1, \cdots, 1)$については $n+1$ 次のHadamard 行列の存在と同値である。 $(k_{1}, \cdots, k_{l})=(2,2,2,1),$ $(5,2,2,2),$ $(4,4,4,3)$ はそれぞれ、$n=7,11,15$ の$\mathrm{D}$-optimal design t こ相当する [7]$\text{。}$また、 $(k_{1_{?}}\cdots, k\iota)=$$(7,7,7,6),$ $(9,9,9,4)$ はそれぞれ、 $n=27,31$ のこれまでに知られている [6]よりも大きな行列式の値を与える。

参考文献
[1]

$\mathrm{R}.\mathrm{C}$. Bose and$\mathrm{W}.\mathrm{S}$. Con nor, Combinatoriai properties of group divis-

ibie incomplete block designs, Ann. Math. Stat. 23 (1952), 367-383.
[2]$\mathrm{W}.\mathrm{S}$. Connor, Some relations among the blocks of symmetrical groupdivisible designs, Ann. Math. Stat. 23 (1952), 602-609.

106[3] J.H.E. Cohn, Almost$\mathrm{D}$-optimal designs, Utilitas Math. 57 (2000), 121-128.
[4] H. Ehlich, Determinantenabsch\"atzungen f\"ur bin\"are Matrizen, Math. Z.
83 (1964), 123-132.
[5] H. Ehlich, Determinantenabsch\"atzungen fiir binie Matrizen mit(mod 4), Math. Z. 84 (1964), 438-447.

$N\equiv$$3$[6] W. P. Orrick, B. Solomon, R. Dow deswell, and W. D. Smith, New
tower bounds for the maximal determinant problem, arXiv preprint
math, $\mathrm{C}\mathrm{O}/0304410$ .

[7] W. P. Orrick, The maximal {-1,1}-determinant of order 15, arXiv.
preprint math .
$\mathrm{C}\mathrm{O}/0401179$