]>
gitweb.michael.orlitzky.com - sage.d.git/blob - doubly_nonnegative.py
4f7f950bb2c897509c2cb4b41d5200bccfd67c49
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 our module names
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
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 # This function is more or less internal, so blow up if passed
103 # something unexpected.
104 raise ValueError('The matrix ``A`` must be symmetric.')
107 n
= ZZ(A
.nrows()) # Columns would work, too, since ``A`` is symmetric.
110 # Zero is in the doubly-nonnegative cone.
113 # See Theorem 3.1 in the cited reference.
119 return r
<= max(1, n
-3)
122 return r
<= max(1, n
-2)
125 def E(matrix_space
, i
,j
):
127 Return the ``i``,``j``th element of the standard basis in
132 - ``matrix_space`` - The underlying matrix space of whose basis
133 the returned matrix is an element
135 - ``i`` - The row index of the single nonzero entry
137 - ``j`` - The column index of the single nonzero entry
141 A basis element of ``matrix_space``. It has a single \"1\" in the
142 ``i``,``j`` row,column and zeros elsewhere.
146 sage: M = MatrixSpace(ZZ, 2, 2)
160 Traceback (most recent call last):
162 IndexError: Index `i` is out of bounds.
164 Traceback (most recent call last):
166 IndexError: Index `j` is out of bounds.
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.')
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
]
186 def is_extreme_doubly_nonnegative(A
):
188 Returns ``True`` if the given matrix is an extreme matrix of the
189 doubly-nonnegative cone, and ``False`` otherwise.
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.
198 2. Berman, Abraham and Shaked-Monderer, Naomi. Completely Positive
199 Matrices. World Scientific, 2003.
203 The zero matrix is an extreme matrix::
205 sage: A = zero_matrix(QQ, 5, 5)
206 sage: is_extreme_doubly_nonnegative(A)
209 Any extreme vector of the completely positive cone is an extreme
210 vector of the doubly-nonnegative cone::
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)
218 We should be able to generate the extreme completely positive
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)
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)
232 The following matrix is completely positive but has rank 3, so by a
233 remark in reference #1 it is not extreme::
235 sage: A = matrix(QQ, [[1,2,1],[2,6,3],[1,3,5]])
236 sage: is_extreme_doubly_nonnegative(A)
239 The following matrix is completely positive (diagonal) with rank 2,
240 so it is also not extreme::
242 sage: A = matrix(QQ, [[1,0,0],[2,0,0],[0,0,0]])
243 sage: is_extreme_doubly_nonnegative(A)
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
)
252 if not A
.base_ring().is_field():
253 raise ValueError('The base ring of ``A`` must be a field.')
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())
260 # Step 1 (see reference #1)
264 # Short circuit, we know the zero matrix is extreme.
267 if not is_symmetric_psd(A
):
270 # Step 1.5, appeal to Theorem 3.1 in reference #1 to short
272 if not has_admissible_extreme_rank(A
):
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
284 for j
in range(0, A
.ncols()):
288 S
= X
.transpose() * (E(M
,i
,j
) + E(M
,j
,i
)) * X
289 spanning_set
.append(S
)
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
)
299 V
= span(vectors
, A
.base_ring())
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
305 two
= A
.base_ring()(2)
306 return d
== (k
*(k
+ 1)/two
- 1)