ON BINARY SOLUTIONS TO A SYSTEM OF LINEAR EQUATIONS MODULO THREE

Issue number 2 from 17.09.2025

Рассмотрена задача поиска двоичного решения для системы линейных уравнений по модулю три. В случае когда количество уравнений ограничено сверху достаточно медленно растущей функцией от числа переменных, предложен новый алгоритм полиномиального времени для распознавания существования двоичного решения у такой системы. Алгоритм основан на замечании: если в матрице коэффициентов присутствуют ненулевые пропорциональные друг другу столбцы, то элиминация соответствующих переменных сохраняет свойство отсутствия двоичного решения системы. В частности, каждая система из двух уравнений от пяти переменных допускает элиминацию некоторых переменных, при которой сохраняется свойство отсутствия двоичного решения системы. На основе этих результатов мы предлагаем безошибочный эвристический алгоритм, который реализован на языке программирования Python. Для представления матриц и выполнения базовых операций используется библиотека NumPy. Входом служит расширенная матрица системы. С использованием этой реализации была рассчитана эмпирическая оценка времени работы. Экспериментально показано, что алгоритм эффективнее для разреженных систем уравнений. Очевидно, метод двоичного поиска позволяет найти двоичное решение системы, когда оно существует. Это открывает возможность применения, в частности, для решения задач математической биологии.

28 0

Effective Lower Bounds on the Matrix Rank and Their Applications

Issue number 5 from 17.09.2025

Предложена эффективно проверяемая нижняя граница для ранга разреженной вполне неразложимой квадратной матрицы, содержащей по два ненулевых элемента в каждой строке и каждом столбце. Ранг такой матрицы равен порядку или отличается на единицу. Построены базисы специального вида в пространствах квадратичных форм от фиксированного числа переменных. Существование таких базисов позволило нам обосновать эвристический алгоритм для решения задачи распознавания, проходит ли данное аффинное подпространство через вершину многомерного единичного куба. В худшем случае этот алгоритм может вернуть уведомление о неопределенности результата вычисления, но для общего подпространства достаточно малой размерности корректно отвергает вход. Алгоритм реализован на языке Python. В ходе тестирования получены оценки времени работы этой реализации алгоритма.

17 0

Lower bounds for the rank of a matrix with zeros and ones outside the leading diagonal

Issue number 2 from 17.09.2025

Найдена нижняя граница для ранга квадратной матрицы, у которой каждый элемент на главной диагонали отличен от нуля и от единицы, а вне главной диагонали каждый элемент равен либо нулю, либо единице. Ранг такой матрицы не меньше половины порядка матрицы. При дополнительном условии нижняя граница на единицу выше. Это условие означает отсутствие двоичного решения у некоторой вспомогательной системы линейных уравнений. Даны примеры, показывающие достижимость указанной нижней границы. Полученная нижняя граница для ранга позволяет свести задачу о поиске двоичного решения для системы линейных уравнений, в которой число линейно независимых уравнений достаточно велико, к аналогичной задаче от меньшего числа переменных. Найдены ограничения на существование большого множества решений, каждое из которых отличается от двоичного решения значением одной переменной. Отдельно обсуждается возможность для сертификации отсутствия двоичного решения у системы из большого числа линейных алгебраических уравнений. Также даны оценки времени работы для вычисления ранга матрицы в системе компьютерной алгебры SymPy. Показано, что ранг матрицы над полем вычетов по модулю простого числа вычисляется за меньшее время, чем обычно требуется для вычисления ранга матрицы того же порядка над полем рациональных чисел.

16 0