Сбалансированный неполный блочный дизайн SBIBD



Hadamard matrix family catalogue and on-line algorithms

© Nickolay A. Balonin, 1.05.2014


Определение 1. Сбалансированным неполным блочным дизайном (a balanced incomplete block design) BIBD(ν;k;λ) называется совокупность из ν объектов, размещенных по k штук в b блоках, так, чтобы λ блоков содержала каждую пару объектов, при этом каждый объект можно встретить в r блоках.

Пример BIBD(6,3,2). Возьмем ν=6 цифр 0, 1, 2, 3, 4, 5, построим из k=3 цифр b=10 векторов, собранных в матрицу размера 3×10 так, чтобы каждые две цифры встречались в λ=2 блоках, при этом каждую цифру можно встретить в r=5 блоках.

0
0
0
0
0
1
1
1
2
2
1
1
2
3
4
2
3
4
3
3
2
3
4
5
5
5
4
5
4
5


Параметры br/k, r=λ(ν–1)/(k–1) зависят от выбора трех основных параметров, и в состав аргументов BIBD(ν;k;λ) не входят. Это ограничение на все такие дизайны, следующие у матриц с цифрами естественным образом из ограниченности объема матрицы.

Определение 2. Матрица связности A (incidence matrix) размера ν×b BIBD(ν,k,λ), описывает его значениями элементов 1, если объект, помечаемый номером строки, содержится в блоке с номером, отвечающим номеру столбца, все остальные элементы матрицы равны 0.

Пример матрицы связности BIBD(6,3,2). Она описывает ровно тот же дизайн, что и выше, не входя в значение цифр для блоков. Важно только размещение этих 6 объектов в 10 блоках, так что

A=
1
1
1
1
1
0
0
0
0
0
1
1
0
0
0
1
1
1
0
0
1
0
1
0
0
1
0
0
1
1
0
1
0
1
0
0
1
0
1
1
0
0
1
0
1
0
1
1
1
0
0
0
0
1
1
1
0
1
0
1



Здесь мы описываем структуру одного и того же дизайна более экономными средствами, поэтому матрицу получили больше по количеству строк, чем выше.

Матрицы связности обладает свойствами, позволяющими использовать ее при построении матриц с ортогональными строками (столбцами):

AAT = (r – λ) I + λ J, J A= k J


где I, J – единичная матрица и квадратная матрица единичных элементов порядков ν, размер матрицы единичных элементов J совпадает с размером матрицы A. Если переназначить нулевые элементы как –1, то в ряде случаев справа можно получить единичную матрицу с иным множителем, конечно.

Определение 3. Симметричный дизайн SBIBD(ν;k;λ) отвечает условию b, для него k=r, то есть, каждый объект можно встретить в k блоках. Соответственно, для всех симметричных дизайнов

λ(ν–1)=k(k–1).



Определение 4. Комплементарного дизайн. Дизайну SBIBD(ν;k;λ) соответствует комплементарный SBIBD(ν;ν–k;ν–2k+λ).

Симметрия достигается у совокупностей ν, включающих неразличимые между собой объекты, например, b=ν блоков из ν элементов со двумя различимыми между собой значениями. Типичный пример симметричного дизайна: циклические матрицы, построенные на базе бинарной последовательности элементов 1 и –1.

Пример SBIBD(7,4,2). Параметр k=r=4 описывает число вхождений 1 в строку (столбец) матрицы, на рисунках это белая клетка. Параметр λ=k(k–1)/(ν–1)=2 описывает число вхождений пар 1-ц в пару соседних строк (столбцов).



Complementary pair SBIBD(7,4,2) and SBIBD(7,3,1)


Комплементарный дизайн SBIBD(7,3,1), это та же самая матрица, у которой при подсчете параметров –1 считается ведущим значением. Такие элементы выделены черным цветом слева и белым справа.

Матрицу связности A=(A+J)/2 такого дизайна несложно получить заменой ведущих элементов 1, и 0 – вспомогательных.

Для большей определенности из пары комплементарных дизайнов в качестве основного принято выбирать тот, у которого ν > 2k. Например, при определении адамарового дизайна.

Определение 5. Адамаров дизайн SBIBD(4t–1;2t–1;t–1) назван так постольку, поскольку после замены в матрице связности A элемента 0 на элемент –1, и добавления каймы из 1, мы получим нормализованную матрицу Адамара H, HHT = n I.



Complementary Hadamard matrices of order 8


У комплементарного дизайна SBIBD(4t–1;2t;t) в качестве каймы придется добавлять дефицитную в нем –1, в то время как нормальная форма должна иметь положительную кайму (этим и определяется выбор основной формы).

Обе формы могут использоваться для получения матриц Адамара более высокого порядка путем замещения внедиагональных клеток кососимметрических матриц порядка матриц Сильвестра 2t, роль компенсатора вместо каймы выполняет диагональные блоки J–2I или J [1].

ПРИМЕРЫ VITRAGE-MATRICES




Conference matrices based on core squares: p2+1



Complementary Hadamard matrices of order 28


Этот алгоритм шире по результатам, поскольку он позволяет любую матрицу Мерсенна, порядка p, вставить в кососимметричную матрицу Адамара, порядка p–3 или p+1, роль компенсатора вместо каймы выполняют диагональные блоки J–2I или J, последние меняют свой вид перестановками предсказуемым образом, если вместо циклических матриц Мерсенна используется универсальная двуциклическая их форма с каймой.



Hadamard matrices of order 28 (for p=7) and 88 (for p=11)




Hadamard matrix of order 80 (for p=5)


For p=13 we have to have complicated OD(128;2,10,58,58)

1. Jennifer Seberry and Mieko Yamada, Hadamard matrices, Sequences, and Block Designs, An Existence Theorem for Hadamard Designs, Lemma 4.8, Cases 1, 2; P. 461.

Rambler's Top100