8
$\begingroup$

Dear Mathematica experts,

Given two square matrices, A and B, how do we use Mathematica to solve a matrix T such that T satisfies this matrix equation? (Here we have A,B,T $\in$ general linear matrix GL($N,\mathbb{Z}$) with integer coefficient.)

Transpose[T]. A . T = B

Roughly we want to solve T by given A and B by some Mathematica command line:

Solve[Transpose[T]. A . T == B, T]  

But this won't work.

Conditions:

    1. We can focus on A and B are symmetric integer matrices, but A and B are not necessarily diagonal. $A_{ij}=A_{ji}, B_{ij}=B_{ji} \in \mathbb{Z}$.
    1. T is an integer matrix but may not be symmetric. $T_{ij} \in \mathbb{Z}$.
    1. All of matrices, including the given A and B, and the solution T have determinant det $= \pm 1$. Namely, $\det A = \det B = \det T =\pm 1$ (either 1 or $-1$). This shall be called unimodular.

(p.s. Ideally it is good to impose T is not only general linear matrix GL($N,\mathbb{Z}$) but special linear matrix SL($N,\mathbb{Z}$) such that the determinant det(T) =1 is better.)

As a test example, let us try two rank-10 matrices which indeed have solutions satisfy the above 3 conditions:

A = ({ {2, -1, 0, 0, 0, 0, 0, 0, 0, 0}, {-1, 2, -1, 0, 0, 0, 0, 0, 0, 0}, {0, -1, 2, -1, 0, 0, 0, -1, 0, 0}, {0, 0, -1, 2, -1, 0, 0, 0, 0, 0}, {0, 0, 0, -1, 2, -1, 0, 0, 0, 0}, {0, 0, 0, 0, -1, 2, -1, 0, 0, 0}, {0, 0, 0, 0, 0, -1, 2, 0, 0, 0}, {0, 0, -1, 0, 0, 0, 0, 2, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, -1} });

B = ({ {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, -1} });

How do we solve T? that satisfies Transpose[T]. A . T = B? Please give a rank-10 T matrix so we can compare.

I saw related questions, but none of them give a complete answer:

Matrix equivalence over the integers

Finding an Integer, Unimodular Matrix that connects two given matrices

https://mathematica.stackexchange.com/a/115905/95437

This answer uses Smith normal form to solve: T'. A . T = B but not Transpose[T]. A . T = B because T' $\neq$ Transpose[T] in general.

Edit: Nasser asked a smaller rank test example, here:

  • A = {{0, 1}, {1, 0}}. B= {{0,1},{1,2}}.

Ans: T={{1, 1},{0, 1}}.

  • A = {{0, 1}, {1, 0}}. B = {{2,5},{5,12}}.

Ans: T= {{1, 2}, {1, 3}}

(These T are in both GL($2,\mathbb{Z}$) and also SL($2,\mathbb{Z}$))

Thanks a lot! Zeta


EDIT to response to who absent-minded closing my question and falsely claiming the response to How to solve for $\mathbf{X}$ in a matrix equation $\mathbf{X A} \mathbf{X}^\top = \mathbf{B}$? solve my question.

  1. I require that all A, B, T are integer matrices. The approach that given in the cited answer there does not produce integer matrix T.

  2. Here I require symmetric integer A and symmetric integer B, and possibly generic non-symmetric integer T. (There is no diagonal matrix as the cited question.)

  3. In fact I require UNIMODULAR determinant = 1 for A, B, T matrices in all my examples.

  4. For those who closed this question, please use my toy rank-10 example to give me a Mathematica solution to it. Just to test that your answer really solves this.

$\endgroup$
12
  • $\begingroup$ If I understand the question well, then it is a possible dupe of mathematica.stackexchange.com/questions/251537/… in which case, there's also an analytic solution (see the accepted answer) $\endgroup$
    – Hans Olo
    Commented Dec 10, 2023 at 18:13
  • $\begingroup$ Thanks @Hans Olo, we can assume that A and B are symmetric integer matrices, but not diagonal. So, this one does not solve my question: NO [How to solve for 𝐗 in a matrix equation π—π€π—βŠ€=𝐁] mathematica.stackexchange.com/questions/251537 DOES NOT solve my question $\endgroup$
    – zeta
    Commented Dec 10, 2023 at 18:26
  • $\begingroup$ In the link the matrices are not assumed to be diagonal, see the example. Then, if I understand correctly the analytical solution (and assorted Mathematica code) should answer your question $\endgroup$
    – Hans Olo
    Commented Dec 10, 2023 at 19:08
  • 2
    $\begingroup$ I don't know who closed this question -- but that approach does NOT work! That is ridiculous! $\endgroup$
    – zeta
    Commented Dec 10, 2023 at 21:19
  • 3
    $\begingroup$ I suggest you ask about this on Mathematics Stack Exchange - once you know how to solve it then we should be able to put together the code, as Mathematica has ample built-in primitives to build an algorithm from like LatticeReduce and Orthogonalize, resource functions etc. $\endgroup$
    – flinty
    Commented Dec 11, 2023 at 2:48

2 Answers 2

3
$\begingroup$

Using the A, B matrices provided by the OP in the question we use the solution found in this post and we find

T=B.MatrixPower[Inverse[B].Inverse[A], 1/2] // N // Chop
(* {{1.09147, 0.830786, 0.971318, 0.729422, 0.525503, 0.341544, 0.168366, 0.470968, 0, 0}, {0.830786, 2.06279, 2.03118, 1.49682, 1.07097, 0.693868, 0.341544, 0.971318, 0, 0}, {0.971318, 2.03118, 3.55961,2.37272, 1.66519, 1.07097, 0.525503, 1.56021, 0, 0}, {0.729422, 1.49682, 2.37272, 2.58829, 1.56021, 0.971318, 0.470968, 1.13968, 0, 0}, {0.525503, 1.07097, 1.66519, 1.56021, 1.89443, 0.96021,      0.445816, 0.812512, 0, 0}, {0.341544, 0.693868, 1.07097, 0.971318, 0.96021, 1.36892, 0.489242, 0.525503, 0, 0}, {0.168366, 0.341544, 0.525503, 0.470968, 0.445816, 0.489242, 0.923108, 0.258454, 0, 0}, {0.470968, 0.971318, 1.56021, 1.13968, 0.812512, 0.525503, 0.258454, 1.44861, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1., 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, -1.}} *)

And as expected the solution satisfies the original equation:

Transpose[T].A.T - B // Chop
(* {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}} *)
$\endgroup$
7
  • 3
    $\begingroup$ $T_{ij}\notin \mathbb{Z}$. $\endgroup$
    – yarchik
    Commented Dec 10, 2023 at 19:30
  • 1
    $\begingroup$ The solution is in general not unique. $\endgroup$
    – yarchik
    Commented Dec 10, 2023 at 19:30
  • $\begingroup$ Indeed I need to impose T is an integer matrix. I know integer T exists. $\endgroup$
    – zeta
    Commented Dec 10, 2023 at 19:31
  • 1
    $\begingroup$ But thanks for the answer, I voted up for your effort. $\endgroup$
    – zeta
    Commented Dec 10, 2023 at 19:35
  • 1
    $\begingroup$ Even though this answer is not what OP was looking for, it may help others who are looking for real solutions, and it can be made a lot faster by doing X = B . MatrixPower[Inverse[N@B] . Inverse[N@A], 1/2] converting to numerical inside instead of at the end. $\endgroup$
    – flinty
    Commented Dec 27, 2023 at 13:40
3
$\begingroup$

I wonder if you're asking the impossible.

Here is an example for 3x3 matrices $A$ and $B$. There are 48 integer-only solutions. Would not having 10x10 matrices result in many, many more integer-only solutions?

A = {{5, 0, -2}, {0, 1, 0}, {-2, 0, 1}};
B = A;
T = Table[t[i, j], {i, 3}, {j, 3}];
sol = Solve[Transpose[T] . A . T == B, Variables[T], Integers];
(T /. # // MatrixForm) & /@ sol

48 solutions for a specific 3x3 matrix

(Det[T] /. # // MatrixForm) & /@ sol

Determinant values

Transpose[#] . A . # - B & /@ (T /. # & /@ sol)
{{{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0,  0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, 
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}},
 {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}}

If you could present code to generate matrices $A$ and $B$ for any size, that would help tell if for 10x10 matrices there might be too many solutions to determine.

$\endgroup$
7
  • 2
    $\begingroup$ I think they just want any solution for $T$ by some clever method that leans on the structure of the problem, or linear algebra magic, rather than brute force ... which I agree will be impossible for 10x10 as you mentioned. I don't think that magic exists yet, and this looks like an open problem. $\endgroup$
    – flinty
    Commented Dec 15, 2023 at 1:44
  • $\begingroup$ @flinty I hope that is true. But the OP needs to state that. I answered because I was bothered that a relatively new Mathematica user stated "This won't work" when at least for smaller matrices they simply had coding errors. $\endgroup$
    – JimB
    Commented Dec 15, 2023 at 1:49
  • 4
    $\begingroup$ A solution can be obtained with obj = (Transpose[T] . A . T - B // Flatten )^2 // Total ; var = Variables[T] ; con = Element[#, Integers] & /@ var ; NMinimize[{obj, con}, var] // Last. $\endgroup$
    – I.M.
    Commented Dec 15, 2023 at 3:30
  • 1
    $\begingroup$ @I.M. or alternatively obj[X_?(MatrixQ[#, NumericQ] &)] := Total[Abs[Transpose[X] . A . X - B], 2]; and then this avoids the Last/Rule stuff: T0 = NArgMin[obj[X], X ∈ Matrices[{10, 10}, Integers]] But it will never terminate with a correct matrix for a 10x10 on my machine. The search space is too big. $\endgroup$
    – flinty
    Commented Dec 15, 2023 at 21:27
  • 1
    $\begingroup$ Unfortunately, no. I was able to do some 3x3 matrices by was too impatient to see if 4x4 matrices would finish. I suspect my computer isn't powerful enough to do 10x10. I'm guessing (but I really don't know) that there are zillions of solutions for a 10.x10 matrix so I'm wondering as @flinty has commented, "Do you need a single or a few solutions or do you need all solutions?" $\endgroup$
    – JimB
    Commented Dec 17, 2023 at 6:23

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.