System of bilinear equations

System of bilinear equations look like the following ${\displaystyle y^{T}A_{i}x=g_{i}}$ for ${\displaystyle i=1,2,\ldots ,r}$ for some integer $r$ where $A_{i}$ are matrices and $g_{i}$ are some real numbers. These arise in many subjects like engineering, biology, statistics etc.

Solving in integers

We consider here the solution theory for bilinear equations in integers. Let the given system of bilinear equation be

${\displaystyle {\begin{alignedat}{2}ax_{1}x_{2}+bx_{1}y_{2}+cx_{2}y_{1}+dy_{1}y_{2}&=&\alpha \\ex_{1}x_{2}+fx_{1}y_{2}+gx_{2}y_{1}+hy_{1}y_{2}&=&\beta \end{alignedat}}}$

This system can be written as

${\displaystyle {\begin{bmatrix}a&b&c&d\\e&f&g&h\end{bmatrix}}{\begin{bmatrix}x_{1}x_{2}\\x_{1}y_{2}\\y_{1}x_{2}\\y_{1}y_{2}\end{bmatrix}}={\begin{bmatrix}\alpha \\\beta \end{bmatrix}}}$

Once we solve this linear system of equations then by using rank factorization below, we can get a solution for the given bilinear system.

${\displaystyle mat({\begin{bmatrix}x_{1}x_{2}\\x_{1}y_{2}\\y_{1}x_{2}\\y_{1}y_{2}\end{bmatrix}})={\begin{bmatrix}x_{1}x_{2}&x_{1}y_{2}\\y_{1}x_{2}&y_{1}y_{2}\end{bmatrix}}={\begin{bmatrix}x_{1}\\y_{1}\end{bmatrix}}{\begin{bmatrix}x_{2}&y_{2}\end{bmatrix}}}$

Now we solve first equation by using smith normal form, given any $m\times n$ matrix $A$, we can get two matrices $U$ and $V$ in ${\displaystyle {\mbox{SL}}_{m}(\mathbb {Z} )}$ and ${\displaystyle {\mbox{SL}}_{n}(\mathbb {Z} )}$, respectively such that ${\displaystyle UAV=D}$, where $D$ is as follows:

${\displaystyle D={\begin{bmatrix}d_{1}&0&0&\ldots &0\\0&d_{2}&0&\ldots &0\\\vdots &&&d_{s}&0&\\0&0&0&\ldots &0\\\vdots &\vdots &\vdots &\vdots &\vdots \end{bmatrix}}_{m\times n}}$

where ${\displaystyle d_{i}>0}$ and ${\displaystyle d_{i}|d_{i+1}}$ for ${\displaystyle i=1,2,\ldots ,s-1}$. It is immediate to note that given a system ${\displaystyle A{\textbf {x}}={\textbf {b}}}$, we can rewrite it as ${\displaystyle D{\textbf {y}}={\textbf {c}}}$, where ${\displaystyle V{\textbf {y}}={\textbf {x}}}$ and ${\displaystyle {\textbf {c}}=U{\textbf {b}}}$. Solving ${\displaystyle D{\textbf {y}}={\textbf {c}}}$ is easier as the matrix $D$ is somewhat diagonal. Since we are multiplying with some nonsingular matrices we have the two system of equations to be equivalent in the sense that the solutions of one system have one-to-one correspondence with the solutions of another system. We solve ${\displaystyle D{\textbf {y}}={\textbf {c}}}$, and take ${\displaystyle {\textbf {x}}=V{\textbf {y}}}$. Let the solution of ${\displaystyle D{\textbf {y}}={\textbf {c}}}$ is

${\displaystyle {\textbf {y}}={\begin{bmatrix}a_{1}\\b_{1}\\s\\t\end{bmatrix}}}$

where ${\displaystyle s,t\in \mathbb {Z} }$ are free integers and these are all solutions of ${\displaystyle D{\textbf {y}}={\textbf {c}}}$. So, any solution of ${\displaystyle A{\textbf {x}}={\textbf {b}}}$ is ${\displaystyle V{\textbf {y}}}$. Let $V$ be given by

${\displaystyle V={\begin{bmatrix}a_{11}&a_{12}&a_{13}&a_{14}\\a_{21}&a_{22}&a_{23}&a_{24}\\a_{31}&a_{32}&a_{33}&a_{34}\\a_{41}&a_{42}&a_{43}&a_{44}\end{bmatrix}}={\begin{bmatrix}A_{1}&B_{1}\\C_{1}&D_{1}\end{bmatrix}}}$

Then ${\textbf {x}}$ is

${\displaystyle M=mat({\textbf {x}})={\begin{bmatrix}a_{11}a_{1}+a_{12}b_{1}+a_{13}s+a_{14}t&a_{31}a_{1}+a_{32}b_{1}+a_{33}s+a_{34}t\\a_{21}a_{1}+a_{22}b_{1}+a_{23}s+a_{24}t&a_{41}a_{1}+a_{42}b_{1}+a_{43}s+a_{44}t\end{bmatrix}}}$

We want matrix $M$ to have rank 1 so that the factorization given in second equation can be done. Solving quadratic equations in 2 variables in integers will give us the solutions for a bilinear systems. This method can be extended to any dimension, but at higher dimension solutions become more complicated. This algorithm can be applied in Sage or Matlab to get to the equations at end.

References

• Charles R. Johnson, Joshua A. Link 'Solution theory for complete bilinear systems of equations' - http://onlinelibrary.wiley.com/doi/10.1002/nla.676/abstract
• Vinh, Le Anh 'On the solvability of systems of bilinear equations in finite fields' - http://arxiv.org/abs/0903.1156
• Yang Dian 'Solution theory for system of bilinear equations' - https://digitalarchive.wm.edu/handle/10288/13726
• Scott Cohen and Carlo Tomasi. 'Systems of bilinear equations'. Technical report, Stanford, CA, USA, 1997.- ftp://reports.stanford.edu/public_html/cstr/reports/cs/tr/97/1588/CS-TR-97-1588.pdf