×

A deterministic PTAS for the commutative rank of matrix spaces. (English) Zbl 1395.68333

Summary: We consider the problem of computing the commutative rank of a given matrix space \(\mathcal{B}\subseteq\mathbb{F}^{n\times n}\), that is, given a basis of \(\mathcal{B}\), find a matrix of maximum rank in \(\mathcal{B}\). This problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is \(n\), subsumes problems such as testing perfect matching in graphs and identity testing of algebraic branching programs. Finding an efficient deterministic algorithm for the commutative rank is a major open problem, although there is a simple and efficient randomized algorithm for it. Recently, there has been a series of results on computing the non-commutative rank of matrix spaces in deterministic polynomial time. Since the non-commutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic \({1}/{2}\)-approximation algorithm for the commutative rank. It is a natural question whether this approximation ratio can be improved. In this paper, we answer this question affirmatively.
We present a deterministic polynomial-time approximation scheme (PTAS) for computing the commutative rank of a given matrix space. More specifically, given a matrix space \(\mathcal{B}\subseteq\mathbb{F}^{n\times n}\) and a rational number \(\epsilon > 0\), we give an algorithm that runs in time \(O(n^{4+3/\epsilon})\) and computes a matrix \(A\in\mathcal{B}\) such that the rank of \(A\) is at least \((1-\epsilon)\) times the commutative rank of \(\mathcal{B}\). The algorithm is the natural greedy algorithm. It always takes the first set of \(k\) matrices that will increase the rank of the matrix constructed so far until it does not find any improvement, where the size \(k\) of the set depends on \(\epsilon\).

MSC:

68W25 Approximation algorithms
15A03 Vector spaces, linear dependence, rank, lineability
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] [1] M ARKUS B LÄSER, G ORAV J INDAL,AND A NURAG P ANDEY: Greedy strikes again: A determinis tic PTAS for commutative rank of matrix spaces. In Proc. 32nd Computational Complexity Conf. T HEORY OF C OMPUTING, Volume 14 (3), 2018, pp. 1-21 18 D ETERMINISTIC PTAS FOR THE C OMMUTATIVE R ANK (CCC’17), volume 79 of LIPIcs, pp. 33:1-33:16. DROPS, 2017. [doi:10.4230/LIPIcs.CCC.2017.33] 1 · Zbl 1440.68330
[2] [2] J ONATHAN F. B USS, G UDMUND S KOVBJERG F RANDSEN,AND J EFFREY O. S HALLIT: The computational complexity of some problems of linear algebra. J. Comput. System Sci., 58(3):572- 596, 1999. Preliminary version in STACS’97. [doi:10.1006/jcss.1998.1608]2 · Zbl 0941.68059
[3] [3] H ARM D ERKSEN AND V ISU M AKAM: On non-commutative rank and tensor rank. Linear and Multilinear Algebra, pp. 1-16, 2017. [doi:10.1080/03081087.2017.1337058,arXiv:1606.06701]5, 6
[4] [4] J ACK R. E DMONDS: Systems of distinct representatives and linear algebra. J. Res. Nat. Bur. Standards Sect. B, 71(4):241-245, 1967. [doi:10.6028/jres.071B.033]2 · Zbl 0178.03002
[5] [5] D AVID E ISENBUD AND J OE H ARRIS: Vector spaces of matrices of low rank. Advances in Mathematics, 70(2):135-155, 1988. [doi:10.1016/0001-8708(88)90054-0]3 · Zbl 0657.15013
[6] [6] S TEPHEN A. F ENNER, R OHIT G URJAR,AND T HOMAS T HIERAUF: Bipartite perfect matching is in quasi-NC. In Proc. 48th STOC, pp. 754-763. ACM Press, 2016. [doi:10.1145/2897518.2897564, arXiv:1601.06319]3 · Zbl 1373.68267
[7] [7] M ARC F ORTIN AND C HRISTOPHE R EUTENAUER: Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank. Séminaire Lotharingien de Combinatoire, 52:B52f, 2004. Available from EuDML.3,5 · Zbl 1069.15011
[8] [8] H AROLD N. G ABOW AND M ATTHIAS F. M. S TALLMANN: An augmenting path algorithm for linear matroid parity. Combinatorica, 6(2):123-150, 1986. Preliminary version in FOCS’84. [doi:10.1007/BF02579169]3 · Zbl 0612.05018
[9] [9] A NKIT G ARG, L EONID G URVITS, R AFAEL M ENDES DE O LIVEIRA,AND A VI W IGDERSON: A deterministic polynomial time algorithm for non-commutative rational identity testing. In Proc. 57th FOCS, pp. 109-117. IEEE Comp. Soc. Press, 2016. [doi:10.1109/FOCS.2016.95,arXiv:1511.03730] 3,5
[10] [10] R OHIT G URJAR AND T HOMAS T HIERAUF: Linear matroid intersection is in quasi-NC. In Proc. 49th STOC, pp. 821-830. ACM Press, 2017. [doi:10.1145/3055399.3055440]3 · Zbl 1370.68325
[11] [11] L EONID G URVITS: Classical complexity and quantum entanglement. J. Comput. System Sci., 69(3):448-484, 2004. Preliminary version in STOC’03. [doi:10.1016/j.jcss.2004.06.003]3 · Zbl 1093.81012
[12] [12] GÁBOR I VANYOS, M AREK K ARPINSKI, Y OUMING Q IAO,AND M IKLOS S ANTHA: Generalized Wong sequences and their applications to Edmonds’ problems. J. Comput. System Sci., 81(7):1373- 1386, 2015. Preliminary version in STACS’14. [doi:10.1016/j.jcss.2015.04.006,arXiv:1307.6429] 3,7,8,9 · Zbl 1320.68222
[13] [13] GÁBOR I VANYOS, M AREK K ARPINSKI,AND N ITIN S AXENA: Deterministic polynomial time algorithms for matrix completion problems. SIAM J. Comput., 39(8):3736-3751, 2010. [doi:10.1137/090781231,arXiv:0907.0774]3 T HEORY OF C OMPUTING, Volume 14 (3), 2018, pp. 1-21 19 M ARKUS B L ASER¨, G ORAV J INDAL,AND A NURAG P ANDEY · Zbl 1209.68269
[14] [14] GÁBOR I VANYOS, Y OUMING Q IAO,AND K. V ENKATA S UBRAHMANYAM: Constructive non commutative rank computation in deterministic polynomial time, 2015-2018. [arXiv:1512.03531] 3
[15] [15] LÁSZLÓL OVÁSZ: On determinants, matchings, and random algorithms. In Proc. 2nd Internat. Conf. Fundamentals of Computation Theory (FCT’79), pp. 565-574, 1979.2,3 · Zbl 0446.68036
[16] [16] LÁSZLÓL OVÁSZ: Singular spaces of matrices and their application in combinatorics. Boletim da Sociedade Brasileira de Matemática-Bulletin/Brazilian Mathematical Society, 20(1):87-99, 1989. [doi:10.1007/BF02585470]3 · Zbl 0757.05035
[17] [17] LÁSZLÓL OVÁSZ AND M ICHAEL D. P LUMMER: Matching Theory. Volume 367. AMS Chelsea Publ., 2009.3 · Zbl 1175.05002
[18] [18] M EENA M AHAJAN AND V. V INAY: Determinant: Combinatorics, algorithms, and complexity. Chicago J. Theor. Comput. Sci., (5), 1997. [doi:10.4086/cjtcs.1997.005]2 · Zbl 0924.68088
[19] [19] J AMES B. O RLIN: A fast, simpler algorithm for the matroid parity problem. In Proc. 13th Internat. Conf. on Integer Programming and Combinatorial Optimization (IPCO’08), volume 5035 of Lecture Notes in Comp. Sci., pp. 240-258. Springer, 2008. [doi:10.1007/978-3-540-68891-4_17]2 · Zbl 1143.90382
[20] [20] J ACOB T. S CHWARTZ: Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980. Preliminary version in EUROSAM’79. [doi:10.1145/322217.322225] 2,17 · Zbl 0452.68050
[21] [21] F. B RUCE S HEPHERD AND A DRIAN V ETTA: The demand-matching problem. Math. Oper. Res., 32(3):563-578, 2007. Preliminary version in IPCO’02. [doi:10.1287/moor.1070.0254]3 · Zbl 1341.90117
[22] [22] S EINOSUKE T ODA: Counting problems computationally equivalent to computing the determinant. Technical Report CSIM 91-07, 1991.2
[23] [23] L ESLIE G. V ALIANT: Completeness classes in algebra. In Proc. 11th STOC, pp. 249-261. ACM Press, 1979. [doi:10.1145/800135.804419]2
[24] [24] V. V INAY: Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proc. 6th IEEE Conf. on Structure in Complexity Theory (SCT’91), pp. 270-284. IEEE Comp. Soc. Press, 1991. [doi:10.1109/SCT.1991.160269]2
[25] [25] R ICHARD Z IPPEL: Probabilistic algorithms for sparse polynomials. In Proc. Symbolic and Algebraic Comput. (EUROSAM’79), volume 72 of Lecture Notes in Comp. Sci., pp. 216-226. Springer, 1979. [doi:10.1007/3 · Zbl 0418.68040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.