Given an \$m \times n\$ matrix of integers A, there exist a \$m \times m\$ matrix P, an \$m \times n\$ matrix D, and an \$n \times n\$ matrix Q such that:
- \$A = P D Q\$.
- P and Q are unimodular matrices (i.e. matrices which are invertible and whose inverses are also integer matrices);
- D is diagonal;
- each diagonal entry \$d_{ii}\$ of D is nonnegative; and
- \$d_{11} \mid d_{22} \mid \cdots \mid d_{nn} \$.
Furthermore, the matrix D is unique in this representation.
Depending on context, the Smith normal form of A is either just the diagonal matrix D, or a Smith normal form decomposition of A is the tuple \$(P, D, Q)\$. For this challenge, you only need to calculate D.
One common way to calculate D is via an algorithm that looks like a combination of the Euclidean algorithm for calculating gcd and Gaussian elimination -- applying elementary row and column operations until the matrix is in the desired format for D. Another way to calculate D is to use the fact that for each i, \$d_{11} d_{22} \cdots d_{ii}\$ is equal to the gcd of all determinants of \$i\times i\$ submatrices (including non-contiguous submatrices) of A.
The challenge
You are to write a function or program that calculates the Smith normal form of an input matrix. The output may either be in the form of the full matrix D, or in the form of a list of the diagonal entries of D. In an imperative programming language, it is also acceptable to write a function that takes a matrix by reference and mutates the matrix into its Smith normal form.
Rules
- This is code-golf: shortest code wins.
- Standard loophole prohibitions apply.
- You do not need to worry about integer overflow, if that applies in your language.
Examples
1 2 3 1 0 0
4 5 6 -> 0 3 0
7 8 9 0 0 0
6 10 1 0
10 15 -> 0 10
6 0 0 1 0 0
0 10 0 -> 0 30 0
0 0 15 0 0 30
2 2 2 0
2 -2 -> 0 4
2 2 4 6 2 0 0 0
2 -2 0 -2 -> 0 4 0 0
3 3 3 1 0 0
4 4 4 -> 0 0 0
5 5 5 0 0 0
Note: Mathematica already has a built-in to calculate Smith normal form. As such, you can use this to play around with test cases: Try it online!