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
  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 base ring of ``A`` cannot be the Symbolic Ring'
  58         raise ValueError.new(msg)
  59
  60     # First make sure that ``A`` is symmetric.
  61     if not A.is_symmetric():
  62         return False
  63
  64     # Check that all of the entries of ``A`` are nonnegative.
  65     if not all([ a >= 0 for a in A.list() ]):
  66         return False
  67
  68     # If ``A`` is symmetric and non-negative, we only need to check
  69     # that it is positive semidefinite. For that we can consult its
  70     # minimum eigenvalue, which should be zero or greater. Since ``A``
  71     # is symmetric, its eigenvalues are guaranteed to be real.
  72     return min(A.eigenvalues()) >= 0
  73
  74
  75
  76 def is_extreme_doubly_nonnegative(A):
  77     """
  78     Returns ``True`` if the given matrix is an extreme matrix of the
  79     doubly-nonnegative cone, and ``False`` otherwise.
  80     """
  81     raise NotImplementedError()