-"""
+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 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
+from mjo.cone.symmetric_psd import (factor_psd,
+ random_symmetric_psd)
+from mjo.basis_repr import basis_repr
def is_doubly_nonnegative(A):
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::
raise ValueError.new(msg)
# Check that all of the entries of ``A`` are nonnegative.
- if not all([ a >= 0 for a in A.list() ]):
+ 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)
+ 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.
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::
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::
return is_admissible_extreme_rank(r,n)
-def E(matrix_space, i,j):
+def stdE(matrix_space, i,j):
"""
Return the ``i``,``j``th element of the standard basis in
``matrix_space``.
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: E(M,0,0)
+ sage: stdE(M,0,0)
[1 0]
[0 0]
- sage: E(M,0,1)
+ sage: stdE(M,0,1)
[0 1]
[0 0]
- sage: E(M,1,0)
+ sage: stdE(M,1,0)
[0 0]
[1 0]
- sage: E(M,1,1)
+ sage: stdE(M,1,1)
[0 0]
[0 1]
- sage: E(M,2,1)
+ sage: stdE(M,2,1)
Traceback (most recent call last):
...
IndexError: Index `i` is out of bounds.
- sage: E(M,1,2)
+ sage: stdE(M,1,2)
Traceback (most recent call last):
...
IndexError: Index `j` is out of bounds.
# 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]
+ return list(matrix_space.basis())[idx]
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::
# Short circuit, we know the zero matrix is extreme.
return True
- if not is_symmetric_psd(A):
+ if not A.is_positive_semidefinite():
return False
# Step 1.5, appeal to Theorem 3.1 in reference #1 to short
# 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):
+ for j in range(A.ncols()):
+ for i in range(j):
if A[i,j] == 0:
M = A.matrix_space()
- S = X.transpose() * (E(M,i,j) + E(M,j,i)) * X
+ 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
# 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())
+ (phi, phi_inverse) = basis_repr(A.matrix_space())
vectors = map(phi,spanning_set)
V = span(vectors, A.base_ring())
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::
# Generate random symmetric positive-semidefinite matrices until
# one of them is nonnegative, then return that.
- A = random_psd(V, accept_zero, rank)
+ A = random_symmetric_psd(V, accept_zero, rank)
- while not all([ x >= 0 for x in A.list() ]):
- A = random_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
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::
"""
- if not is_admissible_extreme_rank(rank, V.dimension()):
+ 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()))