7
$\begingroup$

Let $A$ be a $n \times n$ matrix over field $F$. Let $a_1, \cdots, a_n$ be the column vectors of $A$. For any subset $S \subseteq [n] = \{1, 2, \cdots, n\}$, let $a_S = \sum_{i \in S} a_i$. Alon's celebrated permanent lemma states that if the permanent of $A$ is nonzero, then for any $b \in F^n$ there is some set $S$ such that $a_S$ and $b$ differs in all coordinates.

Let $v_S = \prod_{i=1}^n (a_{S,i} - b_i)$. Then $v_S \neq 0$ iff $a_S$ and $b$ differ in all coordinates. By attempting to prove the lemma by my own, I discovered this identity. $$\sum_{S \subseteq [n]} (-1)^{n-|S|} v_S = \operatorname{perm} A$$ So $\operatorname{perm} A \neq 0$ immediately implies the existence of some $v_S \neq 0$. Note that the formula of left-hand side depends on $b$.

If we are working on a field with absolute value, then the absolute value of $v_S$ measures the difference between $a_S$ and $b$ in coordinates. For example, there is a set $S$ with $|v_S| \geq (\operatorname{perm} A) / 2^n$. The bound is tight for $A = I_n$ and $b = (1/2, \cdots, 1/2)$. This gives a quantitative version of permanent lemma.

Given the simplicity of the identity, I believe that it should had been noticed by other mathematicians. In what literature can I find observations about this identity? Are there any generalizations or applications around this idea?

$\endgroup$

1 Answer 1

8
$\begingroup$

This identity is a particular case of theorem 3 in "A generalization of Combinatorial Nullstellensatz" by Michał Lasoń. Indeed your proof is essentially reinventing the combinatorial nullstellensatz. :)

The usual proof of Alon's lemma looks at the polynomial $\prod_{i=1}^n (\sum_j a_{ij}x_j - b_i)$. And your identity follows by computing the coefficient of $x_1x_2\cdots x_n$ in two different ways, like in the paper above.

$\endgroup$

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.