Нижние границы для ранга матрицы с нулями и единицами вне главной диагонали

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

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

Об авторах

А. В. Селиверстов

Институт проблем передачи информации им. А.А. Харкевича РАН

Автор, ответственный за переписку.
Email: slvstv@iitp.ru
ORCID iD: 0000-0003-4746-6396
Россия, 127051 Москва, Большой Каретный пер., д. 19, стр. 1

О. А. Зверков

Институт проблем передачи информации им. А.А. Харкевича РАН

Email: zverkov@iitp.ru
ORCID iD: 0000-0002-8546-364X
Россия, 127051 Москва, Большой Каретный пер., д. 19, стр. 1

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

  1. Алаев П.Е. Конечно порожденные структуры, вычислимые за полиномиальное время // Сибирский математический журнал. 2022. Т. 63. № 5. С. 953–974.
  2. Леонтьев В.К., Гордеев Э.Н. О числе решений системы булевых уравнений // Автоматика и телемеханика. 2021. № 9. С. 150–168. doi: 10.31857/S0005231021090063
  3. Гордеев Э.Н., Леонтьев В.К. О числе решений диофантова уравнения и проблеме Фробениуса // Журнал Вычислительной Математики и Математической физики, 2022. Т. 62. № 9. С. 1447–1457.
  4. Pan Y., Zhang F. Solving low-density multiple subset sum problems with SVP oracle // Journal of Systems Science and Complexity. 2016. V. 29. P. 228–242. doi: 10.1007/s11424-015-3324-9
  5. Селиверстов А.В. Двоичные решения для больших систем линейных уравнений // Прикладная Дискретная Математика. 2021. № 52. С. 5–15. doi: 10.17223/20710410/52/1
  6. Селиверстов А.В. Обобщение задачи о сумме подмножеств и кубические формы // Журнал вычислительной математики и математической физики. 2023. Т. 63. № 1. С. 51–60.
  7. Akmal S., Chen L., Jin C., Raj M., Williams R. Improved Merlin–Arthur protocols for central problems in fine-grained complexity // Algorithmica. 2023. V. 85. P. 2395–2426. doi: 10.1007/s00453-023-01102-6
  8. Stoichev S.D., Gezek M. Unitals in projective planes of order 25 // Mathematics in Computer Science. 2023. V. 17. No. 5. P. 1–19. doi: 10.1007/s11786-023-00556-9
  9. Chistov A.L. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic // In: L. Budach (eds) Fundamentals of Computation Theory. FCT 1985. Lecture Notes in Computer Science, vol. 199. Springer, Berlin, Heidelberg, 1985. P. 63–69. doi: 10.1007/BFb0028792
  10. Mulmuley K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field // Combinatorica. 1987. V. 7. No. 1. P. 101–104. doi: 10.1007/BF02579205
  11. Cheung H.Y., Kwok T.C., Lau L.C. Fast matrix rank algorithms and applications // Journal of the ACM. 2013. V. 60. No. 5. Article No. 31. P. 1–25. doi: 10.1145/2528404
  12. Переславцева О.Н. О вычислении характеристического полинома матрицы // Дискретная математика. 2011. Т. 23. № 1. С. 28–45. doi: 10.4213/dm1128
  13. Neiger V., Pernet C. Deterministic computation of the characteristic polynomial in the time of matrix multiplication // Journal of Complexity. 2021. V. 67. No. 101572. P. 1–35. doi: 10.1016/j.jco.2021.101572
  14. Birmpilis S., Labahn G., Storjohann A. A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix // Journal of Symbolic Computation. 2023. V. 116. P. 146–182. doi: 10.1016/j.jsc.2022.09.002
  15. Abramov S.A., Petkovšek M., Ryabenko A.A. On ranks of matrices over noncommutative domains // Журнал вычислительной математики и математической физики. 2023. Т. 63. № 5. С. 760–762.
  16. Юран А. Многогранники Ньютона невырожденных квадратичных форм // Функциональный анализ и его приложения. 2022. Т. 56. № 2. С. 92–100. doi: 10.4213/faa3957
  17. Батхин А.Б., Брюно А.Д. Вещественная нормальная форма бинарного многочлена в критической точке второго порядка // Журнал вычислительной математики и математической физики. 2023. Т. 63. № 1. С. 3–15.
  18. Seliverstov A.V. On a simple lower bound for the matrix rank // Компьютерная алгебра: материалы 5-й международной конференции. Москва, 26–28 июня 2023 г. / отв. ред. С.А. Абрамов, А.Б. Батхин, Л.А. Севастьянов. М.: ИПМ им. М.В. Келдыша, 2023. С. 126–128.
  19. Байрамов Р.Э., Блинков Ю.А., Левичев И.В., Малых М.Д., Мележик В.С. Аналитическое исследование кубатурных формул на сфере в системах компьютерной алгебры // Журнал вычислительной математики и математической физики. 2023. Т. 63. № 1. С. 93–101.
  20. Meurer A., Smith C.P., Paprocki M., Čertik O., Kirpichev S.B., Rocklin M., Kumar A., Ivanov S., Moore J.K., Singh S., Rathnayake T., Vig S., Granger B.E., Muller R.P., Bonazzi F., Gupta H., Vats S., Johansson F., Pedregosa F., Curry M.J., Terrel A.R., Roučka Š., Saboo A., Fernando I., Kulal S., Cimrman R., Scopatz A. SymPy: symbolic computing in Python // PeerJ Computer Science. 2017. V. 3. No. e103. P. 1–27. doi: 10.7717/peerj-cs.103

© Российская академия наук, 2024

Данный сайт использует cookie-файлы

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, которые обеспечивают правильную работу сайта.

О куки-файлах