Document Open Access Logo

Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces

Authors Markus Blaeser, Gorav Jindal, Anurag Pandey

PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.33.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Markus Blaeser
Gorav Jindal
Anurag Pandey

Cite As Get BibTex

Markus Blaeser, Gorav Jindal, and Anurag Pandey. Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CCC.2017.33

Abstract

We consider the problem of commutative rank computation of a given matrix space. A matrix space is a (linear) subspace of the (linear) space of n x n matrices over a given field. The 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. An efficient deterministic computation of 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 computation of the commutative rank. This leads to a natural question of 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 B. More specifically, given a matrix space and a rational number e > 0, we give an algorithm, that runs in time O(n^(4 + 3/e)) and computes a matrix A in the given matrix space B such that the rank of A is at least (1-e) times the commutative rank of 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 of the set k depends on e.

Subject Classification

Keywords
  • Commutative Rank
  • Matrix Spaces
  • PTAS
  • Wong sequences

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jonathan F. Buss, Gudmund S. Frandsen, and Jeffrey O. Shallit. The computational complexity of some problems of linear algebra. Journal of Computer and System Sciences, 58(3):572-596, 1999. Google Scholar
  2. Harm Derksen and Visu Makam. On non-commutative rank and tensor rank. arXiv preprint arXiv:1606.06701, 2016. Google Scholar
  3. Jack Edmonds. Systems of distinct representatives and linear algebra. J. Res. Nat. Bur. Standards Sect. B, 71:241-245, 1967. Google Scholar
  4. David Eisenbud and Joe Harris. Vector spaces of matrices of low rank. Advances in Mathematics, 70(2):135-155, 1988. Google Scholar
  5. Marc Fortin and Christophe Reutenauer. Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank. Séminaire Lotharingien de Combinatoire, 52:B52f, 2004. URL: http://eudml.org/doc/125000.
  6. Harold N. Gabow and Matthias Stallmann. An augmenting path algorithm for linear matroid parity. Combinatorica, 6(2):123-150, 1986. Google Scholar
  7. Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. A deterministic polynomial time algorithm for non-commutative rational identity testing. CoRR, abs/1511.03730, 2015. URL: http://arxiv.org/abs/1511.03730.
  8. Leonid Gurvits. Classical complexity and quantum entanglement. Journal of Computer and System Sciences, 69(3):448-484, 2004. Google Scholar
  9. Gábor Ivanyos, Marek Karpinski, Youming Qiao, and Miklos Santha. Generalized Wong sequences and their applications to Edmonds' problems. Journal of Computer and System Sciences, 81(7):1373-1386, 2015. URL: http://arxiv.org/abs/1307.6429.
  10. Gábor Ivanyos, Marek Karpinski, and Nitin Saxena. Deterministic polynomial time algorithms for matrix completion problems. SIAM Journal on Computing, 39(8):3736-3751, 2010. Google Scholar
  11. Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam. Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristics. arXiv preprint arXiv:1512.03531, 2015. Google Scholar
  12. László Lovász. The matroid matching problem. Algebraic Methods in Graph Theory, 1:495-517, 1978. Google Scholar
  13. László Lovász. On determinants, matchings, and random algorithms. In FCT, volume 79 of LNCS, pages 565-574, 1979. Google Scholar
  14. László Lová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. Google Scholar
  15. László Lovász and Michael D. Plummer. Matching theory, volume 367. American Mathematical Soc., 2009. Google Scholar
  16. Meena Mahajan and V. Vinay. Determinant: Combinatorics, algorithms, and complexity. Chicago Journal of Theoretical Computer Science, 1997:5, 1997. Google Scholar
  17. James B. Orlin. A fast, simpler algorithm for the matroid parity problem. In International Conference on Integer Programming and Combinatorial Optimization, pages 240-258. Springer, 2008. Google Scholar
  18. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701-717, 1980. Google Scholar
  19. Seinosuke Toda. Counting problems computationally equivalent to computing the determinant. Technical Report CSIM 91-07, 1991. Google Scholar
  20. L. G. Valiant. Completeness classes in algebra. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC'79, pages 249-261, New York, NY, USA, 1979. ACM. URL: http://dx.doi.org/10.1145/800135.804419.
  21. V. Vinay. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Structure in Complexity Theory Conference, 1991, Proceedings of the Sixth Annual, pages 270-284. IEEE, 1991. Google Scholar
  22. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Edward W. Ng, editor, EUROSAM, volume 72 of Lecture Notes in Computer Science, pages 216-226. Springer, 1979. URL: http://dblp.uni-trier.de/db/conf/eurosam/eurosam1979.html#Zippel79, URL: http://dx.doi.org/10.1007/3-540-09519-5_73.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact