A linear programming based analysis of the CP-rank of completely positive matrices

Yingbo Li; Anton Kummert; Andreas Frommer

International Journal of Applied Mathematics and Computer Science (2004)

  • Volume: 14, Issue: 1, page 25-31
  • ISSN: 1641-876X

Abstract

top
A real matrix A is said to be completely positive (CP) if it can be decomposed as A = BB^T, where the real matrix B has exclusively non-negative entries. Let k be the rank of A and Φ_k the least possible number of columns of the matrix B, the so-called completely positive rank (cp-rank) of A. The present work is devoted to a study of a general upper bound for the cp-rank of an arbitrary completely positive matrix A and its dependence on the ordinary rank k. This general upper bound of the cp-rank has been proved to be at most k(k + 1)/2. In a recent pioneering work of Barioli and Berman it was slightly reduced by one, which means that Φ_k ≤ k(k + 1)/2 - 1 holds for k ≥ 2. An alternative constructive proof of the same result is given in the present paper based on the properties of the simplex algorithm known from linear programming. Our proof illuminates complete positivity from a different point of view. Discussions concerning dual cones are not needed here. In addition to that, the proof is of constructive nature, i.e. starting from an arbitrary decomposition A = B_1B^T_1 (B_1 ≥ 0) a new decomposition A = B_2B^T_2 (B_2 ≥ 0) can be generated in a constructive manner, where the number of column vectors of B_2 does not exceed k(k + 1)/2 − 1. This algorithm is based mainly on the well-known techniques stemming from linear programming, where the pivot step of the simplex algorithm plays a key role.

How to cite

top

Li, Yingbo, Kummert, Anton, and Frommer, Andreas. "A linear programming based analysis of the CP-rank of completely positive matrices." International Journal of Applied Mathematics and Computer Science 14.1 (2004): 25-31. <http://eudml.org/doc/207675>.

@article{Li2004,
abstract = {A real matrix A is said to be completely positive (CP) if it can be decomposed as A = BB^T, where the real matrix B has exclusively non-negative entries. Let k be the rank of A and Φ\_k the least possible number of columns of the matrix B, the so-called completely positive rank (cp-rank) of A. The present work is devoted to a study of a general upper bound for the cp-rank of an arbitrary completely positive matrix A and its dependence on the ordinary rank k. This general upper bound of the cp-rank has been proved to be at most k(k + 1)/2. In a recent pioneering work of Barioli and Berman it was slightly reduced by one, which means that Φ\_k ≤ k(k + 1)/2 - 1 holds for k ≥ 2. An alternative constructive proof of the same result is given in the present paper based on the properties of the simplex algorithm known from linear programming. Our proof illuminates complete positivity from a different point of view. Discussions concerning dual cones are not needed here. In addition to that, the proof is of constructive nature, i.e. starting from an arbitrary decomposition A = B\_1B^T\_1 (B\_1 ≥ 0) a new decomposition A = B\_2B^T\_2 (B\_2 ≥ 0) can be generated in a constructive manner, where the number of column vectors of B\_2 does not exceed k(k + 1)/2 − 1. This algorithm is based mainly on the well-known techniques stemming from linear programming, where the pivot step of the simplex algorithm plays a key role.},
author = {Li, Yingbo, Kummert, Anton, Frommer, Andreas},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {simplex algorithm; pivot process; basic feasible solution; completely positive matrices; cp-rank; linear programming},
language = {eng},
number = {1},
pages = {25-31},
title = {A linear programming based analysis of the CP-rank of completely positive matrices},
url = {http://eudml.org/doc/207675},
volume = {14},
year = {2004},
}

TY - JOUR
AU - Li, Yingbo
AU - Kummert, Anton
AU - Frommer, Andreas
TI - A linear programming based analysis of the CP-rank of completely positive matrices
JO - International Journal of Applied Mathematics and Computer Science
PY - 2004
VL - 14
IS - 1
SP - 25
EP - 31
AB - A real matrix A is said to be completely positive (CP) if it can be decomposed as A = BB^T, where the real matrix B has exclusively non-negative entries. Let k be the rank of A and Φ_k the least possible number of columns of the matrix B, the so-called completely positive rank (cp-rank) of A. The present work is devoted to a study of a general upper bound for the cp-rank of an arbitrary completely positive matrix A and its dependence on the ordinary rank k. This general upper bound of the cp-rank has been proved to be at most k(k + 1)/2. In a recent pioneering work of Barioli and Berman it was slightly reduced by one, which means that Φ_k ≤ k(k + 1)/2 - 1 holds for k ≥ 2. An alternative constructive proof of the same result is given in the present paper based on the properties of the simplex algorithm known from linear programming. Our proof illuminates complete positivity from a different point of view. Discussions concerning dual cones are not needed here. In addition to that, the proof is of constructive nature, i.e. starting from an arbitrary decomposition A = B_1B^T_1 (B_1 ≥ 0) a new decomposition A = B_2B^T_2 (B_2 ≥ 0) can be generated in a constructive manner, where the number of column vectors of B_2 does not exceed k(k + 1)/2 − 1. This algorithm is based mainly on the well-known techniques stemming from linear programming, where the pivot step of the simplex algorithm plays a key role.
LA - eng
KW - simplex algorithm; pivot process; basic feasible solution; completely positive matrices; cp-rank; linear programming
UR - http://eudml.org/doc/207675
ER -

References

top
  1. Barioli F. and Berman A. (2003): The maximal cp-rank of rank completely positive matrices. - Linear Algebra Appl., Vol. 363, pp. 17-33. Zbl1042.15012
  2. Berman A. and Plemmons R. (1979): Nonnegative Matrices in the Mathematical Sciences. - New York: Academic Press. Zbl0484.15016
  3. Berman A. and Shaked-Monderer N. (2003): Completely Positive Matrices. - New York: World Scientific. Zbl1030.15022
  4. Berman A. (1993): Completely positive graphs, In: Combinatorial and Graph-Theoretical Problems in Linear Algebra (R.A. Brnaldi, S. Friedland and V. Klee, Eds.). - New York: Springer, pp. 229-233. Zbl0792.05095
  5. Drew J.H., Johnson C.R. and Loewy R. (1994): Completely positive matrices associated with M-matrices. - Linear and Multilinear Algebra, Vol. 37, No. 4, pp.303-310. Zbl0815.15019
  6. Drew J.H. and Johnson C.R. (1996): The no long odd cycle theorem for completely positive matrices, In: Random Discrete Structures (D. Aldous and R. Premantle, Eds.). - New York: Springer, pp. 103-115. Zbl0838.15011
  7. Golub G.H. and Van Loan Ch.F. (1989): Matrix Computations. - Baltimore: J. Hopkins University Press. 
  8. Glashoff K. and Gustafson S. (1983): Linear Optimization and Approximation. - New York: Springer. Zbl0526.90058
  9. Gray L.J. and Wilson D.G. (1980): Nonnegative factorization of positive semidefinite nonnegative matrices. - Linear Algebra Appl., Vol. 31. Zbl0434.15012
  10. Hall Jr. M. and Newman M. (1963): Copositive and completely positive quadratic forms. - Proc. Cambridge Philos. Soc., Vol. 59, pp. 329-339. Zbl0124.25302
  11. Hall Jr. M. (1967): Combinatorial Theory. - Lexington: Blaisdell Hanna J. and Laffey T.J. (1983): Nonnegative factorization of completely positive matrices. - Linear Algebra Appl., Vol. 55, pp. 1-9. 
  12. Karloff H. (1991): Linear Programming. - Boston: Birkh Kaykobad M. (1988): On nonnegative factorization of matrices. - Linear Algebra Appl., Vol. 96, pp. 27-33. 
  13. Kelly C. (1994): A test of the markovian model of DNA evolution. - Biometrics, Vol. 50, No. 3, pp. 653-664. Zbl0822.62095
  14. Kogan N. and Berman A. (1993): Characterization of completely positive graphs. - Discrete Math., Vol. 114, No. 1-3, pp. 297-304. Zbl0783.05071

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.