Unable to calculate the Determinant of a large matrix

[soopo]

Homework Statement

Find the determinant of the following matrix

0 1 1 ... 1
1 0 1 ... 1
1 1 0 ... 1
.
.
.
1 1 1 ... 0

The zeros are always at the diagonal. All other points are 1.

The Attempt at a Solution

Consider the matrix as block matrices.
We know that the determinant of the first 3 x 3 matrix is 2.

How can you calculate the determinant for the whole matrix?

 

[Hurkyl]

It seems to me the three obvious things to try are:

(1) Use recursion: find a way to compute the nxn version if you know the smaller cases already

(2) Use combinatorics: there's probably a good way to set this up as a counting problem

(3) Simplify: use row/column operations (or other ones whose effect on the determinant is known) to put the matrix into a form easier to work with

(4) Compute the determinants of the next few sizes and see if that gives you any hints


Okay, maybe (2) isn't so obvious, but the other three really should be among the very first things you think of when you try to do problems like this...

 

[AUMathTutor]

This is also simple to do with the method used in intro. calculus and physics... sum of diagonal downs minus sum of diagonal ups.

 

[Hurkyl]

This is also simple to do with the method used in intro. calculus and physics... sum of diagonal downs minus sum of diagonal ups.

The formula you cite involves all permutations on n elements -- only in the cases of n=2 and n=3 does it simplify into "sum of diagonal downs minus sum of diagonal ups".

 

[AUMathTutor]

Oh yeah, duh. I should really read these questions more closely.

 

[Dick]

Concentrate on Hurkyl's suggestion 3). You want to get lots of zeros in the matrix. Here's a hint to get you started. Subtract the first row from all of the other rows. Can you see a second step that will give you even more zeros?

 

[soopo]

Concentrate on Hurkyl's suggestion 3). You want to get lots of zeros in the matrix. Here's a hint to get you started. Subtract the first row from all of the other rows. Can you see a second step that will give you even more zeros?

Thank you for your answer!

I got an identity matrix.
This suggests me that it is determinant is 1, since the determinant of 2 x 2 identity matrix is 1.

 

[HallsofIvy]

Unfortunately, that is not true for the simplest examples. The determinant
\left|\begin{array}{cc}0 & 1 \\ 1 & 0\end{array}\right|
is -1, not 1. while the determinant
\left|\begin{array}{ccc}0 & 1 & 1 \\1 & 0 & 0\\ 1 & 1 & 0\end{array}\right|
is 2, not 1.

 

[Dick]

Thank you for your answer!

I got an identity matrix.
This suggests me that it is determinant is 1, since the determinant of 2 x 2 identity matrix is 1.

You don't get an identity matrix. Do it carefully in the 3x3 or 4x4 case. Show me how you got an identity.

 

[soopo]

You don't get an identity matrix. Do it carefully in the 3x3 or 4x4 case. Show me how you got an identity.

I got the same result again. You can see what I did in the picture:
http://dl.getdropbox.com/u/175564/problemMatrix.JPG

 

[Dick]

I got the same result again. You can see what I did in the picture:
http://dl.getdropbox.com/u/175564/problemMatrix.JPG

Some row operations change the value of the determinant. When you multiplied a row by 1/3, you multiplied the determinant by 1/3. When you flip two rows you change the sign of the determinant. That's why you got 1 instead of the correct answer of -3. Don't try to diagonalize the matrix completely in the general case. Follow my previous suggestion and see if you can see the next step.

 

[soopo]

Some row operations change the value of the determinant. When you multiplied a row by 1/3, you multiplied the determinant by 1/3. When you flip two rows you change the sign of the determinant. That's why you got 1 instead of the correct answer of -3. Don't try to diagonalize the matrix completely in the general case. Follow my previous suggestion and see if you can see the next step.

I did the simplifications again without flipping row and multiplications:
http://dl.getdropbox.com/u/175564/problemMatrix2.png

The determinant of the new reduced matrix is more difficult to calculate than that of the previous reduced matrix. I get that the determinant of the new 3x3 matrix is -1.

I cannot see directly how to get the determinant of 4x4 matrix. The solution is perhaps by considering block matrices.

 

[Dick]

The technique for getting the determinant of the 4x4 matrix is called 'expansion by minors'. Look it up or try looking at http://people.richland.edu/james/lecture/m116/matrices/determinant.html I would use it to expand across the last row.

 

[soopo]

The technique for getting the determinant of the 4x4 matrix is called 'expansion by minors'. Look it up or try looking at http://people.richland.edu/james/lecture/m116/matrices/determinant.html I would use it to expand across the last row.

Thank you for the link!

I do not understand one part in the document:
http://dl.getdropbox.com/u/175564/matrixProblemDeterminant.JPG

I multiply the third row by .5 and add it to the second row, then the determinant changes from 6 to 3.

This seems to be a contradiction with the sentence "If you multiply a row or column by a non-zero constant and add it to another row or column, replacing that row or column, there is no change in the determinant."

The second paragraph gives a warning about setting pivot points only to one. This suggests me that this is apparently what I did wrong.

However, I do not know exactly what I did wrong.

 

[slider142]

Hurkyl's hint 1) is also good if you know the geometric interpretation of determinants. What kind of geometry is present in the image of the standard basis vectors under the transformation in the matrix? This should give you a simple formula for the nxn form that doesn't involve complicated expansions.

 

[slider142]

Thank you for the link!

I do not understand one part in the document:
http://dl.getdropbox.com/u/175564/matrixProblemDeterminant.JPG

I multiply the third row by .5 and add it to the second row, then the determinant changes from 6 to 3.

This seems to be a contradiction with the sentence "If you multiply a row or column by a non-zero constant and add it to another row or column, replacing that row or column, there is no change in the determinant."

The second paragraph gives a warning about setting pivot points only to one. This suggests me that this is apparently what I did wrong.

However, I do not know exactly what I did wrong.

I don't know if you have a unifying picture of what a determinant is, or just a list of seemingly unrelated properties.
If instead of a matrix, you see the square array as an ordered list of n n-dimensional vectors, and we let the determinant be a function of those n vectors, we have the multilinear function det(v₁, ..., v_n) defined to be an alternating multilinear map from Vx...xV (n times) into R.
Alternating means that a single transposition of the arguments changes the sign of the determinant. That is to say det(v₁,...,v_i, v_j,...,v_n) = -det(v₁,...,v_j, v_i,..., v_n).
Multilinear means that it is linear in each argument. That is if s is a number and a and b are vectors, then det(v₁,...,s*a + b,...,v_n) = s*det(v₁,...,a,...,v_n) + det(v₁,...,b,...,v_n).
These are all the defining properties of the determinant; you may derive all others from these two properties. For example, see what happens when you put two of the same vectors in the determinant: det(v₁, ..., v_i, ..., v_i, ..., v_n), and also what happens when you add a multiple of one vector to another: det(v₁, ..., v_i, ..., s*v_i + v_j, ..., v_n). Look and see what happens when one of the vectors is actually just a linear combination of some of the other vectors.
You can also calculate the determinant using these, although it is just as tedious as expanding by minors (Laplace's expansion). ;)

Why is the determinant defined to be like this? Historically, the determinant was an expression that came out of solving systems of linear equations. In other words, to derive the formula for the determinant of a 4x4 matrix, you could go ahead and solve a general system of 4 linear equations in 4 variables. The denominator of each fraction that you got as the expression for each variable would be the same expression, called the determinant of the system. Since it was the denominator, a determinant of 0 meant the system could not have a unique solution. Brilliant minds separated the algebra of the determinant from simply solving systems of linear equations and gave us other ways of calculating and visualizing determinants; one way is as the signed volume of the parallelepiped formed from the vectors making up the matrix.
That is, if we have an ordered list of n vectors in n-dimensional Euclidean space, we define the determinant to be the n-volume of the parallelepiped spanned by those vectors (2-volume is interpreted as area, 1-volume as length) if the vectors are oriented such that they could be rotated and scaled back to the standard basis without using negative scalars, and the negative volume otherwise. From this description, we then write down what properties we want n-volume to have, from whence we get the multilinear property. The alternating property comes from caring about the orientation of the vectors.
An alternate approach is through exterior algebra or geometric algebra, from which the determinant arises naturally from being a certain unique map.

 

[slider142]

Thank you for the link!

I do not understand one part in the document:
http://dl.getdropbox.com/u/175564/matrixProblemDeterminant.JPG

I multiply the third row by .5 and add it to the second row, then the determinant changes from 6 to 3.

This seems to be a contradiction with the sentence "If you multiply a row or column by a non-zero constant and add it to another row or column, replacing that row or column, there is no change in the determinant."

The second paragraph gives a warning about setting pivot points only to one. This suggests me that this is apparently what I did wrong.

However, I do not know exactly what I did wrong.

You actually did two operations. First, you added -1/2 times the last row to the second row. By multilinearity, this had no effect on the determinant. The second thing you did was multiply the last row by 1/2. By multilinearity, the new determinant is 1/2 times the old determinant, which is (1/2)*6 = 3.

 

[soopo]

You actually did two operations. First, you added -1/2 times the last row to the second row. By multilinearity, this had no effect on the determinant. The second thing you did was multiply the last row by 1/2. By multilinearity, the new determinant is 1/2 times the old determinant, which is (1/2)*6 = 3.

Thank you for your answers!

So the sentence seems to mean that you can add any multiple of the row
A to the row B, without changing the determinant.
However, you cannot multiply the row A without changing the determinant.

 

[slider142]

Thank you for your answers!

So the sentence seems to mean that you can add any multiple of the row
A to the row B, without changing the determinant.
However, you cannot multiply the row A without changing the determinant.

That is exactly correct, with the addition that you know the exact value that you are changing the determinant by. So if you see a matrix that has rows that are multiples/linear combinations of matrices with determinants you already know, you don't have to go through the whole rigamarole again, just use alternating multilinearity to get the new determinant. Ie., a 3x3 diagonal matrix which has two 3's and one 1 on the diagonal and zeros everywhere else should have the determinant 3*3*det(I) = 9 where I is the 3x3 identity matrix with trivial determinant of 1.

 

[soopo]

The technique for getting the determinant of the 4x4 matrix is called 'expansion by minors'. Look it up or try looking at http://people.richland.edu/james/lecture/m116/matrices/determinant.html I would use it to expand across the last row.

Thank you Dick!

I got the correct answer finally.
The Laplace expansion is much more powerful than Sarrus for 3x3, when you have many zeros.

 

[larstuff]

Homework Statement

Find the determinant of the following matrix

0 1 1 ... 1
1 0 1 ... 1
1 1 0 ... 1
.
.
.
1 1 1 ... 0

The zeros are always at the diagonal. All other points are 1.

The Attempt at a Solution

Consider the matrix as block matrices.
We know that the determinant of the first 3 x 3 matrix is 2.

How can you calculate the determinant for the whole matrix?

The determinant must eighter be 0 og -1. If the number of rows are even, then the determinant will be zero. If the number of rows are odd, the determinant will be -1.

 

[Hurkyl]

The determinant must eighter be 0 og -1. If the number of rows are even, then the determinant will be zero. If the number of rows are odd, the determinant will be -1.

First, we do not give answers here -- not only does that constitute cheating, but it deprives the poster of a chance to learn.

Secondly, wrong answers are even worse. I'm boggled how you came up with that answer, since it fails in every case I checked: the 1x1, 2x2, and 3x3 cases.

 

[larstuff]

Homework Statement

Find the determinant of the following matrix

0 1 1 ... 1
1 0 1 ... 1
1 1 0 ... 1
.
.
.
1 1 1 ... 0

The zeros are always at the diagonal. All other points are 1.

The Attempt at a Solution

Consider the matrix as block matrices.
We know that the determinant of the first 3 x 3 matrix is 2.

How can you calculate the determinant for the whole matrix?

Try solving for the det. for matrixes from smaller to bigger. This will give an interesting result. Start with a 1x1 matrix, then a 2x2 matrix, and so on. A pattern will then emerge.
The tricky part is to show why this pattern will continue. It all has to do with the diagonals - how many of them are "counting" in each direction.

 

[soopo]

First, we do not give answers here -- not only does that constitute cheating, but it deprives the poster of a chance to learn.

Secondly, wrong answers are even worse. I'm boggled how you came up with that answer, since it fails in every case I checked: the 1x1, 2x2, and 3x3 cases.

This suggests me that the determinant differs for nxn, n-1 x n-1 and n-2 x n-2 matrices.

I assumed that I get the determinant of all square matrices of the specific form if I calculate the determinant of the 4x4 matrix. Thus, the determinant (-3) which I got is only for 4x4 matrix.

The next problem is to know how to calculate the determinant of 5x5 matrix. I assume that the pattern remains such that diagonal has zeros and the rest of the points are ones.

I got the following results for the determinants of different matrices

n nxn
1 0
2 -1
3 2
4 -3
5 -2
6 1

There seems to be some pattern perhaps. I would suggest by the pattern that the determinants continue as follow

n nxn
7 0
8 -1
9 2
10 3
11 -2
12 1
13 0

However, my hypothesis is apparently wrong for the larger matrices.

 

[Count Iblis]

Have you considered the matrix you get by replacing row i by row i minus row 1 for all i > 1?

 

[soopo]

Have you considered the matrix you get by replacing row i by row i minus row 1 for all i > 1?

I actually did the following: I subtracted the second row from other rows.
This is a similar way as your suggestion, to get a lot of zeros to the matrix.

 

[Count Iblis]

I actually did the following: I subtracted the second row from other rows.
This is a similar way as your suggestion, to get a lot of zeros to the matrix.

Do you know the definition of a determinant as a summation over permutations?

 

[Dick]

I actually did the following: I subtracted the second row from other rows.
This is a similar way as your suggestion, to get a lot of zeros to the matrix.

It's similar, but the resulting matrix is less easy to describe than subtracting the first row from the other rows. It will be easier to see what happens in the nxn case if you do it that way.

 

[soopo]

Do you know the definition of a determinant as a summation over permutations?

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?

 

[soopo]

It's similar, but the resulting matrix is less easy to describe than subtracting the first row from the other rows. It will be easier to see what happens in the nxn case if you do it that way.

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.

 

[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?