Елімінація та факторизація

1. Природною метою будь-якої матриці A є розкладання A на C, помножене на R, де C має r незалежних стовпців, а R має r незалежних рядків. Ці стовпці та рядки будуть основою для простору стовпців і простору рядків A. Ранг A буде r. Якщо ми будемо діяти уважно, наша система доведе, що ранг стовпця = рангу рядка для будь-якої матриці. І якщо ми будемо дуже обережні, ми зможемо створити ортогональні стовпці в C і ортогональні рядки в R — ці вектори покажуть нам сингулярний розклад A. Тут ми приймаємо лише фактичні стовпці A в C, тому ця система є більш елементарна і менш стабільна.
   Припустимо, що перші r незалежних стовпців A переходять у C. Тоді інші n − r стовпців A повинні бути комбінаціями CF цих незалежних стовпців C. Ця ключова матриця F є частиною фактора рядка R = I F P, з r незалежних рядків. Тоді ми відразу маємо A = CR:

          A=CR = C CF   P = Незалежні стовпці   Залежні стовпці           Переставні стовпці (1)

   Якщо r незалежних стовпців йдуть першими в A, матриця перестановки буде P = I. В іншому випадку нам потрібно P, щоб переставити n стовпців C і CF у правильне положення в A.
2. Факторизація A = CR підтверджена, але не обчислена. Як ми визначаємо перші r незалежних стовпців у A (що переходять у C) і залежності CF решти n−r стовпців? Це момент для дій із рядками над A. Дозволяються три дії, щоб привести A у її скорочену рядкову ступінчасту форму rref(A):
   (a) Відняти кратне одному рядку з іншого рядка (нижче або вище)
   (b) Поміняти місцями два рядки
   (c) Розділити рядок на його перший ненульовий запис
   Усі вчителі лінійної алгебри та певна частина студентів знають скорочену рядкову ступінчасту форму rref(A). Вона містить одиничну матрицю I r на r (тільки нулі можуть передувати цим одиницям). Положення I розкриває перші r незалежних стовпців A. А рівняння (1) вище розкриває значення F ! Воно показує нам, як n−r залежних стовпців CF A походить від незалежних стовпців у C. Решта m − r залежних рядків A повинні стати нульовими рядками, щоб підтримувати ранг r :

   Елімінація зменшує A до rref(A)  =   I F 0 0   P (2)

   Усі наші дії з рядками (a)(b)(c) є оборотні. (Це елімінація Гаусса-Джордана: дія з рядками над опорним рядком, а також нижче.) Але матриця, яка зводить A до цієї рядкової ступінчастої форми, менш важлива, ніж факторизація A = CR, яку вона розкриває в рівнянні (1).
3. Перш ніж застосувати A = CR для розв’язування Ax = 0, ми хочемо по стовпцях (зліва направо) побудувати rref(A) з A. Після елімінації k стовпців ця частина матриці знаходиться в її власній формі rref. Ми готові до елімінації на поточному стовпці k + 1. Цей новий стовпець має верхню частину u та нижню частину ℓ:

   Перші k + 1 стовпці           I_k F_k 0 0        P_k , а потім u ℓ                         (3)             

   Головне питання: цей новий стовпець k + 1 об'єднується з I_k  чи F_k?
   Якщо ℓ – це всі нулі, новий стовпець залежить від перших k стовпців. Потім u об’єднується з  F_k, щоб отримати  F_k+1 на наступному кроці до стовпця k + 2.
   Якщо ℓ не дорівнює нулю, новий стовпець не залежить від перших k стовпців. Виберіть будь-яке ненульове значення в ℓ (бажано найбільше) як опору. Перемістіть цей рядок A вгору в рядок k + 1. Потім використайте цей опорний рядок, щоб обнулити (шляхом стандартної елімінації) всю решту стовпця k + 1. (Очікується, що цей крок змінить стовпці після k + 1.) Стовпець k + 1 об'єднується з I_k, щоб отримати I_k+1 . Ми готові до колонки k + 2.
   Наприкінці елімінації ми маємо найбажаніший список номерів стовпців. Вони показують нам перші r незалежних стовпців A. Це стовпці C. Вони призвели до одиничної матриці I_{r на r}  у факторі рядка R A = CR.
4. Що досягається шляхом зменшення A до rref(A)? Розмір рядків не змінено! Тоді його ортогональне доповнення (нульовий простір A) не змінюється. Кожен стовпець CF показує нам, як залежний стовпець A є комбінацією незалежних стовпців C. По суті, стовпці F показують нам n − r розв’язків Ax = 0.
   Це найпростіше побачити на прикладі. Припустимо, що Ax = 0 було зменшено шляхом елімінації до I F x = 0:

   3x₁ + 7x₂ + 37x₃ + 57x= 0 зводиться до x₁ + 3x₃ + 5x₄ = 0
   x₁ + 2x₂ + 11x₃ + 17x₄  = 0
   x₂ + 4x₃ + 6x₄= 0

   Розв’язок з x₃  = 1 і x₄= 0 є x = (−3, −4, 1, 0). Розв’язок з  x₃  = 0 і x₄ = 1 є x = (−5, −6, 0, 1). Ці рішення є стовпцями X в AX = 0. (У цьому прикладі P = I.) n − r стовпців X є природною основою для нульового простору А:

   A = C I F     P множить X =  P^T −F I_n−r                     щоб отримати AX = 0. (4)
   З P P ^T = I для перестановки, кожен стовпець X розв’язує Ax = 0. Ці n − r розв’язків у X говорять нам те, що ми знаємо: кожен залежний стовпець A є комбінацією незалежних стовпців у C.

   Елімінація Гаусса-Джордана, що призводить до A = CR, є менш ефективною, ніж процес Гаусса, який безпосередньо розв’язує Ax = b. Останній зупиняється на трикутній системі Ux = c і вичислює x шляхом зворотної підстановки. Гаусс-Джордан має додатковий результат елімінації вгору. Якщо ми хочемо лише розв’язувати рівняння, буде швидше якщо ми зупинимося на трикутній факторизації.
5. Елімінація блоку. Дії в рядках, які зводять A до її рядкової ступінчастої форми, створюють один нуль за один раз. Ключовою частиною цієї рядкової ступінчатої форми є матриця ідентичності r на r. Якщо ми думаємо у більшому масштабі — замість одного рядка за один раз — вихідні дані I показують нам, що деяка матриця r на r була інвертована. Наслідування цьому прикладу приносить «матричне розуміння»елімінації.
   Припустимо, що матриця W у перших r рядках і стовпцях A є оборотною. Тоді елімінація отримує всі інструкції від W ! Один запис за раз або всі одразу  шляхом «усунення блоку» — W зміниться на I. Іншими словами, перші r рядків A дадуть I та F. Це ідентифікує F як  W⁻¹H. І останні m − r рядків стануть нульовими рядками.

   Блок елімінації A =  W H J K  зменшується до I F 0 0  = rref(A). (5)

   Це просто відображає факти лінійної алгебри: якщо A починається з r незалежних рядків, то решта m − r рядків є комбінаціями цих перших r рядків: J K = J W⁻¹ W H. Ці m − r рядки стають нульовими рядками в елімінації.
   Загалом, перший блок r на r може бути необоротним. Але елімінація знайде W. Ми можемо перемістити W у верхній лівий кут шляхом перестановки рядків і стовпців Pr і Pc. Тоді повне відображення блокової елімінації до скороченої рядкової ступінчастої форми є

   PrAPc =  W H J K →  I W⁻¹H 0 0  (6)

6. Це показує цікавий момент. Оскільки A має ранг r, ми знаємо, що воно має r незалежних рядків і r незалежних стовпців. Припустімо, що ці рядки знаходяться в підматриці B, а ці стовпці знаходяться в підматриці C. Чи завжди вірно, що r на r «перетин» W цих рядків із цими стовпцями буде оборотним? (Усі погоджуються, що десь в A є оборотна підматриця r на r. Питання полягає в тому, чи можна розраховувати на B ∩ C, щоб забезпечити таку підматрицю.) Чи W автоматично має повний ранг?
   Відповідь - так. Перетин r незалежних рядків A з r незалежними стовпцями справді створює матрицю W рангу r. W є оборотним.
   Доведення [2]: кожен стовпець A є комбінацією r стовпців матриці C. Кожен стовпець r на n матриці B є такою ж комбінацією r стовпців матриці W. Оскільки B має ранг r, його простір стовпців дорівнює всьому від  R^r .
   Тоді простір стовпців W є також  R^r і квадратна підматриця W має ранг r.

Гілберт Стренг

Факультет математики Массачусетського технологічного інституту

Кембридж, Массачусетс 02139

Список літератури

[1] Гілберт Стренг і Клів Молер, Елімінація LU та CR, Огляд SIAM, 64 (2022) 181–190.

[2] Гілберт Стренг і Деніел Друкер, Три матричні факторизації з етапів елімінації, аналіз і застосування, з’являться.

[3] Гілберт Стренг, Вступ до лінійної алгебри, 6-е видання (2023), Wellesley Cambridge Press.

Ключові слова: елімінація, базис стовпця, базис рядка, базис нульового простору, факторизація, A = CR, скорочена рядкова ступінчаста форма