Fiedler matrix determinant behaviour
4 views (last 30 days)
Show older comments
With the following command I generate a 1000x1000 Fiedler matrix from the Matlab gallery:
A = gallery('fiedler',rand(n,1));
I can see from the description the the resulting matrix A has a dominant positive eigenvalue and all the other eigenvalues are negative. Although the program I have written works fine when the Fiedler matrix has lower dimensions, when I set n to 1000 the matrix A results to be singular. Do you know why that happens and how could I fix it? I care that matrix A has a non zero determinant.
0 Comments
Answers (1)
John D'Errico
on 22 Jul 2017
Edited: John D'Errico
on 22 Jul 2017
Congratulations! You are the 10 millionth person to have a problem, not understanding why matrix determinants are a bad thing.
In fact, students get taught by teachers that you can check the singularity of a matrix using the determinant. WRONG, when this is done using floating point arithmetic. What the teacher never teaches is why determinants fail here. Much of the time, this may simply be because THEIR teacher never taught them the problems. So this meme gets passed down, teacher to student, who then becomes a teacher or writes a book or a paper, ad infinitum.
Determinants are simply the wrong thing to use to test for singularity. In fact, determinants are almost never a good thing to use at all.
Determinants are computationally nasty to compute. Yes, there are methods to compute the determinant in O(n^3) time for purely numerical problems. That is not true if you will compute a symbolic determinant by the way.
But really, the main problem with the determinant is easy to see. Consider the matrix
A = eye(1000);
Is A singular? OF COURSE NOT! A is the most non-singular matrix you can ever find. It is an identity matrix. Det will tell us that, sort of...
det(A)
ans =
1
So det thinks that A is non-singular. I think.
But how about A*5? Scaling an identity matrix by multiplying or dividing it by 5 will NOT make it singular, will it?
det(A*5)
ans =
Inf
det(A/5)
ans =
0
So it looks like A/5 is definitely singular. REALLY????????????? Who am I kidding? Who is det kidding really?
How about if we start with a known singular matrix? I recall that magic square matrices of an even order are singular. Or are they?
A= magic(4)
A =
16 2 3 13
5 11 10 8
9 7 6 12
4 14 15 1
det(A)
ans =
-1.4495e-12
det(A*1000)
ans =
-0.37107
But, if A is a magic square, then 1000*A is ALSO a magic square. A was singular, but 1000*A is not? Is det lying to me here?
The first problem is that determinants scale terribly. Second, as matrices get large, the determinant is known to be the product of the eigenvalues of the matrix. It is also the product of the diagonal elements of one of the factors of an LU decomposition. But those products are of MANY numbers. So we get an underflow or an overflow VERY rapidly as the size of your matrix gets at all large.
The point is, we can get det to tell us anything we want.
Instead, use rank!
rank(eye(1000))
ans =
1000
rank(5*eye(1000))
ans =
1000
rank(eye(1000)/5)
ans =
1000
rank(magic(4))
ans =
3
rank(magic(4)*1000)
ans =
3
Rank tells the truth.
Don't use det. At least, never use det until you know enough about linear algebra to know why you should (almost) never use det.
See Also
Categories
Find more on Linear Algebra in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!