Assume that $V$ is a $n$-dimensional $k$-vector space where, $k$ is an algebraically closed field. Furthermore, assume that $T: V \rightarrow V$ is an endomorphism such that with respect to an ordered basis $\cal{B} \subset V$ has an invertible matrix representation $A$. Given another invertible matrix $B$, can we find a basis of $V$ such that the matrix of $T$ with respect to that new basis is $B$?
I don't mind if we need further assumptions to be made (for instance if $A$ and $B$ are upper triangular, etc.).
In general, no. Changing basis transforms the matrix representation of an endomorphism (of a f.d. vector space) by similarity, that is, by a map $$A \mapsto P A P^{-1}$$ for some $P$, and every choice of $P$ corresponds to a change of basis. Thus, given a linear transformation $T$ with matrix representation $A$ with respect to some basis and a matrix $B$, there is a basis with respect which $T$ has representation $B$ iff $A$ and $B$ are similar.
On the other hand, $A, B$ are similar iff they have the same Jordan Canonical Form (up to reordering of blocks), and this yields an algorithm for deciding which $A, B$ we can do this.