2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David E Speyer Aug 20 '15 at 15:13
  • 4
    $\begingroup$ 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$. $\endgroup$ – Ehud Meir Aug 20 '15 at 15:15
  • 2
    $\begingroup$ 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. $\endgroup$ – Robert Bryant Aug 20 '15 at 15:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Robert Bryant Aug 20 '15 at 16:08
  • 1
    $\begingroup$ 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. $\endgroup$ – David E Speyer Aug 20 '15 at 18:12
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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})$. $\endgroup$ – David E Speyer Aug 21 '15 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.