CODEWITHSUNDEEP
matrixfortran
Kurapika
Kurapika

Reputation: 41

Interpreting the program for finding determinant of a matrix

This is the sample code I've found for calculating the determinant of an (nxn) matrix and it works fine and all but I'm having trouble understanding what's happening in the conversion to triangular form section. Can someone explain what's happening in the "Conversion to upper triangular part"?

I don't have trouble calculating the determinant on my own or doing any upper triangular form conversions but I just don't get how this all translates here in this program.

ii) What is happening with integers (i,j,k,l)? Specifically, what is k and l doing? What is happening inside the IF construct? For a matrix A, I know that something like A(i,j) indicates its position in the matrix and that's all I've ever needed for any matrix programs I've worked with in the past.

========================================================================

    !Function to find the determinant of a square matrix
    !Description: The subroutine is based on two key points:
    !1] A determinant is unaltered when row operations are performed: Hence, 
    using this principle,
    !row operations (column operations would work as well) are used
    !to convert the matrix into upper traingular form
    !2]The determinant of a triangular matrix is obtained by finding the 
    product of the diagonal elements

    REAL FUNCTION FindDet(matrix, n)
        IMPLICIT NONE
        REAL, DIMENSION(n,n) :: matrix
        INTEGER, INTENT(IN) :: n
        REAL :: m, temp
        INTEGER :: i, j, k, l
        LOGICAL :: DetExists = .TRUE.

        l = 1
        !Convert to upper triangular form
        DO k = 1, n-1
            IF (matrix(k,k) == 0) THEN
                DetExists = .FALSE.
                DO i = k+1, n
                    IF (matrix(i,k) /= 0) THEN
                        DO j = 1, n
                            temp = matrix(i,j)
                            matrix(i,j)= matrix(k,j)
                            matrix(k,j) = temp
                        END DO
                        DetExists = .TRUE.
                        l=-l
                        EXIT
                    ENDIF
                END DO
                IF (DetExists .EQV. .FALSE.) THEN
                    FindDet = 0
                    return
                END IF
            ENDIF
            DO j = k+1, n
                m = matrix(j,k)/matrix(k,k)
                DO i = k+1, n
                    matrix(j,i) = matrix(j,i) - m*matrix(k,i)
                END DO
            END DO
        END DO

        !Calculate determinant by finding product of diagonal elements
        FindDet = l
        DO i = 1, n
            FindDet = FindDet * matrix(i,i)
        END DO

    END FUNCTION FindDet

Upvotes: 2

Views: 566

Answers (1)

Rodrigo Rodrigues
Rodrigo Rodrigues

Reputation: 8556

In this implementation, you can interpret the indices i, j, k, l as the following:

  • i and j: will be used interchangeably (there is no consistence in the code in this regard) to represent the row and column coordinates of an element of the matrix.
  • k: will iterate over the "dimension" of the matrix, without meaning a coordinated position. Or, in a different abstraction, iterates over the diagonal.
  • l: will be +1 or -1, alternating its value anytime the algorithm performs a line-switch. It takes into account that switching any two rows of a matrix reverses the sign of its determinant.

So, the interpretation of the code is:

At each iteration over the dimension of the matrix:
  First, check if this diagonal element is zero. If it is zero:
    ALARM: maybe the matrix is degenerate.
    Let's find it out. Iterate downwards over the rest of this row, trying to find a non-zero element.
      If you find a row with a non-zero element in this column, if was a false alarm. Perform row-switch and invert the sign of the determinant. Go on.
      If there were all zeroes, then the matrix is degenerate. There is nothing else to do, determinant is zero.
  Going on. For each row below this diagonal:
    Perform sums and subtractions on the rest of the rows, constructing the diagonal matrix.
Finally, calculate the determinant by multiplying all the elements on the diagonal, taking the sign changes into acount.

Upvotes: 2

Related Questions