What is the fastest method for computing determinants?

  • Context: MHB 
  • Thread starter Thread starter Jundoe
  • Start date Start date
  • Tags Tags
    Matrix
Click For Summary

Discussion Overview

The discussion revolves around methods for computing determinants of matrices, particularly focusing on the process of transforming matrices into upper triangular form. Participants explore the implications of row operations on the determinant and share various techniques, including the rule of Sarrus and Gaussian elimination.

Discussion Character

  • Technical explanation
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant questions the legality of dividing a row by an integer during the process of creating an upper triangular matrix, seeking clarification on its effect on the determinant.
  • Several participants clarify that multiplying or dividing a row by a constant alters the determinant by that constant, indicating that dividing by 2 would also divide the determinant by 2.
  • Another participant notes that the algorithm for calculating a determinant differs from solving a system of equations, but the principle remains the same regarding row operations.
  • One participant suggests using the rule of Sarrus for quick determinant calculations, especially for matrices with many zeros.
  • Another participant mentions that they were using a 3x3 example to understand concepts applicable to larger matrices, specifically for a final exam requiring the determinant of a 4x4 matrix.
  • There is a suggestion that one can always reduce a 4x4 matrix to a 3x3 matrix, prompting further inquiry about the method to achieve this.
  • Some participants discuss the expansion by minors as a method for calculating the determinant of a 4x4 matrix, with one participant expressing satisfaction with this method over reaching an upper triangular form.
  • A participant mentions the Bareiss algorithm as a faster method for computing determinants, indicating a preference for methods that minimize errors.

Areas of Agreement / Disagreement

Participants generally agree on the effects of row operations on the determinant, but there are multiple competing views on the fastest method for computing determinants, with no consensus reached on a single preferred approach.

Contextual Notes

The discussion includes various assumptions about the applicability of methods to different matrix sizes and the potential for error in calculations, which remain unresolved.

Jundoe
Messages
10
Reaction score
0
I want to make an upper triangular matrix. From this:
$\begin{bmatrix}2&0&1\\0&1&1\\3&1&0 \end{bmatrix}$

The first is the correct one. The second is incorrect, yet I fail to understand why.

$\begin{bmatrix}2&0&1\\0&1&1\\3&1&0 \end{bmatrix}$

$\begin{bmatrix}2&0&1\\0&1&1\\0&1&-3/2 \end{bmatrix}$

$\begin{bmatrix}2&0&1\\0&1&1\\0&0&-5/2 \end{bmatrix}$
Second method.

$\begin{bmatrix}2&0&1\\0&1&1\\3&1&0 \end{bmatrix}$

$\begin{bmatrix}1&0&1/2\\0&1&1\\3&1&0 \end{bmatrix}$ As you can see, I've immediately divided the first row by 2 so that I can get a pivot of 1.

$\begin{bmatrix}1&0&1/2\\0&1&1\\0&1&-3/2 \end{bmatrix}$

$\begin{bmatrix}1&0&1/2\\0&1&1\\0&0&-5/2 \end{bmatrix}$What happened? Is dividing a row by an integer illegal?

[edit.] The reason for the upper triangular matrix, is because I want to find the determinant.
I am aware that switching rows causes the sign to change. No big issue, because I can note this, and at the end adjust the determinant accordingly. But is this similar? Is the returned determinant supposed to be re-multiplied because I had divided it first?
 
Last edited:
Physics news on Phys.org
Re: upper triangular matrix

When you multiply a row (or a column) by a constant, you multiply the determinant by that constant. So when you divided the top row by 2, you were also dividing the determinant by 2.
 
Re: upper triangular matrix

The algorithm to calculate a determinant is slightly different from the algorithm to solve a system of equations.
The principle is the same though.
If you divide a row by a number, you also have to divide the result by that number.
 
Re: upper triangular matrix

Jundoe said:
I want to make an upper triangular matrix. From this:
$\begin{bmatrix}2&0&1\\0&1&1\\3&1&0 \end{bmatrix}$

The first is the correct one. The second is incorrect, yet I fail to understand why.

$\begin{bmatrix}2&0&1\\0&1&1\\3&1&0 \end{bmatrix}$

$\begin{bmatrix}2&0&1\\0&1&1\\0&1&-3/2 \end{bmatrix}$

$\begin{bmatrix}2&0&1\\0&1&1\\0&0&-5/2 \end{bmatrix}$
Second method.

$\begin{bmatrix}2&0&1\\0&1&1\\3&1&0 \end{bmatrix}$

$\begin{bmatrix}1&0&1/2\\0&1&1\\3&1&0 \end{bmatrix}$ As you can see, I've immediately divided the first row by 2 so that I can get a pivot of 1.

$\begin{bmatrix}1&0&1/2\\0&1&1\\0&1&-3/2 \end{bmatrix}$

$\begin{bmatrix}1&0&1/2\\0&1&1\\0&0&-5/2 \end{bmatrix}$What happened? Is dividing a row by an integer illegal?

[edit.] The reason for the upper triangular matrix, is because I want to find the determinant.
I am aware that switching rows causes the sign to change. No big issue, because I can note this, and at the end adjust the determinant accordingly. But is this similar? Is the returned determinant supposed to be re-multiplied because I had divided it first?
Hello,
You could Also use rule of sarrus (would take you only 10-15 sec calculate it out)! You got many zero in the matrix so it would be easy to think out the answer!
Or maybe you wanted to practice with reducing the matrix.
Regards,
$$|\pi\rangle$$
 
Re: upper triangular matrix

Petrus said:
Hello,
You could Also use rule of sarrus (would take you only 10-15 sec calculate it out)! You got many zero in the matrix so it would be easy to think out the answer!
Or maybe you wanted to practice with reducing the matrix.
Regards,
$$|\pi\rangle$$

Actually this was an example. I was trying to understand this for a larger matrix seeing as my final will request I find the determinant of a 4x4. *I must've missed that vital information from my textbook–again, thanks EVERYONE for your inputs.

That said, when it comes to finding the determinant for a Cramer's rule application, our finals usually don't go over 3x3, so the rule of Sarrus is awesome for that.
 
Re: upper triangular matrix

Jundoe said:
Actually this was an example. I was trying to understand this for a larger matrix seeing as my final will request I find the determinant of a 4x4. *I must've missed that vital information from my textbook–again, thanks EVERYONE for your inputs.

That said, when it comes to finding the determinant for a Cramer's rule application, our finals usually don't go over 3x3, so the rule of Sarrus is awesome for that.
You can ALWAYS make a 4x4 matrix to 3x3 matrix.

Regards,
$$|\pi\rangle$$
 
Re: upper triangular matrix

Petrus said:
You can ALWAYS make a 4x4 matrix to 3x3 matrix.

Regards,
$$|\pi\rangle$$

This is intriguing. How would I proceed?
Would I have to multiply the [4x4]matrix by some [4x3]matrix, then take the new [4x3] result and have it multiplied like so: [3x4][4x3], thus yielding a [3x3]?

...a google search only offered programmer contents.
 
Re: upper triangular matrix

Jundoe said:
This is intriguing. How would I proceed?
Would I have to multiply the [4x4]matrix by some [4x3]matrix, then take the new [4x3] result and have it multiplied like so: [3x4][4x3], thus yielding a [3x3]?

...a google search only offered programmer contents.
Nop, you expand. Here is a explain Expansion by Minors | Introduction to Linear Algebra | FreeText Library
And here you got an exemple of calculatong determinant of 4x4 matrix http://nebula.deanza.edu/~bloom/math43/Determinant4x4Matrix.pdf
Regards,
$$|\pi\rangle$$
 
  • #10
Re: upper triangular matrix

Petrus said:
Nop, you expand. Here is a explain Expansion by Minors | Introduction to Linear Algebra | FreeText Library
And here you got an exemple of calculatong determinant of 4x4 matrix http://nebula.deanza.edu/~bloom/math43/Determinant4x4Matrix.pdf
Regards,
$$|\pi\rangle$$

Just tried it out. This is much better than doing it by reaching an upper triangle. I don't know which is faster, but for my final I'm definitely going with this method. It's less error-prone. :D

Thanks!
 
  • #11
Re: upper triangular matrix

Jundoe said:
Just tried it out. This is much better than doing it by reaching an upper triangle. I don't know which is faster, but for my final I'm definitely going with this method. It's less error-prone. :D

Thanks!

So far as I know, the fastest exact method for computing determinants is basically Gaussian row-reduction to an upper-triangular matrix. (They have fancy variants of it like the Bareiss algorithm.)
 

Similar threads

Undergrad Factoring Matrices with Elementary Row Operations
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Passive Transformation and Rotation Matrix
  • · Replies 1 ·
Replies
1
Views
4K
Undergrad On a bound on the norm of a matrix with a simple pole
  • · Replies 8 ·
Replies
8
Views
3K
Graduate How to augment a machine learning matrix?
  • · Replies 10 ·
Replies
10
Views
3K
Undergrad Can one find a matrix that's 'unique' to a collection of eigenvectors?
  • · Replies 33 ·
2
Replies
33
Views
3K
Undergrad Basis of 2x2 matrices with real entries
  • · Replies 11 ·
Replies
11
Views
6K
Undergrad Transform a 2x2 matrix into an anti-symmetric matrix
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Determining elements of Markov matrix from a known stationary vector
  • · Replies 24 ·
Replies
24
Views
3K
High School How to multiply matrix with row vector?
  • · Replies 4 ·
Replies
4
Views
4K
MHB Find Matrix A for System Ax=1, 3
  • · Replies 12 ·
Replies
12
Views
2K