Previous |  Up |  Next


completely positive matrix; cp-rank; factorization; discrete maximum principle
A symmetric positive semi-definite matrix $A$ is called completely positive if there exists a matrix $B$ with nonnegative entries such that $A=BB^\top $. If $B$ is such a matrix with a minimal number $p$ of columns, then $p$ is called the cp-rank of $A$. In this paper we develop a finite and exact algorithm to factorize any matrix $A$ of cp-rank $3$. Failure of this algorithm implies that $A$ does not have cp-rank $3$. Our motivation stems from the question if there exist three nonnegative polynomials of degree at most four that vanish at the boundary of an interval and are orthonormal with respect to a certain inner product.
[1] Barioli, F., Berman, A.: The maximal cp-rank of rank $k$ completely positive matrices. Linear Algebra Appl. 363 (2003), 17-33. MR 1969056 | Zbl 1042.15012
[2] Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, River Edge (2003). MR 1986666 | Zbl 1030.15022
[3] Croft, H. T., Falconer, K. J., Guy, R. K.: Unsolved Problems in Geometry. Problem Books in Mathematics 2 Springer, New York (1991). DOI 10.1007/978-1-4612-0963-8_8 | MR 1107516 | Zbl 0748.52001
[4] Berg, M. de, Kreveld, M. van, Overmars, M., Schwarzkopf, O.: Computational Geometry. Algorithms and Applications. Springer, Berlin (2000). DOI 10.1007/978-3-662-04245-8_1 | MR 1763734
[5] Post, K. A.: Triangle in a triangle: on a problem of Steinhaus. Geom. Dedicata (1993), 45 115-120. DOI 10.1007/BF01667408 | MR 1199733 | Zbl 0770.51021
[6] Shaked-Monderer, N.: A note on upper bounds on the cp-rank. Linear Algebra Appl. 431 2407-2413 (2009). MR 2563031 | Zbl 1180.15028
[7] Steinhaus, H.: One Hundred Problems in Elementary Mathematics. Popular Lectures in Mathematics 7 Pergamon Press, Oxford (1963). MR 0157881 | Zbl 0116.24102
[8] Sullivan, J. M.: Polygon in a triangle: Generalizing theorem by Post. Preprint available at (1996).
[9] Vejchodský, T., Šolín, P.: Discrete maximum principle for higher-order finite elements in 1D. Math. Comput. 76 1833-1846 (2007). DOI 10.1090/S0025-5718-07-02022-4 | MR 2336270 | Zbl 1125.65108
Partner of
EuDML logo