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

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]
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];
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.

• Try RiccatiSolve. Jan 11, 2022 at 17:36
• @HenrikSchumacher - Yeah I thought about that the other day, I need to investigate that approach. Thanks for the reminder. To be honest I don't hold out much hope on solving this in some reasonable time for $6 \times 6$ or above. Jan 11, 2022 at 17:44
• Nevermind, I just realized that RicattiSolve seems to be unable to handle the transposition of mM. Jan 11, 2022 at 17:51
• Wait, do you need integer solutions? Jan 11, 2022 at 18:08
• @HenrikSchumacher - yes I require integer solutions. This is a number theory project I am working on. These unknown zero-weight solutions M are integer matrices. And yes - the transposing is what makes this difficult. Jan 11, 2022 at 18:29