+ # Step 2
+ X = factor_psd(A)
+
+ # Step 3
+ #
+ # Begin with an empty spanning set, and add a new matrix to it
+ # whenever we come across an index pair `$(i,j)$` with
+ # `$A_{ij} = 0$`.
+ spanning_set = []
+ for j in range(A.ncols()):
+ for i in range(j):
+ if A[i,j] == 0:
+ M = A.matrix_space()
+ S = X.transpose() * (stdE(M,i,j) + stdE(M,j,i)) * X
+ spanning_set.append(S)
+
+ # The spanning set that we have at this point is of matrices. We
+ # only care about the dimension of the spanned space, and Sage
+ # can't compute the dimension of a set of matrices anyway, so we
+ # convert them all to vectors and just ask for the dimension of the
+ # resulting vector space.
+ (phi, phi_inverse) = basis_repr(A.matrix_space())
+ vectors = map(phi,spanning_set)
+
+ V = span(vectors, A.base_ring())
+ d = V.dimension()
+
+ # Needed to safely divide by two here (we don't want integer
+ # division). We ensured that the base ring of ``A`` is a field
+ # earlier.
+ two = A.base_ring()(2)
+ return d == (k*(k + 1)/two - 1)
+
+
+def random_doubly_nonnegative(V, accept_zero=True, rank=None):
+ """
+ Generate a random doubly nonnegative matrix over the vector
+ space ``V``. That is, the returned matrix will be a linear
+ transformation on ``V``, with the same base ring as ``V``.
+
+ We take a very loose interpretation of "random," here. Otherwise we
+ would never (for example) choose a matrix on the boundary of the
+ cone.
+
+ INPUT:
+
+ - ``V`` - The vector space on which the returned matrix will act.
+
+ - ``accept_zero`` - Do you want to accept the zero matrix (which
+ is doubly nonnegative)? Default to ``True``.
+
+ - ``rank`` - Require the returned matrix to have the given rank
+ (optional).
+
+ OUTPUT:
+
+ A random doubly nonnegative matrix, i.e. a linear transformation
+ from ``V`` to itself.
+
+ SETUP::
+
+ sage: from mjo.cone.doubly_nonnegative import (is_doubly_nonnegative,
+ ....: random_doubly_nonnegative)
+
+ EXAMPLES:
+
+ Well, it doesn't crash at least::
+
+ sage: V = VectorSpace(QQ, 2)
+ sage: A = random_doubly_nonnegative(V)
+ sage: A.matrix_space()
+ Full MatrixSpace of 2 by 2 dense matrices over Rational Field
+ sage: is_doubly_nonnegative(A)
+ True
+
+ A matrix with the desired rank is returned::
+
+ sage: V = VectorSpace(QQ, 5)
+ sage: A = random_doubly_nonnegative(V,False,1)
+ sage: A.rank()
+ 1
+ sage: A = random_doubly_nonnegative(V,False,2)
+ sage: A.rank()
+ 2
+ sage: A = random_doubly_nonnegative(V,False,3)
+ sage: A.rank()
+ 3
+ sage: A = random_doubly_nonnegative(V,False,4)
+ sage: A.rank()
+ 4
+ sage: A = random_doubly_nonnegative(V,False,5)
+ sage: A.rank()
+ 5
+
+ """
+
+ # Generate random symmetric positive-semidefinite matrices until
+ # one of them is nonnegative, then return that.
+ A = random_symmetric_psd(V, accept_zero, rank)
+
+ while not all( x >= 0 for x in A.list() ):
+ A = random_symmetric_psd(V, accept_zero, rank)
+
+ return A
+
+
+
+def random_extreme_doubly_nonnegative(V, accept_zero=True, rank=None):
+ """
+ Generate a random extreme doubly nonnegative matrix over the
+ vector space ``V``. That is, the returned matrix will be a linear
+ transformation on ``V``, with the same base ring as ``V``.
+
+ We take a very loose interpretation of "random," here. Otherwise we
+ would never (for example) choose a matrix on the boundary of the
+ cone.
+
+ INPUT:
+
+ - ``V`` - The vector space on which the returned matrix will act.
+
+ - ``accept_zero`` - Do you want to accept the zero matrix
+ (which is extreme)? Defaults to ``True``.
+
+ - ``rank`` - Require the returned matrix to have the given rank
+ (optional). WARNING: certain ranks are not possible
+ in any given dimension! If an impossible rank is
+ requested, a ValueError will be raised.
+
+ OUTPUT:
+
+ A random extreme doubly nonnegative matrix, i.e. a linear
+ transformation from ``V`` to itself.
+
+ SETUP::
+
+ sage: from mjo.cone.doubly_nonnegative import (is_extreme_doubly_nonnegative,
+ ....: random_extreme_doubly_nonnegative)
+
+ EXAMPLES:
+
+ Well, it doesn't crash at least::
+
+ sage: V = VectorSpace(QQ, 2)
+ sage: A = random_extreme_doubly_nonnegative(V)
+ sage: A.matrix_space()
+ Full MatrixSpace of 2 by 2 dense matrices over Rational Field
+ sage: is_extreme_doubly_nonnegative(A)
+ True
+
+ Rank 2 is never allowed, so we expect an error::
+
+ sage: V = VectorSpace(QQ, 5)
+ sage: A = random_extreme_doubly_nonnegative(V, False, 2)
+ Traceback (most recent call last):
+ ...
+ ValueError: Rank 2 not possible in dimension 5.
+
+ Rank 4 is not allowed in dimension 5::
+
+ sage: V = VectorSpace(QQ, 5)
+ sage: A = random_extreme_doubly_nonnegative(V, False, 4)
+ Traceback (most recent call last):
+ ...
+ ValueError: Rank 4 not possible in dimension 5.
+
+ """
+
+ if rank is not None and not is_admissible_extreme_rank(rank, V.dimension()):
+ msg = 'Rank %d not possible in dimension %d.'
+ raise ValueError(msg % (rank, V.dimension()))
+
+ # Generate random doubly-nonnegative matrices until
+ # one of them is extreme, then return that.
+ A = random_doubly_nonnegative(V, accept_zero, rank)
+
+ while not is_extreme_doubly_nonnegative(A):
+ A = random_doubly_nonnegative(V, accept_zero, rank)
+
+ return A