Effective Lower Bounds on the Matrix Rank and Their Applications

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅或者付费存取

详细

We propose an efficiently verifiable lower bound on the rank of a sparse fully indecomposable square matrix that contains two non-zero entries in each row and each column. The rank of this matrix is equal to its order or differs from it by one. Bases of a special type are constructed in the spaces of quadratic forms in a fixed number of variables. The existence of these bases allows us to substantiate a heuristic algorithm for recognizing whether a given affine subspace passes through a vertex of a multidimensional unit cube. In the worst case, the algorithm may output a computation denial warning; however, for the general subspace of sufficiently small dimension, it correctly rejects the input. The algorithm is implemented in Python. The running time of its implementation is estimated in the process of testing.

作者简介

O. Zverkov

Institute for Information Transmission Problems (Kharkevich Institute), Russian Academy of Sciences

编辑信件的主要联系方式.
Email: zverkov@iitp.ru
Russia, 127051, Moscow, Bol’shoi Karetnyi per. 19/1

A. Seliverstov

Institute for Information Transmission Problems (Kharkevich Institute), Russian Academy of Sciences

编辑信件的主要联系方式.
Email: slvstv@iitp.ru
Russia, 127051, Moscow, Bol’shoi Karetnyi per. 19/1

参考

  1. Геворкян М.Н., Королькова А.В., Кулябов Д.С., Севастьянов Л.А. Пример модульного расширения системы компьютерной алгебры // Программирование. 2020. № 2. С. 30–37. DOI: Перевод: Programming and Computer Software. 2020. V. 46. № 2. P. 98–104.https://doi.org/10.31857/S0132347420020065
  2. 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. https://doi.org/10.1007/BFb0028792
  3. Mulmuley K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field // Combinatorica. 1987. V. 7. № 1. P. 101–104. https://doi.org/10.1007/BF02579205
  4. Malaschonok G., Tchaikovsky I. About big matrix inversion // In: Abramov S.A., Sevastyanov L.A. (eds) Computer algebra. Moscow: MAKS Press, 2021. P. 81–84. https://doi.org/10.29003/m2019.978-5-317-06623-9
  5. Малашонок Г.И., Сидько А.А. Суперкомпьютерная среда выполнения для рекурсивных матричных алгоритмов // Программирование. 2022. № 2. С. 33–46. DOI: Перевод: Programming and Computer Software. 2022. V. 48. P. 90–101.https://doi.org/10.31857/S0132347422020091
  6. Cheung H.Y., Kwok T.C., Lau L.C. Fast matrix rank algorithms and applications // Journal of the ACM. 2013. V. 60. № 5. Article № 31. P. 1–25. https://doi.org/10.1145/2528404
  7. Abdeljaoued J., Malaschonok G.I. Efficient algorithms for computing the characteristic polynomial in a domain // Journal of Pure and Applied Algebra. 2001. V. 156. P. 127–145. https://doi.org/10.1016/S0022-4049(99)00158-9
  8. Переславцева О.Н. О вычислении характеристического полинома матрицы // Дискретная математика. 2011. Т. 23. № 1. С. 28–45. DOI: Перевод: Discrete Mathematics and Applications. 2011. V. 21. № 1. P. 109–128.https://doi.org/10.4213/dm1128
  9. Neiger V., Pernet C. Deterministic computation of the characteristic polynomial in the time of matrix multiplication // Journal of Complexity. 2021. V. 67. № 101572. P. 1–35. https://doi.org/10.1016/j.jco.2021.101572
  10. Chen Z. On nonsingularity of circulant matrices // Linear Algebra and its Applications. 2021. V. 612. P. 162–176. https://doi.org/10.1016/j.laa.2020.12.010
  11. Алаев П.Е., Селиванов В.Л. Поля алгебраических чисел, вычислимые за полиномиальное время. I // Алгебра и логика. 2019. Т. 58. № 6. С. 673–705. DOI: Перевод: Algebra Logiс. 2020. V. 58. P. 447–469.https://doi.org/10.33048/alglog.2019.58.601
  12. Алаев П.Е., Селиванов В.Л. Поля алгебраических чисел, вычислимые за полиномиальное время. II // Алгебра и логика. 2021. Т. 60. № 6. С. 533–548. DOI: Перевод: Algebra Logiс. 2022. V. 60. P. 349–359.https://doi.org/10.33048/alglog.2021.60.601
  13. Harris J., Tu L.W. On symmetric and skew-symmetric determinantal varieties // Topology. 1984. V. 23. № 1. P. 71–84. https://doi.org/10.1016/0040-9383(84)90026-0
  14. Harris J. Algebraic geometry. Springer-Verlag New York, 1992. 330 p. https://doi.org/10.1007/978-1-4757-2189-8
  15. Rubei E. Affine subspaces of matrices with constant rank // Linear Algebra and its Applications. 2022. V. 644. № 1. P. 259–269. https://doi.org/10.1016/j.laa.2022.03.002
  16. Селиверстов А.В. Двоичные решения для больших систем линейных уравнений // Прикладная дискретная математика. 2021. № 52. С. 5–15. https://doi.org/10.17223/20710410/52/1
  17. Кузюрин Н.Н. Полиномиальный в среднем алгоритм в целочисленном линейном программировании // Сибирский журнал исследования операций. 1994. Т. 1. № 3. С. 38–48.
  18. Kuzyurin N.N. An integer linear programming algorithm polynomial in the average case // In: Korshunov A.D. (eds.) Discrete Analysis and Operations Research. Mathematics and Its Applications. V. 355. P. 143–152. Springer, Dordrecht, 1996. https://doi.org/10.1007/978-94-009-1606-7
  19. 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. https://doi.org/10.1007/s11424-015-3324-9
  20. Рыбалов А.Н. О генерической сложности проблемы о сумме подмножеств для полугрупп целочисленных матриц // Прикладная дискретная математика. 2020. № 50. С. 118–126. https://doi.org/10.17223/20710410/50/9
  21. Рыбалов А.Н. О генерической сложности проблемы вхождения для полугрупп целочисленных матриц // Прикладная дискретная математика. 2022. № 55. С. 95–101. https://doi.org/10.17223/20710410/55/7
  22. Селиверстов А.В. Эвристические алгоритмы распознавания некоторых кубических гиперповерхностей // Программирование. 2021. № 1. С. 65–72. DOI: Перевод: Programming and Computer Software. 2021. V. 47. № 1. P. 50–55.https://doi.org/10.31857/S0132347421010106
  23. Minc H. -matrices with minimal permanents // Israel Journal of Mathematics. 1973. V. 15. P. 27–30. https://doi.org/10.1007/BF0277177010.1007/BF02771770
  24. Seliverstov A.V., Lyubetsky V.A. About forms equal to zero at each vertex of a cube // Journal of Communications Technology and Electronics. 2012. V. 57. № 8. P. 892–895. https://doi.org/10.1134/S1064226912080049
  25. Schwartz J.T. Fast probabilistic algorithms for verification of polynomial identities // Journal of the ACM. 1980. V. 27. № 4. P. 701–717. https://doi.org/10.1145/322217.322225
  26. Harris C.R., Millman K.J., van der Walt S.J. et al. Array programming with NumPy // Nature. 2020. V. 585. № 7825. P. 357–362. https://doi.org/10.1038/s41586-020-2649-2
  27. Chen Y.A., Gao X.S. Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems // Journal of Systems Science and Complexity. 2022. V. 35. P. 373–412. https://doi.org/10.1007/s11424-020-0028-6

补充文件

附件文件
动作
1. JATS XML
下载

版权所有 © О.А. Зверков, А.В. Селиверстов, 2023