# System of bilinear equations

In algebra, systems of bilinear equations are collections of equations, each one of which is written as a bilinear form, for which a common solution is sought. Given one set of variables represented as a vector x, and another represented by a vector y, then a system of bilinear equations for x and y can be written $y^{T}A_{i}x=g_{i}$ . Here, i is an integer whose value ranges from 1 to some upper bound r, the $A_{i}$ are matrices and $g_{i}$ are some real numbers. Systems of bilinear equations arise in many subjects including engineering, biology, and statistics.

## Solving in integers

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

{\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

${\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.

${\text{mat}}\left({\begin{bmatrix}x_{1}x_{2}\\x_{1}y_{2}\\y_{1}x_{2}\\y_{1}y_{2}\end{bmatrix}}\right)={\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 the first equation by using the Smith normal form. Given any $m\times n$  matrix $A$ , we can get two matrices $U$  and $V$  in ${\mbox{SL}}_{m}(\mathbb {Z} )$  and ${\mbox{SL}}_{n}(\mathbb {Z} )$ , respectively such that $UAV=D$ , where $D$  is as follows:

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

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

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

$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

$M={\text{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 system. 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.