Solution of non-invertible matrix equation

796 Views Asked by At

Is the following equation solvable for positive integers $m_{1,1}$ and $m_{2,1}$?

enter image description here

Rephrasing the question to A(BC)=(AB)C form yields a diophantine equation with two unknowns $m_{1,1}$ and $m_{2,1}$. But then, I'm looking for a solution using matrix operations such as matrix inversion (if possible) which perhaps leave the unknown 2-by-1-matrix consists the unknowns $m_{1,1}$ and $m_{2,1}$ stays at the left side while the solution is at the right side. The values for the unknowns $m_{1,1}$ and $m_{2,1}$ are restricted to be positive values.

This problem is closely related to a lattice problem since $BM$ is a lattice point where $B$ is a non-singular matrix (a lattice basis) and $M$ is a integral vector. If this problem can be solved (for unique positive $m_{1,1}$ and $m_{2,1}$), then I found that it has cryptographic significance especially in lattice-based cryptography.

1

There are 1 best solutions below

4
On

Let $$ \mathbf{A} = \left [ \begin{matrix} a_{11} & a_{12} \\ \end{matrix} \right ], \quad \mathbf{B} = \left [ \begin{matrix} b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{matrix} \right ], \quad \mathbf{M} = \left [ \begin{matrix} m_{11} \\ m_{21} \\ \end{matrix} \right ], \quad \mathbf{C} = \left [ \begin{matrix} c_{11} \end{matrix} \right ] $$ so that the equation becomes $$\mathbf{A} \mathbf{B} \mathbf{M} = \mathbf{C} \tag{1}\label{NA1}$$ which is equivalent to $$ m_{11} ( a_{11} b_{11} + a_{12} b_{21} ) + m_{21} ( a_{11} b_{12} + a_{12} b_{22} ) = c_{11} \tag{2}\label{NA2} $$ Solving for $m_{21}$ yields $$m_{21} = \frac{c_{11} - m_{11} ( a_{11} b_{11} + a_{12} b_{21} )}{a_{11} b_{12} + a_{12} b_{22}} \tag{3}\label{NA3} $$ Equation $\eqref{NA2}$ can be treated as a simple Diophantine equation $$a x + b y = c$$ where $$\begin{aligned} x &= m_{11} \\ y &= m_{21} \\ a &= a_{11} b_{11} + a_{12} b_{21} \\ b &= a_{11} b_{12} + a_{12} b_{22} \\ c &= c_{11} \\ \end{aligned} \tag{4}\label{NA4}$$

Per the Wikipedia article on Diophantine equation:

  • There is a solution $x, y \in \mathbb{Z}$ (given $a, b, c \in \mathbb{Z}$), if and only if $c$ is a multiple of the greatest common divisor of $a$ and $b$, $d = \operatorname{GCD}(a, b)$.

  • If there is a solution $x, y$, there are other solutions $x^\prime = x + k v$, $y^\prime = y - k u$, where $k \in \mathbb{Z}$, $v = b / d$, $u = a / d$.


If we substitute OP's values, we get $$\begin{aligned} a &= 105 \\ b &= 132 \\ c &= 870 \\ \end{aligned}$$ and therefore $$\begin{aligned} d = \operatorname{GCD}(a, b) &= 3 \\ u = \frac{a}{d} &= 35 \\ v = \frac{b}{d} &= 44 \\ \end{aligned}$$ If we look at equation $\eqref{NA3}$, $$y = \frac{290}{44} - x \frac{35}{44}$$ we can see that for $y \ge 0$, $x \lt 58/7 \lt 9$. So, for positive $x, y$, there is a solution, $$\left\lbrace\begin{aligned} x = m_{11} &= 2 \\ y = m_{21} &= 5 \\ \end{aligned}\right.$$ because $y \lt 0$ for $x \ge 9$, and among the eight possible positive integer values of $x$ left, only $x = 2$ yields a positive integer $y$.

Thus, all integer solutions, not just those with positive integer $x$ and $y$, are $$\left\lbrace\begin{aligned} x &= 2 + 44 k \\ y &= 5 - 35 k \\ \end{aligned}\right., \quad k \in \mathbb{Z}$$


I do not see any sensible way to express the algorithm for finding the solutions in matrix form.

Indeed, as far as I can tell, the only way to find the first solution is via a brute force search (albeit in a very finite range). Then again, I'm not a mathematician, and am only interested in Diophantine equations when they relate to certain lattices in molecular dynamics.