I seem to recall that some time in the mid 1980's, James Davenport was working on an algorithm which guaranteed that an integer matrix is singular by evaluating it modulo a selection of primes. However, I have no idea what became of the project. WFL On 10/7/20, Victor Miller <victorsmiller@gmail.com> wrote:
The rank cannot be overestimated. If the matrix has rank r, and the dimension in n by n for n > r, there is all r+1 by r+1 submatrices have symbolic determinant 0, and so any specialization of them will also have determinant 0. Conversely, if all r+1 by r+1 submatrices have determinant 0 then the rank is <= r.
On Wed, Oct 7, 2020 at 6:13 PM Henry Baker <hbaker1@pipeline.com> wrote:
Suppose you're using a symbolic algebra system & want to estimate the rank of a matrix whose entries are symbolic expressions involving many different variables.
My intuition tells me that I should be able to randomly guess values for all of the variables, numerically compute the rank for that assignment of variables, and do it again several more times.
The *maximum* rank achieved should be close to the actual symbolic rank of the matrix.
2 cases: integers and floating point.
If the symbolic expressions enable exact integer values, then the rank could be computed using arbitrary-precision arithmetic. However, it might be more efficient to do the computation modulo a large number of different primes.
If we work in floating point, the expressions could be incredibly ill-conditioned, in which case telling the difference between very small numbers and actual zeros could be impossible.
Other than such ill-conditioning, is it possible that the rank could be *over* estimated by such random sampling?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun