3
\$\begingroup\$

This is an addition of my previous question Python matrix class. I've added a determinant function using Laplace expansion to my Matrix class. What I am looking for specifically is how 3x3 matrices are calculated, as I feel there is a better way instead of creating three matrices separately and indexing them.

class Matrix:

    # ... other functions removed for brevity ...

    # included for context
    def __init__(self, arrays: list[list[int | float]) -> None:
        self.arrays = copy.deepcopy(arrays)
        self.width = len(arrays[0])
        self.height = len(arrays)


    def determinant(self) -> int | float:
        """
        Finds the determinant of a 2x2 or a 3x3 matrix.

        >>> Matrix([[4, 6], [3, 8]]).determinant()
        14

        >>> Matrix([[2, 7, 9], [1, 15, 4], [12, 21, 4]]).determinant()
        -1171
        """

        def tbtdet(m: Matrix) -> int | float:
            """ 'Two By Two Determinant' => ad - bc """
            return (m[0][0] * m[1][1]) - (m[0][1] * m[1][0])

        if (self.width, self.height) == (2, 2):
            return tbtdet(self.arrays)
        
        if (self.width, self.height) == (3, 3):
            a = Matrix([[self.arrays[1][1], self.arrays[1][2]], [self.arrays[2][1], self.arrays[2][2]]])
            b = Matrix([[self.arrays[1][0], self.arrays[1][2]], [self.arrays[2][0], self.arrays[2][2]]])
            c = Matrix([[self.arrays[1][0], self.arrays[1][1]], [self.arrays[2][0], self.arrays[2][1]]])
            return (self.arrays[0][0] * tbtdet(a)) - (self.arrays[0][1] * tbtdet(b)) + (self.arrays[0][2] * tbtdet(c))

        raise NotImplementedError("Currently only supports 2x2 and 3x3 matricies.")
\$\endgroup\$

3 Answers 3

4
\$\begingroup\$

doctest

Thank you for the beautiful doctests. I assume you're using $ python -m doctest *.py every now and again to ensure they don't bit rot.

You might use fewer ' single quotes within a docstring.

naming

        def tbtdet ...

Prefer tbt_det().

ints are floats

The spec explains that

numeric types ... float and int are not subtypes of each other, but to support common use cases, the type system contains a straightforward shortcut: when an argument is annotated as having type float, an argument of type int is acceptable;

In several places your int | float could be shortened to just float.

smaller matrices

better way instead of creating three matrices separately

No, sorry, the OP code looks like the best way to me.

We could focus on generating sets of indices, and up at the calling layer we use them to produce matrices. It might generalize more nicely to Laplace expansions on larger matrices. But it wouldn't be more readable. For the current problem, what you have here impresses me as the most sensible solution.

\$\endgroup\$
3
\$\begingroup\$

What I am looking for specifically is how 3x3 matrices are calculated, as I feel there is a better way instead of creating three matrices separately and indexing them.

I don't know, it looks reasonable to me. By the way I would not worry about how to generalize this to larger matrices, as Laplace expansion very quickly becomes an unreasonable algorithm to use. Since you are handling not only floating point matrices but also integer matrices, you may be interested in the Bareiss algorithm.

\$\endgroup\$
3
\$\begingroup\$

Please make sure to copy paste code you've written into your post. You're missing import copy and a ] in your __init__ type signature.

'Two By Two Determinant ...': As a general rule, if you need a comment saying "the previous abbreviation means ...", consider less of an abbreviation. That makes your code better at self-documenting. I would also argue that ad-bc is well known enough that you can eliminate that comment entirely.

Actually, I would move the 2x2 determinant calculation into the == (2, 2) branch, and remove the tbtdet function entirely, but that may be more a matter of taste.

NotImplementedError suggests that this may work in the future. And that's true for 4x4 matrices. But for height!=width, TypeError would be more appropriate.

Probably the most interesting comment ("Laplace expansion") isn't in your code.

One way to simplify your 3x3 calculation is to use array slicing, so that [self.arrays[1][1], self.arrays[1][2]] == self.arrays[1][1:], etc. But a better way might be to move "delete row i and column j" into its own function. Then your approach is "go through the first row, using those entries to find the cofactors." And we can implement that as a loop:

This still creates 3 new matrices, but we're not specifying the indices, which is going to be error prone. As a bonus, our loop now works for 4x4 and higher (although as noted elsewhere will be slow for large matrices). So we no longer need the NotImplementedError.

Since we've checked that the matrix is square, we could only test one of the dimensions. If we still want to test both dimensions, we could have self.width == self.height == 2 to skip the tuples. But since numpy usually thinks of a matrix shape as a tuple, lets leave it like that.

Actually, our loop also works for 2x2 if we decide that the determinant of a 1x1 is the lone entry.

Our result:

import copy

class Matrix:

    # ... other functions removed for brevity ...

    def __init__(self, arrays: list[list[float]]) -> None:
        self.arrays = copy.deepcopy(arrays)
        self.width = len(arrays[0])
        self.height = len(arrays)

    def sub_matrix(self, row_to_del: int, col_to_del: int) -> 'Matrix':
        _sub_matrix = copy.deepcopy(self)
        del _sub_matrix.arrays[row_to_del]
        for row in _sub_matrix.arrays:
            del row[col_to_del]
        _sub_matrix.width -= 1
        _sub_matrix.height -= 1
        return _sub_matrix

    def determinant(self) -> float:
        """
        Finds the determinant of a square matrix using Laplace (cofactor) expansion.

        >>> Matrix([[4, 6], [3, 8]]).determinant()
        14

        >>> Matrix([[2, 7, 9], [1, 15, 4], [12, 21, 4]]).determinant()
        -1171
        """

        if self.width != self.height:
            raise TypeError("Determinant only defined for square matrices.")
        if (self.width, self.height) == (1, 1):
            return self.arrays[0][0]
        first_row = self.arrays[0]
        sign = 1
        det = 0
        for col in range(self.width):
            det += sign * first_row[col] * self.sub_matrix(0,col).determinant()
            sign *= -1
        return det
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.