When are powers of square matrices linearly independent? If I have an $n$-by-$n$ matrix $A$, is $1, A, A^2,...,A^{n^2}$ always linearly independent?

No, never, because the space of $n\times n$ matrices has dimension $n^2$ and you have $n^2+1$ matrices there.