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.

Improve this question
$\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

Reset to default
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}} *)
Improve this answer
$\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.

Improve this answer
$\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

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