Unable to calculate the Determinant of a large matrix

Count Iblis

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

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

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:

[tex]\begin{pmatrix}
0&1&1&1&1\\
1&-1&0&0&0\\
1&0&-1&0&0\\
1&0&0&-1&0\\
1&0&0&0&-1
\end{pmatrix}[/tex]

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

Dick

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

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

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

larstuff

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

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

Dick

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

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

Yep, that works.

soopo

Thank you for your help!

Dick

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.)