# Trace of Matrix Exponential closed form expression

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

• Is your matrix diagonalizable, that would make life simpler – Triatticus Jun 10 '16 at 22:24
• 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? – Kiran K. Jun 10 '16 at 22:32
• Well, $\mathbf{tr}(A^k)=\sum_i\lambda_i^k$. Can you make use of that? – amd Jun 10 '16 at 22:38
• 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$ – Triatticus Jun 10 '16 at 22:43
• 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? – Kiran K. Jun 10 '16 at 22:48

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