BasicLinearAlgebraToolsPurePy icon indicating copy to clipboard operation
BasicLinearAlgebraToolsPurePy copied to clipboard

Fixed `determinant_fast()`

Open RandomGamingDev opened this issue 7 months ago • 2 comments

The Algorithm's Issue

When trying to implement the matrix multiplication algorithm in this library (getting the REF (Row Echelon Form) with Gaussian Elimination and then multiplying the main diagonal for the determinant) I found the issue with determinant_fast() that was also mentioned by issue https://github.com/ThomIves/BasicLinearAlgebraToolsPurePy/issues/2. The pivot being 0 would cause determinant_fast() to return the wrong determinant due to the lack of row swapping.

The Fix

This pull request fixes that by adding row swapping like this on line 331:

            found = False
            for i in range(fd+1,n):
                if AM[i][fd] != 0:
                    temp = AM[fd]
                    AM[fd] = AM[i]
                    AM[i] = temp
                    found = True
                    odd_swaps = not odd_swaps
                    break
            if not found:
                return 0 # If there are no other rows that can do that then return the determinant of 0

alongside the odd_swaps variable for check whether there's been an odd number of swaps and the negator at the end for if there has been an odd number of swaps. and removing the "cheat":

            AM[fd][fd] = 1.0e-18  # Cheating by adding zero + ~zero

from here

The Mistake

Contrary to what's said in the article:

"(I did develop a fancy way to reorder rows based on the number of leading zeros and keep track of how many times that was done, so that I could change the final sign of the determinant, but DANG! Just more code and more steps. Cheating was better!"

the cheat and fancy system that includes keeping track of the number of times rows were swapped to change the sign at the end isn't required, all that's required is row swapping and a boolean to tell whether or not there's been an odd number of swaps.

Please update the article

https://integratedmlai.com/find-the-determinant-of-a-matrix-with-pure-python-without-numpy-or-scipy/

The Solution for those who are trying to use the algorithm

The author doesn't appear to be active on his github, so hopefully this'll help anyone who's confused just copy determinant_fast() from my pull request here: https://github.com/RandomGamingDev/BasicLinearAlgebraToolsPurePy/blob/master/LinearAlgebraPurePython.py#L315

How can I contact @ThomIves

Also, I don't know how to contact the author so it'd be appreciated if someone who did know could help contact him or send his contact details to me so that we can update the article.

RandomGamingDev avatar Nov 24 '23 05:11 RandomGamingDev