1

Most of the question is in the title. Suppose that I have $B$ a square $N\times N$ positive definite matrix, and $A$ a low-rank square matrix with its non-zero eigenvalues being a subset of the spectrum of $B^{-1}$. Is there a simple way to compute the trace : $\mathrm{tr}(BA)$?

My intuition is that if $M$ is the rank of $A$, then $B$ and $A$ can share all $N$ eigenvectors and that one can diagonalize $A$ and $B$ and get automatically $\mathrm{tr}(BA) = \sum_{i:\lambda_i>0} \frac{\lambda_i}{\lambda_i} = M$ where $\lambda_i$ are the eigenvalues of $A$. But I am not sure how to obtain the proper ordering etc.

Thanks for your help!

Jessie
  • 1,463
Théo Galy-Fajou
  • 53
  • Without more information about the eigenvectors of $A$, there is no way to take advantage of the eigenvalues of $A$ – Ben Grossmann Feb 02 '21 at 15:09
  • Cost of computing $\operatorname{tr}(BA)$ directly it is $2N^2$ floating point operations. Even having rank factorization $A = KL$ will not allow for any speed up. – Pawel Kowal Feb 02 '21 at 16:33
  • I am not interested in any speed up but I want to find a bound or even better an equality :) – Théo Galy-Fajou Feb 03 '21 at 10:20

2 Answers2

2

Without further information, there is no way to use the eigenvalues of $A$ in this computation. However, we can make use of the fact that $A$ is low-rank. In particular, if $A = CF$ is a rank factorization (so that $C$ is $N \times r$ and $F$ is $r \times N$), then we have $$ \operatorname{tr}(BA) = \operatorname{tr}(BCF) = \operatorname{tr}(FBC). $$ That is, we may rewrite the expression as the trace of an $r \times r$ matrix.

Ben Grossmann
  • 225,327
1

Ok here is a more concrete attempt. So if the eigenvalues of $B^{-1}$ are $\Lambda_B = \{\lambda_i\}_{i=1}^N$, I know that the eigenvalues $\Lambda_A$ of $A$ are a subset of $\Lambda_B$ and the rest are $0$. So I can rewrite $B=W D_B^{-1}W^\top$ where $D_B=\text{diag}(\Lambda_A, \Lambda_{B}/\Lambda_{A})$ and $W$ are the corresponding eigenvectors. Similarly I can rewrite $A$ as $A=WD_AW^\top$ where $D_A=\text{diag}(\Lambda_A, 0)$

Which means I can rewrite \begin{align} \text{tr}(BA) =& \text{tr}(WD_B^{-1}W^\top WD_AW^\top) = \text{tr}(W^\top W D_B^{-1}D_A)\\ =& \text{tr}(D_B^{-1}D_A) = \sum_{i=i}^M \frac{\lambda_i}{\lambda_i} = M. \end{align}

Is there anything wrong with my reasonning?

Théo Galy-Fajou
  • 53
  • 1
    The fact that you assume that we have $B = WD_B^{-1}W^\top$ and $A = WD_AW^\top$ for a single orthogonal matrix $W$ means that you assume that $A$ and $B$ are simultaneously diagonalizable. Equivalently, you're assuming that $AB = BA$. From what you said in the question, we have no reason to believe that this is the case. – Ben Grossmann Feb 03 '21 at 15:52
  • Well $B$ is positive definite and $A$ is positive semi-definite right? So both matrices are symmetric and $AB = BA$ ? – Théo Galy-Fajou Feb 03 '21 at 17:02
  • I just saw https://math.stackexchange.com/questions/1079627/simultaneously-diagonalization-of-two-matrices and it seems that I need my matrices to have the same eigenvectors. Which is automatically the case here. – Théo Galy-Fajou Feb 03 '21 at 17:12
  • You seem to be saying that for every positive definite $A$ and positive semidefinite $B$, we have $AB = BA$. This is not true. For example, $$ A = \pmatrix{1&0\0&2}, \quad B = \pmatrix{1&1\1&1} $$ – Ben Grossmann Feb 03 '21 at 18:10
  • You're right! Sorry my first comment is completely wrong. However the second one holds I think. – Théo Galy-Fajou Feb 03 '21 at 18:29
  • Are you saying that, for your particular example, $A$ and $B$ have the same eigenvectors? – Ben Grossmann Feb 04 '21 at 13:23
  • Yes, and this is due to the fact the $M$ non-negative values of $A$ are the same as $B^{-1}$. There are $M$ common eigenvectors, and the $N-M$ others have eigenvalues $0$ therefore they can be anything as long as they are orthogonal to the first $M$ ones, so I can chose them to be the $N-M$ other eigenvectors of $B^{-1}$ – Théo Galy-Fajou Feb 12 '21 at 15:03
  • What do you mean when you say that you can "choose" them to be certain eigenvectors? For the $A,B$ from your example, either it holds that $AB = BA$ or it doesn't hold. If $AB = BA$, then it can be said that $A,B$ have "the same eigenvectros". If $AB \neq BA$, then this cannot be said. – Ben Grossmann Feb 12 '21 at 15:54
  • And why are there $M$ common eigenvectors? Do you have information about $A$ and $B$ that you didn't include in the question? – Ben Grossmann Feb 12 '21 at 15:55
  • Do you have any information that rules out an example like $$ A = \pmatrix{1&1\1&1}, \quad B = \pmatrix{1/2&0\0&1}? $$ – Ben Grossmann Feb 12 '21 at 15:56