Two Strange Facts

Here are two strange facts about matrices, which I can prove but not in a satisfying way.

  1. If A and B are symmetric matrices satisfying 0 \preceq A \preceq B, then A^{1/2} \preceq B^{1/2}, and B^{-1} \preceq A^{-1}, but it is NOT necessarily the case that A^2 \preceq B^2. Is there a nice way to see why the first two properties should hold but not necessarily the third? In general, do we have A^p \preceq B^p if p \in [0,1]?
  2. Given a rectangular matrix W \in \mathbb{R}^{n \times d}, and a set S \subseteq [n], let W_S be the submatrix of W with rows in S, and let \|W_S\|_* denote the nuclear norm (sum of singular values) of W_S. Then the function f(S) = \|W_S\|_* is submodular, meaning that f(S \cup T) + f(S \cap T) \leq f(S) + f(T) for all sets S, T. In fact, this is true if we take f_p(S), defined as the sum of the pth powers of the singular values of W_S, for any p \in [0,2]. The only proof I know involves trigonometric integrals and seems completely unmotivated to me. Is there any clean way of seeing why this should be true?

If anyone has insight into either of these, I’d be very interested!


3 Responses to Two Strange Facts

  1. Shen says:

    Hi Jacob,

    I was just reading this post by Terrance Tao
    and the last few paragraphs reminded me of the first fact stated here. My gut feeling is the Sylvester equation based approach might be helpful in establishing true/false conclusion of the ‘In general…’ question you asked in the end.

  2. Mark Sellke says:

    Functions with the “operator monotone property” in 1. are worked out in some detail in this survey paper: Key theorems are 2.3, which shows that it does hold for all p in [0,1], and 4.1, which classifies the full set of (positive, though this doesn’t really matter) functions that work as weighted averages of the functions f_t(x)=x/(x+t) by a finite measure (so these x/(x+t) functions are the extreme points). Here f_0(x)=1 and f_{\infty}(x)=x.

    A corollary of the latter is that any operator monotone function like x^{-1} or x^{1/2] has to be increasing, smooth, and concave.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: