3
$\begingroup$

What is the number of terms of the unique multilinear polynomial $f\in\Bbb F_2[x_{1,1},\dots,x_{n,n}]$ in $n^2$ variables such that $f$ vanishes only on matrices that are permutations?

Are there good bounds?

Note that such a polynomial should have $S_n\times S_n$ symmetry.

I think one can even guess how such a polynomial should look like. It is just sum of $n!$ terms. However there could be unreasonable cancellations (at least under some mild error criteria). This could make the polynomial efficiently representable.

There are many many reasons I ask this. One reason is can there be unreasonable cancellations if we replace $\Bbb F_2$ by $\Bbb R$ (note either $1\in\Bbb F_2$ translates to $\neq0$ in $\Bbb R$ and $0\in\Bbb F_2$ translates to $=0$ in $\Bbb R$ or $1\in\Bbb F_2$ translates to $<0$ in $\Bbb R$ and $0\in\Bbb F_2$ translates to $>0$ in $\Bbb R$ are variations)?

$\endgroup$

1 Answer 1

8
$\begingroup$

For any permutation $\sigma\in S_n$ let's define $X(\sigma)=\prod_{i=1}^n x_{i\sigma(i)}$ and $Y(\sigma)=\prod_{i=1}^n\prod_{j\neq\sigma(i)}(1+x_{ij})$.


Lemma: Our polynomial can be written explicitly as $$f(x_{ij})=1+\sum_{\sigma\in S_n}X(\sigma)Y(\sigma)$$ To prove this notice that $X(\sigma)Y(\sigma)=1$ if and only if the $(x_{ij})$ matrix represents $\sigma$.


Let us now write the monomial expansion $$f(x_{ij})=1+\sum_{A\in M_n(\mathbb F_2)}c(A)x^A$$ where $c(A)\in \mathbb F_2$ and $A$ runs over all $n\times n$ matrices with $\{0,1\}$ entries. Here I am using the short hand notation $x^A$ to represent the monomial $\prod_{ij} x_{ij}^{A_{ij}}$.

When we expand the product $X(\sigma)Y(\sigma)$ we see that a term $x^A$ appears if and only if $\prod_{i=1}^n A_{i\sigma(i)}=1$. For a given $A$, let $S(A)$ denote the set of all $\sigma\in S_n$ for which $\prod_{i=1}^n A_{i\sigma(i)}=1$.

From the Lemma we see that $c(A)=|S(A)|\pmod{2}$. In other words $c(A)=\det(A)$.

We conclude that the number of nonzero terms in $f$ is $1+$ the number of matrices $A$ which satisfy $c(A)=1$ which, in turn, is equivalent to $\det{A}\neq 0$. So we get

$$1+|\operatorname{Gl}_n(\mathbb F_2)|=1+2^{\binom{n}{2}}\prod_{i=1}^n (2^i-1).$$

$\endgroup$
0

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.