Unable to calculate the Determinant of a large matrix

[Count Iblis]

I am not completely sure what you mean.

I read the article about permutations in Wikipedia's article about determinants.
However, I am not sure what they mean without a concrete example.
Could you give one, please?

Suppose you have some matrix of which the rows contain zeroes in all but one position. E.g. consider the matrices:

\begin{pmatrix}0&amp;1&amp;0\\<br /> 1&amp;0&amp;0\\<br /> 0&amp;0&amp;1\end{pmatrix}

\begin{pmatrix}0&amp;1&amp;0&amp;0\\<br /> 1&amp;0&amp;0&amp;0\\<br /> 0&amp;0&amp;1&amp;0\\<br /> 0&amp;1&amp;0&amp;0<br /> \end{pmatrix}

Can you then quickly see if the determinant is zero?

 

[soopo]

Suppose you have some matrix of which the rows contain zeroes in all but one position. E.g. consider the matrices:

\begin{pmatrix}0&amp;1&amp;0\\<br /> 1&amp;0&amp;0\\<br /> 0&amp;0&amp;1\end{pmatrix}

\begin{pmatrix}0&amp;1&amp;0&amp;0\\<br /> 1&amp;0&amp;0&amp;0\\<br /> 0&amp;0&amp;1&amp;0\\<br /> 0&amp;1&amp;0&amp;0<br /> \end{pmatrix}

Can you then quickly see if the determinant is zero?

I can see quickly that the determinant of the first matrix is minus one, while the determinant of the last matrix is zero.

 

[Hurkyl]

I can see quickly that the determinant of the first matrix is one,

Incorrect.

 

[soopo]

Incorrect.

You are right.
There was a mistake in my first determinant: it is minus one, not one.
The second determinant is still zero.

 

[Count Iblis]

I can see quickly that the determinant of the first matrix is one, while the determinant of the last matrix is zero.

The determinant of the first matrix is minus one, but I think you see what is going on here. In the first matrix the positions of the ones in the rows from 1 to 3 was:

2, 1, 3

In case of the second matrix the positions of the ones starting from the fist to the last are:

2, 1, 3, 2

In the first case the numbers 2, 1, 3 is a permutation of the numbers 1, 2, 3 (i.e. the 2,1,3, is just the list 1,2,3 written down in a different order) while in the second case we don't get a permutation of the numbers 1, 2, 3, 4. The number 4 is missing and the number 2 is appearing twice.

Do you see that the list of positions of the ones always has to be a permutation of the row numbers for the determinant to be nonzero?

 

[soopo]

Do you see that the list of positions of the ones always has to be a permutation of the row numbers for the determinant to be nonzero?

I can see that now clearly.
Thank you for pointing that out! :)

I investigated matrixes before by having a goal to make an identity matrix.
This way, I had an implicit idea that the ones always has to be a permutation
of the row numbers for the determinant to be nonzero.

This caused me often to forget to change the sign of the determinant when flipping rows,
or to multiply it with x if I multiplied a column/row by x.

 

[conway]

Do you see that the list of positions of the ones always has to be a permutation of the row numbers for the determinant to be nonzero?

That's an excellent point, Iblis. I have been trying to work out the patterns and it is absurdly difficult for me. I wonder if the OP knows about odd and even permutations? In evaluating a determinant, the odd permutations are subtracted from the even permutations: in other words, imagine you are just multiplying the elements along the diagonal, and then swapping rows in and out to change the diagonal elements: each time you swat a pair of rows, you change the sign of the product. I've done the first six matrices (up to 6x6) and I think there's a simple pattern. I know this is a homework thread but it seems prohibitively difficult for the precalculus level...so I'm going to show my work for the 5x5 matrix. Also because I am showing off...

Here goes:

There are 120 possible permutations of the five rows and they can be listed in seven different classes according to how many elements they move. I'm going to use the group theory notation where (123) means 1 goes to 2, 2 goes to 3, 3 goes back to 1, and 4 and 5 are unmoved:

Class 1: Similar to (12345) where everything moves: 24 permutations

Class 2: Similar to (1234) (5) where only four rows move: 30 permutations

Class 3: Similar to (123) where only 3 rows move: 20 permutations

Class 4. Similar to (123)(45) where all 5 rows move (with incomplete mixing!) 20 permutations

Class 5: Similar to (12)(34) where 4 rows move: 15 permutations

Class 6: similar to (12) where only 2 rows move: 10 permutations

Class 7: the identity e, where nothing moves: 1 permuation

A quick check shows I've accounted for all 120 possible permutations of 5 rows. Interesting that each class has a definite parity...members of Class 2, for instance, can all be generated by a composition of 3 simple swaps, hence Clas 2 has odd parity.

Since we need to clear all the zeroes out of the diagonal, we need only be interested in those classes for which every row gets moved. So only Class 1 and Class 4 need be counted. The 24 permutations in Class 1 are even, so they give a net of +24; the 20 permutations in Class 4 are odd so they net -20. Total = 4, which is the determinant of the 5x5 matrix.

 

[Count Iblis]

If you first replace row i by row i minus row 1 for all i > 1, you get the matrix:

\begin{pmatrix}<br /> 0&amp;1&amp;1&amp;1&amp;1\\<br /> 1&amp;-1&amp;0&amp;0&amp;0\\<br /> 1&amp;0&amp;-1&amp;0&amp;0\\<br /> 1&amp;0&amp;0&amp;-1&amp;0\\<br /> 1&amp;0&amp;0&amp;0&amp;-1<br /> \end{pmatrix}

And if you now evaluate the determinant by summing over permutations, it is even simpler.

 

[Dick]

The last row has the following elements
1 0 0 ... -1

This result should suggest me something, since Dick emphasizes it.
However, I am not sure about it.

The main diagonal has now minus ones except the first element is 0.

soopo, you've almost got it. Subtracting the first row from all the other rows gives you a matrix with ones in first row and first column and minus ones in the diagonal except for a zero in the top left corner. Now add all of the rows of this matrix to the first row. Expand in minors along the first row.

 

[soopo]

soopo, you've almost got it. Subtracting the first row from all the other rows gives you a matrix with ones in first row and first column and minus ones in the diagonal except for a zero in the top left corner. Now add all of the rows of this matrix to the first row. Expand in minors along the first row.

Thank you Dick for showing me the way!

I now see what you mean.
I get a lot of zeros for the top rows all matrices.

It seems that the determinant is 4 if there are odd number of rows, while -4 if there are even number of rows in the column.

 

[Dick]

Thank you Dick for showing me the way!

I now see what you mean.
I get a lot of zeros for the top rows all matrices.

It seems that the determinant is 4 if there are odd number of rows, while -4 if there are even number of rows in the column.

Now how are you getting 4? Or -4 for that matter. What does your final matrix look like?

 

[larstuff]

Thank you Dick for showing me the way!

I now see what you mean.
I get a lot of zeros for the top rows all matrices.

It seems that the determinant is 4 if there are odd number of rows, while -4 if there are even number of rows in the column.

That's not what I am getting here.
I would have you start with the 1x1 matrix, find the det for that one, continue with the 2x2 matrix.
Just use the simplest way of calculating the determinant (diagonal --> right --> down = + and diagonal --> left -->down = -).

 

[soopo]

Now how are you getting 4? Or -4 for that matter. What does your final matrix look like?

Please, see the picture for what I have done:
http://dl.getdropbox.com/u/175564/matrixProblemDeterminant2.JPG

 

[Dick]

Please, see the picture for what I have done:
http://dl.getdropbox.com/u/175564/matrixProblemDeterminant2.JPG

Ok, so you've got it right for a 5x5 matrix. The determinant is 4. But you don't always get 4 if the matrix is nxn. What's the general result?

 

[Avodyne]

Here is another approach to the problem. Write the matrix as A-I, where A is the matrix for which every entry is 1. If we could find the eigenvalues of A, it would be easy to calculate the determinant. Compute A²; you should find that A² = nA. What does that tell you about the allowed eigenvalues of A?

 

[Hurkyl]

Ha! I like that method, but you missed a neat trick. We can just do matrix algebra now -- we can find the characteristic polynomial for A, and thus for the original matrix.

 

[soopo]

Ok, so you've got it right for a 5x5 matrix. The determinant is 4. But you don't always get 4 if the matrix is nxn. What's the general result?

I get the following general result

for rows n >= 2

det(n) = (n - 1) * (-1)^(n+1)

A few examples of determinants:

n det
2 -1
3 2
4 -3
5 4
6 -5
...
777 776

The result should now be correct.

 

[Dick]

I get the following general result

for rows n >= 2

det(n) = (n - 1) * (-1)^(n+1)

A few examples of determinants:

n det
2 -1
3 2
4 -3
5 4
6 -5
...
777 776

The result should now be correct.

Yep, that works.

 

[soopo]

Yep, that works.

Thank you for your help!

 

[Dick]

Ha! I like that method, but you missed a neat trick. We can just do matrix algebra now -- we can find the characteristic polynomial for A, and thus for the original matrix.

I can see how that will get you a minimal polynomial, but I don't see how to get to the characteristic polynomial. How do you count the multiplicities?

 

[Avodyne]

I'm not sure what Hurkyl had in mind, but you can get the multiplicities by noting that Tr A = n. (I had this in my original post, but then edited it out so as not to be giving out too much info to the OP.)

 

[Dick]

I'm not sure what Hurkyl had in mind, but you can get the multiplicities by noting that Tr A = n. (I had this in my original post, but then edited it out so as not to be giving out too much info to the OP.)

Oh, yeah. That works. Thanks!

 

[Count Iblis]

Problem solved, it is time to http://arxiv.org/abs/math/9902004"

 

[Dick]

Why? This ones been solved at least two ways. I'm sure there's a million other ways. I'm still kind of leaning to the row reduction as the simplest.

 

[Hurkyl]

I can see how that will get you a minimal polynomial, but I don't see how to get to the characteristic polynomial. How do you count the multiplicities?

A is diagonalizable, and we know its rank.

 

[conway]

Problem solved, it is time to http://arxiv.org/abs/math/9902004"

Well, there's one last point that I'm wondering about: where does this problem come from? Is it just a math question or does it relate to some actual physics or anything else?

 

[soopo]

I'm not sure what Hurkyl had in mind, but you can get the multiplicities by noting that Tr A = n. (I had this in my original post, but then edited it out so as not to be giving out too much info to the OP.)

What is the Tr A = n?
Do you mean transpose of A equals to n that is the size of the matrix?

 

[Count Iblis]

What is the Tr A = n?
Do you mean transpose of A equals to n that is the size of the matrix?

"Tr" means the "trace", i.e. the sum of all the diagonal elements. This is invariant under a change of basis:

Tr[A] = sum over i of A_{i,i}


Tr[S^(-1)AS] =(ommitting summation signs, we are summing over all epeated indices) =

S^(-1)_{i,k}A_{k,j}S_{j,i}= Tr[***^(-1)] = Tr[A]

 

[soopo]

"Tr" means the "trace", i.e. the sum of all the diagonal elements. This is invariant under a change of basis:

Tr[A] = sum over i of A_{i,i}


Tr[S^(-1)AS] =(ommitting summation signs, we are summing over all epeated indices) =

S^(-1)_{i,k}A_{k,j}S_{j,i}= Tr[***^(-1)] = Tr[A]

How can you solve the problem by using trace?
I cannot see how you can proceed with them.