Proving the trace of a transformation is independent of the basis chosen

The simplest way it to note that a basis transformation of a transformation $T$ is done via $ATA^{-1}$ where $A$ is an invertible matrix, and that the trace has the property $\operatorname{tr}(AB)=\operatorname{tr}(BA)$. Putting this together, you get $$\operatorname{tr}(ATA^{-1}) = \operatorname{tr}(A^{-1}AT) = \operatorname{tr}T$$

An elementary proof could be the following. First, let $A$ be the matrix of your linear transformation in any basis of $V$. The characteristic polynomial of $A$ is

$$ Q_A(t) = \mathrm{det}\ (A - tI) = \begin{vmatrix} a^1_1 - t & a^1_2 & \dots & a^1_n \\ a^2_1 & a^2_2 - t & \dots & a^2_n \\ \vdots & \vdots & \ddots & \vdots \\ a^n_1 & a^2_2 & \dots & a^n_n - t \end{vmatrix} $$

You can compute easily at least the first terms of this polynomial taking into account that, by the definition of the determinant:

$$ Q_A(t) = (a^1_1 -t)\cdot \dots \cdot (a^n_n - t) + \quad \text{sums of products with at most $n-2$ terms in the diagonal} \quad \ . $$ Hence $$ Q_A(t) = (-1)^n t^n +(-1)^{n-1} (a^1_1 + \dots + a^n_n) t^{n-1} + \quad ( \text{terms of degree}\ \leq n-2 ) \ . $$

That is, up to a sign, the trace of $A$ is the coefficient of $t^{n-1}$ in the characteristic polynomial of $A$, $Q_A(t)$.

Now you can prove that $Q_A(t)$ does not depend on the basis you have chosen. Indeed, if $B$ is the matrix of the same linear transformation in another basis, then $A$ and $B$ are related through an equality like $B= S^{-1}A S$, where $S$ is the change of basis matrix. So

$$ Q_B(t) = \mathrm{det}\ (S^{-1}A S - tI ) = \mathrm{det}\ (S^{-1}A S - S^{-1}tIS ) = \mathrm{det}\ (S^{-1}(A - tI)S ) $$

Thus

$$ Q_B(t) = \mathrm{det}\ (S^{-1}) \ \mathrm{det}\ (A - tI )\ \mathrm{det}\ (S) = \mathrm{det}\ (A - tI ) = Q_A(t) \ . $$

Hence, the characteristic polynomial is invariant through basis change. In particular, so are its coefficients. More particularly, the trace.

There are a few ways to view this. The simplest is that if you have two $n \times n$ matrices $A, B$ then $$ \operatorname{tr}(AB) = \operatorname{tr}(BA). $$ This is an easy calculation.

Alternatively (some of the words may be unfamiliar to you, in which case ignore this bit), note that we have a canonical isomorphism $\operatorname{End}(V) \approx V \otimes V^\vee$, and that the trace on $\operatorname{End}(V)$ corresponds to the functional on $V \otimes V^\vee$ induced by the natural bilinear pairing of evaluation between $V$ and $V^\vee$. Verifying this is probably just as much work, but I think it's comforting to know that matrices are unnecessary for the definition.