]> gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/cone/doubly_nonnegative.py
makefile: add --long to the test command.
[sage.d.git] / mjo / cone / doubly_nonnegative.py
1 r"""
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 from mjo.cone.symmetric_psd import (factor_psd,
17 is_symmetric_psd,
18 random_symmetric_psd)
19 from mjo.basis_repr import basis_repr
20
21
22 def is_doubly_nonnegative(A):
23 """
24 Determine whether or not the matrix ``A`` is doubly-nonnegative.
25
26 INPUT:
27
28 - ``A`` - The matrix in question
29
30 OUTPUT:
31
32 Either ``True`` if ``A`` is doubly-nonnegative, or ``False``
33 otherwise.
34
35 SETUP::
36
37 sage: from mjo.cone.doubly_nonnegative import is_doubly_nonnegative
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 matrix ``A`` cannot be the symbolic.'
58 raise ValueError.new(msg)
59
60 # Check that all of the entries of ``A`` are nonnegative.
61 if not all( a >= 0 for a in A.list() ):
62 return False
63
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)
67
68
69
70 def is_admissible_extreme_rank(r, n):
71 r"""
72 The extreme matrices of the doubly-nonnegative cone have some
73 restrictions on their ranks. This function checks to see whether the
74 rank ``r`` would be an admissible rank for an ``n``-by-``n`` matrix.
75
76 INPUT:
77
78 - ``r`` - The rank of the matrix.
79
80 - ``n`` - The dimension of the vector space on which the matrix acts.
81
82 OUTPUT:
83
84 Either ``True`` if a rank ``r`` matrix could be an extreme vector of
85 the doubly-nonnegative cone in `$\mathbb{R}^{n}$`, or ``False``
86 otherwise.
87
88 SETUP::
89
90 sage: from mjo.cone.doubly_nonnegative import is_admissible_extreme_rank
91
92 EXAMPLES:
93
94 For dimension 5, only ranks zero, one, and three are admissible::
95
96 sage: is_admissible_extreme_rank(0,5)
97 True
98 sage: is_admissible_extreme_rank(1,5)
99 True
100 sage: is_admissible_extreme_rank(2,5)
101 False
102 sage: is_admissible_extreme_rank(3,5)
103 True
104 sage: is_admissible_extreme_rank(4,5)
105 False
106 sage: is_admissible_extreme_rank(5,5)
107 False
108
109 When given an impossible rank, we just return false::
110
111 sage: is_admissible_extreme_rank(100,5)
112 False
113
114 """
115 if r == 0:
116 # Zero is in the doubly-nonnegative cone.
117 return True
118
119 if r > n:
120 # Impossible, just return False
121 return False
122
123 # See Theorem 3.1 in the cited reference.
124 if r == 2:
125 return False
126
127 if n.mod(2) == 0:
128 # n is even
129 return r <= max(1, n-3)
130 else:
131 # n is odd
132 return r <= max(1, n-2)
133
134
135 def has_admissible_extreme_rank(A):
136 """
137 The extreme matrices of the doubly-nonnegative cone have some
138 restrictions on their ranks. This function checks to see whether or
139 not ``A`` could be extreme based on its rank.
140
141 INPUT:
142
143 - ``A`` - The matrix in question
144
145 OUTPUT:
146
147 ``False`` if the rank of ``A`` precludes it from being an extreme
148 matrix of the doubly-nonnegative cone, ``True`` otherwise.
149
150 REFERENCE:
151
152 Hamilton-Jester, Crista Lee; Li, Chi-Kwong. Extreme Vectors of
153 Doubly Nonnegative Matrices. Rocky Mountain Journal of Mathematics
154 26 (1996), no. 4, 1371--1383. doi:10.1216/rmjm/1181071993.
155 http://projecteuclid.org/euclid.rmjm/1181071993.
156
157 SETUP::
158
159 sage: from mjo.cone.doubly_nonnegative import has_admissible_extreme_rank
160
161 EXAMPLES:
162
163 The zero matrix has rank zero, which is admissible::
164
165 sage: A = zero_matrix(QQ, 5, 5)
166 sage: has_admissible_extreme_rank(A)
167 True
168
169 Likewise, rank one is admissible for dimension 5::
170
171 sage: v = vector(QQ, [1,2,3,4,5])
172 sage: A = v.column()*v.row()
173 sage: has_admissible_extreme_rank(A)
174 True
175
176 But rank 2 is never admissible::
177
178 sage: v1 = vector(QQ, [1,0,0,0,0])
179 sage: v2 = vector(QQ, [0,1,0,0,0])
180 sage: A = v1.column()*v1.row() + v2.column()*v2.row()
181 sage: has_admissible_extreme_rank(A)
182 False
183
184 In dimension 5, three is the only other admissible rank::
185
186 sage: v1 = vector(QQ, [1,0,0,0,0])
187 sage: v2 = vector(QQ, [0,1,0,0,0])
188 sage: v3 = vector(QQ, [0,0,1,0,0])
189 sage: A = v1.column()*v1.row()
190 sage: A += v2.column()*v2.row()
191 sage: A += v3.column()*v3.row()
192 sage: has_admissible_extreme_rank(A)
193 True
194
195 """
196 if not A.is_symmetric():
197 # This function is more or less internal, so blow up if passed
198 # something unexpected.
199 raise ValueError('The matrix ``A`` must be symmetric.')
200
201 r = rank(A)
202 n = ZZ(A.nrows()) # Columns would work, too, since ``A`` is symmetric.
203
204 return is_admissible_extreme_rank(r,n)
205
206
207 def stdE(matrix_space, i,j):
208 """
209 Return the ``i``,``j``th element of the standard basis in
210 ``matrix_space``.
211
212 INPUT:
213
214 - ``matrix_space`` - The underlying matrix space of whose basis
215 the returned matrix is an element
216
217 - ``i`` - The row index of the single nonzero entry
218
219 - ``j`` - The column index of the single nonzero entry
220
221 OUTPUT:
222
223 A basis element of ``matrix_space``. It has a single \"1\" in the
224 ``i``,``j`` row,column and zeros elsewhere.
225
226 SETUP::
227
228 sage: from mjo.cone.doubly_nonnegative import stdE
229
230 EXAMPLES::
231
232 sage: M = MatrixSpace(ZZ, 2, 2)
233 sage: stdE(M,0,0)
234 [1 0]
235 [0 0]
236 sage: stdE(M,0,1)
237 [0 1]
238 [0 0]
239 sage: stdE(M,1,0)
240 [0 0]
241 [1 0]
242 sage: stdE(M,1,1)
243 [0 0]
244 [0 1]
245 sage: stdE(M,2,1)
246 Traceback (most recent call last):
247 ...
248 IndexError: Index `i` is out of bounds.
249 sage: stdE(M,1,2)
250 Traceback (most recent call last):
251 ...
252 IndexError: Index `j` is out of bounds.
253
254 """
255 # We need to check these ourselves, see below.
256 if i >= matrix_space.nrows():
257 raise IndexError('Index `i` is out of bounds.')
258 if j >= matrix_space.ncols():
259 raise IndexError('Index `j` is out of bounds.')
260
261 # The basis here is returned as a one-dimensional list, so we need
262 # to compute the offset into it based on ``i`` and ``j``. Since we
263 # compute the index ourselves, we need to do bounds-checking
264 # manually. Otherwise for e.g. a 2x2 matrix space, the index (0,2)
265 # would be computed as offset 3 into a four-element list and we
266 # would succeed incorrectly.
267 idx = matrix_space.ncols()*i + j
268 return list(matrix_space.basis())[idx]
269
270
271
272 def is_extreme_doubly_nonnegative(A):
273 """
274 Returns ``True`` if the given matrix is an extreme matrix of the
275 doubly-nonnegative cone, and ``False`` otherwise.
276
277 REFERENCES:
278
279 1. Hamilton-Jester, Crista Lee; Li, Chi-Kwong. Extreme Vectors of
280 Doubly Nonnegative Matrices. Rocky Mountain Journal of Mathematics
281 26 (1996), no. 4, 1371--1383. doi:10.1216/rmjm/1181071993.
282 http://projecteuclid.org/euclid.rmjm/1181071993.
283
284 2. Berman, Abraham and Shaked-Monderer, Naomi. Completely Positive
285 Matrices. World Scientific, 2003.
286
287 SETUP::
288
289 sage: from mjo.cone.doubly_nonnegative import is_extreme_doubly_nonnegative
290
291 EXAMPLES:
292
293 The zero matrix is an extreme matrix::
294
295 sage: A = zero_matrix(QQ, 5, 5)
296 sage: is_extreme_doubly_nonnegative(A)
297 True
298
299 Any extreme vector of the completely positive cone is an extreme
300 vector of the doubly-nonnegative cone::
301
302 sage: v = vector([1,2,3,4,5,6])
303 sage: A = v.column() * v.row()
304 sage: A = A.change_ring(QQ)
305 sage: is_extreme_doubly_nonnegative(A)
306 True
307
308 We should be able to generate the extreme completely positive
309 vectors randomly::
310
311 sage: v = vector(map(abs, random_vector(ZZ, 4)))
312 sage: A = v.column() * v.row()
313 sage: A = A.change_ring(QQ)
314 sage: is_extreme_doubly_nonnegative(A)
315 True
316 sage: v = vector(map(abs, random_vector(ZZ, 10)))
317 sage: A = v.column() * v.row()
318 sage: A = A.change_ring(QQ)
319 sage: is_extreme_doubly_nonnegative(A)
320 True
321
322 The following matrix is completely positive but has rank 3, so by a
323 remark in reference #1 it is not extreme::
324
325 sage: A = matrix(QQ, [[1,2,1],[2,6,3],[1,3,5]])
326 sage: is_extreme_doubly_nonnegative(A)
327 False
328
329 The following matrix is completely positive (diagonal) with rank 2,
330 so it is also not extreme::
331
332 sage: A = matrix(QQ, [[1,0,0],[2,0,0],[0,0,0]])
333 sage: is_extreme_doubly_nonnegative(A)
334 False
335
336 """
337
338 if not A.base_ring().is_exact() and not A.base_ring() is SR:
339 msg = 'The base ring of ``A`` must be either exact or symbolic.'
340 raise ValueError(msg)
341
342 if not A.base_ring().is_field():
343 raise ValueError('The base ring of ``A`` must be a field.')
344
345 if not A.base_ring() is SR:
346 # Change the base field of ``A`` so that we are sure we can take
347 # roots. The symbolic ring has no algebraic_closure method.
348 A = A.change_ring(A.base_ring().algebraic_closure())
349
350 # Step 1 (see reference #1)
351 k = A.rank()
352
353 if k == 0:
354 # Short circuit, we know the zero matrix is extreme.
355 return True
356
357 if not is_symmetric_psd(A):
358 return False
359
360 # Step 1.5, appeal to Theorem 3.1 in reference #1 to short
361 # circuit.
362 if not has_admissible_extreme_rank(A):
363 return False
364
365 # Step 2
366 X = factor_psd(A)
367
368 # Step 3
369 #
370 # Begin with an empty spanning set, and add a new matrix to it
371 # whenever we come across an index pair `$(i,j)$` with
372 # `$A_{ij} = 0$`.
373 spanning_set = []
374 for j in range(A.ncols()):
375 for i in range(j):
376 if A[i,j] == 0:
377 M = A.matrix_space()
378 S = X.transpose() * (stdE(M,i,j) + stdE(M,j,i)) * X
379 spanning_set.append(S)
380
381 # The spanning set that we have at this point is of matrices. We
382 # only care about the dimension of the spanned space, and Sage
383 # can't compute the dimension of a set of matrices anyway, so we
384 # convert them all to vectors and just ask for the dimension of the
385 # resulting vector space.
386 (phi, phi_inverse) = basis_repr(A.matrix_space())
387 vectors = map(phi,spanning_set)
388
389 V = span(vectors, A.base_ring())
390 d = V.dimension()
391
392 # Needed to safely divide by two here (we don't want integer
393 # division). We ensured that the base ring of ``A`` is a field
394 # earlier.
395 two = A.base_ring()(2)
396 return d == (k*(k + 1)/two - 1)
397
398
399 def random_doubly_nonnegative(V, accept_zero=True, rank=None):
400 """
401 Generate a random doubly nonnegative matrix over the vector
402 space ``V``. That is, the returned matrix will be a linear
403 transformation on ``V``, with the same base ring as ``V``.
404
405 We take a very loose interpretation of "random," here. Otherwise we
406 would never (for example) choose a matrix on the boundary of the
407 cone.
408
409 INPUT:
410
411 - ``V`` - The vector space on which the returned matrix will act.
412
413 - ``accept_zero`` - Do you want to accept the zero matrix (which
414 is doubly nonnegative)? Default to ``True``.
415
416 - ``rank`` - Require the returned matrix to have the given rank
417 (optional).
418
419 OUTPUT:
420
421 A random doubly nonnegative matrix, i.e. a linear transformation
422 from ``V`` to itself.
423
424 SETUP::
425
426 sage: from mjo.cone.doubly_nonnegative import (is_doubly_nonnegative,
427 ....: random_doubly_nonnegative)
428
429 EXAMPLES:
430
431 Well, it doesn't crash at least::
432
433 sage: V = VectorSpace(QQ, 2)
434 sage: A = random_doubly_nonnegative(V)
435 sage: A.matrix_space()
436 Full MatrixSpace of 2 by 2 dense matrices over Rational Field
437 sage: is_doubly_nonnegative(A)
438 True
439
440 A matrix with the desired rank is returned::
441
442 sage: V = VectorSpace(QQ, 5)
443 sage: A = random_doubly_nonnegative(V,False,1)
444 sage: A.rank()
445 1
446 sage: A = random_doubly_nonnegative(V,False,2)
447 sage: A.rank()
448 2
449 sage: A = random_doubly_nonnegative(V,False,3)
450 sage: A.rank()
451 3
452 sage: A = random_doubly_nonnegative(V,False,4)
453 sage: A.rank()
454 4
455 sage: A = random_doubly_nonnegative(V,False,5)
456 sage: A.rank()
457 5
458
459 """
460
461 # Generate random symmetric positive-semidefinite matrices until
462 # one of them is nonnegative, then return that.
463 A = random_symmetric_psd(V, accept_zero, rank)
464
465 while not all( x >= 0 for x in A.list() ):
466 A = random_symmetric_psd(V, accept_zero, rank)
467
468 return A
469
470
471
472 def random_extreme_doubly_nonnegative(V, accept_zero=True, rank=None):
473 """
474 Generate a random extreme doubly nonnegative matrix over the
475 vector space ``V``. That is, the returned matrix will be a linear
476 transformation on ``V``, with the same base ring as ``V``.
477
478 We take a very loose interpretation of "random," here. Otherwise we
479 would never (for example) choose a matrix on the boundary of the
480 cone.
481
482 INPUT:
483
484 - ``V`` - The vector space on which the returned matrix will act.
485
486 - ``accept_zero`` - Do you want to accept the zero matrix
487 (which is extreme)? Defaults to ``True``.
488
489 - ``rank`` - Require the returned matrix to have the given rank
490 (optional). WARNING: certain ranks are not possible
491 in any given dimension! If an impossible rank is
492 requested, a ValueError will be raised.
493
494 OUTPUT:
495
496 A random extreme doubly nonnegative matrix, i.e. a linear
497 transformation from ``V`` to itself.
498
499 SETUP::
500
501 sage: from mjo.cone.doubly_nonnegative import (is_extreme_doubly_nonnegative,
502 ....: random_extreme_doubly_nonnegative)
503
504 EXAMPLES:
505
506 Well, it doesn't crash at least::
507
508 sage: V = VectorSpace(QQ, 2)
509 sage: A = random_extreme_doubly_nonnegative(V)
510 sage: A.matrix_space()
511 Full MatrixSpace of 2 by 2 dense matrices over Rational Field
512 sage: is_extreme_doubly_nonnegative(A)
513 True
514
515 Rank 2 is never allowed, so we expect an error::
516
517 sage: V = VectorSpace(QQ, 5)
518 sage: A = random_extreme_doubly_nonnegative(V, False, 2)
519 Traceback (most recent call last):
520 ...
521 ValueError: Rank 2 not possible in dimension 5.
522
523 Rank 4 is not allowed in dimension 5::
524
525 sage: V = VectorSpace(QQ, 5)
526 sage: A = random_extreme_doubly_nonnegative(V, False, 4)
527 Traceback (most recent call last):
528 ...
529 ValueError: Rank 4 not possible in dimension 5.
530
531 """
532
533 if rank is not None and not is_admissible_extreme_rank(rank, V.dimension()):
534 msg = 'Rank %d not possible in dimension %d.'
535 raise ValueError(msg % (rank, V.dimension()))
536
537 # Generate random doubly-nonnegative matrices until
538 # one of them is extreme, then return that.
539 A = random_doubly_nonnegative(V, accept_zero, rank)
540
541 while not is_extreme_doubly_nonnegative(A):
542 A = random_doubly_nonnegative(V, accept_zero, rank)
543
544 return A