4
$\begingroup$

Given correlation matrix $B$ (positive semi-definite with ones in the diagonal).

1)Find the correlation matrix $A$ which maximizes $\det\left(A+B\right)$.
2)Find the correlation matrix $A$ which minimizes $\det\left(A+B\right)$

$\endgroup$
  • 1
    $\begingroup$ if A and B are given there is nothing to maximize/minimize; if A is not given, what will stop you from taking A an arbitrarily large multiple of the unit matrix, so that the determinant of A+B will become arbitrarily large? $\endgroup$ – Carlo Beenakker Sep 28 '13 at 17:12
  • $\begingroup$ That is because A is a correlation matrix. So it has 1s on the diagonal. $\endgroup$ – user40607 Sep 28 '13 at 17:22
  • $\begingroup$ Actually this is a nice question, though a bit poorly phrased originally, but now it is clearly stated. $\endgroup$ – Suvrit Sep 29 '13 at 2:21
4
$\begingroup$

I assume that what the OP wanted to say was, given a correlation matrix $B$, find a correlation matrix $A$ that maximizes $\det(A+B)$. Let me cite here a more general theorem that paves the way to a solution.

Theorem Let $A$ and $B$ be Hermitian matrices with eigenvalues $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$, respectively. Then,

\begin{equation*} \det(A+B) \le \max_{\sigma \in \mathfrak{S}_n}\prod_{i=1}^n (a_i + b_{\sigma(i)}). \end{equation*}

Since correlation matrices are Hermitian positive semidefinite, a specialization of this theorem shows us that \begin{equation*} \det(A+B) \le \prod_{i=1}^n (\lambda_i(A) + \lambda_{n-i+1}(B)), \end{equation*} where $\lambda_i(\cdot)$ is the $i$-largest eigenvalue. Thus, in particular, for a fixed $B$, we just need to pick a suitable $A$ that has the same eigenvectors as $B$ (in permuted order, however), but has the largest possible allowable eigenvalues.

EDIT It is not immediate, if these eigenvalues can be easily obtained in closed form. It seems that in some cases the optimum solution can be obtained by setting \begin{equation*} a_{ij} = \begin{cases} -b_{ij} & i \neq j,\\ 1 & i = j \end{cases}. \end{equation*} In this case, $A+B = 2I_n$. But in general, as noted by the OP in the comments below, this construction does not always work. I am still hoping to be able to get a solution more easily than solving an SDP, but at this point it is not clear whether I can do better than solving an SDP (for the maximization problem).

$\endgroup$
  • $\begingroup$ And what A would minimize det(A+B)? $\endgroup$ – user40607 Sep 28 '13 at 18:37
  • $\begingroup$ Actually I think there might be something wrong in that proof. Consider B=[1 .5;.5 1], if A=[1 0;0 1] the det(A+B) is less than if A=[1 -.5;-.5 1]. $\endgroup$ – user40607 Sep 28 '13 at 22:31
  • $\begingroup$ Actually that is true---the simple diagonal $A$ is not going to work because correlation matrices can easily have eigenvalues larger than 1. So $A=I_n$ is not the answer, but the answer will be obtained by finding an $A$ for which the 2nd inequality listed above becomes an equality. $\endgroup$ – Suvrit Sep 29 '13 at 1:51
  • $\begingroup$ I thought a bit more about it; as the above inequality shows, $A$ will have the same eigenvectors as $B$ (just permuted in opposite order); but it is not immediate what the eigenvalues should be---without that, a closed form solution won't be possible, and this turns into a convex optimization problem, which seems overkill.... $\endgroup$ – Suvrit Sep 29 '13 at 2:11
  • $\begingroup$ A(i,j)=-B(i,j) works in 2 dimensions. But for larger dimensions this could be impossible because A needs to be hermitian. For example: if B=[1 1 1;1 1 1;1 1 1] then A should be A=[1 -1 -1;-1 1 -1;-1 -1 1] which is not hermitian. $\endgroup$ – user40607 Sep 29 '13 at 2:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.