How to choose $B$ to have $ \operatorname{trace}(H) \ge \operatorname{trace}(B^{\top}HB)$?

Question

Considering $H \in \mathbb{R}^{N \times N}$ a real symmetric matrix which has both positive and negative eigenvalues, and $B \in \mathbb{R}^{N \times M}$ a real matrix with positive entries.

Can I find a condition to make $ \operatorname{trace}(H) \ge \operatorname{trace}(B^{\top}HB)$?

Answer 1

Since $H $ is real and symmetric, it can be diagonalized as $H = V^T D V $ where $V^T = V^{-1} $ and $ D$ is diagonal. Thus your expression may be rewritten as

$ tr (D) \geq tr ( B^T H B ) = tr ( B B^T H ) $ where I have used that $tr (D) = tr (H) $ and the fact that the trace is invariant under cyclic permutations.

With this in mind, one obvious sufficient condition may be $B^{-1} = B^T $ in which case the equality holds.

Another example: pick $B $ such that $B B^T = H $ so $tr ( B B^T H) = tr ( H^2) = tr (D^2) $. So now you should pick $D $ such that $tr (D) \geq tr (D^2)$, for example, having positive numbers smaller than 1 in the diagonal.

I'm aware these are not general conditions, only particular cases... but I guess this way you can build more examples and maybe get something more general.

Answer 2

If you had looked at the case $n=1$ (and that's what you should have done), you would have seen that

if $H>0$, then $1\geq B^2$, if $H<0$, then $1\leq B^2$ and if $H=0$, then every $B$ works.

We assume that $tr(H)>0$.

The condition is $tr(H))\geq tr(HS)$ where $S=BB^T$ is $N\times N$ symmetric $\geq 0$ with $>0$ entries. The required inequality stands if $S$ (or $B$) is small enough.

More precisely, a sufficient condition is $tr(H^2)tr(S^2)\leq (tr(H))^2$.

Proof. $|tr(HS)|\leq \sqrt{tr(H^2)}\sqrt{tr(S^2)}$ (by Cauchy-Schwartz).

Answer 3

Step 1. Look at the eigendecomposition $$H=VDV^{\rm T}$$

$$ H - \text{symmetric} \Rightarrow \begin{cases} D - \text{diagonal} \\ V - \text{orthogonal} \\\end{cases} $$

Step 2. Come up with any value $\Delta$ you want $-$ that will be your future $\operatorname{trace}(B^{\rm T}HB)$.

Step 3. Choose such $c_k\ge0$ that $\sum c_k\lambda_k= \Delta$, where $\lambda_k$ is the diagonal entries of $D$. It is always possible since the matrix $H$ has both positive and negative eigenvalues.

Step 4a. Take a diagonal matrix $C$ with diagonal entries $\sqrt{c_k}$ .

Step 4b. If you want matrix $B$ to have exactly $M$ columns ($M<N$) then you have to pick exactly $M$ nonzero elements $c_k$ on Step 3 and then drop $N-M$ zero columns of matrix $C$ obtained on Step 4a, leaving yourself with the new matrix $C$ of size $N \times M$.

Step 5. Take $B=VC$ and get $\operatorname{trace}(B^{\rm T}HB)=\Delta$.

The last is true because $$ B^{\rm T}HB=B^{\rm T}VDV^{\rm T}B=C^{\rm T} \color{purple}{ V^{\rm T}V}D\color{purple}{V^{\rm T}V}C=C^{\rm T}DC, $$

which is a diagonal matrix with ${c_k\lambda_k}$ being its diagonal entries.

Unfortunately, this is not a proper answer to your question since I drop the restriction of $B$ being entrywise positive. I realized it after posting the answer but decided to leave it as it is.

Answer 4

Let $H = UDU^T$ where $U$ contains the eigenvectors and $D$ is diagonal containing eigenvalues. Let's choose $B = UW^T$, then $$B^T H B = (UW^T)^T(UDU^T) (UW^T) = W U^T UDU^TUW^T = WDW^T $$ Choosing $W$ as diagonal, we get that $$\operatorname{trace}(H) \ge \operatorname{trace}(B^{\top}HB) \iff \sum d_k \geq \sum w_k^2 d_k$$ Since $d_k$'s could be negative and positive, then choose $w_k = 1$ if $d_k <0$, else $w_k = 0$. This means that $\operatorname{trace}(B^{\top}HB)$ is just summing the negative eigenvalues of $H$ , if any.