Re: Find an invertible integer matrix that satisfies given conditions.

On Mon, Apr 17, 2023 at 8:29 PM Hongyi Zhao <hongyi.zhao@gmail.com> wrote:

On Tue, Apr 18, 2023 at 2:55 AM Bill Allombert
<Bill.Allombert@math.u-bordeaux.fr> wrote:
>
> On Mon, Apr 17, 2023 at 08:44:00PM +0200, Aurel Page wrote:
> > On 17/04/2023 13:43, Hongyi Zhao wrote:
> > > Why this problem can't be in general nicely solved by GP?
> > It could be if someone implemented an algorithm for it, like many other
> > interesting problems. You are welcome to contribute an implementation or to
> > suggest someone willing to write one. I we have a nice reference for an
> > algorithm and sufficiently many requests compared to the time needed to
> > implement the algorithm, we consider working on it.
>
> I would like to add: the algorithm is not polynomial time, which means that
> even if we implement it, it might be too slow for your application.
>
> On the other hand, if you have particular examples you are interested in, the
> procedure we outlined might be sufficient.

For example, using the following two matrices to do the test:

A = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0;
0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0;
0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0;
0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0;
0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0;
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1;
-2, -2, -2, -2, -1, -1, -1, -1, 0, 0, -2, 0, 0, 0];

B = [-21, -11, 12, 9, 15, 8, -22, -23, 2, 6, 8, -2, 2, -8;
32, 17, -22, -10, -18, -14, 28, 35, -5, -6, -13, 4, -1, 13;
1, 4, -17, 6, 11, -12, -6, 18, -16, 8, -7, 7, 4, 9;
21, 13, -24, -11, -19, -21, 33, 48, -15, -4, -15, 7, -1, 18;
14, 8, -16, -2, -2, -11, 10, 23, -9, 0, -9, 5, 0, 9;
-1, 8, -14, -3, 13, -9, -2, 21, -18, 6, -7, 8, 0, 9;
29, 14, -13, -15, -27, -10, 36, 31, 1, -11, -10, 1, -4, 10;
-26, -8, -8, 10, 21, -12, -16, 14, -25, 14, -3, 9, 5, 8;
-8, -6, -1, -9, -31, -14, 34, 31, -8, -7, -4, 1, -2, 10;
-19, -8, 11, -15, -39, -8, 38, 24, -4, -9, 2, -2, -3, 7;
-35, -25, 30, 3, -11, 11, -2, -27, 14, -4, 14, -9, -2, -13;
-19, -21, 32, -6, -34, 11, 21, -21, 23, -14, 13, -13, -5, -12;
10, 5, 3, 11, 31, 16, -36, -36, 11, 7, 5, -2, 3, -12;
12, 7, -7, -13, -27, -7, 30, 24, 2, -11, -5, -1, -5, 6];

Below is the result given by the current implementation in Hecke by
Tommy Hofmann:

julia> using Hecke

Welcome to

_ _ _
| | | | | |
| |__| | ___ ___| | _____
| __ |/ _ \/ __| |/ / _ \
| | | | __/ (__| < __/
|_| |_|\___|\___|_|\_\___|

Version 0.18.9 ...
... which comes with absolutely no warranty whatsoever
(c) 2015-2023 by Claus Fieker, Tommy Hofmann and Carlo Sircana

julia> A = [
0 1 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 1 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 1 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 1 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 1 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 1 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 1 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 1 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 1 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 1 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 1 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 1 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 1;
-2 -2 -2 -2 -1 -1 -1 -1 0 0 -2 0 0 0
];

julia> B = [
-21 -11 12 9 15 8 -22 -23 2 6 8 -2 2 -8;
32 17 -22 -10 -18 -14 28 35 -5 -6 -13 4 -1 13;
1 4 -17 6 11 -12 -6 18 -16 8 -7 7 4 9;
21 13 -24 -11 -19 -21 33 48 -15 -4 -15 7 -1 18;
14 8 -16 -2 -2 -11 10 23 -9 0 -9 5 0 9;
-1 8 -14 -3 13 -9 -2 21 -18 6 -7 8 0 9;
29 14 -13 -15 -27 -10 36 31 1 -11 -10 1 -4 10;
-26 -8 -8 10 21 -12 -16 14 -25 14 -3 9 5 8;
-8 -6 -1 -9 -31 -14 34 31 -8 -7 -4 1 -2 10;
-19 -8 11 -15 -39 -8 38 24 -4 -9 2 -2 -3 7;
-35 -25 30 3 -11 11 -2 -27 14 -4 14 -9 -2 -13;
-19 -21 32 -6 -34 11 21 -21 23 -14 13 -13 -5 -12;
10 5 3 11 31 16 -36 -36 11 7 5 -2 3 -12;
12 7 -7 -13 -27 -7 30 24 2 -11 -5 -1 -5 6
];

julia> is_GLZ_conjugate(matrix(ZZ,A), matrix(ZZ,B))
(true, [6318719816487210536101 20514744442307812988142
27044872794995996371682 15880875021111315079615 -47326738138602619292
-2631842368119625535230 4726747174815148277764 6958022514839196879244
1852675346866011477591 -4209427941933120721717 -4397844611341424954037
-491207497858230330282 1728009335028557710631 1117589676351822646467;
-17538519976636503973889 -51192831114385020463801
-52194990750121071553205 -10270944687137426894103
34731462939222037405070 44032745635305603055909
18599873498198324286119 -8484947673158283735917
-10460487635401336053358 14819137823860426017338
22348684436629430031361 -1674737664794785144433
-16105424549585740374682 -9997721386194315313282;
-5701021350519107184779 -16673231554855304897121
-5894188011007448474936 20950434883153823197005
38707822088145611424660 40515302445827052728666
28228150281828611311111 8835471017540396905059 -3657455173392465391625
6622110635589140099546 15587622143666167774294 -819873212018257346723
-12218310777547523950074 -8901924238019106244531;
-31037785057992760929405 -52786368104237446295649
-41433131146888508751975 -12197544449433941811472
12523715321944887614469 5786822550303587828656
-13129208203099610734910 -19871498100469861128995
2929826805537963510906 27826325570001039789940 3793678685172321820538
-6886362937876445111628 -5545738559966335264339
5868161134394942150851; -11237366341632493146070
-9760945219525371423315 4037028171729885292663 16515913124004612187978
21657952369525693380214 8973035193186604356310 -8421054292906953040781
-12469749920989649560876 4686377413886415165118
15321799257647528199487 -5219784189385947843555
-10363853241495977827432 -4475970178142277405753
4197522678086441582752; -23403326252585575377994
3669417385486402054583 22617507130920951692737 -8363765794454890207493
-51425355344709593811234 -86440668617541331956589
-68211929774900946119846 -11261825302509578090378
46064837503299604746859 31638823177304541436208
-39760341670180710983110 -3539971202641066493314
32963341806254003903990 37888255916223403964073;
-33314515523601435767937 -60022778597425138099195
-55094348917800046162210 -25766735540163786226367
8743956205312409141547 6545933099598337935332 -22021002341278127866001
-37552498681712936215223 -7794798951083672471516
28000420022362190533588 2763086058810947607549
-12334565455815521551019 -10247702967320117992136
4860879411603368520561; -15648420920283915469219
12229768744307566807704 52106133741706244469971
51834402314380960194068 22606165456024309594107
-10963169191697349721118 -14137618019647451490683
3111819311504178366639 29452437096907675756545 26908363929032919036423
-20095342445250286862832 -11402690922843150865196
7118624569412271046095 17723695355479242799455;
-7422697564824451870677 -26923024095005602772878
-37228932633187666122967 -32205394201035642491548
-20333305618276231969169 -9095238558749783526558
-8589872158053535282832 -19315082540024331542741
-25940310155752414276165 -10872611941676915409344
5012297079270148889325 -1606192719753255148482 -8814665868910205629626
-6527874343026712169641; -51501933326144326886744
-102265108778606905574862 -108380876530504346997800
-85219465116960505453207 -49491532872081809717979
-31411827325553741303307 -32866508259164385344613
-47962321127667375528942 -30599026779974640219195
19473811504128176429442 10661965003043894077139
-2676294284593561401169 -9364371837734908540944
4806723986126660343691; 5249233419369071913570 26579442061363766023169
34722112685809142867762 10580293222135467020739
-15838057498815882313423 -20353025721813776003266
-16535705314624656460714 -21087259191104119207530
-19882396083796173958846 -13980662732351593042526
-16948380828764613947297 -13188702901085926358947
-5325529489772982411874 1420355321948118232450; 7922854318220308389871
-9960025070617309520428 -31617494442151754716347
-33640602364115440284315 -16808483298351329427596
6911692567251250735911 -1538239207622316654415
-35125818327594375920766 -55973032004874185479898
-32399590956276284739227 7135254006726780351876
-9152758572768327889303 -22794038388071721834319
-19172721753778118743646; 31477480510805193564736
81760066094801300316729 109263331560503678450521
106609562747290093360891 83302567002139837209415
56906660735554265570789 42734808956599535063413
50138449227863068720569 49765053251333361379750
14021841530487832683819 -5948428411826152080922
-1583166072890988979938 7991569938982370583114 3004263843205512488802;
27125687926938344529215 12983562960621408404768
-45722490398652298018507 -94847470340105763803062
-110193597537356430287797 -75993091484260540429562
-25004783030653748974458 2957201091888352403595
-24810469482516038102197 -52803971899012685004886
-1071768915663799982601 25190468130970617152563
18533875633948381586998 -5780767708363531344454])

> Cheers,
> Bill.

Best,
Zhao