Zero-one completely positive matrices and the A(R, S) classes

• Autorzy: G. Dahl , T. A. Haufmann
• Języki publikacji: EN

Abstrakty

EN

A matrix of the form A = BBT where B is nonnegative is called completely positive (CP). Berman and Xu (2005) investigated a subclass of CP-matrices, called f0, 1g-completely positive matrices. We introduce a related concept and show connections between the two notions. An important relation to the so-called cut cone is established. Some results are shown for f0, 1g-completely positive matrices with given graphs, and for {0,1}-completely positive matrices constructed from the classes of (0, 1)-matrices with fixed row and column sums.

Słowa kluczowe

EN

Completely positive matrix; (0, 1)-matrix; convex cone

• Wydawca: De Gruyter Open
• Czasopismo: Special Matrices
• Rocznik: 2016
• Tom: 4
• Numer: 1
• Strony: 296-304

Daty

otrzymano

2016-04-06

zaakceptowano

2016-05-23

online

2016-07-18

Twórcy

autor

G. Dahl

• Department of Mathematics, University of Oslo, Oslo, Norway

autor

T. A. Haufmann

• Department of Mathematics, University of Oslo, Oslo, Norway

Bibliografia

• [1] A. Berman and N. Shaked-Monderer. Completely Positive Matrices. World Scientific Publishing Co. Pte Ltd., Singapore, 2003.
• [2] A. Berman and C. Xu. {0,1} Completely positive matrices. Linear Algebra Appl., 399:35–51, Apr 2005.
• [3] A. Berman and C. Xu. Uniform and minimal {0,1}-cp matrices. Linear and Multilinear Algebra, 55(5):439–456, Sep 2007.
• [4] R. A. Brualdi. Combinatorial Matrix Classes, volume 13. Cambridge University Press, Cambridge, 2006.
• [5] S. Bundfuss and M. Dür. An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim., 20(1):30–53, 2008.
• [6] S. Burer. On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program., 120(2):479–495, Apr 2008.
• [7] G. Dahl. A note on diagonally dominant matrices. Linear Algebra Appl., 317(1-3):217–224, Sep 2000.
• [8] M. Deza and M. Laurent. Geometry of Cuts and Metrics. Springer, 1997.
• [9] M. Dür. Copositive Programming - A Survey. In Moritz Diehl, Francois Glineur, Elias Jarlebring, and Wim Michiels, editors, Recent Advances in Optimization and its Applications in Engineering, number 1, pages 3–21. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.
• [10] A. V. Karzanov. Metrics and undirected cuts. Math. Program., 32(2):183–198, 1985.
• [11] F. Laburthe, M. Deza, and M. Laurent. The Hilbert basis of the cut cone over the complete graph on six vertices. Technical report, 1995.
• [12] OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, https://oeis.org, 2016.
• [13] J. Zhong. Binary ranks and binary factorizations of nonnegative integermatrices. Electronic J. Linear Algebra, 23(June):540– 552, 2012.

Identyfikatory

DOI

10.1515/spma-2016-0024