bestnorm = Min[(#.#)& /@ matrix];
While[True,
i=RandomInteger[{1, Length[matrix]}];
j=RandomInteger[{1, Length[matrix]}];
While[i==j, j=RandomInteger[{1, Length[matrix]}]];
s=If[Random[]>0.5, 1, -1];
new=matrix[[i]]+s*matrix[[j]];
new /= GCD@@new;
If[(norm=new.new) < matrix[[i]].matrix[[i]] || Random[]<E^(-1/T),
matrix[[i]] = new;
++changes;
If[norm<bestnorm, bestnorm=norm;Print[{norm, changes, new}]]
]
]

While[True,
v=matrix[[i=RandomInteger[{1, Length[matrix]}]]];
j=RandomInteger[{1, Length[matrix]}];
While[i==j, j=RandomInteger[{1, Length[matrix]}]];
w=matrix[[j]];
a=Round[v.w/(w.w)];
If[a ≠ 0 || (T>0 &&  Random[]<E^(-1/T)),
new=matrix[[i]]-a*matrix[[j]];
new /= GCD@@new;
matrix[[i]] = new;
++changes
]
]

{39.98293143957809`, 39.45488114797465`,38.794064687156094`, 38.078875097136475`, 29.036082757450593`}

matrix[[9]].matrix[[4]]

Random[]<E^(-1/T)

matrix