Completely Positive Matrices Over Semirings and Their CP-rank

Mohindru, Preeti
Journal Title
Journal ISSN
Volume Title
University of Guelph

An n x n real matrix A is called completely positive if it can be written as A = BB^T , where B is an n x m real nonnegative matrix for some positive integer m. The smallest such m is called the CP-rank of A. In 1994, Drew, Johnson and Loewy conjectured that the CP-rank of n x n real completely positive matrices of order n ≥ 4 is bounded above by [n²/4]. There was some evidence in support of this conjecture. However, Bomze and his co-workers (2014) disproved this conjecture for real completely positive matrices of order seven through eleven. In this thesis, we initiate the study of completely positive matrices over special types of algebraic structures called semirings. Semirings satisfy all properties of unital rings except the existence of additive inverses. We formulate a notion of complete positivity for matrices over semirings and show that this notion of complete positivity over special types of semirings has some important similarities with the standard notion of complete positivity of real matrices. We find some necessary and sufficient conditions for matrices over certain semirings to be completely positive. We prove the famous Drew-Johnson-Loewy conjecture for completely positive matrices over certain semirings, which include special types of inclines and Boolean algebras. Moreover, we show that in many cases the matrices of interest in graph theory are completely positive matrices over special types of semirings. In addition, we define a new family of ranks of matrices over certain semirings and show that these ranks generalize some known rank functions over semirings such as the determinantal rank. We classify all bijective linear maps which preserve these ranks.

Semirings, Completely Positive Matrices, The Drew-Johnson-Loewy conjecture, CP-rank, Rank of Matrices over semirings