The integer cp-rank of $2 \times 2$ matrices
Thomas Laffey Helena Šmigoc





H.Šmigoc: School of Mathematical Sciences, University College Dublin, Belfield, Dublin 4, Ireland; email: helena.smigoc@ucd.ie
T.J. Laffey: School of Mathematical Sciences, University College Dublin, Belfield, Dublin 4, Ireland; email: thomas.laffey@ucd.ie






The integer cp-rank of 2 × 2 matrices
    Thomas Laffey, Helena Šmigoc
    December 11th, 2019; revised on July 2nd, 2021
==================================================





We show the cp-rank of an integer doubly nonnegative 2 × 2 matrix does not exceed 11. 

Key words: completely positive matrices, doubly nonnegative matrices, integer matrices. 
	MSC[2010] 15B36, 	15B48.



  

Dedicated to Charles R. Johnson. 



§ INTRODUCTION



A n× n matrix A is said to be completely positive, if there exists a (not necessarily square) nonnegative matrix V such that A=VV^T. 
Completely positive matrices have been widely studied, and they play an important role in various applications. It is a subject to which C.R. Johnson has made an important contribution <cit.>.  For further background on completely positive matrices, we refer the reader to the following works and citations therein <cit.>.

Clearly, any completely positive matrix is nonnegative and positive semidefinite. We call the family of matrices that are both nonnegative and positive semidefinite doubly nonnegative. Doubly nonnegative matrices of
order less than 5 are completely positive <cit.>. However, this is no longer true for matrices of order larger than or equal to 6 <cit.>. 



Any n × n completely positive matrix A has many cp-factorizations of the form A=VV^T, where V is an n × m matrix. Note that m is also not unique. We define the cp-rank of A to be the minimal possible m. If we demand that V has rational entries, then we say that A has a rational cp-factorization. We define the rational cp-rank correspondingly. In this note we will study integer cp-factorizations, where we demand V to be an integer nonnegative matrix, and integer cp-rank, the minimal number of columns in the integer cp-factorization of a given matrix. 


Every rational matrix which lies in the interior of the cone of completely positive matrices has a rational cp-factorization <cit.>, but the question is still open for rational matrices on the boundary of the region. On the other hand, for n ≥ 3 it it easy to find examples of n × n integer completely positive matrices that do not have an integer cp-factorization. In <cit.>  the authors answered a question posed in <cit.>, by proving that for n=2 every integer doubly nonnegative matrix has an integer cp-factorization. An alternative proof of this result can be found in <cit.>.  Neither of those proofs offer a bound on the integer cp-rank of such matrices. In this note we prove that the integer cp-rank of 2 × 2 matrices cannot be larger than 11.  






§ MAIN RESULT


The question of determining the completely positive integer rank for a given n× n completely positive matrix is not trivial, even in the case when n=1. In this case the answer is given by Lagrange's Four-Square Theorem. 

[Lagrange's Four Square Theorem]
Every positive integer x can be written as the sum of at most four squares. If x is not of the form 

    x=4^r(8k+7)

 for some nonnegative integers r and k, then x is the sum of at most three squares. 


With Theorem <ref>, rank one  matrices are easy to analyse. 


An integer doubly nonnegative matrix A of rank 1 is completely positive, and has the integer cp-rank equal to the integer cp-rank of the greatest common divisor of its diagonal elements. 



Let A=(a_ij) be an integer doubly nonnegative matrix of rank 1, and let d:=(a_11,a_22,…,a_nn). Since a_ij=√(a_iia_jj), d also divides all the off-diagonal elements of A. Hence, A=dB, where B=(b_ij) satisfies (b_11,b_22,…,b_nn)=1.

We claim that each diagonal element in B is a perfect square. If this is not true, then b_i_0i_0=p c_i_0^2, where p is a product of distinct primes. Now b_i_0j^2=b_i_0i_0b_jj=pc_i_0^2 b_jj. Hence b_jj=p c_j^2 for some positive integer c_j and for all j. This implies that p divides b_jj for all j. As this contradicts our assumption, the claim is proved. 


Proposition below not only gives the first bound on the integer cp-rank of 2 × 2 matrices, but it also provides an approach that is later refined to improve the bound. 



A 2 × 2 integer doubly nonnegative matrix has an integer cp-factorization, and an integer cp-rank less than or equal to 12. 


 Let 
    A=a     b 
     b    c
 be an integer doubly nonnegative matrix. 
First we prove that we can reduce our problem to the case when a ≥ b and c ≥ b. To this end we assume b>c, and write b=α c+b_0, where α≥ 1 is a positive integer, and b_0 ∈{0,…, c-1}. Let 
    S(α):=1     -α
     0    1.
 We claim that 

    A_0=S(α)AS(α)^T=a-2 α b +α^2 c     b-α c 
     b-α c     c=a_0     b_0 
     b_0     c_0
 
is a doubly nonnegative matrix. From S(α)=1, we deduce A_0= A ≥ 0. Now,  the inequalities
A= a_0 c_0-b_0^2≥ 0 and c_0=c >0, imply that a_0=(a-2 α b_0-α c)≥ 0. 

Since S(α)^-1>0, any completely positive factorization of A_0:  A_0=B_0B_0^T, gives us a completely positive factorization of A: 
    A=(S(α)^-1B_0)(S(α)^-1B_0)^T.
 Clearly, B_0 and (S(α)^-1B_0) have the same number of columns, hence the two factorizations give the same bound on the cp-rank. With this we have proved, that to find an integer completely positive factorization for A it is sufficient to solve the problem for A_0, that satisfies a_0 ≥ b_0 and c_0≥ b_0. If b>a, we can repeat the above argument, with the roles of the diagonal elements reversed. 

 From now on we may assume that our given matrix A satisfies a ≥ b and c ≥ b.  Under this assumption we can write: 

    A   =b     b 
     b     b+a-b     0 
     0     c-b
       =b1     1 
     1     1+a-b     0 
     0     0+0     0 
     0     c-b.

By Lemma <ref> each of the rank 1 matrices in the above sum have the integer cp-rank at most 4, so the integer cp-rank of A is at most 12. 


To reduce the bound for the cp-rank to 11 we look more closely at the family of integers that cannot be written as a sum of less than four squares. 


Let x be a positive integer of the form (<ref>). Then x-2, x-6, x+2 and x+6 are not of the form  (<ref>). 



 Let x=4^r(8k+7) for some nonnegative integers r and k. Then: 

    x    ≡ 7 8 when  r=0, 
    
    x    ≡ 4 8 when  r=1, 
    
    x    ≡ 0 8 when  r≥ 2.

In each case, it is straightforward to check that x-6, x-2, x+2, x+6 are not equivalent to 7, 4 or 0 modulo 8, so they cannot be of the form (<ref>). 





 

Let 
    A=a     b 
     b    c
 be an integer doubly nonnegative matrix. Then A has an integer cp-factorization, and an integer cp-rank less than or equal to 11. 

  

 From (<ref>) and Theorem <ref> it is clear that the bound 12 will not be reached unless b, a-b and c-b are all of the form  (<ref>). In particular, the result holds for b ≤ 6, and for a-b ≤ 6 or c-b ≤ 6. So we assume b, a-b and c-b are all greater than or equal to 7, and that they all require four squares in Theorem <ref>.

First let us consider the case when a-b ≢7 8. In this case a-b-3≡ 1 8 or a-b-3≡ 5 8, so a-b-3 is not of the form (<ref>). We write: 
 
    A=a-b-3     0 
     0     c-b+2+(b-6) 1     1 
     1     1+3 
     23     2.

Under our assumption, we can write each a-b-3, c-b+2 and b-6 as sums of at most three squares by Lemma <ref>, so the integer completely positive rank of A is at most 3+3+3+1=10. The case, when  c-b ≢7 8 can be dealt with in a similar way. 
 
 Now we assume that a-b ≡ 7 8 and c-b ≡ 7 8. We write: 
 
    A=a-b-1     0 
     0     c-b+2+(b-2) 1     1 
     1     1+1 
     21     2.

 Since a-b-1 ≡ 6 8 it is not of the form (<ref>), and c-b+2 and b-2 are not of the form (<ref>) by Lemma <ref>, the integer completely positive rank of A is at most 3+3+3+1=10. 
  

Next example shows that the integer cp-rank of a 2 × 2 matrix can be as high as 9, but we were not able to find examples of 2 × 2 matrices with cp-rank larger than that. 


Let 
    A=a     1 
     1     c,
 where a and c are positive integers. Then any integer cp-factorization of A must involve 1 
 11     1, so the integer cp-rank of A is 1+p+q, where p, q are the least number of squares of integers needed to represent a-1, c-1, respectively. In particular, A has the integer cp-rank 9 if a and c are both divisible by 8.    

    

Let 
    B=a     2 
     2    c

with integers c ≥ a ≥ 2. The decomposition 

    B=a-2     0 
     0     c-2+2 1     1 
     1     1

shows that the integer cp-rank of B is at most 4+3+1=8, unless both a-2 and c-2 are of the form (<ref>). But if a-2 is of the form (<ref>) a-4 is not, by Lemma <ref>. In this case the decomposition 

    B=a-4     0 
     0     c-1+2 
     12    1

shows that the integer cp-rank of B is at most 3+4+1=8. We conclude that the integer cp-rank of all such B is at most 8. 
 

plain






