]>
gitweb.michael.orlitzky.com - sage.d.git/blob - cone/doubly_nonnegative.py
2 The doubly-nonnegative cone in `S^{n}` is the set of all such matrices
5 a) are positive semidefinite
7 b) have only nonnegative entries
9 It is represented typically by either `\mathcal{D}^{n}` or
14 from sage
.all
import *
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"
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
26 def is_doubly_nonnegative(A
):
28 Determine whether or not the matrix ``A`` is doubly-nonnegative.
32 - ``A`` - The matrix in question
36 Either ``True`` if ``A`` is doubly-nonnegative, or ``False``
41 Every completely positive matrix is doubly-nonnegative::
43 sage: v = vector(map(abs, random_vector(ZZ, 10)))
44 sage: A = v.column() * v.row()
45 sage: is_doubly_nonnegative(A)
48 The following matrix is nonnegative but non positive semidefinite::
50 sage: A = matrix(ZZ, [[1, 2], [2, 1]])
51 sage: is_doubly_nonnegative(A)
56 if A
.base_ring() == SR
:
57 msg
= 'The matrix ``A`` cannot be the symbolic.'
58 raise ValueError.new(msg
)
60 # Check that all of the entries of ``A`` are nonnegative.
61 if not all([ a
>= 0 for a
in A
.list() ]):
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
)
70 def has_admissible_extreme_rank(A
):
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.
78 - ``A`` - The matrix in question
82 ``False`` if the rank of ``A`` precludes it from being an extreme
83 matrix of the doubly-nonnegative cone, ``True`` otherwise.
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.
94 The zero matrix has rank zero, which is admissible::
96 sage: A = zero_matrix(QQ, 5, 5)
97 sage: has_admissible_extreme_rank(A)
101 if not A
.is_symmetric():
102 raise ValueError('The matrix ``A`` must be symmetric.')
105 n
= A
.nrows() # Columns would work, too, since ``A`` is symmetric.
108 # Zero is in the doubly-nonnegative cone.
111 # See Theorem 3.1 in the cited reference.
117 return r
<= max(1, n
-3)
120 return r
<= max(1, n
-2)
123 def is_extreme_doubly_nonnegative(A
):
125 Returns ``True`` if the given matrix is an extreme matrix of the
126 doubly-nonnegative cone, and ``False`` otherwise.
130 The zero matrix is an extreme matrix::
132 sage: A = zero_matrix(QQ, 5, 5)
133 sage: is_extreme_doubly_nonnegative(A)
141 # Short circuit, we know the zero matrix is extreme.
144 if not is_admissible_extreme_rank(r
):
147 raise NotImplementedError()