Linear algebra around a configuration of lines in the plane

I heard a very nice problem from Hossein Movasati:

Consider a set \(L\) of \(n \ge 3\) lines in the plane in general position, that is, such that any two intersect in a point and no three are concurrent. Let \(V\) be the free Abelian group of formal integral linear combinations of the \(\binom{n}{2}\) points of intersection. For each line \(l \in L\), consider the alternating sum \(v(l) \in V\) of the intersection points of \(l\) with the other lines (ordered as you meet them going along \(l\), so that \(v(l)\) is defined up to choice of sign). The lines in \(L\) divide the plane into \(\binom{n}{2} + \binom{n}{1} + \binom{n}{0}\) regions¹, let \(P\) be the set of those regions that are bounded polygons. There are \(2n\) unbounded regions, and thus \(\binom{n}{2}-n+1\) bounded ones. For each \(p \in P\) let \(w(p) \in V\) be the sum of the vertices of \(p\). Then the subgroup \(K := \langle v(l) : l \in L \rangle + \langle w(p) : p \in P \rangle\) of \(V\) is of full rank and the quotient \(V/K\) is annihilated by \(n\).

The problem is taken from his 2004 paper Center conditions: Rigidity of logarithmic differential equations published in the Journal of Differential Equations, where he comments that it would make a “nice high school problem” (meaning that it is more elementary that the way he discovered it). He later wrote an article in German, Picard-Lefschetz-Theorie der Anordnungen², describing the problem and its origin.

In this note I’ll explain an alternative solution that proves that \(V/K \cong (\mathbb{Z}/n\mathbb{Z})^{n-2}\).

The \(w(p)\) for \(p \in P\) are linearly independent.

Without loss of generality we can assume that the horizontal coordinates of all all \(\binom{n}{2}\) points of intersection of lines in \(L\) are distinct (else rotate the lines a tiny bit). Assume \(\sum_{p \in P} \beta(p) w(p) = 0\). Consider all vertices \(x\) of polygons \(p\) such that \(\beta(p) \neq 0\) and pick the \(x\) furthest to the right. Then \(x\) is a vertex of only one polygon \(p\) with \(\beta(p) \neq 0\) which contradicts that the coefficient of \(x\) in \(\sum_{p \in P} \beta(p) w(p)\) is zero.

Define a bilinear form³ on \(V\) by \(u \cdot v = 0\) for \(u \neq v\) and \(u \cdot u = 1\) for the basis consisting of the points of intersection. This bilinear form has the following properties:

\(v(l) \cdot v(m) = \pm 1\) for \(l \neq m\).
\(v(l) \cdot v(l) = n-1\).
\(v(l) \cdot w(p) = 0\) because if \(l\) meets \(p\) at all it does so in two consecutive vertices on \(l\) which get opposite signs in \(v(l)\).

The most important thing to know is that there is only one linear relation between the \(v(l)\). We’ll show this using the bilinear form defined above.

The signs of the \(v(l)\) can be chosen so that \(\sum_{l \in L} v(l) = 0\). Once that is done, then in any linear combination \(\sum_{l \in L} \alpha(l) v(l) = 0\) all \(\alpha(l)\) must be equal.

Pick signs arbitrarily for the \(v(l)\), we will modify them later to ensure \(\sum_{l \in L} v(l) = 0\). Assume that \(\sum_{l \in L} \alpha(l) v(l) = 0\).

Each point of intersection \(x\) of lines in \(L\) is on exactly two lines, say \(r_x\) and \(s_x\). So looking at the coefficient of \(x\) in \(\sum_{l \in L} \alpha(l) v(l)\) we get either the equation \(\alpha(r_x) = \alpha(s_x)\) or we get the equation \(\alpha(r_x) = - \alpha(s_x)\). Since any pair of lines is \(\{r_x, s_x\}\) for some \(x\), these equations shows there is at most one linear combination (up to scalar multiples) of the \(v(l)\) that results in \(0\), and also that if there is any nontrivial relation at all, then it is possible to choose the signs so that \(\sum_{l \in L} v(l) = 0\).

So we’ve shown that, working over the rationals, the subspace \(\langle v(l) : l \in L \rangle_{\mathbb{Q}}\) has dimension \(n-1\) or \(n\) (recall that \(n\) is the number of lines in \(L\)); and we must eliminate the case of dimension \(n\). This subspace is contained in the orthogonal complement of \(\langle w(p) : p \in P \rangle_{\mathbb{Q}}\), which by the first lemma is of dimension \(|P| = \binom{n}{2}-n+1\) and thus has an \((n-1)\)-dimensional orthogonal complement.

From now on we assume the signs of the \(v(l)\) chosen as in the lemma. Notice that now \(v(l) \cdot v(m) = -1\) for any pair of distinct lines \(l\) and \(m\).

The subgroups \(K_L := \langle v(l) : l \in L \rangle\) and \(K_P := \langle w(p) : p \in P \rangle\) satisfy \(K_L \cap K_P = 0\).

If \(\sum_{l \in L} \alpha(l) v(l) = \sum_{p \in p} \beta(p) w(p)\), take the inner product with \(v(m)\) to get \((n-1)\alpha(m) - \sum_{l \neq m} \alpha(l) = 0\). So \(n \alpha(m) = \sum_{l \in L} \alpha(l)\) is independent of \(m \in L\) which means all \(\alpha(m)\) are equal and so the left hand side, \(\sum_{l \in L} \alpha(l) v(l)\), is zero.

Putting this all together we have proved what we wanted for the rational version of the problem at least:

We have \(\dim (K_L \otimes \mathbb{Q}) = |L|-1 = n-1\), \(\dim (K_P \otimes \mathbb{Q}) = |P| = \binom{n}{2} - n + 1\) and \(K \otimes \mathbb{Q} \cong (K_L \otimes \mathbb{Q}) \oplus (K_P \otimes \mathbb{Q}) \cong V \otimes \mathbb{Q}\).

This means that \(V/K\) is a finite Abelian group. Let’s figure out which one!

The key observation is that for any \(l\) and \(m\), distinct or not, we have \(v(l) \cdot v(m) \equiv -1 \pmod{n}\). This means that for any pair of distinct lines \(l\) and \(m\) the element \(u = v(l) - v(m)\) satisfies \(u \cdot v(k) \equiv 0 \pmod{n}\) for all \(k \in L\) and also \(u \cdot w(p) = 0\) for all \(p \in P\).

Let \(L = \{l_0, \ldots, l_{n-1}\}\). Define a group homomorphism \(\phi : V \to \mathbb{Z}^{n-2}\) by \(\phi(x) := (x \cdot (v(l_1) - v(l_0)), \ldots, x \cdot (v(l_{n-2}) - v(l_0)))\). Notice we did not use \(l_{n-1}\) in defining \(\phi\).

We’ll need a few special values of \(\phi\).

For \(1 \le i \le n-2\), let \(e_i = (0, \ldots, 0, 1, 0, \ldots, 0) \in \mathbb{Z}^{n-2}\) with the \(1\) in the \(i\)-th coordinate. We have:

V₀. \(\phi(l_0) = -(n,n,\ldots,n)\) and \(\phi(l_{n-1}) = (0,0,\ldots,0)\).

V₁. For \(i = 1, \ldots, n-2\), \(\phi(v(l_i)) = n e_i\).

V₂. For any \(p \in P\), \(\phi(w(p)) = 0\).

V₃. For \(i = 1, \ldots, n-2\), \( \phi(x_i) = \pm e_i\) where \(x_i := l_i \cap l_{n-1}\). (The sign is given by the coefficient of \(x_i\) in \(v(l_i)\), i.e., \(\phi(x_i) = (x_i \cdot v(l_i)) e_i\).)

This is straightforward to check.

Let \(\bar\phi : V \to (\mathbb{Z}/n\mathbb{Z})^{n-2}\) be the reduction modulo \(n\) of \(\phi\). We will show that \(\bar\phi\) is surjective and that \(\ker\bar\phi = K\); together these show that \(V/K \cong (\mathbb{Z}/n\mathbb{Z})^{n-2}\).

By V₃, not only \(\bar\phi\) but already \(\phi\) is surjective.

By V₀-V₂, \(K \subseteq \ker\bar\phi\).

Now assume \(\bar\phi(v) = 0\) for some \(v \in V\). We must show \(v \in K\). By V₁, we can add some vector in \(K_L\) to \(v\) if necessary, to ensure that \(\phi(v) = 0 \in \mathbb{Z}^{n-2}\). The only thing left to prove now is that \(\ker\phi \subset K\).

In fact, we will show that \(\ker \phi = \langle v(l_{n-1}) \rangle \oplus K_P =: K' \). Indeed, by V₀ and V₂, \( \ker \phi \) contains \(v(l_{n-1})\) and all \(w(p)\) and thus \(K' \subseteq \ker \phi\). Now, \(K'\) is free Abelian of rank \( |P|+1 = \binom{n}{2} - n + 2\), and since \( V/\ker \phi \cong \mathop{\mathrm{im}} \phi = \mathbb{Z}^{n-2}\) we see that \(\ker \phi\) is also free Abelian with rank equal to \( \mathop{\mathrm{rank}} V - (n-2) = \binom{n}{2} - n + 2\). This implies that given any \( v \in \ker \phi \), there is some multiple \( \lambda v \in K' \), say \( \lambda v = \alpha v(l_{n-1}) + \sum_{p \in P} \beta(p) w(p) \). Taking the inner product with \(v(l_0)\) shows that \(\alpha\) is divisible by \(\lambda\). This shows that \( \sum_{p \in P} \bar\beta(p) w(p) = 0 \) where \( \bar\beta(p) \in \mathbb{Z}/\lambda \mathbb{Z}\) is the mod \(\lambda\) reduction of \(\beta(p)\). By the first lemma, whose proof also works mod \(\lambda\), we see that for all \(p \in P\), \(\beta(p)\) is divisible by \(\lambda\). Now that all coefficients \(\alpha\) and \(\beta(p)\) have been shown to be divisible by \(\lambda\), it follows that \(v \in K'\) as desired.

See Cut the Knot for both an OK proof and a pretty one

Picard-Lefschetz theory of arrangements.

Notice that Mosavati’s papers also define a bilinear form but it’s not the same as this one!