Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society since 1950, Proceedings of the American Mathematical Society is devoted to shorter research articles in all areas of pure and applied mathematics.

ISSN 1088-6826 (online) ISSN 0002-9939 (print)

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Kapranov rank vs. tropical rank
HTML articles powered by AMS MathViewer

by K. H. Kim and F. W. Roush PDF
Proc. Amer. Math. Soc. 134 (2006), 2487-2494 Request permission

Abstract:

We show that determining Kapranov rank of tropical matrices is not only NP-hard over any infinite field, but if solving Diophantine equations over the rational numbers is undecidable, then determining Kapranov rank over the rational numbers is also undecidable. We prove that Kapranov rank of tropical matrices is not bounded in terms of tropical rank, answering a question of Develin, Santos, and Sturmfels.
References
  • Robert Bieri and J. R. J. Groves, The geometry of the set of characters induced by valuations, J. Reine Angew. Math. 347 (1984), 168–195. MR 733052
  • J. Canny, Some algebraic and geometric computations in PSPACE, Proc. 20th Symp. Theory of Computing, Chicago(1988),ACM Press.
  • E. Çela, R. Rudolf, and J. Woeginger, On the Barvinok rank of matrices, presentation at the 2nd Aussois Workshop on Combinatorial Optimization, February 1998.
  • M. Develin, F. Santos, and B. Sturmfels, On the rank of a tropical matrix, arxiv:math.CO/0312114.
  • Marshall Hall, Group Theory, Macmillan, New York, 1964.
  • Philip Hall, On the representatives of subsets, J. London Math. Soc. 10(1935),26-30.
  • Ki Hang Kim, Boolean matrix theory and applications, Monographs and Textbooks in Pure and Applied Mathematics, vol. 70, Marcel Dekker, Inc., New York, 1982. With a foreword by Gian-Carlo Rota. MR 655414
  • K. H. Kim and F. W. Roush, Problems equivalent to rational Diophantine solvability, J. Algebra 124 (1989), no. 2, 493–505. MR 1011609, DOI 10.1016/0021-8693(89)90145-2
  • K. H. Kim and F. W. Roush, Factorization of polynomials in one variable over the tropical semiring, arxiv:math.CO/0501167
  • D. Speyer and B. Sturmfels, The tropical Grassmannian, math.AG/0304218.
  • D. Speyer and B. Sturmfels, Tropical mathematics, arxiv:math.CO/0408099.
Similar Articles
  • Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 15A99, 16Y60
  • Retrieve articles in all journals with MSC (2000): 15A99, 16Y60
Additional Information
  • K. H. Kim
  • Affiliation: Department of Mathematics, Alabama State University, Montgomery, Alabama 36101-0271 – and – Fellow, Korean Academy of Science and Technology
  • Email: khkim@alasu.edu
  • F. W. Roush
  • Affiliation: Department of Mathematics, Alabama State University, Montgomery, Alabama 36101-0271
  • Email: froush@alasu.edu
  • Received by editor(s): March 15, 2005
  • Published electronically: February 8, 2006
  • Communicated by: Bernd Ulrich
  • © Copyright 2006 American Mathematical Society
  • Journal: Proc. Amer. Math. Soc. 134 (2006), 2487-2494
  • MSC (2000): Primary 15A99, 16Y60
  • DOI: https://doi.org/10.1090/S0002-9939-06-08426-7
  • MathSciNet review: 2213725