Drew, Johnson and Loewy conjectured that for n ≥ 4, the CP-rank of every n × n completely positive real matrix is at most [n2/4]. In this paper, we prove this conjecture for n × n completely positive matrices over Boolean algebras (finite or infinite). In addition,we formulate various CP-rank inequalities of completely positive matrices over special semirings using semiring homomorphisms.
@article{bwmeta1.element.doi-10_1515_spma-2015-0007,
author = {Preeti Mohindru},
title = {Completely positive matrices over Boolean algebras and their CP-rank},
journal = {Special Matrices},
volume = {3},
year = {2015},
zbl = {1314.15021},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_1515_spma-2015-0007}
}
Preeti Mohindru. Completely positive matrices over Boolean algebras and their CP-rank. Special Matrices, Tome 3 (2015) . http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_1515_spma-2015-0007/
[1] P.J. Allen, A fundamental theorem of homomorphisms for semirings, Proc. Amer. Math. Soc. 21, (1969), 412-416. [Crossref] | Zbl 0197.02902
[2] P. Butkoviˇc, Max-algebra: the linear algebra of combinatorics?, Linear Algebra and Its Applications, 367, (2003), 313-335.
[3] L. B. Beasley, S. J. Kirkland and B. L. Shader, Rank Comparisons, Linear Algebra and Its Applications, 221, (1995), 171-188. | Zbl 0823.15003
[4] A. Berman and N. Shaked-Monderer, Remarks on completely positive matrices, Linear and Multilinear Algebra 44, (1998), 149-163.
[5] A. Berman and N. Shaked-Monderer, Completely Positive Matrices, World Scientific, River Edge, NJ, (2003).
[6] I. M. Bomze, W. Schachinger and R. Ullrich, From seven to eleven: Completely positive matrices with high cp-rank, Linear Algebra and Its Applications, 459, (2014) 208-221. | Zbl 1310.15059
[7] D. Cartwright and M. Chan, Three notions of tropical rank for symmetric matrices, Combinatorica. 32, (2012), 1, 55-84. [WoS] | Zbl 1299.14050
[8] J. H. Drew and C. R. Johnson, The no long odd cycle theorem for completely positivematrices, In: Random discrete structures, D. Aldous, R. Pemantle, Editors. IMA Vol. Math. Appl., vol. 76, Springer, New York, (1996), 103-115. | Zbl 0838.15011
[9] J. H. Drew, C. R. Johnson, and R. Loewy, Completely positive matrices associated with M-matrices, Linear and Multilinear Algebra 37, (1994), 303-310. | Zbl 0815.15019
[10] P. Erdos, A.W. Goodman, and L. Posa, The representation of a graph by set intersections, Canad. J.Math. (1966), 18, 106-112. | Zbl 0137.43202
[11] J.S. Golan, Semirings for the ring theorist, Rev. Roumaine Math. Pures Appl. 35, (1990), 6, 531-540. | Zbl 0732.16030
[12] Steven Givant and Paul Halmos, Introduction to Boolean Algebras, Undergraduate Texts in Mathematics, Springer, New York, 2009. | Zbl 1168.06001
[13] J. Hannah and T. L. Laffey, Nonnegative factorization of completely positivematrices, Linear Algebra and Its Applications 55, (1983), 1-9. [WoS] | Zbl 0519.15007
[14] Ki Hang Kim, Boolean matrix theory and applications, Marcel Dekker, New York, 1982. | Zbl 0495.15003
[15] M. Kaykobad, On Nonnegative Factorization of Matrices, Linear Algebra and Its Applications 96, (1987), 23-33. | Zbl 0626.15010
[16] S. J. Kirkland and N. J. Pullman, Boolean spectral theory, Linear Algebra and Its Applications, 175, (1992), 177-190. [WoS] | Zbl 0769.15007
[17] S. J. Kirkland and N. J. Pullman, Linear operators preserving invariants of nonbinary Booleanmatrices, Linear andMultilinear Algebra, 33, (1993), 295-300. | Zbl 0847.15006
[18] C. M. Lau and T. L.Markham, Square triangular factorizations of completely positivematrices, J. IndustrialMathematics Soc. 28, (1978), 15-24. | Zbl 0398.15011
[19] R. Loewy and B-S. Tam, CP rank of completely positivematrices of order five, Linear Algebra and Its Applications 363, (2003), 161-176. | Zbl 1019.15009
[20] T. L. Markham, Factorization of completely positive matrices, Proc. Cambridge Philos. Soc. 69, (1971), 53-58. [Crossref] | Zbl 0205.33004
[21] P. Mohindru, The Drew-Johnson-Loewy conjecture for matrices over max-min semirings, Linear and Multilinear Algebra, 63, no. 5, (2015), 914-926. [WoS] | Zbl 1317.15029
[22] M. Plus, Linear systems in (max, +) algebra, In Proceedings of the 29th Conference on Decision and Control, Honolulu, Dec. (1990).
[23] N. Shaked-Monderer, Minimal CP Rank, Electron. J. Linear Algebra 8, (2001), 140-157.
[24] N. Shaked-Monderer, I. M. Bomze, F. Jarre andW. Schachinger, On the CP-rank and minimal CP factorizations of a completely positive matrix, SIAM J. Matrix Anal. Appl. 34, No. 2, (2013), 355-368. [WoS] | Zbl 1314.15025
[25] H. S. Vandiver , Note on a simple type of algebra in which the cancellation law of addition does not hold, Bull. Amer. Math. Soc. 40, (1934), 914-920. [Crossref] | Zbl 0010.38804
[26] X. Zhan, Open problems in matrix theory, Proceedings of the 4th International Congress of Chinese Mathematicians, 1, (2008), 367-382.