@darijgrinberg Thanks, your proof seems to work! You do use implicitly that $\lambda$ has distinct parts, since otherwise $Q_\lambda$ is zero, not $2^{\ell(\lambda)}P_\lambda$, so part 2 doesn't work anymlore (for example $P_{(1,1)}=\frac{1}{2}(p_1^2-p_2)$ so this hypothesis is really needed). Except for that, though, everything looks correct, so if you want to turn your comments into an answer I'll happily accept it.

Thanks for your comment! That seems equivalent to my question actually, since unless I'm mistaken the $P_\lambda$ (for arbitrary $\lambda$) form a $\mathbb{Z}$-basis for $\Lambda$, and in particular those with $\lambda$ having distinct parts form a $\mathbb{Z}$-basis for $\Lambda \cap \mathbb{Q}[p_1,p_3,p_5,\cdots]$.

Can you expand a bit more on what you want? How can a choice of $g$ show that $f \in \sqrt{I}$?

I see, I thought you authorized $u=v$

Yeah you're right so that really only works for characteristic 2. I think that the main claim in my proof is actually false in other characteristics.

$y+z-x\in \{0,1\}^n$ does not assume that $A$ contains zero in characteristic 2, it follows from $\{0,1\}^n$ being an $\mathbb{F}_2$ subspace (if $A$ contains zero then my argument works in any characteristic actually but that's not needed for characteristic 2).

I guess you want to exclude the graph with a unique vertex. In this case the minimal number of vertices is 5 ($K_5$ has two edge-disjoint hamiltonian cycles). It's easy to check that 4 or less is impossible.

Another quite surprising property is that the characteristic polynomial is symmetric in the $\mu_i$, that is, the eigenvalues are independent of the order in which the multiplication is done. I wonder what explains that.

The matrix for a fixed $\lambda$ is diagonalizable, but there is no base that simultaneously (block-)diagonalize all $A(\lambda)$

I think you also need to exclude the case of four eigenvalues $\lambda, -\lambda, \frac{1}{\lambda},-\frac{1}{\lambda}$ all real.

Hahaha ok that explains it. Using sage I got, for $n=3$, $k_1^2k_2^2k_3^2+\sum_{sym} (k_1^2k_2^2 +2k_1^2k_2k_3+4k_1^2+4k_1k_2) +18$ for the coefficient of $t^2$

@მამუკაჯიბლაძე Are you sure? I computed it for $n=3$ and got something completely different (the coefficient of $t^2$ is a messy polynomial in $\mu_1, \mu_2, \mu_3$)