Motivation: determining whether a point $p$ is above or below a plane $\pi$, which is defined by $d$ points, in a $d$-dimensional space, is equivalent to computing the sign of a determinant of a matrix of the form
A = $\begin{pmatrix}p_{1}^{\left(1\right)} & p_{1}^{\left(2\right)} & \cdots & p_{1}^{\left(d\right)} & 1\\ p_{2}^{\left(1\right)} & p_{2}^{\left(2\right)} & \cdots & p_{2}^{\left(d\right)} & 1\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ p_{d}^{\left(1\right)} & p_{d}^{\left(2\right)} & \cdots & p_{d}^{\left(d\right)} & 1\\ p^{\left(1\right)} & p^{\left(2\right)} & \cdots & p^{\left(d\right)} & 1 \end{pmatrix}$
Notes -
- When I say sign, I mean either negative, positive, or exactly zero
- The entry ${p_i}^j$ means the $j$-coordinate (e.g., $x$, $y$ and $z$ when $d$=3) of the $i$'th point in my problem. The matrix is not a Vandermonde matrix.
The resulting matrix is composed of floating-point numbers. It has no special structure, is not diagonally dominant, is not symmetric, and has no special reason to be positive-semidefinite. It might be sparse, though.
It is, however, many times nearly singular.
I'm interested in computing $\mbox{sign}(|A|)$ in a fast and robust way.
Since this is Math-SE, I'm mainly asking if there are any spectral theorems which allow this computation without explicitly computing the determinant. For example, the Greshgorin Circle Theorem could be very useful if $A$ was diagonally-dominant. Alternatively, any cheap test to identify some cases would also be helpful.