Effective Lower Bounds on the Matrix Rank and Their Applications
Pages 441 - 447
Abstract
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.
References
[1]
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 46 98-104
[2]
Chistov A.L. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic Lect. Notes Comput. Sci. 1985 199 63-69
[3]
Mulmuley K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field Combinatorica 1987 7 101-104
[4]
Malaschonok G. and Tchaikovsky I. About big matrix inversion, Comput. Algebra 2021 Moscow MAKS Press
[5]
Malaschonok G.I. and Sidko A.A. Supercomputer environment for recursive matrix algorithms Program. Comput. Software 2022 48 90-101
[6]
Cheung H.Y., Kwok T.C., and Lau L.C. Fast matrix rank algorithms and applications J. ACM 2013 60 1-25
[7]
Abdeljaoued J. and Malaschonok G.I. Efficient algorithms for computing the characteristic polynomial in a domain J. Pure Appl. Algebra 2001 156 127-145
[8]
Pereslavtseva O.N. Calculation of the characteristic polynomial of a matrix Discrete Math. Appl. 2011 21 109-128
[9]
Neiger V. and Pernet C. Deterministic computation of the characteristic polynomial in the time of matrix multiplication J. Complexity 2021 67 1-35
[10]
Chen Z. On nonsingularity of circulant matrices Linear Algebra Appl. 2021 612 162-176
[11]
Alaev P.E. and Selivanov V.L. Fields of algebraic numbers computable in polynomial time. I Algebra Logic 2020 58 447-469
[12]
Alaev P.E. and Selivanov V.L. Fields of algebraic numbers computable in polynomial time. II Algebra Logic 2022 60 349-359
[13]
Harris J. and Tu L.W. On symmetric and skew-symmetric determinantal varieties Topology 1984 23 71-84
[14]
Harris J. Algebraic Geometry 1992 New York Springer
[15]
Rubei E. Affine subspaces of matrices with constant rank Linear Algebra Appl. 2022 644 259-269
[16]
Seliverstov, A.V., Binary solutions to large systems of linear equations, Prikl. Diskretnaya Mat., 2021, no. 52, pp. 5–15.
[17]
Kuzyurin N.N. Polynomial-average algorithm in integer linear programming Sib. Zh. Issled. Oper. 1994 1 38-48
[18]
Kuzyurin N.N. An integer linear programming algorithm polynomial in the average case, Discrete Analysis and Operations Research 1996 Dordrecht Springer
[19]
Pan Y. and Zhang F. Solving low-density multiple subset sum problems with SVP oracle J. Syst. Sci. Complexity 2016 29 228-242
[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.
[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.
[22]
Seliverstov A.V. Heuristic algorithms for recognition of some cubic hypersurfaces Program. Comput. Software 2021 47 50-55
[23]
Minc H. (0, 1)-matrices with minimal permanents Isr. J. Math. 1973 15 27-30
[24]
Seliverstov A.V. and Lyubetsky V.A. About forms equal to zero at each vertex of a cube J. Commun. Technol. Electron. 2012 57 892-895
[25]
Schwartz J.T. Fast probabilistic algorithms for verification of polynomial identities J. ACM 1980 27 701-717
[26]
Harris C.R., Millman K.J., and van der Walt S.J. Array programming with NumPy Nature 2020 585 357-362
[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 35 373-412
Recommendations
Nonpositive eigenvalues of the adjacency matrix and lower bounds for Laplacian eigenvalues
Let N P O ( k ) be the smallest number n such that the adjacency matrix of any undirected graph with n vertices or more has at least k nonpositive eigenvalues. We show that N P O ( k ) is well-defined and prove that the values of N P O ( k ) for k = 1 , ...
Low-Rank Matrix Approximation Using the Lanczos Bidiagonalization Process with Applications
Low-rank approximation of large and/or sparse matrices is important in many applications, and the singular value decomposition (SVD) gives the best low-rank approximations with respect to unitarily-invariant norms. In this paper we show that good low-rank ...
Perturbation Bounds for the $QR$ Factorization of a Matrix
Let A be an $m \times n$ matrix of rank n. The $QR$ factorization of A decomposes A into the product of an $m \times n$ matrix Q with orthonormal columns and a nonsingular upper triangular matrix R. The decomposition is essentially unique, Q being ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© Pleiades Publishing, Ltd. 2023. ISSN 0361-7688, Programming and Computer Software, 2023, Vol. 49, No. 5, pp. 441–447. © Pleiades Publishing, Ltd., 2023. Russian Text © The Author(s), 2023, published in Programmirovanie, 2023, Vol. 49, No. 5.
Publisher
Plenum Press
United States
Publication History
Published: 01 October 2023
Accepted: 30 October 2022
Revision received: 27 July 2022
Received: 26 June 2022
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025