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