# 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 ${\displaystyle y^{T}A_{i}x=g_{i}}$. Here, i is an integer whose value ranges from 1 to some upper bound r, the ${\displaystyle A_{i}}$ are matrices and ${\displaystyle 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

{\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 {\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 ${\displaystyle m\times n}$  matrix ${\displaystyle A}$ , we can get two matrices ${\displaystyle U}$  and ${\displaystyle V}$  in ${\displaystyle {\mbox{SL}}_{m}(\mathbb {Z} )}$  and ${\displaystyle {\mbox{SL}}_{n}(\mathbb {Z} )}$ , respectively such that ${\displaystyle UAV=D}$ , where ${\displaystyle 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}$ . 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 ${\displaystyle 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 ${\displaystyle D{\textbf {y}}={\textbf {c}}}$ , and take ${\displaystyle {\textbf {x}}=V{\textbf {y}}}$ . Let the solution of ${\displaystyle D{\textbf {y}}={\textbf {c}}}$  be

${\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 ${\displaystyle 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 ${\displaystyle {\textbf {x}}}$  is

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