From 7a884aa96ce490425b82d977d3242954511efbdf Mon Sep 17 00:00:00 2001
From: Michael Orlitzky <michael@orlitzky.com>
Date: Tue, 4 Nov 2014 11:04:04 -0500
Subject: [PATCH] Add is_admissible_extreme_rank() and use it to implement
 has_admissible_extreme_rank().

---
 mjo/cone/doubly_nonnegative.py | 108 +++++++++++++++++++++++++++------
 1 file changed, 91 insertions(+), 17 deletions(-)

diff --git a/mjo/cone/doubly_nonnegative.py b/mjo/cone/doubly_nonnegative.py
index 4f7f950..ebb5b68 100644
--- a/mjo/cone/doubly_nonnegative.py
+++ b/mjo/cone/doubly_nonnegative.py
@@ -67,6 +67,67 @@ def is_doubly_nonnegative(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
@@ -93,9 +154,35 @@ def has_admissible_extreme_rank(A):
 
     The zero matrix has rank zero, which is admissible::
 
-    sage: A = zero_matrix(QQ, 5, 5)
-    sage: has_admissible_extreme_rank(A)
-    True
+        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():
@@ -106,20 +193,7 @@ def has_admissible_extreme_rank(A):
     r = rank(A)
     n = ZZ(A.nrows()) # Columns would work, too, since ``A`` is symmetric.
 
-    if r == 0:
-        # Zero is in the doubly-nonnegative cone.
-        return True
-
-    # 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)
+    return is_admissible_extreme_rank(r,n)
 
 
 def E(matrix_space, i,j):
-- 
2.44.2