+ # 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]