inverse of a matrix with Fraction entries

[Mark Wooding]

Daniel Fetchinson <fetchinson at googlemail.com> writes:

> > I wouldn't do it that way.  Let M be your matrix.  Work out the LCM l of
> > the denominators, and multiply the matrix by that to make it an integer
> > matrix N = l M.  Then work out the determinant d of that integer matrix.
> > Next, the big step: use Gaussian elimination to find a matrix A (the
> > `adjugate matrix') such that A N = d I.  This should be doable entirely
> > using integer arithmetic, and I think without needing any divisions.
> > Finally, we have l A M = d I, so (l/d A) M = I and l/d A is the inverse
> > you seek.
> >
> > Does that make sense?
>
> Absolutely! But there is nothing wrong with working out the inverse
> directly using fractions.Fraction arithmetic, I'd think.

It'll work, certainly; but the Fraction implementation will have to do a
buttload of GCD computations that it wouldn't need to do if you worked
with plain integers.  And GCDs are relatively hard, as arithmetical
computations go: the usual algorithms require either a number of
divisions (which are themselves rather costly) or a bitwise traversal of
one of the operands.

A million entries seems nontrivial for a matrix, and Gaussian
elimination has cubic running time if I remember rightly; I suspect that
the transformations I describe would reduce the running time by a fair
amount.  Of course, I might be drastically underestimating the
performance of modern hardware -- I often do -- so this may not be
especially relevant.  Anyway, the possibility's there.

-- [mdw]