D-OPTIMAL DESIGNS

D=
A
B
 –BT 
 AT 
D=
A
 BR 
 BR 
 –A 


© Nickolay Balonin and Jennifer Seberry, 1.05.2014

D-optimal designs catalogue and on-line algorithms


Матрицы максимума детерминанта четных порядков устроены относительно несложно, сказывается парный размер, они тяготеют к бициклической структуре, известно довольно много таких матриц.

Матрицы максимума детерминанта нечетных порядков, напротив, изучены недостаточно полно, среди них мало матриц простой структуры.

Матрицы нечетных порядков распадаются на семейства. Принцип бесконечного их разнообразия, который мы сформулируем более точно и проиллюстрируем ниже, приводит к тому, что семейства сходных между собой матриц, они небольшие. Семейство циклических матриц, например, состоит (никто ранее не высказывал этого предположения, выскажем его) из трех представителей: 3, 5, 13, см. рис. 1. Элементы 1 отображены клетками белого цвета.



Циклические матрицы максимума детерминанта порядков 3, 5, 13



Некоторые общие мотивы обустройства циклических (и бициклических) матриц максимума детерминанта и матриц Адамара просматриваются. Cогласно гипотезе Ризера порядок циклических матриц Адамара не превышает 4. Гипотеза до сих пор не доказана. Таким образом, нечетные матрицы подымают эту планку до характерного критического порядка 13. Корреляция отмеченных порядков 4, 5, 13 с длинами пар 2, 10, 26 последовательностей Голея, порождающих бициклические конструкции матриц Адамара, очевидна.



Матрицы порядков 3×5=15, 3×13=39 с детерминантом около 0.7EW


Помимо семейства циклических матриц максимума детерминанта есть моноциклы с каймой из 1 порядков первых двух простых чисел Мерсенна 3, 7 (они же – бициклы без инверсии знака вида [A B; B A] с каймой), см. рис. 2.



Циклические с каймой матрицы максимума детерминанта порядков 3, 7



Моноциклы Мерсенна, так их будем называть, заканчиваются на первом составном порядке 15, который соответствующую матрицу данной конструкции не порождает, на порядке 31 и последующих простых порядках матрицы данного семейства также не обнаруживаются. Семейство матриц порядков Ферма, соответственно, должно базироваться на первых пяти простых числах Ферма, раскроем это положение несколько полнее.

Семейству моноциклов Мерсенна вторит семейство бициклических матриц (тоже, с каймой) Ферма вида порядков 3, 5, 17, 257, 65537, повторяющих первые простые числа Ферма, здесь e – вектор из 1. Экстремальные свойства первых трех матриц малых порядков не вызывают сомнения, см. рис. 3.



Бициклические матрицы Ферма порядков 3, 5, 17



Для того, чтобы наш обзор матриц максимума детерминанта нечетных порядков был полон, мы приведем еще несколько начальных матричных портретов, в которых несложно выловить закономерность, которая препятствует их нахождению на высоких порядках. А именно, сложность структуры матрицы нарастает вместе с порядком. Возьмем для примера пропущенные в семействах матрицы порядков 9, 11, 15, рис. 4.



Сложные матрицы максимума детерминанта порядков 9, 11, 15



При внимательном рассмотрении видно, что каждую из этих трех матриц отличает свой необычный орнамент. Композиционно все они построены блочно из матрицы Мерсенна третьего порядка с обычной или инверсной диагональю.

Блочная кайма изобилует неповторяющимися у всех трех матриц деталями – для их поиска пришлось применить переборную программу под красноречивым названием “калейдоскоп”. Она синтезирует матрицы максимума детерминанта, заполняя содержимое части циклических блоков прямоугольными вложениями. Даже на низких порядках времени на поиск оптимальной структуры уходит порядком.

Первая матрица существенно отличается от второй стартовым блоком каймы. Третья матрица отличается от обоих инверсией знаков на диагонали блока Мерсенна с образованием четырех симметрично расположенных моноблоков из одинаковых элементов. Иными словами, данные матрицы не образуют семейство, поскольку их орнамент индивидуален, он не предсказуем и не повторяется.

Можно предположить, что нарастание сложности структуры вне пределов семейств матриц связано с составным характером чисел 9, 15. Приведем в противовес этому предположению следующий сэт матриц порядков 19, 21, 23, рис. 5.



Сложные матрицы максимума детерминанта порядков 19, 21, 23


Матрицы простых порядков 11, 19, 23 имеют между собой немало общего, мы видим в их составе все те же блоки малого порядка. Но на порядке 19 каждая четверть матрицы – блочная матрица с каймой, причем первая четверть отличается от трех остальных похожих на нее тем, что в ней с шагом 3 по строкам и по столбцам идут неожиданные вкрапления в виде инверсии знаков элементов. Этот необычный индивидуальный орнаментальный узор, а по Сильвестру матрицы максимума детерминанта – орнаменты, не встречается среди матриц ниже и выше ее по порядку, независимо от того, простой это порядок или составной.

Матрица 21 собрана на основе блоков не 3, а 4-го порядка, про матрицу 23-го порядка, напротив, невозможно высказать суждение, блоками какого размера она заполнена. На каждом порядке мы видим оригинальный орнамент, они не повторяются.

Наше предположение (гипотеза) состоит в том, что особенности орнаментов матриц максимума детерминанта неисчерпаемы. Поэтому с ростом порядка находить их становится все более сложно. Первая сомнительная матрица, детерминант которой не подтвержден на оптимум, встречается уже на порядке 22. Наиболее вероятное решение для размеров 22, 34, и сходных с ними в том, что n–1 не разложимо на сумму двух квадратов (помимо порядка 58), – это бициклы с парной каймой, см. рис. 6.



Матрицы максимума детерминанта порядков 22, 34



Индивидуальность матрицы 22 проявляется в том, что это единственный двоякосимметричный бицикл с каймой, с обоими симметричными блоками A, B. Аналогичная граница симметрии бициклов без каймы на порядках матриц Адамара, обнаружена на критическом порядке 32.

Часть детерминантов матриц четных порядков удовлетворяют граничному значению известного неравенства Адамара (оценка детерминантов сверху), экстремальные матрицы – матрицы Адамара. Сходное неравенство, но для детерминантов матриц нечетных порядков, предложил Гвидо Барба.

Граница Барбы. Матрицы A порядков n с элементами, не превосходящими 1-цы, удовлетворяют неравенству: |det(A)|2≤(det(n–1)I+J)=(n–1)n–1(2n–1), где I – единичная матрица, J – матрица из единиц. Максимум достигается на порядках, для которых 2n–1 – полный квадрат. Это необходимое условие, позволяющее выделить экстремальные решения, выведено из требования целочисленности экстремальной матрицы с элементами 1 и –1.

Граница Барбы достижима на последовательности порядков, описываемой как суммы квадратов близких чисел n=a2+b2, b=a+1. Матрицы Барбы порядков 5, 13, 25 (Raghavarao), 41 (Bridges, Hall and Hayden), 61 (Brower), 85? (Solomon, Orrick), 113 (Brower) и т.п., сложность орнамента чередуется через порядок (порядки 41, 85, и т.п. сложнее), 113, 145, 181, 221, 265, 313, 365, 421, 481, 545, 613, 685 и т.п., сходны с адамаровыми в том, что их детерминант достигает своей границы.

Это витражи – матрицы, построенные вставками блоков в матрицы Адамара, впервые описанные Рагхаварао и Андре Бровером. Принцип нарастания сложности орнамента справедлив и для них, алгоритм построения матриц Барбы встречается и описан лишь в общих чертах, позволяющих найти отдельные матрицы, см. рис. 7.



Матрицы максимума детерминанта порядков 25, 41



Теперь мы подходим к основному тезису нашей статьи, рассматривающей матрицы Ферма. В последовательность чисел n=4t+1 вложены как числа Барбы, отмеченные выше, так и числа Ферма (кроме первого).

Простые числа Ферма – классические объекты теории чисел, известно всего пять таких чисел Fk = 3, 5, 17, 257, 65537.

В 1796 году Карл Фридрих Гаусс обнаружил неожиданную связь между ними и геометрическими фигурами, вписав в круг правильный семнадцатиугольник и доказав более общее положение, что если число сторон правильного многоугольника равно простому числу Ферма, то его можно построить при помощи циркуля и линейки.

Эта междисциплинарная связь глубока и может находить иные оригинальные проявления. Сэт матриц порядков чисел Мерсенна относительно большой, просто устроенных матриц максимума детерминанта среди них мало, так что он обречен быть сложно устроенным. А вот с матрицами Ферма все намного интереснее.

Похоже, они образуют серьезную альтернативу матрицам Барбы. Алгоритмы построения матрицы Ферма обнаружены еще при отыскании форм, которые экстремальны на ортогональных подмножествах матриц. Вместо привычных 1 и –1 в них присутствуют элементы 1 и –b, b – иррациональное число, кайма также отличается своим значением bd ≤ 1. Иррациональные матрицы Ферма сводятся к указанным выше бициклическим формам элементарным округлением.

Таким образом, ортогональные и не ортогональные матрицы Ферма – одни и те же матрицы, отличающиеся параметрической настройкой. Это качество оригинальное и присуще также просто устроенным бициклам, которые образуют основной сэт матриц максимума детерминанта четных порядков. Иными словами, матрицы максимума детерминанта Ферма F – почти ортогональные по строкам и столбцам матрицы, близкие к квазиортогональным матрицам Адамара.

Выделенная близостью к ортогональным структурам цепочка матриц отличается от прочих матриц максимума детерминанта тем, что оптимистическая оценка Барбы для них может быть заменена прагматической точной оценкой.

Для матриц, у которых 2n–1 не составляет полный квадрат, верхняя граница Барбы B завышена. Она иррациональна и, соответственно, не достижима на экстремальных матрицах с целыми элементами 1 и –1, т.е. нуждается в коррекции в сторону уменьшения умножением ее на иррациональный множитель, меньший 1

Для матриц Ферма такой множитель составляет величину Fk–1/(2Fk–1)1/2.

Гипотеза. Матрицы Ферма порядков простых чисел n=Fk=3, 5, 17, 257, 65537, .. – матрицы абсолютного (или локального) максимума детерминанта Fk–1/(2Fk–1)1/2×B, B=(n–1)n–1(2n–1) – оценка Барбы.

В самом деле, одна из конструкций матриц Ферма затрагивает матрицы Адамара с максимальным эксцессом (сумой элементов матрицы). Будучи регулярными, имея равные по значениям суммы строк и столбцов, такие блоки легко ортогонализируются даже в том случае, когда к ним добавлена кайма из равных между собой элементов. Они порождают ортогональные по строками и столбцам матрицы, которые параметрически сводимы (округлением) к экстремальным матрицам Ферма F с элементами 1, –1, изображенным ранее на рис. 3.

Эксцесс, модуль суммы элементов регулярной матрицы Адамара H, равен |eTHe|, где e – вектор с единичными элементами, причем det(F)=(1+eTH–1e)det(H), это позволяет оценить детерминант ((n–1)1/2+1)/(2n–1)1/2, n=4u2+1, u – целое число. Знаки элементов блока H важны, наращивание 1 прибавлением eTH–1e гарантирует избыток отрицательных элементов. Поделив выражение для детерминанта на B, можно получить отмеченную выше относительную границу Fk–1/(2Fk–1)1/2.

Как видно, для порядков в виде чисел Ферма n=Fk удалось получить красивую формулу отличия целочисленного детерминанта от иррациональной для большинства порядков границы Барбы. У целочисленной матрицы детерминант должен быть целочисленным, поэтому масштабный коэффициент поправки иррационален.

Проверим границу Ферма конкретными вычислениями для чисел Fk = 3, 5, 17, 257, 65537.. Первое число 3 стартовое. Для порядка n=5 имеем целое значение поправки детерминанта Fk–1/(2Fk–1)1/2=3/91/2=1. Детерминант достигает здесь целочисленной в данной точке границы Барбы, эта матрица существует, оптимальна, и изображена на рис. 3 второй. Для порядка n=Fk=17 имеем 2Fk–1=33 – не полный квадрат, относительный детерминант равен здесь 5/331/2=0.8704... Это иррациональное число – масштабный множитель, который выступает поправкой к недостижимой иррациональной оценке границы Гвидо Барбы. Их произведение дает целое число 5/331/2×B – детерминант матрицы Ферма порядка 17. Эта матрица существует, оптимальна, и изображена на рис. 3 третьей.

Оптимальность остальных матриц порядков больше 17 не доказать переборными процедурами. Множество матриц с целыми элементами 1, –1 конечно, однако орнаменты экстремальных матриц возрастают в своей сложности.

Вслед матрице порядка Барбы порядка 255 идет матрица Ферма 257-я: имеем заранее предсказуемое относительное значение 17/sqrt(2*257–1)=17/sqrt(9*57)=0.7505.. Ее можно получить модифицированным алгоритмом Сильвестра, см. рис 8.



Матрица Ферма 257


Теорема Адамара состоит в том, что если у квадратной матрицы все элементы по модулю меньше или равны единице, то |det(A)|≤nn/2.

Верхняя граница достигается на матрицах Адамара порядков 1, 2 и n=0 (mod 4). Другими словами, с точки зрения геометрии объем n-мерного тела максимален, когда задающие его векторы взаимно перпендикулярны. Доказательство знаменитого неравенства Адамара опирается на свойство определителей, позволяющее в оценках переходить к произведению A'A, порождающему квадратичные формы от элементов, которые в данном случае просты.

Норма Адамара матрицы: h=mn1/2, m-норма равна максимуму абсолютных значений элементов ортогональной матрицы, получаемой из A нормированием столбцов.

Write D for the D-optimal design of order n = 2m. Ehlich states that |det(D)|≤(2n–2)(n–2)m–1. This leads to the optimal solution with a block-diagonal matrix DTD, where every diagonal block appears as (n–2)I+2J if 2n–2 – the sum of two squares.



Table of two squares sum


For n=22, 34, 58, 70, 78, 94, ... D-optimal designs satisfying the given equation do not exist because 2n–2 is not the sum of two squares. If the matrices A, B are circulant, then the corresponding D-optimal designs are called circulant. Write R for the reversed identity matrix also called the back diagonal matrix.



D-optimal designs D6 and D10



D-optimal designs D14 and D18*



Two versions of D-optimal designs D26



D-optimal design D30



Two Dragomir's D38 and Nick's D38



D-optimal design D46 (not symmetric!)



Dragomir's D-optimal design D62 and D66


D-OPTIMAL DESIGNS BASED ON PROPUS


Let m=3 (mod 4) and D=circ(X,Y) – two circulant symmetric matrix of D-optimal design of order 2m, then symmetric Propus matrix cells A=X, B=C=(Q+I), D=Y of order n=4m can be calculated with symmetric A=X by Goethals-Seidel-Propus array. The reversed task leads to D=circ(X,Y).



Dragomir's GSP H76 and D38



Nick's GSP H76 and D38



GSP 92 and non-symmetric D-optimal design D46



Dragomir's GSP H124 and D62


From: DRAGOMIR (symmetric case m=19), see Propus




TABLES


From: CHRISTOS KOUKOUVINOS

We can form two sets P={p1, p2,..., pr} and Q={q1, q2,..., qs} where pi, qj denote the positions of –1's in the first row of A, B respectively. Then a D-optimal design of order n=2 (mod 4): n=2m, m is odd, is formed (as above) when A, B are mxm commuting circulant matrices, with elements 1,–1, such that

AAT+BBT=(2m–2)I+2J


Since the circulant matrices A, B satisfy the the required matrix equation, the corresponding sets P, Q are supplementary difference sets 2-{m;r,s;λ}, where 2-{m;r,s;λ}, where λ=r+s–(n–2)/4 and s≤r≤0 are found from (m–2r)2+(m–2s)2=4m–2.

In the following table we give the non-equivalent supplementary difference sets, i.e. the non-equivalent circulant D-optimal designs for n=2m, m=1, 3, 5, 7, 9, 13, 15, 19, 21



From: WILL ORRICK TABLE m=23



From: BOOK OF YANG

JENNIFER PAGE | DRAGOMIR | WILL ORRICK| C. H. YANG | INEQUALITIES | REVIEW


Rambler's Top100