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