mjo/cone/doubly_nonnegative.py

   1 """
   2 The doubly-nonnegative cone in `S^{n}` is the set of all such matrices
   3 that both,
   4
   5   a) are positive semidefinite
   6
   7   b) have only nonnegative entries
   8
   9 It is represented typically by either `\mathcal{D}^{n}` or
  10 `\mathcal{DNN}`.
  11
  12 """
  13
  14 from sage.all import *
  15
  16 # Sage doesn't load ~/.sage/init.sage during testing (sage -t), so we
  17 # have to explicitly mangle our sitedir here so that our module names
  18 # resolve.
  19 from os.path import abspath
  20 from site import addsitedir
  21 addsitedir(abspath('../../'))
  22 from mjo.cone.symmetric_psd import factor_psd, is_symmetric_psd
  23 from mjo.matrix_vector import isomorphism
  24
  25
  26 def is_doubly_nonnegative(A):
  27     """
  28     Determine whether or not the matrix ``A`` is doubly-nonnegative.
  29
  30     INPUT:
  31
  32     - ``A`` - The matrix in question
  33
  34     OUTPUT:
  35
  36     Either ``True`` if ``A`` is doubly-nonnegative, or ``False``
  37     otherwise.
  38
  39     EXAMPLES:
  40
  41     Every completely positive matrix is doubly-nonnegative::
  42
  43         sage: v = vector(map(abs, random_vector(ZZ, 10)))
  44         sage: A = v.column() * v.row()
  45         sage: is_doubly_nonnegative(A)
  46         True
  47
  48     The following matrix is nonnegative but non positive semidefinite::
  49
  50         sage: A = matrix(ZZ, [[1, 2], [2, 1]])
  51         sage: is_doubly_nonnegative(A)
  52         False
  53
  54     """
  55
  56     if A.base_ring() == SR:
  57         msg = 'The matrix ``A`` cannot be the symbolic.'
  58         raise ValueError.new(msg)
  59
  60     # Check that all of the entries of ``A`` are nonnegative.
  61     if not all([ a >= 0 for a in A.list() ]):
  62         return False
  63
  64     # It's nonnegative, so all we need to do is check that it's
  65     # symmetric positive-semidefinite.
  66     return is_symmetric_psd(A)
  67
  68
  69
  70 def has_admissible_extreme_rank(A):
  71     """
  72     The extreme matrices of the doubly-nonnegative cone have some
  73     restrictions on their ranks. This function checks to see whether or
  74     not ``A`` could be extreme based on its rank.
  75
  76     INPUT:
  77
  78     - ``A`` - The matrix in question
  79
  80     OUTPUT:
  81
  82     ``False`` if the rank of ``A`` precludes it from being an extreme
  83     matrix of the doubly-nonnegative cone, ``True`` otherwise.
  84
  85     REFERENCE:
  86
  87     Hamilton-Jester, Crista Lee; Li, Chi-Kwong. Extreme Vectors of
  88     Doubly Nonnegative Matrices. Rocky Mountain Journal of Mathematics
  89     26 (1996), no. 4, 1371--1383. doi:10.1216/rmjm/1181071993.
  90     http://projecteuclid.org/euclid.rmjm/1181071993.
  91
  92     EXAMPLES:
  93
  94     The zero matrix has rank zero, which is admissible::
  95
  96     sage: A = zero_matrix(QQ, 5, 5)
  97     sage: has_admissible_extreme_rank(A)
  98     True
  99
 100     """
 101     if not A.is_symmetric():
 102         # This function is more or less internal, so blow up if passed
 103         # something unexpected.
 104         raise ValueError('The matrix ``A`` must be symmetric.')
 105
 106     r = rank(A)
 107     n = ZZ(A.nrows()) # Columns would work, too, since ``A`` is symmetric.
 108
 109     if r == 0:
 110         # Zero is in the doubly-nonnegative cone.
 111         return True
 112
 113     # See Theorem 3.1 in the cited reference.
 114     if r == 2:
 115         return False
 116
 117     if n.mod(2) == 0:
 118         # n is even
 119         return r <= max(1, n-3)
 120     else:
 121         # n is odd
 122         return r <= max(1, n-2)
 123
 124
 125 def E(matrix_space, i,j):
 126     """
 127     Return the ``i``,``j``th element of the standard basis in
 128     ``matrix_space``.
 129
 130     INPUT:
 131
 132     - ``matrix_space`` - The underlying matrix space of whose basis
 133                          the returned matrix is an element
 134
 135     - ``i`` - The row index of the single nonzero entry
 136
 137     - ``j`` - The column index of the single nonzero entry
 138
 139     OUTPUT:
 140
 141     A basis element of ``matrix_space``. It has a single \"1\" in the
 142     ``i``,``j`` row,column and zeros elsewhere.
 143
 144     EXAMPLES::
 145
 146         sage: M = MatrixSpace(ZZ, 2, 2)
 147         sage: E(M,0,0)
 148         [1 0]
 149         [0 0]
 150         sage: E(M,0,1)
 151         [0 1]
 152         [0 0]
 153         sage: E(M,1,0)
 154         [0 0]
 155         [1 0]
 156         sage: E(M,1,1)
 157         [0 0]
 158         [0 1]
 159         sage: E(M,2,1)
 160         Traceback (most recent call last):
 161         ...
 162         IndexError: Index `i` is out of bounds.
 163         sage: E(M,1,2)
 164         Traceback (most recent call last):
 165         ...
 166         IndexError: Index `j` is out of bounds.
 167
 168     """
 169     # We need to check these ourselves, see below.
 170     if i >= matrix_space.nrows():
 171         raise IndexError('Index `i` is out of bounds.')
 172     if j >= matrix_space.ncols():
 173         raise IndexError('Index `j` is out of bounds.')
 174
 175     # The basis here is returned as a one-dimensional list, so we need
 176     # to compute the offset into it based on ``i`` and ``j``. Since we
 177     # compute the index ourselves, we need to do bounds-checking
 178     # manually. Otherwise for e.g. a 2x2 matrix space, the index (0,2)
 179     # would be computed as offset 3 into a four-element list and we
 180     # would succeed incorrectly.
 181     idx = matrix_space.ncols()*i + j
 182     return matrix_space.basis()[idx]
 183
 184
 185
 186 def is_extreme_doubly_nonnegative(A):
 187     """
 188     Returns ``True`` if the given matrix is an extreme matrix of the
 189     doubly-nonnegative cone, and ``False`` otherwise.
 190
 191     REFERENCES:
 192
 193     1. Hamilton-Jester, Crista Lee; Li, Chi-Kwong. Extreme Vectors of
 194        Doubly Nonnegative Matrices. Rocky Mountain Journal of Mathematics
 195        26 (1996), no. 4, 1371--1383. doi:10.1216/rmjm/1181071993.
 196        http://projecteuclid.org/euclid.rmjm/1181071993.
 197
 198     2. Berman, Abraham and Shaked-Monderer, Naomi. Completely Positive
 199        Matrices. World Scientific, 2003.
 200
 201     EXAMPLES:
 202
 203     The zero matrix is an extreme matrix::
 204
 205         sage: A = zero_matrix(QQ, 5, 5)
 206         sage: is_extreme_doubly_nonnegative(A)
 207         True
 208
 209     Any extreme vector of the completely positive cone is an extreme
 210     vector of the doubly-nonnegative cone::
 211
 212         sage: v = vector([1,2,3,4,5,6])
 213         sage: A = v.column() * v.row()
 214         sage: A = A.change_ring(QQ)
 215         sage: is_extreme_doubly_nonnegative(A)
 216         True
 217
 218     We should be able to generate the extreme completely positive
 219     vectors randomly::
 220
 221         sage: v = vector(map(abs, random_vector(ZZ, 4)))
 222         sage: A = v.column() * v.row()
 223         sage: A = A.change_ring(QQ)
 224         sage: is_extreme_doubly_nonnegative(A)
 225         True
 226         sage: v = vector(map(abs, random_vector(ZZ, 10)))
 227         sage: A = v.column() * v.row()
 228         sage: A = A.change_ring(QQ)
 229         sage: is_extreme_doubly_nonnegative(A)
 230         True
 231
 232     The following matrix is completely positive but has rank 3, so by a
 233     remark in reference #1 it is not extreme::
 234
 235         sage: A = matrix(QQ, [[1,2,1],[2,6,3],[1,3,5]])
 236         sage: is_extreme_doubly_nonnegative(A)
 237         False
 238
 239     The following matrix is completely positive (diagonal) with rank 2,
 240     so it is also not extreme::
 241
 242         sage: A = matrix(QQ, [[1,0,0],[2,0,0],[0,0,0]])
 243         sage: is_extreme_doubly_nonnegative(A)
 244         False
 245
 246     """
 247
 248     if not A.base_ring().is_exact() and not A.base_ring() is SR:
 249         msg = 'The base ring of ``A`` must be either exact or symbolic.'
 250         raise ValueError(msg)
 251
 252     if not A.base_ring().is_field():
 253         raise ValueError('The base ring of ``A`` must be a field.')
 254
 255     if not A.base_ring() is SR:
 256         # Change the base field of ``A`` so that we are sure we can take
 257         # roots. The symbolic ring has no algebraic_closure method.
 258         A = A.change_ring(A.base_ring().algebraic_closure())
 259
 260     # Step 1 (see reference #1)
 261     k = A.rank()
 262
 263     if k == 0:
 264         # Short circuit, we know the zero matrix is extreme.
 265         return True
 266
 267     if not is_symmetric_psd(A):
 268         return False
 269
 270     # Step 1.5, appeal to Theorem 3.1 in reference #1 to short
 271     # circuit.
 272     if not has_admissible_extreme_rank(A):
 273         return False
 274
 275     # Step 2
 276     X = factor_psd(A)
 277
 278     # Step 3
 279     #
 280     # Begin with an empty spanning set, and add a new matrix to it
 281     # whenever we come across an index pair `$(i,j)$` with
 282     # `$A_{ij} = 0$`.
 283     spanning_set = []
 284     for j in range(0, A.ncols()):
 285         for i in range(0,j):
 286             if A[i,j] == 0:
 287                 M = A.matrix_space()
 288                 S = X.transpose() * (E(M,i,j) + E(M,j,i)) * X
 289                 spanning_set.append(S)
 290
 291     # The spanning set that we have at this point is of matrices.  We
 292     # only care about the dimension of the spanned space, and Sage
 293     # can't compute the dimension of a set of matrices anyway, so we
 294     # convert them all to vectors and just ask for the dimension of the
 295     # resulting vector space.
 296     (phi, phi_inverse) = isomorphism(A.matrix_space())
 297     vectors = map(phi,spanning_set)
 298
 299     V = span(vectors, A.base_ring())
 300     d = V.dimension()
 301
 302     # Needed to safely divide by two here (we don't want integer
 303     # division). We ensured that the base ring of ``A`` is a field
 304     # earlier.
 305     two = A.base_ring()(2)
 306     return d == (k*(k + 1)/two - 1)