Assume that $V$ is a finite-dimensional, complex vector space such that $v_1,\ldots,v_n\in V$ generate $V$, but $\dim(V)<n$. Let $\phi:V\to V$ be a linear map which I can describe in terms of the $v_i$, i.e. I know $\lambda_{ij}\in\mathbb C$ such that $\phi(v_i)=\sum_{j=1}^n \lambda_{ij} v_j$. I want to compute the trace of $\phi$, but it is technically and computably difficult to find a basis and express $\phi$ in terms of it. Can I compute $\mathrm{tr}(\phi)$ in terms of the $\lambda_{ij}$ somehow? After all, they (edit: together with the $v_i$) completely define the morphism $\phi$. I have no idea where to even start, though.
Edited Version Assume that $V\subseteq \mathbb C^d$ is a subvector space generated by $v_1,\ldots,v_n\in \mathbb C^d$. Assume that $\dim(V)<d$. As before, assume that we know $\lambda_{ij}$ with $\phi(v_i)=\sum_{j=1}^n \lambda_{ij} v_j$. The matrix $\Lambda=(\lambda_{ij})$ is very sparse, i.e. only about $n$ of the $\lambda_{ij}$ are not equal to zero. A special case which is already very interesting is $\phi(v_i)=v_{\pi(i)}$ for some permutation $\pi\in S_n$. Furthermore, $d$ is much larger than $n$. I would now like a method to compute the trace of $\phi$ that takes only $O(n)$ many steps, using the $v_i$ and the $\lambda_{ij}$ as input. The $v_i$ can be assumed to be black-box, i.e. given $v_i$ and $k\in\{1,\ldots,d\}$, an oracle will give you the coefficient of $v_i$ with respect to the $k$-th standard basis vector.