lan496 / hsnf Goto Github PK

All functions sometimes return a wrong answer even for small-size matrices with small values. For instance:

For matrix

[[ 1 -10 0 4 2 -3 6]
[ -6 -8 -3 -2 7 0 -8]
[ -8 0 0 -4 8 10 -5]
[ 8 -3 3 9 9 10 6]
[ -5 -3 -9 10 -4 7 9]
[ -4 -9 -9 -5 2 0 1]
[ 4 2 -5 1 7 -10 -1]]

function column_style_hermite_normal_form provides output

[[-346925671050097202 -252755 -466370
-630998 -478778 -600398
-659835]
[ 835296760844636953 608561 1122884
1519261 1152759 1445585
1588692]
[-479143188193987710 -349083 -644109
-871479 -661246 -829217
-911306]
[ 191046112789960095 139188 256822
347480 263655 330629
363360]
[1118641869143326448 814994 1503783
2034617 1543792 1935949
2127600]
[-828222439379453903 -603407 -1113374
-1506394 -1142996 -1433342
-1575237]
[ 535626295318601958 390234 720039
974212 739196 926968
1018734]],

[[ 1 0 0 0 0 0 0]
[ 0 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0]
[ 0 0 0 1 0 0 0]
[ 0 0 0 0 1 0 0]
[ 0 0 0 0 0 1 0]
[18454335 13439499 24797837 33551452 25457599 31924387 35084770]]

however, direct multiplication with calculator shows, that element (6, 6) of the HNF in this case would be 18446744073728005951 instead of 18454335 (i.e. the answer has even a self-contradiction). Numpy multiplication doesn't work normally in this case due to int overflow; seems, an implementation has the same problem.

To compare, the correct answer is

1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 1 0
20000231 13439499 24797837 33551452 25457599 31924387 35084770.

--
All the best,
Siggy Laewsky

let H = AR, H is HNF of A, then H=(h_{ij}) should satisfy the following conditions:
(1) h_{ij} = 0 (for i < j)
(2) h_{ii} >= 0
(3) 0 <= h_{ij} < h_{ii} (for i > j s.t. h_{ii} > 0)
(4) h_{ij} = 0 (for i > j s.t. h_{ii} = 0)

But, (3) and (4) are broken in my current implementation......