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&1&0\\ 1&0&0\\ 0&0&1\end{pmatrix}$$

$$\begin{pmatrix}0&1&0&0\\ 1&0&0&0\\ 0&0&1&0\\ 0&1&0&0 \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&1&0\\ 1&0&0\\ 0&0&1\end{pmatrix}$$

$$\begin{pmatrix}0&1&0&0\\ 1&0&0&0\\ 0&0&1&0\\ 0&1&0&0 \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?