Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 140
Текст из файла (страница 140)
Все выброшенные я-ила~кости пазьваются бесконечно удаленнылги й-плоскостями. Те из оставшихся )т-плоскостей, которые пересекаются по бесконечно удаленной й-плоскости, называются параллельными. Принято в!абраг!!вать гиперплоскость, определяемую уравнением х = О. 1 ада лты можем считать, что координата х у всех точек из АВ !гп, г'„) равняется 1, и рассматривать для этих точек только ос!альные координаты. Так как Рл! (т, го) содержит д'" +... ,' а 1 точек, а удаленная гиперплоскость содержит !) -!+... .. )- й ", 1 точек, то АО (гп, )Г ) содержит д точек.
)г-плоскость в Аб (т, й'о) состоит из всех )(о точек, координаты которых удовлетворяют системе уравнений гг~охо '! ' - аьт тхт,-+а!т — — О, !'=1, ..., т — й, матрица коэффициентов которой имеет ранг т — и. В частности, гпперплоскость задается уравнением а,хо -)- + ат.гхт т -'- ат = О, в котором не все коэффициенты а,, ..., ат, равны О. Если зафиксировать коэффициенты ао, ..., а „а а заставить пробе!ап, все множество элементов поля «ч, то мы получаем пучок параллельных гиперплоскостей. $4. Приложения к комбинаторике В этом параграфе мы опишем некоторые примеры использопвюгн конечных полей в комбинаторике.
14л!еется тесная связь между конечными геометриями и так называемыми схемами '). Схемы, которые мы собираемся рас) В комбинаторной литературе термин беыйп обычно переводят как «блоке'омам но мы будем употреблять последний термин и качестве кратного синонима .'рооновеженвой неполной блок.
схемы, тем более что вто не приводит к недора- 3! чснням -- Прим. пере« 632 Гл 9. П9нланееннн конечных палей сматривать, состоят из двух непустых множеств объектов и ношения пнцидентности между объектами, принадлежащими р ным множествам. Так, например, объектами могут быть то н прямые, а отношение инцидентности определяет, лежит данн точка на данной прямой или нет. Терминология, которая обыч используется в этой области комбинаторики, берет свое нач в статистических приложениях, точнее в теории планирован' экспериментов. Два типа объектов обычно называются элемен и блоками. В приложениях, заложивших основы этой теорн элементамн обычно были сорта растений или удобрения.
Чи элементов обычно обозначается через и, а число блоков — через Схема, в которой каждый блок содержит одно и то же чис элементов. равное )е, а каждый элемент инцндентен одному и т" же числу блоков г, называется схемой инцидентногти нли тической конфигурацией.
Очевидно, что иг = Ьй. ( Если и =- Ь и, следовательно, г ---- й, то соответствующая сх'" инцидентностн называется симметричной. Например, точки', прямые проективной плоскости Рб (2, К ) образуют симмет ную схему инцидентностн с и = Ь =- ае + а + 1 н г = =- д,— 1. Свойство проективной плоскости, состоящее в том, каждая пара различных точек ннцндентна единственной пря приводит к следующему определению, обобщающему это свой ' 9.72.
Определение. Схема инцидентности называется ур еешенной неполной блок-схемой или (и, и, ))-блок-схемой, если М' ) й ) 2 и каждая пара различных элементов инцидентна од' и тому же числу блоков Х. Далее для краткости будем наз " ее просто блок-схемой, Если для любого фиксированного элемента а, подсчи "' двумя способами число всех различных пар (а,, В), где а, чн' а  — блок, инцидентный паре (а,.
а,), то мы приходим к деству (9: г (й — 1) == Д (и — !) которое должно выполняться для любой (и, и, ).)-блок-схе, Таким образом, нз (9.9) н (9.10) следует, что параметры Ь блок-схемы определяются значениями параметров и, й и Х. 9.73. Пример. Пусть (О, 1, 2, 3, 4, 5, 6) — множество ментов, а подмножества (О, 1, 3), (1, 2, 4), (2, 3, 5), (3, 4, (4, 5, О), (5, 6, 1), (6, О, 2) образуют множество блоков. Отно ние инцндентности между элементами и блоками определи ', очевидным образом. Тогда это симметричная блок-схема с а := Ь вЂ” 7, г -- й — 3 и ).
=- 1. Эта схема эквивалентна плоск Фана из примера 9.55. В общем случае если й =- 3, а Х = 1, з 4. Приложения к коиоииаторике , т-!-1 о=— о — 1 где, как и выше, Л = 1 при ! = 1. В аффинном случае такая блок-схема не может быть симметричной. П Схему инцндентности можно описать с помощью ее ма!при!)ы ииииденглности. Эта матрица, обозначаемая в дальнейшем через А, имеет о строк и Ь столбцов, строки соответствуют элементам схемы, з столбцы — блокам.
Занумеруем элементы и блоки. Тогда если !'-й элемент инцидентен /-му блоку, то положим (1, ))-й элемент матрицы А равным 1, в противном случае положим его равным О. Сумма элементов по каждой строке равняется г, сумма по каждому столбцу равняется я. Если А — матрица инцидентностн (и, й, Л)-блок-схемы, то скалярное произведение любых двух не равных между собой строк матрицы А равняется Л.
Отсюда следует, что если через Ат обозначить транспонированную матрицу А, то Л ... Л Л г ... Л ААт = =(г — Л) !+и, Л Л соответствующая блок-схема называется актемой троек Штей- нкрп. й.74. Пример. Блок-схему можно получить, выбирая в каче- стве элементов точки некоторой проективной или аффннной геометрии, а в качестве блоков бплоскости для некоторого фикси- рованного 1, 1 < Г < гп, где т — порядок соответствующей гео- метрии. В случае проективной геометрии Рб (ле, К ) параметры соответствующей блок-схемы имеют вид !е1 ! Ь=-П,, г=П т — !+! ! т — (+1 ! — ! 1-~-! !,—, т — !.~-! Л=П' где прн ! == 1 последнее произведение полагается равным 1.
Полученная блок-схема является симметричной, если ! =- гл — 1, т е. если блоки являются гиперплоскостями проективной гео- метрии Рб (гл, !г' ). В случае аффинной геометрии Аб (и, Ке) параметры соответствующей блок-схемы задаются формулами 1 1 т — г-~ ! т — ье! о=-дт, Ь=дт 'П, г= П Е вЂ” ! ! ! о — ! ! ! †! й = Ч!, Л = П ч,.+ !, 634 Гл. 9. Приложения конечных полей где ( обозначает единичную матрицу размера охи, а l — матриц того же размера, все элементы которой равняются 1. Для тог чтобы найти определитель матрицы А Ат, вычтем сначала первый столбец из всех остальных, а зртем прибавим к первой строк сумму всех остальных строк. В результате, используя (9,1Щ" получаем гя О 0 ... 0 Х г — Х 0 ... 0 Х О г — Х ...
0 де1(АА") = =- г(г (г — Х)' ) О О ... г — Л Если и --- я, блок-схема становится тривиальной, так как в это ' случае каждый блок инцидентен всем а элементам. Если и > й ' то по (9.10) г > Х, и тогда ранг матрицы ААт равняется и. М ' трица А не может иметь меньший ранг. Таким образом, мы полу' чаем соотношение (9.1 Из (9.9) и (9.11) получаем также, что г > й. Для симметричнои (и, й, Х)-блок-схемы справедливо раве ство г — й. Отсюда следует, что А( =- /А и что матрица А ко мутирует с матрицей (г — Х) ( + ХУ =- ААт. Если и > й, то А невырожденная матрица, и потому АтА =: ААт = (г — Х) ( + М.
Отсюда следует, что любые два различных блока имеют равна' ' общих элементов, Последнее свойство очевидным образом справ пиво, если и = я. Мы видели, что условия (9.9), (9.10), а также (9.11) являю необходимыми для существования блок-схемы с параметрами б, г. я, к. Однако эти условия не являются достаточными для су шествования соответствующей блок-схемы. Так, например, и н вестно, что блок-схем с параметрами о =- Ь вЂ” 43, г =- я = $ и к — 1 не существует, Элементы и блоки симметричной (и, (г, й)-блок-схемы с (г дэ и й == ! удовлетворяют условиям, которым должны удовлетво: рять точки и прямые конечной проективной плоскости. Верно М:", обратное.
Таким образом, понятия симметричной (о, й, 1)-блоич:- схемы с й > 3 и конечной проективной плоскости эквивалентн '' Рассмотрим блок-схему из примера 9.73. Будем рассматри"' вать элементы этой блок-схемы О, 1, 2, 3, 4, 5, 6 как целые числа!; по модулю 7.
Каждый блок этой схемы обладает тем свойством:"", что разности между различными входящими в него элементами; пробегают все ненулевые вычеты по модулю 7. Это приводит: к следующему определению. 4 4. Приложении н комбинаторика бзб 9.76. Определение. Множество Р = (й,, ..., йд), состоящее из 2 различных вычетов по модулю и, называется (и, я, Х)- рс1зностным множеством, если для любого й „=в- :0 (шод о) существует ровно Х упорядоченных пар (дь дл), йь Фл ЕР, таких, что д; — дл =- д (глод и). Следующий результат устанавливает связь между разностпымн множествами, блок-схемами и конечными проективными плоскостями.
9.76. ТеоРема. Пусть (с(,. ", д,) является (и, и, )) юпным мноясеством, Тогда если в качестве элементов взять все вычеты по модулю о, а в качестве блоков — множества вида В~ = )да+ (, ..., дь-!.!), 1= 0, 1, ..., и — 1, то мы получим симметричную (о, я, Х)-блок-схему с очевидным тпношением инцидентности. Доказательство. Каждый вычет по модулю о, скажем а, встречается только в тех блоках, нижний индекс которых равен одпой из величин а — д,...., а — Н„по модулю о. Отсюда получаем, что каждый элемент инпидентен одному н тому же числу блоков, равному я. Каждая пара различных вычетов по модулю о, скажем а и с, принадлежит одному блоку В, тогда и только тогда, когда а:=-.
Н, + ! (шод о) и с = д, + С (шоб о) для некоторых с(, и д,. Следовательно, а — с = — д, — дг (гпод о). Верно и обратное: если пара (до Ил) является решением последнего сравнения, то оба элемента а и с встречаются в блоке В,, где г == а — Н, (гпод о). По условию теоремы имеется ровно ). различных решений вида (сь Ил), поэтому выполнены все условия для существования симметричной (о, я, Х)-блок-схемы. сл 9.77. Следствие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
