zbMATH — the first resource for mathematics

Nonnegative ranks, decompositions, and factorizations of nonnegative matrices. (English) Zbl 0784.15001
Let \(A\) be an \(m \times n\) nonnegative matrix with elements in an ordered field. The smallest nonnegative integer \(q\) for which there exist \(q\) nonnegative column vectors such that each column of \(A\) can be expressed as a nonnegative linear combination of those vectors is called the nonnegative column rank, \(c-\text{rank}_ +A\). The nonnegative row rank, \(r-\text{rank}_ +A\), is defined in a similar manner. Two other nonnegative ranks are defined for \(A\) and all four are proved to be equal.
The authors show that in calculating these rank it is sufficient to calculate the appropriate nonnegative rank of a bivariate probability matrix or a stochastic matrix associated with \(A\). They prove that if the (ordinary) rank, rank \(A\), does not exceed 2 then \(\text{rank} A= \text{rank}_ +A\). Finally, they show that the nonnegative rank can be computed exactly over the reals by a finite algorithm. They pose the problem of determining whether or not the nonnegative ranks of a rational matrix, over the reals and rationals, respectively, are equal.

15A03 Vector spaces, linear dependence, rank, lineability
15B48 Positive matrices and their generalizations; cones of matrices
15A23 Factorization of matrices
15B51 Stochastic matrices
Full Text: DOI
[1] Berman, A.; Hershkowitz, D., Combinatorial results on completely positive matrices, Linear algebra appl., 95, 111-125, (1987) · Zbl 0623.05040
[2] Berman, A.; Plemmons, R., Nonnegative matrices in the social sciences, (1979), Academic New York
[3] Breiman, L., The ∏ method for estimating multivariate functions from noisy data, Technometrics, 33, 125-143, (1991) · Zbl 0742.62037
[4] Cohen, P.J., Decision procedures for real and p-adic fields, Comm. pure appl. math., 22, 131-151, (1969) · Zbl 0167.01502
[5] Collins, G.E., Quantifier elimination for real closed fields by cylindrical algebraic decomposition, (), 515-532
[6] Eaves, B.C.; Rothblum, U.G., A theory on extending algorithms for parametric problems, Math. oper. res., 14, 502-533, (1989) · Zbl 0673.90081
[7] Gregory, D.A.; Pullman, N.J., Semiring rank: Boolean rank and nonnegative rank factorization, J. combin. inform. system sci., 3, 223-233, (1983) · Zbl 0622.15007
[8] Harshman, R.A., Foundations of the \scparafac procedure: models and conditions for an ‘explanatory’ multi-modal factor analysis, UCLA working paper in phonetics, 16, (1970)
[9] Hayashi, C., An algorithm for the solution of \scparafac model and analysis of the databy the international Rice adaptation experiments, Bull. biometric soc. Japan, 3, 77-91, (1982)
[10] Henry, L., Schémas de nuptialité: Déséquilibre des sexes et célibat, Population (Paris), 24, 457-486, (1969)
[11] Henry, L., Schémas de nuptialité: Déséquilibre des sexes et âge au mariage, Population (Paris), 24, 1067-1122, (1969)
[12] Henry, L., Nuptiality, Theoret. population biol., 3, 135-152, (1972)
[13] Jacobson, N., Lectures in abstract algebra III, (1964), Van Nostrand Princeton, N.J
[14] Lancaster, P.; Tismenetsky, M., The theory of matrices with applications, (1985), Academic Orlando, Fla · Zbl 0516.15018
[15] Levin, B., On calculating maximum rank-one underapproximations for positive arrays, ()
[16] Nisan, N., Lower bounds for non-commutative computation, Proceedings of the 23rd annual ACM symposium on theory of computing, 410-418, (1991)
[17] Renegar, J., On the computational complexity and geometry of the first-order theory of the reals, parts I, II, III, J. symbolic logic, 13, 255-352, (1992) · Zbl 0798.68073
[18] Saboulin, M.de, Remarques sur le célibat engendré par LES déséquilibres de la répartition par sexe, Union internationale pour l’etude scientifique de la population, 22, (1985), Florence, Séance F.
[19] Seidenberg, A., A new decision method for elementary algebra, Ann. of math., 60, 365-374, (1954) · Zbl 0056.01804
[20] Suppes, P.; Zanotti, M., When are probabilistic explanations possible?, Synthese, 48, 191-199, (1981) · Zbl 0476.03011
[21] Tarski, A., A decision method for elementary algebra and geometry, (1951), Univ. of California Press Berkeley · Zbl 0044.25102
[22] Yannakakis, M., Expressing combinatorial optimization problems by linear programs, Proceedings of the 20th annual ACM symposium on theory of computing, 223-228, (1988)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.