""" The doubly-nonnegative cone in `S^{n}` is the set of all such matrices that both, a) are positive semidefinite b) have only nonnegative entries It is represented typically by either `\mathcal{D}^{n}` or `\mathcal{DNN}`. """ 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 our module names # resolve. from os.path import abspath from site import addsitedir addsitedir(abspath('../../')) from mjo.cone.symmetric_psd import factor_psd, is_symmetric_psd, random_psd from mjo.matrix_vector import isomorphism def is_doubly_nonnegative(A): """ Determine whether or not the matrix ``A`` is doubly-nonnegative. INPUT: - ``A`` - The matrix in question OUTPUT: Either ``True`` if ``A`` is doubly-nonnegative, or ``False`` otherwise. EXAMPLES: Every completely positive matrix is doubly-nonnegative:: sage: v = vector(map(abs, random_vector(ZZ, 10))) sage: A = v.column() * v.row() sage: is_doubly_nonnegative(A) True The following matrix is nonnegative but non positive semidefinite:: sage: A = matrix(ZZ, [[1, 2], [2, 1]]) sage: is_doubly_nonnegative(A) False """ if A.base_ring() == SR: msg = 'The matrix ``A`` cannot be the symbolic.' raise ValueError.new(msg) # Check that all of the entries of ``A`` are nonnegative. if not all([ a >= 0 for a in A.list() ]): return False # It's nonnegative, so all we need to do is check that it's # symmetric positive-semidefinite. return is_symmetric_psd(A) def is_admissible_extreme_rank(r, n): """ 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. 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 # 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. 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 E(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. EXAMPLES:: sage: M = MatrixSpace(ZZ, 2, 2) sage: E(M,0,0) [1 0] [0 0] sage: E(M,0,1) [0 1] [0 0] sage: E(M,1,0) [0 0] [1 0] sage: E(M,1,1) [0 0] [0 1] sage: E(M,2,1) Traceback (most recent call last): ... IndexError: Index `i` is out of bounds. sage: E(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 matrix_space.basis()[idx] def is_extreme_doubly_nonnegative(A): """ 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. 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 """ 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 is_symmetric_psd(A): 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(0, A.ncols()): for i in range(0,j): if A[i,j] == 0: M = A.matrix_space() S = X.transpose() * (E(M,i,j) + E(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) = isomorphism(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. 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_psd(V, accept_zero, rank) while not all([ x >= 0 for x in A.list() ]): A = random_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. 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 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