Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
bh.bn-1 +
bhbn-i ^n-i
ll = 1 Г
^sV ¦' ' If t b ) I J
640
Гл. 9. Приложения конечных полей
Л4
':Л
№
я
¦ч
х<'?
Щх
'Щ
образуют множество из г попарно ортогональных латинск квадратов порядка
п.
Схемы инцидентности и латинские квадраты нспользуюте!
прн планировании статистических экспериментов. пусть нам требуется
сравнить урожайность п сортов пшеницу на данном типе почвы. Пусть опытный
участок представляет со бой прямоугольное поле, разбитое на л2 участков.
Даже если щ будем очень тщательно выбирать опытное поле, все равно различ
ные его участки будут отличаться по плодородию почвы, если засеять
участки первого ряда одним сортом пшеницы, ^ может оказаться, что именно
первый ряд участков отличается!5 наиболее высоким плодородием почвы, и мы
сделаем неправильный вывод о высокой урожайности этого сорта пшеницы,
оценки будут более правильными, если засеять участки такиШ образом, что
один сорт пшеницы будет встречаться по одному| разу в каждом вертикальном
и каждом горизонтальном рядах. Другими словами, посев п сортов пшеницы
надо провести такщ| образом, чтобы получился латинский квадрат порядка п.
Часто бывает необходимо одновременно учесть и другие фак торы, влияющие
иа урожайность. Пусть, иапрнмер, мы хотнм использовать п различных видов
удобрений и оценить эффектна* ность их использования. Тогда мы
распределим удобрения и сорта пшеницы по я8 участкам таким образом, чтобы
как размещений удобрений, так и размещение сортов пшеницы определяли
латЧНЙГ ский квадрат порядка п и чтобы при этом каждый сорт пшеннЩГ и
каждое удобрение "сходились" ровно на одном участке. Таквд| образом, на
языке комбинаторики латинские квадраты, соотвщ^ ствующие размещению
сортов пшеницы и размещению видб| удобрений, должны быть ортогональны.
Диалогичные прим#* нения существуют и для уравновешенных неполных блок-
схем^
В качестве еще одного примера применения теории конечньШ| полей к
комбинаторике рассмотрим так называемые матрицы Ада*| мара. Эти матрицы
используются в теории кодирования, в тЩ рии связи, а также в физике (в
виде преобразований АдамарД; в задачах, связанных с определением веса,
сопротивления, наЦ пряжения и т. п.
9.86. Определение. Матрицей Адамара Нп называется (пХаЩ матрица,
элементами которой являются +1 и -1, щая еоотношеиню
НЯН1 = п(.
Так как Щ1 = (1;д) НТП, то справедливо также соотношение
Н1НП - nl. Таким образом, любые,две различные строки, так Ж?| как и любые
два различных столбца матрицы Hnt являются орто| тональными.
ш
Vi*;, • *-у
'.:АЩ
•да
§ 4. Приложения к комбинаторике
641
Адамар показал, что определитель любой действительной (а хя)-матрицы М с
элементами, по абсолютной величине не превосходящими 1, удовлетворяет
неравенству | det М | пп^.
В случае матрицы Адамара Нп мы имеем det (НПНЦ) - пп, так что | det Нп |
- пп^, т. е. указанная верхняя граница достижима.
Одновременная смена знаков у всех элементов любой строки или любого
столбца не меняет свойств, определяющих матрицу Адамара. Назовем матрицу
Адамара Нп нормализованной, если все элементы ее первой строки и первого
столбца равны + 1. Нетрудно показать, что порядок п матрицы Адамара (аи)
может лишь равняться 1, 2 или быть кратным 4. В самом деле, для всех п >
3
?<"./
п
а2/) ("I/ + %) S аЬ ~ п>
и при этом каждый член в первой сумме равен или 0, или 4. Существует.
гипотеза, что для любого допустимого значения п существует
соответствующая матрица Адамара Нп.
9.87. Пример. Нормализованные матрицы Адамара низших порядков нмеют вид
1
1
1
Я1=,( 1), Ht-(
I
1
I
I
).
Я4 =
1
1
1
?
Приведем теперь конструктивный метод получения матриц Адамара,
использующий свойства конечных полей.
9.88. Теорема. Пусть %, aq - элементы поля q =
= 3 (mod 4), и пусть т) - квадратичный характер поля Тогда матрица
Н
(1 1 1 1 ... 11
1 1 &12 &13 * * * hq
1 V - 1 ^23 • • ¦ hq
1 &31 ^32 1 ... &3 q
1 V ЬЧ 2 bq% . . . 1 ¦
где Ьи
= ц (aj - а(), 1 i, / ^ q, i Ф /, является матрицей Адамара порядка q -
hi.
Доказательство, Так как все элементы матрицы И равны ±1, то достаточно
показать, что скалярное произведение любых
Н Зак. 243
642
Гл. 9. Приложения конечных полей
двух различных строк матрицы Н равняется 0. Скалярное нроиа ведение 1-й и
(i f 1)-й строк (1 < i < q) равно в силу (5.1
= Е п (о.) -
/?* i
1 Н->)
f . I
)+t
fli) = Е Ц (с) = 0.
¦'I
c?F
*
Я
m
Скалярное произведение (t 1 1}*й и (к < k < q) в свою очередь равно
1)-й строк (1 < I
1
- btk -f- 5] btjbkj -
!+i. к
1 _ ц (flj - ak) - r\ (ah - fl,)
/V"4L4
sj$
у-''Ця
¦ и/
=-- 1 "11 г П (- 1)) Л ("! - Oft)
+ Е Л (?) - а,) Г) (Uj - ah)
i + i, *
+ Е Л ((с - at) (с Я*))=0
в силу того, что т] (-1) - -1 для q ~ 3 (mod 4) (см. замечай^ 5.13), и
того, что последняя сумма равна -1 (см. теорему 5.48).
5 сУ*
?=>•
*у, •
- - iS<r сЛ^АТВ
Если Яп - матрица Адамара порядка и, то матрица
Л , 'А\;
н
н
н
•а
п
к ?
н
является матрицей Адамара порядка 2м. Следовательно, зт методом можно
