Bilinear systems with two supports:

Koszul resultant matrices, eigenvalues, and eigenvectors

By Matías R. Bender, Jean-Charles Faugère, Angelos Mantzaflaris, and Elias Tsigaridas

Download example data

Example of solving

Consider $S_x(d_x) := \mathbb{K}[x_0,x_1]_{d_x}$, $S_y(d_y) := \mathbb{K}[y_0,y_1]_{d_y}$, and $S_z(d_z) := \mathbb{K}[z_0,z_1]_{d_z}$; and let $S(d_x,d_y,d_z) := S_x(d_x) \otimes S_y(d_y) \otimes S_z(d_z)$ be the space of multihomogeneous polynomials of multidegrees $(d_x,d_y,d_z)$.

We want to solve the multihomogeneous system given by the polynomial $$ \left\{ \begin{array}{lll} f_1 := & \!\quad 7 \, x_0 y_0 - 8 \, x_0 y_1 - \, x_1 y_0 + 2 \, x_1 y_1 & \in S(1,1,0) \\ f_2 := & - 5 \, x_0 y_0 + 7 \, x_0 y_1 - \, x_1 y_0 - \,\; x_1 y_1 &\in S(1,1,0) \\ f_3 := & - 6 \, x_0 z_0 + 9 \, x_0 z_1 - \, x_1 z_0 - 2 \, x_1 z_1 & \in S(1,0,1) \end{array} \right. . $$

This system has $2$ solutions over $\mathbb{P}^1 \otimes \mathbb{P}^1 \otimes \mathbb{P}^1$, $$ \left\{ \begin{array}{ll} \alpha_1 := & (1\!:\!1 \;;\; 1\!:\!1 \;;\; 1\!:\!1) \\ \alpha_2 := & (1\!:\!3 \;;\; 1\!:\!2 \;;\; 1\!:\!3) \end{array} \right. . $$

We introduce a trilinear polynomial $$ f_0 := 3 \, x_{0} y_{0} z_{0} - x_{0} y_{0} z_{1} - 4 \, x_{0} y_{1} z_{0} + 2 \, x_{0} y_{1} z_{1} + x_{1} y_{0} z_{0} + 2 \, x_{1} y_{0} z_{1} + 2 \, x_{1} y_{1} z_{0} - 2 \, x_{1} y_{1} z_{1}. $$

We pick the degree vector $(0,-1,1)$, and consider the Weyman complex $K_\bullet((f_0,f_1,f_2,f_3),(0,-1,1))$
This complex reduces to $$ %% K_\bullet((f_0,f_1,f_2,f_3),(0,-1,1)) : \\ 0 \rightarrow \begin{matrix} (S_x(1)^* \otimes S_y(1)^* \otimes S_z(0) \otimes \bigwedge\limits_{2,1,0} E) \\ \bigoplus \\ (S_x(1)^* \otimes S_y(2)^* \otimes S_z(0) \otimes \bigwedge\limits_{2,0,1} E) \end{matrix} \xrightarrow{\delta_1} \begin{matrix} (S_x(0)^* \otimes S_y(0)^* \otimes S_z(0) \otimes \bigwedge\limits_{1,1,0} E) \\ \bigoplus \\ (S_x(0)^* \otimes S_y(1)^* \otimes S_z(1) \otimes \bigwedge\limits_{2,0,0} E) \\ \bigoplus \\ (S_x(0)^* \otimes S_y(1)^* \otimes S_z(0) \otimes \bigwedge\limits_{1,0,1} E) \\ %% \bigoplus \\ %% (S_x(0)^* \otimes S_y(2)^* \otimes S_z(1) \otimes \bigwedge\limits_{2,-1,1} E) \\ \end{matrix} \rightarrow 0 $$

The following matrix represents the map $\delta_1$, \[ %\left[ \begin{array}{c || cccccccc | cc} & (A) & (B) & (C) & (D) & (E) & (F) & (G) & (H) & (I) & (J) %% \partial x_0^1 \partial y_1^2 {\boldsymbol{e}}_{\{1,2,3\}} & %% \partial x_1 \partial y_0^2 {\boldsymbol{e}}_{\{1,2,3\}} & %% \partial x_1 \partial y_1^2 {\boldsymbol{e}}_{\{1,2,3\}} & %% \partial x_0^1 \partial y_0^1 {\boldsymbol{e}}_{\{2,3,4\}} & %% \partial x_0^1 \partial y_1^1 {\boldsymbol{e}}_{\{2,3,4\}} & %% \partial x_1 \partial y_0^1 {\boldsymbol{e}}_{\{2,3,4\}} & %% \partial x_1 \partial y_1^1 {\boldsymbol{e}}_{\{2,3,4\}} & %% \partial x_1 \partial y_0^1\partial y_1^1 {\boldsymbol{e}}_{\{1,2,3\}} & %% \partial x_0^1 \partial y_0^2 {\boldsymbol{e}}_{\{1,2,3\}} & %% \partial x_1 \partial y_0^1\partial y_1^1 {\boldsymbol{e}}_{\{1,2,3\}} % back up %% {\boldsymbol{e}}_{\{1,2,3\}}{\it dx}_{{0}}{{\it dy}_{{1}}}^{2} & %% {\boldsymbol{e}}_{\{1,2,3\}}{\it dx}_{{1}}{{\it dy}_{{0}} }^{2} & %% {\boldsymbol{e}}_{\{1,2,3\}}{\it dx}_{{1}}{{\it dy}_{{1}}}^{2} & %% {\boldsymbol{e}}_{\{2,3,4\}}{\it dx}_{{0}}{\it dy}_{{0}} & %% {\boldsymbol{e}}_{\{2,3,4\}}{\it dx}_{{0} }{\it dy}_{{1}} & %% {\boldsymbol{e}}_{\{2,3,4\}}{\it dx}_{{1}}{\it dy}_{{0}} & %% {\boldsymbol{e}}_{\{2,3,4\}}{\it dx}_{{1}}{\it dy}_{{1}} & %% {\boldsymbol{e}}_{\{1,2,3\}}{ \it dx}_{{1}}{\it dy}_{{0}}{\it dy}_{{1}} & %% {\boldsymbol{e}}_{\{1,2,3\}}{\it dx}_{{0}}{{\it dy}_{{0}}}^{2} & %% {\boldsymbol{e}}_{\{1,2,3\}}{\it dx}_{{0}}{\it dy}_{{0 }}{\it dy}_{{1}} \\ \hline \hline % (I) & 0&0&0&5&-7&1&1&0 &0&0\\ (II) & 0&0&0&7&-8&-1&2&0&0&0 \\ (III) & 0&-1&0&0&0&0&0&-1 &-5&7\\ (IV) & 7&0&-1&0&0&0 &0&-1&0&-5\\ (V) & 0&1&0&0 &0&0&0&-2&-7&8\\ (VI) &8&0 &-2&0&0&0&0&1&0&-7\\ (VII) & 0&2&0&9&0&-2&0&-2&-1&2\\ (VIII) & 2&0&-2&0&9&0&-2&2&0&-1\\ \hline (IX) & 0&1&0&-6&0&-1&0&2&3&-4 \\ (X) & -4&0&2&0&- 6&0&-1&1&0&3 %% {\boldsymbol{e}}_{\{2,4\}} & 0&0&0&5&-7&1&1&0&0&0 \\ %% {\boldsymbol{e}}_{\{3,4\}} & 0&0&0&7&-8&-1&2&0&0&0 \\ %% {\boldsymbol{e}}_{\{1,2\}}{\it dy}_{{0}} & 0&-1&0&0&0&0&0&-1&-5&7 \\ %% {\boldsymbol{e}}_{\{1,2\}}{\it dy}_{{1}} &7&0&-1&0&0&0&0&-1&0&-5 \\ %% {\boldsymbol{e}}_{\{1,3\}}{\it dy}_{{0}}&0&1&0&0&0&0&0&-2&-7&8 \\ %% {\boldsymbol{e}}_{\{1,3\}}{\it dy}_{{1}}&8&0&-2&0&0&0&0&1&0&-7 \\ %% {\boldsymbol{e}}_{\{2,3\}}{\it dy}_{{0}}z_{{1}} & 0&2&0&9&0&-2&0&-2&-1&2 \\ %% {\boldsymbol{e}}_{\{2,3\}}{\it dy}_{{1}}z_{{1}} & 2&0&-2&0&9&0&-2&2&0&-1 \\ \hline %% {\boldsymbol{e}}_{\{2,3\}}{\it dy}_{{0}}z_{{0}} &0&-1&0&-6&0&-1&0&0&-7&10 \\ %% {\boldsymbol{e}}_{\{2,3\}}{\it dy}_{{1}}z_{{0}} &10&0&0&0&-6&0&-1&-1&0&-7 \end{array} %\right] \]

Basis of $K_1$ (Columns)
(A) $ \boldsymbol{\partial x}^{(1,0)} \otimes \boldsymbol{\partial y}^{(0,2)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{0,1,2\}} $
(B) $ \boldsymbol{\partial x}^{(0,1)} \otimes \boldsymbol{\partial y}^{(2,0)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{0,1,2\}} $
(C) $ \boldsymbol{\partial x}^{(0,1)} \otimes \boldsymbol{\partial y}^{(0,2)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{0,1,2\}} $
(D) $ \boldsymbol{\partial x}^{(1,0)} \otimes \boldsymbol{\partial y}^{(1,0)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{1,2,3\}} $
(E) $ \boldsymbol{\partial x}^{(1,0)} \otimes \boldsymbol{\partial y}^{(0,1)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{1,2,3\}} $
(F) $ \boldsymbol{\partial x}^{(0,1)} \otimes \boldsymbol{\partial y}^{(1,0)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{1,2,3\}} $
(G) $ \boldsymbol{\partial x}^{(0,1)} \otimes \boldsymbol{\partial y}^{(0,1)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{1,2,3\}} $
(H) $ \boldsymbol{\partial x}^{(1,0)} \otimes \boldsymbol{\partial y}^{(1,1)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{0,1,2\}} $
(I) $ \boldsymbol{\partial x}^{(1,0)} \otimes \boldsymbol{\partial y}^{(2,0)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{0,1,2\}} $
(J) $ \boldsymbol{\partial x}^{(0,1)} \otimes \boldsymbol{\partial y}^{(1,1)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{0,1,2\}} $
Basis of $K_0$ (Rows)
(I) $ \boldsymbol{\partial x}^{(0,0)} \otimes \boldsymbol{\partial y}^{(0,0)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{1,3\}}$
(II) $ \boldsymbol{\partial x}^{(0,0)} \otimes \boldsymbol{\partial y}^{(0,0)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{2,3\}}$
(III) $ \boldsymbol{\partial x}^{(0,0)} \otimes \boldsymbol{\partial y}^{(1,0)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{0,1\}}$
(IV) $ \boldsymbol{\partial x}^{(0,0)} \otimes \boldsymbol{\partial y}^{(0,1)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{0,1\}}$
(V) $ \boldsymbol{\partial x}^{(0,0)} \otimes \boldsymbol{\partial y}^{(1,0)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{0,2\}}$
(VI) $ \boldsymbol{\partial x}^{(0,0)} \otimes \boldsymbol{\partial y}^{(0,1)} \otimes \boldsymbol{z}^{(0,0)} \otimes {\boldsymbol{e}}_{\{0,2\}}$
(VII) $ \boldsymbol{\partial x}^{(0,0)} \otimes \boldsymbol{\partial y}^{(1,0)} \otimes \boldsymbol{z}^{(0,1)} \otimes {\boldsymbol{e}}_{\{1,2\}}$
(VIII) $ \boldsymbol{\partial x}^{(0,0)} \otimes \boldsymbol{\partial y}^{(0,1)} \otimes \boldsymbol{z}^{(0,1)} \otimes {\boldsymbol{e}}_{\{1,2\}}$
(IX) $ \boldsymbol{\partial x}^{(0,0)} \otimes \boldsymbol{\partial y}^{(1,0)} \otimes \boldsymbol{z}^{(1,0)} \otimes {\boldsymbol{e}}_{\{1,2\}}$
(X) $ \boldsymbol{\partial x}^{(0,0)} \otimes \boldsymbol{\partial y}^{(0,1)} \otimes \boldsymbol{z}^{(1,0)} \otimes {\boldsymbol{e}}_{\{1,2\}}$


We split the matrix as $\bigl[\begin{smallmatrix}M_{1,1} & M_{1,2} \\ M_{2,1} & M_{2,2} \end{smallmatrix} \bigr]$, and consider the Schur complement of $M_{2,2}$, $$ M_{2,2} - M_{2,1} \cdot M^{-1}_{1,1} \cdot M_{1,2} = \left[\begin{matrix} 5 & -2 \\ 4 & -1 \end{matrix} \right] $$
The Eigenvalues of the matrix are $$ \begin{array}{cc} \text{Eigenvalues} & \text{Eigenvectors} \\ \frac{f_0}{\boldsymbol{w}^{\theta}}(\alpha_1) = 3 & (7,7)^{\top} \\ \frac{f_0}{\boldsymbol{w}^{\theta}}(\alpha_2) = 1 & (1,2)^{\top} \end{array} . $$
We extend those eigenvectors to, for $\alpha_1 = (1\!:\!1 \;;\; 1\!:\!1 \;;\; 1\!:\!1)$ $$ \left( \boldsymbol{\partial x}^{(1,0)} +\boldsymbol{\partial}\boldsymbol{x}^{(0,1)} \right) \otimes \left( \boldsymbol{\partial y}^{(2,0)} +\boldsymbol{\partial y}^{(1,1)} +\boldsymbol{\partial y}^{(0,2)}\right) \otimes 7 \otimes \boldsymbol{e}_{\{0,1,2\}} \\ % + % \left( \boldsymbol{\partial x}^{(1,0)} +\boldsymbol{\partial x}^{(0,1)} \right) \otimes \left( \boldsymbol{\partial y}^{(1,0)} +\boldsymbol{\partial y}^{(0,1)}\right) \otimes -1 \otimes \boldsymbol{e}_{\{1,2,3\}} $$ and, for $\alpha_2 = (1\!:\!3 \;;\; 1\!:\!2 \;;\; 1\!:\!3)$ $$ \left( \boldsymbol{\partial x}^{(1,0)} +3\,\boldsymbol{\partial x}^{(0,1)} \right) \otimes \left( \boldsymbol{\partial y}^{(2,0)} +2\,\boldsymbol{\partial y}^{(1,1)} +4\,\boldsymbol{\partial y}^{(0,2)}\right) \otimes 1 \otimes \boldsymbol{e}_{\{0,1,2\}} \\ % + % \left( \boldsymbol{\partial x}^{(1,0)} +3\,\boldsymbol{\partial x}^{(0,1)} \right) \otimes \left( \boldsymbol{\partial y}^{(1,0)} +2\,\boldsymbol{\partial y}^{(0,1)} \right) \otimes 1 \otimes \boldsymbol{e}_{\{1,2,3\}} $$