Skip to main content
corrected the answer in light of comments
Source Link
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

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 iscan 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).

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 the optimum solution is 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$.

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).

modified answer to fix prior incorrect conclusion.
Source Link
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

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 from whichthat paves the conclusion follows triviallyway 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---seems like $A=I_n$ does.

EDIT It is not immediate, if these eigenvalues can be easily obtained in closed form. It seems that the job!optimum solution is 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$.

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 from which the conclusion follows trivially.

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$ but has the largest possible eigenvalues---seems like $A=I_n$ does the job!

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 the optimum solution is 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$.

Source Link
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

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 from which the conclusion follows trivially.

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$ but has the largest possible eigenvalues---seems like $A=I_n$ does the job!