12
$\begingroup$

How would I go about computing the determinant of large matrices, such as $6 \times 6$. I believe that I need to use multilinear maps, but I am not sure how I can go about computing the determinant in a nice and efficient way.

Can anyone show me how I can determine the determinant of the matrix below in a simple and efficient way?

\begin{pmatrix} 0 & 0& 1& 1& 1 & 1\\ 1 & 0 & 0 & 0& 0& 1\\ 1 & 0 & 1& 1 & 1 &1 \\ 0 & 1 & 1 & 1 & 0 &1 \\ 0 & 1 & 0& 1 & 0& 0\\ 0 & 0& 1& 0 & 0& 0 \end{pmatrix}

$\endgroup$
  • 6
    $\begingroup$ Do you know the effects that elementary row operations on a matrix have on its determinant? Consider row reducing first to get the matrix into a triangular form, keeping track of how whatever operations you used would have affected the final result. $\endgroup$ – JMoravitz Nov 9 '17 at 0:11
  • 7
    $\begingroup$ @Huffman_Coding It's not a case of similarity, it's Gaussian elimination. Every real matrix can be reduced to row echelon form by Gaussian elimination. $\endgroup$ – Robert Israel Nov 9 '17 at 0:19
  • 2
    $\begingroup$ There are algorithms for computing determinants of large matrices. They are complicated and fiddly and mostly a human would not want to do them. In this specific case I might try some Gaussian elimination but I would mainly observe that all elements are 0 or 1 which makes things easier on my poor brain and then I would try to go through the slow standard algorithm of breaking up into determinants of smaller matrices by considering all 1s in a row/column, the corresponding sign, and the matrix with that row and column removed. You can take rows in any order so choose well—start at the bottom. $\endgroup$ – Dan Robertson Nov 9 '17 at 0:25
  • 6
    $\begingroup$ $6 \times 6$ is not a particularly large matrix ;) Come back when you have some hundred thousand rows and columns. $\endgroup$ – mathreadler Nov 9 '17 at 6:58
  • 2
    $\begingroup$ @Rahul: Actually it's worse than exponential, it's factorial... $\endgroup$ – psmears Nov 9 '17 at 15:19
15
$\begingroup$

You can use Laplace's expansion of the determinant.

More precisely, begin expanding by the last row, then some row manipulation and expanding by convenient rows/columns ends up in a $2\times2$ determinant: \begin{align} \begin{vmatrix} 0&0&1&1&1&1 \\ 1&0&0&0&0&1 \\ 1&0&1&1&1&1 \\ 0&1&1&1&0&1 \\ 0&1&0&1&0&0 \\ 0&0&\color{red}1&0&0&0\end{vmatrix}&= -\begin{vmatrix} 0&0&1&1&1 \\ 1&0&0&0&1 \\ 1&0&1&1&1 \\ 0&1&1&0&1 \\ 0&1&1&0&0\end{vmatrix}= -\begin{vmatrix} 0&0&1&1&1 \\ 1&0&0&0&1 \\ 1&0&1&1&1 \\ 0&0&0&0&\color{red}1 \\ 0&1&1&0&0\end{vmatrix}= +\begin{vmatrix} 0&0&1&1 \\ \color{red}1&0&0&0 \\ 1&0&1&1 \\ 0&1&1&0 \end{vmatrix}\\ &=-\begin{vmatrix} 0&1&1 \\ 0&1&1 \\ \color{red}1&1&0 \end{vmatrix}=-\begin{vmatrix} 1&1 \\ 1&1 \end{vmatrix}=0. \end{align}

$\endgroup$
16
$\begingroup$

As mentioned in the comments above, row reduction can take you a long way. Each step in the row reduction process will change the determinant in a predefined fashion (e.g. swapping rows will multiply the determinant by negative one, adding two rows together won't change the determinant at all, etc...).

If going through the whole row reduction process is too tedious, you might try your luck at spotting whether any rows are linear combinations of others or if any columns are linear combinations of the others. If they are, then use what you know about invertible versus noninvertible matrices.

For your matrix, the second column plus the fifth column is equal to the fourth column.

$\endgroup$
5
$\begingroup$

While it is true that the determinant is zero and one can detect it, let me give a way to calculate the determinant without any clever observations. This idea will work in great generality, not relying on the structure of your specific example. Having a lot of zeroes makes it easier.

You can use row or column operations, and I have chosen rows. I always deduct the green row from the red one: $$ \begin{split} & \det\begin{pmatrix} 0&0&1&1&1&1 \\ \color{green}1&\color{green}0&\color{green}0&\color{green}0&\color{green}0&\color{green}1 \\ \color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}1&\color{red}1 \\ 0&1&1&1&0&1 \\ 0&1&0&1&0&0 \\ 0&0&1&0&0&0 \end{pmatrix} \\=& \det\begin{pmatrix} 0&0&1&1&1&1 \\ 1&0&0&0&0&1 \\ 0&0&1&1&1&0 \\ \color{red}0&\color{red}1&\color{red}1&\color{red}1&\color{red}0&\color{red}1 \\ \color{green}0&\color{green}1&\color{green}0&\color{green}1&\color{green}0&\color{green}0 \\ 0&0&1&0&0&0 \end{pmatrix} \\=& \det\begin{pmatrix} \color{red}0&\color{red}0&\color{red}1&\color{red}1&\color{red}1&\color{red}1 \\ 1&0&0&0&0&1 \\ \color{red}0&\color{red}0&\color{red}1&\color{red}1&\color{red}1&\color{red}0 \\ \color{red}0&\color{red}0&\color{red}1&\color{red}0&\color{red}0&\color{red}1 \\ 0&1&0&1&0&0 \\ \color{green}0&\color{green}0&\color{green}1&\color{green}0&\color{green}0&\color{green}0 \end{pmatrix} \\=& \det\begin{pmatrix} \color{red}0&\color{red}0&\color{red}0&\color{red}1&\color{red}1&\color{red}1 \\ 1&0&0&0&0&1 \\ \color{green}0&\color{green}0&\color{green}0&\color{green}1&\color{green}1&\color{green}0 \\ 0&0&0&0&0&1 \\ \color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}0&\color{red}0 \\ 0&0&1&0&0&0 \end{pmatrix} \\=& \det\begin{pmatrix} 0&0&0&0&0&1 \\ 1&0&0&0&0&1 \\ 0&0&0&1&1&0 \\ 0&0&0&0&0&1 \\ 0&1&0&0&-1&0 \\ 0&0&1&0&0&0 \end{pmatrix} \end{split} $$ At this point you can start developing the determinant by hand: $$ \begin{split} & \det\begin{pmatrix} 0&0&0&0&0&1 \\ 1&0&0&0&0&1 \\ 0&0&0&1&1&0 \\ 0&0&0&0&0&1 \\ 0&1&0&0&-1&0 \\ 0&0&1&0&0&0 \end{pmatrix} \\=& - \det\begin{pmatrix} 0&0&0&0&1 \\ 0&0&1&1&0 \\ 0&0&0&0&1 \\ 1&0&0&-1&0 \\ 0&1&0&0&0 \end{pmatrix} \\=& + \det\begin{pmatrix} 0&0&0&1 \\ 0&1&1&0 \\ 0&0&0&1 \\ 1&0&0&0 \end{pmatrix} \\=& - \det\begin{pmatrix} 0&0&1 \\ 1&1&0 \\ 0&0&1 \end{pmatrix} \\=& + \det\begin{pmatrix} 0&1 \\ 0&1 \end{pmatrix} \end{split} $$ This last determinant happens to be zero, so the initial determinant is zero. But this method would work perfectly even if the original matrix was in fact invertible.

In more general cases you will also have to multiply the columns and rows suitably. In this special the simplest operations are enough.

Instead of developing the determinant column by column, one can also a column operation and then another row operation: $$ \begin{split} & \det\begin{pmatrix} 0&0&0&\color{green}0&\color{red}0&1 \\ 1&0&0&\color{green}0&\color{red}0&1 \\ 0&0&0&\color{green}1&\color{red}1&0 \\ 0&0&0&\color{green}0&\color{red}0&1 \\ 0&1&0&\color{green}0&\color{red}-1&0 \\ 0&0&1&\color{green}0&\color{red}0&0 \end{pmatrix} \\=& \det\begin{pmatrix} \color{green}0&\color{green}0&\color{green}0&\color{green}0&\color{green}0&\color{green}1 \\ 1&0&0&0&0&1 \\ 0&0&0&1&0&0 \\ \color{red}0&\color{red}0&\color{red}0&\color{red}0&\color{red}0&\color{red}1 \\ 0&1&0&0&-1&0 \\ 0&0&1&0&0&0 \end{pmatrix} \\=& \det\begin{pmatrix} 0&0&0&0&0&1 \\ 1&0&0&0&0&1 \\ 0&0&0&1&0&0 \\ 0&0&0&0&0&0 \\ 0&1&0&0&-1&0 \\ 0&0&1&0&0&0 \end{pmatrix} \end{split} $$ Now one of the rows is zero, so the determinant has to vanish.

There is no unique correct way to go, but I hope the way of approaching this is clearer now.

$\endgroup$
1
$\begingroup$

First, note that row 6 is mostly '$0$'s. Next note the red values in row 2. The non-zero part of the determinant has to go through that $1$, so swap rows 2 and 5, \begin{align} \begin{vmatrix} 0&0&1&1&1&1 \\ 1&\color{red}0&0&\color{red}0&0&1 \\ 1&0&1&1&1&1 \\ 0&1&1&1&0&1 \\ 0&1&0&1&0&0 \\ 0&0&\color{red}1&0&0&0 \end{vmatrix}& = - \begin{vmatrix} 0&0&1&1&1&1 \\ 0&1&0&1&0&0 \\ 1&0&1&1&1&1 \\ 0&1&1&1&0&1 \\ 1&\color{red}0&0&\color{red}0&0&1 \\ \color{red}0&\color{red}0&1&\color{red}0&\color{red}0&\color{red}0 \end{vmatrix}= 0 \end{align} which shows that the determinant is zero.

The column solution is even easier:

\begin{align} \begin{vmatrix} 0&\color{red}0&1&1&1&1 \\ 1&\color{red}0&0&0&0&1 \\ 1&\color{red}0&1&1&1&1 \\ \color{red}0&1&1&1&0&1 \\ \color{red}0&1&\color{red}0&1&0&0 \\ \color{red}0&0&1&0&0&0 \end{vmatrix}& = 0 \end{align}

This is a medium sized matrix at most - to find the determinant for a actual large matrix ($n>100$), look up RRQR.

$\endgroup$
0
$\begingroup$

In this particular case, the fifth column is equal to the sum of the second and fourth columns; so the determinant is zero.

$\endgroup$
  • 2
    $\begingroup$ Unless we are working in $\Bbb Z_2$, this is incorrect as it is the fourth column which is the sum of the second and fifth columns. Further, this does not add anything or provide more detail that was not already stated elsewhere by the time you started writing the answer. I already made note of this very observation in my answer above. $\endgroup$ – JMoravitz Nov 9 '17 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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