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 \( 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
\( {\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 \( 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} \). 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, 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 A x = b {\displaystyle A{\textbf {x}}={\textbf {b}}} {\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={\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.
See also
Systems of linear equations
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' - https://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
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
