Completely positive matrices over Boolean algebras and their CP-rank

Preeti Mohindru

Special Matrices (2015)

  • Volume: 3, Issue: 1, page 69-81, electronic only
  • ISSN: 2300-7451

Abstract

top
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.

How to cite

top

Preeti Mohindru. "Completely positive matrices over Boolean algebras and their CP-rank." Special Matrices 3.1 (2015): 69-81, electronic only. <http://eudml.org/doc/271036>.

@article{PreetiMohindru2015,
abstract = {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.},
author = {Preeti Mohindru},
journal = {Special Matrices},
keywords = {Boolean matrices; matrices over semirings; completely positive matrices; diagonally dominant matrices; semiring homomorphisms},
language = {eng},
number = {1},
pages = {69-81, electronic only},
title = {Completely positive matrices over Boolean algebras and their CP-rank},
url = {http://eudml.org/doc/271036},
volume = {3},
year = {2015},
}

TY - JOUR
AU - Preeti Mohindru
TI - Completely positive matrices over Boolean algebras and their CP-rank
JO - Special Matrices
PY - 2015
VL - 3
IS - 1
SP - 69
EP - 81, electronic only
AB - 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.
LA - eng
KW - Boolean matrices; matrices over semirings; completely positive matrices; diagonally dominant matrices; semiring homomorphisms
UR - http://eudml.org/doc/271036
ER -

References

top
  1. [1] P.J. Allen, A fundamental theorem of homomorphisms for semirings, Proc. Amer. Math. Soc. 21, (1969), 412-416. [Crossref] Zbl0197.02902
  2. [2] P. Butkoviˇc, Max-algebra: the linear algebra of combinatorics?, Linear Algebra and Its Applications, 367, (2003), 313-335. 
  3. [3] L. B. Beasley, S. J. Kirkland and B. L. Shader, Rank Comparisons, Linear Algebra and Its Applications, 221, (1995), 171-188. Zbl0823.15003
  4. [4] A. Berman and N. Shaked-Monderer, Remarks on completely positive matrices, Linear and Multilinear Algebra 44, (1998), 149-163. 
  5. [5] A. Berman and N. Shaked-Monderer, Completely Positive Matrices, World Scientific, River Edge, NJ, (2003). 
  6. [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. Zbl1310.15059
  7. [7] D. Cartwright and M. Chan, Three notions of tropical rank for symmetric matrices, Combinatorica. 32, (2012), 1, 55-84. [WoS] Zbl1299.14050
  8. [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. Zbl0838.15011
  9. [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. Zbl0815.15019
  10. [10] P. Erdos, A.W. Goodman, and L. Posa, The representation of a graph by set intersections, Canad. J.Math. (1966), 18, 106-112. Zbl0137.43202
  11. [11] J.S. Golan, Semirings for the ring theorist, Rev. Roumaine Math. Pures Appl. 35, (1990), 6, 531-540. Zbl0732.16030
  12. [12] Steven Givant and Paul Halmos, Introduction to Boolean Algebras, Undergraduate Texts in Mathematics, Springer, New York, 2009. Zbl1168.06001
  13. [13] J. Hannah and T. L. Laffey, Nonnegative factorization of completely positivematrices, Linear Algebra and Its Applications 55, (1983), 1-9. [WoS] Zbl0519.15007
  14. [14] Ki Hang Kim, Boolean matrix theory and applications, Marcel Dekker, New York, 1982. Zbl0495.15003
  15. [15] M. Kaykobad, On Nonnegative Factorization of Matrices, Linear Algebra and Its Applications 96, (1987), 23-33. Zbl0626.15010
  16. [16] S. J. Kirkland and N. J. Pullman, Boolean spectral theory, Linear Algebra and Its Applications, 175, (1992), 177-190. [WoS] Zbl0769.15007
  17. [17] S. J. Kirkland and N. J. Pullman, Linear operators preserving invariants of nonbinary Booleanmatrices, Linear andMultilinear Algebra, 33, (1993), 295-300. Zbl0847.15006
  18. [18] C. M. Lau and T. L.Markham, Square triangular factorizations of completely positivematrices, J. IndustrialMathematics Soc. 28, (1978), 15-24. Zbl0398.15011
  19. [19] R. Loewy and B-S. Tam, CP rank of completely positivematrices of order five, Linear Algebra and Its Applications 363, (2003), 161-176. Zbl1019.15009
  20. [20] T. L. Markham, Factorization of completely positive matrices, Proc. Cambridge Philos. Soc. 69, (1971), 53-58. [Crossref] Zbl0205.33004
  21. [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] Zbl1317.15029
  22. [22] M. Plus, Linear systems in (max, +) algebra, In Proceedings of the 29th Conference on Decision and Control, Honolulu, Dec. (1990). 
  23. [23] N. Shaked-Monderer, Minimal CP Rank, Electron. J. Linear Algebra 8, (2001), 140-157. 
  24. [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] Zbl1314.15025
  25. [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] Zbl0010.38804
  26. [26] X. Zhan, Open problems in matrix theory, Proceedings of the 4th International Congress of Chinese Mathematicians, 1, (2008), 367-382. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.