Fastest way to detect degeneracy in a matrix

Question

Given that degeneracy in a matrix seems to be 3 or more lines/vectors intersecting the same point (assumption), I am wondering about the fastest algorithm that can detect degeneracy in a matrix. Say we have:

[
  [ a, b, c, d, e, f],
  [ g, h, i, j, k, l],
  [ m, n, o, p, q, r]
]

I suppose the matrix is degenerate if these three vectors intersect? but to determine if they intersect, I think we need to have b-values, let's tack those on:

[
  [ a, b, c, d, e, f, = b1],
  [ g, h, i, j, k, l, = b2],
  [ m, n, o, p, q, r, = b3]
]

how can we go about doing this for a matrix of MxN?

At this time, I don't know if a degenerate point for vectors with N dimensions needs to intersect at the same point for all (in this case N) dimensions or just 2+...N makes more sense to me.

My best guess is that a degenerate point occurs under these conditions:

1. 3 or more vectors (vectors with dimension N)
2. intersecting at the same point in all N dimensions

but if that's not correct, please correct me. Note that degeneracy in a linear system might pertain specifically to linear optimization methods, here is some background:

http://www.columbia.edu/~cs2035/courses/ieor3608.F05/degeneracy1.pdf

https://advol.cas.mcmaster.ca/feng/4O03/LP.Degeneracy.pdf

Answer 1

In Linear Programming, the quickest way to denote a degenerate Linear Model is when the Minimum Ratio Test is the same for two or more rows on the same basis. This ensures that the other row that is not chosen will have a zero right-hand-side that will forever not contribute to the model upon future pivots.

An example (with $x_1$ being the pivot column):

\begin{array}{|c|c|}\hline BV & z & x_1 & x_2 & s_1 & s_2 & s_3 & RHS & RT \\ \hline z & 1 & -1 0 & 5 & 0 & 0 &0 &0& - \\ \hline s_1 & 0 & 2 & -4 &1 & 0 &0& 8 & 4 \\ \hline s_2 & 0 & 2 & 1&0& 1 &0& 8 & 4 \\ \hline s_3 & 0 & -7 & 25&0 & 0 &1&29 & \infty \\ \hline \end{array}

then, \begin{array}{|c|c|}\hline BV & z & x_1 & x_2 & s_1 & s_2 & s_3 & RHS & RT \\ \hline z & 1 & 0 & -15 & 0 & 0 &0 &40& - \\ \hline x_1 & 0 & 1 & -2 &1/2 & 0 &0& 4 & \\ \hline s_2 & 0 & 0 & 5&-1& 1 &0& 0& \\ \hline s_3 & 0 & 0 & 9&7/2& 0 &1&57& \\ \hline \end{array}

The next pivoting column will be $x_2$ with the $s_2$ row as the minimum ratio test produced by the $s_2$ row will be zero. Thus, watching for the minimum ratio test being the same value for multiple rows is where to detect degeneracy.

---

We could think of degeneracy like this: An extreme point occurs when $n$ constraints overlap at a certain point, with where $n$ is denoted by the current dimension of $\Bbb R^n$. If another constraint overlaps an extreme point such that there are $n+1$ constraints on one point, then it can either do three things:

1. It exists on top of the another constraints,

2. It cuts off a part of the feasible region of the model,

3. It doesn’t do either 1) or 2) and exists in the model to only overlap one extreme point shared by the other $n$ constraints.

In part 1), it would obviously be redundant, as it would be a duplicate constraint. For part 2), that third constraint would make one of the another constraints redundant as it cuts off more of the feasible region than one of the other two constraints and is better than one of the other ones. For part 3), if a constraint only exists on one point in the model that $n$ other constraints already intersect/make an extreme point at, then it would redundant as it doesn’t contribute anything more to the model than what has already been contributed by those $n$ other constraints.