Question: Let $K$ be a field, $n$ a natural number. Suppose that $(e\_i)\_{i=1}^{n^2}$ is a $K$-basis of the matrix algebra $\mathbb{M}\_n(K)$ (on which multiplication is defined in the usual manner). One does not know what these elements $e\_i$ look like, but we do know the $n^6$ elements $(a\_{i, j, k})\_{i, j, k = 1}^{n^2}$ of $K$ such that
$$
\forall i, j=1, \ldots, n^2 : e\_i \cdot e\_j = \sum\_{k=1}^{n^2} a\_{i, j, k}e\_k .
$$
One calls the $(a\_{i, j, k})\_{i, j, k=1}^{n^2}$ the structure constants of the basis. If $n > 1$ they do not uniquely determine the $e\_i$: if $S \in \mathbb{M}\_n(K)$ is invertible, then the basis of $\mathbb{M}\_n(K)$ given by $(S^{-1}e\_iS)\_{i=1}^{n^2}$ has the same structure constants. By the Skolem-Noether Theorem, the converse also holds: if $(e\_i')\_{i=1}^{n^2}$ is another basis with the same structure constants, then we have for all $i$ that $e\_i' = S^{-1}e\_iS$ for some invertible $S \in \mathbb{M}\_n(K)$.

It follows that norm and trace (even characteristic polynomial) of the $e\_i$ are uniquely determined by these structure constants. But how to calculate them?

Answer: 
Yes, it's possible.

Let $M^{i,j}\in \mathbb{M}\_n(K)$, where $1\leq i,j\leq n$, be the matrix which has $1$ at the intersection of $i$-th row and $j$-th column. Then if $B\in \mathbb{M}\_n(K)$ is a matrix with entries $b\_{k,l}$, then $B\cdot M^{i,j} = \sum\_{k=1}^n b\_{k,i}M^{k,j}$. It means that if we consider the linear operator $\text{ad}\_B: \mathbb{M}\_n(K)\to \mathbb{M}\_n(K)$ given by $\text{ad}\_B (X) = B\cdot X$, then in the basis $(M^{1,1}, M^{2,1}, \dots, M^{n,1}, M^{1,2}, \dots \dots, M^{n,n})$, the matrix of $\text{ad}\_B$ is $n^2\times n^2$ matrix with $n$ copies of matrix $B$ along the main diagonal and zeros everywhere else. The trace of this matrix is $n~\text{tr }B$, the determinant is $(\det B)^n$, and the characteristic polynomial is the $n$-th power of the characteristic polynomial of $B$.

This can be used to find traces and determinants of $e\_i$. In the basis $(e\_k)\_{k=1}^{n^2}$, the matrix of $\text{ad}\_{e\_i}$ has entries $(\text{ad}\_{e\_i})\_{j,k} = a\_{i,k,j}$. Since trace, determinant and characteristic polynomial of an operator are basis-independent, the trace etc. of this matrix are related to the trace etc. of $e\_i$ as described above. If the characteristic of $K$ does not divide $n$, then you can compute $\text{tr }e\_i$ as $\frac1n\text{tr ad}\_{e\_i}$. If $K$ has no $n$-th roots of unity other than $1$, then you can compute $\text{det }e\_i$ as $\sqrt[n]{\det\text{ad}\_{e\_i}}$. Otherwise, you can compute the characteristic polynomial of $e\_i$ as the $n$-th root of the characteristic polynomial of $\text{ad}\_{e\_i}$ which is a monic polynomial, and then you can find the trace and determinant of $e\_i$ from its characteristic polynomial.

The same approach works for any linear combination of $e\_i$.
The determinant of an element $A\in M\_n(K)$ can be computed by looking at $A$ in isolation. To compute this we don't even use the fact that $M\_n(K)$ is a $K$-vector space, much less the algebra structure. So a different algebra structure will have no influence on any determinant values: however the property $\det(AB) =\det(A)\det(B)$ will not be valid for other algebra structures.