# Algebraically independent matrix invariants

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).

• I would expect $k \approx n$, not $n^{1/2}$. The space $V$ has dimension $2n^2$, and your are quotienting by a group of dimension $n^2$, so you should expect about $n^2$ invariants. – David E Speyer Aug 20 '15 at 15:13
• You actually need more invariants, because you need to consider also the noncommutative monomials: for example $Tr(A^{i_1}B^{j_1}A^{i_2}\ldots A^{i_m}B^{i_m})$. Procesi proved that the number of required monomials to generate the invariants is bounded by monomials of length $\leq 2^n - 1$. He also studied the relations between the invariants, see his paper "The invariant theory of $n\times n$ matrices", Advances in mathematics 19, 1976. If you look specifically on the monomials $Tr(A^iB^j)$ then I agree with David, and I would also guess that $k\approx n$. – Ehud Meir Aug 20 '15 at 15:15
• The OP is only dividing out by a finite group $G\simeq S_n$, so the maximum number of independent invariants is $2n^2$, not $n^2$. Also, don't you need to omit the trivial case $i=j=0$? For example, when $n=1$, one should take $i+j=1$, as $k=0$ is too small and $k=1$ is too large. – Robert Bryant Aug 20 '15 at 15:34
• The case $n=2$ is interesting: Setting $T_{ij}=Tr(A^i B^j)$, then $T_{10}$, $T_{01}$, $T_{20}$, $T_{11}$, and $T_{02}$ are independent, and this is the maximum number that could be independent because these are also invariants for the full conjugation action of $\mathrm{GL}(2,\mathbb{C})$. Even the noncommutative monomials will be invariant under the action of $\mathrm{GL}(2,\mathbb{C})$, so there is no hope of getting $8$ independent invariants under $G\simeq S_n$ in this way. – Robert Bryant Aug 20 '15 at 16:08
• Whether the OP is thinking about dividing by $S_n$ or $GL_n$, all the functions being considered are invariant for $GL_n$, so they live in a ring of dimension $n^2+1$ (the $+1$ is because the center of $GL_n$ is one dimensional and acts trivially.) So we can't get more than $n^2+1$ algebraically independent quantities from this set. – David E Speyer Aug 20 '15 at 18:12

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.

• A modification which I don't feel like editing into the original: For $n$ prime, the invariants $Tr(A^i B^j)$ with $0 \leq i,j \leq n-1$ and $(i,j) \neq (0,0)$, together with $Tr(A^n)$ and $Tr(B^n)$ provide $n^2+1$ algebraically independent functions. Proof: Copy the above and, in addition, consider differentiation with respect to $B_{n1}$. You get $n$ blocks of size $n \times n$ as before, and a $1 \times 1$ block in position $(Tr(B^n), B_{n1})$. – David E Speyer Aug 21 '15 at 16:00