Let $V$ be the space of pairs of $n \times n$ matrices over $\mathbb{C}$ and let $G$ be the space of $n \times n$ permutation matrices which acts on $(A,B) \in V$ by simultaneous conjugation. It is obvious that for any $i, j \in \mathbb{N}$, $Tr(A^i \cdot B^j)$ is an invariant under this group action. Does there exist a set $S \subseteq \{(i,j) : 0 \le i, j \le n^{1/2}\}$ such that $|S| = \Theta(n)$ and the invariants $\{Tr(A^i \cdot B^j) : (i,j) \in S\}$ are algebraically independent? 


(The earlier question incorrectly said that invariants of the form $Tr(A^i \cdot B^j)$ generate all the invariants. That is false as indicated by the comments below. Also, the earlier question asked if $\{Tr(A^i \cdot B^j) : 0 \le i, j \le \sqrt{n}\}$ are algebraically independent. That however is not true as Robert Bryant indicates: You need to remove some of the extreme cases. However, I am interested in the presence of a large number of low-order algebraically independent invariants and hence I am editing the question). 



Algebraically independent matrix invariants
If $n$ is prime, I will show that $Tr(A^r B^s)\_{1 \leq r \leq n,\ 0 \leq s \leq n-1}$ is algebraically independent. This is one less the potentially optimal $n^2+1$, since all such traces live in the ring of $GL\_n$ conjugacy invariants and that ring has dimension $n^2+1$. Since smaller matrices include into larger matrices, this shows that $Tr(A^r B^s)\_{1 \leq r \leq p,\ 0 \leq s \leq p-1}$ is independent where $p$ is any prime less than $n$. By Bertrands postulate, this gets me up to at least $(n/2)^2$ (and $n^2(1-o(1))$ for $n$ large). I suspect that the stated list is always algebraically independent, but I don't want to work more on this.


We recall the use of Jacobian determinants to establish algebraic independence: If $f\_1$, $f\_2$, ..., $f\_r$ are polynomials in variables $x\_1$, $x\_2$, ..., $x\_r$ (and possibly other variables as well), and there is a polynomial relationship between the $f\_i$, then $\det(\partial f\_i/\partial x\_j)$ will be identically zero. (Proof sketch: Implicit differentiation of the polynomial relation.) Thus, if I show that this determinant is nonzero at any point, it shows that the $f\_i$ are algebraically independent.


The indices of my matrices will always be modulo $n$. I will consider the above traces as functions of the $n^2$ variables $A\_{ii}$, for $1 \leq i \leq n$, and $B\_{jk}$ for $1 \leq i,j \leq n$, $k \not \equiv j+1 \bmod n$. I will evaluate the Jacobian at
$$A = \begin{pmatrix} \alpha\_1 & & & \\ & \alpha\_2 & & \\ & & \ddots & \\ & & & \alpha\_n \end{pmatrix} \qquad B=\begin{pmatrix} & 1 & & \\ & & \ddots & \\ & & & 1 \\ 1 & & & \end{pmatrix}$$
where the $\alpha$'s are distinct and nonzero and all unlabeled entries are $0$.


First, observe that (among the variables we are differentiating with respect to), $Tr(A^r)$ depends only on the $A\_{ii}$. Therefore, the monomials $Tr(A^r)$ and the variables $A\_{ii}$ form an $n \times n$ block in our $n^2 \times n^2$ matrix, and it is well known that this block is invertible whenever the $\alpha\_i$ are distinct. So we can concentrate instead on the $(n^2-n) \times (n^2-n)$ matrix which uses the monomials $Tr(A^r B^s)\_{1 \leq r \leq n,\ 1 \leq s \leq n-1}$ and the variables $B\_{jk}$, $k \not \equiv j+1 \bmod n$.


Fix $s$ and think about $Tr(A^r B^s)\_{1 \leq r \leq n} = \sum\_i \alpha\_i^r (B^s)\_{ii}$. As $r$ varies, we get $n$ different linear combinations of the quantities $(B^s)\_{ii}$. 
Since the $\alpha$'s are distinct and nonzero, this linear transformation is invertible, so we may think instead about the $n^2-n$ functions $((B^s)\_{ii})\_{1 \leq s \leq n-1,\ 1 \leq i \leq n}$.


Let $k \not \equiv j+1 \bmod n$ and consider $\partial ((B^s)\_{ii})/\partial B\_{jk}$, evaluated at the $B$-matrix above. It will be zero unless $j \equiv k+s-1 \bmod n$ and $(k,i,j)$ are weakly circularly ordered. In that latter case, it will be $1$.


Thus, the $(n^2-n) \times (n^2-n)$ Jacobian breaks into $n \times n$ blocks. For each block, we fix and $s$ and look at the $n$ functions $(B^s)\_{ii}$ and the $n$ variables $B\_{jk}$, $j \equiv k+s-1 \bmod n$. This block looks like 
$$\begin{pmatrix}
1 & 1 & 1 & 0 & 0 & \cdots & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & \cdots & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & \cdots & 0 & 0 & 0 \\
& & & & & \ddots & & & \\
0 & 0 & 0 & 0 & 0 & \cdots & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & \cdots & 0 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 & \cdots & 0 & 0 & 1 \\
\end{pmatrix}.$$
Here there are $s$ ones and $n-s$ zeroes in each row.
The eigenvalues of this circulant matrix are $1+\zeta+\zeta^2+ \cdots + \zeta^{s-1}$ when $\zeta$ runs through the $n$-th roots of unity (including $1$). If $n$ is prime, all these sums are nonzero, so the determinant is nonzero and we win.


