Take an arbitrary matrix of integer values and an column vector of integers . We wish to find all such that . In order to do so, we prove the following proposition.
Theorem for diagonalization of integer matrices For any integer matrix , there exists square integer matrices such that is of the form
Proof: Invertible square integer matrices are generated by
- Those which are diagonal and such that diagonal elements are all units, in this case all .
- Those which swap rows or columns.
- Those which add an integer multiple of one row to another row (or one column to another column).
We shall proof this theorem by induction on the partial order of . We will assume also that the matrix is not all zeros, for which the theorem trivially holds.
In the base case where or , one uses the Euclidean algorithm repeatedly on two arbitrary non-zero elements (done per 3) until all but one of the elements is non-zero. Finally, one swaps the non-zero element to the first row or column.
In the case of where and WLOG , we first make the following sequence of transformations, where is the unique integer quotient equal to :
Now, it suffices to prove that every matrix integer matrix, which can be expressed in the form , where is a and is and is , can be reduced to the form . To do this, we first observe that if there is an element in the first column that divides every element in the first column in addition to dividing all elements in its row, there one can realize this reduction by swap its row with the first row and then adding an integer of the first row to every other row to null out the all of the other entries of the first column. One of course can do similar to null out all but the first entry of the first row as well. Analogous of course also holds with there is an element in the first row that divides element in the first row in addition to dividing all elements in its column.
When is not a factor of some element in or , one can apply operations corresponding to an iteration of the Euclidean algorithm on those two elements to decrease the value of . We notice that if , the matrix is necessarily one of Case 1. Since when the matrix is not in base form, must strictly decrease after an iteration of the procedure described above, repeated iteration of that procedure must eventually result in an matrix of Case 1.
The matrix is diagonal and there is a diagonal entry, which we shall call , that divides every other diagonal entry. We note that if one of the diagonal entries is , Case 3 is trivially satisfied. We take the matrix obtained by removing the row and column of . By our inductive hypothesis, we can apply the desired reduction to that. We have that multiplication of a matrix in Case 3 by any invertible integer matrix cannot decrease the greatest common divisor of all the entries in it, which is necessarily a factor of, which proves this case.
By our inductive hypothesis, we can assume that can be reduced to diagonal form with the desired divisibility condition. After such a reduction, if the matrix is in Case 3, then we are finished. If not, there must exist two row indices and two column indices such that its corresponding matrix is in Case 1. We then perform the reduction associated with Case 1 for the two rows and two columns, necessarily decreasing one of the matrix elements in the process. Either the algorithm will terminate to a Case 3 matrix without a unit in the diagonal, or it will terminate with a unit in the diagonal, in which case the matrix is in Case 3. This completes our inductive proof.
Now to solve , we diagonalize such that and , which gives . In solving for , the entries corresponding to a non-zero diagonal entry in exist and are unique iff divisibility holds in each case, and the entries corresponding to zero diagonal entry can be arbitrary. Multiplying this solution set by then gives the solution set for .
Propositions regarding quotients, remainders, divisibility, and greatest common divisors in the Euclidean domain of integers were proven in full rigor in . A reader not comfortable with such rigor is of course welcome to read . I believe that it was also much the process of writing up  that made this theorem more or less trivial for me to prove.