Skip to main content
added 30 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

For any of your diagonal matrices $D$, let $J:=J_D$ be the set such that $D_{i,j}=1(i=j\in J)$ for all $i,j$ in the set $[N]:=\{1,\dots,N\}$, where, for any matrix $M$, its $(i,j)$-entry is denoted by $M_{i,j}$. Then $J$ is in $\binom{[N]}m$, the set of all subsets of $[N]$ of cardinality $m$.

So, for $J:=J_D$, $$\text{Tr}(ADBD) =\sum_{i,j,k,l\in[N]}A_{i,j}1(j=k\in J)B_{k,l}1(l=i\in J) \\ =\sum_{i\in[N],j\in J}A_{i,j}B_{j,i}=\sum_{j\in J}(BA)_{j,j}. $$$$\text{Tr}(ADBD) =\sum_{i,j,k,l\in[N]}A_{i,j}1(j=k\in J)B_{k,l}1(l=i\in J) \\ =\sum_{i,j\in J}A_{i,j}B_{j,i}=\text{Tr}(A_J B_J),$$ where $M_J:=[M_{i,j}\colon i,j\in J]$.

So, $\max_D\text{Tr}(ADBD)$ is the summaximum of the $m$ largest diagonal entries of the matrix$\text{Tr}(A_J B_J)$ over all $BA$$J\in\binom{[N]}m$.

For any of your diagonal matrices $D$, let $J:=J_D$ be the set such that $D_{i,j}=1(i=j\in J)$ for all $i,j$ in the set $[N]:=\{1,\dots,N\}$, where, for any matrix $M$, its $(i,j)$-entry is denoted by $M_{i,j}$. Then $J$ is in $\binom{[N]}m$, the set of all subsets of $[N]$ of cardinality $m$.

So, for $J:=J_D$, $$\text{Tr}(ADBD) =\sum_{i,j,k,l\in[N]}A_{i,j}1(j=k\in J)B_{k,l}1(l=i\in J) \\ =\sum_{i\in[N],j\in J}A_{i,j}B_{j,i}=\sum_{j\in J}(BA)_{j,j}. $$

So, $\max_D\text{Tr}(ADBD)$ is the sum of the $m$ largest diagonal entries of the matrix $BA$.

For any of your diagonal matrices $D$, let $J:=J_D$ be the set such that $D_{i,j}=1(i=j\in J)$ for all $i,j$ in the set $[N]:=\{1,\dots,N\}$, where, for any matrix $M$, its $(i,j)$-entry is denoted by $M_{i,j}$. Then $J$ is in $\binom{[N]}m$, the set of all subsets of $[N]$ of cardinality $m$.

So, for $J:=J_D$, $$\text{Tr}(ADBD) =\sum_{i,j,k,l\in[N]}A_{i,j}1(j=k\in J)B_{k,l}1(l=i\in J) \\ =\sum_{i,j\in J}A_{i,j}B_{j,i}=\text{Tr}(A_J B_J),$$ where $M_J:=[M_{i,j}\colon i,j\in J]$.

So, $\max_D\text{Tr}(ADBD)$ is the maximum of $\text{Tr}(A_J B_J)$ over all $J\in\binom{[N]}m$.

Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

For any of your diagonal matrices $D$, let $J:=J_D$ be the set such that $D_{i,j}=1(i=j\in J)$ for all $i,j$ in the set $[N]:=\{1,\dots,N\}$, where, for any matrix $M$, its $(i,j)$-entry is denoted by $M_{i,j}$. Then $J$ is in $\binom{[N]}m$, the set of all subsets of $[N]$ of cardinality $m$.

So, for $J:=J_D$, $$\text{Tr}(ADBD) =\sum_{i,j,k,l\in[N]}A_{i,j}1(j=k\in J)B_{k,l}1(l=i\in J) \\ =\sum_{i\in[N],j\in J}A_{i,j}B_{j,i}=\sum_{j\in J}(BA)_{j,j}. $$

So, $\max_D\text{Tr}(ADBD)$ is the sum of the $m$ largest diagonal entries of the matrix $BA$.