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)$
$\begingroup$
$\endgroup$
3
-
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 BeenakkerSep 28, 2013 at 17:12
-
$\begingroup$ That is because A is a correlation matrix. So it has 1s on the diagonal. $\endgroup$– user40607Sep 28, 2013 at 17:22
-
$\begingroup$ Actually this is a nice question, though a bit poorly phrased originally, but now it is clearly stated. $\endgroup$– SuvritSep 29, 2013 at 2:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
11
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).
-
-
$\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$ Sep 28, 2013 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$– SuvritSep 29, 2013 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$– SuvritSep 29, 2013 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$ Sep 29, 2013 at 2:46