The algorithm of Section 8 for finding, given A, unimodular matrices M and N such that MAN is diagonal can be justified without even mentioning `tilts'. The basic idea is that adding a row to an adjacent row in a product matrix AB is the same as adding that row to that adjacent row in A and multiplying the result on the left by B. Similarly, subtracting a row from an adjacent row of AB is the same as performing the subtraction on A and multiplying the result on the left by B. As for adding a column to an adjacent column of AB, this is accomplished by doing the same column addition on B and then multiplying the result on the left by A, and similarly for subtraction of a column from an adjacent column. These statements all follow from an examination of the way in which a matrix product is computed.
At each step of the algorithm of Section 8, one has an (m+n)x(m+n) matrix consisting of an upper left mxn corner, call it B, an upper right mxm corner, call it M, a lower left nxn corner, call it N, and a lower right nxm corner consisting of zeros (except for the number m in the lower right corner entry used by the Matlab programs). At the outset, B is A and M and N are identity matrices. Therefore, at the outset, MAN = B.
The steps of the algorithm do one of four things, each of which leaves the equation MAN = B intact. First, one may add a row of B to an adjacent row of B and add the same row of M to the same adjacent row of M. This changes M and B, and leaves N unchanged, in such a way that, by the above observation, the new M times AN is the new B. Or, the operation may be a row subtraction, which is similar. Or, the operation may add a column of B to an adjacent column and add the same column of N to the same adjacent column, in which case MA times the new N is the new B, given that MA times the old N is the old B. Finally, a column subtraction also leaves the equation MAN = B intact.
Clearly, at each step M and N are unimodular, that is, are equivalent to identity matrices, because they start out as identity matrices and the operations that are performed transform them to equivalent matrices at each step.
Thus, if a sequence of steps that transform A into a diagonal matrix D are applied to the matrix hat(A), it will terminate with a matrix that has D in the upper left corner, and unimodular matrices M and N in the upper right and lower left corners respectively, with the property that MAN = D, as was to be shown.
Return to Chapter 2.