Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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