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