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 "mjo.cone"
  18 # resolves.
  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
  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 is_extreme_doubly_nonnegative(A):
 126     """
 127     Returns ``True`` if the given matrix is an extreme matrix of the
 128     doubly-nonnegative cone, and ``False`` otherwise.
 129
 130     EXAMPLES:
 131
 132     The zero matrix is an extreme matrix::
 133
 134         sage: A = zero_matrix(QQ, 5, 5)
 135         sage: is_extreme_doubly_nonnegative(A)
 136         True
 137
 138     """
 139
 140     r = A.rank()
 141
 142     if r == 0:
 143         # Short circuit, we know the zero matrix is extreme.
 144         return True
 145
 146     if not is_admissible_extreme_rank(r):
 147         return False
 148
 149     raise NotImplementedError()