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

Фісуненко, А. (2024). Formulas for determinant and characteristic polynomial of seven-like matrices. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics, 79(2), 72–79. https://doi.org/10.17721/1812-5409.2024/2.12

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