Top

Programming and Computer Software

Published in:

01-10-2023

Effective Lower Bounds on the Matrix Rank and Their Applications

Authors: O. A. Zverkov, A. V. Seliverstov

Published in: Programming and Computer Software | Issue 5/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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.

previous article Resonances and Periodic Motions of Atwood’s Machine with Two Oscillating Weights

next article Automated Verification of Multi-Party Agreements and Scheduling of Sending Messages in Distributed Ledger Systems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Gevorkyan, M.N., Korolkova, A.V., Kulyabov, D.S., and Sevast’yanov, L.A., A modular extension for a computer algebra system, Program. Comput. Software, 2020, vol. 46, no. 2, pp. 98–104.MathSciNetCrossRefMATH

Chistov, A.L., Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic, Lect. Notes Comput. Sci., 1985, vol. 199, pp. 63–69. https://doi.org/10.1007/BFb0028792MathSciNetCrossRefMATH

Mulmuley, K., A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Combinatorica, 1987, vol. 7, no. 1, pp. 101–104. https://doi.org/10.1007/BF02579205MathSciNetCrossRefMATH

Malaschonok, G. and Tchaikovsky, I., About big matrix inversion, Comput. Algebra, Abramov, S.A. and Sevastyanov, L.A., Eds., Moscow: MAKS Press, 2021, pp. 81–84. https://doi.org/10.29003/m2019.978-5-317-06623-9CrossRef

Malaschonok, G.I. and Sidko, A.A., Supercomputer environment for recursive matrix algorithms, Program. Comput. Software, 2022, vol. 48, pp. 90–101.MathSciNetCrossRefMATH

Cheung, H.Y., Kwok, T.C., and Lau, L.C., Fast matrix rank algorithms and applications, J. ACM, 2013, vol. 60, no. 5, pp. 1–25. https://doi.org/10.1145/2528404MathSciNetCrossRefMATH

Abdeljaoued, J. and Malaschonok, G.I., Efficient algorithms for computing the characteristic polynomial in a domain, J. Pure Appl. Algebra, 2001, vol. 156, pp. 127–145. https://doi.org/10.1016/S0022-4049(99)00158-9MathSciNetCrossRefMATH

Pereslavtseva, O.N., Calculation of the characteristic polynomial of a matrix, Discrete Math. Appl., 2011, vol. 21, no. 1, pp. 109–128.MathSciNetCrossRefMATH

Neiger, V. and Pernet, C., Deterministic computation of the characteristic polynomial in the time of matrix multiplication, J. Complexity, 2021, vol. 67, no. 101572, pp. 1–35. https://doi.org/10.1016/j.jco.2021.101572MathSciNetCrossRefMATH

10.

Chen, Z., On nonsingularity of circulant matrices, Linear Algebra Appl., 2021, vol. 612, pp. 162–176. https://doi.org/10.1016/j.laa.2020.12.010MathSciNetCrossRefMATH

11.

Alaev, P.E. and Selivanov, V.L., Fields of algebraic numbers computable in polynomial time. I, Algebra Logic, 2020, vol. 58, pp. 447–469.MathSciNetCrossRefMATH

12.

Alaev, P.E. and Selivanov, V.L., Fields of algebraic numbers computable in polynomial time. II, Algebra Logic, 2022, vol. 60, pp. 349–359.MathSciNetCrossRefMATH

13.

Harris, J. and Tu, L.W., On symmetric and skew-symmetric determinantal varieties, Topology, 1984, vol. 23, no. 1, pp. 71–84. https://doi.org/10.1016/0040-9383(84)90026-0MathSciNetCrossRefMATH

14.

Harris, J., Algebraic Geometry, New York: Springer, 1992. https://doi.org/10.1007/978-1-4757-2189-8CrossRefMATH

15.

Rubei, E., Affine subspaces of matrices with constant rank, Linear Algebra Appl., 2022, vol. 644, no. 1, pp. 259–269. https://doi.org/10.1016/j.laa.2022.03.002MathSciNetCrossRefMATH

16.

Seliverstov, A.V., Binary solutions to large systems of linear equations, Prikl. Diskretnaya Mat., 2021, no. 52, pp. 5–15. https://doi.org/10.17223/20710410/52/1

17.

Kuzyurin, N.N., Polynomial-average algorithm in integer linear programming, Sib. Zh. Issled. Oper., 1994, vol. 1, no. 3, pp. 38–48.MathSciNetMATH

18.

Kuzyurin, N.N., An integer linear programming algorithm polynomial in the average case, Discrete Analysis and Operations Research, Korshunov, A.D., Ed., Dordrecht: Springer, 1996, vol. 355, pp. 143–152. https://doi.org/10.1007/978-94-009-1606-7CrossRef

19.

Pan, Y. and Zhang, F., Solving low-density multiple subset sum problems with SVP oracle, J. Syst. Sci. Complexity, 2016, vol. 29, pp. 228–242. https://doi.org/10.1007/s11424-015-3324-9MathSciNetCrossRefMATH

20.

Rybalov, A.N., On the generic complexity of the subset sum problem for semigroups of integer matrices, Prikl. Diskretnaya Mat., 2020, no. 50, pp. 118–126. https://doi.org/10.17223/20710410/50/9

21.

Rybalov, A.N., On the generic complexity of the occurrence problem for semigroups of integer matrices, Prikl. Diskretnaya Mat., 2022, no. 55, pp. 95–101. https://doi.org/10.17223/20710410/55/7

22.

Seliverstov, A.V., Heuristic algorithms for recognition of some cubic hypersurfaces, Program. Comput. Software, 2021, vol. 47, no. 1, pp. 50–55.MathSciNetCrossRefMATH

23.

Minc, H., (0, 1)-matrices with minimal permanents, Isr. J. Math., 1973, vol. 15, pp. 27–30. https://doi.org/10.1007/BF02771770MathSciNetCrossRefMATH

24.

Seliverstov, A.V. and Lyubetsky, V.A., About forms equal to zero at each vertex of a cube, J. Commun. Technol. Electron., 2012, vol. 57, no. 8, pp. 892–895. https://doi.org/10.1134/S1064226912080049CrossRef

25.

Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 1980, vol. 27, no. 4, pp. 701–717. https://doi.org/10.1145/322217.322225MathSciNetCrossRefMATH

26.

Harris, C.R., Millman, K.J., van der Walt, S.J., et al., Array programming with NumPy, Nature, 2020, vol. 585, no. 7825, pp. 357–362. https://doi.org/10.1038/s41586-020-2649-2CrossRef

27.

Chen, Y.A. and Gao, X.S., Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems, J. Syst. Sci. Complexity, 2022, vol. 35, pp. 373–412. https://doi.org/10.1007/s11424-020-0028-6MathSciNetCrossRefMATH

Title: Effective Lower Bounds on the Matrix Rank and Their Applications
Authors: O. A. Zverkov
A. V. Seliverstov
Publication date: 01-10-2023
Publisher: Pleiades Publishing
Published in: Programming and Computer Software / Issue 5/2023
Print ISSN: 0361-7688
Electronic ISSN: 1608-3261
DOI: https://doi.org/10.1134/S0361768823020160

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 5/2023

Application of Computer Simulation to the Anonymization of Personal Data: Synthesis-Based Anonymization Model and Algorithm

Twenty Similarity Functions for Two Finite Sequences

Database Migration from ORACLE to PostgreSQL

Automated Verification of Multi-Party Agreements and Scheduling of Sending Messages in Distributed Ledger Systems

Automata-Based Software Engineering with Event-B

Metaclasses in UML and in Programming Languages

Premium Partner