Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
в статиотических приложениях, точнее в теории планирован! экспериментов.
Два типа объектов обычно называются элемента и блоками. В приложениях,
заложивших основы этой теори элементами обычно были сорта растений или
удобрения, Чнс элементов обычно обозначается через и, а число блоков -
через]
Схема, в которой каждый блок содержит одно и то же чщ| элементов, равное
k, а каждый элемент инцидентен одному н тё* же числу блоков г, называется
схемой инцидентности или тической конфигурацией. Очевидно, что
V? J.v
vr hk. (1|
/ *• '• •
Если v - Ь и, следовательно, г - к, то соответствующая схС^ инштдентности
называется симметричной. Например, точки прямые проективной плоскости PG
(2, Ffi) образуют симметр|| ную схему инцидентности с v - Ь = q2 f q {- 1
и г = 1| == q +¦ !. Свойство проективной плоскости, состоящее в том,
каждая пара различных точек инцидентна единственной пряС приводит к
следующему определению, обобщающему это свойст
9.72. Определение. Схема инцидентности называется урф" вешенной неполной
блок-схемой или (о, к, к)-блпк-схемой, если.Ц*
2 и каждая пара различных элементов инцидентна одй;Г и тому же числу
блоков X. Далее для краткости будем назш^^ ее просто блок-схемой.
• • • -Г Y-
Если для любого фиксированного элемента at подсчитЦ двумя способами число
всех различных пар (ай, Б), где а% а В - блок, инцидентный паре (пь аг),
то мы приходим к tjf деству
г {к - 1) - X (и - !), (§4
'• '/ j
которое должно выполняться для любой (у, ky Х)-блок-схе#| Таким образом,
нз (9.9) и (9,10) следует, что параметры b Ijjj блок-схемы определяются
значениями параметров v, к и X, }
: 4
9.73. Пример. Пусть (0, 1, 2, 3, 4, 5, 6} - множество зС* ментов, а
подмножества {0, I, 3}, {1, 2, 4}, {2, 3, 5}, {3, 4, С {4, 5, 0}, {5, 6,
!}, {6, 0, 2} образуют множество блоков. Отишг] ние иицидентности между
элементами и блоками определяй! очевидным образом. Тогда это симметричная
блок-схема с ё]
- Ь - 7, г ¦ к 3 и X - 1. Эта схема эквивалентна плоско Фано из.примера
9.55. В общем случае если к -- 3, а X -
§ 4. Приложения к комбинаторике
633
соответствующая блок-схема называется системой троек Штейнера .
9,74. Пример. Блок-схему можно получить, выбирая в качестве элементов
точки некоторой проективной или аффинной геометрии, а в качестве блоков
/-плоскости для некоторого фиксированного /, ! < / < т, где m - порядок
соответствующей геометрии. В случае проективной геометрии PG (т. F$)
параметры
соответствующей блок-схемы имеют вид
/-4-1 i
чт+' ~ 1 ь = П чт~1+' ~ 1 г = П qm~'+i ~ 1
V
1 • о, ч'~ 1 • ,v, *'-1
1 * 14 J _ 1
t= f Я ~ 1
'Ь
где при t = 1 последнее произведение полагается равным !. Полученная
блок-схема является симметричной, если / ~ гп - !, т е. если блоки
являются гиперплоскостями проективной геометрии PG (т, SF9). В
случае аффинной геометрии AG (т, (р9)
параметры соответствующей блок-схемы задаются формулами
t ... t ...
j r-г nm-t+i i
-7-;-. г=П?
t-1 ?'-1 fct C-1
g~.
Я
где, как и выше, X = 1 при / = 1. В аффинном случае такая блок-схема не
может быть симметричной. ?
Схему инцидентности можно описать с помощью ее матрицы инцидентности. Эта
матрица, обозначаемая в дальнейшем через Л, имеет v строк и b столбцов,
строки соответствуют элементам схемы, а столбцы - блокам. Занумеруем
элементы и блоки. Тогда если t-й элемент инцидентен /-му блоку, то
положим (/, /}-й элемент матрицы А равным !, в противном случае положим
его равным 0. Сумма элементов по каждой строке равняется г, сумма по
каждому столбцу равняется k.
Если А - матрица инцидентности (v, k, Х)-блок-схемы, то скалярное
произведение любых двух не равных между собой строк матрицы А равняется
X. Отсюда следует, что если через Лт обозначить транспонированную матрицу
А, то
г X ... X
634
Гл. 9. Приложения конечных полей
где / обозначает единичную матрицу размера их и, а 7 - того же размера,
все элементы которой равняются 1, Для тог чтобы найти определитель
матрицы ЛЛТ, вычтем сначала первы столбец из всех остальных, а зртем
прибавим к первой строку сумму всех остальных строк. В результате,
используя (9Л0| получаем
•ч
№
•Д
•4
щ
'№
det (А Ат)
rk 0 0 0
X г - X 0 0
X 0 i i >* 0
X 0 0 г X
= rk (г - X)
о- 1
VV 8*
'tic
¦4
т
Ж
Нели v - к, блок-схема становится тривиальной, так как в случае каждый
блок инцидентен всем и элементам. Если у > то но (9.10) г > X, и тогда
ранг матрицы ЛЛТ равняется и. трмца Л не может иметь меньший ранг. Таким
образом, мы пол j чаем соотношение
м
•\tv-
(9.1
Из (9.9) и (9.11) получаем также, что г > к.
Для симметричной (у, k, Я)-блок-схемы справедливо раве ство г к. Отсюда
следует, что AJ = JА и что матрица Л ком мутирует с матрицей (r~ X) / +
X/ = ЛЛТ. Если у > к, то Л невырожденная матрица, и потому ЛТЛ - ЛЛТ (г -
X) / j- X 7. Отсюда следует, что любые два различных блока имеют ровно
общих элементов. Последнее свойство очевидным образом с праве; ливо, если
у = к.
Мы видели, что условия (9.9), (9.10), а также (9Л1) являютс необходимыми
