mjo/cone/completely_positive.py

   1 """
   2 The completely positive cone `$\mathcal{K}$` over `\mathbb{R}^{n}$` is
   3 the set of all matrices `$A$`of the form `$\sum uu^{T}$` for `$u \in
   4 \mathbb{R}^{n}_{+}$`. Equivalently, `$A = XX{T}$` where all entries of
   5 `$X$` are nonnegative.
   6 """
   7
   8 # Sage doesn't load ~/.sage/init.sage during testing (sage -t), so we
   9 # have to explicitly mangle our sitedir here so that "mjo.cone"
  10 # resolves.
  11 from os.path import abspath
  12 from site import addsitedir
  13 addsitedir(abspath('../../'))
  14 from mjo.cone.symmetric_psd import factor_psd, is_symmetric_psd
  15
  16
  17 def is_completely_positive(A):
  18     """
  19     Determine whether or not the matrix ``A`` is completely positive.
  20
  21     INPUT:
  22
  23       - ``A`` - The matrix in question
  24
  25     OUTPUT:
  26
  27     Either ``True`` if ``A`` is completely positive, or ``False``
  28     otherwise.
  29
  30     EXAMPLES:
  31
  32     Generate an extreme completely positive matrix and check that we
  33     identify it correctly::
  34
  35         sage: v = vector(map(abs, random_vector(ZZ, 10)))
  36         sage: A = v.column() * v.row()
  37         sage: A = A.change_ring(QQ)
  38         sage: is_completely_positive(A)
  39         True
  40
  41     The following matrix isn't positive semidefinite, so it can't be
  42     completely positive::
  43
  44         sage: A = matrix(QQ, [[1, 2], [2, 1]])
  45         sage: is_completely_positive(A)
  46         False
  47
  48     This matrix isn't even symmetric, so it can't be completely
  49     positive::
  50
  51         sage: A = matrix(QQ, [[1, 2], [3, 4]])
  52         sage: is_completely_positive(A)
  53         False
  54
  55     """
  56
  57     if A.base_ring() == SR:
  58         msg = 'The matrix ``A`` cannot be the symbolic.'
  59         raise ValueError.new(msg)
  60
  61     if not is_symmetric_psd(A):
  62         return False
  63
  64     # Would crash if we hadn't ensured that ``A`` was symmetric
  65     # positive-semidefinite.
  66     X = factor_psd(A)
  67     return X.rank() == 1
  68