By Nick Higham and Alan Edelman (MIT)
In a 2005 talk the second author noted that the MATLAB
det function returns an odd integer for a certain 27-by-27 matrix composed of s and s:
>> A = edelman; % Set up the matrix.
>> format long g, format compact, det(A)
However, the determinant is, from its definition, a sum of an even number (27 factorial) of odd numbers, so is even. Indeed the correct determinant is 839466457497600.
At first sight, this example is rather troubling, since while MATLAB returns an integer, as expected, it is out by . The determinant is computed as the product of the diagonal entries of the factor in the LU factorization with partial pivoting of , and these entries are not all integers. Standard rounding error analysis shows that the relative error from forming that product is bounded by , with , where is the unit roundoff, and this is comfortably larger than the actual relative error (which also includes the errors in computing ) of . Therefore the computed determinant is well within the bounds of roundoff, and if the exact result had not been an integer the incorrect last decimal digit would hardly merit discussion.
However, this matrix has more up its sleeve. Let us compute the determinant using a different implementation of Gaussian elimination with partial pivoting, namely the function
gep from the Matrix Computation Toolbox:
>> [Lp,Up,Pp] = gep(A,'p'); det(Pp)*det(Up)
Now we get the correct answer! To see what is happening, we can directly form the products of the diagonal elements of the factors:
>> [L,U,P] = lu(A);
>> d = diag(U); dp = diag(Up);
>> rel_diff_U_diags = norm((dp - d)./d,inf)
>> [prod(d), prod(dp)]
>> [prod(d(end:-1:1)), prod(dp(end:-1:1))]
We see that even though the diagonals of the two factors differ by a small multiple of the unit roundoff, the computed products differ in the last decimal digit. If the product of the diagonal elements of is accumulated in the reverse order then the exact answer is obtained in both cases. Once again, while this behaviour might seem surprising, it is within the error bounds of a rounding error analysis.
The moral of this example is that we should not be misled by the integer nature of a result; in floating-point arithmetic it is relative error that should be judged.
Finally, we note that numerical evaluation of the determinant offers other types of interesting behaviour. Consider the Frank matrix: a matrix of integers that has determinant 1. What goes wrong here in the step from dimension 24 to 25?
>> A = gallery('frank',24); det(A)
>> A = gallery('frank',25); det(A)
The Edelman matrix is available in the MATLAB function available in this gist, which is embedded below. A Julia notebook exploring the Edelman matrix is available here.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters