Unable to calculate the Determinant of a large matrix

  1. 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. jcsd
  3. Hurkyl

    Hurkyl 15,987
    Staff Emeritus
    Science Advisor
    Gold Member

    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....
  4. This is also simple to do with the method used in intro. calculus and physics... sum of diagonal downs minus sum of diagonal ups.
  5. Hurkyl

    Hurkyl 15,987
    Staff Emeritus
    Science Advisor
    Gold Member

    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".
  6. Oh yeah, duh. I should really read these questions more closely.
  7. Dick

    Dick 25,913
    Science Advisor
    Homework Helper

    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?
  8. 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.
  9. HallsofIvy

    HallsofIvy 41,264
    Staff Emeritus
    Science Advisor

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

    Dick 25,913
    Science Advisor
    Homework Helper

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

    Dick 25,913
    Science Advisor
    Homework Helper

    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. I did the simplifications again without flipping row and multiplications:

    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.
  13. Dick

    Dick 25,913
    Science Advisor
    Homework Helper

  14. Thank you for the link!

    I do not understand one part in the document:

    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. 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. 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. 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. 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.
  19. 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. 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.
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?
Similar discussions for: Unable to calculate the Determinant of a large matrix