1611141234-c9398682b029dca593d2e7400e783f93 (824980), страница 68
Текст из файла (страница 68)
Пусть теперь и любое произвольно большое натуральное число. Дополнив матрицы порядка и до ближайшего порядка 2" нулями, можно убедиться в том, что для нх умножения достаточно 0(пмяьг) = 0(пх "') опораций (уг. 8хгаввеп, 1969). Позднее было доказано (Соррегвпг1хуг-44гупо8гаг(, 1982), что достаточно и 0(пг "о) операций. Остается открытой следующая Гипотеза. Существует алгоритм, гарантирующий умножение двух п х и-матриц при больших натуральных и за 0(пг ь ) операций, где е --- любое сколь угодно малое вещественное число. 2.
Ортогональные разложения. Пусть я, — комплексное векторное пространство всех матриц порядка п с нулевым следом; С = (А Е ЛХн(С) ~ 1г А = О). Относительно операции комму тирования (А,В) = А — ВА пространство С является алгеброй Ли в1(п, С) (или, как принято говоритгь алгеброй Ли типа А„г). На Г определено невырожденное скалярное произведение (А~В) = ФгАВ, обладающее (см. (7) из ~ 2 гл. 6) свойством ассоциативности: ([А,В) ~С) = (А~ (В,С]). Легко проверяется, что ограничение (А~В)~, на подпространжь ство Яо = (г11а8(Лг,..., Л„) ~ Лг = О) всех диагональных матриц из Г. невырождено.
То же относится и к любой сопряженной подалгебре Я = Х гЯвХ, деГХ ~ 0 у' б. Нервщвнныв задачи 341 (в теории алгебр Ли говорят о подалгебре Картана Я). Можно показать, что Т как векторное пространство может быть разложено в прямую сумму подалгсбр Картана; С=91обЯ,Ж,, й391„, где Я,=Х Мхз Х, --. подходящим образом выбранные невырожденные матрицы. Ставится следующий Вопрос. Можно ли найти такие матрицы соиряжения Хи чтобы в разложении (1) тшдпростпранства М, были иопарно ортогональны! Если это так, то говорят об ортогональном р вложении (коротко: ОР) алгебры Ли л .
Существование ОР интересно с точки зрения приложений к теории конечных групп, целочисленных решеток и т.д. (см. по этому поводу монографию: Ков1г1кзп А.Т., Рйат Нии Тйер. ОгеЬояопа1 Весозпровйюпе аз1с1 1пседга1 Ьа111сея. " Вег11п К1езч Уогк: Ч'а11ег с1е Огцутег, 1994). Гипотеза. ОР алгебры Ли Т = в1(п,С) суиьествуепз тогда и только тогда, когда и = р сишпень некоторого простого числа р. В одну сторону гипотеза доказана: для каждого и = рь ОР построено. Осталось доказать, что при и ф р~ ОР построить невозможно. Очевидно, и = 6 наименьшее целое число, для которого гипотезу надо доказать или опровергнуть. Итак, существуют ли 7 попарно ортогональных 5-мерных подпространств М, в я1(6, С), удовлетворяющих условию (1)7 Ответить на этот, казалось бы, весьма конкретный вопрос пока не представляется возможным.
3. Конечные проектнвные плоскости. Развивая тему Е 3 из гл. 5, назовем прогктивной плоскостью П множество точек с выделенными подмножествами -- прямыми, удовлетворяющими следующим аксиомам. Р1. Любые двг различные точки принадлежат одной и только одной прямой. Р2. Любые две различные прямые содержат одну и только одну общую точку. Р3.
Сущгсгпвуют четыре точки, никакие три иэ которых нг лежат на одной прямой. Справедлива следующая Теорема 1. Пусть дано целое. число и ) 2. В ироективной плоскости П следующие свойства эквивалентны: 1) некоторая прямая состоит в точности из и+ 1 тиочек, 2) некоторая точка пранадлгжитп в точносто.
и+ 1 различным прямым; 3) каждая прлмол состоип~ в точности из и, + 1 точек; 342 Гл. 7. Приложения 4) каждая точка принадлежит в точности и + 1 различным 'прямым; 5) П содержит ровно их + п, + 1 точек; 6) П содержит ровно пз + п + 1 прямых; Доказательство можно извлечь, например, из книги: Холл М. Теория групп. --- ГИг ИЛ, 1962. Определение. В случае ~П~ = пи+и+1 говорят о проективной плоскости порядки»ь В ~ВА П1) будет установлено, что для любого простого числа р и любого натурального числа й существует поле Р» — — Сг (у) из у = р" элементов (при А = 1 нам это известно). Если И трехмерное векторное пространство над Р», то лл = Р(1г) — дезаргова (сьь [2)) проективная плоскость порядка у.
Вообще говоря, при й > 1 существуют и недезарговы проективные плоскости порядка ф Но (и это самое замечательное) до сих пор не построено ни одной проективной плоскости порядка п ~ р". Гипотеза. Порядок любой конечной проективной плоскяс»пи должен быть степенью некоторого просп»ого числа р. По своей формулировке эта гипотеза напоминает гипотезу из п.
2, и какая-то скрытая аналогия на самом деле существует, но задача о проективных плоскостях имеет более почтенный возраст. Реву.льтаты однако довольно скромные. Приведем интересный результат арифметического характера (Вгпск, Нуяег): если П --- проективная плоскость порядка я и и = = 1, 2 (шо»14), »по п = аз+ба сумма квадратов двух целых чисел. Скажем, и = 6., не представимое в виде суммы двух квадратов, не может быть порядком проективной плоскости. Долгие годы оставался открытым вопрос о возможности построения проективной плоскости порядка 10 = Зг + 1».
Лишь грубый счет на ЭВМ "Крейг" в течение 700 ч чистого процессорного времени привел к выводу о несуществовании такой плоскости. Разумеется, идти по такому пути далее не представляется возможным. При и > 10 гипотеза остается недоказанной. 4. Базисы пространств и латинские квадраты. На уровне понимания гл.
1 формулируется следующая Гипотеза 1 (Вота, 1989). Пусть И и-мерное векторное проширинтпво над любым бесконечным т»олвм. Предположим, ппо Вм Вг,... В„какие-то и базисов пространства К. Тогда каждый из базисов В, может быть так упорядочен, скажем, В, = (Ьп, Ью,...,Ь,и), что наборы С, = (Ъ»,Ьх,,Ьи ), 1 < у < и, тоже будут базисами в 1~'.
Другими словами, после надлежащего упорядочения каждая строка и каждый столбец матрицы В = (Ь,у) буду т состоять из базисных элементов. Уже при и = 3 возникает маленькое упражнение, а при при любых и гипотеза, имеющая отношение к теории инвариантов, у б. Нереизенные задачи пока не доказана. Между тем установлено, что при любом четном и гипотеза 1 вытекает из гипотезы 2 ниже, относящейся к другому старинному комбинаторному объекту.
Квадратную и х и-таблицу (или матрицу) Р, заполненную и символами, скажем, целыми числами О, 1,..., .п — 1, нвзывак~т латинским квадратом, если символы в каждой строке и в каждом столбце оказываются различными. Знаком строки или столбца латинского квадрата Р называется знак перестановки на множестве (О, 1,... „и — Ц, отвечающей данной строке или данному столбцу. Произведение всех 2п знаков строк и столбцов называется знаком е!Ь) квадрата Р. По определению Л четный, если е(Ь) = +1.
и нечетный., если е(Л) = — 1. При нечетном и число четных и нечетных латинских квадратов порядка п одинаково, но уже при и = 2, 4, 6 зто не так. Гипотеза 2 (А!оп-Таге!, 1986). Пусть и - четное натуральное число. Тоеда 2 е(Ц ~ О, где сумма берется по всем латинским квадратам Ь порядка и. Совсем недавно было доказано !Ргееко А.А. // Ле!чзпсев !и Масй. 1997.
— № 128. - Р. 20. 35), что если и = р -~- 1, где р .. нечетное простое число, то гипотеза 2 верна. Следовательно, верна при любом и = р+ 1 и гипотеза 1. Возможно ли обобщение этого результата на случай ее = р" + 17 ОТВЕТЫ И УКАЗАНИЯ К УПРАЖНЕНИЯМ Номер рорг отсылает к упражнению г из з ц главы р. 1.2.9. с((шМабз(лг) = 3. 4(шМа8„(!4) = 8.
1.2.10. Непосредственно проверяется, что оА = о(А)о = Аэ для .любой полумагической матрицы А. Кроме того, э" = и'" 'о для любого показателя т 3 1. Если теперь Маб~(!4) (соответственно Бй!а8"„) множество магических (соответственно полумагичоских) матриц с нулевым следом, то Маб (()) = Маб~(лх) Ж('„Б> БМа8„Я) = БМаб~(ф !О!45 (*) 1 (достаточно заметить, что сг(.4 — — сг(А)л) = О). и Далее, 4(ш Маб"„(!х) ) 4(ш БМа8~(ф — 2, поскольку пространство магических квадратов получается из полумагических квадратов добавлением ровно двух ограничений. Более точно, БМа8",(лх) = У!а8„(!4) О! !4Е Ю л)л). Действительно, предположим, что имеется соотношение А Ч- ЛЕ -Ь рР = О, где Л,р б !х, А б й!або(()). Умножив его на э', получим (Л -!- !лф = О, откуда Л + р = О.
Если же в соотношении перейти к следу, то получим пЛ -Ь рог Р = О. Результатом будет Л = д = О. Остается сопоставить равенства (*) и (**). 1.2.11. У'каз ание. Рассмотреть отображенио из прямой сумглы подпространств К в прямую сумму Й вЂ” 1 экземпляров пространства К, а именно (чл,...,чл) л вЂ Л (чл — чз,чл — чз,...,чЛ вЂ” 1 — чЛ). Пересечение всех К есть ядро этого отображения, имеющее размерность не менее,чем 4)ш Гл + ...-!- 4(ш Рл. — (Й вЂ” 1)п. 1.4.3. -1/2 < Л < 1, р < -2.
1 4 4. зл = хлул зхзрз+хзуз, зз = хлрз тхзрл ! хзрз, хлрз~ хзуз з харь 2.1.3. Очевидно. 2 2 7. Пусть с(!ш !шА' = 1+), причем !шА' = (А' лем...,А' ел; А' еллл,..., А' елзл), где (А' 'ел,..., А' 'ел = !шА' ' П КегА.). Таким образом., К = (ею .., ел; еллл..., ельб еллллм..., е„), (елз ллм...,е„) = КегА' -1 (ел,..., ел; ел лллл,..., е„) = Кег А', 345 Оигввты и указания к грирожненияи и мы имеем с(ппКегА' ~ = и — ь — 1., гйгшКегА' = и — К г(гггг(1гпА' ' й КегА) = 1 = (и — 1) — (и — 1 — 1). 2.2.8. По ус ювию А = С 'ВС, где С б М„(С). Нужно доказать, что среди решений уравнения ХА = ВХ наряду с Х = С найдется и невы- рожденная вещественная матрица Р. Решения над С нашего уравнения составляют комплексное векторное пространство Иг с базисом Сп..., С Представив С в виде С = С + гН с С, Н е М (Е), мы убеждаемся в том, что С,А = ВС, и Н,А = ВН„т.е.
пространство И' допускает вешественный базис (Рг,..., Р ) (некоторую выборку из Сп..., С: Нг,... ...,Н,). Пусть 1(И,...,Г ) = с(ег(ггРг + ... + Г Р,„) -- вещественный многочлен от т переменных. По условию он не равен тождественно нулю над С, а в таком случае он не равен тождественно нулю и над Ж.
Значит, наше матричное уравнение имеет невырожденное вещественное решение оР + оР' 2.2.9. а) Очевидно. б) В случае и = бппя й' = 1 утверждение справедливо. Действуем по индукции относительно и. Пусть И вЂ”. произвольная гиперплоскость в й, так что й' = (ййг,е)я. По предположению индукции существует вектор и Е И' такой, что дл, (А)И' = О.
Положим Ув(Г) =РА,, (Г), 1=0,1,... Согласно а) )г(г) делит д ~(г). Но таких делителей конечное число, по- этому 1,(Г) = уг(Г):= 1(Г) для некоторой пары индексов г, 15 г Р 1 (поле Й бесконечно). Итак, 1(А)(гч+ ге) = 0 = 1(А)(чч+уе). Отсюда 1(А)чч = 0 = 1(А)е, и вектор а = ш -й ге или а = вг + уе будет искомым. 2.2.10. а) Ясно, что ( о ) ~ й й + Г Э И г + ( Г й й ) ) й 5 Далее, Рг(И' й Г) = ййг -й Рг(Н) = й г.
Поэтому й' = И' -й Г. б) По усговию ч О й' .=э ъ = и -~- и, чч б Иг, п б Г. Значит, ч = = '(Рг (чч) -~- Р (чч)) -й )Рг (п) -й Рг(п)) = (Рг (чч) -~- Рг(п)) о; )Рг(и ) -й Рг(п)). Если ч В йй, то Рг(ьч)+Рг(п) = О. Но по условию Рг(С)йййгг = О, поэтому Рг(гч) = 0 = Рг(п) и, следовательно, йг = И'г + (Г й йг).
Применяя Рг к й' = И' -~- Н, получаем йхг = И'г -~- Рг(Ц, т.е. справедливы разложения (*). Наконец, чч и Иг й Н =ь Рг(чч) б Рг (И ) й Рг(Г) = И' й Р (С) = 0 =ь =э чч б Ий и гч б Ий й Г, т.е. И' й Г = ИЗ й йг. 2.2.11. Матрице А отвечаот линейный оператор А: 1' -о й' с гг А = О. Пусть при этом йг = (еп..., е„). Задача заключается в построении нового базиса (е'„ ....е' ), относительно которого оператору А отвечала бы матрица А' с нужными свойствами.
Если А = Лс, то ггА = иЛ и Л = О. Если А ф Лв, то облзательно найдутся два линейно независимых вектора вида е'„ег = Ае',. Это дает 346 Ответы и уназаная к упражнениям возможность поставить О в левом верхнем углу матрицы оператора А. Пусть уже построены линейно независимые векторы еы...,е~а, относительно которых а,1 —— ... — — а~ьв — — О.
Берем теперь такой вектор еьы ф Га, Гв = (еы...,еа), чтобы ее+а — — Аеа+, не содержался в (Ъю еь+,). Получаем еще один нуль на диагонали. Если это невозможно, то приходим к ситуации, когда х ф Ъ'ь =.~ Ах б Ъь. В случае Ах б 1'ь Чх ф Ъ'в любой базис пространства Г, продолжающий е'„..., е'„., будет искомым. Пусть теперь Ах = Л. х +..., где точками обозначен вектор из \ ы Если Л, = Л Чх ф Гы то снова ЪгА = (и — й)Л = О =э Л = О., и все доказано. Если же Ап = Лн, Ач = рч, Л ~ рв для некоторых векторов и, ч ф Ъ'ы то полагаем, например, еа+, — — н -Ъ т, е'„+з — — А(и + ч) = Лн -Ъ дч. Это дает возможность поставить дополнительный нуль на диагонали. Очевидная индукцня завершает рассуждение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
