# Unable to calculate the Determinant of a large matrix

1. ### soopo

226
1. The problem statement, all variables and given/known data
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.

3. 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?

2. ### Hurkyl

16,089
Staff Emeritus
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....

3. ### AUMathTutor

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

4. ### Hurkyl

16,089
Staff Emeritus
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".

5. ### AUMathTutor

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

6. ### Dick

25,893
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?

7. ### soopo

226

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.

8. ### HallsofIvy

40,932
Staff Emeritus
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.

9. ### Dick

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

226
11. ### Dick

25,893
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.

12. ### soopo

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

25,893
14. ### soopo

226

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.

15. ### slider142

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

16. ### slider142

960
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(v1, ..., vn) 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(v1,...,vi, vj,...,vn) = -det(v1,...,vj, vi,..., vn).
Multilinear means that it is linear in each argument. That is if s is a number and a and b are vectors, then det(v1,...,s*a + b,...,vn) = s*det(v1,...,a,...,vn) + det(v1,...,b,...,vn).
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(v1, ..., vi, ..., vi, ..., vn), and also what happens when you add a multiple of one vector to another: det(v1, ..., vi, ..., s*vi + vj, ..., vn). 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.

Last edited: May 16, 2009
17. ### slider142

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

18. ### soopo

226

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.

19. ### slider142

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

20. ### soopo

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