Monday 2 November 2020

Vampire Matrices algoritm

Can you find two 3x3 matrices L and R with integer values such that LR=nL+RLR = nL+R with nn an integer constant?
First, let write our matrices as

L=[a1a2a3b1b2b3c1c2c3]R=[x1y1z1x2y2z2x3y3z3]L = \begin{bmatrix} a_1 & a_2 & a_3\\ b_1 & b_2 & b_3\\ c_1 & c_2 & c_3\\ \end{bmatrix}\\R = \begin{bmatrix} x_1 & y_1 & z_1\\ x_2 & y_2 & z_2\\ x_3 & y_3 & z_3\\ \end{bmatrix}
This means that LR=[a1x1+a2x2+a3x3a1y1+a2y2+a3y3a1z1+a2z2+a3z3b1x1+b2x2+b3x3b1y1+b2y2+b3y3b1z1+b2z2+b3z3c1x1+c2x2+c3x3c1y1+c2y2+c3y3c1z1+c2z2+c3z3]LR = \left[\begin{matrix}a_{1} x_{1} + a_{2} x_{2} + a_{3} x_{3} & a_{1} y_{1} + a_{2} y_{2} + a_{3} y_{3} & a_{1} z_{1} + a_{2} z_{2} + a_{3} z_{3}\\b_{1} x_{1} + b_{2} x_{2} + b_{3} x_{3} & b_{1} y_{1} + b_{2} y_{2} + b_{3} y_{3} & b_{1} z_{1} + b_{2} z_{2} + b_{3} z_{3}\\c_{1} x_{1} + c_{2} x_{2} + c_{3} x_{3} & c_{1} y_{1} + c_{2} y_{2} + c_{3} y_{3} & c_{1} z_{1} + c_{2} z_{2} + c_{3} z_{3}\end{matrix}\right]
And nL+R=[a1n+x1a2n+y1a3n+z1b1n+x2b2n+y2b3n+z2c1n+x3c2n+y3c3n+z3]nL+R = \left[\begin{matrix}a_{1} n + x_{1} & a_{2} n + y_{1} & a_{3} n + z_{1}\\b_{1} n + x_{2} & b_{2} n + y_{2} & b_{3} n + z_{2}\\c_{1} n + x_{3} & c_{2} n + y_{3} & c_{3} n + z_{3}\end{matrix}\right]
Combining these to expressions with LR=nL+RLR = nL+R yields nine equations of a similar form.
α1γ1+α2γ2+α3γ3=nαi+γj\alpha_1 \gamma_1 + \alpha_2 \gamma_2 + \alpha_3 \gamma_3 = n\alpha_i + \gamma_j

Now, let us define a mathamatical object, that we call a local triple, that has the following properties.

  1. A 3d vector (α1,α2,α3)(\alpha_1,\alpha_2,\alpha_3) of integers
  2. An index 1,2,3 related to the row/column that the triple is on
  3. A token, left/right, based on if the triple is in the left or right matrix.
    We will note left local triples as (α1,α2,α3,j\left(\alpha_1,\alpha_2,\alpha_3, j\right| and right triples as γ1,γ2,γ3,i)\left|\gamma_1,\gamma_2,\gamma_3, i\right)
    Let us call two triples (α1,α2,α3,j\left(\alpha_1,\alpha_2,\alpha_3, j\right| and γ1,γ2,γ3,i)\left|\gamma_1,\gamma_2,\gamma_3, i\right)connected if α1γ1+α2γ2+α3γ3=nαi+γj\alpha_1 \gamma_1 + \alpha_2 \gamma_2 + \alpha_3 \gamma_3 = n\alpha_i + \gamma_j
    Note that the index of a local triple indexes the vector of the other local triple, not the own vector.
    Now that this is done, we can check for each left local triple all possible right local triples, and store them in a set.
    Then we can check for each set of 3 left local triples, with each a different index, if the intersection for the three corresponding sets contains at least one right local triple of each index. If it does, we can use the 6 local triples with corresponding indexes to build our original matrices back.
    The rust code that performs this for single digit non zero integers for n=10n=10 can be found here: https://gitlab.com/Elmosfire/vampire-matrices/-/blob/master/main.rs