8
$\begingroup$

Let $V = \mathbb{C}^m$, endowed with the standard hermitian inner product which we will denote by $\langle \cdot, \cdot \rangle$, $n$ be a positive integer and $\Sigma_n$ denote the symmetric group on $\{1, \ldots, n\}$. Denote by $$ T = \bigotimes_{i = 1}^n V,$$ namely $T$ is the tensor product (over $\mathbb{C}$) of $n$ copies of $V$. If $G$ is a subgroup of $\Sigma_n$, we associate to $G$ the following linear map $\pi_G$ from $T$ to itself, mapping $$v = v_1 \otimes \cdots \otimes v_n \in T$$ where each $v_i \in V$, to $$\pi_G(v) = \frac{1}{|G|}\left( \sum_{\sigma \in G} \bigotimes_{i=1}^n v_{\sigma^{-1}(i)} \right).$$ We also denote the image of $\pi_G$ by $T_G \subseteq T$, and remark that $\pi_G$ is an orthogonal projection from $T$ onto $T_G$, with respect to the hermitian inner product on $T$ induced by the hermitian inner product $\langle ., \rangle$ on $\mathbb{C}^m$. We will also use the same notation for the induced hermitian inner product on $T$, by abuse of notation.

If $v_i \in \mathbb{C}^m$ for $i = 1, \ldots, n$ are nonzero vectors, then their tensor product $$ v := v_1 \otimes \cdots \otimes v_n$$ is also non-zero. I claim that for any subgroup $G$ of $\Sigma_n$, $\pi_G(v) \neq 0$. First, if $G = \Sigma_n$, then the claim follows the fact that the ring of complex homogeneous polynomials in $m$ variables is an integral domain (in particular, there are no zero divisors). If $G$ is an arbitrary subgroup of $\Sigma_n$, then $$ \pi_{\Sigma_n}(\pi_G(v)) = \pi_{\Sigma_n}(v) \neq 0, $$ so that $\pi_G(v) \neq 0$, as claimed.

Let us say we are given two subgroup $G_1$ and $G_2$ of $\Sigma_n$. Let $v$ be, as above, the tensor product of $n$ nonzero vectors $v_i \in \mathbb{C}^m$ for $i = 1, \ldots, n$. Let $$ w := \pi_G(v)$$ where $G$ is the subgroup of $\Sigma_n$ containing $G_1$ and $G_2$.

Question 1: is it true that $$ \Re \langle \pi_{G_1}(v), \pi_{G_2}(v) \rangle > 0 \text{?}$$

If so, then I would have a proof of Do these cousins of permanents satisfy the following inequality?

Actually, some numerical testing seems to possibly suggest the following stronger (conjectural) inequality. Assume that each of $G_1$, $G_2$ is a product of symmetric groups corresponding to two partitions of $\{1, \ldots, n\}$ respectively. So for example, if $n = 6$ and we partition $\{1, \ldots, 6\}$ as the disjoint union of, say, $\{1, 2, 3\}$, $\{4, 5\}$ and $\{6\}$, then the corresponding subgroup of $\Sigma_n$ is the symmetric group on $\{1, 2, 3\}$ times the symmetric group on $\{4, 5\}$ times the symmetric group on $\{6\}$. Thus $G_1$ (resp. $G_2$) is a product of symmetric groups corresponding to a partition $\mathcal{P}_1$ (resp. $\mathcal{P}_2$) of $\{1, \ldots, n\}$. Note that $\mathcal{P}_1$ and $\mathcal{P}_2$ could be different, so that $G_1$ and $G_2$ need not be the same.

Question 2: under these assumptions, is it true that for any $v$ such as above, we have $$ \Re \langle \pi_{G_1}(v), \pi_{G_2}(v) \rangle \geq \frac{\lVert v \rVert^2}{|G_1| |G_2|} \text{?}$$

Note that without the above assumption on $G_1$ and $G_2$, the inequality in question 2 does not hold in general. Indeed, there is a counterexample if $n = 3$ and we take, say, $G_1 = \langle (123) \rangle$ and $G_2$ trivial, and we take $$ v_i = (1, \gamma^i)^T, $$ for $i = 1, \ldots, 3$, where $\gamma = e^{\frac{2 \pi i}{3}}$. This does not, however, constitute a counterexample to the conjecture in question 1.

Edit 1: I generalized the statement further. Let $H$ be a nonzero $N$ by $N$ hermitian positive semidefinite matrix and let $K_1$ and $K_2$ denote two subgroups of the symmetric group $S_N$. Assuming that

$$ \sum_{\sigma \in K} \operatorname{tr}(H P^{-1}_\sigma) \neq 0,$$ (and thus positive) for any subgroup $K$ of $S_n$, is it true that

$$ \Re \sum_{\sigma_1 \in K_1, \sigma_2 \in K_2} \operatorname{tr}(P_{\sigma_1} H P^{-1}_{\sigma_2}) > 0,$$ where $P_{\sigma_i}$ is the $N$ by $N$ permutation matrix representing $\sigma_i$, for $i = 1, 2$?

If true, the above statement should "just" be a matter of bookkeeping, so to speak. If false, well, it was worth a shot, as they say.

Note that if, say, $K_1$ is trivial and $K_2 = S_n$, then the LHS is nothing but the sum of all entries of $H$.

Added note: @DavidESpeyer found a counterexample to this optimistic generalization, see his answer below (thank you again). I was being too optimistic. But I am still interested in the main problem explained in the post, which is still open.

Edit 2: Here is a special case, where $G_1$ and $G_2$ are sort of similar to the ones used in @DavidESpeyer's answer, but for which the original statement (and not the generalized one for which David E Speyer found a counterexample) can be proved.

Let $v_i \in \mathbb{C}^m$ for $i = 1, \ldots, 3$ be nonzero vectors. I will not always write the tensor product (or, if you prefer, the Kronecker product), for brevity. Let $h_{ij} = \langle v_i, v_j \rangle$, for $i, j = 1, \ldots, n$.

We are interested, say, in the following quantity $$f(v_1, v_2, v_3) := \Re \langle v_1 v_2 v_3 + v_2 v_1 v_3, v_1 v_2 v_3 + v_1 v_3 v_2 \rangle.$$ This corresponds to $G_1 = \langle (12) \rangle$ and $G_2 = \langle (23) \rangle$. Expanding, we obtain $$ f(v_1, v_2, v_3) = h_{11} h_{22} h_{33} + h_{11} |h_{23}|^2 + |h_{12}|^2 h_{33} + \frac{1}{2} h_{21} h_{13} h_{32} + \frac{1}{2}h_{12} h_{31} h_{23}.$$

I claim that if $G$ is any subgroup of $\Sigma_n$, then $$ \sum_{\sigma \in G} \prod_{i=1}^n h_{i \sigma^{-1}(i)} = \frac{1}{|G|} \lVert \sum_{\sigma \in G} \bigotimes_{i=1}^n v_{\sigma^{-1}(i)} \rVert^2.$$ The previous is true in general, for any number $n$ of vectors $v_i$ in $\mathbb{C}^m$. It can be proved by expanding the RHS and then using the usual trick to transfer the permutation acting on the left index so that it becomes the inverse permutation acting on the right index.

In particular, if we chose $G = \langle (123) \rangle$, we get $$h_{11}h_{22}h_{33} + h_{12}h_{23}h_{31} + h_{13}h_{32}h_{21} = \frac{1}{3} \lVert v_1 v_2 v_3 + v_2 v_3 v_1 + v_3 v_1 v_2 \rVert^2$$ which is thus positive. Indeed, it can be proved that what is inside the norm squared is nonzero, assuming the $v_i$ are nonzero, for $i = 1, \ldots, 3$.

We finally deduce that $$f(v_1, v_2, v_3) > \frac{1}{2} h_{11} h_{22} h_{33}.$$ This proves our statement, in this very special case!

As a note, we have proved the following formula: $$f(v_1, v_2, v_3) = \frac{1}{2}\lVert v_1 \rVert^2 \lVert v_2 \rVert^2 \lVert v_3 \rVert^2 + \lVert v_1 \rVert^2 |\langle v_2, v_3 \rangle|^2 + |\langle v_1, v_2 \rangle|^2 \lVert v_3 \rVert^2 + \frac{1}{6} \lVert v_1 v_2 v_3 + v_2 v_3 v_1 + v_3 v_1 v_2 \rVert^2,$$ which expresses $f(v_1, v_2, v_3)$ as a sum of positive and nonnegative quantities.

One may obtain a sharper inequality than the above. Note that one has $$f(v_1, v_2, v_3) = h_{11}h_{22}h_{33} + \frac{1}{2}(\operatorname{perm}(H) - h_{11}h_{22}h_{33}) + \frac{1}{2}h_{11}|h_{23}|^2 + \frac{1}{2}|h_{12}|^2 h_{33}.$$

By Marcus's inequality, the term that is between parentheses on the RHS is nonnegative. We have thus proved the following sharper inequality:

$$f(v_1, v_2, v_3) \geq h_{11} h_{22} h_{33}.$$

So this sort of gives clues about the kind of tools needed, but I don't immediately see how to generalize the argument.

$\endgroup$
2
  • 3
    $\begingroup$ Feels like it must be related to Schur-Weyl duality, though I don't immediately see how... $\endgroup$ Oct 14, 2023 at 14:23
  • $\begingroup$ I feel that Halmos's two projections theorem could be relevant. I have just learned about it. It does illuminate the problem a lot. There is a positive contribution coming from the 00 component of $\mathbb{C}^n$, no contribution from the 01, 10 and 11 components but, the contribution from the last two components (the 0 and 1 components) may be negative, in some cases. If we start with a $v$ as in the post, it is not clear that the sum of these terms is always positive, i.e. it is not clear that the first term would dominate the last one, should the contribution of that last term be negative... $\endgroup$
    – Malkoun
    Oct 31, 2023 at 2:50

1 Answer 1

4
$\begingroup$

$\def\Tr{\text{Tr}}$The further generalization is not true. Take $N=3$, $K_1 = \langle (12) \rangle$ and $K_2 = \langle (23) \rangle$. Take $$H_0 = \begin{bmatrix} 1&-2&1 \\ -2&4&-2 \\ 1&-2&1 \end{bmatrix}.$$ Then $$\sum_{\sigma_1 \in K_1,\ \sigma_2 \in K_2} (\sigma_1 H_0 \sigma_2^{-1}) = \begin{bmatrix} -2 & 1 & 1 \\ -2 & 1 & 1 \\ 4 & -2 & -2 \\ \end{bmatrix}$$ with trace $-3$.

This isn't quite a counterexample, because $\sum_{\sigma \in S_3} \Tr(H_0 \sigma)=\sum_{\sigma \in A_3} \Tr(H_0 \sigma) = 0$. However, if we take $H = H_0 + \epsilon \text{Id}$ for some small $\epsilon$, then we obey the condition that $\sum_{\sigma \in K} \Tr(H \sigma) > 0$ for every subgroup $K$ of $S_3$, and we still have $\text{Tr} \sum_{\sigma_1 \in K_1,\ \sigma_2 \in K_2} (\sigma_1 H_0 \sigma_2^{-1}) < 0$.

Since I am not clear on the relation between this problem and the original problem about the pure tensor, I am not sure whether the original problem is also false.

$\endgroup$
3
  • $\begingroup$ Thank you so much for your contribution. Yes this is definitely a counterexample to my optimistic generalization, in which I erroneously thought that perhaps the fact that the vector space is a space of tensors does not play a role. But it is not a counterexample to my original conjecture. What happened is I generalized too much, so much that the generalized statement became false. It was worth a shot. I will upvote your contribution of course and I do thank you for it. But I am still interested in the main conjecture related to tensors. $\endgroup$
    – Malkoun
    Oct 16, 2023 at 13:05
  • $\begingroup$ It looks like it works to perturb $H_0$ to $(1\ -2.1\ 1)^T (1\ -2.1\ 1)$ instead, thus preserving the rank one condition. $\endgroup$ Oct 16, 2023 at 14:51
  • $\begingroup$ Ah ok, thank you! Yes, I also see numerically that the generalized statement does not work. So yes, even with the added rank $1$ hypothesis on $H$, it doesn't work (sorry for having deleted that comment). $\endgroup$
    – Malkoun
    Oct 16, 2023 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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