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