LLL Hermite normal form algorithm: 4x4 Example
alpha=1
P A
1 0 0 0 -6 9 -15 -18
0 1 0 0 4 -6 10 12 (1)
0 0 1 0 10 -15 18 35
0 0 0 1 -24 36 -46 -82
Row 1 -> - Row 1
-1 0 0 0 6 -9 15 18
0 1 0 0 4 -6 10 12 (2)
0 0 1 0 10 -15 18 35
0 0 0 1 -24 36 -46 -82
Swapping Rows 1 and 2
0 1 0 0 4 -6 10 12
-1 0 0 0 6 -9 15 18 (3)
0 0 1 0 10 -15 18 35
0 0 0 1 -24 36 -46 -82
Row 2 -> Row 2 - Row 1
0 1 0 0 4 -6 10 12
-1 -1 0 0 2 -3 5 6 (4)
0 0 1 0 10 -15 18 35
0 0 0 1 -24 36 -46 -82
Swapping Rows 1 and 2
-1 -1 0 0 2 -3 5 6
0 1 0 0 4 -6 10 12 (5)
0 0 1 0 10 -15 18 35
0 0 0 1 -24 36 -46 -82
Row 2 -> Row 2 - 2 x Row 1
-1 -1 0 0 2 -3 5 6
2 3 0 0 0 0 0 0 (6)
0 0 1 0 10 -15 18 35
0 0 0 1 -24 36 -46 -82
Swapping Rows 1 and 2
2 3 0 0 0 0 0 0
-1 -1 0 0 2 -3 5 6 (7)
0 0 1 0 10 -15 18 35
0 0 0 1 -24 36 -46 -82
Row 3 -> Row 3 - 5 x Row 2
2 3 0 0 0 0 0 0
-1 -1 0 0 2 -3 5 6 (8)
5 5 1 0 0 0 -7 5
0 0 0 1 -24 36 -46 -82
Swapping Rows 2 and 3
2 3 0 0 0 0 0 0
5 5 1 0 0 0 -7 5 (9)
-1 -1 0 0 2 -3 5 6
0 0 0 1 -24 36 -46 -82
Row 2 -> Row 2 + -2 x Row 1
2 3 0 0 0 0 0 0
1 -1 1 0 0 0 -7 5 (10)
-1 -1 0 0 2 -3 5 6
0 0 0 1 -24 36 -46 -82
Row 2 -> - Row 2
2 3 0 0 0 0 0 0
-1 1 -1 0 0 0 7 -5 (11)
-1 -1 0 0 2 -3 5 6
0 0 0 1 -24 36 -46 -82
Row 4 -> Row 4 + 12 x Row 3
2 3 0 0 0 0 0 0
-1 1 -1 0 0 0 7 -5 (12)
-1 -1 0 0 2 -3 5 6
-12 -12 0 1 0 0 14 -10
Swapping Rows 3 and 4
2 3 0 0 0 0 0 0
-1 1 -1 0 0 0 7 -5 (13)
-12 -12 0 1 0 0 14 -10
-1 -1 0 0 2 -3 5 6
Row 3 -> Row 3 + -2 x Row 2
2 3 0 0 0 0 0 0
-1 1 -1 0 0 0 7 -5 (14)
-10 -14 2 1 0 0 0 0
-1 -1 0 0 2 -3 5 6
Swapping Rows 2 and 3
2 3 0 0 0 0 0 0
-10 -14 2 1 0 0 0 0 (15)
-1 1 -1 0 0 0 7 -5
-1 -1 0 0 2 -3 5 6
Row 2 -> Row 2 + 5 x Row 1
2 3 0 0 0 0 0 0
0 1 2 1 0 0 0 0 (16)
-1 1 -1 0 0 0 7 -5
-1 -1 0 0 2 -3 5 6
Swapping Rows 1 and 2
0 1 2 1 0 0 0 0
2 3 0 0 0 0 0 0 (17)
-1 1 -1 0 0 0 7 -5
-1 -1 0 0 2 -3 5 6
The transformation matrix is
-1 -1 0 0
-1 1 -1 0
0 1 2 1
2 3 0 0
The row echelon Form is
2 -3 5 6
0 0 7 -5
0 0 0 0
0 0 0 0
Last altered 6th February 2007