Том 1 (1113042), страница 7
Текст из файла (страница 7)
1 . Можно ли операцию транспонирования матрицы общего вида свести к элементарным преобразованиям ее строк иГлава I. Матрицы36столбцов?3.9. Матрицей перестановки Р называется квадратная матрица, у которой в каждой строке и в каждом столбце ровно одинэлемент отличен от нуля и равен 1 . Найти все матрицы перестановок третьего порядка.3. 10. Доказать, что множество матриц перестановок одногопорядка замкнуто относительно операции умножения матриц.3. 1 1 . Доказать, что всякая матрица перестановки являетсяпроизведением матриц Pij элементарных преобразований первого типа.3.
12. Доказать, что матрицы перестановок ортогональны.3. 13. Доказать, что стохастическая матрица является ортогональной тогда и только тогда, когда она является матрицейперестановки.3. 14. Доказать, что линейная комбинация матриц перестановок с коэффициентами а 1 , а 2 , . . . , O: k , удовлетворяющими условиям aj > О, Vj-=k1 , k, I: O:jj= l=1 , является дважды стохастическойматрицей.3. 15. Доказать, что матрицы перестановок периодичны.3 . 16. Доказать , что если один из столбцов м атрицы А является линейной комбинацией других столбцов, то существуетненулевой вектор-столбец Ь такой, что А Ь = О . Сформулироватьстрочный вариант этой задачи.3 . 17. Доказать, что если одна из строк матрицы А являетсялинейной комбинацией других строк, то существует ненулеваяматрица В такая , что БА = О . Сформулировать столбцовыйвариант этой задачи.3.
18. Пусть L - одна из матриц элементарных преобразований . К акому преобразованию строк и столбцов м атрицы А приводит умножение Lт AL ?3. 19 . Доказать, что:а ) перестановка двух строк (столбцов ) матрицы может бытьосуществлена последовательным выполнением элементарныхпреобразований строк (соответственно столбцов) второго и третьего типов;б ) каждая матрица Pij элементарного преобразования первого типа может быть представлена в виде произведения матрицэлементарных преобразований второго и третьего типов.37§3. Элементарные преобразования матриц3.
20. Используя свойства матриц элементарных преобразо-ваний, найти произведение:1 2 3 41а)в)11111 2 31 1 21 1 1о о оо 1 2 ооо 1 о2 о о 112-11 21 11 11 1ооо1 о оо 1оо о 132114321г)1 21 1б)1 11 11 -113211243213о ооо о 1оо о о 11 о о211оо о оо оо о о -111112111321143213. 2 1 . При каком условии матрицы Pij и Pkl элементарныхпреобразований первого типа перестановочны?3.22. При каком условии матрицы Lij и L kl элементарныхпреобразований третьего типа с ненулевыми коэффициентами (3'и (3" соответственно перестановочны?3 .
23 . По аналогии с элементарными преобразованиями строки столбцов числовой матрицы можно ввести и элементарные преобразования блочной матрицы. Будем считать, что клетка Aijблочной м атрицы А = (Aij ) , i = 1 , р, j = 1 , s , имеет размерmi х nj . Элементарными преобразованиями блочной матрицы Абудем называть преобразования следующих типов:1 ) перестановка двух блочных строк (столбцов) матрицы;2) умножение всех клеток i-й строки слева на квадратнуюматрицу D порядка mi или умножение всех клеток j-го столбцасправа на квадратную матрицу D порядка nj ;3) прибавление к каждой клетке i-й строки соответствующейклетки другой k-й строки, умноженной слева на матрицу В размера mi х m k , или прибавление к каждой клетке j-го столбца соответствующей клетки другого l-го столбца, умноженной справана матрицу В размера n1 х nj .Доказать , что:а) любое элементарное преобразование строк (столбцов)блочной матрицы равносильно ее умножению слева ( соответственно справа) на некоторую квадратную матрицу;б) элементарные преобразования блочной матрицы первого итретьего типов равносильны суперпозиции обычных элементарных преобразований .Глава I I .
О пределители§ 4.ПерестановкиУпорядоченная совокупность чисел 0 1 , а 2 , . . . , О п , в которой1 ) G i { 1 , 2, " . , п} , i == 1 , п ; 2) Gi -:/= Gj при i -:j= j ,называется перестановкой из чисел 1 , 2, . . . , п.Перестановка 1 , 2, . . . , п называется натуралъной.Аналогично рассl\�атриваются перестановки из п произвольных символов: достаточно перенумеровать эти символы и иметь дело с их номерами1 , 2, .
. . , п .Преобразование перестановки, при котором два ее числа Gi и Gj с номерами i -:/= j меняются местами, называется транспоз1щиеu.Говорят, что два числа a .L и аj в перестановке а 1 , 0 2 , . . . , й п образуютинверсию {беспор.ядок}, если большее из них предшествует меньшему, т.е.если Gi > Gj при i < j, и порядок в противном случае, т. е. если G i <Ojпри i < j . Перестановка называется 'Четной, если общее число инверсийв ней четно, и не-ч,етной, если нечетно. Общее число инверсий в перестановкеа 1 , а 2 , . .
. , й п обозначается символами а ( а 1 , а 2 , . . . , а п ) или а ( а) .П р и м е р 4. 1 . Найдем общее число инверсий в перестановке 4, 3, 5, 1 , 2.Р е ш е н и е. Число 4 образует три инверсии с числами 3, 1 и 2; число 3- две инверсии с числами 1 и 2 ( пара ( 4,3) уже была рассмотрена) ; число5 - две инверсии с числами 1 и 2; пара ( 1 ,2) не образует инверсию.
Такимобразом, а ( 4, 3, 5, 1 , 2) = 3 + 2 + 2 7.Запишем количество инверсий, которые образует каждое число в перестановке с последующими, под этим числом:4, 3, 5, 1 , 2===} а ( 4, 3, 5, 1 , 2)3 + 2 + 2 + О = 7. •l l l l3 2 2 оЕ-===П р и м е р 4.2. Определим четность перестановки3, 6, 9, . . . , 3п, 2, 5, 8, . . . , 3п - 1 , 1 , 4, 7, . . . , 3п - 2.Р е ш е н и е. Данная перестановка из 3п чисел разбивается на три последовательные группы из п чисел.
Внутри каждой из групп инверсий нет. Приэтом3, 6, 9, . . . ' 3п, 2, 5, 8, . . . ' 3п - 1 , 1 , 4 , 7, " . , 3п - 2l112 4 61ll12п 1 2 3lпlllо о оа ( а) (2 + 4 + 6 + " . + 2п) + ( 1 + 2 + 3 + . " + п) 3п(п + 1 )/2.Четность 3п(п + 1 )/2 определ яется четностью числа п(п + 1 ) /2, котороечетно при п == 4k и п 4k + 2, k Е N, и нечетно при п = 4k + 1 и п 4k + 3 ,k N.
Таким образом, данная перестановка четна для тех п , которые приделении на 4 дают четные остатки, и нечетна в проти1.ном случае. •===}Е========39§4. Перестановкино п! .новки.Т е о р е м а 4. 1 . Число всевозмоЖН'ЫХ перестановок из п 'Чисел равТ е о р е м а 4. 2 . Каждая т'!Юнспози'Ци.я мен.лет 'Четностъ перестар.ядо'Ч-еНЪt так, 'Чтобы каждая после дующая оrп.1�u'Чаласъ от предЪtдущей наодну транспози'Цию, при'Чем на'Чинатъ это упор.ядо'Чение можно с любойперестановки.С л е д с т в и е 1 . При п > 2 'Число 'Четнъ�х перестановок 'JЮвно 'Ч.uс.луне'Четных.С л е д с т в и е 2. От каждой перестановки из п 'Чисел можно перейти к любой другой перестановке из этих {)fCe 'Чисел при помощи коне'Ч-ного'Числа транспози'Ций.Т е о р е м а 4.4. Ее.ли а 1 , а 2 , .
. . , йn перестановка из первъtх п натуралънъ�х 'Чисел с 'Ч-ис.лом инверсий s , то после преобразования ее в натуралъную перестановку индекснЪtе номе'[Ю 1 , 2, . . . , п образуют новую перестановку с тем {)fCe 'Числом инверсий s .Т е о р е м а 4. 3. Все п! перестановок из п 'Чисел могут 6'ытъ упо-Проиллюстрируем утверждение теоремы на примере перестановки4, 3, 5, 1 , 2.
В этой перестановке а 1 = 4, а 2 = 3, аз = 5, а4 = 1 , as = 2.После преобразования перестановки в натуральную получим перестановку1 , 2, 3, 4, 5, т.е. Q4 , as , а 2 , а 1 , а з , при этом перестановка из индексных номеров будет иметь вид 4, 5, 2, 1 , 3. Осталось проверить, что а (4, 3, 5, 1 , 2) = 7 иа (4, 5, 2, 1 , 3) = 7 .ЗАД АЧИ4. 1 . Выписать транспозиции, посредством которых от натуральной перестановки можно перейти:а ) к перестановке 3, 5, 4, 1 , 2 ;б ) к перестановке 5 , 4, 3, 2, 1 .4.2. Определить общее число инверсий в перестановках:а ) 3 , 1 , 4, 5, 2;6) 3 , 7, 4, 1, 5 , 2, 6;в ) 1 , 6 , 9 , 4, 2 , 5 , 3 , 8, 7;г ) 4, 7, 1 , 3, 2 , 6 , 5;д ) l , 3 , 5 , .
. . , 2n - 1 , 2 , 4, 6 , . . . , 2n;е ) 2 , 4, 6 , . . . , 2n, 1 , 3, 5, . . . , 2n - 1 ;ж ) k, k + 1 , . . . , п , 1 , 2 , . . . , k - 2 , k - 1 ;з ) k, k + 1 , . . . , n, k - 1 , k - 2 , . . . , 2, 1 .4.3. Найти i и k , при которых указанная перестановка является четной:а ) 2 , 4, 1 , i , 6, 9, k, 7, 5 ;б ) 8 , 1 , 6, i, 3 , 7, k, 4, 2.4.4. В перестановке а 1 , а2 , . , йп -1 , й п имеется р инверсий ,причем известно, что первый и последний ее элементы образуютс остальными элементами суммарно s инверсий. Сколько инверсий станет в этой перестановке, если поменять местами первыйи последний ее элементы?..Глава II.40О пределители4. 5 .
В перестановке a i , а 2 , . . . , йп - 1 , йп имеется р инверсий.Сколько инверсий будет в перестановке йп , йп - 1 , . . . , а2 , а 1 ?4.6. Какая перестановка из первых п натуральных чисел имеет наибольшее число инверсий? Чему оно равно?4.7. Сколько инверсий образует число 1 , стоящее на k-м местеперестановки?4.8. Сколько инверсий образует число п , стоящее на k-м месте в перестановке из первых п натуральных чисел?4.8.
1 . Сколько инверсий образует число k (1 < k < п ) , стоящее в перестановке из первых п натуральных чисел:б) на последнем месте?а) на первом месте;4.8.2. Указать количество всех перестановок п-го порядка, вкоторых первый и последний элементы образуют инверсию.4.9. В указанных перестановках определить общее число инверсий и выяснить, при каких п эти перестановки нечетные:. . . , 3п;а) 4, 7, . . .
, 3 п - 2, 2, 8, . . . , 3п - 1 , 3,б) 2 , 8, . . . , 3 п3,, 3п 4, 7, . . . , 3 п - 2 ;в ) 1 , . . . , 4п - 3 , 2 , . . . , 4п - 2 , 3, 7 , . . . , 4 п4 , 8, . . . , 4п ;г) 1 , . . . , 4п - 3 , 3 , 7, . . . , 4п - 1 , 2, 6, . . . , 4п - 2, 4, 8, . . . , 4п ;д) 4п , 4n -4, . .
. , 8, 4, 4п- 1 4 п - 5, . . . , 7, 3, 4п - 2 , 4п - 6, . . .2,1.4п - 3, 4п - 7 ,4. 10. Чему равна сумма числа инверсий и числа порядков влюбой перестановке первых п натуральных чисел?4. 1 1 . Для каких значений п четность числа инверсий и числапорядков во всех перестановках из первых п натуральных чиселодинакова и для каких противоположна?4. 1 2 . Доказать, что для любого k Е Z: О < k < n ( n - 1 ) / 2существует перестановка из первых п натуральных чисел , числоинверсий которой равно k.4. 1 2 . 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
