Bull. Malays. Math. Sci. Soc. DOI 10.1007/s40840-017-0490-z

Preservers of Completely Positive Matrix Rank for Inclines LeRoy B. Beasley1 · Preeti Mohindru2 · Rajesh Pereira3

Received: 9 November 2016 / Revised: 22 March 2017 © Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia 2017

Abstract A real symmetric matrix A is called completely positive if there exists a nonnegative real n × k matrix B such that A = B B t . The smallest value of k for all possible choices of nonnegative matrices B is called the CP-rank of A. We extend the ideas of complete positivity and the CP-rank to matrices whose entries are elements of an incline in a similar way. We classify maps on the set of n × n symmetric matrices over certain inclines which strongly preserve CP-rank-1 matrices as well as maps which preserve CP-rank-1 and CP-rank-k. The result suggests that there is a certain standard class of solutions for CP-rank preserver problems on incline matrices. Keywords Semirings · Inclines · Completely positive matrices · Cp-rank · (Strong) linear preservers Mathematics Subject Classification 15A86

Communicated by Emrah Kilic. The research of this author was supported by the Natural Sciences and Engineering Research Council of Canada Discovery Grant No. 400550.

B

LeRoy B. Beasley [email protected] Preeti Mohindru [email protected] Rajesh Pereira [email protected]

1

Department of Mathematics and Statistics, Utah State University, Logan, UT 84322-3900, USA

2

Cogswell College, San Jose, CA 95134, USA

3

Department of Mathematics and Statistics, University of Guelph, Guelph, ON N1G 2W1, Canada

123

L. B. Beasley et al.

1 Introduction A semiring is a set together with two binary operations (S, +, ·) such that (S, +) is a commutative monoid having identity 0, (S, ·) is a monoid with identity 1, multiplication distributes over addition, and 0 · s = s · 0 = 0 for all s ∈ S. The semiring S is commutative if (S, ·) is commutative, S is antinegative if a + b = 0 implies that a = b = 0. An element, a, of a semiring S is said to be cancellative if whenever ab = ac for some b, c ∈ S, we have that b = c. We now define the concepts of a semilattice and an incline; the latter can be thought of as a special class of semiring. Definition 1.1 A semilattice is a set together with a commutative, associative and idempotent binary operation (S, ). Definition 1.2 [2] An incline is a set with two binary operations, (S, , ), satisfying the following three conditions 1. (S,  ≡ l.u.b.) is a semilattice 2.  distributes over  3. x  (x  y) = x for all x, y ∈ S.

(1)

We note that several authors use ⊕ and ⊗ instead of  and . We will reserve ⊕ for the direct sum of two matrices which is also used in this paper. In an incline, we have the usual semilattice partial order ≤ defined by x ≤ y ⇔ x  y = y. We use the standard notion of < where x < y means both x = y and x ≤ y. We also let x  x = x 2 . Henceforth, except in formal definitions, we shall represent addition in any semiring with + and multiplication by juxtaposition. If an incline has an additive identity 0, it will always be the least element of the incline. If an incline has a multiplicative identity 1, it will always be the greatest element of the incline. An incline with both additive and multiplicative identities is always an antinegative semiring. Henceforth we will assume that all inclines have both an additive and a multiplicative identity. We will also assume without exception that all of the semirings and inclines in this paper are commutative (i.e., their multiplication operation is commutative). The theory of inclines and their applications is discussed in [2]. Kim and Roush [4] have surveyed and described algebraic properties of inclines and matrices over inclines. Definition 1.3 [3] An incline is said to be linearly ordered or totally ordered if the semilattice partial order ≤ is a total order relation.

123

Preservers of Completely Positive Matrix Rank for Inclines

Examples of totally ordered inclines include the two element Boolean semiring ({0, 1}), the max–min fuzzy algebra ([0, 1], max(x, y), min(x, y)), the max-plus semiring ([−∞, 0], max(x, y), x + y), and the max-times semi ring ([0, 1], max(x, y), x y) where x y is the ordinary real multiplication. Note that distributive lattices and Boolean algebras are also inclines but they are not necessarily totally ordered. Let Mm,n (S) denote the set of all m ×n matrices with entries in S. Clearly Mm,n (S) is a semimodule over S where all operations are defined as if S were a field. If m = n we use the notation Mn (S). We let Jm,n denote the m × n matrix of all ones, Om,n the m × n matrix of all zeros, and In the n × n identity matrix. If m = n we write Jn and On . The subscripts are suppressed unless there is possibility of confusion, and we write J, O, I , respectively. The matrix E i, j in Mm,n (S) is the m × n matrix with exactly one nonzero entry, that being a one in the (i, j) position and is called a cell. We call E i,i ∈ Mn (S) a diagonal cell. Let Dn denote the set of all diagonal matrices. The matrix Di, j , for i = j, is the n × n matrix with exactly two nonzero entries, those being a one in the (i, j) position and a one in the ( j, i) position. That is, Di, j = E i, j + E j,i . The matrix Di, j is called a digon. A weighted diagonal cell is a scalar multiple of a diagonal cell, and a weighted digon is a scalar multiple of a digon. Let A, B ∈ Mm,n (S). We say that A dominates B if ai j = 0 implies that bi j = 0. This is denoted by A B or B  A. The following algebraic version of the dominance order will be very useful in linear preserver theory. Lemma 1.1 Let S be a commutative incline with no zero divisors and A, B ∈ Mm,n (S). Then A B if and only if there exists a nonzero k ∈ S such that A + k B = A. Proof Suppose A B. Let k be the product of all nonzero elements of A. If ai j = 0, then kbi j ≤ k ≤ ai j and if ai j = 0, then bi j = 0. In either case, we have ai j + kbi j = ai j . The converse follows from the fact that the incline is antinegative and has no zero divisors. Let A ◦ B denote the Hadamard product of A and B, that is A ◦ B = [ai j bi j ] ∈ Mm,n (S). The direct sumof twomatrices A ∈ Mm,n (S) and B ∈ Mr,s (S) is the A O (m + r ) × (n + s) matrix . O B A matrix A ∈ Mm,n (S) has factor rank k if there are matrices B ∈ Mm,k (S) and C ∈ Mk,n (S) such that A = BC and k is minimal in this respect. The set Sn (S) is the subset of Mn (S) consisting of all symmetric matrices in Mn (S). Definition 1.4 A semiring S is said to have the unique square root property if for every s ∈ S, there exists a unique x ∈ S such that x 2 = s. All above examples of totally ordered inclines are examples of semirings with the unique square root property. Distributive lattices and Boolean algebras also have the unique square root property, and in these semirings, every element is a unique square

123

L. B. Beasley et al.

root of itself. Not every totally ordered incline has the unique square root property. Let S = {0, 1, 2} with a  b being the maximum of a and b and a  b being 1 if neither a nor b is 0 and being 0 otherwise. This incline has no zero divisors and is totally ordered but does not have the unique square root property. Given a semiring S, let P be the subsemiring of all elements of S that can be written as a sum of squares of elements from S. This subsemiring is called the positive subsemiring. For example, if S = R then P = R+ , and if S is a semiring with the unique square root property, then P = S. For more details on the positive subsemiring we refer the reader to [5]. We will also need the following concept from [6]. Definition 1.5 A commutative incline S is said to have the LI-property if for all x, y ∈ s with x ≤ y there exists z ∈ S such that x = yz. All of the examples given in the paragraph immediately following Definition 1.3 have the LI-property. More about the LI-property including several equivalent conditions and the reason for its name can be found in [6]; we will not need any of this theory here. Definition 1.6 [5] A matrix A ∈ Sn (S) is said to be completely positive if there is some matrix B ∈ Mn,k (P) such that A = B B t . The CP-rank of the matrix A, denoted cp(A), is the smallest k such that A = B B t for some B ∈ Mn,k (P). A mapping T : Sn (S) → Sn (S) is called a linear operator if T (α A + β B) = αT (A) + βT (B) for all A, B ∈ Sn (S) and for all α, β ∈ S. In particular T (O) = O. It follows from lemma 1.1 that all linear operators preserve the dominance order (i.e., A B implies that T (A) T (B)). Let X be a subset of Sn (S). We say that a linear operator T preserves the set X if T (A) ∈ X whenever A ∈ X . The operator T strongly preserves X if T (A) ∈ X if and only if A ∈ X . If f is a function, f : S → Z for some set Z, then we say that T preserves f if f (T (A)) = f (A) for all A ∈ Sn (S). A significant number of linear preserver problems deal with linear operators on the space of all m × n matrices which preserve the rank function of matrices. In this article we study linear preservers of the CP-rank of completely positive matrices over certain classes of semirings. In Sects. 2 and 3, we develop preliminary results needed to characterize all linear operators T : Sn (S) → Sn (S) over certain classes of semirings that (1) strongly preserve the set of CP-rank-1 matrices and (2) preserve 2 the set of CP-rank-1 matrices and, for some fixed k such that 2 ≤ k ≤  (n−1) 4 , the set of CP-rank-k matrices. In Sect. 4, we show that for matrices over totally ordered inclines, a linear operator T strongly preserves the set of CP-rank-1 matrices or the set of CP-rank-1 matrices and the set of CP-rank-2 matrices if and only if T is of the form T (A) = P t (D AD + ((AB) ◦ I ))P where P is a permutation matrix, D is a diagonal matrix all of whose diagonal entries are cancellative, B is a matrix whose entries lie in a certain ideal and ◦ is the Hadamard product. We show a similar result over certain semirings when T preserves CP-rank-1 matrices and CP-rank-k matrices for some fixed k.

123

Preservers of Completely Positive Matrix Rank for Inclines

2 Strong CP-rank-1 Preservers In this section, we shall characterize the linear operators that map the set of matrices over certain classes of semirings of CP-rank 1 to itself and the complement of that set to itself. Let C Pk denote the set of all matrices in Sn (S) that have CP-rank-k. A special function we shall use is a mapping concerning the number of nonzero diagonal elements of a rank one matrix. Definition 2.1 Define φ : C P1 → Z+ by φ(A) = k if A = xxt and |x| = k, where |x| denotes the number of nonzero entries in the vector x. The next lemma is key in our investigation. Lemma 2.1 Let S be a commutative incline with both additive and multiplicative identities and without zero divisors and T : Sn (S) → Sn (S) be a linear operator that strongly preserves C P1 or that preserves both C P1 and C P2 , then T preserves the function φ. Proof We will use in our proof the fact that if A ∈ C P1 and φ(A) = q, then there are two matrices, an n by n diagonal matrix D with no zeros along the main diagonal and a permutation matrix P such that A = P D(Jq ⊕ O)D P t . Further, G(X ) = P D X D P t is a linear operator that preserves φ, complete positivity, and C P−rank-1. Suppose for some A ∈ C P1 that φ(A) = k and φ(T (A)) < k. Let k be the smallest positive integer such that there exists a B ∈ C P1 with k = φ(B) > φ(T (B)). By the above observation about the operator G, we may assume that B = Jk ⊕ O, and T (Jk ⊕ O)  T (Jk−1 ⊕ O). It follows that T (E k,k )  T (Jk−1 ⊕ O). Suppose for some A ∈ C P1 that φ(A) =  and φ(T (A)) > . By the above observation about the operator G, we may assume that A = J ⊕ O. Now, since φ(T (Jn )) ≤ n, there is some k such that T (Jk ⊕ O)  T (Jk−1 ⊕ O). It follows that T (E k,k )  T (Jk−1 ⊕ O). Now, if T (E k,k )  T (Jk−1 ⊕ O), let T (E k,k ) = F = ( f i j ) and T (Jk−1 ⊕ O) = yyt . Let  L be2 the set of indices such that yi = 0 if and only if i ∈ L. Let α = i∈L yi . Now, since S has no zero divisors, α  = 0. Further, the (i, j) entry of T (Jk−1⊕ O + α E k,k) = T (Jk−1 ⊕ O) + αT (E k,k ) is yi y j + α f i j . But, α fi j = ,=i y )( ∈L ,= j y )( f i j )] so that yi y j + α f i, j = yi y j +  yi y j [( ∈L yi y j [( ∈L ,=i y )( ∈L ,= j y )( f i j )] = yi y j by the special property of incline arithmetic (1). Thus, the (i, j) entry of T (Jk−1 ⊕ O + α E k,k ) is yi y j . That is, T (Jk−1 ⊕ O + α E k,k ) = T (Jk−1 ⊕ O), a contradiction since cp(Jk−1 ⊕ O + α E k,k ) = 2 and cp(Jk−1 ⊕ O) = 1. We now have that if A is a CP-rank-1 matrix, φ(T (A)) = φ(A).   Corollary 2.1 Let S be a commutative incline with both additive and multiplicative identities and without zero divisors and let T : Sn (S) → Sn (S) be a linear operator that preserves the set of CP-rank-1 matrices strongly, or the set of CP-rank-1 matrices and the set of CP-rank-2 matrices, then T maps the set of diagonal cells one to one onto a set of n distinct weighted diagonal cells (i.e., no two are the same diagonal cell weighted differently).

123

L. B. Beasley et al.

A linear operator T on Sn (S) is singular if T (A) = O for some nonzero A ∈ Sn (S). Otherwise T is nonsingular. Corollary 2.2 Let S be a commutative incline with the unique square root property, with both additive and multiplicative identities and without zero divisors and T be a linear operator on Sn (S). For 1 ≤ k < n, if T preserves C Pk and C Pk+1 , then T is nonsingular. Proof If T is singular, there is some X ∈ Sn (S) such that T (X ) = O. Since S is antinegative, if X dominates the digon, Di, j then T (Di, j ) = O, and if X dominates the diagonal cell E i,i , then T (E i,i ) = O. Thus we need only consider these two cases. Suppose that T (Di, j ) = O for some Di, j . Since the CP-rank is invariant under permutational similarity, we may assume that T (D1,2 ) = O. Suppose k = 1. Let A be the matrix, A = E i,i + E j, j + Di, j . Then for some nonzero α, β ∈ S, T (A) = α Er,r + β E s,s , using Corollary 2.1. But then cp(A) = 1 and cp(T (A)) = 2; hence, we have a contradiction. Now, suppose that k ≥ 2. Let A be the completely positive matrix, A = (E 1,1 +   k+1  E 2,2 + D1,2 ) + El,l so that cp(A) = k. Let B be the completely positive matrix, l=3

B = E 1,1 + E 2,2 +

 k+1 

 El,l so that cp(B) = k + 1. Then, since T (Di, j ) = O,

l=3

T (A) = T (B), a contradiction. Hence, given the pair (i, j), T (Di, j ) = O. If T (E i,i ) = O for some i, then by permuting we may assume that i = k + 1 and we have that T (Ik ⊕ O) = T (Ik+1 ⊕ O), contradicting that T preserves both C Pk and C Pk+1 . Thus, T is nonsingular.   Before stating our next lemma, we introduce the following concepts. Definition 2.2 Let S be an incline. A subset I of S is said to be an ideal if the following two conditions are satisfied: 1. a, b ∈ I implies that a  b ∈ I 2. a ∈ I and c ≤ a implies that c ∈ I Definition 2.3 Let S be a commutative incline and let a ∈ S. Then Q(a) is the set defined as follows: Q(a) = {s ∈ S : s  x ≤ (a  x)2 for all x ∈ S}. Let a ∈ S be arbitrarily chosen. It can easily be seen that Q(a) is an ideal in S. As an example, if S is the max–min incline ([0, 1], max, min), then Q(a) = [0, a], but if S is the max-times incline ([0, 1], max, ×), then Q(a) = {0}. Lemma 2.2 Let S be a totally ordered commutative incline with the unique square root property, with both additive and multiplicative identities and without zero divisors and let T : Sn (S) → Sn (S) be a linear operator that preserves the set of CPrank-1 matrices strongly, such that T (E i,i ) = ai2 E i,i , then T (Di, j ) = ai a j Di, j + α E i,i + β E j, j for some α and β such that α ∈ Q(ai ) and β ∈ Q(a j ). Further, T (E i,i + E j, j + Di, j ) = ai2 E i,i + a 2j E j, j + ai a j Di, j .

123

Preservers of Completely Positive Matrix Rank for Inclines

Proof Let A = x Di, j + x 2 E i,i + E j, j where x is an arbitrary nonzero element of S. Then, A is a CP-rank-1 matrix and φ(A) = 2. By Lemma 2.1 we have that cp(T (A)) = 1 and φ(T (A)) = 2. Thus, T (A) = (x 2 ai2 + xα)E i,i + (a 2j + xβ)E j, j + xγ Di, j for some α, β and γ in S. If xα ≥ x 2 ai2 , then T (A) = T (x Di, j + E j, j ), contradicting that T strongly preserves the set of CP-rank-1 matrices since x Di, j + E j, j is not a CP-rank1 matrix. Thus, α ∈ Q(ai ). Using a similar argument with A = x Di, j + E i,i + x 2 E j, j will give us β ∈ Q(a j ). For the choice of x = 1, since S has the unique square root property, we now have that T (A) = ai2 E i,i + a 2j E j, j + γ Di, j , and consequently, γ = ai a j since cp(T (A)) = 1.   Lemma 2.3 Let S be a totally ordered commutative incline with the unique square root property, with both additive and multiplicative identities and without zero divisors and T : Sn (S) → Sn (S) be a linear operator that preserves the set of CP-rank-1 matrices strongly, such that T (E i,i ) = ai2 E i,i , then ai is a cancellative element of S for all i. Proof Suppose ai is not a cancellative element of S for some fixed i, then there exists b, c ∈ S with b > c such that ai b = ai c. Note that if b2 = c2 , the element b2 would have two distinct square roots which would contradict the unique square root property so b2 = c2 . Let x = ai b = ai c. Let A = b2 E i,i + cDi, j + E j, j , which means that T (A) = x 2 E i,i + xa j Di, j + a 2j E j, j . Hence A has CP-rank-2 since b2 = c2 , but T (A) has CP-rank-1 which is a contradiction, so all of the ai s must be cancellative elements.   Lemma 2.4 Let S be a commutative incline with both additive and multiplicative identities and without zero divisors and A ∈ Sn (S) be completely positive and D, B ∈ Mn (S) where D is a diagonal matrix and B has entries which satisfy bi j ∈ Q(d j j ) for all i, j. Then ((AB) ◦ I ) ≤ D AD. Proof By linearity, it is sufficient to prove this result for completely matripositive n T . Then [(AB) ◦ I ] ces of CP-rank-1. So suppose A = vv = v v jj i=1 i j bi j ≤ n 2 d 2 = [D AD] . Hence (AB) ◦ I ≤ D AD. v b ≤ v   jj i=1 j i j j jj

3 Preservers of C P1 and C Pk In this section, if a matrix, A, is not completely positive, then we define cp(A) = −1. Let S be an antinegative semiring without zero divisors. Define a mapping ηS : Z+ → Z+ by ηS (r ) = min max cp(b A). Note that ηS also depends on the size b∈S\{0} A Jr ⊕O

of the matrix n. For any fixed n, the function ηS (r ) is a function from {1, 2, . . . , n} → N which is nonincreasing in r . A base element is either a diagonal cell or a digon so called because they form a basis of Sn (S) Lemma 3.1 Let S be an antinegative semiring without zero divisors, T : Sn (S) → Sn (S) be a linear operator that preserves C P1 and let X ∈ Sn (S) be completely positive. Then cp(T (X )) ≤ cp(X ).

123

L. B. Beasley et al.

The proof depends on considering the image of a CP-rank-1 decomposition of X and is left to the reader. Lemma 3.2 Let S be an antinegative semiring without zero divisors and suppose that ηS (n) < max A∈Sn (S) cp(A). Let k be a fixed integer such that k ≥ 2 and such that ηS (n) ≤ k < max A∈Sn (S) cp(A), and let T : Sn (S) → Sn (S) be a linear operator that preserves C P1 and C Pk . Then the image of a diagonal cell is a weighted diagonal cell. Proof Suppose that the image of some diagonal cell is not a weighted diagonal cell. Since each diagonal cell is a CP-rank-1 matrix, its image must also be a CP-rank1 matrix. Thus, by permuting we may assume that T (E 1,1 ) = D1 Jr1 D1 ⊕ O for some r1 ≥ 2 and r1 × r1 diagonal matrix D1 with all diagonal entries nonzero. That is, T (J1 ⊕ O) = (D1 Jr1 D1 ⊕ O) for some r1 ≥ 2 and r1 × r1 diagonal matrix D1 with all diagonal entries nonzero. Unless T (E 1,1 ) T (Jn ), there is some base element whose image is not dominated by Jr1 ⊕ O. By permuting and adding necessary base elements we may assume that T (J2 ⊕ O) Jr1 +1 ⊕ O. That is, T (J2 ⊕ O) = (D2 Jr2 D2 ⊕ O) with r2 ≥ 3 and r2 × r2 diagonal matrix D2 with all diagonal entries nonzero. Continuing in this way we have that if 2 ≤  ≤ n, either T (J ⊕ O) T (Jn ) or T (J ⊕ O) = (D Jr D ⊕ O) for some r ≥  + 1 and r × r diagonal matrix D with all diagonal entries nonzero. Fix  such that ηS () ≥ k and ηS ( + 1) < k. Note that  exists since ηS (n) ≤ k ≤ max A∈Sn (S) cp(A) and ηS (n) < max A∈Sn (S) cp(A). Then, there exists B ∈ Sn (S) such that B J ⊕ O and cp(B) = k. Since linear operators preserve the dominance order, T (B) J+1 ⊕ O. By the choice of , cp(T (B)) < k, a contradiction. Thus, the image of a diagonal cell is a diagonal cell.   Corollary 3.1 Let S be an antinegative semiring without zero divisors and suppose that ηS (n) < max A∈Sn (S) cp(A). Let k be a fixed integer such that k ≥ 2 and such that ηS (n) ≤ k < max A∈Sn (S) cp(A), and let T : Sn (S) → Sn (S) be a linear operator that preserves C P1 and C Pk . Then the image of the direct sum of any  diagonal cells is the sum of at most  weighted diagonal cells. Lemma 3.3 Let S be a commutative incline with both additive and multiplicative identities and without zero divisors, and suppose that ηS (n) < max A∈Sn (S) cp(A). Let k be a fixed integer such that k ≥ 2 and such that ηS (n) ≤ k < max A∈Sn (S) cp(A)

and k ≤  (n−1) 4 , and let T : Sn (S) → Sn (S) be a linear operator that preserves C P1 and C Pk . Then, T induces a bijection on the set {1, 2, · · · , n} corresponding to the image of the diagonal cells (i.e., no two diagonal cells are mapped to a weighted cell in the same location). 2

Proof By Lemma 3.2 the image of a diagonal cell is a weighted diagonal cell. Suppose that T (E i,i ) = α Er,r and T (E j, j ) = β Er,r for some i = j. Without loss of generality, by permuting, we may assume that T (E 1,1 ) = α E 2,2 , T (E 2,2 ) = β E 2,2 and α ≤ β.. Note also that since the arithmetic of S satisfies (1), given x ∈ S, x + x = x and since  ≡ l.u.b, α + β = β.

123

Preservers of Completely Positive Matrix Rank for Inclines

If k ≤ n, let X = E 1,1 +E 2,2 +· · ·+E k,k so that cp(X ) = k, and hence cp(T (X )) = k since T preserves C Pk . But, T (X ) = (α + β)E 2,2 + T (E 3,3 ) + · · · + T (E k,k ) so that cp(T (X ) < k, a contradiction. 2 Now suppose k > n. Let I = {(i, j)|2 ≤ i ≤  n2  < j ≤ n} so that |I| =  (n−1) 4 . Let J ⊆ I be a subset such that (2, 3) ∈ / J and |J | = k − 2. Let X = E 1,1 + (E 2,2 + D2,3 + E 3,3 ) + (i, j)∈J (E i,i + Di, j + E j, j ) so that cp(X ) = k, and hence cp(T (X  )) = k since T preserves C Pk . But, T (X ) = T (E 1,1 )+ T (E 2,2 ) + T (D2,3+ E 3,3 ) + (i, j)∈J T (E i,i + Di, j + E j, j ) = α E 2,2 + β E 2,2 + T (D2,3 + E 3,3 ) + (i, j)∈J T (E i,i + Di, j + E j, j ) = (α + β)E 2,2 +T (D2,3 + E 3,3 ) +  (i, j)∈J T (E i,i + Di, j + E j, j ) = β E 2,2 + T (D 2,3 + E 3,3 ) + (i, j)∈J T (E i,i + T (D + E ) + Di, j + E j, j ) = T (E 2,2 ) + 2,3 3,3 (i, j)∈J T (E i,i + Di, j + E j, j ) =  T (E 2,2 + D2,3 + E 3,3 ) + (i, j)∈J T (E i,i + Di, j + E j, j ), so that T (X ) is the sum of k − 1 CP-rank-1 matrices since T preserves C P1 . That is, cp(T (X )) ≤ k − 1, a contradiction. Thus the image of two distinct diagonal cells is the sum of two weighted distinct diagonal cells. The lemma follows.   Lemma 3.4 Let S be a commutative incline with both additive and multiplicative identities and without zero divisors, and suppose that ηS (n) < max A∈Sn (S) cp(A). Let k be a fixed integer such that k ≥ 2 and such that ηS (n) ≤ k < max A∈Sn (S) cp(A)

and k ≤  (n−1) 4 , and let T : Sn (S) → Sn (S) be a linear operator that preserves C P1 and C Pk , and such that T (E i,i ) = αi E i,i for all i = 1, · · · , n. Then, for each (i, j) with 1 ≤ i < j ≤ n there are αi, j , i, j and δi, j such that T (Di, j ) = αi, j Di, j + i, j E i,i + δi, j E j, j . 2

Proof Suppose, without loss of generality, that T (D1,2 ) F where F is a base element that is not in {E 1,1 , E 2,2 , D1,2 }. Then, by permuting we have that T (E 1,1 + E 2,2 + D1,2 ) Jr2 ⊕ O and r2 ≥ 3. As in the proof of Lemma 3.2 we have that if  ≤ n, either T (J ⊕ O) T (Jn ) or T (J ⊕ O) T (Jr ⊕ O) for some r ≥  + 1. Now, fixing  such that ηS () ≥ k and ηS ( + 1) < k, there exists B ∈ Sn (S) such that  B J ⊕ O, T (B) J+1 ⊕ O, and cp(B) = k, cp(T (B)) < k, a contradiction.  Combining the above two lemmas we have: Corollary 3.2 Let S be a commutative incline with both additive and multiplicative identities and without zero divisors, and suppose that ηS (n) < max A∈Sn (S) cp(A). Let k be a fixed integer such that k ≥ 2 and such that ηS (n) ≤ k < max A∈Sn (S) cp(A) and

k ≤  (n−1) 4 , and let T : Sn (S) → Sn (S) be a linear operator that preserves C P1 and C Pk . Then, there exists a permutation matrix P, a diagonal matrix D with all nonzero diagonal entries, and an n × n matrix B such that T (X ) = P t (D X D + (B X ) ◦ I )P. 2

We note that the converses of corollary 3.2 may be false for many semirings without more conditions on B and D. In fact in certain cases T (X ) = P t (D X D + (B X ) ◦ I )P may not even preserve complete positivity. In certain cases finding these conditions on D and B is possible; the first theorem in our next section is an example.

123

L. B. Beasley et al.

4 Main Theorems For totally ordered inclines we can classify all strong CP-rank-1 preservers. Theorem 4.1 Let S be a totally ordered commutative incline with both additive and multiplicative identities, with the L I -property and the unique square root property and no zero divisors and let T : Sn (S) → Sn (S) be linear. Then the following are equivalent 1. T preserves CP-rank. 2. T strongly preserves the set of CP-rank-1 matrices. 3. T is of the form T (A) = P T (D AD + (AB) ◦ I )P where P is a permutation matrix, D is a diagonal matrix all of whose diagonal entries are cancellative and B is a matrix with bi j ∈ Q(d j j ) for all i, j. Proof That condition one implies condition two is immediate. Next we show condition two implies condition three. By Corollary 2.1, there exists a permutation matrix P such that P T (E i,i )P T = ai2 E i,i , for some ai ∈ S for all i. By Lemma 2.3, all of the ai s are cancellative. Let D = diag(a1 , a2 , . . . , an ). Now by Lemma 2.2, P T (Di, j )P T = ai a j Di, j + αi, j E i,i + βi, j E j, j where αi, j ∈ Q(ai ) and βi, j ∈ Q(a j ). Let B be the matrix whose main diagonal entries are zero and whose (i, j) entry is βi, j and whose ( j, i) entry is αi, j . Then bi, j ∈ Q(d j j ) for all i, j and T (A) = P T (D AD+(AB)◦I )P. We now prove that condition three implies condition one. We begin by showing that if D is a diagonal matrix all of whose diagonal entries are cancellative, D AD is a CP-rank-1 matrix if and only if A is CP-rank-1. Since the “if” direction is obvious, we prove the “only if” case. Suppose D AD is CP-rank-1, then there exists v such that D AD = vv T . Then vi v j = di ai j d j . By the unique square root property, √ √ √ vi = di aii for all i. Therefore di ai j d j = di aii a j j d j . Since the di s are cancella√ √ tive, ai j = aii a j j for all i, j. Therefore A has CP-rank-1. Let R be an arbitrary completely positive matrix. It is easy to see that cp(T (R)) ≤ cp(R), so we prove the opposite inequality. vectors v 1 , v 2 , . . . , v m m Letk m k=T cp(T (R)), then there exist k such that T (R) = k=1 v (v ) . Then for all (i, j), (v )i (v k ) j ≤ di d j ri j . Taking i = j and using the unique square roots property along with the total ordering we get √ (v k ) j ≤ d j r j j , and using the L I -property, there exists ckj ∈ S such that (v k ) j =  √ √ k k T d j ckj r j j . Let w k be a vector whose jth entry is ckj r j j . Let M = m k=1 w (w ) . k k T k k T Since Dw (w ) D = v (v ) , we have D M D = D R D. Since all of the nonzero entries of D are cancellative, R = M and hence cp(R) ≤ k = cp(T (R)). Therefore cp(T (R)) = cp(R) as required.   Note that all semirings for which addition is min or max, in particular, a chain semiring, the fuzzy reals, as well as the tropical semirings (([−∞, 0], max, +) or ([0, ∞], min, +)), are totally ordered inclines with the unique square root property and no zero divisors. Theorem 4.2 Let S be a commutative incline with both additive and multiplicative identities with the L I -property and the unique square root property and without zero divisors, and suppose that ηS (n) < max A∈Sn (S) cp(A). Let k be a fixed integer such

123

Preservers of Completely Positive Matrix Rank for Inclines

that k ≥ 2 and such that ηS (n) ≤ k < max A∈Sn (S) cp(A) and k ≤  (n−1) 4 , and let T : Sn (S) → Sn (S) be linear. Then the following are equivalent. 2

1. T preserves CP-rank. 2. T preserves the set of CP-rank-1 matrices and CP-rank-k matrices. 3. T is of the form T (A) = P T (D AD + (AB) ◦ I )P where P is a permutation matrix, D is a diagonal matrix all of whose diagonal entries are cancellative and B is a matrix with bi j ∈ Q(d j j ) for all i, j. Proof The proof of this theorem is nearly the same as the proof of Theorem 4.1: That condition one implies condition two is immediate. Next we show that condition two implies condition three. By Corollary 3.2, there exists a permutation matrix P such that P T (E i,i )P T = ai2 E i,i , where ai ∈ S for all i. Let D = diag(a1 , a2 , . . . , an ). Now by Lemma 3.4, P T (Di, j )P T = ai a j Di, j + αi, j E i,i + βi, j E j, j where αi, j ∈ Q(ai ) and βi, j ∈ Q(a j ). Let B be the matrix whose main diagonal entries are zero and whose (i, j) entry is βi, j and whose ( j, i) entry is αi, j . Then bi, j ∈ Q(d j j ) for all i, j. and T (A) = P T (D AD + (AB) ◦ I )P. That condition three implies condition 1 is precisely the last two paragraphs of the proof of Theorem 4.1.   Since when A is a completely positive matrix, we have P T (D AD + (AB) ◦ I )P = D AD P whenever bi j ∈ Q(d j j ) for all i, j. It has been noted [1, Corollary 3.1] that T (X ) = P T D AD P is a C P-rank preserver on the space of real matrices whenever P is a permutation matrix and D is a positive diagonal matrix. In [5] and [6], it was noted that there are many intriguing similarities between the properties of completely positive real matrices and the properties of completely positive matrices over certain semirings and inclines; the results in this section provide a further instance of this. PT

Acknowledgements The authors would like to thank the referees for their careful reading of the paper and for many helpful suggestions which greatly improved the paper.

References 1. Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, Singapore (2003) 2. Cao, Z.Q., Kim, K.H., Roush, F.W.: Incline Algebra and Applications. Ellis Horwood, Chichester, England, Wiley, New York (1984) 3. Duan, J.-S., Guo, A.-P., Zhao, F.-X., Xu, Li, Tang, W.-G.: Standard bases of a vector space over a linearly ordered incline. Commun. Algebra 39(4), 1404–1412 (2011). doi:10.1080/00927871003738915 4. Kim, K.H., Roush, F.W.: Inclines and incline matrices: a survey. Linear Algebra Appl. 379, 457–473 (2004) 5. Mohindru, P., Pereira, R.: Orderings on semirings and completely positive matrices. Linear Multilinear Algebra 64, 818–833 (2016). doi:10.1080/03081087.2015.1059405 6. Mohindru, P., Pereira, R.: The DJL conjecture for CP matrices over special inclines. Commun. Algebra 44, 3818–3841 (2016). doi:10.1080/00927872.2015.1087011

123