Sheng Li (gmachine1729) wrote,
Sheng Li

How to solve integer matrix equations

Originally published at 狗和留美者不得入内. You can comment here or there.

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


wherein [公式] .

Proof: Invertible square integer matrices are generated by

  1. Those which are diagonal and such that diagonal elements are all units, in this case all [公式] .
  2. Those which swap rows or columns.
  3. 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.

Base case:

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.

Case 1:

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.

Case 2:

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.

Case 3:

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.

Case 4:

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 [1]. A reader not comfortable with such rigor is of course welcome to read [1]. I believe that it was also much the process of writing up [1] that made this theorem more or less trivial for me to prove.


Tags: uncategorized

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened