Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- For example, to solve mx + ny = gcd(x,y) one begins with
- two rows [m 1 0], [n 0 1], representing the two
- equations m = 1m + 0n, n = 0m + 1n. Then one executes
- the Euclidean algorithm on the numbers in the first column,
- doing the same operations in parallel on the other columns,
- Here is an example: d = x(80) + y(62) proceeds as:
- in equation form | in row form
- ---------------------+------------
- 80 = 1(80) + 0(62) | 80 1 0
- 62 = 0(80) + 1(62) | 62 0 1
- row1 - row2 -> 18 = 1(80) - 1(62) | 18 1 -1
- row2 - 3 row3 -> 8 = -3(80) + 4(62) | 8 -3 4
- row3 - 2 row4 -> 2 = 7(80) - 9(62) | 2 7 -9
- row4 - 4 row5 -> 0 = -31(80) -40(62) | 0 -31 40
- row1 row2 row3 row4 row5
- namely: 80, 62, 18, 8, 2 = Euclidean remainder sequence
- | |
- for example 62-3(18) = 8, the 2nd step in Euclidean algorithm
- becomes: row2 -3 row3 = row4 on the identity-augmented matrix.
- In effect we have row-reduced the first two rows to the last two.
- The matrix effecting the reduction is in the bottom right corner.
- It starts as the identity, and is multiplied by each elementary
- row operation matrix, hence it accumulates the product of all
- the row operations, namely:
- [ 7 -9] [ 80 1 0] = [2 7 -9]
- [-31 40] [ 62 0 1] [0 -31 40]
- The 1st row is the particular solution: 2 = 7(80) - 9(62)
- The 2nd row is the homogeneous solution: 0 = -31(80) + 40(62),
- so the general solution is any linear combination of the two:
- n row1 + m row2 -> 2n = (7n-31m) 80 + (40m-9n) 62
- The same row/column reduction techniques tackle arbitrary
- systems of linear Diophantine equations. Such techniques
- generalize easily to similar coefficient rings possessing a
- Euclidean algorithm, e.g. polynomial rings F[x] over a field,
- Gaussian integers Z[i]. There are many analogous interesting
- methods, e.g. search on keywords: Hermite / Smith normal form,
- invariant factors, lattice basis reduction, continued fractions,
- Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.
Add Comment
Please, Sign In to add comment