- PII
- 10.31857/S0132347424020133-1
- DOI
- 10.31857/S0132347424020133
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume / Issue number 2
- Pages
- 100-107
- Abstract
- We have found a lower bound on the rank of a square matrix, where every entry in the leading diagonal is neither zero nor one, but every entry outside the leading diagonal is either zero or one. The rank of such a matrix is at least half the order of the matrix. Under an additional condition, the lower bound is one higher. This condition means that some auxiliary system of linear equations has no binary solution. Examples are given showing the achievability of the lower bound. This lower bound on the rank allows us to reduce the problem of finding a binary solution to a system of linear equations, where the number of linearly independent equations is sufficiently large, to a similar problem in a smaller number of variables. Restrictions on the existence of a large set of solutions are found, each of which differs from binary one by the value of one variable. In addition, we discuss the possibility of certifying the absence of a binary solution to a system of a large set of linear algebraic equations. Estimates of the running time for calculating the rank of a matrix with the SymPy computer algebra system are also given. It is shown that the matrix rank over the field of residues modulo a prime number is calculated in less time than is usually required to calculate the rank of a matrix of the same order over the field of rational numbers.
- Keywords
- ранг матрицы система линейных уравнений система компьютерной алгебры SymPy
- Date of publication
- 17.09.2025
- Year of publication
- 2025
- Number of purchasers
- 0
- Views
- 18
References
- 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
