3
$\begingroup$

Is there a reliable method for testing how invertible a Hermitian Toeplitz matrix is without going through the work of actually inverting it?

A determinant is obviously easy to compute, but I'm not sure what threshold to compare it against.

The algorithm I am using is Levinson recursion. The function can detect the divide-by-zero condition, but I am interested in also detecting/scoring the matrices that are almost singular.

1 Answers 1

2

It's the condition number $\kappa$ you should be looking at, not the determinant. Since Levinson is an O(n²) method, you can hook it up to the Hager-Higham condition estimator for determining how near to singularity your matrix is. The classical heuristic is that one loses $\log_{b}\kappa$ base-$b$ significant figures in solving a linear system.

  • 1
    See also [Mathworld](http://mathworld.wolfram.com/ConditionNumber.html) and [Wikipedia](http://en.wikipedia.org/wiki/Condition_number)'s descriptions of the condition number. If you are using some linear algebra library, note that many calculate the reciprocal of the condition number by default.2010-09-15