About an identity which gives immediate proof of the permanent lemma

Question

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?

Answer 1

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.