Kapranov rank vs. tropical rank
Authors:
K. H. Kim and F. W. Roush
Journal:
Proc. Amer. Math. Soc. 134 (2006), 24872494
MSC (2000):
Primary 15A99, 16Y60
Published electronically:
February 8, 2006
MathSciNet review:
2213725
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We show that determining Kapranov rank of tropical matrices is not only NPhard 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.
 1.
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 (86c:14001)
 2.
J. Canny, Some algebraic and geometric computations in PSPACE, Proc. 20th Symp. Theory of Computing, Chicago(1988),ACM Press.
 3.
E. Çela, R. Rudolf, and J. Woeginger, On the Barvinok rank of matrices, presentation at the 2nd Aussois Workshop on Combinatorial Optimization, February 1998.
 4.
M. Develin, F. Santos, and B. Sturmfels, On the rank of a tropical matrix, arxiv:math.CO/0312114.
 5.
Marshall Hall, Group Theory, Macmillan, New York, 1964.
 6.
Philip Hall, On the representatives of subsets, J. London Math. Soc. 10(1935),2630.
 7.
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 GianCarlo Rota. MR 655414
(84a:15001)
 8.
K.
H. Kim and F.
W. Roush, Problems equivalent to rational Diophantine
solvability, J. Algebra 124 (1989), no. 2,
493–505. MR 1011609
(90i:03048), http://dx.doi.org/10.1016/00218693(89)901452
 9.
K. H. Kim and F. W. Roush, Factorization of polynomials in one variable over the tropical semiring, arxiv:math.CO/0501167
 10.
D. Speyer and B. Sturmfels, The tropical Grassmannian, math.AG/0304218.
 11.
D. Speyer and B. Sturmfels, Tropical mathematics, arxiv:math.CO/0408099.
 1.
 R. Bieri and J.R.J. Groves, The geometry of the set of characters induced by valuations, J. reine und angewandte Mathematik 347(1984),168195. MR 0733052 (86c:14001)
 2.
 J. Canny, Some algebraic and geometric computations in PSPACE, Proc. 20th Symp. Theory of Computing, Chicago(1988),ACM Press.
 3.
 E. Çela, R. Rudolf, and J. Woeginger, On the Barvinok rank of matrices, presentation at the 2nd Aussois Workshop on Combinatorial Optimization, February 1998.
 4.
 M. Develin, F. Santos, and B. Sturmfels, On the rank of a tropical matrix, arxiv:math.CO/0312114.
 5.
 Marshall Hall, Group Theory, Macmillan, New York, 1964.
 6.
 Philip Hall, On the representatives of subsets, J. London Math. Soc. 10(1935),2630.
 7.
 K. H. Kim, Boolean Matrix Theory and Applications, Marcel Dekker, New York, 1982. MR 0655414 (84a:15001)
 8.
 K. H. Kim and F. W. Roush, Problems equivalent to rational Diophantine solvability, Proc. A.M.S 124, no. 2 (1989),493505. MR 1011609 (90i:03048)
 9.
 K. H. Kim and F. W. Roush, Factorization of polynomials in one variable over the tropical semiring, arxiv:math.CO/0501167
 10.
 D. Speyer and B. Sturmfels, The tropical Grassmannian, math.AG/0304218.
 11.
 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 361010271 – and – Fellow, Korean Academy of Science and Technology
Email:
khkim@alasu.edu
F. W. Roush
Affiliation:
Department of Mathematics, Alabama State University, Montgomery, Alabama 361010271
Email:
froush@alasu.edu
DOI:
http://dx.doi.org/10.1090/S0002993906084267
PII:
S 00029939(06)084267
Keywords:
Kapranov rank,
tropical rank
Received by editor(s):
March 15, 2005
Published electronically:
February 8, 2006
Communicated by:
Bernd Ulrich
Article copyright:
© Copyright 2006
American Mathematical Society
