Правило блокового множення матриць. Операція транспонування матриці та її властивості

При побудові паралельних способівВиконання матричного множення поряд з розглядом матриць у вигляді наборів рядків і стовпців широко використовується блочне подання матриць. Розглянемо докладніше даний спосіборганізації обчислень.

7.4.1. Визначення підзавдань

Блокова схема розбиття матриць докладно викладена у першому розділі "Паралельні методи множення матриці на вектор". При такому способі поділу даних вихідні матриці А, В і результуюча матриця З представлені у вигляді наборів блоків. Для більш простого викладу наступного матеріалу будемо припускати далі, що всі матриці є квадратними розміру nxn кількість блоків по горизонталі і вертикалі однаково і дорівнює q (тобто розмір всіх блоків дорівнює kxk, k = n/q). При такому поданні даних операція матричного множення матрицьА і B у блочному вигляді може бути представлена ​​так:

Де кожен блок C ij матриці C визначається відповідно до виразу

При блочному розбиття даних визначення базових подзадач природним представляється взяти основою обчислення, виконувані над матричними блоками. З урахуванням сказаного визначимо базове підзавдання як процедуру обчислення всіх елементів одного з блоків матриці З.

Для виконання всіх необхідних обчислень базовим завданням повинні бути доступні відповідні набори рядків матриці A та стовпців матриці B . Розміщення всіх необхідних даних у кожному підзавданні неминуче призведе до дублювання та значного зростання обсягу використовуваної пам'яті. Як результат, обчислення повинні бути організовані таким чином, щоб у кожний момент часу підзадачі містили лише частину необхідних для проведення розрахунків даних, а доступ до решти даних забезпечувався за допомогою передачі даних між процесорами. Один із можливих підходів – алгоритм Фоксу ( Fox) – розглянуто далі у цьому підрозділі. Другий спосіб - алгоритм Кеннона ( Cannon) – наводиться у підрозділі 7.5.

7.4.2. Виділення інформаційних залежностей

Отже, за основу паралельних обчисленьдля матричного множення при блочному розділенні даних прийнятий підхід, при якому базові підзавдання відповідають за обчислення окремих блоків матриці C і при цьому в підзавданнях на кожній ітерації розрахунків розташовується лише по одному блоку вихідних матриць A і B. Для нумерації підзадач використовуватимемо індекси розміщуються в підзавдання блоків матриці C , тобто. підзавдання (i,j) відповідає за обчислення блоку C ij - тим самим, набір підзавдань утворює квадратну решітку, що відповідає структурі блочного подання матриці C .

Можливий спосіб організації обчислень за таких умов полягає у застосуванні широко відомого алгоритму Фоксу (Fox) - див, наприклад, [[34], [51]].

Відповідно до алгоритму Фокса в ході обчислень на кожній базовій підзадачі (i,j) розташовується чотири матричні блоки:

• блок C ij матриці C , що обчислюється підзавданням;
• блок A ij матриці A , що розміщується в підзадачі перед початком обчислень;
• блоки A" ij , B" ij матриць A і B , одержувані підзавданням під час виконання обчислень.

Виконання паралельного методу включає:

• етап ініціалізації, на якому кожній підзадачі (i,j) передаються блоки A ij , B ij і обнуляються блоки C ij всіх підзавданнях;
• етап обчислень, у межах якого кожної ітерації l, 0<=l

Для пояснення цих правил паралельного методу на рис. 7.6 наведено стан блоків у кожній підзадачі в ході виконання ітерацій етапу обчислень (для решітки підзадач 2x2).

7.4.3. Масштабування та розподіл підзадач по процесорах

У розглянутій схемі паралельних обчислень кількість блоків може змінюватись в залежності від вибору розміру блоків – ці розміри можуть бути підібрані таким чином, щоб загальна кількість базових завдань збігалася з числом процесорів p . Так, наприклад, у найпростішому випадку, коли число процесорів представимо у вигляді (тобто є повним квадратом), можна вибрати кількість блоків у матрицях по вертикалі та горизонталі рівним (тобто ). Такий спосіб визначення кількості блоків призводить до того, що об'єм обчислень у кожній підзадачі є однаковим і тим самим досягається повне балансування обчислювального навантаження між процесорами. У більш загальному випадку при довільній кількості процесорів та розмірах матриць балансування обчисленьможе відрізнятися від абсолютно однакової, проте при належному виборі параметрів може бути розподілена між процесорами рівномірно в рамках необхідної точності.

Для ефективного виконання алгоритму Фокса, в якому базові підзадачі представлені у вигляді квадратних ґрат і в ході обчислень виконуються операції передачі блоків по рядках і стовпцям решітки підзадач, найбільш адекватним рішенням є організація безлічі процесорів також у вигляді квадратних ґрат. У цьому випадку можна здійснити безпосереднє відображення набору підзадач на множину процесорів - базове підзавдання (i,j) слід розташовувати на процесорі P i,j. Необхідна структура мережі передачі може бути забезпечена фізично, якщо топологія обчислювальної системи має вигляд грати чи повного графа.

7.4.4. Аналіз ефективності

Визначимо обчислювальну складність цього алгоритму Фокса. Побудова оцінок відбуватиметься за умови виконання всіх раніше висунутих припущень: всі матриці є квадратними розміру nxn, кількість блоків по горизонталі та вертикалі є однаковим і рівним q (тобто розмір всіх блоків дорівнює kxk, k=n/q), процесори утворюють квадратну решітку та їх кількість дорівнює p=q 2 .

Як зазначалося, алгоритм Фокса вимагає свого виконання q ітерацій, під час яких кожен процесор перемножує свої поточні блоки матриць і В і додає результати множення до поточного значення блоку матриці C . З урахуванням висунутих припущень загальна кількість операцій, що виконуються при цьому, матиме порядок n 3 /p . Як результат, показники прискорення та ефективності алгоритму мають вигляд:

Загальний аналіз складності дає ідеальні показники ефективності паралельних обчислень. Уточнимо отримані співвідношення - для цього вкажемо більш точно кількість обчислювальних операцій алгоритму та врахуємо витрати на виконання операцій передачі данихміж процесорами.

Визначимо кількість обчислювальних операцій. Складність виконання скалярного множеннярядки блоку матриці A на стовпець блоку матриці можна оцінити як 2(n/q)-1 . Кількість рядків і стовпців у блоках дорівнює n/q і, як результат, трудомісткість операції блочного множення виявляється рівною (n2/p) (2n/q-1). Для складання блоків потрібно n2/p операцій. З урахуванням усіх перелічених виразів час виконання обчислювальних операцій алгоритму Фокса може бути оцінений так:

(Нагадаємо, що є час виконання однієї елементарної скалярної операції).

Оцінимо витрати на виконання операцій передачі данихміж процесорами. На кожній ітерації алгоритму перед множенням блоків один із процесорів рядка процесорних ґрат розсилає свій блок матриці A іншим процесорам свого рядка. Як зазначалося раніше, при топології мережі як гіперкуба чи повного графа виконання цієї операції може бути забезпечено за log 2 q кроків, а обсяг блоків, що передаються, дорівнює n 2 /p . Як результат, час виконання операції передачі блоків матриці A під час використання моделі Хокні може оцінюватися як

Де – латентність, – пропускна спроможність мережі передачі, а w є розмір елемента матриці в байтах. У разі коли топологія рядків процесорної решітки являє собою кільце, вираз для оцінки часу передачі блоків матриці A набуває вигляду:

Далі після множення матричних блоків процесори передають свої блоки матриці. Ці операції можуть бути виконані процесорами паралельно, і тим самим тривалість такої комунікаційної операції становить:

(нагадаємо, що параметр q визначає розмір процесорних ґрат і ).

9.Операція транспонування матриці та її властивості.

Визначення:Матриця А', що виходить з матриці А шляхом заміни рядків стовпцями називається транспонованою по відношенню до матриці А.

Справедливі такі правила транспонування матриць:

(αА+αВ)'=αA' + αB'

(AB)'=B'A'

Ідея доказу показати, що матриці (AB)' і B'A' мають однакову розмірність і у них рівні відповідні елементи.

Визначення:Якщо А – довільна квадратна матриця та A=A' (-A=A'), то матриця А називається симетричною
або кососиметричної

10. Визначення зворотної матриці. Довести, що у кожної оборотної матриці існує лише одне звернення.

Визначення:

А А -1= А -1 А=Е Звідси випливає, що для матриці А -1 зворотної буде (А -1) -1 =А

Теорема:Кожна оборотна матриця має єдине звернення.

Доведення:Припустимо, що у матриці А існує поряд з Х ще одна зворотна матриця У, тобто. АУ=Е. Тоді

(ХА)У=ЕУ=У ┐

Х(АУ)=ХЕ=Х ┘Отже Х=У. Тобто. у матриці А існує єдиний обіг. (ч.т.д.)

11. Визначення зворотної матриці. Довести що (АВС) -1 =С -1 У -1 А -1 .

Визначення:Квадратна матриця А називається оборотною, якщо існує така квадратна матриця Х, що АХ=ХА=Е. (1)

Кожна матриця Х, що задовольняє рівності (1), називається зворотною матрицею А або зверненням матриці А. Зворотна матриця до матриці А позначається А -1

А А -1= А -1 А=Е Звідси випливає, що для матриці А -1 зворотної буде (А -1) -1 =А (3)

Теорема:Якщо квадратні матриці А, В, З одного і того ж порядку оборотні, то їх добуток теж оборотний і (АВС) -1 = С -1 -1 А -1 .

Доведення:А(В(СС -1)В -1)А -1 =Е і С -1 (В -1 (А -1 А)В)С=Е (ч.т.д.)

Для будь-якого натурального m за визначенням А m =А*А*…*А – m-раз.

За визначенням А 0 =Е.

Визначення:Для кожної оборотної матриці А, А -2 = А -1 * А -1; А -3 = А -1 * А -1 * А -1 (4)

З (3) і (4) випливає, що для кожної оборотної матриці А і будь-яких цілих чисел р і q мають місце звичайні правила дії зі ступенями:

А р А q = А р + q

(АВ) р = А р В р якщо АВ = ВА

(А р) q = А р * q

12.Довести що в результаті транспонування оборотної матриці виходить знову оборотна матриця і ( A ’) -1 =( A -1 )’.

Теорема:В результаті транспонування оборотної матриці А виходить знову оборотна матриця і (A') -1 = (A -1)'.

Доведення:Застосуємо правила транспонування співвідношення АХ=ХА=Е:

(АХ)’=(ХА)’=Е’

А'Х'=Х'А'=Е

З визначення зворотної матриці випливає, що (A') -1 = Х'=(A -1)'(ч.т.д.)

13. Блокові матриці. Складання та множення блокових матриць. Теорема про визначника квазітрикутної матриці.

Прямокутну матрицю А можна вертикальними та горизонтальними лініями розбити на прямокутні клітини (блоки). Зокрема матриця може бути розбита лише горизонтальними або вертикальними лініями. (А α,β) s , t - Блокова матриця. Розглянемо дві матриці А і однакової розмірності і з однаковим розбиттям на блоки. Відповідні блоки А α,β і α,β мають однакову розмірність m α x n β , α=1..s, β=1..t. Тоді згідно з правилом складання матриць операція складання блокових матриць однакових розмірів з однаковим розбиттям на блоки, проводиться точно так, якби замість блоків стояли числові елементи.

Щоб поширити правило множення матриць на блокові матриці необхідно, щоб усі горизонтальні розміри блоків першої матриці збіглися з відповідними розмірами другого співмножника. Число стовпців блоку А α,β дорівнює числу рядків блоку β,с.

Β змінюється від 1 доt, змінюється від 1 до u. Таким чином можливе множення матриць А і формально також як якби замість блоків стояли числові елементи.

Визначення:Квадратна матриця у якої всі елементи розташовані під головною діагоналлю рівні 0 називається верхньою (нижньою) трикутною матрицею. Аналогічні поняття вводяться й у блокових матриць.

Визначення:Блокова матриця А називається верхньою (нижньою) квазітрикутною матрицею якщо всі діагональні блоки і сама матриця А квадратні матриці, і всі діагональні блоки розташовані під (над) діагональними блоками нульові матриці.

Визначення:Блокова матриця А називається квазідіагональною, якщо всі діагональні блоки і сама матриця А квадратні матриці, а всі недіагональні блоки – нульові матриці.

Теорема:Визначник квазітрикутної матриці пов'язаний з визначником діагональних матриць наступним співвідношенням:

(♀) де П – твір.

Доведення:Розглянемо спочатку квазітрикутну матрицю
де А 12 = 0,
,
,

За визначенням

Т.к. А 12 =0 то з усіх творів можуть бути ≠0 тільки ті в яких індекси
. Внаслідок цього інші індекси можуть набувати значень тільки з множини
. У цих умовах кількість інверсій у перестановці
одно:

З огляду на це знаходимо що

звідси слідує що

Розглядаючи у загальному випадку квазітрикутну матрицю

Як матрицю
де

згідно (*) будемо мати
. Матриця
знову квазітрикутна. Зробивши над нею тугішу операцію, отримаємо
. Після (р-1) таких кроків прийдемо до (♀).

Аналогічно доводиться рівність (♀) стосовно верхньої квазітрикутної матриці.(ч.т.д.)

Глава 1
МАТРИЦІ ТА ВИЗНАЧНИКИ

У цьому розділі вивчаються таблиці з чисел, звані матрицями і які у подальшому найважливішу роль. Тут вводяться основні операції над матрицями та детально вивчаються властивості так званих визначників, які є основною числовою характеристикою квадратних матриць.

§ 1. Матриці

1. Концепція матриці. Матрицею називається прямокутна таблиця з чисел, що містить кілька m рядків і кілька n стовпців. Числа тип називаються порядками матриці. Якщо m = n , матриця називається квадратною, а число m = n - її порядком. Надалі для запису матриці будуть застосовуватися або здвоєні рисочки, або круглі дужки:

Втім, для короткого позначення матриці часто використовуватиметься одна велика латинська літера (наприклад, А), або символ ║ a ij ║, а іноді і з роз'ясненням:
Числа a ij , що входять до складу даної матриці, називають її елементами. У записі a ij – перший індекс i означає номер рядка, а другий індекс j – номер стовпця.
У разі квадратної матриці

вводяться поняття головної та побічної діагоналей. Головною діагоналлюматриці (1.1) називається діагональ a 11 a 22 ...a nn , що йде з лівого верхнього кута цієї матриці в нижній правий її кут. Побічною діагоналлюТієї ж матриці називається діагональ a n1 a (n-1)2 ...a 1n , що йде з лівого нижнього кута в правий верхній кут.

2. Основні операції над матрицями та його властивості.Насамперед домовимося рахувати дві матриці рівнимиякщо ці матриці мають однакові порядки і всі їх відповідні елементи збігаються.
Перейдемо визначення основних операцій над матрицями.
а) Додавання матриць.Сумоюдвох матриць А = ║ a ij ║(i = 1, 2,..., m; j = 1, 2,..., n) і В = (i = 1, 2,..., m; j = 1, 2,... , n ) одних і тих же порядків m і n називається матриця С = (i = 1, 2,..., m ; j = 1, 2,... , n ) тих же порядків m і n елементи c ij - якій рівні

C ij = a ij + b ij (i = 1, 2,..., m; j = 1, 2,..., n) (1.2

Для позначення суми двох матриць використовується запис С = А + В. Операція складання суми матриць називається їх додаванням. Отже, за визначенням

З визначення суми матриць, а точніше, з формули (1.2), безпосередньо випливає, що операція складання матриць має ті ж властивості, що і операція складання речових чисел, а саме:
1) переміщувальною властивістю: А + В = В + А;
2) комбінаційною властивістю: (А + В) + С = А + (Б + С).
Ці властивості дозволяють не дбати про порядок проходження доданків матриць при складанні двох або більшого числа матриць.

б) Множення матриці на число. Творомматриці А = ║ a ij ║(i = 1, 2,..., m; j = 1, 2,..., n) на речовинне
число λ називається матриця С = (i = 1, 2,..., m; j = 1, 2,..., n), елементи c ij якої рівні

c ij = λ a ij (i = 1, 2,..., m; j = 1, 2,..., n) (1.3)

Для позначення добутку матриці на число використовується запис С = А або С = А . Операція складання твору матриці на число називається множенням матриці цього числа. Безпосередньо з формули (1.3) ясно, що множення матриці на число має такі властивості:
1) сполучною властивістю щодо числового множника: (λ µ )А = λ ( µ А);

2) розподільною властивістю щодо суми матриць: λ (А + В) = λ А + λ В;
3) розподільною властивістю щодо суми чисел: (λ + µ )А = λ А + µ A.
Зауваження. Різницею двох матриць А і однакових порядків тип природно назвати таку матрицю З тих же порядків m і n, яка в сумі з матрицею дає матрицю А. Для позначення різниці двох матриць використовується природний запис: С = А - В.
Дуже легко переконатися в тому, що різниця С двох матриць А і може бути отримана за правилом С = А + (-1)В.
в) Перемноження матриць. Творомматриці А = ║ a ij ║(i = 1, 2,..., m ; j = 1, 2,... , n ), що має порядки, відповідно рівні m і n , на матрицю В = (i = 1, 2,..., n ; , p ), що має порядки, відповідно рівні m і p і елементи c ij , що визначаються формулою

Для позначення твору матриці А на матрицю використовують запис С = А - В. Операція складання твору матриці А на матрицю В називається перемноженнямцих матриць. Зі сформульованого вище визначення випливає, що матрицю А можна помножити не на будь-яку матрицю: необхідно, щоб число стовпців матриці А дорівнювало числу рядків матриці В.
Зокрема, обидва твори АВ і В А можна визначити лише в тому випадку, коли число стовпців А збігається з числом рядків Б, а число рядків А збігається з числом стовпців В. При цьому обидві матриці А – В та В – А будуть квадратними Але порядки їх будуть, взагалі кажучи, різними. Для того, щоб обидва твори А В і В А не тільки були визначені, але й мали однаковий порядок, необхідно і достатньо, щоб обидві матриці А та В були квадратними матрицямиодного й того самого порядку.
Формула (1.4) є правилом складання елементів матриці С, що є твором матриці А на матрицю В. Це правило можна сформулювати і словесно: елемент c ij , що стоїть на перетиніi -й рядки таj- го стовпця матриці

С = А В дорівнює сумі попарних творів відповідних елементів i-го рядка матриці А і у го стовпця матриці В.
Як приклад застосування зазначеного правила наведемо формулу перемноження квадратних матриць другого порядку

З формули (1.4) випливають такі властивості добутку матриці А на матрицю:
1) сполучна властивість: (АВ)С = А(ВС);
2) розподільна щодо суми матриць властивість: (А + В) С = АС + ВС або А (В + С) = АВ + АС.
Розподільча властивість відразу випливає з формул (1.4) і (1.2), а для доказу поєднаної властивості досить помітити, що якщо А = ║ a ij ║(i = 1, 2,..., m; j = 1, 2,..., n), В = (i = 1, 2,..., n; j = 1, 2,... , p), С = (i = 1, 2, ..., m; j = 1, 2, ..., p), то
елемент d il матриці (АВ)С (1.4) дорівнює а елемент d il "матриці А(ВС) дорівнює але тоді рівність d il = d il "випливає з можливості зміни порядку підсумовування щодо j і до.
Питання про перестановочному властивості твори матриці А на матрицю має сенс ставити лише для квадратних матриць А і В однакового порядку (бо, як зазначалося вище, тільки для таких матриць А і В обидва твори АВ і В А визначені і є матрицями однакових порядків). Елементарні приклади показують, що добуток двох квадратних матриць однакового порядку не має, взагалі кажучи, перестановної властивості. Справді, якщо покласти

Тут ми вкажемо, однак, важливі окремі випадки, в яких справедлива перестановна властивість (Дві матриці, для твору яких справедлива перестановна властивість, прийнято називати комутуючими). Серед квадратних матриць виділимо клас так званих діагональнихматриць, кожна з яких елементи, розташовані поза головною діагоналі, рівні нулю. Кожна діагональна матриця порядку n має вигляд

де d 1 , d 2 ,..., d n - які завгодно числа. Легко бачити, якщо всі ці числа рівні між собою, тобто d 1 = d 2= ...= d n = d, то для будь-якої
квадратної матриці А порядку n справедлива рівність AD = DA. Справді, позначимо символами Cij і cf(j елементи, що стоять на перетині i-го рядка і j-ro стовпця матриць AD і DA відповідно. Тоді з рівності (1.4) і виду матриці D отримаємо, що c ij =a ij d j = a ij d, c ij "= d i a ij = da ij (1.6), тобто c ij = c ij".

Серед усіх діагональних матриць (1.5) з елементами, що збігаються d 1 = d 2= ...= d n особливо важливу роль відіграють дві матриці. Перша з цих матриць виходить за d = 1, називається одиничною матрицею п-го порядкуі позначається символом Е. Друга матриця виходить за d = 0, називається нульовою матрицею п-го порядкуі позначається символом О. Таким чином,

У силу доведеного вище АЕ = ЕА і АО = О А. Більше того, з формул (1.6) очевидно, що

AE = EA = E, АТ = ОА = О. (1.7)

Перша формул (1.7) характеризує особливу роль одиничної матриці Е, аналогічну тієї ролі, яку відіграє число 1 при перемноженні дійсних чисел. Що ж до особливої ​​ролі нульової матриці О, її виявляє як друга з формул (1.7), а й елементарно перевіряється рівність А + Про = Про + А = А (ця рівність є прямим наслідком формули (1.2)).
На закінчення зауважимо, що поняття нульової матриці можна вводити і для неквадратних матриць (нульовий називають будь-яку матрицю, всі елементи якої дорівнюють нулю).
3. Блокові матриці.Припустимо, що деяка матриця А = ║ a ij ║за допомогою горизонтальних і вертикальних прямих розбита на окремі прямокутні клітини, кожна з яких є матрицею менших розмірів і називається блоком вихідної матриці. У такому разі виникає можливість розгляду вихідної матриці А як деякої нової (так званої блокової) матриці А = ║ A αβ ║, елементами A αβякою служать зазначені блоки.
Зазначені елементи ми позначаємо великою латинською літерою, щоб підкреслити, що вони є, взагалі кажучи, матрицями, а не числами і (як звичайні числові елементи) забезпечуємо двома індексами, перший з яких вказує номер блокового рядка, а другий - номер блокового » стовпця. Наприклад, матрицю

можна розглядати як блочну матрицю , елементами якої є такі блоки:

Чудовим є той факт, що основні операції з блочними матрицями відбуваються за тими самими правилами, за якими вони здійснюються із звичайними числовими матрицями, лише ролі елементів виступають блоки.
Справді, елементарно перевіряється, якщо матриця А = ║ a ij ║є блоковою і має блокові елементи A αβ, то при тому ж розбиття на блоки матриці А = ║λ a ij ║відповідають блокові елементи A αβ(При цьому блокові елементи A αβсамі обчислюються за правилом множення матриці A αβна число λ).
Так само елементарно перевіряється, що якщо матриці A і мають однакові порядки і однаковим чином розбиті на блоки, то сумі матриць А і В відповідає блокова матриця з елементами A αβ = A αβ + B αβ(тут A αβі B αβ- Блокові елементи матриць А та В).
Нехай, нарешті, А і В - дві блокові матриці такі, що число стовпців кожного блоку A αβдорівнює кількості рядків блоку В β γ (так що
за будь-яких α, β та γ визначено добуток матриць A αβУ β γ ). Тоді добуток С = А являє собою матрицю з елементами С α γ , що визначаються формулою

Для доказу цієї формули достатньо розписати ліву та праву її частини в термінах звичайних (числових) елементів матриць A та В (надаємо це зробити читачеві).
Як приклад застосування блокових матриць зупинимося на понятті так званої прямої суми квадратних матриць. Прямою сумоюдвох квадратних матриць А і порядків m і n відповідно називається квадратна блочна матриця порядку m + n, рівна . Для позначення прямої суми матриць А та В використовується запис С = А

Часто доводиться користуватися матрицями, розбитими на прямокутні частини – «клітини» чи «блоки». Розгляду таких «блочних» матриць ми присвячуємо цей параграф.

1. Нехай дана прямокутна матриця

За допомогою горизонтальних та вертикальних ліній розсічемо матрицю на прямокутні блоки:

. (58)

Про матрицю (58) будемо говорити, що вона розбита на блоки розміром або що вона представлена ​​у вигляді блокової матриці. Замість (58) будемо скорочено писати:

У разі користуватимемося і таким записом:

Дії над блоковими матрицями виробляються за тими самими формальними правилами, як і у випадку, коли замість блоків маємо числові елементи. Нехай, наприклад, дано дві прямокутні матриці однакових розмірів і з однаковим розбиттям на блоки:

Легко побачити, що

. (62)

Докладніше зупинимося на множенні блокових матриць. Відомо (див. гл. I, стор. 17), що при множенні двох прямокутних матриць і довжина рядків у першому співмножнику повинна збігатися з висотою стовпців у другому співмножнику. Для можливості блокового множення цих матриць ми додатково вимагатимемо, щоб при розбитті на блоки всі горизонтальні розміри в першому співмножнику збігалися з відповідними вертикальними розмірами в другому:

, . (63)

Тоді легко перевірити, що

, де . (64)

Окремо відзначимо той окремий випадок, коли одним із співмножників є квазідіагональна матриця. Нехай - квазідіагональна матриця, тобто і при . У цьому випадку формула (64) нам дає:

При множенні блокової матриці зліва на квазідіагональну матрицю рядка блокової матриці збільшуються ліворуч на відповідні діагональні клітини квазідіагональної матриці.

Нехай тепер - квазідіагональна матриця, тобто і при . Тоді з (64) отримуємо:

При множенні блокової матриці праворуч на квазідіагональну всі стовпці блокової матриці множаться праворуч на відповідні діагональні клітини квазідіагональної матриці.

Зауважимо, що множення квадратних блокових матриць одного і того ж порядку завжди можна здійснити, коли співмножники розбиті на однакові квадратні схеми блоків і в кожному з співмножників на діагональних місцях стоять квадратні матриці.

Блокова матриця (58) називається верхньою (нижньою) квазітрикутною, якщо і все (відповідно все при ). Окремим випадком квазітрикутної матриці є квазідіагональна матриця.

З формули (64) легко побачити, що добуток двох верхніх (нижніх) квазітрикутних матриць є знову верхньою (нижньою) квазітрикутною матрицею; при цьому діагональні блоки добутку виходять шляхом перемноження відповідних діагональних блоків співмножників.

Дійсно, вважаючи (64) і

.

Аналогічно розуміється випадок нижніх квазітрикутних матриць.

Зазначимо правило обчислення визначника квазітрикутної матриці. Це правило можна отримати виходячи з розкладання Лапласа.

Якщо - квазітрикутна (зокрема, квазідіагональна) матриця з квадратними діагональними блоками, то визначник цієї матриці дорівнює добутку визначників діагональних блоків:

(67)

2. Нехай дана блокова матриця

(68)

Додамо до -й блочному рядку -ю рядок, попередньо помножену зліва на прямокутну матрицю розміром . Отримаємо блочну матрицю

. (69)

Введемо допоміжну квадратну матрицю, представлену у вигляді наступної квадратної схеми блоків:

. (70)

У діагональних клітинах матриці стоять поодинокі матриці, порядки яких рівні відповідно; всі недіагональні блоки матриці дорівнюють нулю, за винятком блоку , що стоїть на перетині -й блокового рядка з -м блоковим стовпцем.

Неважко бачити, що

Звідси, оскільки - неособлива матриця, для рангів матриць і маємо

В окремому випадку, коли – квадратна матриця, з (71) маємо:

Але визначник квазітрикутної матриці дорівнює 1:

Отже,

Таких же висновків можна дійти, якщо до якогось стовпця матриці (67) додавати інший стовпець, попередньо помножений праворуч на прямокутну матрицю належних розмірів.

Отримані результати можуть бути сформульовані у вигляді наступної теореми.

Теорема 3. Якщо в блоковій матриці до -й блоковому рядку (стовпцю) додати -й блоковий рядок (стовпець), попередньо помножену зліва (праворуч) на прямокутну матрицю відповідних розмірів, то при цьому перетворенні не зміняться ранг матриці , а також у випадку, коли - квадратна матриця, та визначник матриці .

3. Розглянемо тепер той окремий випадок, як у матриці діагональний блок - квадратна і до того ж неособлива матриця ().

До рядку матриці додамо перший рядок, помножений зліва на . Тоді отримаємо матрицю

, (76)

. (77)

Якщо квадратна неособлива матриця, то цей процес можна продовжити. Ми приходимо таким чином до узагальненого алгоритму Гауса.

Нехай – квадратна матриця. Тоді

. (78)

Формула (78) зводить обчислення визначника, що складається з блоків, до обчислення визначника меншого порядку, що складається з блоків.

Розглянемо визначник, розбитий на чотири блоки:

де - квадратні матриці.

Нехай. Тоді віднімемо з другого рядка перший, попередньо помножений зліва на . Отримаємо:

. (I)

Точно так само, якщо , то ми віднімемо з першого рядка другий, попередньо помножену зліва на . Отримаємо:

. (II)

В окремому випадку, коли всі чотири матриці , , , - квадратні (одного і того ж порядку ), з (I) і (II) слідують формули Шура, що зводять обчислення визначника -го порядку до обчислення визначника -го порядку:

(), (Iа)

(). (IIа)

Якщо матриці і перестановочні між собою, то (Iа) випливає:

(за умови ). (Iб)

Так само, якщо й перестановочні між собою, то

(за умови ). (IIб)

Формула (Iб) була отримана у припущенні , а формула (IIб) за умови . Проте, з міркувань безперервності, ці обмеження можна відкинути.

З формул (Iа) - (IIб) можна одержати ще шість формул, помінявши місцями у правих частинах і одночасно .

.

За формулою (Iб)

.

4. Встановимо формулу Фробеніуса для звернення блокової матриці. Нехай неособлива квадратна матриця () розбита на блоки

, (80)

і нехай також неособлива квадратна матриця (). Потрібно визначити.

Застосуємо до матриці узагальнений алгоритм Гаусса. З другого блокового рядка віднімемо перший, попередньо помножений зліва на . Ця операція рівносильна множенню матриці зліва на матрицю, де. Тому

. (81)

Введемо позначення

і зауважимо, що з рівності (81) випливає:

Тому, оскільки , і . Переходячи до зворотних матриць у рівності (81), отримаємо

. (83)

Зворотну матрицю для матриці шукатимемо у вигляді . Тоді з рівності

знаходимо, що . Таким чином,

. (84)

Але тоді з рівності (83) знаходимо

Виконуючи множення блокових матриць у правій частині рівності (85), приходимо до формули Фробеніуса

, (86)

. (87)

Формула Фробеніуса (86) зводить звернення матриці порядку до звернення двох матриць порядку і до операцій складання і множення матриць з розмірами , , і .

Якщо припустити, що (замість ) і поміняти ролями матриці і , можна отримати інший вид формули Фробеніуса:

, (88)

. (89)

приклад. Потрібно знайти елементи зворотної матриці для матриці

.

Вважаємо

Знаходимо послідовно

, ,

, ,

,

,

,

.

Тому за формулою (86) знаходимо:

.

5. З теореми 3 випливає так само

Теорема 4. Якщо прямокутна матриця представлена ​​у блочному вигляді

де - квадратна неособлива матриця порядку (), то ранг матриці дорівнює лише тому випадку, коли

Доведення. Віднімемо з другого блокового рядка матриці першу, попередньо помножену зліва на . Тоді отримаємо матрицю

. (92)

Матриці і згідно з теореми 3 мають один і той же ранг. Ранг ж матриці збігається з рангом матриці (тобто з) тоді і лише тоді, коли має місце, тобто (91). Теорему доведено.

Проілюструємо цей спосіб знаходження наступного прикладу.

приклад. Нехай

Потрібно обчислити.

Застосовуємо кілька видозмінений метод виключення до матриці

.

До всіх рядків додаємо другий рядок з деяким множником і домагаємося того, щоб усі елементи першого стовпця, крім другого елемента, дорівнювали нулю. Після цього до всіх рядків, крім другого, додаємо третій рядок з деяким множником і досягаємо того, щоб у другому стовпці всі елементи, крім другого та третього, дорівнювали нулю. Після цього до останніх трьох рядків додаємо перший рядок з деяким множником та отримуємо матрицю виду

.

,

,

.