Solving or Minimizing the Norm of the matrix equation $M^TAM - M^TB - B^TM =C$

Question

I am trying to solve the matrix equation $M^TAM - M^TB - B^TM=C$ where I know A, B and C. My unknown matrix is M which has the special form that all the rows and columns sum to zero.

i.e. I have four unknowns $m1, m2, m3, m4$ for a $3 \times 3$ matrix M.

Now throwing this into Solve or FindInstance (over Integers) I have the following code:

mA = {{13, 7, -8}, {7, 61, -56}, {-8, -56, 76}}; Print["mA = ", mA]
mB = {{36, -45, 9}, {252, -315, 63}, {-288, 360, -72}}; Print["mB = ",mB]
mC = {{-756, 1188, -432}, {1188, -1485, 297}, {-432, 297, 135}}; Print["mC = ", mC]
mM = {{m1, m2, -m1 - m2}, {m3, m4, -m3 - m4}, {-m1 - m3, -m2 - m4, m1 + m2 + m3 + m4}}; Print["mM = ", mM]
answer = 
    FindInstance[
     Transpose[mM] . mA . mM - Transpose[mM] . mB - 
       Transpose[mB] . mM == mC, {m1, m2, m3, m4} , Integers]; // 
  AbsoluteTiming // First
mM = Join @@ (mM /. answer);Print["mM = ", mM]
Transpose[mM] . mA . mM - Transpose[mM] . mB - Transpose[mB] . mM == mC

(*

mA = {{13,7,-8},{7,61,-56},{-8,-56,76}}

mB = {{36,-45,9},{252,-315,63},{-288,360,-72}}

mC = {{-756,1188,-432},{1188,-1485,297},{-432,297,135}}

mM = {{m1,m2,-m1-m2},{m3,m4,-m3-m4},{-m1-m3,-m2-m4,m1+m2+m3+m4}}

0.021557

mM = {{-3,4,-1},{3,-5,2},{0,1,-1}}

True

*)

This works with matrices up to $5\times 5 $ taking about 40 seconds, using Solve gives 156 solutions in about 3 minutes. The $3\times 3 $ case above takes 0.02 seconds . Sadly, for me, I have never got a $6\times 6 $ case to return from Solve (or FindInstance) in many hours.

So I tried using Minimize[] with, simply :

mM = {{m1, m2, -m1 - m2}, {m3, m4, -m3 - m4}, {-m1 - m3, -m2 - m4, 
    m1 + m2 + m3 + m4}};
Minimize[{Norm[
    Transpose[mM] . mA . mM - Transpose[mM] . mB - 
     Transpose[mB] . mM - mC]}, {m1, m2, m3, m4}, Integers] // Last

This returns, after quite a while, with just a $\mathbb {Z}$ as the output, even though we know there are solutions from FindInstance or Solve. Though a $2\times 2$ case does work. Does anyone know different ways to use Solve/FindInstance, Minimize or some other Mathematica function for solving this problem (in of course the eternal wish it's done quickly)?

As per a request here is an attempt for a $6 \times 6$ matrix.

AbsoluteTiming[
  mA = {{865, 3, 4, 9, 9, -26}, {3, 873, 12, 27, 27, -78}, {4, 12, 
     880, 36, 36, -104}, {9, 27, 36, 945, 81, -234}, {9, 27, 36, 81, 
     945, -234}, {-26, -78, -104, -234, -234, 1540}}; 
  Print["mA = ", mA // MatrixForm];
  mB = {{216, -216, 216, -432, -216, 432}, {648, -648, 
     648, -1296, -648, 1296}, {864, -864, 864, -1728, -864, 
     1728}, {1944, -1944, 1944, -3888, -1944, 3888}, {1944, -1944, 
     1944, -3888, -1944, 3888}, {-5616, 5616, -5616, 11232, 
     5616, -11232}}; Print["mB = ", mB // MatrixForm];
  mC = {{1446336, 
     793152, -793152, -93312, -326592, -1026432}, {793152, 
     2192832, -1446336, -1026432, -46656, -466560}, {-793152, \
-1446336, 1446336, 1026432, -326592, 93312}, {-93312, -1026432, 
     1026432, 
     1306368, -1026432, -186624}, {-326592, -46656, -326592, -1026432,
      1073088, 653184}, {-1026432, -466560, 93312, -186624, 653184, 
     933120}}; Print["mC = ", mC // MatrixForm];
  mM = {{m1, m2, m3, m4, m5, -m1 - m2 - m3 - m4 - m5}, {m6, m7, m8, 
     m9, m10, -m10 - m6 - m7 - m8 - m9}, {m11, m12, m13, m14, 
     m15, -m11 - m12 - m13 - m14 - m15}, {m16, m17, m18, m19, 
     m20, -m16 - m17 - m18 - m19 - m20}, {m21, m22, m23, m24, 
     m25, -m21 - m22 - m23 - m24 - m25}, {-m1 - m11 - m16 - m21 - 
      m6, -m12 - m17 - m2 - m22 - m7, -m13 - m18 - m23 - m3 - 
      m8, -m14 - m19 - m24 - m4 - m9, -m10 - m15 - m20 - m25 - m5, 
     m1 + m10 + m11 + m12 + m13 + m14 + m15 + m16 + m17 + m18 + m19 + 
      m2 + m20 + m21 + m22 + m23 + m24 + m25 + m3 + m4 + m5 + m6 + 
      m7 + m8 + m9}}; Print["mM = ", mM // MatrixForm];
answer = 
    FindInstance[
     Transpose[mM] . mA . mM - Transpose[mM] . mB - 
       Transpose[mB] . mM == mC, {m1, m2, m3, m4,m5,m6,m7,m8,m9,m10,m11,m12,m13,m14,m15,m16,m17,m18,m19,m20,m21,m22,m23,m24,m25} , Integers]; // 
  AbsoluteTiming // First
mM = Join @@ (mM /. answer);Print["mM = ", mM]
Transpose[mM] . mA . mM - Transpose[mM] . mB - Transpose[mB] . mM == mC
// First

Now I must mention - I do not know if this has a solution. I suspect it does but it just goes off and doesn't return (certainly not after a few hours). But if it returned with {} telling me no solution was found would be useful.