About the Kannan-Bachem algorithm
arXiv:2411.02422
Abstract
The Smith reduction is a basic tool when analyzing integer matrices up to equivalence, and the Kannan-Bachem (KB) algorithm is the first polynomial algorithm computing such a reduction. Using this algorithm in complicated situations where the rank of the studied matrix is not maximal revealed an unexpected obstacle in the algorithm. This difficulty is described, analyzed, a simple solution is given to overcome it, finally leading to a general organization of the KB algorithm, simpler than the original one, efficient and having a general scope.
An equivalent algorithm is used by the Magma program, without any detailed explanation, without any reference. The present text could so be useful