]>
gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/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 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
, random_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 sage: from mjo.cone.doubly_nonnegative import is_doubly_nonnegative
45 Every completely positive matrix is doubly-nonnegative::
47 sage: v = vector(map(abs, random_vector(ZZ, 10)))
48 sage: A = v.column() * v.row()
49 sage: is_doubly_nonnegative(A)
52 The following matrix is nonnegative but non positive semidefinite::
54 sage: A = matrix(ZZ, [[1, 2], [2, 1]])
55 sage: is_doubly_nonnegative(A)
60 if A
.base_ring() == SR
:
61 msg
= 'The matrix ``A`` cannot be the symbolic.'
62 raise ValueError.new(msg
)
64 # Check that all of the entries of ``A`` are nonnegative.
65 if not all([ a
>= 0 for a
in A
.list() ]):
68 # It's nonnegative, so all we need to do is check that it's
69 # symmetric positive-semidefinite.
70 return is_symmetric_psd(A
)
74 def is_admissible_extreme_rank(r
, n
):
76 The extreme matrices of the doubly-nonnegative cone have some
77 restrictions on their ranks. This function checks to see whether the
78 rank ``r`` would be an admissible rank for an ``n``-by-``n`` matrix.
82 - ``r`` - The rank of the matrix.
84 - ``n`` - The dimension of the vector space on which the matrix acts.
88 Either ``True`` if a rank ``r`` matrix could be an extreme vector of
89 the doubly-nonnegative cone in `$\mathbb{R}^{n}$`, or ``False``
94 sage: from mjo.cone.doubly_nonnegative import is_admissible_extreme_rank
98 For dimension 5, only ranks zero, one, and three are admissible::
100 sage: is_admissible_extreme_rank(0,5)
102 sage: is_admissible_extreme_rank(1,5)
104 sage: is_admissible_extreme_rank(2,5)
106 sage: is_admissible_extreme_rank(3,5)
108 sage: is_admissible_extreme_rank(4,5)
110 sage: is_admissible_extreme_rank(5,5)
113 When given an impossible rank, we just return false::
115 sage: is_admissible_extreme_rank(100,5)
120 # Zero is in the doubly-nonnegative cone.
124 # Impossible, just return False
127 # See Theorem 3.1 in the cited reference.
133 return r
<= max(1, n
-3)
136 return r
<= max(1, n
-2)
139 def has_admissible_extreme_rank(A
):
141 The extreme matrices of the doubly-nonnegative cone have some
142 restrictions on their ranks. This function checks to see whether or
143 not ``A`` could be extreme based on its rank.
147 - ``A`` - The matrix in question
151 ``False`` if the rank of ``A`` precludes it from being an extreme
152 matrix of the doubly-nonnegative cone, ``True`` otherwise.
156 Hamilton-Jester, Crista Lee; Li, Chi-Kwong. Extreme Vectors of
157 Doubly Nonnegative Matrices. Rocky Mountain Journal of Mathematics
158 26 (1996), no. 4, 1371--1383. doi:10.1216/rmjm/1181071993.
159 http://projecteuclid.org/euclid.rmjm/1181071993.
163 sage: from mjo.cone.doubly_nonnegative import has_admissible_extreme_rank
167 The zero matrix has rank zero, which is admissible::
169 sage: A = zero_matrix(QQ, 5, 5)
170 sage: has_admissible_extreme_rank(A)
173 Likewise, rank one is admissible for dimension 5::
175 sage: v = vector(QQ, [1,2,3,4,5])
176 sage: A = v.column()*v.row()
177 sage: has_admissible_extreme_rank(A)
180 But rank 2 is never admissible::
182 sage: v1 = vector(QQ, [1,0,0,0,0])
183 sage: v2 = vector(QQ, [0,1,0,0,0])
184 sage: A = v1.column()*v1.row() + v2.column()*v2.row()
185 sage: has_admissible_extreme_rank(A)
188 In dimension 5, three is the only other admissible rank::
190 sage: v1 = vector(QQ, [1,0,0,0,0])
191 sage: v2 = vector(QQ, [0,1,0,0,0])
192 sage: v3 = vector(QQ, [0,0,1,0,0])
193 sage: A = v1.column()*v1.row()
194 sage: A += v2.column()*v2.row()
195 sage: A += v3.column()*v3.row()
196 sage: has_admissible_extreme_rank(A)
200 if not A
.is_symmetric():
201 # This function is more or less internal, so blow up if passed
202 # something unexpected.
203 raise ValueError('The matrix ``A`` must be symmetric.')
206 n
= ZZ(A
.nrows()) # Columns would work, too, since ``A`` is symmetric.
208 return is_admissible_extreme_rank(r
,n
)
211 def stdE(matrix_space
, i
,j
):
213 Return the ``i``,``j``th element of the standard basis in
218 - ``matrix_space`` - The underlying matrix space of whose basis
219 the returned matrix is an element
221 - ``i`` - The row index of the single nonzero entry
223 - ``j`` - The column index of the single nonzero entry
227 A basis element of ``matrix_space``. It has a single \"1\" in the
228 ``i``,``j`` row,column and zeros elsewhere.
232 sage: from mjo.cone.doubly_nonnegative import stdE
236 sage: M = MatrixSpace(ZZ, 2, 2)
250 Traceback (most recent call last):
252 IndexError: Index `i` is out of bounds.
254 Traceback (most recent call last):
256 IndexError: Index `j` is out of bounds.
259 # We need to check these ourselves, see below.
260 if i
>= matrix_space
.nrows():
261 raise IndexError('Index `i` is out of bounds.')
262 if j
>= matrix_space
.ncols():
263 raise IndexError('Index `j` is out of bounds.')
265 # The basis here is returned as a one-dimensional list, so we need
266 # to compute the offset into it based on ``i`` and ``j``. Since we
267 # compute the index ourselves, we need to do bounds-checking
268 # manually. Otherwise for e.g. a 2x2 matrix space, the index (0,2)
269 # would be computed as offset 3 into a four-element list and we
270 # would succeed incorrectly.
271 idx
= matrix_space
.ncols()*i
+ j
272 return list(matrix_space
.basis())[idx
]
276 def is_extreme_doubly_nonnegative(A
):
278 Returns ``True`` if the given matrix is an extreme matrix of the
279 doubly-nonnegative cone, and ``False`` otherwise.
283 1. Hamilton-Jester, Crista Lee; Li, Chi-Kwong. Extreme Vectors of
284 Doubly Nonnegative Matrices. Rocky Mountain Journal of Mathematics
285 26 (1996), no. 4, 1371--1383. doi:10.1216/rmjm/1181071993.
286 http://projecteuclid.org/euclid.rmjm/1181071993.
288 2. Berman, Abraham and Shaked-Monderer, Naomi. Completely Positive
289 Matrices. World Scientific, 2003.
293 sage: from mjo.cone.doubly_nonnegative import is_extreme_doubly_nonnegative
297 The zero matrix is an extreme matrix::
299 sage: A = zero_matrix(QQ, 5, 5)
300 sage: is_extreme_doubly_nonnegative(A)
303 Any extreme vector of the completely positive cone is an extreme
304 vector of the doubly-nonnegative cone::
306 sage: v = vector([1,2,3,4,5,6])
307 sage: A = v.column() * v.row()
308 sage: A = A.change_ring(QQ)
309 sage: is_extreme_doubly_nonnegative(A)
312 We should be able to generate the extreme completely positive
315 sage: v = vector(map(abs, random_vector(ZZ, 4)))
316 sage: A = v.column() * v.row()
317 sage: A = A.change_ring(QQ)
318 sage: is_extreme_doubly_nonnegative(A)
320 sage: v = vector(map(abs, random_vector(ZZ, 10)))
321 sage: A = v.column() * v.row()
322 sage: A = A.change_ring(QQ)
323 sage: is_extreme_doubly_nonnegative(A)
326 The following matrix is completely positive but has rank 3, so by a
327 remark in reference #1 it is not extreme::
329 sage: A = matrix(QQ, [[1,2,1],[2,6,3],[1,3,5]])
330 sage: is_extreme_doubly_nonnegative(A)
333 The following matrix is completely positive (diagonal) with rank 2,
334 so it is also not extreme::
336 sage: A = matrix(QQ, [[1,0,0],[2,0,0],[0,0,0]])
337 sage: is_extreme_doubly_nonnegative(A)
342 if not A
.base_ring().is_exact() and not A
.base_ring() is SR
:
343 msg
= 'The base ring of ``A`` must be either exact or symbolic.'
344 raise ValueError(msg
)
346 if not A
.base_ring().is_field():
347 raise ValueError('The base ring of ``A`` must be a field.')
349 if not A
.base_ring() is SR
:
350 # Change the base field of ``A`` so that we are sure we can take
351 # roots. The symbolic ring has no algebraic_closure method.
352 A
= A
.change_ring(A
.base_ring().algebraic_closure())
354 # Step 1 (see reference #1)
358 # Short circuit, we know the zero matrix is extreme.
361 if not is_symmetric_psd(A
):
364 # Step 1.5, appeal to Theorem 3.1 in reference #1 to short
366 if not has_admissible_extreme_rank(A
):
374 # Begin with an empty spanning set, and add a new matrix to it
375 # whenever we come across an index pair `$(i,j)$` with
378 for j
in range(0, A
.ncols()):
382 S
= X
.transpose() * (stdE(M
,i
,j
) + stdE(M
,j
,i
)) * X
383 spanning_set
.append(S
)
385 # The spanning set that we have at this point is of matrices. We
386 # only care about the dimension of the spanned space, and Sage
387 # can't compute the dimension of a set of matrices anyway, so we
388 # convert them all to vectors and just ask for the dimension of the
389 # resulting vector space.
390 (phi
, phi_inverse
) = isomorphism(A
.matrix_space())
391 vectors
= map(phi
,spanning_set
)
393 V
= span(vectors
, A
.base_ring())
396 # Needed to safely divide by two here (we don't want integer
397 # division). We ensured that the base ring of ``A`` is a field
399 two
= A
.base_ring()(2)
400 return d
== (k
*(k
+ 1)/two
- 1)
403 def random_doubly_nonnegative(V
, accept_zero
=True, rank
=None):
405 Generate a random doubly nonnegative matrix over the vector
406 space ``V``. That is, the returned matrix will be a linear
407 transformation on ``V``, with the same base ring as ``V``.
409 We take a very loose interpretation of "random," here. Otherwise we
410 would never (for example) choose a matrix on the boundary of the
415 - ``V`` - The vector space on which the returned matrix will act.
417 - ``accept_zero`` - Do you want to accept the zero matrix (which
418 is doubly nonnegative)? Default to ``True``.
420 - ``rank`` - Require the returned matrix to have the given rank
425 A random doubly nonnegative matrix, i.e. a linear transformation
426 from ``V`` to itself.
430 sage: from mjo.cone.doubly_nonnegative import (is_doubly_nonnegative,
431 ....: random_doubly_nonnegative)
435 Well, it doesn't crash at least::
437 sage: V = VectorSpace(QQ, 2)
438 sage: A = random_doubly_nonnegative(V)
439 sage: A.matrix_space()
440 Full MatrixSpace of 2 by 2 dense matrices over Rational Field
441 sage: is_doubly_nonnegative(A)
444 A matrix with the desired rank is returned::
446 sage: V = VectorSpace(QQ, 5)
447 sage: A = random_doubly_nonnegative(V,False,1)
450 sage: A = random_doubly_nonnegative(V,False,2)
453 sage: A = random_doubly_nonnegative(V,False,3)
456 sage: A = random_doubly_nonnegative(V,False,4)
459 sage: A = random_doubly_nonnegative(V,False,5)
465 # Generate random symmetric positive-semidefinite matrices until
466 # one of them is nonnegative, then return that.
467 A
= random_psd(V
, accept_zero
, rank
)
469 while not all([ x
>= 0 for x
in A
.list() ]):
470 A
= random_psd(V
, accept_zero
, rank
)
476 def random_extreme_doubly_nonnegative(V
, accept_zero
=True, rank
=None):
478 Generate a random extreme doubly nonnegative matrix over the
479 vector space ``V``. That is, the returned matrix will be a linear
480 transformation on ``V``, with the same base ring as ``V``.
482 We take a very loose interpretation of "random," here. Otherwise we
483 would never (for example) choose a matrix on the boundary of the
488 - ``V`` - The vector space on which the returned matrix will act.
490 - ``accept_zero`` - Do you want to accept the zero matrix
491 (which is extreme)? Defaults to ``True``.
493 - ``rank`` - Require the returned matrix to have the given rank
494 (optional). WARNING: certain ranks are not possible
495 in any given dimension! If an impossible rank is
496 requested, a ValueError will be raised.
500 A random extreme doubly nonnegative matrix, i.e. a linear
501 transformation from ``V`` to itself.
505 sage: from mjo.cone.doubly_nonnegative import (is_extreme_doubly_nonnegative,
506 ....: random_extreme_doubly_nonnegative)
510 Well, it doesn't crash at least::
512 sage: V = VectorSpace(QQ, 2)
513 sage: A = random_extreme_doubly_nonnegative(V)
514 sage: A.matrix_space()
515 Full MatrixSpace of 2 by 2 dense matrices over Rational Field
516 sage: is_extreme_doubly_nonnegative(A)
519 Rank 2 is never allowed, so we expect an error::
521 sage: V = VectorSpace(QQ, 5)
522 sage: A = random_extreme_doubly_nonnegative(V, False, 2)
523 Traceback (most recent call last):
525 ValueError: Rank 2 not possible in dimension 5.
527 Rank 4 is not allowed in dimension 5::
529 sage: V = VectorSpace(QQ, 5)
530 sage: A = random_extreme_doubly_nonnegative(V, False, 4)
531 Traceback (most recent call last):
533 ValueError: Rank 4 not possible in dimension 5.
537 if not is_admissible_extreme_rank(rank
, V
.dimension()):
538 msg
= 'Rank %d not possible in dimension %d.'
539 raise ValueError(msg
% (rank
, V
.dimension()))
541 # Generate random doubly-nonnegative matrices until
542 # one of them is extreme, then return that.
543 A
= random_doubly_nonnegative(V
, accept_zero
, rank
)
545 while not is_extreme_doubly_nonnegative(A
):
546 A
= random_doubly_nonnegative(V
, accept_zero
, rank
)