search

ivanseed / google-foobar-help

Guidance on how to tackle some of the foobar challenges.
174 stars 47 forks source link

How do you calculate inverse of matrix with fractions? #17

Closed mehtasagar closed 3 years ago

mehtasagar commented 7 years ago

I ma trying to follow the method given here. To calculate inverse of the matrix, what approach should I follow to maintain the output in Fractions of integers as given in post. Let me know if you need more details?

franklinvp commented 6 years ago

@mehtasagar In general one shouldn't compute the inverse matrix $(I-Q)^{-1}$}. That is not efficient, since it would effectively compute (I-Q)^{-1}I. Since the final goal is to compute (I-Q)^{-1}R what you should do is compute this directly by computing the columns of this matrix. The i-th column of this matrix is the solution X_i of the system (I-Q)X_i = R_i, where R_i is the i-th column of R and X_i is a column vector. To solve these systems of equations, you better first factor I-Q in LU decomposition. This is, a product of a lower triangular matrix L and an upper triangular matrix. Then for each system LUX_i=R_i you only need to do back substitution with L and forward substitution for U. Search how to do LU decomposition and implement it for fractions, if some library doesn't have it already. In most places they will have it implemented for floating point (https://en.wikipedia.org/wiki/LU_decomposition#C_code_examples). Just replace the floating point types with your own rational number (pairs of integers) type.

franklinvp commented 6 years ago

@mehtasagar I did a Python implementation here, with plenty of comments. The LU and back/forth-substitution are the same as the Wikipedia page above, but written to use fractions instead of doubles.