The trace
The trace is an operation which turns outer products into inner products,
\operatorname{tr}\colon |b\rangle\langle a| \longmapsto \langle a|b\rangle.
We have just seen that any linear operator can be written as a sum of outer products, and so we can extend the definition of trace (by linearity) to any operator.
Equivalently, for any square matrix A, the trace of A can be defined to be the sum of its diagonal elements:
\operatorname{tr}A = \sum_k \langle e_k|A|e_k\rangle = \sum_k A_{kk}.
In fact, the trace of A is equal to the sum of the eigenvalues of A, even in the case where A is not diagonalisable.
You can show, using this definition or otherwise, that the trace is cyclic (\operatorname{tr}(AB) = \operatorname{tr}(BA)) and linear (\operatorname{tr}(\alpha A+\beta B) = \alpha\operatorname{tr}(A)+\beta\operatorname{tr}(B), where A and B are square matrices and \alpha and \beta complex numbers).
To recover the first definition from the second, we argue as follows:
\begin{aligned}
\operatorname{tr}|b\rangle\langle a|
&= \sum_k \langle e_k|b\rangle\langle a|e_k\rangle
\\&= \sum_k \langle a|e_k\rangle\langle e_k|b\rangle
\\&= \langle a|\mathbf{1}|b\rangle
\\&= \langle a|b\rangle.
\end{aligned}
Here, the second term can be viewed both as the sum of the diagonal elements of |b\rangle\langle a| in the |e_k\rangle basis, and as the sum of the products of two complex numbers \langle e_k|b\rangle and \langle a|e_k\rangle.
We have used the decomposition of the identity, \sum_k|e_k\rangle\langle e_k|=\mathbf{1}.
Given that we can decompose the identity by choosing any orthonormal basis, it is clear that the trace does not depend on the choice of the basis.