5
$\begingroup$

I would like to compute the $\mathbf{tr}(e^A)$ where $A$ is some square matrix with entries that have only values of either $0$ or $1$, and $\mathbf{tr}$ is the trace operator. Are there closed form expressions for this or some way to compute it easily without having to compute the actual matrix exponential for every element in A?

I have gotten this far: $$ \mathbf{tr}(e^A) = \sum_{k=0}^\infty \frac{1}{k!} \mathbf{tr}(A^k) $$ due to the property that $$ \mathbf{tr}(A+B) = \mathbf{tr}(A) + \mathbf{tr}(B) $$ but not sure how to go further and perhaps get a simpler expression? I would like some expression form of this because I am going to use this as a constraint in an optimization problem... otherwise I wouldn't worry about the computational cost of computing all the elements of $e^A$.

$\endgroup$
  • 1
    $\begingroup$ Is your matrix diagonalizable, that would make life simpler $\endgroup$ – Triatticus Jun 10 '16 at 22:24
  • $\begingroup$ I don't know if I can assume that unfortunately ..., I will look into figuring out if it is diagonalizable, but if so, how does this make life simpler? $\endgroup$ – Kiran K. Jun 10 '16 at 22:32
  • 1
    $\begingroup$ Well, $\mathbf{tr}(A^k)=\sum_i\lambda_i^k$. Can you make use of that? $\endgroup$ – amd Jun 10 '16 at 22:38
  • 1
    $\begingroup$ If your matrix is diagonalizable then it can be written as $A = P^{-1}DP$ where D is diagonal, then it is easy to calculate traces of powers of such matrix since $\operatorname{Tr}((P^{-1}DP)^k) = \operatorname{Tr}(P^{-1}D^k P) = \operatorname{Tr}(D^k) = \sum_i \lambda^k_i$ $\endgroup$ – Triatticus Jun 10 '16 at 22:43
  • $\begingroup$ Right, good point to both Triatticus and @amd, I guess I need to look to see if my matrix will always be diagonalizable. Wonder if people have any ideas if I cannot ensure this for A? $\endgroup$ – Kiran K. Jun 10 '16 at 22:48
8
$\begingroup$

There is a general form for this expression, but it relies on the fact that every square matrix has a Jordan canonical form. That is, for every $A$ there is invertible matrix $Q$ and some block diagonal $J$ with 1's on the super-diagonal such that $A = Q^{-1}JQ$. Notice now that $A^k = (Q^{-1}JQ)^k = Q^{-1}J^kQ$ and so your sum for the matrix exponential reduces to

$$ \exp(A) \;\; =\;\; Q^{-1} \left ( \sum_{k=0}^\infty \frac{1}{k!}J^k \right ) Q \;\; =\;\; Q^{-1} \exp(J) Q. $$

Now, given the fact that $Tr(ABC) = Tr(BCA) = Tr(CAB)$ we have that $Tr(\exp(A)) = Tr(\exp(J))$. Here, because you're only computing the trace, you only need to worry about the actual diagonal values in the Jordan block matrix $J$. Therefore

$$ Tr(\exp(A)) \;\; =\;\; \sum_{\lambda \in \Lambda(A)} m_\lambda e^\lambda $$

where $\Lambda(A)$ is the set of distinct generalized eigenvalues of $A$, and $m_\lambda$ is the multiplicity corresponding to $\lambda \in \Lambda(A)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.