mjo/cone/doubly_nonnegative.py

   1 """
   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 # 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
  18 # resolve.
  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
  24
  25
  26 def is_doubly_nonnegative(A):
  27     """
  28     Determine whether or not the matrix ``A`` is doubly-nonnegative.
  29
  30     INPUT:
  31
  32     - ``A`` - The matrix in question
  33
  34     OUTPUT:
  35
  36     Either ``True`` if ``A`` is doubly-nonnegative, or ``False``
  37     otherwise.
  38
  39     SETUP::
  40
  41         sage: from mjo.cone.doubly_nonnegative import is_doubly_nonnegative
  42
  43     EXAMPLES:
  44
  45     Every completely positive matrix is doubly-nonnegative::
  46
  47         sage: v = vector(map(abs, random_vector(ZZ, 10)))
  48         sage: A = v.column() * v.row()
  49         sage: is_doubly_nonnegative(A)
  50         True
  51
  52     The following matrix is nonnegative but non positive semidefinite::
  53
  54         sage: A = matrix(ZZ, [[1, 2], [2, 1]])
  55         sage: is_doubly_nonnegative(A)
  56         False
  57
  58     """
  59
  60     if A.base_ring() == SR:
  61         msg = 'The matrix ``A`` cannot be the symbolic.'
  62         raise ValueError.new(msg)
  63
  64     # Check that all of the entries of ``A`` are nonnegative.
  65     if not all([ a >= 0 for a in A.list() ]):
  66         return False
  67
  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)
  71
  72
  73
  74 def is_admissible_extreme_rank(r, n):
  75     """
  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.
  79
  80     INPUT:
  81
  82     - ``r`` - The rank of the matrix.
  83
  84     - ``n`` - The dimension of the vector space on which the matrix acts.
  85
  86     OUTPUT:
  87
  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``
  90     otherwise.
  91
  92     SETUP::
  93
  94         sage: from mjo.cone.doubly_nonnegative import is_admissible_extreme_rank
  95
  96     EXAMPLES:
  97
  98     For dimension 5, only ranks zero, one, and three are admissible::
  99
 100         sage: is_admissible_extreme_rank(0,5)
 101         True
 102         sage: is_admissible_extreme_rank(1,5)
 103         True
 104         sage: is_admissible_extreme_rank(2,5)
 105         False
 106         sage: is_admissible_extreme_rank(3,5)
 107         True
 108         sage: is_admissible_extreme_rank(4,5)
 109         False
 110         sage: is_admissible_extreme_rank(5,5)
 111         False
 112
 113     When given an impossible rank, we just return false::
 114
 115         sage: is_admissible_extreme_rank(100,5)
 116         False
 117
 118     """
 119     if r == 0:
 120         # Zero is in the doubly-nonnegative cone.
 121         return True
 122
 123     if r > n:
 124         # Impossible, just return False
 125         return False
 126
 127     # See Theorem 3.1 in the cited reference.
 128     if r == 2:
 129         return False
 130
 131     if n.mod(2) == 0:
 132         # n is even
 133         return r <= max(1, n-3)
 134     else:
 135         # n is odd
 136         return r <= max(1, n-2)
 137
 138
 139 def has_admissible_extreme_rank(A):
 140     """
 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.
 144
 145     INPUT:
 146
 147     - ``A`` - The matrix in question
 148
 149     OUTPUT:
 150
 151     ``False`` if the rank of ``A`` precludes it from being an extreme
 152     matrix of the doubly-nonnegative cone, ``True`` otherwise.
 153
 154     REFERENCE:
 155
 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.
 160
 161     SETUP::
 162
 163         sage: from mjo.cone.doubly_nonnegative import has_admissible_extreme_rank
 164
 165     EXAMPLES:
 166
 167     The zero matrix has rank zero, which is admissible::
 168
 169         sage: A = zero_matrix(QQ, 5, 5)
 170         sage: has_admissible_extreme_rank(A)
 171         True
 172
 173     Likewise, rank one is admissible for dimension 5::
 174
 175         sage: v = vector(QQ, [1,2,3,4,5])
 176         sage: A = v.column()*v.row()
 177         sage: has_admissible_extreme_rank(A)
 178         True
 179
 180     But rank 2 is never admissible::
 181
 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)
 186         False
 187
 188     In dimension 5, three is the only other admissible rank::
 189
 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)
 197         True
 198
 199     """
 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.')
 204
 205     r = rank(A)
 206     n = ZZ(A.nrows()) # Columns would work, too, since ``A`` is symmetric.
 207
 208     return is_admissible_extreme_rank(r,n)
 209
 210
 211 def stdE(matrix_space, i,j):
 212     """
 213     Return the ``i``,``j``th element of the standard basis in
 214     ``matrix_space``.
 215
 216     INPUT:
 217
 218     - ``matrix_space`` - The underlying matrix space of whose basis
 219                          the returned matrix is an element
 220
 221     - ``i`` - The row index of the single nonzero entry
 222
 223     - ``j`` - The column index of the single nonzero entry
 224
 225     OUTPUT:
 226
 227     A basis element of ``matrix_space``. It has a single \"1\" in the
 228     ``i``,``j`` row,column and zeros elsewhere.
 229
 230     SETUP::
 231
 232         sage: from mjo.cone.doubly_nonnegative import stdE
 233
 234     EXAMPLES::
 235
 236         sage: M = MatrixSpace(ZZ, 2, 2)
 237         sage: stdE(M,0,0)
 238         [1 0]
 239         [0 0]
 240         sage: stdE(M,0,1)
 241         [0 1]
 242         [0 0]
 243         sage: stdE(M,1,0)
 244         [0 0]
 245         [1 0]
 246         sage: stdE(M,1,1)
 247         [0 0]
 248         [0 1]
 249         sage: stdE(M,2,1)
 250         Traceback (most recent call last):
 251         ...
 252         IndexError: Index `i` is out of bounds.
 253         sage: stdE(M,1,2)
 254         Traceback (most recent call last):
 255         ...
 256         IndexError: Index `j` is out of bounds.
 257
 258     """
 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.')
 264
 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]
 273
 274
 275
 276 def is_extreme_doubly_nonnegative(A):
 277     """
 278     Returns ``True`` if the given matrix is an extreme matrix of the
 279     doubly-nonnegative cone, and ``False`` otherwise.
 280
 281     REFERENCES:
 282
 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.
 287
 288     2. Berman, Abraham and Shaked-Monderer, Naomi. Completely Positive
 289        Matrices. World Scientific, 2003.
 290
 291     SETUP::
 292
 293         sage: from mjo.cone.doubly_nonnegative import is_extreme_doubly_nonnegative
 294
 295     EXAMPLES:
 296
 297     The zero matrix is an extreme matrix::
 298
 299         sage: A = zero_matrix(QQ, 5, 5)
 300         sage: is_extreme_doubly_nonnegative(A)
 301         True
 302
 303     Any extreme vector of the completely positive cone is an extreme
 304     vector of the doubly-nonnegative cone::
 305
 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)
 310         True
 311
 312     We should be able to generate the extreme completely positive
 313     vectors randomly::
 314
 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)
 319         True
 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)
 324         True
 325
 326     The following matrix is completely positive but has rank 3, so by a
 327     remark in reference #1 it is not extreme::
 328
 329         sage: A = matrix(QQ, [[1,2,1],[2,6,3],[1,3,5]])
 330         sage: is_extreme_doubly_nonnegative(A)
 331         False
 332
 333     The following matrix is completely positive (diagonal) with rank 2,
 334     so it is also not extreme::
 335
 336         sage: A = matrix(QQ, [[1,0,0],[2,0,0],[0,0,0]])
 337         sage: is_extreme_doubly_nonnegative(A)
 338         False
 339
 340     """
 341
 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)
 345
 346     if not A.base_ring().is_field():
 347         raise ValueError('The base ring of ``A`` must be a field.')
 348
 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())
 353
 354     # Step 1 (see reference #1)
 355     k = A.rank()
 356
 357     if k == 0:
 358         # Short circuit, we know the zero matrix is extreme.
 359         return True
 360
 361     if not is_symmetric_psd(A):
 362         return False
 363
 364     # Step 1.5, appeal to Theorem 3.1 in reference #1 to short
 365     # circuit.
 366     if not has_admissible_extreme_rank(A):
 367         return False
 368
 369     # Step 2
 370     X = factor_psd(A)
 371
 372     # Step 3
 373     #
 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
 376     # `$A_{ij} = 0$`.
 377     spanning_set = []
 378     for j in range(0, A.ncols()):
 379         for i in range(0,j):
 380             if A[i,j] == 0:
 381                 M = A.matrix_space()
 382                 S = X.transpose() * (stdE(M,i,j) + stdE(M,j,i)) * X
 383                 spanning_set.append(S)
 384
 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)
 392
 393     V = span(vectors, A.base_ring())
 394     d = V.dimension()
 395
 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
 398     # earlier.
 399     two = A.base_ring()(2)
 400     return d == (k*(k + 1)/two - 1)
 401
 402
 403 def random_doubly_nonnegative(V, accept_zero=True, rank=None):
 404     """
 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``.
 408
 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
 411     cone.
 412
 413     INPUT:
 414
 415     - ``V`` - The vector space on which the returned matrix will act.
 416
 417     - ``accept_zero`` - Do you want to accept the zero matrix (which
 418                         is doubly nonnegative)? Default to ``True``.
 419
 420     - ``rank`` - Require the returned matrix to have the given rank
 421                  (optional).
 422
 423     OUTPUT:
 424
 425     A random doubly nonnegative matrix, i.e. a linear transformation
 426     from ``V`` to itself.
 427
 428     SETUP::
 429
 430         sage: from mjo.cone.doubly_nonnegative import (is_doubly_nonnegative,
 431         ....:                                          random_doubly_nonnegative)
 432
 433     EXAMPLES:
 434
 435     Well, it doesn't crash at least::
 436
 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)
 442         True
 443
 444     A matrix with the desired rank is returned::
 445
 446         sage: V = VectorSpace(QQ, 5)
 447         sage: A = random_doubly_nonnegative(V,False,1)
 448         sage: A.rank()
 449         1
 450         sage: A = random_doubly_nonnegative(V,False,2)
 451         sage: A.rank()
 452         2
 453         sage: A = random_doubly_nonnegative(V,False,3)
 454         sage: A.rank()
 455         3
 456         sage: A = random_doubly_nonnegative(V,False,4)
 457         sage: A.rank()
 458         4
 459         sage: A = random_doubly_nonnegative(V,False,5)
 460         sage: A.rank()
 461         5
 462
 463     """
 464
 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)
 468
 469     while not all([ x >= 0 for x in A.list() ]):
 470         A = random_psd(V, accept_zero, rank)
 471
 472     return A
 473
 474
 475
 476 def random_extreme_doubly_nonnegative(V, accept_zero=True, rank=None):
 477     """
 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``.
 481
 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
 484     cone.
 485
 486     INPUT:
 487
 488     - ``V`` - The vector space on which the returned matrix will act.
 489
 490     - ``accept_zero`` - Do you want to accept the zero matrix
 491                         (which is extreme)? Defaults to ``True``.
 492
 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.
 497
 498     OUTPUT:
 499
 500     A random extreme doubly nonnegative matrix, i.e. a linear
 501     transformation from ``V`` to itself.
 502
 503     SETUP::
 504
 505         sage: from mjo.cone.doubly_nonnegative import (is_extreme_doubly_nonnegative,
 506         ....:                                          random_extreme_doubly_nonnegative)
 507
 508     EXAMPLES:
 509
 510     Well, it doesn't crash at least::
 511
 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)
 517         True
 518
 519     Rank 2 is never allowed, so we expect an error::
 520
 521         sage: V = VectorSpace(QQ, 5)
 522         sage: A = random_extreme_doubly_nonnegative(V, False, 2)
 523         Traceback (most recent call last):
 524         ...
 525         ValueError: Rank 2 not possible in dimension 5.
 526
 527     Rank 4 is not allowed in dimension 5::
 528
 529         sage: V = VectorSpace(QQ, 5)
 530         sage: A = random_extreme_doubly_nonnegative(V, False, 4)
 531         Traceback (most recent call last):
 532         ...
 533         ValueError: Rank 4 not possible in dimension 5.
 534
 535     """
 536
 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()))
 540
 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)
 544
 545     while not is_extreme_doubly_nonnegative(A):
 546         A = random_doubly_nonnegative(V, accept_zero, rank)
 547
 548     return A