3
$\begingroup$

Let $X \in S^{n}_{+}$ be a positive semi-definite matrix with $X_{ii} = 1$ for all $i \leq n$ (thus $X$ is a correlation matrix). Since $X$ is positive semi-definite, we have $|X_{ij}| \leq 1$ for any entry $(i,j)$.

Let $\arcsin(X) = (\arcsin(X_{ij}))_{i,j \leq n}$, i.e., the arcsin function applies on the matrix X element-wisely. From the Schur product theorem, we know $\arcsin(X) \succeq X$, where $A \succeq B$ means $A-B$ is positive semi-definite. I wonder, do we have an inequality on the other side, i.e., there exists some real number $a> 0$ such that $a X \succeq \arcsin(X)$?

I am asking this question because SDP relaxation usually provides good approximation algorithms to combinatorial optimization with a maximization objective. I am thinking about if we can still apply SDP to minimization problems.

$\endgroup$
2
  • 1
    $\begingroup$ A trivial $3\times 3$ counterexample is $\begin{bmatrix}1&-0.5&-0.5\\-0.5&1&-0.5\\-0.5&-0.5&1\end{bmatrix}$. $1\times 1$ is certainly fine and $2\times 2$ seems OK too though I haven't checked it thoroughly. $\endgroup$
    – fedja
    Feb 12 '21 at 0:52
  • $\begingroup$ @fedja I see. I think it's a great example. Here $arcsin(X)$ is positive definite but $X$ is only positive semi-definite. We can find an invertible matrix $P$ such that $arcsin(X) = P^{T} P$ and $X = P^{T} D P$, with $D$ being a diagonal matrix with some diagonal entry being zero. Thus, $aX - arcsin(X) = P^{T} (aD - I) P$ can not be positive semi-definite. $\endgroup$
    – zxzx179
    Feb 12 '21 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.