1

Consider the following equation:

$$ \begin{pmatrix} n_1 \\ n_2 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 0 & 0 & 1 & 0 \\ 2 & 1 & 2 & 3 & 0 & 1 \end{pmatrix} \begin{pmatrix} m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ m_6 \end{pmatrix} $$

where $n_i \in \mathcal{N}$ are known and $m_i$ are unknown. I would like to find all the possible solutions $m_i \in \mathcal{N}$. Note the trivial solutions $m_i = n_i = 0$ and $m_{1,2,3,4} = 0; m_5 = n_1; m_6 = n_2$. Also note I have considered $\mathcal{N}$ to contain zero.

What's an algorithmic way to get all possible solutions compatible with given $n_i$? Something implementable in, e.g., Python, is OK for my purposes.

Miguel
  • 229
  • @Jean-ClaudeArbaut Thanks for the suggestion, I'll start from there. It's also clear that because of the zeros/ones in the matrix m3 to m6 would be good choices for the parameters, in the sense that it's easy to work out their bounds in terms of n1 and n2. Still, this will be a bit of a brute force approach, but 4 parameters definitely better than 6 unknowns, 2 orders of magnitude faster for brute forcing it. – Miguel Dec 11 '22 at 19:31
  • Wait, I didn't pay attention to the constraint that the $m_i$ have to be natural integers. What you have is a linear system of diophantine equations, and it's not as simple. – Jean-Claude Arbaut Dec 11 '22 at 19:34
  • @Jean-ClaudeArbaut But I still think I can use what you suggested to invert the row echelon matrix and use the inverse to generate solutions using code. In practice n1 and n2 are small so that I can constrain the domain of parameters to a subset of small naturals and get all the valid solutions by eliminating those that contain m_i not in N. – Miguel Dec 11 '22 at 21:07
  • @Jean-ClaudeArbaut Please take a look at the proposed solution (which I could easily implement in Python) and let me know what you think. – Miguel Dec 12 '22 at 07:50

1 Answers1

1

Here goes my own answer (I will leave it unaccepted until someone comes up with a better, more elegant, more efficient, solution). As per @Jean-ClaudeArbaut's suggestion in the comments (which however overlooked the $m_i$ should be naturals), I express the matrix in row echelon form and choose 4 parameters (the difference between the dimension [6] and rank [2] of my matrix):

$$ \begin{pmatrix} n_1 \\ n_2 - 2n_1 \\ m_3 \\ m_4 \\ m_5 \\ m_6 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & -1 & 2 & 3 & -2 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ m_6 \end{pmatrix} $$

I have chosen $m_3$ to $m_6$ as parameters out of convenience because the two rows of my original matrix allow me to easily establish the bounds to find solutions:

$$ m_3 \in [0,\text{int}(n_2/2)] \\ m_4 \in [0,\text{int}(n_2/3)] \\ m_5 \in [0,n_1] \\ m_6 \in [0,n_2] $$

where $\text{int}(n)$ stands for the integer part of $n$ (the "floor" function). By inverting my matrix, I obtain a solution generator:

$$ \begin{pmatrix} m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ m_6 \end{pmatrix} = \begin{pmatrix} 1 & 1 & -2 & -3 & 1 & -1 \\ 0 & -1 & 2 & 3 & -2 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} n_1 \\ n_2 - 2n_1 \\ m_3 \\ m_4 \\ m_5 \\ m_6 \end{pmatrix} $$

Solutions are generated algorithmically for the fixed $n_i$ and varying $m_3$ to $m_6$ within their predetermined bounds (as given above; more efficient bounds could be determined).

All the valid solutions are those for which $m_i \in \mathcal{N}$, all other solutions (which in this case involve negative $m_i$) are discarded.

Miguel
  • 229