-"""
+r"""
The doubly-nonnegative cone in `S^{n}` is the set of all such matrices
that both,
from sage.all import *
-# Sage doesn't load ~/.sage/init.sage during testing (sage -t), so we
-# have to explicitly mangle our sitedir here so that "mjo.cone"
-# resolves.
-from os.path import abspath
-from site import addsitedir
-addsitedir(abspath('../../'))
-from mjo.cone.symmetric_psd import factor_psd
-
+from mjo.cone.symmetric_psd import (factor_psd,
+ random_symmetric_psd)
+from mjo.basis_repr import basis_repr
def is_doubly_nonnegative(A):
INPUT:
- - ``A`` - The matrix in question
+ - ``A`` - The matrix in question
OUTPUT:
Either ``True`` if ``A`` is doubly-nonnegative, or ``False``
otherwise.
+ SETUP::
+
+ sage: from mjo.cone.doubly_nonnegative import is_doubly_nonnegative
+
EXAMPLES:
Every completely positive matrix is doubly-nonnegative::
"""
if A.base_ring() == SR:
- msg = 'The base ring of ``A`` cannot be the Symbolic Ring'
+ msg = 'The matrix ``A`` cannot be the symbolic.'
raise ValueError.new(msg)
- # First make sure that ``A`` is symmetric.
- if not A.is_symmetric():
+ # Check that all of the entries of ``A`` are nonnegative.
+ if not all( a >= 0 for a in A.list() ):
return False
- # Check that all of the entries of ``A`` are nonnegative.
- if not all([ a >= 0 for a in A.list() ]):
+ # It's nonnegative, so all we need to do is check that it's
+ # symmetric positive-semidefinite.
+ return A.is_positive_semidefinite()
+
+
+
+def is_admissible_extreme_rank(r, n):
+ r"""
+ The extreme matrices of the doubly-nonnegative cone have some
+ restrictions on their ranks. This function checks to see whether the
+ rank ``r`` would be an admissible rank for an ``n``-by-``n`` matrix.
+
+ INPUT:
+
+ - ``r`` - The rank of the matrix.
+
+ - ``n`` - The dimension of the vector space on which the matrix acts.
+
+ OUTPUT:
+
+ Either ``True`` if a rank ``r`` matrix could be an extreme vector of
+ the doubly-nonnegative cone in `$\mathbb{R}^{n}$`, or ``False``
+ otherwise.
+
+ SETUP::
+
+ sage: from mjo.cone.doubly_nonnegative import is_admissible_extreme_rank
+
+ EXAMPLES:
+
+ For dimension 5, only ranks zero, one, and three are admissible::
+
+ sage: is_admissible_extreme_rank(0,5)
+ True
+ sage: is_admissible_extreme_rank(1,5)
+ True
+ sage: is_admissible_extreme_rank(2,5)
+ False
+ sage: is_admissible_extreme_rank(3,5)
+ True
+ sage: is_admissible_extreme_rank(4,5)
+ False
+ sage: is_admissible_extreme_rank(5,5)
+ False
+
+ When given an impossible rank, we just return false::
+
+ sage: is_admissible_extreme_rank(100,5)
+ False
+
+ """
+ if r == 0:
+ # Zero is in the doubly-nonnegative cone.
+ return True
+
+ if r > n:
+ # Impossible, just return False
return False
- # If ``A`` is symmetric and non-negative, we only need to check
- # that it is positive semidefinite. For that we can consult its
- # minimum eigenvalue, which should be zero or greater. Since ``A``
- # is symmetric, its eigenvalues are guaranteed to be real.
- return min(A.eigenvalues()) >= 0
+ # See Theorem 3.1 in the cited reference.
+ if r == 2:
+ return False
+
+ if n.mod(2) == 0:
+ # n is even
+ return r <= max(1, n-3)
+ else:
+ # n is odd
+ return r <= max(1, n-2)
+
+
+def has_admissible_extreme_rank(A):
+ """
+ The extreme matrices of the doubly-nonnegative cone have some
+ restrictions on their ranks. This function checks to see whether or
+ not ``A`` could be extreme based on its rank.
+
+ INPUT:
+
+ - ``A`` - The matrix in question
+
+ OUTPUT:
+
+ ``False`` if the rank of ``A`` precludes it from being an extreme
+ matrix of the doubly-nonnegative cone, ``True`` otherwise.
+
+ REFERENCE:
+
+ Hamilton-Jester, Crista Lee; Li, Chi-Kwong. Extreme Vectors of
+ Doubly Nonnegative Matrices. Rocky Mountain Journal of Mathematics
+ 26 (1996), no. 4, 1371--1383. doi:10.1216/rmjm/1181071993.
+ http://projecteuclid.org/euclid.rmjm/1181071993.
+
+ SETUP::
+
+ sage: from mjo.cone.doubly_nonnegative import has_admissible_extreme_rank
+
+ EXAMPLES:
+
+ The zero matrix has rank zero, which is admissible::
+
+ sage: A = zero_matrix(QQ, 5, 5)
+ sage: has_admissible_extreme_rank(A)
+ True
+
+ Likewise, rank one is admissible for dimension 5::
+
+ sage: v = vector(QQ, [1,2,3,4,5])
+ sage: A = v.column()*v.row()
+ sage: has_admissible_extreme_rank(A)
+ True
+
+ But rank 2 is never admissible::
+
+ sage: v1 = vector(QQ, [1,0,0,0,0])
+ sage: v2 = vector(QQ, [0,1,0,0,0])
+ sage: A = v1.column()*v1.row() + v2.column()*v2.row()
+ sage: has_admissible_extreme_rank(A)
+ False
+
+ In dimension 5, three is the only other admissible rank::
+
+ sage: v1 = vector(QQ, [1,0,0,0,0])
+ sage: v2 = vector(QQ, [0,1,0,0,0])
+ sage: v3 = vector(QQ, [0,0,1,0,0])
+ sage: A = v1.column()*v1.row()
+ sage: A += v2.column()*v2.row()
+ sage: A += v3.column()*v3.row()
+ sage: has_admissible_extreme_rank(A)
+ True
+
+ """
+ if not A.is_symmetric():
+ # This function is more or less internal, so blow up if passed
+ # something unexpected.
+ raise ValueError('The matrix ``A`` must be symmetric.')
+
+ r = rank(A)
+ n = ZZ(A.nrows()) # Columns would work, too, since ``A`` is symmetric.
+
+ return is_admissible_extreme_rank(r,n)
+
+
+def stdE(matrix_space, i,j):
+ """
+ Return the ``i``,``j``th element of the standard basis in
+ ``matrix_space``.
+
+ INPUT:
+
+ - ``matrix_space`` - The underlying matrix space of whose basis
+ the returned matrix is an element
+
+ - ``i`` - The row index of the single nonzero entry
+
+ - ``j`` - The column index of the single nonzero entry
+
+ OUTPUT:
+
+ A basis element of ``matrix_space``. It has a single \"1\" in the
+ ``i``,``j`` row,column and zeros elsewhere.
+
+ SETUP::
+
+ sage: from mjo.cone.doubly_nonnegative import stdE
+
+ EXAMPLES::
+
+ sage: M = MatrixSpace(ZZ, 2, 2)
+ sage: stdE(M,0,0)
+ [1 0]
+ [0 0]
+ sage: stdE(M,0,1)
+ [0 1]
+ [0 0]
+ sage: stdE(M,1,0)
+ [0 0]
+ [1 0]
+ sage: stdE(M,1,1)
+ [0 0]
+ [0 1]
+ sage: stdE(M,2,1)
+ Traceback (most recent call last):
+ ...
+ IndexError: Index `i` is out of bounds.
+ sage: stdE(M,1,2)
+ Traceback (most recent call last):
+ ...
+ IndexError: Index `j` is out of bounds.
+
+ """
+ # We need to check these ourselves, see below.
+ if i >= matrix_space.nrows():
+ raise IndexError('Index `i` is out of bounds.')
+ if j >= matrix_space.ncols():
+ raise IndexError('Index `j` is out of bounds.')
+
+ # The basis here is returned as a one-dimensional list, so we need
+ # to compute the offset into it based on ``i`` and ``j``. Since we
+ # compute the index ourselves, we need to do bounds-checking
+ # manually. Otherwise for e.g. a 2x2 matrix space, the index (0,2)
+ # would be computed as offset 3 into a four-element list and we
+ # would succeed incorrectly.
+ idx = matrix_space.ncols()*i + j
+ return list(matrix_space.basis())[idx]
"""
Returns ``True`` if the given matrix is an extreme matrix of the
doubly-nonnegative cone, and ``False`` otherwise.
+
+ REFERENCES:
+
+ 1. Hamilton-Jester, Crista Lee; Li, Chi-Kwong. Extreme Vectors of
+ Doubly Nonnegative Matrices. Rocky Mountain Journal of Mathematics
+ 26 (1996), no. 4, 1371--1383. doi:10.1216/rmjm/1181071993.
+ http://projecteuclid.org/euclid.rmjm/1181071993.
+
+ 2. Berman, Abraham and Shaked-Monderer, Naomi. Completely Positive
+ Matrices. World Scientific, 2003.
+
+ SETUP::
+
+ sage: from mjo.cone.doubly_nonnegative import is_extreme_doubly_nonnegative
+
+ EXAMPLES:
+
+ The zero matrix is an extreme matrix::
+
+ sage: A = zero_matrix(QQ, 5, 5)
+ sage: is_extreme_doubly_nonnegative(A)
+ True
+
+ Any extreme vector of the completely positive cone is an extreme
+ vector of the doubly-nonnegative cone::
+
+ sage: v = vector([1,2,3,4,5,6])
+ sage: A = v.column() * v.row()
+ sage: A = A.change_ring(QQ)
+ sage: is_extreme_doubly_nonnegative(A)
+ True
+
+ We should be able to generate the extreme completely positive
+ vectors randomly::
+
+ sage: v = vector(map(abs, random_vector(ZZ, 4)))
+ sage: A = v.column() * v.row()
+ sage: A = A.change_ring(QQ)
+ sage: is_extreme_doubly_nonnegative(A)
+ True
+ sage: v = vector(map(abs, random_vector(ZZ, 10)))
+ sage: A = v.column() * v.row()
+ sage: A = A.change_ring(QQ)
+ sage: is_extreme_doubly_nonnegative(A)
+ True
+
+ The following matrix is completely positive but has rank 3, so by a
+ remark in reference #1 it is not extreme::
+
+ sage: A = matrix(QQ, [[1,2,1],[2,6,3],[1,3,5]])
+ sage: is_extreme_doubly_nonnegative(A)
+ False
+
+ The following matrix is completely positive (diagonal) with rank 2,
+ so it is also not extreme::
+
+ sage: A = matrix(QQ, [[1,0,0],[2,0,0],[0,0,0]])
+ sage: is_extreme_doubly_nonnegative(A)
+ False
+
"""
- raise NotImplementedError()
+
+ if not A.base_ring().is_exact() and not A.base_ring() is SR:
+ msg = 'The base ring of ``A`` must be either exact or symbolic.'
+ raise ValueError(msg)
+
+ if not A.base_ring().is_field():
+ raise ValueError('The base ring of ``A`` must be a field.')
+
+ if not A.base_ring() is SR:
+ # Change the base field of ``A`` so that we are sure we can take
+ # roots. The symbolic ring has no algebraic_closure method.
+ A = A.change_ring(A.base_ring().algebraic_closure())
+
+ # Step 1 (see reference #1)
+ k = A.rank()
+
+ if k == 0:
+ # Short circuit, we know the zero matrix is extreme.
+ return True
+
+ if not A.is_positive_semidefinite():
+ return False
+
+ # Step 1.5, appeal to Theorem 3.1 in reference #1 to short
+ # circuit.
+ if not has_admissible_extreme_rank(A):
+ return False
+
+ # 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