Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 283
Текст из файла (страница 283)
Докажите, что если г — ранг матрицы А размером и х и и у Е гс(А), то 1Р(А,у)~ = 2" '. Пусть 0 < т < и, и предположим, что мы разбиваем множество Я„на блоки последовательных чисел, где 1-й блок состоит из 2 чисел 12™,12 + 1,12 + 2,..., (1+ 1)2 — 1. Для любого подмножества Я С Я„определим 6(Я, т) как множество блоков Я„размером 2, содержащих некоторый элемент Я. В качестве примера при и = 3, т = 1 и Я = (1, 4, 5) множество В(Я, т) состоит нз блоюв 0 (поскольку 1 входит в нулевой блок) и 2 (посюльку и 4, и 5 находятся в блоке 2). в.
Пусть г — ранг нижней левой подматрицы А размером (и — т) х т, т.е. матрицы, полученной путем пересечения и — т нижних строк и ги левых столбцов А. Пусть Я вЂ” произвольный блок Я„размером 2 и пусть У = (у: Г2ВГ Приеаиеение Г. Матрицы у = Ах для некоторого х е Я). Докажите, что ~8(ог, т) ~ = 2' и что для каждого блока в В(У, т) на этот блок отображаются ровно 2 ' чисел из Я. Поскольку умножение нулевого вектора на любую матрицу дает нулевой вектор, множество перестановок 5„, определяемое умножением на 0-1-матрицы размером и х и с полным рангом над полем СЕ(2), не может включать все перестановки Я„.
Расширим класс перестановок, определяемых матрично-векторным умножением, путем включения аддитивного члена, так что х б Я„отображается на Ах+ с, где с — и-битовый вектор, а сложение выполняется над полем СГ(2). Например, когда мы получаем следующую перестановку ял,е.' ял,е(0) = 2, ял,,(1) = 1, ял,е(2) = О, ял е(3) = 3. Назовем перестановку, отображающую х б Я„на Ах+ с для некоторой 0-1-матрицы А размером и х п с полным рангом и некоторого п-битового вектора с, линейной перестановкой (1шеаг ретпшгайоп). а Воспользуйтесь комбинаторными методами, чтобы показать, что количество линейных перестановок Я„ гораздо меньше числа перестановок Я„.
д. Приведите пример значения и и перестановки Я„, которую нельзя получить никакой линейной перестановкой.(Указаниег подумайте, как для заданной перестановки умножение матрицы на вектор связано со столбцами матрицы.) Заключительные замечании Много информации о матрицах можно найти в учебниках по линейной алгебре. В особенности хочется отметить книги Стрэнга (3Ггапй) (321,322).
Лот яра лора !гвз [17] Атпе Апдюмоп, ТогЬеп Навегир, Бгейп %1ввоп, апд Ка)ееч Кюпап. Богйпв ш 1тпеаг тппе7 гоигла! о/Сотритег алд Яулгет Ясгелсял, 57:74-93, 1998. [18] Тош М. Ароюо!. Со!си(ш, чо)шпе 1. В1ювдеП РнЫтвйпв Сон!рану, весопд еййоп, 1967. [!9] КПшат Б. Агота, КоЬеп В. В!шпоГе, аш1 С. бтев Р1вхтоп. ТЬтеай всЬедиПп8 Гог шн!г(рговгвшпед пю10ргосеввогв, 1п Ртосеяйлвя о/ йе 10й Аллиа! АСМ Яуероюие ол РагаИе! А18ог!йел ала'Агсвпестигял, равев 119-129, !998. [20] Бюцееч Ахата. РгоЬаЬ110дс свесЛтлВ о/ргоо/л алй йе Лалдлеш о/аррптлттагтол ргоЫетл.
РЬО йев(в, Упйепдгу оГ Са)тщош(а, ВегЬе(еу, 1994. [2!] Бюиееч Агота. ТЬе арргохнпаЫПту оГ ЫР-Ьагд ргоЫюпв. !и Ргоссясвлвв о/йе 30й Аллин( АСМЯутроюие ол ТЛеогу о/Сотридлв, равев 337-348, 1998. [22] Бап)ееч Агота. Ро!упопйа! Пше арргохппайоп всЬешев Гот енс1Ыеап тгачеПп8 ва1еппап апй ойет Беошюпс ргоЫепп..!оигла1 о/йе АСМ, 45(5);753-782, 1998. [23] Бащееч Агота апд Сювгеп (юпд. Ншдпевв оГ арргохнпайопв. !п Вопт Б.
НосЬЬашп, ед(тот, Аррлп1тайол А18огггвтл/ог НР-Налг РгоЫетл, равев 399-446. Р%8 РиЫ(вЬЬщ Сатрапу, 1997. [24] МПйнн! 1. АгаПаЬ, едЬог. А(войт!еи алд ТЛеогу о/Сотршайол Налдвоов. СКС Ргевв, 1999. [25] б. Анв(еПо, Р. Сгезссы!, б. ОашЬов!, Ч. Каоп, А. МвтсЬен(-Брассенс!а„апд М. Рготаю'. Сокр(ехпу алд Арргохолайол: Сотйлагопа( Ордтиатгол РгоЫетл алд ТЛей Аррпи1таЬ! 1Лу Ргорягдел.
Брппвег, 1999. [26] БЬа1 Ачддап апд Апе! БЬаппг. Беат сагчшв Гог состоит-ватаге ппаве гевшищ. АСМ Тгаллагдолл ол Сгарвтсл, 26(3), апк!е 10, 2007. [27] Бша Валле апй А1ап Чап беЫег. Сотригег А!вопйтл; глондисдол то Г)югвл алд Ала!ухи. Адд)воп-ччев!еу, йид ейооп, 2000. [28] Епс ВвсЬ.
Рпчате сошптшисадоп, 1989. [29] Епс ВасЬ. ХшпЬег-тЬеогейс а18опйпп. 1п Аллин! Килек о/Соеритег Ястслсе, чо1шпе 4, раув 119 — 172. Аплиа1 Райепв, 1пс., 1990. [30] Епс ВасЬ апд !еГГгеу БЬаПп. А(воейт1с №твег ТЛеогу — !Мите Л Е/Ттсгелт А!вогиЛтт. ТЬе М!Т Ргевв, 1996. [3!] Оачы н. Вю1еу, кьщ 1.ее, впд ноит тт. Бппоп. Ов(пв Бтглввеп'в а)8опйш то ассе!статс йе во!одоп оГ 1шеаг вувтептв. ТЛе.!оюна! о/Яирегсотригглв, 4(4):357-371, 1990. [32] Бнтепдег Вазеапа, КюпшЬ Нагйагяп, апд Бапдеер Беп. (шрточед десгептепш) а!Бопйпю Гог шашшшищ !тапа(нче с1овнге апд аП-рюлв вЬогтевг райх.
гошпа1 о/А!Бог!!вел, 62(2):74-92, 2007. [33] К. Вауес Я)попе!по Ьшлху В-!геев: )уата впнсгше ютд пташтепапсе а)вопйптв. Асга 1л)огеадса, 1(4):290-306, 1972. [34] К. Вауег апд Е. М. МсСге(БЬт. Отвал)вийон аш1 пниптепапсе оГ 1юве огдегед шдехев. Асга 1л(опладса, 1(3):173-189, 1972. [35] Ртепе ВеансЬетош, бтПев Вгавяатд, С!анде Сгереац С!аш1е бонйег, апд Свг! Рошешпсе.
ТЬе Бепегагкп оГгютдош пшпЬегв йат ате ргоЬаЫу роше.,!оигла1 о/Стурто!ову, 1(1):53-64, 1988. [36] К)сЬюй ВеПпип, Оулат1с РлтвгаттглВ. Рппсетоп (Гп(чегв(гу Ргевв, 1957. [37] К(сЬюд ВеПптап. Оп а гонйпв ргоЫепт. (виагтег!у о/Арр11ед Майятадся, ! 6(! ):87-90, 1958. [38] МкЬае! Веп-Ог. (.очгег ЬошиЬ Гог а!веЬгак сошрнгайоп !геев. 1п Рлксеавлвх о/ йе Ревел!в Алина( АСМ Яуероюие ол ТЬсоту о/Сотритглв, равев 80-86, 1983. 1284 77иверавура [39] М(сЬае) А. Вепйег, ЕпЕ О. Оепга!пе, аай Магйп РатасЬ-СоИоп.
СасЬе-оЫ!ч!ов В-пеев. !п РгосеейлВв о/тЛе 41зг Аллиа! Бутроз)ит ол Роитбттголз о/Сотригег Бе!елее, раВев 399-409, 2000. [40] Былие! %, Вепг тгй 1оЬп %. )оЬп. Р!пй!пВ йе вейап гег)шгев 2п соврапиопв. 1п РгосеейглВз о/йе Бечеитеелй Аллиа( АСМ Бутрозлил ол ТЛеогу о/Соглриплр, раВев 213-216, 1985. [41] 1оп 1.. Вепг!еу.
Вййлй Е//тстелт РгоВгатз. Ргепйсе НаП, 1982. [42] 1оп 1.. Вепйеу. РгоВгаттглВ РеагЬ. Аййвоп-%ев1еу, 1986. [43] 1оп 1.. Вепг!еу, ОогогЬеа НаЕеп, алй Галиев В. Бахе. А Вепепй веймм1 Гог во1йпВ йчЫе-впйсопг)нег геснпепсев. БГОАСТ Лтегчз, 12(3):36-44, 1980. [44] Оаше1 ВгепшосЕ апй Веи)апнп МсС1овЕу. Т!ВЬгеп!пВ випр)ех в!хеййпгеВег иеш нлй Вивиан!сей Ьошн!в, Оргилпайол Олйле, ййу 2008. [45] РагпсЕ ВП)вВв!еу. РгоЬаЬ)Игу алые Митина )оЬл %г!еу й Бопв, весопй еййоп, 1986. [46] бну Е. В!еПосЬ. Бсал РНтПгиез алй РагаПе! Уестог Мойе1з. РЬО йеюв, Оерапвепг оГ Е!ее!пса! ЕпВшееппВ апй Соврнгег Бс(енсе, М1Т, 1989. АчайаЫе ав М1Т ЕаЬогагогу Гот Сопгршег Бс!сисе ТесЬшса) Керогг М1ТЛ.СБ/ТК-463.
[47] биу Е. В)еПосЬ. РгоВгавпнпВ равПе) а18опйгпв. Солииилгсаполз о/йе АСМ, 39(3):85-97, 1996. [48] бну Е. В!еПосЬ, РЫП!р В. бгЬЬопв, апй Уовв! Манав. РгочаЫу еГПс!епг всЬейиПиВ Гог !влВнаВез нлй Гше-Вввей рагаПеПвв, 1п РгосеейлВз о/йе 7й Аилиа( АСМ Бувроюит ол РагаПе1 А18оййтз алй АкЬЬесгигез, раВев 1-12, 1995. [49) Манне! В)шп, КоЬеп %. Р)суй, ЧанВЬап Ргап, КопаЫ 1.. Кгчевг, апй КоЬегг Е. Тт!ап.
Типе ЬошмЬ Гог ве)есйоп..)оигла1 о/Сотритег алй Бузгет Бстелсез, 7(4):448-461, 1973. [50] КоЬегг О. В!шпоГе, СЬпвгорЬег Р, )оегВ, Вгай1еу С. Кншгпан!, СЬаг!ев Е. Ее!вешал, КеиЬ Н. КапйаП, апй УнП ЕЬон. С!Пс Ап е(Пс!епг вн)г!Пиеайей пшйпе вуигев..тоигла1 о/Рата!1е1 алй Оиггйитей Сотриттй, 37(1)55-69, 1996. [51] КоЬегг О. В!шпоГе апй СЬаг1ев Е. 1.е!вегвоп. БсЬеййпВ пш16йвайей соврнгайоов Ьу ччогЕ втеа!ш8..1оигла! о1 йе АСМ, 46(5):720-748, 1999. [52) Ве1а ВоПоЬЬв.
Яалйов ОгарЪ. Асайепис Ргевв, 1985. [53) бгПев Втыватй апй Ран) Вгайеу. Рилйателгай о/А18оййлисз, Ргепгке НаП, 1996. [54] КзсЬатй Р. Втсп!. ТЬе рагаПе) еча)набоп оГ Бенета) апйнпебс ехргевиопв. зоигиа1 о/йе АСМ, 21(2); 201-206, 1974. [55] К!сЬап1 Р. Втсп!. Ап лпргочей Моите Сга)о Гасгопхайоп а18опйгп. БГТ, 20(2):176-184, 1980. [56) 1. Р. ВнЫег, Н. %.
Сенина, )г., апй Саг) Роветапсе. Расгопп8 !пгеВегв ийгЬ йе пшпЬег Пей в(ече. 1п А. К. 1.епвгга апй Н. %. 1.спина, Гг., ей!гот, ТЛе Вече(артели и/йе Ьгитбег Рте!й Бтече, чо1шпе 1554 оГ бес!иге Ьтотез!л МатЬетайсз, раВев 50-94. БрппВег, 1993. [57] 1. Еантеисе Саггег апй МагЕ Ы. %еВгпап. Оп!чета! с!аваев оГ ЬавЬ бгпсг!опи..Уоигиа1 о1' Сотритег ат( Бузтет Бстелсез, 18(2):143 — 154, 1979. [58] ВтЪага СЬарвап, баЬпе!е )ош, апй Кши) чап йег Раи. (7з!лВ ОрелМР: РогтаЫе БЬагп( Метогу Рата!!е! РгоВгатттлВ.
ТЬе М1Т Ргеив, 2007. [59] Вевтй СЬааеПе. А пишпюв врали(пВ ггее в!ВопгЬгп нйй |пчегве-АсЕеппапп гуре согпр1ехЬу. .1оигиа1 о/гЛе АСМ, 47(б):1028-1047, 2000. [60) ГоверЬ СЬепуап апй ТогЬеп НаВетир. А гапйов!хей вюпвшп-Почч а)Вопйап. БГАМ зоигиа1 ол Соврит1лВ, 24(2):203 — 226, 1995. Литер ур 1285 [61] 1оверЬ СЬепуап апд Б. ЬС. МаЬевЬюап'. Апа!уйв оГ ргейонс ривЬ а18опбипз Гог пшхппшн пепчог1с Нош Б1АМ/оигпа! ол Сотринли, 18(6):1057-1086, 1989. [62] Вонь Ч. СЬег1сызЬу апб Апбгесч Ч.
Оо)ПЬш8. Оп ппр1еспепс!п8 йе рнвЬ-ге!аЬе! псейоб Гог йе пих!шнш Посл ртоЫеш. А18ог0!тиса, 19(4):390-410, 1997. [63) Вопя Ч. СЬейаы1су, Апбгечт Ч. Оо!6Ьег8, апб Топшзх ПабЫс. БЬогсевс райв а)8опйшв: ТЬеогу апд ехреппсепш) еча!иабоп. Майетассса) Рго8гатт!н8, 73(2);129-174, 1996. [64) Вонь Ч.
СЬег1сыв!су, Апс)тсчт Ч. Оо!6Ьег8, апб Сгас8 БПчегвсе)п. ВнсЬесв, Ьеарв, !шп апб пюпосоне рпопсу Бнены. Б/АМ/оигна1 он СотриПл8, 28(4):1326 — 1346, 1999. [65] Н. СЬепсоП. А шеаьше оГ ыутнрсопс еГПссепсу йг сеять оГ а Ьуройевсв Ьавш) оп йе вшп оГ обьетчабопь. Алла(т о/ Майетапса! Бтасслисл, 23(4):493 — 507, 1952.
[бб) Кас 1.ш С!шп8. Е(стел!агу Ргобабс!Лу ТЛеосу ичсЛ Бсос/интас Рлзселлел. Брпп8ег, 1974. [67] Ч. СЬчйпй А Бгеебу Ьеипв6с Гог йе яес-сочепп8 ргоЫепс. Майетапся о/ Орегаиолл БелеагсЛ, 4(3):233-235, 1979. [68] Ч. СЬъаса1. Ейеаг Рто8гтнтсн8. %.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
