From 7a884aa96ce490425b82d977d3242954511efbdf Mon Sep 17 00:00:00 2001 From: Michael Orlitzky 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