The first guess is correct and follows directly from the permutation expansion of the determinant. The second guess is also correct. The generalization is
$$\text{tr}^{(n)}(A) = \text{tr } \Lambda^n(A) = \frac{1}{n!} \sum_{\pi \in S_n} \text{sgn}(\pi) \text{tr}_{\pi}(A)$$
where $\Lambda^n(A)$ is the action of $A$ on the exterior power $\Lambda^n$, $\text{tr}_n(A) = \text{tr}(A^n)$ and, for a permutation $\pi$ with cycle type $(\lambda_1, ... \lambda_k)$, we define $\text{tr}_{\pi} = \text{tr}_{\lambda_1} ... \text{tr}_{\lambda_k}$.
For example, $S_3$ has one element with cycle type $(1, 1, 1)$, three elements with cycle type $(1, 2)$, and two elements with cycle type $(3)$. It follows that
$$\text{tr}^{(3)}(A) = \frac{1}{6} \left( \text{tr}(A)^3 - 3 \text{tr}(A^2) \text{tr}(A) + 2 \text{tr}(A^3) \right).$$
This identity is really an identity of symmetric functions expressing the elementary symmetric functions in terms of the power symmetric functions. It can be deduced from Newton's identities or the exponential formula. You can find a more thorough exposition in Stanley's Enumerative Combinatorics, Vol. II, Chapter 7.
Some exposition is in order regarding what this has to do with exterior powers. Suppose that $A$ is diagonalizable with eigenvalues $\lambda_1, ... \lambda_n$ and eigenvectors $e_1, ... e_n$. Then of course $\text{tr}(A) = \sum \lambda_i$. More generally $\text{tr}^{(k)}(A) = \sum_{i_1 < ... < i_k} \lambda_{i_1} ... \lambda_{i_k}$ is the $k^{th}$ elementary symmetric polynomial in the eigenvalues.
Now, if $A$ acts on a vector space $V$, then the exterior power $\Lambda^k(V)$ inherits an action of $A$ by functoriality. In this basis, it is particularly easy to describe: it is given by
$$\Lambda^k(A)(e_{i_1} \wedge ... \wedge e_{i_k}) = \lambda_{i_1} ... \lambda_{i_k} e_{i_1} \wedge ... \wedge e_{i_k}.$$
Hence the wedges of all possible ordered $k$-tuples of distinct eigenvectors of $A$ forms an eigenbasis for $\Lambda^k(A)$ acting on $\Lambda^k(V)$. It follows that $\text{tr } \Lambda^k(A) = \text{tr}^{(k)}(A)$ for all diagonalizable $A$, hence for all $A$ by continuity. Of course you can ignore all of this if you want to, but I thought I would mention it because it is a precise sense in which the other coefficients of the characteristic polynomial encode "higher traces."
You can use the Caley-Hamilton theorem. Put your matrix in the characteristic polynomial and you should find $0$. Explicitly, $\chi_A(A) = A^n + a_{n-1}A^{n-1}+\cdots + a_0I=0$. This checks the
characteristic polynomial, the minimal polynomial and the eigenvalues. The only thing not checked is the dimension of the eigenspace, and the eigenvectors.
Of course this checking is simple, if your software computes matrix algebra.
Best Answer
Let $A=\begin{bmatrix} a & b \\ c & d \end{bmatrix}$.
Than it's characteristic equation is given by $|A-xI|=0$
i.e. $\begin{vmatrix} a-x & b \\ c & d-x \end{vmatrix}=0$
On solving the determinant : $(a-x)(d-x)-cb=0 \implies x^2-\underbrace{(a+d)}_{ tr.(\text{A})}x+\underbrace{(ad-cb)}_{\det(A)}=0$
Here $a+d = tr.(\text{A}), ~ad-cb = \det{(A)}$