Ці дії з рядками матриці такі:

• перестановка рядків;

• множення чи ділення всіх елементів одного рядка на відмінне від нуля число при вираженні однієї змінної через решту;

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

Вид матриці після виконання певних дій подано у тексті одразу після опису цих дій для випадку відсутності вільних змінних (коефіцієнти при яких в усіх рівняннях відмінні від нуля):

• нулем позначено нульовий елемент матриці або її прямокутну частину, заповнену нулями;

• одиницею позначено елемент матриці на діагоналі, що дорівнює одиниці;

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

Модифікацію запроваджено лише для полегшення сприйняття алгоритму читачами-учнями при першому знайомстві. Зміст наступного речення, виділеного курсивом, стане зрозумілим після ознайомлення з поданим алгоритмом: немодифікований алгоритм передбачає визначення змінних через усі наступні змінні (зведення матриці коефіцієнтів до верхньо-трикутного вигляду) з наступним вилученням змінних зі співвідношень для попередніх змінних (зведення основної матриці коефіцієнтів до діагонального вигляду). Таким чином, модифікація призводить до незначного скорочення коду і збільшення обсягу обчислень. Після реалізації модифікованого алгоритму радимо реалізувати і немодифікований, що передбачає меншу кількість обчислень.

Вилучення x₁
Виберемо рівняння (з найменшим порядковим номером), у якому коефіцієнт при x₁ відмінний від 0. Поміняємо його місцем з першим рівнянням системи.

Розглядаючи перше рівняння відносно x₁, знаходимо вираз для x₁ через відомі коефіцієнти та решту змінних: поділимо всі елементи першого рядка матриці коефіцієнтів на його перший елемент a₁₁.

Після такого перетворення перше рівняння матиме такий вигляд:

Підставимо отриману величину для x₁ у всі, крім першого, рівняння, яке залишаємо без змін. Інакше кажучи, при j = 2, 3, …, n та k = 1, 2, 3, …, (m + 1) величину елемента a_jk у рядку j і стовпчику k замінюємо на таку різницю:

Тобто до j-го рядка додаємо перший рядок, помножений на (– a_j1). Отримуємо еквівалентну систему, в усіх рівняннях якої, крім першого, відсутня змінна x₁.

Якщо коефіцієнти при x₁ в усіх рівняннях системи дорівнюють 0, то робимо висновок, що x₁ може набувати довільної величини.

Вилучення x₂
Вибираємо серед усіх рівнянь, починаючи з другого, (з усіх, якщо ми дійшли висновку, що x₁ може бути довільним), таке рівняння з найменшим порядковим номером, у якого коефіцієнт при x₂ відмінний від 0. Поміняємо його місцями з другим (з першим, якщо ми дійшли висновку, що x₁ може бути довільним) рівнянням системи

й виразимо з нього x₂ через відомі коефіцієнти та наступні змінні: поділимо всі елементи другого рядка матриці коефіцієнтів на його другий елемент a₂₂.

Підставимо отриману величину x₂ в усі рівняння системи, крім того, з якого визначили x₂ і яке залишимо без змін. Інакше кажучи, при j = 1, 3, 4, …, n та k = 2, 3, …, (m + 1) величину елемента a_jk у рядку j і стовпчику k замінюємо на таку різницю:

Тобто до j-го рядка додаємо другий рядок, помножений на (– a_j2). Отримуємо еквівалентну систему, в усіх рівняннях якої, крім другого, відсутня змінна x₂.

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

Вилучення x_r
Позначимо через l кількість таких змінних серед перших (r – 1), які можуть набувати довільних величин, r′ = r – l. Вибираємо з рівнянь системи, починаючи з r′-го, таке рівняння з найменшим порядковим номером, у якого коефіцієнт при x_r відмінний від 0. Поміняємо це рівняння місцями з r′-им.

Виразимо з цього рівняння x_r: поділимо всі елементи r′-го рядка матриці коефіцієнтів на його r-ий елемент a_r′r.

Підставимо отриману величину x_k в усі рівняння системи, крім того, з якого визначили x_k, і яке залишимо без змін.

Інакше кажучи, при j = 1, 2, 3, …, r′ – 2, r′ – 1, r′ + 1, r′ + 2, …, n та k = r, r + 1, …, (m + 1) величину елемента a_jk у рядку j і стовпчику k замінюємо на таку різницю:

Тобто до j-го рядка додаємо r′-ий рядок, помножений на (– a_jr).

Якщо коефіцієнти при x_r в усіх рівняннях системи дорівнюють нулю, то робимо висновок, що ця змінна може набувати довільної величини.

Примітка. Для немодифікованого алгоритму матриця на цьому кроці матиме такий вигляд.

У цьому випадку після «спуку вниз» (вичерпання рядків, що підлягають описаній зміні) потрібно почати «підйом вгору» — додаванням до рядка добутку числа на рядок знизу утворити нулі над одиницями.

Виконання алгоритму потрібно продовжувати доти, доки є змога виключати змінні.

Якщо на якомусь кроці за допомогою описаних еквівалентних перетворень системи отримаємо рівняння вигляду 0 = a_j (m + 1) (коефіцієнти при змінних дорівнюють нулю), то при a_j (m + 1) = 0 потрібно вилучити це рівняння (тотожність) з розгляду. Інакше потрібно припинити виконання алгоритму з висновком про несумісність системи рівнянь.

Якщо такої аварійної зупинки не буде, то алгоритм або зведе основну матрицю коефіцієнтів до одиничної (1 — на діагоналі, 0 — зовні діагоналі), або ні.

У першому випадку отримана система матиме такий вигляд:

Інакше кажучи, (m + 1)-ий стовпчик (вільних членів) містить відповідь.

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

9.2. Хімія (аналіз рядкових змінних + оптимізований перебір або лінійна алгебра)

1. Визначити кількість атомів кожного елемента у кожному субстраті й продукті.

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